8.1 查询执行器：Scan、Join、Aggregate 与资源边界

同一条 SQL 可以全表扫描，也可以查索引；连接还可能使用嵌套循环、哈希或归并。执行器把这些选择落实为算子和数据流。本课沿着扫描、连接与聚合，检查哪些步骤能边读边输出、哪些必须先积累状态，以及内存不足时会发生什么。

本课目标

• 区分 logical plan 与 physical plan；
• 理解 iterator、materialization 与 vectorized execution；
• 比较 sequential/index/bitmap scan；
• 正确分析 nested-loop、hash、merge join；
• 识别 memory budget、spill、blocking 与 pipeline breaker。

从 SQL 到执行计划

SQL text
  -> parse tree
  -> name/type resolution and semantic checks
  -> logical rewrite/normalization
  -> physical alternatives and cost search
  -> executable plan
  -> result protocol

有些系统把 rewrite 放进 optimizer，有些先生成 bound relational tree；view expansion、subquery decorrelation 和 predicate inference 的支持也不同。不能声称所有产品都严格经历同四个阶段。

Iterator model

经典 volcano iterator 为 operator 定义：

open()
next() -> next tuple or end
close()

parent 调用 child next()，形成 pull pipeline：

Limit
└─ Project
   └─ Filter
      └─ Index Scan

优势是 composable 与 streaming；成本是 per-tuple calls、branches 和 poor instruction locality。现代 engines 可使用 batch-at-a-time/vectorized、push-based 或 compiled pipeline。

Streaming 与 blocking operators

• filter/project/most scans 可读到 tuple 后立即产出；
• full sort 通常要先读完 input；
• hash join build side 要先建 hash table；
• hash aggregate 通常要看到足够 input 才能完成 groups；
• materialize/cache operator 保存 input 供重复读取。

blocking operator 是 pipeline breaker，会增加 startup latency 和 memory/spill risk。LIMIT 若位于能早停的 ordered scan 上可少做很多工作；位于 full sort 上方则未必。

Sequential scan

sequential scan 遍历 relation pages/segments，并对可见 tuples 应用 filter：

SELECT customer_id, name
FROM customers
WHERE level >= 15;

这条 SQL 可在 1.2 的 SQLite 练习库运行：初始数据匹配客户 A、B，顺序不作保证；数据库实际选择何种扫描仍要看计划。顺序扫描可能优于 index scan：

• table 小；
• predicate 命中比例高；
• output 需要大部分 columns/rows；
• sequential/readahead 带宽优于大量 random heap fetch；
• parallel scan 可用；
• table/index cache state 与 correlation 不利于 index。

“全表扫描最笨但永远正确”不严谨：scan 是合法 physical path，但 predicate expression 仍可能抛错，snapshot/permission/corruption 也会影响执行。

Index scan 与 index-only scan

CREATE INDEX idx_customers_level_id
ON customers (level, customer_id);

index scan 先得到 matching index entries，再访问 base rows。若 entries 指向的 heap pages 分散，random fetch 成本会上升。

index-only 需要：

• query required columns 能从 index entry 提供；
• engine 能从 index/visibility metadata 确认版本可见；
• plan 认为收益高。

PostgreSQL 即使 columns 被覆盖，也可能因 visibility map 未标 all-visible 而 heap fetch。InnoDB secondary index 的“回表”则通常通过 primary key lookup，物理模型不同。

Bitmap scan

PostgreSQL bitmap index scans 可以组合多个 index results，形成 page/tuple bitmap，再按 heap-page order 访问：

Bitmap Heap Scan
└─ BitmapAnd
   ├─ Bitmap Index Scan(status)
   └─ Bitmap Index Scan(reward)

它把大量 tuple-locator accesses 聚合到 pages，减少重复/离散 heap visits，但不能保证物理设备上严格连续 I/O。memory 不足时 bitmap 可变 lossy，只记录 page，heap scan 必须 recheck predicate。

bitmap path 适合 intermediate selectivity；极少 rows 常用 direct index scan，绝大多数 rows 常用 sequential scan。

Nested-loop join

for outer_row in outer:
    for inner_row in parameterized_inner(outer_row.key):
        if join_predicate:
            emit

没有 access path 时，重复扫描 inner 成本可能很高；有 index 的 parameterized lookup 时，适合 small outer 或 highly selective probes。

complexity 不能只写 outer × log(inner)：每次 probe 可能返回多个 rows、cache hit 不同、predicate evaluation 和 random I/O 也不同。

NLJ 还可用于 non-equality/lateral correlations，是最通用 join framework。

Hash join

等值 join 的概念流程：

build:
  for row in build_input:
    hash_table.get_or_create(hash(row.key)).append(row)

probe:
  for row in probe_input:
    for candidate in hash_table.get(hash(row.key), []):
      if equality(candidate.key, row.key):
        emit pair

hash bucket 必须保存多个 candidates，不能用 hash_table[key] = row 覆盖 duplicate。hash collision 后还要按数据库 equality 精确比较。这里是普通等值连接的伪代码，未画出 NULL、外连接和资源管理；SQL = 下，NULL 键不应作为相等的匹配对输出。

optimizer 通常偏好较小 estimated input 做 build，但 row width、skew、parallel exchange、outer-join semantics 与 available memory 会改变选择。

Spill/batching

build 放不下时，engine 可将两侧按 secondary hash 分 batches/partitions：matching keys 落入同 partition，逐批加载 build/probe。但这不是无代价的“优雅降级”：

• temporary I/O 增加；
• skewed heavy key 仍可能让单 partition 放不下；
• repartition/recursive batching 增加 passes；
• concurrent hash nodes/workers 放大 memory 与 disk pressure；
• spill tail latency 可能突增。

Merge join

两侧按 compatible join keys 排序时：

compare current key groups
smaller side advances
equal groups produce all matching pairs

duplicate group 必须输出 Cartesian matches。merge join 适合 merge-joinable operators/order semantics，并非任意 <、BETWEEN 都能自动使用同一算法；具体 operator class/support 由 engine 决定。

输入 order 可来自 index scan、upstream sort 或已有 pathkey。若两侧都需外排，hash join 可能更便宜；若 parent 同样需要 order，sort cost 可能被复用。

Aggregation

Hash aggregate

group_key -> aggregate states。适合 groups 能在 memory 中管理，或 engine 能有效 partition/spill。高 cardinality、宽 states、skew 会增加风险。

Sort/group aggregate

input 按 group keys 排序后，逐 group accumulation。已有 order 时很有吸引力；否则要支付 sort/spill。

Streaming aggregate

如果 input 已按 grouping key ordered，可只保留 current group state，memory 很小。

COUNT(DISTINCT)、ordered aggregate 与 large user-defined state 会改变 operator requirements。

Resource ownership

query memory 不是“一条查询一个固定池”这么简单：

• 多个 sort/hash nodes 可能同时存在；
• parallel workers 各有 state；
• pipelined nodes 的 lifetime overlap；
• materialization/spool 产生 temp files；
• result buffering、client backpressure 也占资源。

估算时应累加同时活跃节点的预算，再考虑 worker 和 session 并发；真正共享的状态只计一次。以 PostgreSQL 为例，hash 节点还需乘 hash_mem_multiplier，分配也不保证所有节点同时达到上限。盲目增大 work_mem 可能把 spill 换成 OOM。PostgreSQL 资源配置

本课小结

执行计划是 operators 与 data flow 的组合。scan 选择取决于 selectivity、coverage 和 locality；join 选择取决于 cardinality、order、memory 与 predicate；spill 是 resource boundary，不是透明细节。下一课解释 optimizer 如何用统计与成本在这些 alternatives 中做选择。