Lec15 查询规划与优化 — 规则、启发式方法和搜索策略

前面的课程讲解了单个算子如何执行（扫描、连接、排序）。本讲退后一步，回答一个更高层次的问题：给定一条 SQL 查询，DBMS 如何选择执行哪个计划？答案涉及利用代数等价性转换逻辑表示、应用启发式规则，以及——在基于代价的优化器中——搜索等价计划空间以找到代价最低的那个。

查询规划流水线

一条 SQL 语句在执行前要经历若干阶段：

SQL 字符串
  → Parser（解析器）  → 抽象语法树 (AST)
  → Binder（绑定器）  → 逻辑计划（已解析名称和类型）
  → Tree Rewriter     → 重写后的逻辑计划（表达式简化）
  → Optimizer（优化器）→ 物理计划（具体算法和访问路径）

解析器检查语法并产生 AST。绑定器通过系统目录解析表名和列名，将它们映射到内部标识符，产生逻辑计划——一棵关系代数算子树，指定要计算什么数据，但不指定怎么计算。

优化器的任务是将逻辑计划转换为最优的物理计划——指定具体的算法（哈希连接 vs 排序归并连接）、访问方法（顺序扫描 vs 索引扫描）和算子顺序。

两种基本方法： 1. 启发式/基于规则：应用静态转换规则，通常能改善计划，但不估算代价 2. 基于代价：枚举等价计划，利用统计信息估算代价，选择最便宜的

大多数实际系统两者兼用——先做启发式重写，然后在简化后的空间中进行基于代价的搜索。

关系代数等价性

优化器重排查询计划的能力建立在等价性之上——保证两个表达式产生相同结果的代数恒等式。这些等价性定义了优化器搜索空间中的合法变换。

选择等价性

分解（级联）：

\[\sigma_{p_1 \wedge p_2}(R) \equiv \sigma_{p_1}(\sigma_{p_2}(R))\]

合取谓词可以拆分为一连串独立的选择。这是谓词下推的基础——拆分后，各个谓词可以被推到更接近数据源的位置。

交换律：

\[\sigma_{p_1}(\sigma_{p_2}(R)) \equiv \sigma_{p_2}(\sigma_{p_1}(R))\]

相邻选择的顺序不影响结果。基于代价的优化器可以重新排列，让选择性最高（或代价最低）的谓词先执行。

投影等价性

投影是幂等的——对相同列投影两次等价于投影一次：

\[\pi_{a_1}(R) \equiv \pi_{a_1}(\pi_{a_1, a_2, \ldots}(R))\]

这使得早期投影成为可能：优化器可以在树的较低位置插入投影以减少元组宽度，从而降低后续算子的 I/O 和内存开销。

连接等价性

交换律：

\[R \bowtie S \equiv S \bowtie R\]

优化器可以自由交换哈希连接的构建端和探测端，或选择嵌套循环连接的外层关系。

结合律：

\[(R \bowtie S) \bowtie T \equiv R \bowtie (S \bowtie T)\]

这是多表连接中影响最大的等价性。可能的连接顺序数量随表数量超指数增长——对于 \(n\) 张表，不同连接树的数量为卡塔兰数 \(C(n)\)。10 张表的连接有超过 170 亿种可能的顺序。

启发式/基于规则的优化

启发式优化器按固定顺序应用转换规则，不考虑实际数据。这些规则代表”通常有效”的策略：

核心启发式规则

拆分合取谓词：将 WHERE p1 AND p2 AND p3 分解为独立的过滤器
谓词下推：将选择算子尽可能推到树的底部，理想情况下推到表扫描处。这减少了计划其余部分处理的元组数量
用连接替换笛卡尔积：如果笛卡尔积后面跟着一个连接谓词上的选择，则将两者替换为单个连接算子
投影下推：将投影下推以尽早消除不需要的列，减少元组宽度
按选择性排列谓词：在过滤器链中，先计算选择性最高的谓词（消除最多元组的那个）

转换示例

考虑一个三表查询：

SELECT s.name, c.title
FROM students AS s, enrolled AS e, courses AS c
WHERE s.sid = e.sid
  AND e.cid = c.cid
  AND e.grade = 'A';

原始计划从所有三张表的笛卡尔积开始，然后是所有选择，最后是投影。启发式优化逐步转换：

拆分合取 WHERE 为三个独立的选择
下推 e.grade = 'A' 到 enrolled 的扫描处
替换笛卡尔积 + 连接谓词为适当的连接算子
下推投影以尽早丢弃不需要的列

结果是一个代价大幅降低的计划——尽早过滤意味着连接处理的元组要少得多。

启发式优化的局限性

启发式规则不考虑： - 中间结果的实际大小 - 索引的可用性或选择性 - 不同物理算子的相对代价 - 数据分布（倾斜、相关性）

启发式优化器无论数据如何都应用相同的转换。例如，它总是下推谓词——但偶尔一个谓词选择性很低，下推它只会增加开销而不减少基数。

表达式重写

在搜索最优计划之前，优化器通过表达式重写简化谓词——消除冗余或不可能条件的语法转换。

不可能/冗余谓词

-- 不可能：没有行能同时满足两个条件
WHERE val BETWEEN 1 AND 5 AND val BETWEEN 10 AND 20
→ 空结果（完全跳过执行）

-- 冗余：第二个谓词被包含
WHERE val >= 5 AND val >= 3
→ WHERE val >= 5

谓词合并

1
2
3

-- 合并重叠的 BETWEEN 谓词
WHERE val BETWEEN 1 AND 10 AND val BETWEEN 5 AND 20
→ WHERE val BETWEEN 5 AND 10

连接消除

如果执行了连接但被连接表的列都不出现在输出中，且连接条件基于外键保证匹配，则可以完全消除该连接。这有时出现在视图连接了比查询实际需要更多的表时。

基于代价的优化

启发式处理”显然有益”的转换后，在真正不同的策略之间做选择（例如哈希连接 vs 排序归并连接、不同的连接顺序）需要代价模型。优化器枚举等价计划，估算每个计划的代价，选择最便宜的。

基于代价的组件需要三样东西： 1. 枚举等价计划的方式（搜索策略） 2. 估算每个计划代价的方式（代价模型——在第 16 讲讲解） 3. 剪枝搜索空间以保持可处理性的方式

搜索策略

优化器必须探索逻辑等价计划的空间。两种主要范式：

自底向上（System R / 前向链接）

System R 优化器（1979）开创了基于代价的优化。它自底向上构建最优计划：

从基础关系开始，为每个关系找到最优访问路径（顺序扫描 vs 索引扫描）
枚举所有两表连接顺序。对每一对，考虑所有连接算法（嵌套循环、排序归并、哈希），仅保留每对的最优计划
构建三表连接，通过扩展最优两表计划，依此类推
在每个层级，剪枝严格劣于另一个具有相同结果和相同”有趣顺序”的计划

关键洞察是带有趣顺序的动态规划：一个产生有序输出的计划可能单独看不是最优的，但能节省后续的排序操作。优化器为每个（关系集合, 输出顺序）组合保留最优计划。

1
2
3

Level 1: {R}, {S}, {T} 各自的最优单表访问
Level 2: {R,S}, {R,T}, {S,T} 的最优连接计划
Level 3: {R,S,T} 的最优连接计划 — 扩展 Level 2 的赢家

对于 \(n\) 张表，这探索 \(O(2^n)\) 个子集——代价高但对典型查询（< 15 张表）可处理。这种方法只考虑左深连接树（每个连接的右孩子始终是基础表），这限制了搜索空间并保证中间结果通过流水线流过而无需完全物化。

自顶向下（Volcano / Cascades / 后向链接）

Volcano（1993）和 Cascades（1995）框架采用相反的方法：

从根节点的完整逻辑表达式开始
应用转换规则生成等价的逻辑表达式（存储在称为 memo 表的共享结构中）
对每个逻辑表达式，应用实现规则生成物理替代方案
使用分支定界剪枝递归优化子表达式——如果部分计划的代价已经超过已知最优完整计划，则放弃该分支

Optimize(LogicalExpr):
    for each equivalent expr in ApplyRules(LogicalExpr):
        for each physical impl of expr:
            cost = EstimateCost(impl)
            if cost < upper_bound:
                recursively optimize children
                update best plan

Memo 表至关重要——它确保等价的子表达式被识别并只优化一次。Memo 中的每个组代表一组逻辑等价的表达式，优化器存储每个组找到的最优物理计划。

Enforcer（强制算子）

两种搜索策略都必须处理某些算子要求的物理属性。例如，排序归并连接要求其输入按连接键排序。Enforcer 是一个物理算子（如 Sort），优化器插入它以保证所需属性。

优化器将 enforcer 作为附加选择：它比较（排序 + 归并连接）与（无需排序的哈希连接）的代价，选择更便宜的选项。

自底向上 vs 自顶向下比较

方面	自底向上（System R）	自顶向下（Volcano/Cascades）
方向	前向链接（小 → 大）	后向链接（大 → 小）
搜索模式	BFS（在 \(k+1\) 表计划之前枚举所有 \(k\) 表计划）	带记忆化的 DFS
剪枝	在每个层级丢弃被支配的计划	带上界的分支定界
树形状	通常仅左深树	可探索灌木状树
实现	更容易实现	更灵活，可扩展的规则系统
使用者	PostgreSQL, IBM DB2, MySQL	SQL Server, CockroachDB, Apache Calcite

实践中，两种方法找到的计划质量相似。自顶向下方法更具扩展性（添加新规则无需重构搜索），但更难调试。

星型和雪花型查询

数据仓库通常使用星型模式（一张事实表被多张维度表包围）和雪花型模式（维度表进一步规范化）。这些查询将一张大事实表与多张小维度表连接。

标准动态规划枚举（\(n\) 张表的 \(2^n\) 个子集）在 \(n\) 较大时（10+ 维度表）变得不可行。特殊策略包括：

以事实表为中心：始终从事实表开始连接顺序
先对维度表做谓词下推：在连接事实表之前先过滤维度表，使用位图过滤器或半连接来减少事实表扫描
星型连接优化：识别星型模式并使用专门的多索引或位图交集策略

Lec15 要点回顾

优化器利用代数等价性将逻辑计划转换为物理计划——查询优化的正确性完全建立在这些等价性的可靠性之上
启发式规则（谓词下推、投影下推、笛卡尔积转连接）应用成本低且几乎总是有益——每个实际的优化器都首先应用它们
基于代价的优化枚举等价计划并选择最优——两种主要范式（自底向上的 System R 和自顶向下的 Cascades）代表根本不同的搜索策略但结果相似
连接顺序是影响最大的优化决策——合法顺序的数量超指数增长，使得大查询的穷举搜索不可能
Enforcer 弥合逻辑等价性和物理需求之间的差距——优化器在比较计划时必须考虑排序顺序等属性

Lec16 查询规划与优化 — 代价模型、统计信息和基数估计

第 15 讲建立了优化器如何搜索等价计划。本讲回答互补的问题：优化器如何估算一个计划的代价？答案需要关于数据的统计信息、将统计信息转化为估算 I/O 和 CPU 代价的代价模型，以及预测中间结果大小的基数估计。

为什么代价估算重要

优化器的计划选择取决于其代价估算的质量。完美的搜索算法配上糟糕的代价估算，只会自信地选择一个糟糕的计划。代价模型是优化器的”预言机”——其准确性直接决定查询性能。

代价估算有三个组成部分： 1. 统计信息：数据分布的摘要（直方图、sketch、样本） 2. 基数估计：预测每个算子产生多少元组 3. 代价模型：将基数和算子类型映射到估算的执行代价

统计信息

DBMS 维护关于表和列的内部统计信息以支持代价估算。这些信息存储在系统目录中，通常通过显式的 ANALYZE 命令（PostgreSQL）或后台自动更新。

基本统计量

对于每个关系 \(R\)： - \(N_R\)：\(R\) 中的元组数量 - \(V(A, R)\)：属性 \(A\) 在 \(R\) 中的不同值数量（有时称为 \(A\) 的基数） - \(B_R\)：包含 \(R\) 元组的磁盘块（页）数量

选择基数 \(SC(A, R)\) 是具有给定 \(A\) 值的平均元组数：

\[SC(A, R) = \frac{N_R}{V(A, R)}\]

如果 \(A\) 是键（所有值不同），\(SC(A, R) = 1\)。如果 \(A\) 只有一个不同值，\(SC(A, R) = N_R\)。

直方图

真实数据很少是均匀的。直方图捕获列中值的分布，使优化器能比均匀假设更准确地估算选择性。

等宽直方图：将值域划分为固定宽度的桶，统计每个桶中有多少元组。

范围	计数
[0, 10)	120
[10, 20)	340
[20, 30)	90
[30, 40)	450

构建简单但在值聚集时可能产生误导——跨越密集区域和稀疏区域的桶隐藏了真实分布。

等深（等高）直方图：调整桶边界使每个桶包含大约相同数量的元组。

这能更好地捕获倾斜分布——数据密集处出现窄桶，稀疏处出现宽桶。大多数生产系统使用等深直方图。

端偏直方图：存储最常见值（MCV）的精确频率，对剩余值使用单个直方图。PostgreSQL 使用这种方法——它为每个分析过的列同时维护 MCV 列表和直方图。

Sketch

对于非常大的数据集或流式场景，精确直方图可能代价高昂。概率 sketch 以最小空间提供有界误差的近似统计。

Count-Min Sketch：一个包含 \(d\) 个哈希函数的二维计数器数组。要记录一个值，用每个函数对其哈希并递增相应计数器。要查询频率，取所有哈希函数中的最小值（因此叫”count-min”）。使用最小值是因为哈希冲突只能使计数膨胀，不能缩小。

空间：\(O(d \times w)\)，其中 \(w\) 是宽度（每行计数器数量）
误差：基于 \(d\) 和 \(w\) 的概率保证
用途：估算单个值的频率（点查询）

HyperLogLog (HLL)：利用哈希值中最大前导零数量与基数对数的关系来估算不同值数量（基数）。使用极少空间（几 KB）即可估算数十亿级别的基数。

空间：\(O(m)\)，其中 \(m\) 是寄存器数量（通常 1024–16384）
误差：当 \(m = 16384\) 时约 \(\pm 2\%\)
用途：不扫描整列即可估算 \(V(A, R)\)

采样

预计算统计信息的替代方案：维护每张表的随机元组样本，对样本运行查询谓词以估算选择性。这对复杂谓词（包括相关谓词）自然适应，但运行时代价更高。

使用基于采样估算的系统包括 Oracle（动态采样）和一些将采样与学习模型结合的新系统。

代价模型

代价模型将统计信息和基数估计转化为每个计划的单一数值代价。两种主要风格：

物理代价模型

估算实际资源消耗：磁盘 I/O、CPU 周期、内存使用、网络传输。这是最准确的方法，但将优化器绑定到特定硬件。

考虑的因素包括： - 顺序 I/O vs 随机 I/O（顺序读取便宜 10–100 倍） - 每元组的比较、哈希、表达式求值 CPU 代价 - 哈希表、排序缓冲区的可用内存 - 分布式查询的网络代价

逻辑代价模型

为算子分配抽象的相对代价，不建模物理硬件。这使优化器可跨硬件配置移植，但对任何特定部署不够准确。

PostgreSQL 代价模型

PostgreSQL 使用带可配置魔法常数的物理代价模型，这些常数近似不同操作的相对代价：

参数	默认值	含义
`seq_page_cost`	1.0	顺序读取一页的代价
`random_page_cost`	4.0	随机读取一页的代价
`cpu_tuple_cost`	0.01	处理每个元组的 CPU 代价
`cpu_index_tuple_cost`	0.005	每个索引条目的 CPU 代价
`cpu_operator_cost`	0.0025	每次算子求值的 CPU 代价

计划的总代价是 I/O 代价和 CPU 代价之和：

\[\text{Total Cost} = (\text{pages\_read} \times \text{page\_cost}) + (\text{tuples\_processed} \times \text{cpu\_tuple\_cost})\]

这些常数编码了随机 I/O 比顺序 I/O 贵 4 倍的假设——对机械硬盘合理但对 SSD 过于保守，SSD 的比率接近 1.5–2 倍。管理员可以为其硬件调整这些常数。

基数估计

代价模型最关键的工作：预测每个算子产生多少元组。计划中每个后续的代价估算都依赖于这些预测。

选择性

谓词 \(P\) 的选择性 \(\text{sel}(P)\) 是满足 \(P\) 的元组比例：

\[\text{sel}(P) = \frac{|\sigma_P(R)|}{N_R}\]

选择的估算输出基数为：

\[|\sigma_P(R)| = N_R \times \text{sel}(P)\]

常见谓词的选择性

等值：\(A = \text{constant}\)

\[\text{sel}(A = c) = \frac{1}{V(A, R)}\]

假设均匀分布——每个不同值出现概率相等。

范围：\(A \geq c\)（给定值域 \([\text{min}, \text{max}]\)）

\[\text{sel}(A \geq c) = \frac{\text{max} - c}{\text{max} - \text{min}}\]

假设值在范围内均匀分布。

否定：\(\text{NOT } P\)

\[\text{sel}(\text{NOT } P) = 1 - \text{sel}(P)\]

合取：\(P_1 \text{ AND } P_2\)

\[\text{sel}(P_1 \wedge P_2) = \text{sel}(P_1) \times \text{sel}(P_2)\]

假设谓词之间独立——一个强假设，通常不成立（例如 city = 'Pittsburgh' 和 state = 'PA' 高度相关）。

析取：\(P_1 \text{ OR } P_2\)

\[\text{sel}(P_1 \vee P_2) = \text{sel}(P_1) + \text{sel}(P_2) - \text{sel}(P_1) \times \text{sel}(P_2)\]

三个基本假设

经典基数估计建立在三个简化假设之上：

均匀分布：列中所有值出现概率相等。在倾斜数据（如实际工作负载中常见的 Zipf 分布）下失效。
独立性：不同列上的谓词统计独立——知道列 \(A\) 的值不会告诉你关于列 \(B\) 的任何信息。在相关属性（城市/州、年龄/毕业年份）下失效。
包含（Containment）原则：对于连接 \(R \bowtie_{A} S\)，较小关系中值的域包含在较大关系的域中。即较小集合中出现的每个值也出现在较大集合中。

连接大小估计

对于等值连接 \(R \bowtie_{R.A = S.A} S\)，估算结果大小为：

\[|\text{est}| \approx \frac{N_R \times N_S}{\max(V(A, R), V(A, S))}\]

直觉：除以较大的不同值数量，因为包含假设意味着较小的值集合完全”包含”在较大的集合中。较小域中的每个值与 \(R\) 中的 \(SC(A, R)\) 个元组和 \(S\) 中的 \(SC(A, S)\) 个元组匹配。

对于笛卡尔积（无连接谓词），结果大小就是 \(N_R \times N_S\)。

多连接估计与误差传播

对于连接多张表的查询，优化器必须估算中间结果大小，每个估算都反馈到下一个。误差以乘法方式累积：

考虑三表连接 \(R \bowtie S \bowtie T\)： 1. 估算 \(|R \bowtie S|\) ——假设估算偏差 2 倍 2. 用该估算计算 \(|(R \bowtie S) \bowtie T|\) —— 2 倍误差传播

经过 \(k\) 次连接后，估算误差可以累积到 \(O(2^k)\) 甚至更大。这就是为什么基数估计常被称为查询优化的阿喀琉斯之踵——即使每步很小的误差也能导致优化器为复杂查询选择灾难性错误的计划。

方法	思路	局限性
多列统计	维护列组合的联合直方图或统计	可能的组合数量指数级
贝叶斯网络	将列间依赖建模为图模型	构建和维护复杂
反馈驱动	使用实际运行时基数校正未来估算	需要先执行查询
学习型基数估计器	在查询日志上训练 ML 模型预测基数	数据漂移、训练代价、可靠性

Lec16 要点回顾

统计信息（直方图、sketch、样本）是基于代价优化的基础——没有准确的数据摘要，优化器就是盲飞
代价模型将基数估计转化为计划代价——PostgreSQL 的魔法常数编码了硬件特定假设，管理员应针对性调整
在均匀/独立/包含假设下的基数估计对简单查询效果好，但在相关属性和多连接查询下失效
估算误差通过连接链以乘法方式传播——每次连接 2 倍误差，经过 10 次连接变成 1000 倍误差，导致灾难性错误的计划选择
相关属性问题仍然是查询优化中最困难的挑战之一——多列统计、学习型估计器和反馈循环是活跃的研究领域

总结

主题	核心思想
规划流水线	SQL → AST → 逻辑计划 → 物理计划；优化器桥接逻辑到物理
关系代数等价性	选择分解、连接交换律/结合律——定义合法搜索空间
启发式优化	静态规则（谓词下推、投影下推）——成本低且几乎总是有益
表达式重写	在搜索前简化/消除不可能或冗余的谓词
自底向上搜索（System R）	对关系子集的动态规划，\(O(2^n)\)，左深树，有趣顺序
自顶向下搜索（Cascades）	带 memo 表的 DFS，分支定界剪枝，支持灌木状树
Enforcer	插入的物理算子（如 Sort）以保证所需属性
统计信息	直方图（等宽、等深、端偏）、sketch（Count-Min、HLL）、采样
代价模型	将基数 + 算子类型 → 数值代价；物理（PostgreSQL）vs 逻辑
基数估计	\(\text{sel}(P) \times N_R\)；依赖均匀、独立、包含假设
连接大小估计	在包含假设下 \(N_R \times N_S / \max(V(A,R), V(A,S))\)
误差传播	估算误差通过连接链以乘法方式累积
相关属性	独立性假设失效；解决方案包括多列统计、学习模型

核心要点：查询优化是一个在等价计划上的搜索问题，由依赖基数估计的代价模型引导——而基数估计，尽管经过数十年的研究，仍然是链条中最薄弱的一环。把统计信息做对比拥有精密的搜索算法更重要。

参考文献

P. Selinger et al., “Access Path Selection in a Relational Database Management System,” SIGMOD, 1979.
G. Graefe, “The Cascades Framework for Query Optimization,” IEEE Data Engineering Bulletin, 1995.
G. Graefe and W. McKenna, “The Volcano Optimizer Generator: Extensibility and Efficient Search,” ICDE, 1993.
V. Leis et al., “How Good Are Query Optimizers, Really?,” PVLDB, 2015.
PostgreSQL Documentation, “Planner Cost Constants,” postgresql.org.

本文基于 CMU 15-445/645 数据库系统课程材料，授课教师 Andy Pavlo & Jignesh Patel（Lecture #15: Query Planning & Optimization I，Lecture #16: Query Planning & Optimization II）。