查询规划器 — Join 顺序与路径生成：优化器如何选中 Nested Loop

你在 EXPLAIN 输出里见过无数次 Nested Loop、Hash Join、Merge Join，也见过 Seq Scan、Index Scan、Bitmap Index Scan。但 PG 的优化器到底是怎么决定用哪个的？为什么有时候一个三表 Join 的查询，明明建了索引却走了 Seq Scan？为什么超过一定表数量后执行计划突然变差？

这些问题的答案都在 make_one_rel() 这个函数里。它是 PG 查询优化器的路径生成入口——从单表扫描方式的选择，到两表 Join 算法的决策，再到多表 Join 顺序的排列搜索，全在这里调度。

本文从 make_one_rel() 的调用链开始，拆解四种访问路径的创建条件、三种 Join 方式的代价对比、动态规划到 GEQO 的切换逻辑，最后用 EXPLAIN (ANALYZE, BUFFERS) 对照 planner 的内部决策。

一、从 Query 到 RelOptInfo：make_one_rel 的全景

调用链

规划器的主入口在 src/backend/optimizer/plan/planner.c 的 standard_planner()。它调用 subquery_planner() 做子查询规划，后者调用 grouping_planner()，最终到达 query_planner()，而 query_planner() 的核心调用就是 make_one_rel()：

```text standard_planner() → subquery_planner() → grouping_planner() → query_planner() → add_base_rels_to_query() // 为 FROM 中每个表创建 RelOptInfo → build_base_rel_tlists() // 构建 target list → deconstruct_jointree() // 将 jointree 展平为 JoinExpr 列表 → make_one_rel() // ★ 核心：生成所有 Join 路径bash

make_one_rel() 的内部阶段

// src/backend/optimizer/path/allpaths.c
RelOptInfo *
make_one_rel(PlannerInfo *root, List *joinlist)
{
    RelOptInfo *rel;

    // 阶段 1：为每个基表生成访问路径（SeqScan, IndexScan 等）
    set_base_rel_pathlists(root);

    // 阶段 2：为所有基表的 RelOptInfo 构造 joinrel
    //         按 joinlist 顺序——先做 FROM/JOIN 子句，再做 WHERE
    rel = make_rel_from_joinlist(root, joinlist);

    return rel;
}

set_base_rel_pathlists() 为 FROM 子句中的每个基表（RelOptInfo）生成所有可行的访问路径，加入 rel->pathlist。make_rel_from_joinlist() 按 joinlist 中指定的 Join 配对关系，递归地构造 joinrel（Join 关系的 RelOptInfo），并在每个级别上调用 add_paths_to_joinrel() 生成 Join 路径。

关键数据结构

RelOptInfo 是优化器内部对”一个关系”（基表或 Join 中间结果）的抽象，其路径信息记录在：

// src/include/nodes/pathnodes.h
typedef struct RelOptInfo {
    Relids      relids;          // 该关系包含的 base rel OID 集合
    List       *pathlist;        // 该关系当前最优路径的列表（Path 链表）
    List       *partial_pathlist;// 可并行化的部分路径
    List       *cheapest_startup_path;   // 启动代价最低的路径
    List       *cheapest_total_path;     // 总代价最低的路径
    PathTarget *reltarget;       // 输出列
    // ... 大量其他字段（行数估算、宽度、索引信息等）
} RelOptInfo;
```text

`Path` 是单一执行路径的抽象，核心字段：

```c
typedef struct Path {
    NodeTag     type;
    RelOptInfo *parent;         // 所属的 RelOptInfo
    Cost        startup_cost;   // 启动代价（产生第一行之前的开销）
    Cost        total_cost;     // 总代价
    List       *pathkeys;       // 输出行的排序顺序
} Path;

每种扫描方式和 Join 方式都是 Path 的子结构：IndexPath 包含索引选择信息（indexclauses、indexorderbys），JoinPath 包含内外表的路径指针和 Join 条件。

二、基表访问路径：四种扫描方式

set_base_rel_pathlists() 为每个基表生成访问路径。最终进入 rel->pathlist 的路径类型取决于表上有什么索引、统计信息怎么说、GUC 怎么配。源码在 src/backend/optimizer/path/allpaths.c。

SeqScan（顺序扫描）

顺序扫描是最朴素的路径——从表的第一个页面读到最后一个页面。创建条件是无条件：只要表存在，就有一条 SeqScan 路径。

// src/backend/optimizer/path/allpaths.c, set_plain_rel_pathlist()
// 即使有其他路径可选，SeqScan 也永远被加入 pathlist
add_path(rel, create_seqscan_path(root, rel, required_outer, 0));
```text

代价计算在 `cost_seqscan()` 中：基本公式是 `N_page * seq_page_cost + N_tuple * cpu_tuple_cost`。`seq_page_cost` 默认 1.0，`cpu_tuple_cost` 默认 0.01。在 `random_page_cost` 远大于 `seq_page_cost` 的配置下（比如默认 4.0 vs 1.0），SeqScan 在规划器眼中对大表极为划算——这正是 NVMe 上 `random_page_cost=4.0` 导致优化器不选索引的原因。

### IndexScan（索引扫描）

IndexScan 用索引定位符合条件的行，然后到 heap 取对应的 tuple。创建条件是存在索引且索引列与查询条件相关。

```c
// src/backend/optimizer/path/indxpath.c, create_index_paths()
// 关键调用链：
//   get_index_paths()
//     → build_index_paths()
//       → create_index_path()

生成 IndexPath 时最关键的两个决策： - 选择率估算：clauselist_selectivity() 根据 MCV/histogram 估算索引条件的过滤率。如果过滤率太高（比如返回超过表的 30%），IndexScan 的总代价可能高于 SeqScan。 - 排序利用：如果索引的排序与查询的 ORDER BY 一致，pathkeys 直接满足排序需求，省掉了显式 Sort 节点。

代价计算在 cost_index() 中：索引页面 I/O + heap 页面 I/O（随机读，用 random_page_cost）+ CPU 开销。索引扫描的 heap 读取是随机的（按 ctid 跳页），这是它的主要劣势——如果几乎所有页面都被遍历到，SeqScan 反而更便宜。

IndexOnlyScan（仅索引扫描）

IndexOnlyScan 不需要读取 heap——所有需要的列都在索引中。创建条件是查询的 target list 和 WHERE 条件中的所有列都被索引覆盖。

// IndexOnlyScan 的额外条件（除 IndexScan 条件外）：
// 1. 索引包含所有需要的列（无论是作为 key column 还是 included column）
// 2. Visibility Map 标识对应 heap 页面为 all-visible
//    ——如果 VM 不认为页面 all-visible，必须回表查 heap 页面确认可见性
```text

IndexOnlyScan 的代价中，heap I/O 的部分乘以 `vm_all_visible_fraction`——即 VM 认为 all-visible 的页面比例。如果 VM 陈旧（很久没有 VACUUM），IndexOnlyScan 的优势大幅缩水。

### BitmapScan（位图索引扫描）

BitmapScan 分两步：先在内存中构建一个 bitmap（每个 heap 页面一位），然后按页面顺序扫描 heap。它可以合并多个索引的 bitmap（`BitmapAnd`、`BitmapOr`），并将随机 I/O 转换为顺序 I/O（bitmap 按页面号排序后批量读）。

```c
// src/backend/optimizer/path/indxpath.c
// 核心路径：create_index_paths() → generate_bitmap_or_paths()
// 为单个索引创建 BitmapPath：cost_index() + bitmap 代价
// 为 OR 条件创建 BitmapOrPath：合并多个 BitmapPath

BitmapScan 的创建条件是任何 IndexScan 的条件。对多个索引的条件组合（WHERE a = 1 OR b = 2），优化器可能为每个索引生成 BitmapPath，然后用 BitmapOr 合并。

它的优势场景是：返回行数中等（太多 IndexScan 回表随机读太贵，太少 Bitmap 构建开销不值），尤其在有多个 OR 条件的查询中。

三、Join 路径生成：三种 Join 方式的创建条件与代价

从 make_one_rel() → make_rel_from_joinlist() → standard_join_search()，优化器逐级构建 joinrel——先两表 Join，再三表 Join。

add_paths_to_joinrel() 是加入 Join 路径的核心函数，源码在 src/backend/optimizer/path/joinpath.c。对每一对内外表路径，它调用三个函数：

// src/backend/optimizer/path/joinpath.c, add_paths_to_joinrel()
match_unsorted_outer();   // 尝试 Nested Loop（外表不需要排序）
hash_inner_and_required(); // 尝试 Hash Join（内表需要 hashable）
match_unsorted_outer() 中 → sort_inner_and_outer(); // 尝试 Merge Join（需要排序）
```bash

### Nested Loop Join（嵌套循环连接）

Nested Loop（NL）是最通用的 Join 方式：对外表的每一行，扫描内表（或在内表上做索引查找）找到匹配行。

```c
// src/backend/optimizer/path/joinpath.c, match_unsorted_outer()
// 对每一对 (outerpath, innerpath)：
//   1. 检查 join 条件是否能用作 inner scan key（参数化路径）
//   2. 如果能：创建 parameterized NestLoop（内表是 IndexScan，外表行值作为扫描键）
//   3. 如果不能：创建 plain NestLoop（内表重复全扫描）

代价公式：\(C_{total} = C_{outer} + N_{outer} \times C_{inner\_rescan}\)

如果内表能用索引扫描（parameterized path），\(C_{inner\_rescan}\) 是索引查找的代价，很便宜。
如果内表只能全扫描（plain NestLoop），\(C_{inner\_rescan} \approx C_{inner}\)，对大数据量极其昂贵。

Nested Loop 的选择条件：外表小（行数少）且内表有高效索引，或 Join 条件不是等值条件（Nested Loop 是唯一支持非等值 Join 的方式）。它也是 LEFT JOIN 中唯一保证驱动表每一行都输出的方式。

Hash Join（哈希连接）

Hash Join 为内表构建内存 hash 表，然后扫描外表，每一行 probe hash 表找匹配。

// src/backend/optimizer/path/joinpath.c, hash_inner_and_required()
// 创建条件：
//   1. Join 条件是等值条件（equality operator，必须有 hash 函数）
//   2. 内表路径可哈希化
```text

代价公式：$C_{total} = C_{outer} + C_{inner} + N_{outer} \times cpu\_operator\_cost + N_{inner} \times cpu\_operator\_cost$

Hash Join 的关键风险在内存：如果 hash 表放不进 `work_mem * hash_mem_multiplier`（PG 15+ 的额外乘数），就会溢出到磁盘（分批 batch），代价骤增。`EXPLAIN (ANALYZE, BUFFERS)` 输出中的 `Buckets:`、`Batches:` 和 `Memory Usage:` 显示 hash 表的实际大小和溢出情况。

**Hash Join 的选择条件**：两个表都不算太小（否则 Nested Loop 用索引更快）、Join 条件是等值条件、内表能全部装入 work_mem 的 hash 表或溢出不太多。

### Merge Join（归并连接）

Merge Join 要求两个表都按 Join 键排序，然后双指针同步扫描。

```c
// src/backend/optimizer/path/joinpath.c, sort_inner_and_outer()
// 创建条件：
//   1. Join 条件是 mergejoinable 的等值条件（有 btree opfamily）
//   2. 两个表的路径都按 Join 键排序——要么天然有排序（索引），要么加 Sort 节点

代价公式：\(C_{total} = C_{outer\_sorted} + C_{inner\_sorted} + (N_{outer} + N_{inner}) \times cpu\_operator\_cost\)

其中 \(C_{outer\_sorted}\) 和 \(C_{inner\_sorted}\) 包含可能的 Sort 代价。如果表本身已经按 Join 键排序（例如来自索引扫描），Sort 代价为零。

Merge Join 的选择条件：两个表都很大（Hash Join 的 hash 表装不下内存、Nested Loop 太贵），且至少一个表已经按 Join 键排序（或排序代价可接受）。Merge Join 还有一个附带好处——输出天然按 Join 键排序，如果 ORDER BY 与 Join 键一致，省掉最终的 Sort。

三种 Join 的选择对比

``````text 条件：两表大小相当，都有索引，等值 Join

内表小，有高效索引？ → Nested Loop（外表每行一次索引查找）内表中等，Hash 表能装进 work_mem？ → Hash Join（一次构建 hash + 一次扫描外表）两个表都大，排序开销可接受？ → Merge Join（如果已排序则极快）


---

## 四、Join 顺序搜索：动态规划与 GEQO 的切换

### 动态规划：standard_join_search()

PG 对 Join 顺序的搜索使用自底向上的动态规划（DP）。源码在 `src/backend/optimizer/path/joinrels.c` 的 `standard_join_search()`。

```c
// 算法概要：
// levels_needed = FROM 子句中的基表数
for (lev = 2; lev <= levels_needed; lev++) {
    // 对每个 level（包含 k 个基表的 joinrel）：
    //   生成所有包含 lev 个基表的 joinrel
    //   对每个 joinrel 的每种拆分方式 (outer_rel, inner_rel)：
    //     调用 add_paths_to_joinrel() 创建 joinpath
    //     用 add_path() 加入 joinrel->pathlist（dominance check）
    //   保留下来的 joinpath 进入下一级
}

DP 算法保证找到理论上的最优 Join 顺序（在代价模型正确的前提下），因为所有可能的拆分方式都被遍历。但搜索空间是 Catalan number 增长：n 个基表的 Join 顺序数量是 \(C_{n-1} = \frac{(2n-2)!}{n!(n-1)!}\)，即 \(n=5\) 时 14 种、\(n=10\) 时 4862 种、\(n=15\) 时约 267 万种。

GEQO：geqo_threshold 的切换

当 levels_needed >= geqo_threshold（默认 12）时，PG 不再用 DP 做穷举搜索，而是切换到 GEQO（Genetic Query Optimizer，遗传算法）。源码在 src/backend/optimizer/geqo/geqo_main.c。

// src/backend/optimizer/path/allpaths.c
// 决策点：
if (levels_needed <= geqo_threshold)
    rel = standard_join_search(root, levels_needed, joinlist);
else
    rel = geqo(root, levels_needed, joinlist);  // 遗传算法
```text

GEQO 的遗传算法流程（`geqo_main.c`）：

``````text
1. 初始化种群：生成 NumberGenerations 个随机 join 顺序（默认 pool_size=0 时自适应）
2. 对每个个体（join 顺序）评估代价（fitness），保留 best_keep 个（默认 2）
3. 对每一代：
   a. 选择（selection）：biased linear selection——代价低的个体更可能被选中
   b. 交叉（crossover）：交换两个亲代的部分 join 顺序，生成子代
   c. 变异（mutation）：随机交换子代中的两个位置
4. 重复直到 max_generations 代，选择最优个体

GEQO 不保证最优解，但搜索时间是多项式级别而非指数级。geqo_threshold 的默认 12 是基于 1990 年代的硬件设定的——今天的 CPU 可以在 DP 下处理更多表。geqo_effort（默认 5，范围 1-10）控制种群大小和代数，但 GEQO 的结果天然不稳定——同一查询可能两次得到不同计划。

关键运维事实：当查询涉及 12+ 个表时，你看到的执行计划不一定是最优的，只是 GEQO 在有限代数内找到的较优解。如果 12 表查询的性能不稳定，考虑降低 join_collapse_limit 或将部分 Join 编码为子查询/CTE 来减少搜索空间。

join_collapse_limit 与 from_collapse_limit

这些 GUC 限制优化器重排 Join 顺序的范围。默认值（与 geqo_threshold 相同）让优化器自由重排所有显式 Join 和 FROM 列表中的表，但保留显式括号的语义。当这些值设为 1 时，优化器完全按照 SQL 中写的 Join 顺序执行——这是排查”优化器选错顺序”时的有用工具。

五、并行路径生成

当查询涉及大表扫描或大 Join 时，PG 可以为路径生成并行版本。入口在 set_plain_rel_pathlist() 中：

// src/backend/optimizer/path/allpaths.c, set_plain_rel_pathlist()
if (rel->pages > parallel_threshold) {  // min_parallel_table_scan_size
    create_plain_partial_paths(root, rel);
}
```text

`create_plain_partial_paths()` 生成 **partial path**（部分路径）——表示可以由一个并行 worker 执行的那部分扫描。这些路径被加入 `rel->partial_pathlist`，然后在 Join 路径生成时，优化器可以将 partial path 与 `Gather`/`Gather Merge` 节点组合，生成并行执行计划。

并行 Join 的三种方式：
- **Parallel Hash Join**：多个 worker 共享一个 hash 表（`SharedHashInfo`），每个 worker 并行扫描外表并与共享 hash 表做 probe。
- **Parallel Merge Join**：每个 worker 并行扫描外表的一部分（数据已排序并分区），与共享的内表扫描指针做 merge。
- **Parallel Nested Loop**：外表被分区，每个 worker 扫描一个分区并独立执行内表索引查找。

`parallel_setup_cost` 和 `parallel_tuple_cost` 分别控制启动并行 worker 和 worker 间传递 tuple 的代价估算。

---

## 六、实验：EXPLAIN 输出与 Planner 决策对照

### 实验环境

```bash
# PG 17, shared_buffers=512MB, work_mem=4MB, random_page_cost=4.0

1. 构造三表 Join 和索引选择

CREATE TABLE orders (
    order_id   INTEGER PRIMARY KEY,
    customer_id INTEGER,
    order_date DATE,
    amount     NUMERIC
);

CREATE TABLE customers (
    customer_id INTEGER PRIMARY KEY,
    name        TEXT,
    region      TEXT
);

CREATE TABLE products (
    product_id  INTEGER PRIMARY KEY,
    order_id    INTEGER,
    product_name TEXT
);

-- 灌入数据
INSERT INTO orders SELECT g, (g % 1000) + 1,
    '2025-01-01'::DATE + (g % 365),
    (random() * 1000)::NUMERIC(10,2)
FROM generate_series(1, 100000) g;

INSERT INTO customers SELECT g, 'customer_' || g,
    CASE WHEN g % 4 = 0 THEN 'East' ELSE 'West' END
FROM generate_series(1, 1000) g;

INSERT INTO products SELECT g, (g % 100000) + 1, 'product_' || g
FROM generate_series(1, 200000) g;

-- 创建外键索引（products 表）
CREATE INDEX idx_products_order ON products(order_id);

-- ANALYZE
ANALYZE orders;
ANALYZE customers;
ANALYZE products;
```bash

### 2. 观察三表 Join 的计划选择

```sql
EXPLAIN (ANALYZE, BUFFERS, TIMING)
SELECT c.name, o.order_date, p.product_name
FROM customers c
JOIN orders o ON c.customer_id = o.customer_id
JOIN products p ON o.order_id = p.order_id
WHERE c.region = 'West';

输出解读：

```text Nested Loop (cost=0.29..8912.45 rows=1500 width=...) (actual time=0.045..18.234 rows=150000 loops=1) Buffers: shared hit=4623 -> Seq Scan on customers c (cost=0.00..19.00 rows=750 width=...) (actual time=0.012..0.284 rows=750 loops=1) Filter: (region = 'West') Buffers: shared hit=13 -> Nested Loop (cost=0.29..11.82 rows=2 width=...) (actual time=0.008..0.022 rows=200 loops=750) Buffers: shared hit=4610 -> Index Scan using orders_customer_id_idx on orders o (cost=0.29..4.31 rows=1 width=...) (actual time=0.004..0.006 rows=100 loops=750) Index Cond: (customer_id = c.customer_id) Buffers: shared hit=1360 -> Index Scan using idx_products_order on products p (cost=0.42..7.50 rows=2 width=...) (actual time=0.003..0.008 rows=200 loops=75000) Index Cond: (order_id = o.order_id) Buffers: shared hit=3250text

对照分析：

最外层 Seq Scan on customers——customers 表只有 1000 行，SEQSCAN 扫描 13 个 buffer（8KB × 13 ≈ 104KB），optimizer 认为选索引不如直接扫。region = 'West' 过滤掉 25%（750 行），优化器估算准确（rows=750）。
内层 Nested Loop——外表 customers 的 750 行作为驱动表，每行触发一次 orders_customer_id_idx 索引扫描（loops=750）。每个 customer_id 平均匹配 100 个订单（因为 100000 orders / 1000 customers = 100），所以 actual rows=100 per loop。
最内层 Nested Loop——上一步返回的每行订单（750 × 100 = 75000），再触发一次 idx_products_order 索引扫描。每个 order_id 平均匹配 2 个产品（200000 products / 100000 orders = 2），所以 actual rows=200 per loop，总 loops=75000。
优化器为什么选 Nested Loop 而不是 Hash Join？ 因为 customers 被 WHERE region = 'West' 过滤后只有 750 行（估算准确），作为驱动表很划算。内表的每次索引扫描代价很低。如果优化器错误估算 customers 的行数（比如统计信息过时导致认为只有 10 行），可能选 Hash Join 更优。

3. 强制观察 Hash Join 和 Merge Join

-- 强制禁用特定 join 方式来观察替代计划
SET enable_nestloop = off;

EXPLAIN (ANALYZE, BUFFERS)
SELECT c.name, o.order_date, p.product_name
FROM customers c
JOIN orders o ON c.customer_id = o.customer_id
JOIN products p ON o.order_id = p.order_id
WHERE c.region = 'West';

-- 观察计划是否变为 Hash Join
-- 恢复
SET enable_nestloop = on;

-- 有排序需求时观察 Merge Join
EXPLAIN (ANALYZE, BUFFERS)
SELECT c.name, o.order_date, p.product_name
FROM customers c
JOIN orders o ON c.customer_id = o.customer_id
JOIN products p ON o.order_id = p.order_id
ORDER BY c.customer_id, o.order_id;
-- customer_id 和 order_id 都有索引，Merge Join 可能直接利用排序
```bash

### 4. 触发 GEQO

```sql
-- 查看当前 geqo_threshold
SHOW geqo_threshold;  -- 默认 12

-- 修改为较低值来触发 GEQO
SET geqo_threshold = 3;

EXPLAIN SELECT * FROM
  (SELECT generate_series(1,100) AS a) t1,
  (SELECT generate_series(1,100) AS b) t2,
  (SELECT generate_series(1,100) AS c) t3,
  (SELECT generate_series(1,100) AS d) t4
WHERE t1.a = t2.b AND t2.b = t3.c AND t3.c = t4.d;

-- 注意 EXPLAIN 输出中不再保证最优 Join 顺序
-- 恢复
RESET geqo_threshold;

5. 观察并行查询

-- 确保并行查询已启用
SET max_parallel_workers_per_gather = 4;

EXPLAIN (ANALYZE, BUFFERS)
SELECT count(*) FROM orders WHERE amount > 900;

-- 输出可能包含 Gather 节点：
-- Gather  (cost=1000.00..1500.00 rows=10000 width=8)
--   Workers Planned: 2
--   ->  Partial Aggregate
--         ->  Parallel Seq Scan on orders
```text

---

## 七、运维：路径选择的常见问题与排查

### 1. 优化器不选索引：random_page_cost 过高

**现象**：表上建了索引，`EXPLAIN` 仍然显示 Seq Scan。

**根因**：`random_page_cost` 默认 4.0，意味着优化器假设一次随机页面读取的成本是一次顺序页面读取的 4 倍。在 NVMe SSD 上，这个假设严重高估了随机读的成本，导致优化器认为 SeqScan（全顺序读）比 IndexScan（随机读 + 回表）更便宜。

**排查**：

```sql
-- 查看当前配置
SHOW random_page_cost;

-- 用 pg_test_fsync 实测磁盘随机 vs 顺序读的性能比
-- 然后按比例设置。NVMe 上通常 1.0-1.5 合理
ALTER SYSTEM SET random_page_cost = 1.5;
SELECT pg_reload_conf();

2. 统计信息漂移导致 Join 顺序错乱

现象：曾经很快的查询突然变慢，EXPLAIN 显示 Join 顺序变了或选错了 Join 方式。

根因：大表频繁插入/删除后统计信息过期。pg_stat_user_tables.n_mod_since_analyze 过大，优化器对行数和选择率的估算严重偏离实际。

排查：

-- 查看统计信息的新鲜度
SELECT relname, n_live_tup, n_dead_tup, n_mod_since_analyze,
       last_analyze, last_autoanalyze
FROM pg_stat_user_tables
WHERE relname IN ('orders', 'customers', 'products');

-- 如果 n_mod_since_analyze 远大于 n_live_tup * autovacuum_analyze_scale_factor（默认 0.1）
-- 说明 auto-analyze 没有及时触发或阈值太高
ANALYZE orders;  -- 立即更新统计信息
```bash

### 3. work_mem 与 Hash Join 溢出的互相影响

**现象**：`EXPLAIN (ANALYZE, BUFFERS)` 中 Hash Join 的 `Batches:` 大于 1，查询比预期慢很多。

**根因**：`work_mem` 太小（或并发连接太多，每连接的实际可用内存远小于 `work_mem`），Hash Join 的 hash 表装不下内存，溢出到磁盘批次处理。每次溢出产生额外的磁盘 I/O——内表数据被多次写入和读出临时文件。

**排查**：

```sql
EXPLAIN (ANALYZE, BUFFERS, SETTINGS)
SELECT ...;

-- 观察 Hash Join 节点的输出：
-- Hash Join  (cost=...) (actual time=...)
--   Hash Cond: (...)
--   Buckets: 16384  Batches: 8  Memory Usage: 2049kB
--   ↑ Batches > 1 表示发生了溢出

-- 溢出时增加 work_mem：
SET work_mem = '64MB';  -- 仅当前 session
-- 或全局：
-- ALTER SYSTEM SET work_mem = '64MB';

注意 work_mem 的危险性：设太大的 work_mem + 高并发 = 后端内存爆炸。hash_mem_multiplier（PG 15+）给 hash 操作额外的乘数，work_mem * hash_mem_multiplier 才是 hash 操作能用的内存上限。

4. 多表 Join 计划不稳定（GEQO 区）

现象：12+ 表 Join 的查询，每次 EXPLAIN 输出可能不同，执行时间在几秒到几十秒之间波动。

根因：geqo_threshold 默认为 12，超过此数量的表使用 GEQO 遗传算法搜索 Join 顺序——遗传算法不保证找到最优解，每次运行可能产生不同的计划。

排查与缓解：

```sql – 方案 A：提高 geqo_threshold 让更多表走 DP SET geqo_threshold = 15; – 小心：DP 的复杂度是 Catalan 数

– 方案 B：降低 join_collapse_limit 限制 DP 搜索空间 SET join_collapse_limit = 8;

– 方案 C：将部分 Join 编码为子查询或 CTE WITH sub AS ( SELECT … FROM t1 JOIN t2 … WHERE … ) SELECT … FROM sub JOIN t3 …;

– 方案 D：固定部分 Join 顺序（显式括号 + join_collapse_limit=1） – 让优化器按 SQL 书写的顺序执行 ```text

八、关键要点

make_one_rel() 是 Join 路径生成的调度中心。先为每个基表生成扫描路径（set_base_rel_pathlists()），然后按 joinlist 逐级构造 joinrel 并生成 Join 路径（make_rel_from_joinlist()）。
四种扫描路径各有用武之地：SeqScan 无条件存在，IndexScan 依赖索引和选择率估算，IndexOnlyScan 需要索引覆盖且依赖 VM all-visible，BitmapScan 适合中等过滤率和多索引 OR 组合。
三种 Join 方式的选择来自代价比较而非硬规则：Nested Loop 适合驱动表小 + 内表有索引；Hash Join 适合等值 Join + 内表能装进 work_mem；Merge Join 适合大表且至少一个表已排序。
GEQO 在 geqo_threshold（默认 12）个表时接管——遗传算法不保证最优，可能导致计划不稳定。超出此阈值时排查计划波动是 GEQO 而非统计信息的问题。
EXPLAIN (ANALYZE, BUFFERS) 是 plan 决策的”事后解剖”：actual rows vs plan rows 的差异暴露统计信息问题，Batches > 1 暴露 Hash Join 内存溢出，Buffers: read 暴露磁盘 I/O。

下一章：执行器与表达式求值，拆解火山模型的 ExecProcNode 调度、EEO (Expression Evaluation) 的 opcode 编译和 TupleTableSlot 机制。

上一章：查询规划器 — 统计信息与代价模型

参考资料

源码（PG 17）

src/backend/optimizer/path/allpaths.c：make_one_rel(), set_base_rel_pathlists(), set_plain_rel_pathlist(), create_plain_partial_paths()
src/backend/optimizer/path/joinpath.c：add_paths_to_joinrel(), match_unsorted_outer(), hash_inner_and_required(), sort_inner_and_outer()
src/backend/optimizer/path/joinrels.c：make_rel_from_joinlist(), standard_join_search()
src/backend/optimizer/path/costsize.c：cost_seqscan(), cost_index(), cost_nestloop(), cost_hashjoin(), cost_mergejoin()
src/backend/optimizer/path/indxpath.c：create_index_paths(), get_index_paths(), build_index_paths()
src/backend/optimizer/geqo/geqo_main.c：geqo(), GEQO 遗传算法主循环
src/backend/optimizer/geqo/geqo_eval.c：geqo_eval()，个体评估
src/backend/optimizer/geqo/geqo_selection.c：选择算子
src/backend/optimizer/geqo/geqo_cx.c、geqo_ox.c、geqo_pmx.c：交叉算子（cycle / order / partially matched crossover）
src/include/nodes/pathnodes.h：RelOptInfo, Path, IndexPath, JoinPath, PlannerInfo 结构体
src/backend/optimizer/util/pathnode.c：add_path() ——路径比较和 dominance check

官方文档

PostgreSQL Documentation, Chapter 60: Genetic Query Optimizer
PostgreSQL Documentation, Section 20.7: Query Planning（GUC 参数说明：geqo_threshold, geqo_effort, join_collapse_limit, from_collapse_limit）
PostgreSQL Documentation, Section 14.1-14.3: Using EXPLAIN

论文

Selinger, P. G. et al. Access Path Selection in a Relational Database Management System. SIGMOD 1979. — System R 代价模型，PG 代价估算的学术原型。
Graefe, G. The Cascades Framework for Query Optimization. IEEE Data Eng. Bull. 1995. — 查询优化器架构的通用框架，PG 的 DP 搜索遵循此框架的设计思路。

同主题继续阅读

把当前热点继续串成多页阅读，而不是停在单篇消费。

2026-06-16 · database / kernel

【PG 内核】执行器与表达式求值：从计划树到行数据的一趟流水

拆解 PostgreSQL 执行器的火山模型（ExecInitNode→ExecProcNode→ExecEndNode）、Hash Join 内存化实现、EEO 表达式求值的 opcode 编译与解释执行机制、TupleTableSlot 的三种数据承载方式（virtual/heap/minimal）。附带查询 hang 住的完整诊断路径：pg_stat_activity 的 wait_event + pg_blocking_pids() 追踪锁等待链 + EXPLAIN ANALYZE 计划行数与实际行数差异定位。

2026-06-16 · database / kernel

【PG 内核】查询规划器 — 统计信息与代价模型：优化器为什么选错了索引

拆解 PostgreSQL 查询优化器的决策基础：pg_statistic 中 MCV/histogram/correlation 的存储结构、ANALYZE 的采样流程与精度边界、clauselist_selectivity 如何逐层估算选择率、seq_page_cost 等代价常量的物理意义与调优依据、CREATE STATISTICS 解决多列相关性问题、以及统计信息漂移的诊断 SQL 与排查路径。读完你能回答：优化器为什么选 Seq Scan 而不是你建的索引，以及怎么定位根因。

2026-06-16 · database / kernel

【PG 内核】PostgreSQL 内核机制深度拆解

从进程模型到磁盘页面、从 MVCC 到流复制——对 PostgreSQL 内核做完整的源码级拆解。不止步于源码分析：26 篇中 6 篇是运维实战——经典故障的根因与排查路径、性能调查的五层工具链、配置陷阱与恢复边界。面向想读懂 PG 内核源码、在生产环境排查过问题、准备给 PG 贡献代码的工程师。

2026-06-16 · database / kernel

【PG 内核】进程模型与共享内存：Postmaster 如何管理 100 个 Backend

拆解 PostgreSQL 多进程架构的核心：Postmaster 的启动与信号处理、Backend 进程的 fork()→InitPostgres→主循环生命周期、CreateSharedMemoryAndSemaphores() 的共享内存初始化流程、PGPROC/ProcArray/PGXACT 等关键共享内存结构的内存布局，以及 Background Worker 的注册与调度。理解了这个地基，才能理解 PG 为什么用进程而不是线程，以及 max_connections 为什么不能随便调大。

【PG 内核】查询规划器 — Join 顺序与路径生成：优化器如何选中 Nested Loop

文章导航

目录

查询规划器 — Join 顺序与路径生成：优化器如何选中 Nested Loop

一、从 Query 到 RelOptInfo：make_one_rel 的全景

调用链

make_one_rel() 的内部阶段

关键数据结构

二、基表访问路径：四种扫描方式

SeqScan（顺序扫描）

IndexOnlyScan（仅索引扫描）

三、Join 路径生成：三种 Join 方式的创建条件与代价

Hash Join（哈希连接）

三种 Join 的选择对比

GEQO：geqo_threshold 的切换

join_collapse_limit 与 from_collapse_limit

五、并行路径生成

1. 构造三表 Join 和索引选择

3. 强制观察 Hash Join 和 Merge Join

5. 观察并行查询

2. 统计信息漂移导致 Join 顺序错乱

4. 多表 Join 计划不稳定（GEQO 区）

八、关键要点

参考资料

源码（PG 17）

官方文档

论文

同主题继续阅读

【PG 内核】执行器与表达式求值：从计划树到行数据的一趟流水

【PG 内核】查询规划器 — 统计信息与代价模型：优化器为什么选错了索引

【PG 内核】PostgreSQL 内核机制深度拆解

【PG 内核】进程模型与共享内存：Postmaster 如何管理 100 个 Backend