type
status
date
slug
summary
tags
category
icon
password
引言（Introduction）
在学习 SQL 时，我们通常会建立一个“查询执行的心理模型”：
- 首先获取
FROM子句中所有表的行；
- 然后根据
WHERE条件筛选记录；
- 接着进行选择性投影（只保留所需列）；
- 最后得到结果。
这种模型对理解 SQL 语义很有帮助，因为它确保你能得到正确的结果。但实际的数据库并不是按这个顺序执行的。
查询优化的关键：
数据库可以重新排序操作的执行顺序，以实现最佳性能。
本课程中，我们使用 I/O 次数 来衡量查询的性能。
查询优化（Query Optimization） 的目标就是：找到一个 Query Plan（查询计划），使得执行该查询所需的 I/O 最少。
查询计划（Query Plan）是什么？
查询计划是一个 操作序列（sequence of operations），它最终会给出和 SQL 相同的正确结果，但顺序可能不同。
我们使用 关系代数（Relational Algebra） 表达这些操作。
图示说明（Query Plan 示例）
含义：
- 先做连接：
Sailors ⨝ Reserves，连接条件是sid;
- 再做选择：
σ_bid=3（只保留bid = 3的记录）；
- 最后做投影：
π_name,time（只保留name和time字段）。
结论
目前这个查询计划是“连接 → 选择 → 投影”，但之后我们会看到：
我们可以构造更高效的查询计划（比如先做选择再连接，减少连接时处理的数据量）。
Iterator Interface（迭代器接口）
查询计划 = 表达式树（Expression Tree）
- 图中的表达式树代表了一个查询计划：
- 边（edge） 表示数据流；
- 节点（vertex） 表示关系代数操作符（如选择、投影、连接）；
- 叶子节点 表示底层的数据表。
查询优化器的目标：生成一个操作序列（查询计划），在保证正确结果的前提下尽量减少 I/O 或计算代价。
查询执行 = 一系列迭代器
数据库执行引擎会将每个操作符实现为一个 迭代器（Iterator）对象，所有操作符共同遵循一个标准的 Iterator 接口。
Iterator 的作用：
- 核心方法：
next()
- 每个操作符都通过调用
next()来向其子操作符请求下一条记录
- 这种模型叫做 pull-based（拉模式）执行模型
工作机制：
以图中的例子为例：
执行顺序如下：
- 顶层的
ProjectIterator（投影sname）调用next()；
- 它调用下层的
JoinIterator；
JoinIterator又调用下层连接、过滤器等的next()，一直递归到最底层的表扫描；
- 最终由
IndexedScanIterator访问表中的数据返回元组。
单线程模型
这种执行方式是单线程的（single-threaded），因为每次调用
next() 都是从根节点往下递归到底，再一级一级返回一条记录。Streaming vs Blocking Operators
- Streaming Operators（流式算子）
- 一边读一边产出结果
- 如：投影（
π）、选择（σ）、索引扫描等 - 每次调用
next()就有可能返回一个结果
- Blocking Operators（阻塞算子）
- 必须“全部读完再输出”
- 如：排序（Sort）、聚合（Group By）等
next()不会立刻返回结果，直到消费完整个输入
图示解读：
图中清晰地展示了执行流：
- 从
ProjectIterator(sname)开始；
- 经过两个层次的连接操作（Index NL Join）；
- 每个连接下接的是投影、索引扫描等；
- 所有节点都实现了
next()方法，实现流式推导。
Selectivity Estimation（选择率估计）
背景：
在查询优化中，我们无法事先确切知道一个查询计划会产生多少 I/O，除非真的去执行它。
这带来了两个重要意义：
- ❌ 我们不能保证找到最优查询计划；
- ✅ 我们需要一种方法来估算一个计划的代价，其中一种工具就是 选择率估计。
什么是 Selectivity？
- 选择率（Selectivity） 表示一个操作符过滤后留下的记录比例；
- 用来估计多少页面（page）或记录可以“通过”该操作，传递给上层操作符；
- 选择率越低，说明过滤作用越强，能减轻后续操作负担。
例如：
- 如果 WHERE 子句能过滤掉 90% 的数据，那我们就希望尽早执行它；
- 如果选择率是 0.01，说明只有 1% 的记录被保留。
常见选择率估算公式：
这些公式适用于整数型字段，浮点型等会有不同估算方式。
条件类型 | 估算公式 | 说明 |
X = a | 1 / (# X 的唯一值数量) | 单值匹配 |
X = Y | 1 / max(# X 唯一值, # Y 唯一值) | 两列相等 |
X > a | (max(X) - a) / (max(X) - min(X) + 1) | 区间选择 |
cond1 AND cond2 | Selectivity(cond1) × Selectivity(cond2) | 联合过滤条件，假设独立性 |
举个例子：
假设列
age 的唯一值有 100 个：age = 25→ Selectivity =1 / 100 = 0.01；
age > 25，假设min(age)=1,max(age)=100→
= (100 - 25) / (100 - 1 + 1) = 75 / 100 = 0.75。总结
选择率估计是 成本估算器（cost estimator） 的核心部分，影响查询计划中的：
- 操作顺序（选择下推）；
- 连接顺序选择（Join Order）；
- 算法选择（例如选择 Nested Loop vs Hash Join）等。
Selectivity of Joins（连接的选择率）
当我们对两个表
A 和 B 执行连接（例如 A.id = B.id）时，输出结果的大小（元组数）取决于：- 表的大小；
- 连接字段的选择率。
笛卡尔积的基础数量：
如果没有连接条件，结果将是
|A| × |B|，即全表与全表的笛卡尔积。有连接条件时（如 A.id = B.id）：
我们需要用以下公式估计连接后的输出元组数（连接选择率）：
这个分母就是我们之前讲过的选择率公式
1 / max(|A.id|, |B.id|)。三步计算连接输出页数（估算）：
- 计算连接的选择率
使用
1 / max(唯一值数 in A, 唯一值数 in B) 公式- 估计连接输出元组数
用选择率 ×
|A| × |B| 的笛卡尔积元组数- 估计输出页数
用输出元组数除以每页记录数，得到页数估计值
重要提示：不能直接用选择率 × 页数 来估计输出页数！
举个例子：
R = S = 1 页，每页有 5 条记录；
- 假设选择率是 1 ⇒ 全部 25 个笛卡尔积元组被选中；
- 输出页数 = 25 / 5 = 5 页；
- 而如果直接算
[R] × [S] = 1 × 1 = 1 页，那就严重低估了。
总结：
步骤 | 操作 | 说明 |
① | 选择率估计 | 1 / max(唯一值数 in A, B) |
② | 输出元组数估计 | ` |
③ | 输出页数估计 | 输出元组数 / 每页记录数 |
常见优化启发式（Common Heuristics）
在分析复杂查询时，可能的查询计划组合太多，不可能全部考虑。
为了缩小搜索空间，我们采用以下几条启发式规则：
启发式规则列表：
- 将投影（π）和选择（σ）尽量下推（尽可能早地执行）
- 只考虑左深查询计划（left-deep plans）
- 尽量避免使用笛卡尔积（cross join），除非别无选择
各规则解释
① 投影和选择下推（Push-down）
- 选择下推（σ）：提早过滤无关记录，减少数据量，加快后续处理；
- 投影下推（π）：提前移除不需要的列，减少数据页大小；
- 行更小 ⇒ 每页可放更多行 ⇒ 更少的 I/O；
- ⚠️ 注意：不能投影掉查询后续仍需使用的列！
② 左深查询计划（Left-Deep Plans）
定义：左深计划中，连接的右边总是原始表（base table），而不是其他连接的结果。
图中说明：
- ✅ 左图：合法的左深计划；
- ❌ 中图 & 右图：不是左深计划（右边是连接结果）。
好处：
- 大幅减少计划空间复杂度
- 原始计划空间是关系数的阶乘级别；
- 限制为左深结构后，组合数量大大减少。
- 支持流水线执行（Pipelining）
- 数据可以一条一条传递，不用中间结果落盘。
③ 避免笛卡尔积（Cross Join）
- Cross Join 是最糟糕的连接方式；
- 没有 join 条件，输出是完全的笛卡尔积；
- 导致大量页面输出，I/O 成本极高；
- 除非别无选择，尽量避免！
总结表
启发式 | 目的 | 好处 |
投影/选择下推 | 尽早减少数据量 | 更少页、更快过滤、更少后续负担 |
只用左深计划 | 缩小搜索空间 | 数量级减少、支持 pipelining |
避免 Cross Join | 降低连接成本 | 避免指数级输出与高 I/O |
System R 优化器 - 第一步（Pass 1）
System R 是一个经典的查询优化器模型，在其第一阶段中要解决的问题是：
如何选择每个表的访问方式（Access Method）？
可用的两种访问方式：
- 全表扫描（Full Scan）
- 索引扫描（Index Scan）（针对表上已有索引）
注意：
此阶段只处理与单个表相关的过滤条件（即
WHERE 子句中只涉及该表的谓词）。连接条件不会用于 Pass 1 的估算，因为连接涉及多个表。成本模型
① Full Scan
- 成本为：
[P]，即该表的页数；
- 无论有没有过滤条件，都要扫描整个表。
② Index Scan（以 Alt. 1 为例）
- Alt. 1 是聚簇索引（clustered），可按范围扫描；
- 成本估算公式：
- 示例：
- 表
A有A页； C1是高度为 2 的索引；- 条件
C1 > 5 ∧ C2 < 6，假设选择率为0.5 × 0.5 = 0.25； - 如果只有
C1有索引，最多可过滤出 0.5 × A 页。
所以：
③ Alt. 2 / 3（非聚簇或多列索引）
公式变为：
最后一步：选择性传递到下一步的访问方式
System R 在 Pass 1 只保留：
- I/O 成本最小的访问方式（optimal）
- 具有 interesting order 的访问方式
什么是 Interesting Order？
排序顺序如果在后续查询中会用到，则视为“有趣顺序”。
例如：
- 用在
ORDER BY
- 用在
GROUP BY
- 用在后续的连接条件中
示例（SQL + 5 个访问方式）
访问方式列表：
编号 | 访问方式 | 成本 | 是否保留 | 原因说明 |
1 | Full Scan players | 100 | ❌ | 不如 index players.age 好 |
2 | Index Scan players.age | 90 | ✅ | 成本最小 |
3 | Index Scan players.teamid | 120 | ✅ | 虽不是最优但 teamid 是 join 键，属于 interesting order |
4 | Full Scan teams | 300 | ✅ | 成本最小（相比 400） |
5 | Index Scan teams.record | 400 | ❌ | 成本太高 |
总结 Pass 1 流程：
步骤 | 操作 |
① | 枚举所有可访问方式（全表 + 所有索引） |
② | 计算 I/O 成本（使用选择率、索引结构） |
③ | 选择两个保留方式：最优 & 有趣顺序的方式 |
System R 优化器的 Passes 2 到 n
目标：
System R 的第 2 轮及之后的步骤关注的是如何连接多个表。每一轮（Pass i）尝试将 i 个表连接在一起，使用上一步 Pass i-1 的结果。
限制条件：
- 仅考虑 左深查询计划（Left-Deep Plans）
- 尽量避免 Cross Join
- 每轮为每一组表：
- 选择最优 join 计划（最小 I/O）
- 选择产生 interesting order 的 join 计划（若存在）
Pass 2 举例
我们要执行以下 SQL 查询：
假设数据库仅支持 SMJ 和 BNLJ（Sort-Merge Join / Block Nested Loop Join）
可能的 Join 方式（Pass 2）：
编号 | Join 方式 | 估算成本 | 是否保留 | 原因 |
1 | A BNLJ B | 1000 | ✅ | 成本最小，适用于 {A, B} |
2 | B BNLJ A | 1500 | ❌ | 成本高 |
3 | A SMJ B | 2000 | ❌ | 排序输出没用（A.aid B.bid 不再使用） |
4 | B BNLJ C | 800 | ❌ | 非左深结构（右表是非 base 表） |
5 | B BNLJ B | 600 | ✅ | 最优 {B, C}，输出顺序为 C.cid 是 interesting |
6 | C SMJ B | 1000 | ✅ | 输出为 C.cid，有用的 interesting order |
最终保留：Join 1, 5, 6
Pass 3 举例
把 {A, B} 连接到 C，或 {B, C} 连接到 A（左深计划）
编号 | Join 方式 | 成本 | 是否保留 | 原因 |
1 | {A, B} BNLJ C | 10,000 | ❌ | 输出顺序不是 C.cid，不感兴趣 |
2 | {B, C} SMJ A | 12,000 | ✅ | 输出仍然按 C.cid 排序，有用 |
3 | {B, C} BNLJ A | 10,000 | ✅ | 最优整体计划（所有 3 表）但无有用顺序 |
4-6 | 其他计划 | ≥18,000 | ❌ | 成本太高且顺序无用 |
总结：System R Join Plan 策略
步骤 | 内容 |
Pass 1 | 对每个表选出最优/interesting 的访问方式（Scan） |
Pass 2~n | 连接更多表，只构造左深计划，保留最优计划和 interesting order |
只保留 | 成本最小 和 排序对下游查询有意义的计划（如用于 ORDER BY, GROUP BY, join key） |
计算联接操作的 I/O 成本
在估算查询的 I/O 成本时，我们需要考虑以下几点：
- 中间结果的物化（Materialization）：是否将中间结果写入磁盘并再次读取，或者使用流式传递（streaming）。
- 有趣排序（Interesting Order）：如果输出能保留下游算子需要的排序，就能节省额外的排序开销。
- 连接算法的不同性质：不同的连接算法对输出顺序有不同影响，如 SMJ 能保持排序，GHJ 不能。
考虑 #1：物化 vs 流式
在估算 I/O 成本时，我们往往不能直接套用公式，因为是否物化中间结果会极大影响成本。
- 物化（Materialize）：上一个算子输出的所有页都写入磁盘，然后下一个算子重新读入。
- 流式（Streaming）：基于 Volcano 模型的拉取（pull-based）执行，即上游算子直接提供下游算子需要的单个元组，而不需要物化。
示例：物化 vs 流式
假设我们有如下查询：
假设：
- [P] = 50， [T] = 100
- 满足
P.teamid < 200的页数为 30
- 满足
T.tname = 'Team5'的页数为 40
计划 1：不下推选择条件
I/O 成本：
- 扫描 P：50 页
- 扫描 T：100 页
- BNLJ：
- 总成本：5100 I/Os
计划 2：仅下推左侧选择
- I/O 成本：
- 说明：
- 下推左侧后，减少了 P 的输入页数，但 T 仍然全表扫描。
计划 3：同时下推左右选择
- I/O 成本：
- 说明：
- 进一步减少右侧输入页数，提升性能。
流式 vs 物化的比较
在 System R 中，若算子使用流式连接而不是物化，则可避免额外写回读入 I/O。
如果中间结果必须物化，那么成本还需再加上：
- 写中间结果页数 + 重新读取页数
考虑 #2：有趣排序（Interesting Order）
一些连接算法（如 SMJ）可以输出有序数据，保留有趣排序。
而其他如 BNLJ、PNLJ、GHJ 则无法保证输出有序。
示例：下推后排序优化
假设最终查询要求
ORDER BY teamid，那么：- 使用 SMJ 会比 BNLJ 更具优势，因为 SMJ 的输出自带排序。
- 结合下推后的流式优化，可以进一步减少成本。
练习题：
- 如果仅全表扫描并进行 BNLJ，成本是多少？
- 如果将
σ_teamid<200下推，成本如何？
- 如果进一步将
σ_tname='Team5'也下推，成本如何？
- 哪些连接算法能保持左侧顺序？哪种能输出全局排序？
- 在以上示例中，选择流式是否能减少 I/O？
考虑 #2：有趣排序（Interesting Order）
在进行查询优化时，我们还需要考虑上游操作符产生的有趣排序。
例如，我们正在优化以下查询：
- players 表包含 50 页，teams 表包含 100 页。
选择下推和索引扫描
假设我们将选择条件
P.teamid > 200 下推：- 对 P 表使用索引扫描，成本为 60 I/Os。
- 对 T 表使用全表扫描，成本为 100 I/Os。
由于索引扫描按
teamid 排序输出，因此它是一个有趣排序，可以在 P 和 T 的连接操作中被利用。
连接算法选择：SMJ
假设我们选择 SMJ (Sort-Merge Join) 作为 P 和 T 的连接算法：
- 根据之前的公式，I/O 成本为：
- 最后一项是合并阶段的成本，包含读入两个表的开销。
利用索引优化
由于我们在 P 上使用索引扫描，因此不需要再对 P 进行外排序。
- 我们直接将索引扫描的输出流入合并阶段。
- 因此，新的 I/O 成本为：
- 相比未优化的方案，大大减少了排序 P 的成本。
总结
- 通过将选择条件下推到 P 表，并使用索引扫描替代外排序，显著减少了成本。
- SMJ 充分利用了索引带来的排序特性，使得连接更加高效。
- 最终 I/O 成本：160 I/Os。
练习题：
给定如下表：
表名 | 页数 | 列信息 | 索引 |
Teams | 100 | ㅤ | ㅤ |
Players | 500 | rating 值域 [1,10] | 聚簇索引：按 rating（高度 1，100 叶页）聚簇索引：按 playerid（高度 1，50 叶页） |
Coaches | 200 | ㅤ | ㅤ |
针对下列查询，回答问题 1-7：
1. p.rating > 5 的选择率是多少？
2. 在 Pass 1（单表访问）中，哪些访问计划会保留并进入下一阶段？
- 全表扫描 Teams
- 全表扫描 Players
- 索引扫描 Players.rating
- 索引扫描 Players.playerid
- 全表扫描 Coaches
3. 哪两个二表连接计划会进入 Pass 3？
假设给出的 I/O 成本均为该连接顺序下的最优成本，且所有输出均不排序。
- Teams ⨝ Players (1000 I/Os)
- Players ⨝ Teams (1500 I/Os)
- Players ⨝ Coaches (2000 I/Os)
- Coaches ⨝ Players (800 I/Os)
- Teams ⨝ Coaches (500 I/Os)
- Coaches ⨝ Teams (750 I/Os)
4. 哪些三表连接计划会被 Pass 3 考虑？
假设给出的 I/O 成本均为该连接顺序下的最优成本，且所有输出均不排序。
- (Teams ⨝ Players) ⨝ Coaches - 10,000 I/Os
- Coaches ⨝ (Teams ⨝ Players) - 8,000 I/Os
- (Players ⨝ Teams) ⨝ Coaches - 9,000 I/Os
- (Players ⨝ Coaches) ⨝ Teams - 12,000 I/Os
- (Teams ⨝ Coaches) ⨝ Players - 15,000 I/Os
5. 哪个三表连接计划最终会被使用？
6. 假设我们使用 System R 查询优化器优化如下查询：
- 假设 B = 5， [P] = 50 页， [T] = 100 页
- 有 30 页 players 符合 P.teamid > 200
- 有 40 页 teams 符合 T.tname > 'Team5'
- Pass 1 中选出的访问计划：
- 索引扫描 P.teamid：60 I/Os
- 全表扫描 T：100 I/Os
计算 Pass 2 中 P SMJ T 的平均 I/O 成本（假设使用未优化 SMJ）。
7. 假设我们运行自定义优化器针对如下查询：
- 假设 B = 5， [S] = 20 页， [T] = 30 页
- 有 12 页学生记录符合 S.absences > 10
- 有 15 页教师记录符合 T.days_worked < 50
- System R 选择 BNLJ，成本为 130 I/Os
设计一个更优的查询计划，并计算相比 System R 优化器节省的 I/O 数量。
解答（Solutions）
1. 选择率计算：
p.rating > 5 的选择率是多少？
- 答案：1/2
- rating 值域为 [1, 10]，大于 5 的值有 5 个（6, 7, 8, 9, 10），总共有 10 个值，选择率为：
Selectivity=510=12\text{Selectivity} = \frac{5}{10} = \frac{1}{2}
2. Pass 1 中可推进的单表访问计划：
答案：a, c, d, e
- 每个表至少需要一个访问计划才能推进，Teams 和 Coaches 只有全表扫描。
- Players 表有两种索引：
- 索引扫描 Players.rating：带有选择性优化
- 索引扫描 Players.playerid：有有趣排序，因为 ORDER BY playerid
- 这两种索引都能保留，因此可行的计划为：
- 全表扫描 Teams
- 全表扫描 Players
- 索引扫描 Players.rating
- 索引扫描 Players.playerid
- 全表扫描 Coaches
成本计算：
- 全表扫描 Players： 500 I/Os
- Players.rating 索引扫描： 1 (root) + 100 (叶) + 500 (数据页) = 601
- Players.playerid 索引扫描： 1 + 50 + 500 = 551
- 结论： Playerid 索引扫描因有排序特性，也会被保留。
3. Pass 2 中推进的两表连接计划：
答案：a, e
- Players ⨝ Coaches 不被考虑，因为没有连接条件（等同于 cross join）。
- Teams ⨝ Players (1000 I/Os)
- Teams ⨝ Coaches (500 I/Os)
- 结论：
- Teams ⨝ Players：成本较低
- Teams ⨝ Coaches：成本较低
4. Pass 3 中保留的三表连接计划：
答案：1, 2, 3
- 这些三表计划均符合从 Pass 2 中推进的两表集（Teams, Players）和（Teams, Coaches）。
- 成本计算：
- (Teams ⨝ Players) ⨝ Coaches - 10,000 I/Os
- Coaches ⨝ (Teams ⨝ Players) - 8,000 I/Os
- (Players ⨝ Teams) ⨝ Coaches - 9,000 I/Os
- 结论：
- (Teams ⨝ Players) ⨝ Coaches 最优（成本最小）。
5. 最终三表连接计划：
答案：1
- (Teams ⨝ Players) ⨝ Coaches
- 成本最低，且满足连接顺序要求。
6. SMJ 连接成本估算：
假设我们在 Pass 2 中使用 SMJ 来连接 P 和 T：
I/O 成本计算：
- 排序 T 表：
- 读取： 100 I/Os
- 写出： 40 I/Os（T.tname > 'Team5' 的数据）
- 合并：
- Pass 1： B-1 = 4 个 run，合并为 2 个 run，成本 40 + 40
- Pass 2： 合并 2 个 run 为最终结果，成本 40 + 40
- 读取 P 表：
- 索引扫描： 60 I/Os
- 合并阶段：
- 最终合并： 40 I/Os
总成本：
(100+40)+(40+40)+60+40=400 I/Os(100 + 40) + (40 + 40) + 60 + 40 = 400 \text{ I/Os}
优化：
如果直接在第一轮合并后使用 SMJ，可以减少一次合并：
(100+40)+(40+40)+60+40=320 I/Os(100 + 40) + (40 + 40) + 60 + 40 = 320 \text{ I/Os}
7. 自定义优化方案：
查询：
- 假设：
- B = 5
- [S] = 20 页， [T] = 30 页
- 符合 S.absences > 10 的记录：12 页
- 符合 T.days_worked < 50 的记录：15 页
System R 原计划：
- 使用 BNLJ，估计成本：130 I/Os
优化策略：
- 下推选择条件：
- 将
S.absences > 10和T.days_worked < 50下推到 Scan 层。
- 连接算法选择：
- 使用 Block Nested Loop Join (BNLJ)，将 Teachers 作为外表，Students 作为内表。
- I/O 成本计算：
- 读取 T： 30 I/Os
- 读取 S： 20 I/Os
- 物化 S： 12 I/Os
- 连接：
- 总成本：
节省：
- 比 System R 优化器减少 8 I/Os。
- 物化学生选择结果减少重复读取成本。