Scan 算子实现了各种“读数据”的操作，是理解 PG 执行器节点的一个很好入口。

Seq Scan

Seq Scan 即顺序扫描，是 Scan 家族里最简单的一类。

它的典型栈轨迹如下：

#0  heap_getnextslot (sscan=0xb3f12c32cc40, direction=ForwardScanDirection, slot=0xb3f12c32c5c0) at heapam.c:1389
#1  table_scan_getnextslot (sscan=0xb3f12c32cc40, direction=ForwardScanDirection, slot=0xb3f12c32c5c0) at ../../../src/include/access/tableam.h:889
#2  SeqNext (node=0xb3f12c32c3d0) at nodeSeqscan.c:80
#4  ExecScan (node=0xb3f12c32c3d0, accessMtd=0xb3f118942c74 <SeqNext>, recheckMtd=0xb3f118942d24 <SeqRecheck>) at execScan.c:183
#5  ExecSeqScan (pstate=0xb3f12c32c3d0) at nodeSeqscan.c:112
#6  ExecProcNode (node=0xb3f12c32c3d0) at ../../../src/include/executor/executor.h:242
// ... 执行器栈轨迹

几个要点：

  • #6以下是执行器的通用栈轨迹（见之前执行器的介绍）。
  • ExecScan() 是各类 Scan（包括后面要提到的 Index Scan、Bitmap Scan 等）的通用模板。不同 Scan 类型的区别，主要体现在传入的 access / recheck 回调函数不同。简化实现如下： 
    TupleTableSlot *ExecScan(ScanState *node, ExecScanAccessMtd accessMtd, ExecScanRecheckMtd recheckMtd) {
  ...

  if (!qual && !projInfo)
      // return tuple directly if no qualification and projection
      return ExecScanFetch(node, accessMtd, recheckMtd);

  for (;;) {
      // do EvalPlanQual recheck and return (*accessMtd) (node)
      slot = ExecScanFetch(node, accessMtd, recheckMtd);

      // no more results
      if (TupIsNull(slot)) return slot;

      // check tuple satisfies the qual-clause
      if (qual == NULL || ExecQual(qual, econtext))
          // Found a satisfactory scan tuple
          if (projInfo)
              // do projection and return
              return ExecProject(projInfo);
          else
              // Here, we aren't projecting, so just return scan tuple
              return slot;
  }
  ...
}
  • ScanState 中记录了 Scan 节点的执行器状态；根据 Scan 类型不同，再细分出 SeqScanState、IndexScanState 等子类型。
  • EvalPlanQual() 用来在某些并发更新场景下对 tuple 做再次检查，需要调用传入的 recheck 回调。
  • Projection 和 Qualification：前者就是投影（select col），后者就是过滤条件（where）；在 PG 中它们本质上都通过表达式求值实现。
  • 最终通过 table AM / heap AM 接口拿到实际 tuple。

其他 Scan

★Index Scan

当表上存在索引时，对于点查这类选择率较低的 SQL，优化器通常会倾向于选择 Index Scan。

以 btree 索引为例，其栈轨迹如下：

#0  _bt_first (scan=0xb2db99ca6ed0, dir=ForwardScanDirection) at nbtsearch.c:748
#1  btgettuple (scan=0xb2db99ca6ed0, dir=ForwardScanDirection) at nbtree.c:247
#2  index_getnext_tid (scan=0xb2db99ca6ed0, direction=ForwardScanDirection) at indexam.c:529
#3  index_getnext_slot (scan=0xb2db99ca6ed0, direction=ForwardScanDirection,  lot=0xb2db99ca60b0) at indexam.c:621 // note: scan is IndexScanDesc
#4  IndexNext (node=0xb2db99ca5dc0) at nodeIndexscan.c:133
#5  ExecScanFetch (node=0xb2db99ca5dc0, accessMtd=0xb2db8b091cb0 <IndexNext>, recheckMtd=0xb2db8b092398 <IndexRecheck>) at execScan.c:133
#6  ExecScan (node=0xb2db99ca5dc0, accessMtd=0xb2db8b091cb0 <IndexNext>, recheckMtd=0xb2db8b092398 <IndexRecheck>) at execScan.c:183

它的实现依然复用了 ExecScan 模板： ExecScan(&node->ss, (ExecScanAccessMtd) IndexNext, (ExecScanRecheckMtd) IndexRecheck)，具体逻辑在 IndexNext() 中：

ExecIndexScan -> ExecScan -> 
    IndexNext(): 
        index_beginscan(IndexScanDesc scan, ...) // call rel->rd_indam->ambeginscan()
        (index_rescan if RuntimeKeysReady)
        index_getnext_slot()
            index_getnext_tid()		// call rd_indam->amgettuple
            index_fetch_heap()		// call rd_tableam->index_fetch_tuple

简单说，index_getnext_slot() 会先通过 index_getnext_tid() 调用 btree AM 返回一个 TID，然后再在 index_fetch_heap() 中调用 heap AM 接口，通过这个 TID 取回对应的 heap tuple。

另外，如果索引里已经包含了查询所需的全部列，并且优化器预计很多相关 heap page 都是 all-visible，就还可能选择 Index Only Scan。执行过程中如果遇到并非 all-visible 的页面，仍然可能回退去访问 heap 做可见性检查。此时，索引本身就有点像一个小型“列存”。

    if (scandesc->xs_itup) // itup是一个indextuple
        StoreIndexTuple(node, slot, scandesc->xs_itup, scandesc->xs_itupdesc);

★Bitmap Scan

它的适用场景介于 Seq Scan 和 Index Scan 之间：表上有索引，但选择率中等，例如范围查询时，常会走 Bitmap Scan。它会先通过索引收集 TID，再按页面维度组织访问顺序，尽量保证每个页面只做一次 I/O 并加载进 buffer pool 供后续使用。

具体行为可以参考这里。其实现依然是 ExecScan(&node->ss, (ExecScanAccessMtd) BitmapHeapNext, (ExecScanRecheckMtd) BitmapHeapRecheck)，重点在位图结构 TIDBitmap 的实现。

It’s a bitmap data structures that are spiritually similar to Bitmapsets, but are specially adapted to store sets of tuple identifiers (TIDs), or ItemPointers.

★Custom Scan

名义上它属于 scan，实际上却是一个非常灵活的可扩展通用节点，可以实现各类自定义节点逻辑，甚至不局限于“扫描”。我自己还没有系统深入这部分，后续需要结合具体 case 来看，可以先参考 pg_mooncake。

scan中几个特殊行为

尽管 Scan 的行为看起来相对简单，但因为它是最常走的代码路径之一，所以里面塞满了各种细节优化。

★buffer选择

Scan 读取页面时都要经过 buffer，但这里还有一个问题：到底使用主 buffer pool，还是使用进程私有的 ring buffer？策略细节可以看 GetAccessStrategy()。

这块放到后续写 heap AM 或 buffer pool 时再细说。

★同步扫描

多个并发的 Seq Scan 可以共享扫描起点和进度，尽量避免重复读取同一批 page，从而减少磁盘 I/O 并提升性能。

这里主要提升的是 OS page cache 的命中率，而不是 PG 自己的 buffer pool 命中率。

工作原理如下：

  1. 起始位置：Seq Scan 开始后，如果表足够大且启用了同步扫描，就会从一个共享起点（rs_startblock）开始。这个位置由 ss_get_location 计算，通常接近上一次扫描结束的位置。
  2. 扫描进度：扫描过程中会定期调用 ss_report_location()，把当前位置汇报给共享内存中的全局状态： 
     /* Pointer to struct in shared memory */
 static ss_scan_locations_t *scan_locations;
  3. 扫描协作：多个并发扫描通过这份共享状态协作，尽量避免重复扫描相同 page。扫描到表尾后，会再折返到表头继续扫完剩余部分。

★并行执行

PostgreSQL 是进程模型，因此很长一段时间里，单条 query 很难直接从多核中受益。从 pg9.6 开始引入了并行 query 执行机制：基于 DSM（dynamic shared memory，src/backend/storage/ipc/dsm.c）和 parallel worker 框架，从而加速部分 CPU 密集型 query。简化架构如下：

              ┌───────┐                                 
              │       ◄───a Worker1                             
  Leader  c───►  DSM  │                                 
              │       ◄───a Worker2                            
              └───────┘

一般执行步骤：

  1. Leader 创建位于共享内存中的 DSM，并把任务切分规则（例如块范围）写入 DSM 中的结构体（如 ParallelBlockTableScanDescData）。
  2. Leader 随后启动多个 worker，这些 worker 会 attach 到 DSM 上。
  3. Worker 从 DSM 中领取自己的任务并处理，最后把部分结果写回。
  4. Leader 等待全部 worker 完成，然后汇总结果并释放 DSM。

几种 Scan 的切分方法如下，留意版本之间可能会有细微变化：

  • parallel seq scan
    • 在 pg12 中：每个 worker 一次只分配一个 block。
    • 在 pg14 中：每个 worker 分配一段连续 block（chunk），从而让 OS 更容易做预读。
  • parallel index scan：每个 worker 分配一段连续的 index block，随后再访问对应 heap block。
  • parallel bitmap scan：由 leader 先生成位图，再由其他 worker 并行扫描表数据。

★写行为

Scan 本质上是读操作，但在某些场景下也会带出一些出乎意料的写行为，比如设置 hint bits、做 page pruning 等，可以参考这里。

Discussion

Scan 作为 PostgreSQL 中最常用的执行器算子之一，细节优化点很多，需要结合代码多看看。

Questions:

  1. Scan 中的 rechecker 函数和 Index / Bitmap Scan 中的 xs_recheck 是一个东西吗？

    xs_recheck是lossy index相关

  2. ExecScan的返回一个输出slot，对于TTSBufferTuple，具体数据是什么时候物化到了slot->tts_values中的？

    可以gdb watch看一下