数据库优化器系统学习路径：论文、源码与实践

一、先建立全局认知：优化器到底在解决什么问题

优化器决定了一条SQL“怎么执行”：在语义等价的众多执行方案中，挑选出预估代价最低的那一个。无论何种数据库内核，整条链路都可以概括为：

词法/语法解析 → 语义分析与名称绑定 → 查询改写（基于规则的等价变换）→ 逻辑计划生成 → 物理计划选择（基于代价）→ 交付执行引擎

围绕这条链路，优化器的核心问题始终是三个：

1. 等价性：哪些变换是语义保持的？谓词下推、聚合上推、子查询去嵌套，本质上都是在回答这个问题；
2. 搜索空间：多表连接的顺序是组合爆炸的，如何高效枚举并剪枝？动态规划、贪心、随机化搜索各自适用于什么规模；
3. 代价评估：如何利用统计信息估算中间结果基数与算子开销？基数估计的误差直接决定最终计划的合理性。

建议在正式开始论文精读之前，先能用自己的话讲清楚“这三个问题分别难在哪里”，后续阅读才不会迷失在细节中。

二、分阶段学习路径

阶段一：打地基（约1～2个月）

• 关系代数与SQL语义：重点关注三值逻辑与NULL的处理、聚合与分组语义、嵌套子查询的求值语义——大量改写规则的正确性证明都依赖这些细节；
• 执行模型：算子的迭代器模型、向量化执行、编译执行。不理解执行模型，就无法理解“代价从何而来”；
• 学会读执行计划：通过EXPLAIN及其扩展形式观察真实计划，先积累对“好计划与坏计划”的直觉。

阶段二：论文精读（2～3个月，可持续进行）

• 按主题组织阅读，而非按发表时间；先综述后专题，先经典后前沿；
• 每篇输出一份笔记：动机、核心机制、与前人工作的差异、遗留的开放问题。

阶段三：源码验证（与阶段二并行）

把论文中的概念映射到源码中的具体模块，是“啃源码不低效”的关键所在。

阶段四：动手实现

写一个玩具优化器，把知识形成闭环。

三、按主题整理的论文阅读地图

以下清单按主题分组，均可在公开学术渠道检索原文。

1. 基石：基于代价的优化

• 《Access Path Selection in a Relational Database Management System》（1979）：代价优化的开山之作，提出了访问路径选择、连接顺序的动态规划搜索、保留有用排序（interesting order）等概念，几乎所有现代优化器中都能找到它的思想痕迹；
• 《An Overview of Query Optimization in Relational Systems》（1998）：综述性文章，系统梳理等价变换规则全景，适合作为“地图”最先阅读；
• 《Query Processing in Main Memory Database Management Systems》（1988）：主存数据库的查询处理，为理解内存型执行的代价特性提供视角。

2. 优化器架构：搜索框架的演进

• 《Grammar-like Functional Rules for Representing Query Optimization Alternatives》（1988）：用类文法规则描述备选方案，是规则化描述思想的早期探索；
• 《The Volcano Optimizer Generator》（1993）：将变换规则与搜索策略解耦，构建统一框架；
• 《The Cascades Framework for Query Optimization》（1995）：在记忆结构上执行目标驱动的动态规划搜索，规则、任务、目标分层清晰，是多个现代优化器的直接设计蓝本；
• 面向大数据的模块化优化器架构论文（2014）：将优化器拆分为可独立演进、可独立测试的模块，服务于大规模分布式分析场景；
• 某分布式实时分析数据库的现代优化器设计论文（2016）：展示经典框架在分布式实时分析场景下的工程化扩展，能看到“论文理念如何落地”。

3. 查询变换与子查询优化

• 《Query Optimization by Predicate Move-Around》（1994）：谓词的移动与推导；
• 《Eager Aggregation and Lazy Aggregation》（1995）：聚合的提前与延迟，包括将聚合下推到连接之下；
• 《Parameterized Queries and Nesting Equivalences》（2000）：对嵌套查询等价性的形式化刻画；
• 《Orthogonal Optimization of Subqueries and Aggregation》（2001）：将子查询优化与聚合优化正交化，缓解规则组合爆炸；
• 利用窗口聚合消除子查询的论文（2003）：针对特定形态的相关子查询给出消除方法；
• 某商业数据库关于基于代价的查询变换的论文（2003）与子查询优化增强的论文（2009）：工业界将“规则改写”纳入代价搜索的代表性实践；
• 《Unnesting Arbitrary Queries》（2015）：一般化的子查询去嵌套，堪称该主题的集大成之作；
• 《The Complete Story of Joins》：从语义层面讲清楚连接的分类与相互转换关系。

4. 连接顺序优化与搜索算法

• 连接顺序搜索的分析类论文：对比穷举、贪心、随机化等策略在搜索规模与计划质量之间的取舍。

5. 优化器测试与验证

• 《Testing the Accuracy of Query Optimizers》：研究如何验证优化器产出计划的最优性与代价估算的准确性，工程价值极高却常被忽视。

四、源码阅读不低效的五个方法

直接从第一行代码开始通读，是效率最低的方式。推荐如下方法：

1. 自顶向下走主干：选一条典型SQL，在解析入口处打断点，单步跟踪直到计划生成结束，先画出调用主干，再逐层补充细节；
2. 把内部结构可视化：善用执行计划输出与优化器的跟踪开关，打印每一步改写前后的计划树，与论文中的变换规则一一对应；
3. 用回归测试当文档：内核测试用例是“行为语义的最小完整描述”，比注释更可靠；
4. 建立概念-模块映射表：例如论文中的代价估算对应统计信息模块与代价公式函数，搜索策略对应连接顺序枚举实现，维护一张映射表，读到哪补到哪；
5. 反向实验：临时调整代价权重或伪造统计信息，观察执行计划翻转，倒推代价模型的敏感点。

五、动手实践：让知识闭环

1. 实现一个玩具优化器。面向最小SQL子集（单表过滤＋两三表连接＋分组聚合），依次实现：语法树到逻辑计划的转换、若干改写规则（谓词下推、投影裁剪）、简单基数估计、连接顺序动态规划。搜索部分可参考如下伪代码：

best[S]：关系集合S的最优（计划，代价）
for size = 1 to n:
    for each 满足 |S| == size 的集合 S:
        for each S 的二分拆分 (S1, S2):
            for each 连接算法 j:
                plan = Join(best[S1].plan, best[S2].plan, j)
                if cost(plan) < best[S].cost:
                    best[S] = (plan, cost(plan))
return best[全部关系]

2. 构造对照实验。例如：

EXPLAIN SELECT o.id, c.name
FROM orders o JOIN customer c ON o.cid = c.id
WHERE o.amount > 100;

在不同索引、不同数据分布、不同统计信息下对比执行计划，验证自己对基数估计的判断。

3. 结合真实环境印证。在实际生产或云上托管数据库（例如百度智能云的数据库类服务）中，借助慢查询分析、执行计划查看等通用能力，把理论学习与真实负载互相印证，逐步形成优化直觉。

六、常见误区与建议

• 试图通读全部源码：正确姿势是“按需深入”，以论文概念为索引定向阅读；
• 只读论文不碰代码：概念容易悬空；反过来只碰代码不读论文，则只见树木不见森林；
• 忽视统计信息：优化器一半的复杂度在代价估计，而代价估计的根基是统计信息的采集与使用；
• 忽视优化与执行的耦合：算子代价与执行模型强相关，脱离执行引擎谈优化器是不完整的；
• 贪多求全：先在一条主线上打穿（例如“连接顺序＋代价模型”），再横向扩展到子查询、窗口函数等主题。

七、结语

优化器学习是一场“论文—源码—实践”三线并进的长跑：论文给你体系与语言，源码给你工程真相，动手实现给你肌肉记忆。建议持续以笔记输出驱动输入，遇到不确定的语义或代价行为时，用小实验验证而非凭记忆下结论。坚持半年，你会发现自己审视执行计划的眼光已经完全不同。