一、查询优化的核心问题与搜索空间
关系查询优化器基于SQL语句的代数等价变换寻找代价最小的执行计划。对于一个涉及N个关系的JOIN查询，可用的左深树(left-deep)、右深树(right-deep)和灌木树(bushy)计划总数呈卡塔兰数(Catalan numbers)增长：对于N=6，笛卡尔积式的左深树已有132种可能，包含灌木树的总数达到10,395种。每一JOIN的候选算法（嵌套循环、哈希、排序归并、索引扫描）和每张表的候选访问方法（行扫描、索引扫描、索引覆盖）进一步使其组合爆炸。
查询优化的两大流派：自顶向下(Top-Down)以System R和Volcano/Cascades为代表，从目标表达式出发向下搜索匹配的子查询等效形式并使用记忆化(memoization)避免重复计算；自底向上由子表达式出发逐步构建更大的等效形式。Cascades框架将这两种策略融合在一个统一的搜索结构(Memo)中。
搜索优化的第一步是逻辑等价转换(Logical Transformation)：在代数表达式空间内应用交换律、结合律、率分配律和查询重写规则（谓词下推、投影消除、父节点消除等），将原始代数表达式爆炸式扩展为一组等效的候选逻辑计划，供物理计划搜索使用。
二、System R优化器与动态规划算法
IBM研究院在1979年的System R原型中提出了现代查询优化器的两个核心创新：基于代价的优化(Cost-Based Optimization, CBO) 和 动态规划搜索(Dynamic Programming Search)。
System R的优化器将查询中每个WHERE子句（多表JOIN条件+选择条件）转化为JOIN树和过滤条件的组合。搜索按子问题规模递增：对于N个表的JOIN，先计算最优的单表扫描计划（代价取决于可用索引和列上的基数估计），然后对{N选2}的所有两表JOIN子集计算最优计划（上一步单表计划+JOIN算法+JOIN算法的IO/CPU代价），依此类推直到覆盖所有表。
关键的剪枝策略剪枝次优计划(pruning)：对每个问题子集只保留代价最小的计划，被更高一级子问题的JOIN最优引用。现代优化器在此基础上引入物理属性(Physical Properties)感知的剪枝：对需要有序输出的子问题（如后续MergeJoin或ORDER BY），保留排序中最优的计划而非单纯总体最优，实现了"Pareto最优"保留。
这一算法在关系数较少时(N ≤ 12-15)最优，参与表数量爆炸时需引入随机器(Greedy / GOO)或遗传算法(PostgreSQL GEQO)近似搜索以避免代价过高。
三、Cascades优化框架与Memo结构
Cascades框架由Goetz Graefe在1995年提出，是Volcano优化器的进化版，被Microsoft SQL Server、Apache Calcite和Polarized等现代系统采用。其核心数据结构是Memo——一个树状分组的表达式集合，每个Group包含等价的逻辑和物理表达式，每棵子表达式树引用Memo中对应位置的子Group。
Cascades的优化由规则(Rule)驱动，规则将一个逻辑/物理表达式模式(pattern)转换为等价的表达式。规则触发后新表达式被插入Memo对应的Group中；如果该Group已完成探索(containing group's exploration完成)，后续规则不会再次探索，避免了System R动态规划中的冗余计算。
Cascades的关键优势包括：
可扩展性：新增优化规则只需在框架中注册，无需修改搜索逻辑。如添加"窗口函数下推"规则，只需定义模式匹配和转换逻辑。
需求驱动(Demand-Driven Optimization)：从根Group的最优计划需求出发，自顶向下触发子Group的物理优化而非自底向上枚举所有子集的JOIN计划，对于大型JOIN能避免不必要的优化开销。
分阶段优化(Branch-and-Bound Pruning)：搜索过程分组执行逻辑表达式探索(Legal Exploration)和物理方案优化(Physical Optimization)，每阶段之间可设置分支定界剪枝条件提前淘汰成本过高的候选方案。
动态规划+备忘录：融合自顶向下和自底向上两种搜索策略，Memo缓存避免重复计算子问题的最优解，支持物理属性感知的剪枝策略。
四、代价模型与基数估计(Cardinality Estimation)
查询优化的"最省代价计划"取决于精确的基数估计(Cardinality Estimation, #输出行数)和IO/CPU代价模型。估计误差在JOIN链中累积可导致计划质量灾难性下降。
传统代价模型：单表选择性基于均匀分布假设和列间独立性假设：谓词A=5 AND B=10的输出基数 = N_rows × sel(A=5) × sel(B=10)，sel(value) = 1/NDV（不同值个数）。列上直方图(histogram)用于范围谓词。
现代基数估计的挑战：实际数据存在强相关性（如城市名→省和区邮编），使独立性假设严重失真。处理策略包括：(a)多列统计(multi-column statistics)和交叉直方图捕获联合分布；(b)直方图与采样的混合策略；(c)运行时反馈修正(Adaptive Query Processing)。
代价函数的典型参数：a_seq_page_cost(随机IO代价, 4.0)、cpu_tuple_cost(每行处理代价, 0.01)、cpu_index_tuple_cost(索引元组代价, 0.005)和effective_cache_size(共享缓存实际使用估计)。在分布式/云数据库中还需增加网络传输代价和网络带宽参数。
学习型基数估计(Learned CE)：2020年以来研究用神经网络回归模型(如MSCN、NeuroCard)从原始数据分布直接学习条件分布P(output_rows|WHERE_clause)，突破独立性假设限制。华为CDB、Microsoft的"学习型基数估计"将该技术引入产品化。
五、分布式查询优化与适应性执行
在Share-Nothing分布式数据库(CockroachDB、TiDB、Greenplum等)中，查询优化必须考虑网络分布：
数据重分布(Redistribution)：COLOCATION JOIN要求参与表的分区键相同且分区策略兼容，否则需要BROADCAST（小表复制到所有节点）或HASH SHUFFLE（两表重分区）以局部化JOIN。优化器选择代价最低的重分布方式。
适应性运行时处理(Runtime Adaptivity)：将部分物理策略决策延迟到运行时执行时。例如Bail系统通过运行时探测(Probe)获取实际基数，动态切换JOIN算法；又如Ripple Join在数据量估计偏差时动态调整哈希表构建时间。
Cascades的分布式扩展：物理优化规则中引入网络代价，All属性网络代价考量；代价估计中引入数据倾斜因子(sketches)和分区对齐度(partition alignment)度量，以O(1)的运行时开销修正大偏差场景。
LakeHouse与Spark / Databricks SQL优化：Apache Spark SQL的Catalyst优化器也采用Cascades框架：先进行逻辑优化（如PushDownPredicate、ReplaceDistinctAggregate 等规则），再基于统计信息选择物理策略（如 SortMergeJoin 与 BroadcastHashJoin 的选择），最后生成RDD/DAG执行计划。Databricks的Photone引擎进一步通过 QE(Query Execution)运行时反馈适应性调整运行中计划(Adaptive Query Execution, AQE)，融合Spark Catalyst逻辑AQE与Photone运行时AQE以应对数据分布偏差。
六、查询优化未来展望
查询优化正在经历"从规则到学习"的范式转变：传统规则型优化器的基数估计误差是导致次优计划的根本原因，而学习型优化器以数据分布内在规律为优化依据，在复杂查询和跨机器分布式场景中展现优势。
同时，数据库内机器学习(ML inside DB)与查询优化器深度融合正成为新范式：Oracle Database内置ML模型用于执行计划推荐，Microsoft SQL Server 2022的度量和预测性计划(Hinted Plan)用历史执行特征维护稳健性，Microsoft的基于机器学习的优化器(LETO)在统计信息缺失时利用时序特征预测基数。这一融合趋势预示了查询优化器走向自治(autonomous)和自调优(self-tuning)的演进方向。
云原生场景中的优化已扩展至端到端的智能查询处理：存储层自适应Indexing、网络层跨层优化(Network-aware optimization)、缓存层基于增量物化视图的Workload caching；同时查询优化器需支持多目标优化(执行时间 / 硬件效率 / 成本/能耗)并适应异构硬件(向量存储加速列存、GPU加速JOIN+ROW过滤)。
发表评论 取消回复