从索引命中到查询结果

前几篇沿着 B-tree 看过搜索、分裂和旧记录清理。搜索走到叶子页，找到匹配的 Key，拿到 Heap TID。TID 就是 (block, offset)，分别是页号和页内行指针的编号。

上一篇《B-tree 里的重复 Key 与旧记录的清理》处理的是索引内部的空间。这一次，TID 要离开索引，去表里找记录；沿着它往后走，索引和表之间的分工才真正露出来。版本的可见性、索引条件要不要复验、剩下的过滤怎么处理，会依次出现在这条路上；几种索引扫描计划里的 Recheck Cond、Filter 和 Heap Fetches，就是它们留下的痕迹。

下面的实测在 PostgreSQL 18 上完成，建表和造数 SQL 放在文末。

同一个条件，为什么出现了两次

先看一张有一百万行的表 t_scan，索引只建在 grp 上。grp = 42 对应一千条记录，其中五百条满足 flag = 1。

EXPLAIN (ANALYZE, COSTS OFF, TIMING OFF)
SELECT id, payload
FROM t_scan
WHERE grp = 42 AND flag = 1;

这次走的是 Bitmap 路径。省略部分字段后，计划如下：

Bitmap Heap Scan on t_scan (actual rows=500.00 loops=1)
  Recheck Cond: (grp = 42)
  Filter: (flag = 1)
  Rows Removed by Filter: 500
  Heap Blocks: exact=1000
  ->  Bitmap Index Scan on t_scan_grp_idx
        (actual rows=1000.00 loops=1)
        Index Cond: (grp = 42)

从下往上看，B-tree 按 Index Cond 里的 grp = 42 找出一千个候选位置，Bitmap Heap Scan 再去表里取记录。flag 没有参与索引定位，要等记录取出来才检查；五百行不满足，最后留下五百行。

Heap Blocks: exact=1000 说明这一千个候选散在一千个页上，页内 Offset 都记得很清楚，这次没有出现 Lossy 页。

grp = 42 已经交给 B-tree 判断过，为什么上面又出现一个相同的 Recheck Cond？

Bitmap 记不下 Offset 以后

B-tree 确实已经判断过这个等值条件。不过，从索引到表，中间还经过了一份 Bitmap。它是按 Heap Page 组织的候选位置集合；保存这些位置时，未必能把原来的精度一直保留下来。

普通 Index Scan 取得一个 TID，就可以去表里找记录。Bitmap 路径先收集候选位置，再按 Heap Block 的顺序访问，把同一页上的候选放在一起处理。索引顺序和 Heap 的物理顺序差得远时，这样能减少一些来回跳转；代价是要先构造 Bitmap，B-tree 原有的 Key 顺序也保不住。

把条件放宽成 grp BETWEEN 1 AND 80，索引会找到八万条候选，Bitmap 要记的位置也多了。这里固定走 Bitmap 路径，分别把 work_mem 设成 64kB 和 64MB。TIDBitmap 会按这个参数算出自己能在内存里保留多少候选信息：

BEGIN;
SET LOCAL enable_seqscan = off;
SET LOCAL enable_indexscan = off;
SET LOCAL work_mem = '64kB';

EXPLAIN (ANALYZE, COSTS OFF, TIMING OFF)
SELECT id, payload
FROM t_scan
WHERE grp BETWEEN 1 AND 80 AND flag = 1;

SET LOCAL work_mem = '64MB';

EXPLAIN (ANALYZE, COSTS OFF, TIMING OFF)
SELECT id, payload
FROM t_scan
WHERE grp BETWEEN 1 AND 80 AND flag = 1;
ROLLBACK;

内存够用时，Bitmap 会记住页号和命中的 Offset，计划里把这种页计为 Exact。

记不下时，TIDBitmap 会把部分页面改成更粗的表示：页号还在，具体哪些 Offset 命中过已经不记了。这些页就变成了 Lossy。

用一页六条记录示意，先假定它们全部可见：

Heap Block 42
  offset       1    2    3    4    5    6
  grp         10  300   50  900   70  400
  1 <= grp <= 80
               Y    .    Y    .    Y    .

Exact
  block = 42, offsets = {1, 3, 5}
                    |
                    | discard offsets
                    v
Lossy
  block = 42, offsets = unknown

原来拿着 Bitmap，可以直接去找 Offset 1、3、5。现在手里只剩一个「Block 42」，已经分不清页内哪些位置命中过，只好把这一页的可见记录都拿来检查。

Offset 2、4、6 就是这样混进来的。重新执行 grp BETWEEN 1 AND 80，才能把它们排除。这一步才是这里的 Recheck。

页内还可能留着旧版本。查询会依据 Snapshot（事务快照）判断哪些版本能被自己看到，后续检查只处理这些可见记录。进入 Lossy Page 后，顺序就是：

1. 找出页内对当前 Snapshot 可见的记录。
2. 对可见记录重新判断索引条件，排除同页带进来的额外候选。
3. 继续执行 flag = 1 这个普通 Filter。

位置集合占用的内存省下来了，进页以后要做的检查却多了。真正匹配的记录仍然都在，只是需要从更大的候选范围里重新筛一次。

一次实测的结果如下（页大小 8KB）。这里比较的是同一份数据在两种 work_mem 下的差别：

两种 work_mem 下，候选页都是 2,363 个，最终结果也都是四万行。内存少的这次，多检查并淘汰了 37,300 条不满足 grp 条件的记录；没有多访问候选页，却在页里多干了不少活。

这里容易误读：grp = g % 1000 看起来会把 grp 打散到整张表，但数据是按 g 顺序写入的。grp BETWEEN 1 AND 80 命中的 g 是 1–80、1001–1080、2001–2080……一共 1,000 段连续的 80 行。

本次每页容纳 55 行，一段只落在两三页上；而 grp = 42 的 1,000 行每隔 1,000 行出现一次，正好落在 1,000 个不同的页上。全表 18,182 页，范围条件只碰到其中的 2,363 页。

前面那次 grp = 42 的查询就没有这份额外工作：B-tree 已经精确匹配了条件，Bitmap 又全部保留着 Offset，这次执行没有产生 Lossy 页，Recheck 可以直接跳过。

Recheck Cond 列出了需要时可以重算的条件，并不表示这次每条记录都重算过。

Rows Removed by Index Recheck 也只统计复验失败的记录。即使执行了复验，只要都通过，这项仍然可以是零，不能靠它单独判断有没有做过 Recheck。

位置精确了，条件还可能需要复验

不过，Exact 这个词只说明位置保存得精确。拿到了准确的 TID，索引条件仍然可能需要复验。

TIDBitmap 为 Exact Page 保存候选 Offset，同时还可以保留一个 recheck 标志。位置虽然准确，这些候选仍可能需要重新判断索引条件。这个要求可以由索引带进来，也可能在 Bitmap 合并时产生。两个 Bitmap 求交时，如果同一页在一边是 Exact、另一边是 Lossy，保留下来的候选也需要复验。

索引在比较数据时，依赖一组称作 Operator Class 的规则：支持哪些运算符、怎样判断匹配。某些 Operator Class 会先用近似信息筛选候选。

比如 GiST 处理几何类型时，常用多边形的包围盒来缩小搜索范围。点落在这个矩形里，却可能落在多边形外，要取到原始对象才能判断。

索引告诉你去 (42, 3) 找，位置没有错，但那里的对象未必真的满足条件。把它放进 Bitmap 时，这个「还要检查」的要求也得一起带上。

所以，看到 Heap Blocks: exact，只能知道 Offset 还在，不能据此认定索引条件都已经判断完了。

两种原因，处理办法也不一样。Bitmap 因为内存不足丢了 Offset，增加 work_mem 可能有帮助；索引自身采用的就是近似匹配，内存给得再多，也替它完成不了对原始对象的判断。

候选和 Recheck 怎样交接

PostgreSQL 通过 Index AM（索引访问方法）的公共接口接入不同索引实现，B-tree 只是其中一种。

这个复验要求得一路传到执行条件的地方。只传 TID、不传「还要检查」，后面就可能把近似匹配直接当成准确结果返回。

普通 Index Scan 通过 amgettuple 逐步取得候选，Index AM 可以通过 xs_recheck 标记复验要求。Bitmap 路径通过 amgetbitmap 收集候选，往 TIDBitmap 里加 TID 时可以带上 recheck 标志，这份要求便跟着候选一起交出去。

表达式则留在 Executor 手里，需要复验时再执行。Executor 负责运行执行计划中的各个节点，具体索引只需说明这件事还没做完，不必自己接管 SQL 表达式的执行。

执行表达式之前，还得先找到当前 Snapshot 能看见的 Tuple。B-tree 返回的 TID 可能指向旧版本，也可能是一条 HOT Chain 的起点。

HOT Chain 是同一页内、可以从一个索引入口访问的行版本链。沿着 TID 或 HOT Chain 找到可见版本，由 Table AM 处理。

普通扫描和 Bitmap 扫描，大致在这里接起来：

                       Index AM
                     /          \
           amgettuple              amgetbitmap
        TID + xs_recheck       TIDBitmap + recheck
                     \          /
                       Table AM
                 Snapshot -> visible Tuple
                           |
                           v
                        Executor
                           |
                recheck required?
                  /             \
                yes              no
                 |                |
          index condition         |
          fail -> discard         |
          pass ------+------------+
                     |
                   Filter
              fail /    \ pass
             discard    output

这里的可见性检查和 Recheck 各管一件事：先确认当前 Snapshot 能否看见这个版本，再按需要重算索引条件，最后处理普通 Filter。Rows Removed by Index Recheck 和 Rows Removed by Filter 数的是后面两步淘汰的记录，都不包含可见性检查跳过的版本。

把版本访问留在 Table AM，也省得每种索引都去解释 Heap Tuple Header、追踪 HOT Chain。否则，表的版本实现就会散落到各个索引里，以后改变表的存储方式，还得跟着修改它们。

Executor 这边也一样。它保留着原始条件，知道怎么对一条记录执行这些表达式，就能接住不同索引留下的复验要求。至于候选是怎样搜出来的，用了什么页面结构，都留给具体的 Index AM。

Index Only Scan 也需要可见性依据

Index Only Scan 也没有省掉可见性判断。

把查询改成只取索引里已有的 grp：

EXPLAIN (ANALYZE, COSTS OFF, TIMING OFF)
SELECT grp FROM t_scan WHERE grp = 42;

在 VACUUM 之后，得到：

Index Only Scan using t_scan_grp_idx on t_scan
  (actual rows=1000.00 loops=1)
  Index Cond: (grp = 42)
  Heap Fetches: 0

这次 grp 的值可以直接从索引取得。可见性则借助 Visibility Map 判断：这是一张按表页记录状态的辅助位图。Visibility Map 中对应表页的 All-Visible 位设上，表示整页记录对所有事务都可见。

对应页的这个位已经设上，查询就有了可见性依据，不用再回 Heap 逐条确认。

如果 All-Visible 位没设上，就少了这份依据，仍然要回 Heap 检查。它不表示这一页一定存在不可见版本，只表示这一步暂时省不掉。

所以 Index Only Scan 下面也可能跟着很高的 Heap Fetches。它记录的是为确认可见性而发起的 Heap 取数次数，不是不同页面数，也不代表一定发生了物理读；即使这次没有找到可见版本，也已经记了一次。近期更新会清掉相关页面的 All-Visible 标记，查询和索引都没换，这部分工作量也会跟着变。

换成 GIN，候选还可以从两处来

这套分工给具体索引留下了不少余地。GIN 是一个和 B-tree 很不一样的例子，它常用来查哪些数组包含指定元素、哪些文档出现过某些词。

先看文章标签。假设 posts 表里有一个 text[] 类型的 tags 字段：

从表里看，是一篇文章有哪些标签。GIN 反过来，为每个标签保存出现过它的记录位置：

这就是倒排索引。GIN 的全称是 Generalized Inverted Index，通用倒排索引。表里为了方便阅读写了文章 id，索引实际关联的仍是 Heap TID。

如果要找同时带有「PostgreSQL」和「开源」标签的文章，可以这样建索引、写查询：

CREATE INDEX posts_tags_idx ON posts USING gin(tags);

SELECT id
FROM posts
WHERE tags @> ARRAY['PostgreSQL', '开源'];

@> 表示左边的数组包含右边的所有元素。按上面的数据，两个标签分别对应 {1, 2} 和 {2, 3}，取交集就找到文章 2。

这种组织对查找很方便，写入时却要多做些工作。新文章有十个标签，就可能要维护十个标签对应的位置集合；换成全文检索，一篇文档能拆出更多词项。

fastupdate 就是为这部分写入成本准备的。开启后，新条目可以先放进 Pending List，也就是索引内部的待合并列表，以后再批量整理到主要索引结构。

这样可以把一部分整理工作往后放，但查询时得把两处都查到。Pending List 积压得越多，查询需要额外处理的工作也越多。

GIN 把两处找到的候选汇入 Bitmap，通过 amgetbitmap 交出去。它没有提供普通扫描使用的 amgettuple，公共接口允许具体索引选择适合自己的扫描方式。

Executor 不需要知道某个候选来自 Pending List，还是来自已经整理好的结构。GIN 把内部各处的数据找全，后面照常处理可见性和必要的复验。

内部整合可以晚一点做，查询的完整性不能跟着推迟。一条记录在当前 Snapshot 下应当可见、又满足查询条件时，尚未合并不能成为漏掉它的理由。后面的 Recheck 能排除多带进来的候选，却补不回索引没有交出来的位置。

三段交接

Index AM 负责找出候选，并说明这些位置是否还需要复验；Table AM 顺着 TID 或 HOT Chain，找到当前 Snapshot 能看见的版本；Executor 接着处理必要的索引条件复验和剩余的 Filter。

这样分工之后，索引换一种实现，可见性判断和表达式执行不必跟着重写；表换一种存储方式，索引也不用知道版本是怎么串起来的。开头那个问题也就有答案了：Recheck Cond 和查询条件长得一模一样，并不表示 PostgreSQL 把同一个条件算了两遍。它只是把「这个条件可能还要再确认一次」写在了计划里；是否实际复验、复验多少条记录，要看位置有多精确，也要看索引自己有没有把判断做完。

复现实验的数据

CREATE TABLE t_scan (
    id      int,
    grp     int,
    flag    int,
    payload text
);

INSERT INTO t_scan
SELECT g,
       g % 1000,
       (g / 1000) % 2,
       repeat('x', 100)
FROM generate_series(1, 1000000) AS g;

CREATE INDEX t_scan_grp_idx ON t_scan (grp);
VACUUM (ANALYZE) t_scan;

SET max_parallel_workers_per_gather = 0;
SET work_mem = '64MB';