第二章-查询树 - 大梦不醒

1.1 查询优化的简介#

查询优化器是数据库管理系统中承上启下的模块：

1
语法分析 → 查询树 → 【查询优化器】 → 执行计划 → 执行器

输入：语法分析模块传递的查询树输出：最优的查询执行计划

为什么需要查询优化器？#

查询优化器相对于人工优化有三大优势：

优势	说明
信息不对称	优化器参考统计模块自动产生的统计信息，从各角度描述数据分布；用户无法全面了解数据分布，人脑也难以构建精确的代价计算模型
时效性不同	数据瞬息万变，A时间点的高性能计划在B时间点可能很低效；优化器随时根据数据变化调整，用户只能手动更改
计算能力不同	优化器可从几百种方案中选最优，人脑全面计算需要的时间远远更长

优化的两个层次#

1
查询优化
2
├── 逻辑优化（RBO，Rule Based Optimization）
3
│   └── 基于关系代数的等价逻辑变换
4
└── 物理优化（CBO，Cost Based Optimization）
5
    └── 基于代价估算的物理路径筛选

逻辑优化：对关系代数表达式进行等价变换，可能获得执行性能更好的等价式
物理优化：关系代数中的连接是逻辑运算符，需要生成多个物理连接路径，通过代价计算模型选择”最优”路径

1.2 逻辑优化#

1.2.1 关系模型基础#

基本概念：

关系（Relation）：通常所谓的”表”，形态类似二维数组
元组（Tuple）：关系中的一行，也称N-元组
属性（Attribute）：关系中的一列
域（Domain）：所有属性的值组成的集合

示例表：

1
STUDENT(sno, sname, ssex)
2
COURSE(cno, cname, tno)
3
SCORE(sno, cno, degree)
4
TEACHER(tno, tname, tsex)

关系代数的5个基本操作符#

操作符	符号	说明
选择	σ	按条件筛选行
投影	Π	选择指定列
笛卡尔积	×	两个关系的所有可能组合
并集	∪	两个关系的合并
差集	－	从一个关系中减去另一个关系

衍生的重要操作：

交集（∩）：可以用并集和差集表达
连接（⋈）：可以用笛卡尔积、选择和投影表达

扩展操作（非经典关系代数，但常用）#

操作	说明
左外连接（⟕）	保留左表全部，右表不匹配补NULL
右外连接（⟖）	保留右表全部，左表不匹配补NULL
全外连接（⟗）	保留两表全部，不匹配补NULL
半连接（⋉）	左表中与右表匹配的行（只返回左表列）
反连接	左表中与右表不匹配的行
聚集和分组（γ）	AVG、SUM、GROUP BY等

连接操作的术语：

外表/左表/LHS：连接操作左侧的表
内表/右表/RHS：连接操作右侧的表
Nonnullable-side：外连接中无需补NULL值的表（如左连接的左表）
Nullable-side：外连接中需要补NULL值的表（如左连接的右表）

关系演算#

关系演算从更高层次描述计算结果，不关心计算过程：

元组关系演算：基于元组的操作
域关系演算：基于属性的操作

元组关系演算的操作符：

存在量词（∃）和全称量词（∀）
比较操作符（>，>=，<，<=，=，!=）
逻辑操作符（¬，∧，∨，=>）

关系代数与关系演算的等价对照：

关系代数	元组关系演算
Πsno(STUDENT)	{P \| ∃(t) ∧ (STUDENT(t) ∧ P.sno = t.sno)}
σsno=1(STUDENT)	{P \| ∃(t) ∧ (STUDENT(t) ∧ P.sno = t.sno ∧ … ∧ t.sno = 1)}

SQL语言的定位#

SQL是一种介于关系代数和关系演算之间的描述性语言：

吸取了关系代数的逻辑操作符
放弃了关系代数的”过程化”特点
更多地采用了关系演算的方法

关键特性：SQL只规定了”WHAT”（要什么），没有规定”HOW”（怎么做），这导致查询优化”大有可为”。

关系代数等价变换规则#

规则1：交换律

1
A × B == B × A
2
A ⋈ B == B ⋈ A
3
A ⋈F B == B ⋈F A（F是约束条件）

规则2：结合律

1
(A × B) × C == A × (B × C)
2
(A ⋈F1 B) ⋈F2 C == A ⋈F1 (B ⋈F2 C)

规则3：分配律

1
σF(A × B) == σF(A) × B（其中F ∈ A）
2
σF(A × B) == σF1(A) × σF2(B)（其中F = F1 ∪ F2）
3
Πp,q(A × B) == Πp(A) × Πq(B)（其中p ∈ A，q ∈ B）

规则4：串接律

1
ΠP(ΠQ(A)) == ΠP(A)（其中P ⊆ Q）
2
σF1(σF2(A)) == σF1∧F2(A)

推论：选择操作满足交换律

1
σF1(σF2(A)) == σF2(σF1(A))

1.2.2 逻辑优化示例#

问题：查询”编号为5的老师承担的所有课程名字”

原始表达式：

1
Πcname (σTEACHER.tno=5 ∧ TEACHER.tno=COURSE.tno (TEACHER × COURSE))

优化步骤1：选择下推（规则3分配律）

1
Πcname (σTEACHER.tno=COURSE.tno (σTEACHER.tno=5(TEACHER) × COURSE))

原理：笛卡儿积是”重”操作，先选择后连接可降低计算量
效果：TEACHER从5行缩小到1行，笛卡儿积从5×5=25行降到1×5=5行

优化步骤2：投影下推（规则4串接律）

1
Πcname (σTEACHER.tno=COURSE.tno (σTEACHER.tno=5(TEACHER) × Πcname,tno(COURSE)))

原理：COURSE只需要cname和tno列，垂直方向缩小
注意：连接条件TEACHER.tno=COURSE.tno中需要COURSE.tno，投影时必须保留

优化步骤3：等价推理

1
Πcname (σTEACHER.tno=COURSE.tno (σTEACHER.tno=5(TEACHER) × Πcname,tno(σCOURSE.tno=5(COURSE))))

推理：TEACHER.tno=5 ∧ TEACHER.tno=COURSE.tno → COURSE.tno=5
效果：COURSE从5行缩小到2行

优化步骤4：消除冗余条件

1
Πcname (σTEACHER.tno=5(TEACHER) × Πcname,tno(σCOURSE.tno=5(COURSE)))

推理：经过选择后TEACHER.tno一定是5，COURSE.tno也一定是5，连接条件恒为TRUE
效果：消除不必要的连接判断

最终效果对比：

指标	优化前	优化后
笛卡儿积输入	5×5=25行	1×2=2行
中间结果属性数	6属性	5属性
输出结果	1属性，2元组	1属性，2元组

逻辑优化的两个启发式规则#

尽量将选择操作下推到下层节点来做（水平方向缩小）
尽量在叶子节点上使用投影缩小中间结果（垂直方向缩小）

逻辑优化的挑战#

扩展操作（外连接、聚集操作）增加了优化难度
内连接中能下推的约束条件，换成外连接不一定能下推
基于内连接能做的等价推理，换成外连接也不一定等价

1.3 物理优化#

代价模型#

执行代价 = IO代价 + CPU代价

IO代价的挑战#

挑战	说明
磁盘种类不同	机械磁盘和SSD的读写效率差异大
缓存系统	数据可能在缓存中，不产生IO
顺序/随机读写	机械磁盘上差异大，SSD上差异小
磁盘缓存	磁盘本身也有缓存系统

CPU代价的挑战#

挑战	说明
CPU型号差异	不同型号性能不同
多级cache	CPU的cache比数据库缓存效率更高
表达式复杂度	不同表达式代价不同

数据分布的影响#

相同数据在不同分布下开销不同（有序vs无序、稀疏vs紧凑）
相同数据面临不同选择操作时开销不同（高频值vs低频值）

核心观点：代价模型不需要”准确”，只需要能用于比较物理路径的优劣就够了。

1.3.1 物理优化的4个”法宝”#

1. B+树#

B树的性质：

除根节点外，每个节点至少拥有m/2个子节点（半满到全满）
所有叶节点都在同一层（查找复杂度相同，等于树高）
有k棵子树的分支节点存在k-1个关键码，关键码递增排列

PostgreSQL的B+树：基于Lehman和Yao的论文改进，增加了”下一个节点的指针”和”页内最大值”，提高使用效率。

在查询优化中的作用：

B+树索引可用于索引扫描、位图扫描
单值查询、范围查询效率高
代价等于B+树的树高

2. Hash表#

在查询优化器中的使用：

实现分组操作（Hash天然具有分类功能）
建立Hash索引（适用于等值约束条件）
Hash Join（对内表建立Hash表，外表元组在Hash表中探测）

3. 排序#

在查询优化中的用途：

实现分组操作（排序后相同数据聚集）
B树索引建立（堆存储无序，B树叶子节点有序）
MergeJoin（先排序后归并）
Order By操作

排序的代价：取决于数据量和可用内存（内排序vs外排序）

4. 物化#

定义：将扫描或连接的中间结果保存起来

优点：数据可一次产生多次利用（如5%数据作为中间结果，物化后STUDENT表每条元组只和这5%连接）

代价：中间结果大时需写入外存，产生IO

决策：比较物化和不物化两条路径的代价，选择较低者

1.3.2 物理路径的生成过程#

扫描路径（针对单个关系）#

扫描方式	说明	优点	缺点
顺序扫描	遍历全部数据页面	普适性强	代价通常较高
索引扫描	扫描索引获得元组地址，再访问数据	避免全表扫描	可能大量随机读
快速索引扫描	索引上的数据满足要求，只扫描索引	效率最高	需要索引覆盖
位图扫描	通过位图将地址变得有序，消除随机读	减少随机读	需要额外的位图构建
TID扫描	根据元组在磁盘上的存储地址直接获取	效率非常高	只适用于已知TID的情况

扫描路径的层级：扫描路径通常是执行计划的叶子节点，为连接路径做准备。

连接路径（针对两个关系）#

连接方式	算法复杂度	适用场景
Nested Loop Join	O(mn) 或 O(mlogn)（内表有索引）	内表有索引时效率高
Hash Join	O(m*n/N)（N为Hash桶数）	内表无索引但数据量适中
Merge Join	取决于排序代价	已排序数据或小数据集

Nested Loop Join：

外表顺序扫描，内表索引扫描
整体复杂度O(m*logn)

Hash Join：

对内表建立Hash表
外表元组在Hash表中探测
假设Hash表有N个桶，时间复杂度O(m*n/N)

Merge Join：

先对两个关系排序
然后进行归并
如果关系上有有序索引，可以不用单独排序

路径搜索的方法#

问题：多表连接的解空间以几何级数增长

3个表，每个表3个扫描路径，连接顺序12种，连接路径9种
总共需要计算27×12×9 = 2916种情况

搜索方法：

方法	方式	优点	缺点
动态规划	自底向上	能找到全局最优解	表多时耗时很长
自顶向下	先构建逻辑树再枚举物理路径	逻辑和物理优化无明显界限	实现复杂
遗传算法	随机搜索	效率可控	可能只是局部最优

PostgreSQL的策略：

表数≤11：采用动态规划方法
表数>11：启用遗传算法

1.4 文件介绍#

PostgreSQL查询优化器代码位于 src/backend/optimizer 目录：

1
optimizer/
2
├── plan/          # 总入口，调用prep和path
3
├── prep/          # 逻辑优化（逻辑重写）
4
│   ├── preplistlist.c    # 投影重写
5
│   ├── prepqual.c        # 选择条件重写
6
│   ├── prepjointree.c    # 连接操作重写
7
│   └── prepunion.c       # 集合操作重写
8
├── path/          # 物理优化（路径生成）
9
│   ├── allpath.c         # 物理路径入口
10
│   ├── indexpath.c       # 索引扫描路径
11
│   ├── tidpath.c         # TID扫描路径
12
│   ├── costsize.c        # 代价计算
13
│   ├── clausesel.c       # 选择率计算
14
│   ├── equivclass.c      # 等价类处理
15
│   ├── joinrels.c        # 生成连接表
16
│   ├── joinpath.c        # 生成连接路径
17
│   └── pathkeys.c        # 记录有序性
18
├── geqo/          # 遗传算法
19
└── util/          # 公共函数

执行流程：

1
Plan入口 → Prep模块（逻辑重写） → Path模块（物理优化）
2
                                    ├── 启用遗传算法？→ geqo目录
3
                                    └── 否 → path目录

1.5 示例约定#

逻辑优化阶段使用的表：

1
CREATE TABLE STUDENT(sno INT primary key, sname VARCHAR(10), ssex INT);
2
CREATE TABLE COURSE(cno INT primary key, cname VARCHAR(10), tno INT);
3
CREATE TABLE SCORE(sno INT, cno INT, degree INT);
4
CREATE TABLE TEACHER(tno INT primary key, tname VARCHAR(10), tsex INT);

物理优化阶段使用的表：

1
CREATE TEST_A(a INT, b INT, c INT, d INT);
2
CREATE TEST_B(a INT, b INT, c INT, d INT);
3
CREATE TEST_C(a INT, b INT, c INT, d INT);
4
CREATE TEST_D(a INT, b INT, c INT, d INT);

1.6 小结#

逻辑优化核心#

基于关系代数等价变换
大量逻辑等价规则（交换律、结合律、分配律、串接律）
核心手段：选择下推 + 投影下推
目标：缩小中间结果以提高执行效率

物理优化核心#

通过代价估算挑选代价较低的物理路径
分为扫描路径和连接路径
代价模型：IO代价 + CPU代价
搜索算法：动态规划（小表量）/ 遗传算法（大表量）

本章定位#

本章建立了查询优化器的知识框架，后续章节将深入展开：

第2章：查询优化器的预处理阶段
第7章：动态规划和遗传算法的详细介绍

音乐

音乐