深入理解数据库查询优化器：从基于代价的优化到自适应执行

引言

查询优化器是数据库系统中最核心的组件之一，它负责将用户提交的SQL语句转换为最高效的执行计划。一个优秀的优化器可以将查询性能提升数个数量级，而一个糟糕的选择可能导致系统崩溃。本文将深入剖析查询优化器的核心原理，从经典的基于代价优化（Cost-Based Optimization）到现代的自适应执行（Adaptive Execution），带你理解这个数据库"大脑"的运作机制。

1. 查询优化的基本架构

现代查询优化器通常采用三段式架构：

• 解析与重写层（Parser & Rewriter）：将SQL文本转换为逻辑计划视图，并进行子查询展开、视图替换、谓词下推等逻辑优化
• 优化器核心（Optimizer Core）：生成候选物理计划，通过代价模型选择最优方案
• 执行引擎（Execution Engine）：执行最终选定的物理计划，并在运行时反馈调整

2. 逻辑优化：关系代数的魔法

逻辑优化阶段基于关系代数等价变换规则，不关心物理实现方式。核心技术包括：

2.1 谓词下推（Predicate Pushdown）

将过滤条件尽可能推向数据源，减少中间结果集大小。优化器通过分析选择条件的引用列，将其下推到扫描节点或连接节点之前执行。

2.2 子查询去相关（Subquery Decorrelation）

相关子查询（Correlated Subquery）是性能杀手，因为它对外层每一行都要重新执行。优化器通过转换为Semi-Join或Anti-Join来消除这种N+1查询模式。

2.3 列裁剪与投影下推

在列式存储引擎中，列裁剪能显著减少I/O。优化器分析所有表达式引用的列，在扫描阶段只读取必要的列。

3. 基于代价的优化（CBO）

代价优化器是现代数据库的标准配置，其核心思想是为每个候选计划估算执行代价，选择最小值。

3.1 统计信息：优化的基石

优化器依赖准确的统计信息来估算行数和代价。关键统计量包括：

• 基数（Cardinality）：表的总行数和不同值的数量（NDV）
• 直方图（Histogram）：数据分布的形状，包括等宽直方图、等高直方图、压缩直方图
• MCV（Most Common Values）：高频值列表及其频率
• 相关性（Correlation）：物理存储顺序与逻辑值的相关性

3.2 基数估算的挑战

最古老也最棘手的问题是连接基数估算。经典假设（独立性假设）认为多列过滤条件的选择率等于各列选择率的乘积，这在列相关时会产生严重偏差。现代优化器采用以下技术改进：

• 多维直方图捕获列间相关性
• 随机采样运行实际查询片段获取统计
• 机器学习模型学习数据分布特征

3.3 代价模型

代价模型将物理操作转换为可比较的代价值，通常表示为：

Cost = w_io × IO操作 + w_cpu × CPU操作 + w_net × 网络传输 + w_mem × 内存占用

权重系数的调优需要通过大量真实工作负载标定，不同场景（OLTP vs OLAP）差异巨大。

4. 搜索空间与动态规划

连接顺序（Join Order）是优化器面临的最核心决策。N张表的连接有N!种排列和(2N-2)!/(N-1)!种拓扑结构，穷举不可行。

4.1 自底向上动态规划（Bottom-Up DP）

System R开创的DP算法按子集大小递增计算最优计划。对每个表子集，枚举所有可能的分割方式，保留每个子集的最优解。复杂度O(3^N)，实际中通过剪枝控制在可接受范围。

4.2 遗传算法（Genetic Algorithm）

PostgreSQL的geqo模块对大表连接使用遗传算法：随机生成初始种群，通过交叉和变异产生新代，以代价为适应度函数，收敛到近似最优解。适合20+表的复杂查询。

4.3 Top-Down搜索（Memo结构）

SQL Server和Cascades框架采用Top-Down探索，通过Memo结构缓存等价表达式和已探索的子树。好处是支持更丰富的优化规则，可按需剪枝。

5. 自适应执行：运行时优化新范式

传统优化器在查询开始前就确定最终计划，当统计信息不准或运行时环境变化时会导致严重性能退化。自适应执行将部分决策延迟到运行时。

5.1 自适应连接（Adaptive Join）

SQL Server 2017引入的动态自适应连接在运行时监测实际行数。如果发现Hash Join的实际输入远小于预期，可动态切换为Nested LoopJoin，避免内存溢出和浪费。

5.2 弹性分区（Adaptive Partitioning）

Spark AQE（Adaptive Query Execution）在Shuffle后根据实际分区大小决定是否合并过小的分区（Coalesce）、拆分过大的分区（Split）、或切换Broadcast Hash Join。这解决了静态分区数难以调优的问题。

5.3 运行时缓存与物化

重复子计划在复杂查询中极常见。SQL Server的Reactive Cache在运行时检测重复子表达式并自动创建临时物化视图；Oracle的Result Cache则缓存整个查询结果，当基表数据未变更时直接返回。

6. 机器学习驱动的查询优化

近年来ML在查询优化领域取得突破性进展：

6.1 Learned Index与基数估算

Deep Unsupervised Learning（如Normalizing Flows）数据分布建模精度远超传统直方图。Google的Neural Network Cardinality Estimator在复杂相关性下将估算误差从数量级降低到2-5倍。

6.2 基于强化学习的优化器

pg的BayesPlan和Microsoft的Bao使用强化学习（RL）训练策略网络，将连接顺序决策建模为马尔可夫决策过程。Bao在TPC-H基准上能自动识别出优于SQL Server默认选择的计划，平均提升15-30%性能。

6.3 查询性能预测

训练回归模型直接在查询编译时预测执行时间，无需执行。Facebook的QueryFormer和CardTinker通过Transformer编码查询结构和条件，预测误差在10%以内，可用于在线查询路由和资源分配。

7. 工业级优化器实践

7.1 PostgreSQL优化器

PostgreSQL使用带geqo的CBO，支持GEQO_THRESHOLD触发遗传算法。其代价模型基于seq_page_cost、random_page_cost等参数调优。扩展性方面，pg_hint_plan允许人工指定执行计划，pg_stat_statements提供性能数据反馈。

7.2 MySQL优化器演进

从MySQL 5.6到8.0，优化器发生巨变：持久化统计信息（5.6）、直方图支持（8.0）、隐藏索引（8.0）、Hash Join（8.0.18）、EXPLAIN ANALYZE（8.0.18）将估算与实际行数并列展示，极大便利了诊断。

7.3 分布式优化器：CockroachDB TiDB

分布式优化器面临额外挑战：数据分布（Partitioning）、Locality感知、网络传输代价估算。使用Gossip协议同步节点统计信息，但存在统计信息过时问题。TiDB的星型模型通过运行时Feedback不断修正估算。

8. 未来展望

查询优化器仍在快速演进，几个值得关注的方向：

• 混合事务分析处理（HTAP）：优化器需同时考虑行存和列存的访问代价，自动选择执行位置
• Serverless数据库：弹性资源假设下，代价模型需考虑冷启动、并发预热和跨节点数据共享
• AI原生优化器：完全基于学习的优化器可能消除对统计信息的依赖，直接从数据分布和硬件特征学习最优计划
• 跨查询优化：面向工作负载的优化，多个查询间共享中间结果、连接操作符和物化视图

总结

查询优化器从System R诞生至今经历了半个世纪的发展，从简单的规则优化到复杂的代价模型，再到如今的机器学习和自适应执行。其本质是在庞大搜索空间中寻找最优解的约束满足问题。理解优化器原理，不仅是DBA和内核开发者的必备技能，更是每个数据库使用者写出高性能SQL的关键。选择合适索引、保持统计信息准确、理解执行计划输出——这些实践都建立在对优化器工作原理的深入理解之上。