查询优化器：System R 动态规划、Cascades Memo 与基数误差

同一条 SQL 可以写得很短，执行计划却可能从一次索引嵌套循环到多路哈希连接差几个数量级。优化器要解决的问题不是“会不会用 hash join”，而是在三件事之间同时取舍：哪些等价变换应该纳入搜索，哪些物理性质值得为上层保留，以及统计信息的误差会不会把搜索导向错误的计划。

本文按一条线索展开：System R 用左深动态规划和 interesting orders 建立了代价优化器的基本范式；Volcano/Cascades 把等价表达式、规则和物理性质放进 memo；后来的 DPccp/DPhyp 重新审视 join-order 枚举；生产系统再用阈值、启发式和超时约束规划时间。所有枚举数字与基数误差实验来自同目录 reproduce/query_optimizer_experiment.py，源码事实钉住 PostgreSQL REL_16_9 与 Apache Calcite 1.37.0。

一、优化器到底在优化什么

关系查询优化器输入的是逻辑代数树，输出的是物理执行计划。对一个只含内连接的子问题，可以把参与连接的表记为集合 \(S\)，优化器通常要为每个 \(S\) 找到若干候选计划：

• 逻辑等价：\(A \bowtie B\) 与 \(B \bowtie A\) 等价，\((A \bowtie B) \bowtie C\) 与 \(A \bowtie (B \bowtie C)\) 在内连接且谓词可重排时等价；
• 物理实现：同一个逻辑 join 可以实现为 nested loop、hash join 或 merge join；这些算子的代价和输出顺序不同；
• 物理性质（physical properties）：输出是否按某个键有序、是否已分区、使用哪种执行 convention，会影响上层是否还要排序或 repartition；
• 统计估计：基表行数、列直方图、最常见值、distinct 值和谓词选择率决定代价模型的输入。

对 \(n\) 张表，左深树的叶子排列已有 \(n!\) 种；完全二叉 bushy 树的叶子标号数为 \(n! C_{n-1}\)，其中 \(C_{n-1}\) 是 Catalan 数。\(n=10\) 时，左深排列是 \(3,628,800\)，bushy 形状乘标号是 \(17,643,225,600\)。这还没有乘上访问路径、join 算子和有序性的组合。优化器必须把“枚举足够多”与“规划时间可接受”同时作为目标。

本文不重复上一篇 Join 算法：嵌套循环、排序归并与 Hybrid Hash 的代价和实现 已经讲过的 join 算子内部实现；这里把 join 当作候选物理算子，重点看它们如何被组织进搜索空间。

二、System R：左深动态规划与 interesting orders

Selinger、Astrahan、Chamberlin、Lorie 和 Price 在 SIGMOD 1979 的 “Access Path Selection in a Relational Database Management System” 中给出了后来代价优化器的基本形状。System R 的输入是关系代数表达式和统计信息，输出是预计代价最小的访问路径与连接顺序。它有三个今天仍能在优化器里看到的设计。

左深动态规划

System R 只枚举左深树（left-deep tree）：每一步把已经得到的中间结果与一个基表相连。设 best[S, p] 是连接集合 \(S\)、并满足物理性质 \(p\) 的最佳计划，简化后的递推是：

for each base relation R:
    keep cheapest access paths for {R}
for size = 2..n:
    for each subset S with |S| = size:
        for each R in S:
            L = S - {R}
            if L can join R:
                combine every retained plan of L with every access path of R
                keep cheapest plan per required physical property

这个递推利用了最优子结构：若一个左深计划最后一步是 \(L \bowtie R\)，那么 \(L\) 的子计划也应该是某个性质下的最优候选。它牺牲了 bushy 计划，但让搜索从超指数形状压到按子集组织的动态规划。PostgreSQL 的常规 join 搜索仍然按 join relation 的大小分层，这一点与 System R 的思路相同，尽管它会在有连接谓词时生成有限的 bushy 组合（第七节）。

Interesting orders

System R 的一个关键洞察是：局部最便宜不等于全局最便宜。一个索引扫描也许比顺序扫描贵，但它输出的顺序可能让上层 merge join、ORDER BY 或 GROUP BY 省掉排序。System R 把这种对后续算子有价值的顺序称为 interesting order。

因此，优化器不能只为每个 \(S\) 保留一个最低代价计划，而要按物理性质保留多个候选：一个可能是无序但便宜的 hash join，另一个可能是稍贵但按连接键有序的 merge join。这个想法后来在 Volcano/Cascades 里被推广为 trait 或 physical property。

代价公式与边界

System R 论文里的代价函数把页读取（page fetch）与 RSI 调用数（可近似理解为元组级 CPU 工作）合在一起，形式是页读取数加权 CPU 调用数。这个模型很粗，但它确立了一个原则：优化器比较的是估算代价，而估算代价由统计信息、算子模型和物理性质共同决定。

这也给 System R 留下边界：它主要处理单块查询的访问路径与左深 join 顺序；对于大量等价变换、复杂物理属性和可扩展规则集，手写动态规划会迅速变得难维护。

三、连接顺序枚举：形状比表数更重要

连接顺序不是只由表数决定，还由查询图决定。把每张表看成顶点，每个 join 谓词看成边；不允许笛卡尔积时，候选子计划必须对应连通子图。链、星和团三种图在同样表数下给优化器的压力完全不同。

reproduce/query_optimizer_experiment.py 实现了两个小枚举器：

• DPsize-left-deep：按集合大小枚举左深扩展，只把一个已连通子集与一个相邻基表相连；
• DPccp-style csg-cmp：按连通子图（connected subgraph, CSG）与互补连通子图（CMP）成对枚举可连接的 bushy 拆分。它不是 Moerkotte–Neumann 论文的逐行复刻，但计数口径与 DPccp 的核心对象一致：只枚举有连接谓词的 CSG-CMP 对。

运行命令：

cd post/algorithms/60-query-optimizer/reproduce
taskset -c 15 python3 query_optimizer_experiment.py

本机复核环境是 Python 3.14.5、matplotlib 3.11.2、Linux 6.6.87.2，CPU 可用编号为 0–23；实验指标是候选数和代价比，不依赖墙钟时间。脚本输出 results/enumeration_counts.csv、results/cardinality_error.csv、results/summary.txt，并重画本文三张 SVG。

\(n=12\) 时，脚本得到的候选数如下：

三点值得注意。

第一，链式查询虽然有 12 张表，但连通子集只有所有区间，共 \(78\) 个；优化器只要沿相邻边扩展，搜索很小。第二，星形查询的连通子集已经接近 \(2^{11}\)：任何包含中心点的叶子集合都是连通的。第三，团图中 bushy CSG-CMP 候选远多于左深候选，因为任意两个不相交子集都能连接。只看“表数超过多少”不能判断优化难度，查询图的稠密度同样关键。

Moerkotte 和 Neumann 的贡献就在这里。VLDB 2006 的 DPccp 关注如何枚举 connected subgraph/complement pair 而不重复、且避免无连接谓词的笛卡尔积；SIGMOD 2008 的 “Dynamic Programming Strikes Back” 引入 DPhyp，把动态规划扩展到更复杂的 hypergraph 表达。它们反驳了“DP 只能做小查询”的简单说法：如果枚举对象选得对，DP 在不少实际查询上仍有竞争力。

四、Volcano 与 Cascades：memo、规则和性质

Graefe 与 McKenna 在 ICDE 1993 的 Volcano Optimizer Generator 中把优化器写成可扩展的规则系统：逻辑变换、物理实现和搜索策略解耦。Graefe 1995 年的 Cascades 进一步把 memo、top-down 搜索和物理性质整合成一个框架。今天很多系统并不逐字实现 Cascades，但 memo 化搜索、规则驱动和 trait 传播已经成了优化器工程的通用语言。

Memo 的结构

Cascades memo 不是一棵树，而是等价表达式的 DAG。一个 group 表示同一逻辑结果的等价类；一个 group expression 是某个具体表达式，它的孩子指向 group，而不是指向某棵固定子树。这样，交换律、结合律生成的新表达式可以共享同一个子问题。

图里 Group 0 表示三表连接结果；它可以包含逻辑 join 的不同结合顺序，也可以包含 hash join、merge join 等物理表达式。Group 1、Group 2 等子 group 被多条表达式共享。重要的是：winner 不是全局唯一的。同一个 group 可能在“无序输出”下 hash join 最便宜，在“按连接键有序”下 merge join 加少量排序更便宜。

规则与 enforcer

Cascades 风格的规则通常分三类：

Top-down 搜索从根 group 和 required properties 出发，给每个子 group 传递所需性质与剩余代价上界。若当前表达式的局部代价已经超过上界，就可以剪枝。这与 System R 的 bottom-up DP 不矛盾：两者都依赖 memo，只是搜索方向与规则组织不同。

Calcite 的 VolcanoPlanner

Apache Calcite 1.37.0 的 org.apache.calcite.plan.volcano.VolcanoPlanner 是一个可核对的生产级例子。findBestExp() 会先 ensureRootConverters()，再 ruleDriver.drive() 触发规则，最后调用 root.buildCheapestPlan(this) 生成最便宜计划。registerImpl() 会调用 rel.onRegister(this) 递归注册子表达式，用 digest 去重，并把等价表达式放入 RelSet / RelSubset。

Calcite 的名字是 VolcanoPlanner，但它也有 Cascades 语境里的关键部件：memo 化等价类、规则驱动、trait set 和 converter。把它称为“使用 Volcano/Cascades 思想的 planner”比把它说成某篇论文的逐字实现更准确。

五、基数估计：优化器争论的主战场

搜索算法再精巧，也要吃估算基数。设真实基数为 \(c\)，估计基数为 \(\hat c\)，数据库论文常用 q-error 衡量相对误差：

\[ q(\hat c, c) = \max\left(\frac{\hat c}{c}, \frac{c}{\hat c}\right). \]

\(q=1\) 表示完全准确，\(q=10\) 表示高估或低估 10 倍。Ioannidis 和 Christodoulakis 在 SIGMOD 1991 的 “On the Propagation of Errors in the Size of Join Results” 中已经指出，join 结果大小误差会沿连接树传播；在独立性假设失效时，多个选择率误差会相乘。

一个可复现实验

脚本里的第二个实验固定一张 6 表查询图和真实选择率。优化器用带 lognormal 噪声的选择率估计做左深 DP，选出计划；然后用真实选择率重新计算该计划的真实代价，并与真实最优左深计划比较。每个误差强度跑 30 个固定种子，指标仍然不依赖时钟。

results/summary.txt 的汇总如下：

这个小实验不代表真实数据库负载，但它展示了两个机制。第一，轻微误差不一定改变计划：许多种子下最优顺序仍然稳定，所以中位数代价比为 1。第二，尾部风险增长很快：当某几条边同时被严重低估或高估，优化器会把大中间结果提前物化，最坏代价比达到 \(44.98\)。

Leis、Gubichev、Mirchev、Boncz、Kemper 和 Neumann 在 PVLDB 2015 的 “How Good Are Query Optimizers, Really?” 用 Join Order Benchmark 系统地讨论了同一个问题。他们把优化器拆成四部分评估：基数估计、代价模型、物理算子选择和枚举算法。论文的核心结论是：在他们的实验中，基数估计误差是导致坏计划的主因；如果喂给优化器真实基数，很多系统即使用相对简单的代价模型也能得到接近最优的计划。

这不是说代价模型无关。代价模型决定 hash join、merge join、index nested loop、排序和并行的取舍；但如果一个中间结果被估成 \(10^3\) 行、真实却是 \(10^9\) 行，再精细的 CPU cache 参数也救不了错误的连接顺序。

六、代价模型：粗糙但必须一致

一个代价模型至少要把三类量放到同一单位里：

• I/O：顺序读、随机读、临时文件写入、缓存命中概率；
• CPU：谓词求值、哈希计算、排序比较、函数调用；
• 内存与物理性质：hash table 是否溢出、排序是否多趟、输出是否满足上层顺序。

System R 的页读取加 CPU 调用只是最早的版本。现代系统会有更多参数，但核心仍是“可比较”。PostgreSQL 的 EXPLAIN 显示的是抽象 cost，不是毫秒；MySQL、SQL Server、Oracle 也不会把代价单位暴露成真实时间。抽象单位的好处是稳定，坏处是参数不准时容易和硬件脱节。

Interesting orders 可以看成代价模型与物理性质的交界：一个计划为了保持排序多花了本地代价，但让上层少一次排序。Cascades 的 required properties 则把这种取舍系统化：上层请求“需要按 \(k\) 有序”，子 group 才会比较“直接产生有序输出”和“先无序输出再加 sort enforcer”的总代价。

工程上最危险的不是模型简单，而是模型前后不一致。例如，规划阶段认为 hash join 不会溢出，执行阶段却因为内存估计错误分批落盘；或者统计信息假设列独立，真实数据里两个过滤条件高度相关。这些问题最终都会以“代价模型输入错了”的形式表现出来。

七、PostgreSQL 16：DP、bushy 限制与 GEQO

PostgreSQL REL_16_9 的常规 join 搜索可以在 src/backend/optimizer/path/joinrels.c 里直接看到。join_search_one_level(PlannerInfo *root, int level) 的注释写明：它构造恰好包含 level 个 jointree items 的 join relations，是 standard_join_search 动态规划的一步。

代码分三段。

1. 先把 level - 1 个关系的 joinrel 与一个基表相连，也就是左深或右深扩展。若有相关 join clause 或 join order restriction，调用 make_rels_by_clause_joins()；若没有，就生成必要的 clauseless join。
2. 再枚举 bushy 组合：把大小为 \(k\) 的 joinrel 与大小为 level-k 的 joinrel 相连，但只在 have_relevant_joinclause() 或 have_join_order_restriction() 成立时生成，避免无谓的笛卡尔积爆炸。
3. 如果前面完全没有生成可用 joinrel，最后才用 clauseless join 兜底，处理某些 join 子问题被语法边界隔开的特殊情况。

make_rels_by_clause_joins() 的注释还说明，(a join b) join c 与 (b join c) join a 会落到同一个 RelOptInfo，不同路径作为 Path 加进去；join_rel_level 机制保证新 joinrel 只加入列表一次。这正是 memo 思想在 PostgreSQL 自有数据结构里的体现。

表很多时，PostgreSQL 默认不再使用穷举 DP。src/backend/utils/misc/guc_tables.c 中 geqo_threshold 的默认值是 12，说明文字是 “Sets the threshold of FROM items beyond which GEQO is used.”。达到阈值后会进入 GEQO（Genetic Query Optimizer）：src/backend/optimizer/geqo/geqo_main.c 里可以看到 gimme_pool_size()、gimme_number_generations()、random_init_pool()、sort_pool() 以及 chromosome 交叉变异相关代码。

这不是“PostgreSQL 只能优化 12 表以内查询”。准确说法是：默认配置下，FROM items 数达到 12（levels_needed >= geqo_threshold）时，优化器为了限制规划时间，会从穷举动态规划切到遗传搜索；用户可以调整 geqo_threshold 或关闭 GEQO，但代价是规划时间可能急剧上升。

八、学习型优化器：开放问题而不是替代品

学习型优化器常被写成“取代 CBO”，但论文里的主张更具体。

Neo（Marcus、Negi、Mao、Zhang、Alizadeh、Kraska、Papaemmanouil、Tatbul，PVLDB 2019）把优化过程表示成候选计划搜索与神经网络价值评估：模型从已执行查询中学习计划质量，逐步引导搜索。Bao（Marcus、Negi、Mao、Tatbul、Alizadeh、Kraska，SIGMOD 2021）更工程化：它不直接生成任意计划，而是在现有优化器外面选择一组 hint，让底层数据库继续负责合法计划生成；模型根据实际执行反馈更新。

二者的共同点是：都承认传统优化器已有大量工程约束，学习组件更现实的位置是补充估计或选择，而不是绕过执行器、事务语义和物理算子限制从零生成计划。

学习型方向仍有几个具体开放问题：

• 安全性：模型探索坏计划会直接伤害线上查询，Bao 用 hint 集合限制动作空间，就是为了降低风险；
• 分布漂移：统计信息、数据分布、索引和硬件变化后，历史反馈不一定可靠；
• 冷启动：新 workload 没有足够执行样本，纯学习方法很难优于 CBO 的先验；
• 可解释性与调试：DBA 需要知道坏计划来自统计信息、规则缺失、代价参数，还是模型误判。

因此，本篇把学习型优化器放在开放问题里，而不是把它写成 System R → Cascades 之后的必然终点。Leis 等人的结论也提醒我们：先把基数估计、相关性建模和生产实现里的边界做好，往往比换一个搜索器更重要。

九、工程判断：读执行计划时先看什么

面对一条慢 SQL，按下面顺序排查比直接调优化器开关更稳。

几个经验边界也要分清。

• 左深树不是低级实现。它牺牲部分 bushy 计划，换来流水线和可控搜索；在星型事实表查询里，左深计划常常已经足够好。
• Bushy 枚举不是越多越好。第三节实验显示团图 12 表的 CSG-CMP 候选已达 261,625；若再乘物理算子和 trait，规划时间会成为问题。
• Hint 不是根治。Hint 能验证“如果按这个顺序会更快”，但统计信息仍然错时，下一条相似 SQL 可能继续失败。
• 真实执行反馈很有价值，但不能替代优化器正确性。自适应 re-optimization、Bao 这类 feedback 方法都需要安全边界。

十、复现程序说明

reproduce/query_optimizer_experiment.py 做三件事：

1. 枚举 chain、star、clique 三种查询图在 \(n=4..12\) 时的连通子集、左深候选和 CSG-CMP 候选；
2. 在固定 6 表查询图上注入选择率估计误差，记录最大 q-error、所选计划真实代价和真实最优代价；
3. 生成 plan-enumeration.svg、cardinality-error.svg 与 cascades-memo.svg。

复现命令如下（需要 Python 3 与 matplotlib；脚本只输出计数与代价，不计时）：

cd post/algorithms/60-query-optimizer/reproduce
taskset -c 15 python3 query_optimizer_experiment.py
cat results/summary.txt

输出应与第三、五节表格一致：n=12 时 chain/star/clique 的候选数分别为 132/11,275/24,564（左深）和 286/11,264/261,625（CSG-CMP）；sigma=2.0 时 median_q=21.12、p90_regret=4.69、worst=44.98。

如果系统 Python 没有 matplotlib，安装依赖或使用带 matplotlib 的虚拟环境即可；脚本本身不依赖本机私有路径。生成图使用固定 svg.hashsalt，没有墙钟时间元数据。

十一、参考资料

源码与文档

• PostgreSQL REL_16_9, src/backend/optimizer/path/joinrels.c：join_search_one_level()、make_rels_by_clause_joins()、make_rels_by_clauseless_joins()。
• PostgreSQL REL_16_9, src/backend/utils/misc/guc_tables.c：geqo_threshold 默认值 12。
• PostgreSQL REL_16_9, src/backend/optimizer/geqo/geqo_main.c：GEQO pool、generation 与 chromosome 搜索主流程。
• Apache Calcite 1.37.0, core/src/main/java/org/apache/calcite/plan/volcano/VolcanoPlanner.java：findBestExp()、registerImpl()。
• Apache Calcite 1.37.0, RelSet.java 与 RelSubset.java：Volcano planner 的等价集合与 trait 子集。

核心论文

• P. G. Selinger, M. M. Astrahan, D. D. Chamberlin, R. A. Lorie, T. G. Price, “Access Path Selection in a Relational Database Management System”, SIGMOD 1979, pp. 23–34.
• Goetz Graefe, William J. McKenna, “The Volcano Optimizer Generator: Extensibility and Efficient Search”, ICDE 1993, pp. 209–218.
• Goetz Graefe, “The Cascades Framework for Query Optimization”, IEEE Data Engineering Bulletin 18(3), 1995, pp. 19–29.
• Yannis E. Ioannidis, Stavros Christodoulakis, “On the Propagation of Errors in the Size of Join Results”, SIGMOD 1991, pp. 268–277.
• Viktor Leis, Andrey Gubichev, Atanas Mirchev, Peter Boncz, Alfons Kemper, Thomas Neumann, “How Good Are Query Optimizers, Really?”, Proceedings of the VLDB Endowment 9(3), 2015, pp. 204–215.

Join 枚举论文

• Guido Moerkotte, Thomas Neumann, “Analysis of Two Existing and One New Dynamic Programming Algorithm for the Generation of Optimal Bushy Join Trees without Cross Products”, VLDB 2006, pp. 930–941.
• Guido Moerkotte, Thomas Neumann, “Dynamic Programming Strikes Back”, SIGMOD 2008, pp. 539–552.

学习型优化器

• Ryan Marcus, Parimarjan Negi, Hongzi Mao, Chi Zhang, Mohammad Alizadeh, Tim Kraska, Olga Papaemmanouil, Nesime Tatbul, “Neo: A Learned Query Optimizer”, Proceedings of the VLDB Endowment 12(11), 2019, pp. 1705–1718.
• Ryan Marcus, Parimarjan Negi, Hongzi Mao, Nesime Tatbul, Mohammad Alizadeh, Tim Kraska, “Bao: Making Learned Query Optimization Practical”, SIGMOD 2021, pp. 1275–1288.

实验

• reproduce/query_optimizer_experiment.py：本文第三、五、十节的枚举计数、基数误差实验与三张 SVG 的生成脚本。

系列导航： - 上一篇：Join 算法：嵌套循环、排序归并与 Hybrid Hash 的代价和实现 - 下一篇：数据库缓冲池替换：LRU-K、2Q 与生产级扫描保护

相关阅读： - Join 算法：嵌套循环、排序归并与 Hybrid Hash 的代价和实现 - 数据库缓冲池替换：LRU-K、2Q 与生产级扫描保护 - 页面置换算法：从 OPT、LRU 到 ARC 与 Linux 页面回收