一个关于PostgreSQL使用组合索引的问题
近期阅读了《数据库查询优化器的艺术》这本书，对PG和Mysql优化器技术的轮廓有了一定了解。在阅读的过程中，因为知识背景和书本身的表述问题产生了许多困惑，这里就分享对其中一个困惑的探索过程作为看完书的总结。
在这本书的第十八章，关于PG和Mysql的优化器对于索引的优化能力对比中的一段让我困惑不已。如图一所示，单独使用组合索引的后半部分作为查询条件使用了顺序扫描，而再加上一个与索引无关的过滤条件，扫描方式竟然就变成了BitMap Index Scan。
考虑到该书针对的PG是9.2.3，这么个老版本，难道是这是两个人写的代码，一个优化了一个忘记了？但是，仔细观察这两个执行计划的代价发现了一丝不对劲，因为两者代价的差值是32.13-32.09=0.04。这个值太小了，而且是加了个过滤条件将预测到结果集行数从9降到3产生的。直观上感觉这个过滤条件能带来的裁剪效果应该不止这么点，所以很可能是索引扫描本身代价过高拖累了谓词优化效果。
PostgreSQL中的组合索引
为了分析这个问题，首先了解一下组合索引的大体结构，即怎么样才能只使用组合索引的后半部分完成查询。目前以及有很多讲索引结构的文章，想详细了解的话推荐德歌的《深入浅出PostgreSQL B-Tree索引结构》，本文就简要概括一下。
PG默认创建的索引都是B-Tree索引，整体上索引文件和表一样是块页式存储，元信息存储在根页，所以查询的时候也是从根页一层一层的找到实际存储地址。如果没有指定组合索引的开头一列，那么可以基于B-Tree层层过滤，把所有满足后半部分值要求的索引页都读取到内存，这时很容易就读取了整个索引文件，当数据量大的时候代价较高。
上文提及的问题中的索引文件结构如图二所示，其中meta page中记录了root page是1，然后下面的root page详情则直接指明了到具体heap page的偏移量以及每一项索引的取值。因此，问题中的索引扫描至少要读取两个索引页，同时在root page的data中顺序查找满足条件的索引，如果有多级的话能够过滤掉一些一定不包含结果的索引项。
什么是BitMap Heap Scan
图二的执行计划中可以看到有个BitMap Index Scan，看起来似乎是基于位图索引的扫描。然而，PG默认创建的索引是基于B-tree，同时也并不支持位图索引，不过PG会在索引创建时建立位图表（Bitmap Heap Table）。有一段描述BitMap Heap Scan的话：
A plain indexscan fetches one tuple-pointer at a time from the index,
and immediately visits that tuple in the table. A bitmap scan fetches
all the tuple-pointers from the index in one go, sorts them using an
in-memory "bitmap" data structure, and then visits the table tuples in
physical tuple-location order
上面的意思是说，普通的索引扫描一次读一条索引项，而BitMap Heap Scan一次性将满足条件的索引项全部取出，并在内存中进行排序, 然后根据取出的索引项访问表数据。由于BitMap Heap Scan会输出整个数据块的数据，因此需要recheck，对输出的索引项进行过滤。就我个人理解，BitMap Heap Scan就是针对有多个索引项满足条件时，通过饱和式的索引页读取结合排序大幅减少随机读取，提升I/O效率。
问题的真相
在理解完背景知识之后，开始正式探索真相。首先本地复现书中的实验，具体SQL语句如下：
create table tkey(key_pk int, key_part1 int, key_part2 int, nokey int, primary key(key_pk));
create index tkey_multi_k on tkey(key_part1,key_part2);
insert into tkey values(1,1,1,1);
insert into tkey values(2,2,1,1);
insert into tkey values(3,2,2,1);
insert into tkey values(4,3,1,1);
insert into tkey values(5,3,2,1);
insert into tkey values(6,3,3,1);
insert into tkey values(7,4,1,1);
insert into tkey values(8,4,2,1);
insert into tkey values(9,4,3,NULL);
基于PG 9.2.3本地分别执行explain select * from tkey where key_part2=2;和explain select * from tkey where key_part2=2 and nokey>2;两条SQL语句查看执行计划，如下图三所示。从图中可以看到，Seq Scan算子的代价较书中少了0.01，其他的与书中一致，完成实验复现。
为了证实可以使用基于索引的扫描，使用set session enable_seqscan=false;将顺序扫描禁止，再查询执行计划，得到结果如图四所示。在关闭顺序索引后，两条查询最终都使用了BitMap Index Scan，但是实际估算出来的代价比顺序查找还低了0.05。懵逼！玄学？
结合书上第七章的源码分析，PG选择扫描方式的时候会依次搜索顺序扫描、索引扫描和tid扫描。针对索引扫描找到postgresql-9.2.3/src/backend/optimizer/path/indexpath.c:create_index_paths函数，然后这个会调用/Users/yijiang/workspace/postgresql-9.2.3/src/backend/optimizer/util/pathnode.c:add_path函数添加具体查询计划。add_path函数在添加路径时会对比新路径和已有的老路径，判断是不是有添加的必要，以及是否要删掉已经搜索出来的老路径。具体对比项包括代价、排序方式和依赖的上游信息量。其中最重要的一点就是代价对比，在源码中有一段：
/*
* Do a fuzzy cost comparison with 1% fuzziness limit. (XXX does this
* percentage need to be user-configurable?)
*/
costcmp = compare_path_costs_fuzzily(new_path, old_path, 1.01);
这个一句的意思是忽略1%以内的代价差进行对比，也就是实验中的顺序扫描方法和自身差异在0.32以内的计划，其代价都认为是一样的。所以仅低0.05的BitMap Index Scan被认为与顺序扫描代价一致，同时排序方式一致，且都没有上游依赖项。最终，在PG 9.2.3看来这两个扫描方式一致，所以新的路径就不用加了，最终索引扫描因为先来后到的问题被踢出局。至此，上文中的现象都得到了解释。
由于PG 9.2.3版本比较太老，所以基于更新的PG 10.5再进行一轮实验，看看是否有什么差异。实验结果如图五(a)所示，发现两个查询都变成BitMap Index Scan，同时代价也比之前估算的更高了一些。在看关闭索引扫描后的图五(b)，此时代价高了超过1%，说明在新版的PG对顺序扫描的代价计算进行了修订，同时也意味着查询优化器给出的代价看似精确，但也仅仅是一次估算，需要不断的调整。
因此，显示的执行计划与预期不一致，并一定某个优化规则不支持，而是经过了复杂的可行解搜索，发现了朴素的做法实际代价更靠谱，本质上还是代价权衡的结果。
讨论
上文中关于代价对比有个忽略1%误差的设定，本人猜测是考虑到代价估算本身就是基于经验的启发式计算，同时也很难基于数值完全刻画出具体算子的执行代价，因为越是复杂的计算越是难以估计其资源消耗（如上文中PG 10.5的索引扫描代价估计）。因此，估算的代价本身就有一定误差，而在大数据的场景下误差会被放大，所以设定1%作为误差范围，同时优先搜索简单路径，尽可能尝试朴素做法，达到提升查询效率的目的。
