查询优化器：System R 动态规划、Cascades Memo 与基数误差
内容提要
本文梳理关系查询优化器的发展主线：System R 以左深动态规划和 interesting orders 奠定代价优化范式；Volcano/Cascades 通过 memo、规则与物理性质组织搜索；DPccp/DPhyp 改进连接枚举。实验表明，查询图稠密度比表数量更影响枚举规模，基数估计误差是产生坏计划的主因。PostgreSQL 16 默认在超过 12 个表时转为 GEQO，学习型优化器宜作为补充。
延伸解读
查询图稠密度：被忽视的优化难度指标
文章实验表明，连接顺序枚举的规模不仅取决于表数量，更受查询图稠密度影响。链式查询12张表仅有78个连通子集，而星形查询连通子集接近2^11，团图则产生261,625个CSG-CMP候选。这意味着仅凭“表数超过12”判断优化难度可能误导。实际工程中，应关注查询图的连接结构，对于星形或团图查询，即使表数不多，也可能需要调整优化器阈值或采用启发式搜索。
基数估计误差：坏计划的主要根源
文章引用实验显示，当选择率估计误差增大时，计划真实代价的尾部风险快速上升，最坏代价比可达44.98。这与Leis等人的结论一致：基数估计误差是导致坏计划的主因，而非代价模型或枚举算法。因此，优化器调优应优先改善统计信息质量，如更新统计、增加多列统计、处理列相关性，而非过度调整代价参数或搜索策略。
PostgreSQL GEQO阈值：规划时间与计划质量的权衡
PostgreSQL 16默认在FROM items达到12时从穷举DP切换到GEQO遗传搜索，以限制规划时间。这并非硬性限制，用户可调整geqo_threshold或关闭GEQO，但代价是规划时间可能急剧上升。对于复杂查询，若规划时间过长，可考虑分解查询或物化中间结果；若计划质量差，可临时调整阈值，但需权衡规划开销。
学习型优化器的现实定位：补充而非替代
文章指出，学习型优化器如Neo和Bao并非取代传统优化器，而是作为补充。Bao通过选择hint限制动作空间，降低风险；Neo则引导搜索。它们面临安全性、分布漂移、冷启动和可解释性等开放问题。因此，在生产环境中，学习型优化器更适合用于基数估计或计划选择，而非完全替代现有优化器。
Q&A
System R 优化器中的 interesting orders 是什么？为什么它重要？
Interesting orders 是 System R 提出的概念，指对后续算子有价值的输出顺序。局部最便宜的计划可能不是全局最优，因为一个稍贵的索引扫描可能输出有序结果，让上层 merge join、ORDER BY 或 GROUP BY 省去排序。因此优化器需要为每个子集按物理性质保留多个候选计划，而不是只保留一个最低代价计划。
查询图的结构如何影响连接顺序枚举的规模？
查询图的结构比表数量更影响枚举规模。链式查询的连通子集少，搜索空间小；星形查询的连通子集接近 2^(n-1)；团图则因任意两个不相交子集都能连接，导致 bushy 候选数远多于左深候选。例如 12 张表时，链、星、团的左深候选分别为 132、11275、24564，而 CSG-CMP 候选分别为 286、11264、261625。
Cascades 优化器中的 memo 是什么？它如何组织搜索？
Memo 是等价表达式的 DAG，不是树。一个 group 表示同一逻辑结果的等价类，group expression 是具体表达式，其孩子指向 group。这样交换律、结合律生成的新表达式可以共享子问题。Winner 不是全局唯一的，同一个 group 在不同 required trait 下可能选择不同物理计划，例如无序时 hash join 最便宜，有序时 merge join 加排序更便宜。
基数估计误差对查询计划质量有什么影响？
基数估计误差是导致坏计划的主因。实验表明，轻微误差不一定改变计划，中位数代价比常为 1；但尾部风险增长很快，当多条边同时被严重低估或高估时，优化器可能提前物化大中间结果，最坏代价比可达 44.98。Leis 等人的研究也指出，如果喂给优化器真实基数，很多系统即使用简单代价模型也能得到接近最优的计划。
PostgreSQL 16 在表数量多时如何处理连接顺序优化？
PostgreSQL 16 默认在 FROM items 数达到 12（geqo_threshold 默认值）时，从穷举动态规划切换到 GEQO（遗传查询优化器），以限制规划时间。用户可调整 geqo_threshold 或关闭 GEQO，但代价是规划时间可能急剧上升。常规搜索仍按 join relation 大小分层，并生成有限的 bushy 组合。
学习型优化器（如 Neo 和 Bao）与传统优化器是什么关系？
学习型优化器更现实的位置是补充估计或选择，而不是取代传统优化器。Neo 用神经网络评估候选计划引导搜索；Bao 在现有优化器外选择 hint 集合，让底层数据库负责合法计划生成。它们都承认传统优化器已有大量工程约束，学习组件不能绕过执行器、事务语义和物理算子限制。学习型方向仍面临安全性、分布漂移、冷启动和可解释性等开放问题。
