查询处理的基本步骤#

数据库接收到 SQL 后，大体经历三个阶段。

1. Parsing and Translation

• 语法检查
• 检查查询中引用的 relation / attribute 是否存在
• 把 SQL 翻译成内部表示，再转成关系代数表达式

2. Optimization

• 生成与原表达式等价的其他表达式
• 为每种表达式考虑不同物理执行方法
• 估计每种执行计划的代价
• 选择估计代价最低的计划

3. Evaluation

• query-execution engine 接收最终计划
• 实际执行该计划
• 返回查询结果

SQL 只描述“我要什么结果”；执行计划决定“系统如何拿到这些结果”。

表达式与执行计划#

考虑查询：

1
select name, title
2
from instructor natural join (teaches natural join course)
3
where dept_name = 'Music';

直接转换得到的关系代数表达式可以写成：

这个表达式的语义没有问题，但未必高效。

可以先把只涉及 instructor 的选择条件下推：

还可以只保留后续 join 和最终输出需要的属性：

这些仍然只是逻辑表达式。
一个完整的 evaluation plan（执行计划） 还需要明确：

• dept_name='Music' 是否使用索引
• 两次 join 分别选择 hash join、merge join 还是 nested-loop join
• 是否需要排序
• projection 去重采用什么算法
• 操作之间使用 materialization 还是 pipelining

例如一个计划可能是：

• 用 dept_name 上的索引筛选 instructor
• 将筛选后的结果按 ID 排序
• 对 teaches 和 course 做 hash join
• 对两个输入做 merge join
• 最终排序去重并输出 name, title

关系代数树只说明操作结构；执行计划还为节点标注了实际算法与执行协调方式。

基于代价的查询优化#

同一查询的不同计划，代价差异可能达到：

• 几秒
• 几分钟
• 甚至几天

Cost-based query optimization 通常分为三步：

1. 使用等价规则生成逻辑等价表达式。
2. 给每个表达式配置不同算法，得到候选 evaluation plans。
3. 根据估计代价选择最便宜的计划。

代价估计依赖三类信息：

• 基本关系统计信息
  • tuple 数量
  • block 数量
  • 属性 distinct value 数量
• 中间结果规模估计
  • selection 后剩多少 tuple
  • join 后产生多少 tuple
• 物理算法代价公式
  • index scan / sequential scan
  • nested-loop / merge join / hash join
  • sort 的 I/O 代价

这一章最重要的闭环是：

1
statistics
2
   ↓
3
cardinality estimation
4
   ↓
5
operator cost estimation
6
   ↓
7
plan comparison
8
   ↓
9
chosen plan

查看执行计划#

多数数据库都允许查看 optimizer 选择的计划。

1
-- PostgreSQL
2
EXPLAIN <query>;
3

4
-- PostgreSQL：同时实际执行，显示真实运行统计
5
EXPLAIN ANALYZE <query>;

其他系统的典型形式：

1
-- Oracle
2
EXPLAIN PLAN FOR <query>;
3
SELECT * FROM TABLE(DBMS_XPLAN.DISPLAY);
4

5
-- SQL Server
6
SET SHOWPLAN_TEXT ON;

在 PostgreSQL 中，常见的成本显示形式是：

1
cost = f .. l

其中：

• f：产生第一条结果 tuple 的估计代价
• l：产生全部结果 tuple 的估计总代价

TIP

EXPLAIN 和 EXPLAIN ANALYZE 的区别：

• EXPLAIN：只展示估计计划，不真正执行查询
• EXPLAIN ANALYZE：执行查询，再把实际 tuple 数、实际耗时等信息与估计值一起展示

因此，分析 cardinality estimation 是否失准时，EXPLAIN ANALYZE 更有价值。

等价表达式#

两个关系代数表达式 $E_1$ 和 $E_2$ 等价，指的是：

对每一个合法数据库实例，它们都产生相同的结果。

传统关系代数把 relation 当作集合。
SQL 的输入输出一般采用 multiset / bag semantics（多重集语义），所以优化器必须保证：

• 结果中的 tuple 值相同
• 每个 tuple 出现的次数也相同

一个 equivalence rule（等价规则） 给出两种可互换的表达式形式。
优化器可以用它把当前表达式改写为其他候选表达式。

Selection 与 Projection 规则#

设 $E$、$E_1$、$E_2$ 为关系代数表达式，$\theta$ 为选择条件，$L$ 为属性集合。

Join 规则#

Set Operation、Aggregation 与 Outer Join 规则#

Outer Join 的限制#

内连接上的很多等价规则，不能机械地套到 outer join 上。

例如：

除非能证明 selection 对 teaches 的空值扩展 tuple 是 null-rejecting，且语义确实允许消去外连接。

Outer join 通常也不满足结合律：

WARNING

优化时遇到 outer join，应先确认：

• 哪一侧需要保留未匹配 tuple
• selection 是否引用 null-supplying side
• selection 是否是 null-rejecting
• join reorder 是否会改变补 null 的位置

直接把内连接的下推、重排规则照搬到 outer join，会改变查询语义。

Multiple Transformations Example#

查询目标：

找出 Music 系教师在 2017 年教授过的课程名称，并输出教师名与课程标题。

原始表达式：

优化过程可以分成三步。

Projection pushdown#

在 join 过程中，只保留必要属性：

• instructor 侧保留 ID, name
• teaches 侧保留 ID, course_id
• course 侧保留 course_id, title

于是最终树中，大量不参与后续计算的属性不会进入中间结果。

优化后的结构可以概括为：

$$\Pi_{\text{name},\text{title}} \left( \left( \Pi_{\text{name},\text{course\_id}} \left( \sigma_{\text{dept\_name}=\text{"Music"}}(instructor) \bowtie \sigma_{\text{year}=2017}(teaches) \right) \right) \bowtie \Pi_{\text{course\_id},\text{title}}(course) \right)$$

等价表达式的生成#

最直接的方法是：

1. 从原表达式开始。
2. 对当前已找到的每个表达式及其所有子表达式，尝试应用每条等价规则。
3. 把新表达式加入候选集合。
4. 重复直到不能产生新表达式。

伪代码思想：

1
EQ = {initial expression}
2

3
repeat
4
    对 EQ 中每个表达式的每个子表达式应用全部可用规则
5
    将新得到的等价表达式加入 EQ
6
until 不再出现新表达式

问题是：

• 候选表达式数量可能极大
• 同一子表达式会被反复生成
• 时间和空间消耗都难以接受

优化方式：

• 共享公共子表达式：表达式用 DAG 而非大量重复的树表示。
• 检测重复表达式：同样的子表达式只保存一份。
• Dynamic Programming / Memoization：一个子问题的最优计划只计算一次。
• Cost-based pruning：明显不可能胜出的计划尽早剪枝。
• Heuristics：只搜索更有希望的结构，例如 left-deep join tree。

为什么需要统计信息#

执行一个 operator 的成本，依赖它输入关系的大小。

但在复杂查询中：

• operator 的输入通常不是基本表
• 输入是上一个操作产生的中间结果

因此 optimizer 必须估计：

• 中间关系有多少 tuple
• 每个 tuple 多大
• 需要多少 block
• 属性值分布如何
• 是否会产生大量重复值

这类估计称为：

Cardinality Estimation（基数估计）：估计每个关系代数子表达式会产生多少 tuple。

Cardinality estimation 一旦严重失准，可能导致：

• 错误的 join order
• 错误的 join algorithm
• 错误的 index / scan 选择
• 实际执行代价远高于估计代价

Catalog 中的基本统计量#

对于 relation $r$，系统 catalog 常保存：

如果 tuple 紧密存放在文件中：

其中：

• $n_r$ 决定逻辑规模
• $b_r$ 更直接决定磁盘 I/O
• $V(A,r)$ 是估计 selection 和 join 结果规模的关键统计量

Histogram#

只有 min、max 和 distinct value 数，往往不足以描述数据分布。

例如：

• 年龄可能集中在 18–22
• 工资可能高度偏斜
• 某些 department 的 tuple 数可能远大于其他 department

数据库系统通常使用 histogram（直方图） 保存值分布信息。

常见形式：

• Equi-width histogram：每个桶覆盖相同的值域区间
• Equi-depth histogram：每个桶尽量包含相近数量的 tuple

用途：

• 更准确估计范围选择
• 更准确估计偏斜属性上的 join
• 降低 uniform distribution 假设带来的误差

Selection 结果大小估计#

复杂选择条件的 Selectivity#

选择条件 $\theta_i$ 的 selectivity（中选率） 定义为：

也就是：

• 一个随机 tuple 满足该条件的概率估计

Join 结果大小估计#

设：

• $r(R)$ 与 $s(S)$ 为两个关系
• natural join 的共同属性为 $R \cap S$

共同属性是某一侧的 Key#

如果 $R \cap S$ 是 $R$ 的 key，则：

• $s$ 中每个 tuple 至多匹配 $r$ 中一个 tuple

因此：

$$n_{r \bowtie s} \le n_s$$

如果共同属性还是 $s$ 中引用 $r$ 的 foreign key，并且外键值均有效，则：

$$n_{r \bowtie s} = n_s$$

即：

外键侧每一行都恰好 join 到被引用表中的一行。

表格示例#

设：

关系	tuple 数	$V(A,\cdot)$
$r$	$4$	$3$
$s$	$6$	$4$

则两个方向的估计为：

$$\frac{4 \times 6}{V(A,s)} = \frac{24}{4} = 6$$$$\frac{4 \times 6}{V(A,r)} = \frac{24}{3} = 8$$

取较小值：

$$n_{r \bowtie s} \approx 6$$

实际 join 结果包含 7 个 tuple。
这个例子说明：

• 公式只是在分布假设下的估计
• 不保证等于真实结果
• 其价值在于为计划选择提供数量级判断

其他操作的结果大小估计#

中间结果的 Distinct Value 估计#

很多更上层的 cardinality estimate 又依赖 $V(A,E)$。
因此不仅要估计 tuple 数，还要估计中间结果上的 distinct value 数。

操作之间会相互影响#

不能对每个 operator 各自选择局部最便宜的算法，然后期待整体计划最优。

例如：

• 对 $r_1 \bowtie r_2$，hash join 的当前代价可能低于 merge join
• 但 merge join 会输出按 join attribute 排序的结果
• 这个有序结果可以直接用于接下来的 merge join、order by 或 group by
• 总体计划反而可能更便宜

因此 plan selection 必须考虑：

• 中间结果 cardinality
• 中间结果 physical property，例如排序顺序
• 后续 operator 对这些性质的利用

Join Order 的搜索空间#

对于：

不同 join 顺序的数量非常大。

示例：

直观例子（$n=5$）：

子集 $\{r_1,r_2,r_3\}$ 的 join order 有 12 种。若先求出该子集的最优顺序，再与 $r_4$、$r_5$ 逐步合并，原本需要比较的 $12 \times 12$ 种组合可以理解为拆成 $12 + 12$ 的两步选择。

因此不必生成全部 join order：动态规划把每个子集的最优顺序只计算一次并复用。

这说明：

• 枚举全部 join trees 在关系数稍大时就不可行
• 必须用动态规划、限制树形或启发式方法压缩搜索空间

Dynamic Programming 选择 Join Plan#

动态规划的关键观察是：

如果已经知道某个 relation 子集的最优计划，就应复用它，而不应在更大 join 中重复求解。

令 bestplan[S] 表示：

• 计算 relation 集合 $S$ 的最佳计划
• 以及该计划的估计代价

1
procedure FindBestPlan(S):
2
    if bestplan[S] has been computed:
3
        return bestplan[S]
4

5
    if S contains only one relation:
6
        bestplan[S] = cheapest access plan for S
7
                       using selections and available indices
8
        return bestplan[S]
9

10
    for each non-empty proper subset S1 of S:
11
        P1 = FindBestPlan(S1)
12
        P2 = FindBestPlan(S - S1)
13

14
        for each applicable join algorithm A:
15
            P = join P1 and P2 using A
16
            cost(P) = cost(P1) + cost(P2) + joinCost(A)
17

18
            if cost(P) < bestplan[S].cost:
19
                bestplan[S] = P
20

21
    return bestplan[S]

Left-Deep Join Tree#

Left-deep join tree 的限制是：

每次 join 的右输入必须是一个基本关系，而不能是一个由 join 得到的中间结果。

例如 left-deep：

1
(((r1 ⋈ r2) ⋈ r3) ⋈ r4) ⋈ r5

而下面是 bushy / non-left-deep 结构：

1
(r1 ⋈ r2) ⋈ (r3 ⋈ (r4 ⋈ r5))

Left-deep 的优势：

• 搜索空间更小
• 适合 pipelined evaluation
• 每一层只需要把左侧中间流继续向上管道传递
• 右侧通常是可以直接扫描或使用索引访问的基本关系

复杂度：

• 当 $n=10$ 时，全 join order 规模约为 176 亿
• bushy-tree 动态规划只需数量级约 59000 的子组合计算

Interesting Sort Order#

考虑：

三个关系通过共同属性 $A$ join。

对于第一个 join：

• hash join 也许成本最低
• merge join 也许成本更高，但会输出按 $A$ 排序的结果

若接下来仍要按 $A$ 做 merge join，则：

• 前一个 merge join 的排序结果可被复用
• 总成本可能低于“前一步局部最便宜”的选择

这种以后可能有价值的排序属性称为：

Interesting sort order：对后续 join、order by 或 group by 可能有用的中间结果排序顺序。

因此动态规划不能只保存：

• 每个 relation subset 的唯一最便宜计划

还要保存：

• 每个 subset 在不同 interesting sort order 下的最佳计划

通常 interesting order 的种类不多，所以不会显著改变复杂度数量级。

基于等价规则的 Cost-Based Optimization#

仅处理 join order 还不够。更通用的 optimizer 需要同时处理：

• selection
• projection
• join
• aggregation
• outer join
• nested query rewrite
• physical operator selection

Physical equivalence rules 可以把逻辑节点转换成具体物理算法，例如：

• logical join → hash join
• logical join → merge join
• logical selection → table scan
• logical selection → index scan

高效实现通常需要：

• 用共享结构表示表达式，避免复制相同子树
• 快速检测重复 derivation
• 用 memoization 存储某个子表达式的最优物理计划
• 用 cost-based pruning 避免枚举所有计划

Heuristic Optimization#

Cost-based optimization 很有价值，但优化本身也消耗时间。

常见 heuristic rules：

• 尽早执行 selection
• 尽早执行 projection
• 优先执行结果规模最小的 selection / join
• 避免不必要的 Cartesian product
• 优先考虑 left-deep join order

这些规则通常有效，因为它们倾向于压缩中间结果。

WARNING

“Selection 越早越好”是一条 heuristic，不是绝对规律。

例如：

• $r$ 非常小
• $s$ 非常大
• $s$ 的 join attribute 上有索引
• selection predicate 涉及 $s$ 的另一个没有索引的属性

此时先扫描整个 $s$ 做 selection 可能很贵。
更好的计划可能是：

• 以小关系 $r$ 为外表
• 利用 $s$ 的 join 索引做 indexed nested-loop join
• join 后再过滤 selection 条件

所以最终仍应由 cost estimation 决定。

现实系统常采用混合策略：

• 对 nested block structure 与 aggregation 先用 heuristic rewrite
• 对各查询块内部的 join order 做 cost-based search
• 为优化器设定 optimization cost budget
• 超过预算时返回当前找到的最好计划
• 缓存已经求得的计划，供重复查询复用

对于很便宜的查询：

• 优化开销可能高于执行收益
• 系统可能只进行简单 heuristic optimization

对于高代价查询：

• 更充分的枚举和成本比较通常是值得的

Correlated Evaluation#

考虑查询：

1
select name
2
from instructor
3
where exists (
4
    select *
5
    from teaches
6
    where instructor.ID = teaches.ID
7
      and teaches.year = 2022
8
);

内层查询引用了外层 relation 的属性：

1
instructor.ID

这个属性叫做 correlation variable（相关变量）。

SQL 语义上，可以把内层 subquery 理解为一个依赖外层当前 tuple 的函数：

• 对外层 instructor 的每一条 tuple
• 带入其 ID
• 执行一次内层查询
• 判断是否存在匹配的 teaches tuple

这种执行方式称为：

Correlated evaluation（相关执行）。

问题：

• 外层有多少 tuple，内层可能就执行多少次
• 可能产生大量随机 I/O
• 对大表极其昂贵

Semijoin 与重复元组问题#

上面的 exists 查询不能直接粗暴改写成普通 join：

1
select name
2
from instructor, teaches
3
where instructor.ID = teaches.ID
4
  and teaches.year = 2022;

原因：

• 一名教师在 2022 年可能教授多门课程
• 普通 join 会为每条匹配 teaches tuple 输出一份教师 tuple
• exists 只要求“至少存在一条”，不会因为多次匹配而增加外层 tuple 的出现次数

为保持 SQL multiset 语义，应使用 semijoin（半连接）。

定义：

• 若 $r$ 中 tuple $r_i$ 出现 $n$ 次
• 且 $s$ 中至少存在一条 tuple 与其满足 join condition
• 则 $r_i$ 在 $r \ltimes_\theta s$ 中仍出现 $n$ 次
• $s$ 的属性不进入输出结果

因此查询可写为：

等价 SQL 还可以通过先去重再 join 实现：

1
with t1 as (
2
    select distinct ID
3
    from teaches
4
    where year = 2022
5
)
6
select name
7
from instructor, t1
8
where t1.ID = instructor.ID;

Anti-Semijoin#

对于 not exists：

1
select name
2
from instructor
3
where not exists (
4
    select *
5
    from teaches
6
    where instructor.ID = teaches.ID
7
      and teaches.year = 2022
8
);

可使用 anti-semijoin（反半连接）：

含义：

• 保留 instructor 中找不到任何匹配 teaches tuple 的那些 tuple

Decorrelation#

一般形式：

1
select A
2
from r1, r2, ..., rn
3
where P1
4
  and exists (
5
      select *
6
      from s1, s2, ..., sm
7
      where P21 and P22
8
  );

其中：

• $P_{21}$ 不涉及 correlation variables
• $P_{22}$ 涉及 correlation variables

可转换为：

把 nested query 转换为 join / semijoin / anti-semijoin 的过程称为：

Decorrelation（去相关）。

收益：

• 不必对外层每条 tuple 重复执行 inner query
• 可以使用高效 join algorithm
• optimizer 可以统一考虑 join order 和索引

Scalar Aggregate Subquery#

聚合子查询的 decorrelation 更复杂。

例子：

1
select name
2
from instructor
3
where 1 < (
4
    select count(*)
5
    from teaches
6
    where instructor.ID = teaches.ID
7
      and teaches.year = 2022
8
);

含义：

• 找出 2022 年教授课程数超过 1 门的教师

可以先对 teaches 分组聚合：

然后与 instructor 做带条件的 semijoin：

但并非所有 scalar subquery 都能这样安全转换：

• 标量子查询返回多行时，原 SQL 可能产生 runtime exception
• 聚合、null 与重复语义会增加转换难度
• decorrelation 是否值得做，也应经过成本比较

因此现实优化器对复杂 nested subquery 的 decorrelation 支持通常有限。

物化视图的作用#

普通 view 通常只保存定义查询。
Materialized view（物化视图） 会把查询结果实际计算并存储下来。

例子：

1
create view department_total_salary(dept_name, total_salary) as
2
select dept_name, sum(salary)
3
from instructor
4
group by dept_name;

如果系统频繁查询：

• 每个系的教师工资总额

那么物化该视图可以避免每次都：

• 扫描 instructor
• 按 dept_name 分组
• 重新计算 sum(salary)

查询时直接读物化结果即可。

代价是：

• 数据存在冗余
• 基表更新后，物化视图也必须同步更新

View Maintenance#

保持物化视图与基表一致的任务称为：

Materialized View Maintenance（物化视图维护）。

可选方式：

• 每次基表更新后完整重算视图
• 使用触发器维护
• 在应用程序更新基表时同步维护
• 周期性重算，例如每天夜间刷新
• 使用数据库系统直接提供的 materialized view refresh 机制

完整重算逻辑简单，但通常代价大。
更常用的思想是：

只根据基表发生的变化，计算视图中应新增或删除的部分。

这叫 Incremental View Maintenance（增量视图维护）。

Differential 与 Incremental Maintenance#

设 relation $r$ 发生变化：

• $i_r$：插入到 $r$ 的 tuple 集合
• $d_r$：从 $r$ 删除的 tuple 集合

这两个变化集合称为 relation 的 differential（差分）。

更新操作可等价看成：

• 先删除旧 tuple
• 再插入新 tuple

因此只讨论 insert / delete 即可覆盖 update 的核心逻辑。

常见关系操作的增量维护#

Join#

设物化视图：

$$v = r \bowtie s$$

若向 $r$ 中插入 $i_r$：

$$r_{new} \bowtie s = (r_{old} \cup i_r) \bowtie s = (r_{old} \bowtie s) \cup (i_r \bowtie s)$$

因为：

$$v_{old} = r_{old} \bowtie s$$

所以：

$$v_{new} = v_{old} \cup (i_r \bowtie s)$$

若从 $r$ 中删除 $d_r$：

$$v_{new} = v_{old} - (d_r \bowtie s)$$

关键点：

• 不重新计算整个 $r \bowtie s$
• 只 join 发生变化的少量 tuple

1
r(A, B) = {(a, 2), (a, 3)}
2
ΠA(r)   = {(a)}

使用物化视图优化查询#

物化视图不仅要被维护，还可以被 optimizer 用于 query rewrite。

Materialized View Selection 与 Index Selection#

系统需要决定：

• 哪些 view 值得物化
• 哪些 index 值得建立

二者共同特点：

• 都属于派生数据
• 都会加快某些查询
• 都会增加存储空间
• 都会增加更新维护成本

选择依据通常是 workload：

• 经常执行哪些查询
• 经常进行哪些更新
• 哪些查询有严格响应时间要求
• 可用存储空间和维护预算是多少

典型目标：

在空间限制和关键查询 / 更新约束下，使总体 workload 执行时间最小。

许多商业数据库提供 tuning assistant / wizard，协助 DBA 选择索引和物化视图。

Top-K Queries#

很多查询只需要排序结果中的前 $K$ 条：

1
select *
2
from r, s
3
where r.B = s.B
4
order by r.A ascending
5
limit 10;

若系统先生成完整 join 结果，再排序并只保留 10 条：

• 大量中间结果最终被丢弃
• 当 $K$ 很小时极其浪费

优化思路：

1
and r.A <= H

Optimization of Updates 与 Halloween Problem#

考虑：

1
update R
2
set A = 5 * A
3
where A > 10;

假设：

• 属性 A 上有索引
• 系统使用该索引扫描所有 A > 10 的 tuple
• 找到 tuple 后立即修改 A 与索引项

那么同一条 tuple 更新后，新的索引项可能再次落到尚未扫描的位置。
该 tuple 可能被再次发现并重复更新。

这称为：

Halloween Problem：更新改变了用于定位待更新 tuple 的查询执行过程，使同一 tuple 被错误地反复处理。

解决方式：

Join Minimization#

有时查询来自 view 展开，包含了其实不需要的 join。

例子：

1
select r.A, r.B
2
from r, s
3
where r.B = s.B;

若满足：

• r.B 是引用 s.B 的 foreign key
• r.B 声明为 not null
• 查询不需要 s 的任何属性
• 查询也不对 s 施加额外 filtering condition

则与 s 的 join 不会：

• 删除 r 中任何 tuple
• 产生 r tuple 的额外副本

因此可删除该 join：

1
select r.A, r.B
2
from r;

课件还给出含重复别名的例子：

1
select r.A, s2.B
2
from r, s as s1, s as s2
3
where r.B = s1.B
4
  and r.B = s2.B
5
  and s1.A < 20
6
  and s2.A < 10;