PostgreSQL如何通过AND运算符组合两个B-tree索引？

问题背景 #

我对PostgreSQL官方文档中关于通过AND运算符组合两个B-tree索引的描述存疑：文档指出当查询包含WHERE "col1" = 'A' AND "col2" = 'B'子句，且col1和col2均建有B-tree索引时，会为每个索引在内存中建立对应每行的位图，再通过AND运算得到匹配结果集。

我认为这一方式极不合理，尤其是针对B-tree索引，这意味着查询时间与内存消耗均会随数据库总行数线性增长，与实际匹配行数无关，将导致PostgreSQL在诸多场景下无法使用。我希望了解：稀疏匹配的PostgreSQL查询是否真的随总行数线性扩展？

我更倾向于认为索引是通过直接相交B-tree节点实现组合的，比如构建存储唯一值的B-tree，在每个叶子节点存储对应值的id堆，通过相交堆来获取共同行。

核心解答 #

1. 位图扫描的实际逻辑：并非基于总行数的线性消耗 #

你对位图扫描的理解存在偏差：PostgreSQL的位图扫描不是为每行建立一个位，而是以数据块（page）为单位构建位图。每个位对应一个数据块，标记该块中是否存在匹配条件的行。这种设计下，内存消耗和查询时间只与匹配条件涉及的数据块数量相关，和数据库总行数完全无关。

2. 稀疏匹配查询的性能表现 #

对于稀疏匹配（即匹配行数极少的场景），PostgreSQL的处理不会随总行数线性扩展：

• 首先，两个B-tree索引会分别快速定位到col1='A'和col2='B'对应的叶子节点，获取匹配行的TID（元组标识符，包含块号和行号）集合；
• 随后将这些TID转换为位图（仅标记包含匹配行的数据块）；
• 最后对两个位图执行AND操作，得到同时满足两个条件的数据块列表，再批量读取这些块并筛选出最终匹配行。

整个过程的时间和内存开销仅由匹配行的数量（以及对应的块数）决定，和数据库总行数没有线性关联。

3. 为何不直接相交TID堆？ #

你的思路（相交B-tree叶子节点的TID集合）和PostgreSQL的底层逻辑有相似性，但位图扫描是更优的IO优化策略：

• 如果直接合并两个TID列表，可能会多次重复访问同一个数据块（比如同一个块中有多个匹配行）；
• 位图扫描先标记所有需要访问的块，再一次性批量读取这些块，大幅减少磁盘IO的次数，提升查询效率。

内容的提问来源于stack exchange，提问作者Luke Hutchison