数据库优化器学习路线：从经典理论到工程实践

一、先理解优化器到底在解决什么问题

很多开发者第一次接触优化器，是从一条执行缓慢的 SQL 开始的。明明逻辑上等价的写法，执行耗时却可能相差几十倍。造成这种差异的根源在于：SQL 是声明式语言，它只描述“要什么”，不描述“怎么算”。数据库必须自行决定以何种顺序、何种算法、何种数据访问路径来完成查询。

优化器的核心任务，可以概括为三个层次：

1. 逻辑优化：在关系代数层面改写查询，使等价表达式在逻辑上更优，例如谓词下推、投影裁剪、子查询解嵌套。
2. 物理优化：为逻辑算子选择具体实现，例如选择哈希连接还是嵌套循环连接，选择全表扫描还是索引扫描。
3. 代价估算：对候选执行计划进行成本预估，选择代价最小的计划。

理解这三个层次，是后续学习所有优化器技术的主线。很多具体算法和论文，本质上都是在回答其中某一层的问题。

二、从经典论文建立知识骨架

优化器领域有一条清晰的研究脉络。与其零散阅读博客，不如沿着关键论文逐步深入。

2.1 奠基阶段：代价模型与访问路径

1979 年的经典论文《Access Path Selection in a Relational Database Management System》第一次系统性地解决了“访问路径选择”问题。它提出了基于统计信息的代价估算模型，为后续几乎所有基于代价的优化器奠定了基础。

学习这篇论文时，建议重点关注三点：

• 如何利用表的基数、选择率来估算中间结果集大小；
• 如何比较顺序扫描与索引扫描的代价；
• 多表连接时如何决定连接顺序。

这些看似基础的内容，在今天依然被广泛使用。即使是最现代化的分布式优化器，其代价模型的核心思路仍然可以追溯到这篇论文。

2.2 搜索框架：从动态规划到 Volcano 与 Cascades

有了代价模型，下一个问题是如何在巨大的计划空间中高效搜索。早期系统普遍采用自底向上的动态规划，即先确定单表访问方式，再逐步扩大连接集合，记录每个子集的最优计划。

但动态规划在连接表数量较多时面临指数级膨胀。后续提出的 Volcano 优化器生成器与 Cascades 框架，将优化过程抽象为“规则驱动”的重写系统。它不再固定搜索顺序，而是通过声明式规则驱动逻辑重写与物理实现选择，支持更灵活的搜索策略。

对于工程实践者来说，Volcano/Cascades 的价值不只在于算法本身，更在于它展示了一种可扩展的优化器架构：将“规则”与“搜索引擎”解耦，新增优化能力时不需要重写整个优化器。

2.3 子查询与聚合优化

子查询解嵌套是逻辑优化的核心难题之一。2001 年的《Orthogonal Optimization of Subqueries and Aggregation》系统阐述了子查询与聚合之间的正交优化关系，提出了将两者分离处理的框架。后续研究进一步扩展到任意子查询的解嵌套方法。

实际开发中，这类问题的价值极高。一个含有 NOT EXISTS 或 IN 子查询的 SQL，经过正确的解嵌套改写后，执行计划可能从相关子查询的逐行求值变为高效的反连接或半连接。

三、实践层面的关键设计

理论学习最终要落到工程实现。以下是构建或深度使用优化器时最值得关注的几个工程维度。

3.1 统计信息与基数估算

优化器的决策质量高度依赖统计信息的准确性。在单表情况下，需要掌握直方图、高频值、空值比例等基础统计手段；在多表连接情况下，则要考虑列之间的相关性。

一个常被忽视的问题是统计信息的时效性。数据分布剧烈变化后，过期的统计信息可能导致优化器选择错误计划。现代系统通常提供自动或手动的统计信息收集机制，并结合采样来平衡准确性与开销。

3.2 执行计划的稳定性与可解释性

优化器生成计划后，开发者往往需要理解“为什么这样选”。因此，计划的可解释性至关重要。良好的优化器应当能输出结构清晰的计划树，标明每个算子的代价估算、行数估算和关键决策依据，最好能提供提示机制，让用户在必要时进行干预。

3.3 测试与验证

如何验证优化器的正确性与有效性？答案是建立一套系统的测试方法论。

• 正确性测试：使用大量生成的 SQL，对比不同计划下返回结果是否一致。
• 准确性测试：校验优化器估算的行数与真实执行行数之间的偏差。
• 性能回归测试：对固定 SQL 集，比较优化器版本升级前后的执行耗时。

测试的难点在于 SQL 空间巨大，需要结合随机查询生成、模板化查询集和真实业务负载来获得足够覆盖。

四、面向现代场景的延伸

随着数据规模扩大和架构演进，优化器面对的场景也在变化。

4.1 分布式环境下的优化

在分布式数据库中，优化器除了考虑单机代价外，还要考虑数据传输代价。连接顺序的选择不再只由计算成本主导，数据是否需要在节点之间重分布、能否利用数据本地性完成局部聚合，都会显著影响整体性能。

这一领域的关键论文涉及如何在分布式执行计划中系统性地加入数据交换算子，将其纳入统一代价模型进行搜索。对于希望深入理解分布式分析引擎的开发者，建议在掌握单机优化器后再进入这一主题。

4.2 实时分析场景的权衡

在实时分析数据库中，查询通常要求毫秒到秒级响应，但数据持续写入。这给优化器带来两个变化：一是统计信息必须快速更新甚至在线更新；二是计划搜索空间需要更严格的控制，不能为了寻找最优计划而耗费过长的优化时间。实践中常见的做法是对搜索空间进行裁剪，或用启发式策略先确定大部分结构，再对局部进行代价搜索。

五、一条建议的学习路线

如果从零开始学习数据库优化器，可以参考以下顺序：

1. 复习关系代数、等价变换规则，理解逻辑优化的基础语言；
2. 阅读 1979 年的访问路径选择论文，理解代价模型的基本构建方式；
3. 学习 Volcano/Cascades 框架，掌握规则驱动优化的核心思想；
4. 精读子查询优化相关论文，理解解嵌套的典型模式；
5. 深入一个开源数据库的优化器源码，从代码层面验证所学理论；
6. 扩展到分布式优化与实时场景，了解工业界的设计取舍。

整个过程不必追求一次吃透所有论文。优化器是一个庞大的系统，先建立整体地图，再针对自己工作中遇到的具体问题定点深入，往往效果更好。真正掌握优化器的人，不是记住了所有规则，而是在面对一条慢 SQL 时，能够从逻辑改写、物理实现和代价估算三个层面快速定位问题所在。