数据库查询优化器的现代演进：从基于成本的优化到自适应执行引擎

引言

查询优化器是数据库管理系统的"大脑"——它将SQL声明式查询转化为高效的执行计划。随着数据规模和工作负载复杂度的指数级增长，传统基于静态成本模型的优化器面临严峻挑战。从System R的Cascades框架，到现代数据库的自适应执行和机器学习驱动的基数估计，查询优化技术正在经历一场深刻的范式变革。

1. 查询优化的理论基础

查询优化的核心挑战是搜索空间爆炸问题。对于n个表连接查询，可能的执行计划数量为O(n!)。穷举所有计划在n>5时不可行，因此需要智能搜索策略。

查询代数基础：关系代数提供查询优化的数学基础。等价变换规则（选择下推、投影下推、连接交换律结合律）定义了合法的搜索空间。查询优化的本质是在等价计划空间中寻找代价最小的那一条路径。

System R优化器：1979年System R引入的基于成本的优化(CBO)成为当代数据库的标准方法。核心思路：对每种候选计划估算I/O、CPU、网络成本，选择总成本最小的计划。比较左深树与浓密树两种形状——左深树更适合流水线执行，因此大多数优化器优先搜索左深树(搜索空间从O(n!)降到O(2^n))。

2. 统计信息与基数估计

成本模型依赖准确的基数估计——即每个中间结果集的元组数量。传统方法使用数据分布统计信息：直方图（等宽、等高、压缩直方图）、NDV(不同值数量)、相关性统计。

直方图技术：等宽直方图对均匀分布效果良好，但对倾斜数据会产生巨大误差。等高直方图(Equi-Height)保证每个桶包含近似相同元组数，更适合倾斜数据。压缩直方图(Compressed Histogram)对高频值单独存储频率，低频值用直方图近似——混合方法在精度与存储之间取得平衡。

多列相关性：传统优化器假设列间独立——"WHERE city=A AND age=30"的过滤率等于两列过滤率的乘积。但现实中城市与年龄分布并不独立(如某些城市人口更年轻)。PostgreSQL的CREATE STATISTICS命令和SQL Server的多列统计对象可以捕获部分相关性，但高维统计的实际存储开销巨大。

3. Cascades框架与Volcano模型

Cascades是现代查询优化器的代表架构(SQL Server、Oracle、TiDB的优化器均基于此或其变种)。核心创新是上下文驱动(Context-Driven)的优化：

搜索组织：优化器维护已探索的子计划表达式组和已发现的等价组。每个等价组(Group)包含逻辑等价但物理形式不同的表达式。优化过程逐步将逻辑组转化为物理组。

规则引擎：将等价变换规则实现为可组合的对象——规则转换器(Rule)将一种逻辑表达式转化为另一种。常见规则包括：JoinCommutativity(交换)、JoinAssociativity(结合)、ProjectJoinTranspose(投影下推)。

记忆化与剪枝：Cascades通过记住每个等价组的最低成本表达式来避免重复计算。一旦找到更优解，立即剪枝更昂贵的替代路径，大幅减少搜索空间。

4. 自适应查询执行(AQE)

传统优化器在运行时"确定"执行计划后不再更改，但静态计划面对中间结果基数估计错误时很脆弱。自适应查询执行(AQE)在运行时动态调整计划。

Spark AQE：Spark 3.0引入的核心特性：动态合并Shuffle分区(小分区合并提升I/O效率)、动态切换Join策略(BroadcastJoin与SortMergeJoin运行时切换)、动态优化数据倾斜(将大倾斜分区拆分为小分区并行处理)。运行时统计信息打破了"提交时定计划"的限制。

Oracle自适应计划：Oracle的Adaptive Statistics在首次执行后收集运行时实际基数，与预估比较。当偏差超过阈值，后续执行切换到更优的计划。连接Broadcast与Hash的切换是典型场景——小表超过Broadcast阈值时自动降级为Hash Join。

5. 机器学习驱动的优化

近年来，ML技术被引入解决传统优化器的核心难点：

<

基数估计：Neo(Learn database via deep neural networks)和Deep Unsupervised Cardinality Estimation用深度学习替代直方图。神经网络直接学习联合概率分布，对高维相关性有更好的建模能力——但推理延迟是当前瓶颈。

衍生执行计划：DQN(Deep Q-Network)训练强化学习代理选择最优Join顺序。在合成与真实工作负载上，学习优化器在准确率上可与最先进的手工优化器媲美，但泛化到未知跨工作负载仍需进一步研究。

端到端替代：DataBaby等研究尝试用神经网络完全替代传统查询优化器——将数据库模型和工作负载以张量输入，直接输出最优执行计划。该方向仍处于早期阶段，但展示了未来优化器的可能形态。

6. 分布式场景的新维度

分布式查询优化引入额外复杂度：网络传输成本主导执行时间、节点间数据重分布(Shuffle)代价高、数据倾斜放大热点节点效应。

CBO for Distributed：C-Store(Vertica, 2005)开创的分布式优化器需额外决定：数据物理放置(本地计算vs远程获取)、副本选择（就近原则vs负载均衡）、并行度设置。执行计划的空间顶点是本地执行的逻辑计划，边是各种Repartitioning/Redistribution操作。

TiDB的分布式优化：storage层TiKV使用RocksDB存储数据。TiDB服务器无状态，执行优化后通过Cop Task(推送到TiKV本地执行算子)或Root Task(在TiDB服务器处理)。动态选择Cop执行层级，减少网络传输。

结论

查询优化器从System R的左深树CBO，经过Cascades规则引擎，演进到今天的自适应执行和ML增强——技术的进步始终围绕同一个核心：让优化器"看"到更准确的分布，"想"出更高效的计划，"调"整更灵活地应对运行时变化。理解查询优化的原理与局限，对于写出高性能SQL和诊断复杂性能问题具有不可替代的价值。