查询优化 - 小鱼儿clouding的博客

一、查询优化器总体架构

1.1 优化器的整体流程

一个完整的查询优化器将 SQL 查询转化为执行计划的过程大致分为以下步骤：

查询分块（Query Block Decomposition）：将一个含嵌套的 SQL 查询拆分为若干个无嵌套的查询块，每个块有唯一的 SELECT...FROM...WHERE... 结构
翻译为关系代数：将每个查询块翻译为关系代数表达式（笛卡尔积 -> 选择 -> 投影的基础形式）
生成候选访问计划：针对每个关系代数表达式，枚举各种可能的访问方法（全表扫描、索引扫描、索引嵌套循环连接等）
代价估计：利用数据字典中的统计信息估算每个候选计划的 IO 代价
选择最优计划：从所有候选计划中选出代价最低的执行计划
嵌套查询的整合：将各个查询块的最优计划组合起来，处理关联子查询的去关联化

优化器把一个查询分成若干小块，每个小块翻译成一个关系代数表达式，然后分别做优化，最后再考虑嵌套查询之间的组合。

1.2 查询分块

对于带有嵌套子查询的 SQL，优化器先将嵌套拆开单独处理。基本思想是：

将嵌套的子查询独立拿出来优化
如果子查询的结果是一个不变的值（与外部查询无关），则只需执行一次，将结果填入外部查询
如果子查询引用了外部属性（关联子查询 / correlated subquery），则对外部每条元组都需要重新执行

这种分解策略将复杂的嵌套查询优化问题做了简化，但也意味着后续需要在嵌套查询优化阶段重新考虑它们之间的组合方式。

二、代价估计（Cost Estimation）

2.1 为什么需要代价估计

在生成多种候选访问计划后，优化器需要估算每个计划的执行代价，以便比较。需要估算的关键信息包括：

每个操作的结果大小（元组数、字节数）
结果是否有序
使用的是 Pipeline（无额外 IO，数据在内存中流水传递）还是临时表（需要写磁盘）

代价估计所利用的信息存储在数据库的数据字典（data dictionary）中，包括各表的元组数、每个属性上取值的统计等。

2.2 选择率估计的基本前提

教材中介绍的简单方法基于两个前提假设：

均匀分布假设：一个列上各取值的出现次数大致相同
属性独立假设：不同列之间的取值分布相互正交（无关）

在这两个假设下，选择率（selectivity）的估计非常简单：

条件类型	选择率估计
`column = value`	$\frac{1}{\text{该列不同取值个数}}$
`column > value`	$\frac{\max - \text{value}}{\max - \min}$
`column IN (value_list)`	$\frac{\text{list中的取值个数}}{\text{该列不同取值总数}}$
多个 AND 条件	各条件选择率的乘积

这两个前提实际上是非常强烈的假设。在一列上的值不可能是均匀分布的，列和列之间也不可能是完全无关的（例如，在学校里，年长的老师工资总体偏高）。如果这些条件不满足，上述公式得到的结果存在误差。

对于单个属性，可以用直方图等办法改进估计。但问题在于，如果涉及多个属性的联合约束条件（如 WHERE A=X AND B=Y），不可能耗费大量空间去记录任意两个属性之间的联合分布关系。这正是数据库领域的一个核心难题。

2.3 直方图（Histogram）

为了比简单的均匀分布假设更准确地描述数据分布，数据库通常使用直方图。主要有两种类型：

等宽直方图（Equi-width Histogram）

将值的范围按宽度均匀分成若干个桶（bucket）
每个桶内包含相同个数的不同取值
例如：15个不同取值分成5个桶，每桶3个值
优点：结构简单，便于管理
缺点：对数据做了平滑处理，极端值（如高频值）的信息会丢失

等深直方图（Equi-depth Histogram）

保持每个桶内的元组总数大致相同
高频值可能独占一个桶，低频值则多个合并
例如：总共45条记录，5个桶，每桶约9条。出现14次的某个值独自占一个桶，出现7次和8次的两个值合占一个桶
优点：对极端值的描述更准确，高频值的信息保留得好
缺点：当数据发生变化时，维护成本高

不同数据库采用不同的直方图来表示数据分布，但一般来说都会记录一下每个属性上取值的统计信息。有些数据库还会只维护出现次数最多的前十个值（Top-K），这样就可以用更少的空间获得关键信息。

2.4 AI 模型与代价估计

最近几年，AI 模型结合到数据库系统中的一个重要应用方向就是代价估计——用 AI 模型来更准确地估计参数和查询代价。这是目前数据库研究的热点之一。

三、关系代数表达式的等价变换

3.1 初始转换

任何一个 SQL 查询都可以被转换为最基础的关系代数表达式：

\[\pi(\sigma(\text{Table}_1 \times \text{Table}_2 \times \cdots \times \text{Table}_n))\]

即先将所有表做笛卡尔积，再做选择，最后做投影。

3.2 核心优化思想：早做选择和投影

关系代数变换的核心原则是：

尽可能让选择操作（$\sigma$）和投影操作（$\pi$）在连接（$\Join$）之前执行。

选择操作提早做可以大幅减少参与连接的元组数量
投影操作中间插入可以去掉后续计算不需要的列，减少元组长度

将选择操作”下推”到笛卡尔积之前，实际上是利用关系代数的等价变换规则实现的。

3.3 变换规则的工程意义

经过这些代数变换后，访问计划的搜索空间被定义在语义等价但执行代价不同的多种关系代数表达式之上。

四、单关系访问计划的生成

4.1 不使用索引：全表扫描

对于单张表的查询，如果没有索引可用，只能对该表的文件进行全表扫描（sequential scan），扫描过程中同时做选择和投影。

代价估算示例（基于船只/船员/租船记录的例子）：

原始表大小：$50$ 页
投影后每元组长度为原来的 $0.8$ 倍
rating > 5 的选择率为 $0.5$
age = 20 的选择率为 $0.1$
最终结果大小：$50 \times 0.8 \times 0.5 \times 0.1 = 20$ 页
全表扫描代价：$50$（扫描）+后续排序等操作

4.2 使用单个索引

当表上存在索引时，有多种搜索方式：

先用选择性好的索引：如果 age 上有索引且其选择率低（只有10%的人满足），则先用 age 索引找到符合条件的元组，再用 rating 条件做二次筛选
先用另一个索引：如果 rating 上有索引，也可以反过来
选择的原则：优先使用选择性更小（即约束更严格）的索引，因为能筛掉更多元组

4.3 同时使用多个索引分别搜索再合并

如果两个涉及条件各自的属性上都有索引，可以：

两个索引各自找出符合各自条件的所有元组 ID
对两组 ID 进行交集操作，得到同时满足两个条件的元组

4.4 利用有序索引完成 GROUP BY

如果 GROUP BY 的属性恰好与某个索引的排序属性一致，可以直接利用该索引完成排序，无需额外的排序开销。

4.5 仅通过索引完成查询（Index-only Access）

在创建索引时，某些数据库（如 DB2）支持在索引中附带附加属性：

CREATE INDEX idx ON Sailors(sid) INCLUDE (age, rating);

这样，索引的叶子节点（data entry）中不仅包含索引键（sid），还包含了 age 和 rating 的值。如果查询涉及的所有属性都在索引中存在，就可以完全利用索引完成查询而无需访问实际的数据文件。这是数据库系统中非常常用的优化技巧——通过索引覆盖查询所需的所有属性，从而彻底避免访问基本表。

五、多关系访问计划的生成

5.1 连接顺序与连接树形态

对于多表连接，访问计划的核心问题是连接顺序和连接树的结构。

连接树有两种基本形态：

形态	描述	特点
左深树（Left-deep Join Tree）	AB 连接，结果再与 C 连接，结果再与 D 连接……	支持 Pipeline（`on the fly`），IO 效率高
浓密树（Bushy Tree）	AB 连接，CD 连接，两个结果再连接	候选方案极多，且需生成大量临时表

当前主流数据库系统基本上只考虑左深树（left-deep tree），不考虑浓密树（bushy tree）。原因有两点：第一，浓密树的候选方案太多，优化时间有限；第二，浓密树中每次”两个临时结果再连接”会产生大量中间临时表，IO 代价大。而左深树可以充分利用 Pipeline 方式——on the fly——将下层连接产生的每条元组直接传递给上层连接。

5.2 连接方案的枚举过程

优化器采用动态规划思想，分多遍扫描来枚举所有候选计划：

第一遍扫描：枚举每个单表的所有访问方法（全表扫描/索引扫描/索引覆盖），考虑其上的选择和投影
第二遍扫描：枚举任意两个表的所有连接方案，包括：
- 连接顺序（谁左谁右）
- 谁作为外关系（outer），谁作为内关系（inner）
- 连接算法（嵌套循环连接、索引嵌套循环连接、哈希连接等）
- 能否使用 Pipeline 方式
第三遍扫描：在二表连接的结果上，枚举第三个表的连接方案
以此类推，直到覆盖所有涉及的表

5.3 连接算法的选择

选择连接算法时要考虑索引的可用性：

关键决策示例：假设 reserves 和 sailors 做连接。sailors 在 sid 上有索引，但 reserves 在 sid 上没有索引。如果以 reserves 为外关系，以 sailors 为内关系，就可以使用索引嵌套循环连接（reserves 中每条元组用 sid 去 sailors 的索引上查找）。反之则不能用索引嵌套循环连接，只能用其它连接算法。

5.4 Pipeline vs Temp Table

Pipeline（流水线）：连接产生的每条元组立即传递给下一个操作，数据一直在内存中，无额外 IO
临时表（Temp Table / Materialization）：操作的结果先全部写入磁盘的临时表，后续操作再从临时表读取，有额外 IO 代价

优化器在枚举方案时，会优先考虑能使用 Pipeline 的方案（即左深树），因为这种方式可以显著减少 IO。

六、嵌套子查询的优化

6.1 非关联子查询（Non-correlated Subquery）

如果子查询没有引用外部查询的任何属性，其结果是不变的：

只需执行一次子查询，将结果代入外部查询
在查询分块阶段即可将这类子查询与外部查询分离

6.2 关联子查询（Correlated Subquery）

如果子查询引用了外部查询的属性（例如 WHERE R.sid = S.sid），其值随外部每条元组而变化：

对外部查询的每条元组，子查询都需要重新执行
这种”逐条执行子查询”的方式代价极大

对于关联子查询（correlated subquery），基本优化策略是尽可能将其转换为连接操作。一旦转换为连接，就可以利用各种连接优化技术。

6.3 去关联化（Decorrelation）

去关联化（将关联子查询转换为连接）是一个已被研究多年的问题，但至今并未完全解决。对于不同形式的关联子查询，去关联的方法各不相同，目前仍然有研究工作在推进。

查询优化是数据库中一个持久性的研究问题，不仅包括新的优化算法，还有分布式查询优化、时序数据上的查询优化、图数据上的查询优化等方向。

6.4 多查询优化（Multi-query Optimization）

在数据仓库场景中：

数据通常不频繁更新
多个查询之间可能有重叠的计算
优化器可以批量考察近期到达的多个查询，做统一优化
目标是最大化中间结果的复用

七、查询执行模型

7.1 从执行计划到可执行程序

查询优化的输出是一个执行计划（规定了哪些操作、用什么算法），但它本身不是程序。查询执行阶段的任务就是将执行计划转化为真正可运行的代码。

查询执行的优化目标是以最短的时间完成查询，手段包括：

减少总的执行指令数
减少循环数量
利用并行处理

7.2 拉取式 vs 推送式

特点	拉取式（Pull-based）	推送式（Push-based）
数据流向	从根节点向上层请求，逐级向下”拉”数据	从底层数据源出发，逐级向上”推”数据
驱动方式	顶层的查询操作需要数据时才向下索取	底层扫描完成后直接将结果逐级上送
内存消耗	低（每次只需要少量数据）	高（可能要将整张表送上）
函数调用	多（每次都逐层调用 `get_next`）	少
适用场景	OLTP 类型的短查询（数据量小）	OLAP 类型的批量查询（数据量大）
并行友好性	较线性，”等着”上一级完成	更适合规划和调度分布式/异步计算

拉取式类似从上层不断发命令往下要数据，下级找到数据后一层层反馈回来，然后再要下一条。推送式则类似流水线，底层做完了直接往上送，不用等上面的命令。

7.3 拉取式的三种实现模型

拉取式模型依靠三个核心接口函数：

open() — 打开/初始化
get_next() — 获取下一条（一批）元组
close() — 清理和关闭

三种模型的核心区别在于 get_next() 每次返回多少元组：

火山模型（Volcano Model / Iterator Model）

每次 get_next() 只返回一条元组
函数调用最频繁，但内存消耗最小
最经典的数据库执行模型

物化模型（Materialization Model）

每次 get_next() 返回所有元组（整张表或整个中间结果）
需要在每层用 out 空间存储全量结果
函数调用最少，但内存压力最大
与推送式方法的思路相似

向量化模型（Vectorized Model）

每次 get_next() 返回一批元组（如一次10条或一批，受阈值 $N$ 控制）
是前两者的折中方案
对内存压力适中，效率高于火山模型
现代列存数据库普遍采用的方式

三种模型的执行过程本质上完全一样，唯一的差别就是每次返回元组的数量不同。向量化模型是当前最实用的选择——既不会像火山模型那样调用太多次函数，也不像物化模型那样对内存压力太大。

7.4 火山模型的详细执行过程

以查询”选修了1号课程的学生姓名和成绩”为例，执行计划为： $\pi_{\text{sname, grade}}(\text{Student} \Join_{\text{sno}} \sigma_{\text{cno}=1}(\text{SC}))$

火山模型的执行过程：

最上层投影操作需要一条元组，向连接操作发出 get_next()
连接操作为了实现一条结果元组，向左子树和右子树分别索取数据
左子树的 get_next() 沿树向下传递到 Student 表的扫描操作
右子树的选择操作先要拿到 SC 表中符合条件的元组
选择操作向下要到 SC 表的一条元组，判断 cno=1 是否为真，为真则返回
连接操作拿到左右各一条元组后，按哈希连接匹配后生成一条结果返回给投影
投影操作提取所需属性，输出给用户
用户再要求下一条时，整个过程重复

关键特点：每层都是一个独立的运算符（operator），互不干扰，通过标准接口 open/get_next/close 配合工作。这种设计使得任意运算符都可以任意组合。

八、并行执行

8.1 并行的三个层次

数据库系统的并行执行可以在三个层次上实现：

层次	名称	描述
第一层	节点间并行（Inter-node Parallelism）	多台机器/多个数据节点同时计算（MPP架构）
第二层	节点内多线程并行（Intra-node Parallelism）	单机多核 CPU 上多线程同时执行
第三层	单指令多数据并行（SIMD）	CPU 指令级并行，一个指令同时处理多个数据

8.2 节点间并行：MPP架构

在现代分布式数据库（如云计算平台）中，数据被分割存储在多个节点上。当一个查询到来时，可以在多个数据节点上同时执行计算。

架构演进：

早期（协调节点主导）：协调节点（coordinator）负责接收查询、分发数据、收集结果，每个数据节点自身计算能力有限。类似 MapReduce 的框架：每个 map/reduce 阶段都有大量网络通讯开销
现代（数据节点自主）：协调节点退化为路由/代理角色，只负责制定执行方案。真正的查询执行由底下的数据节点自主完成——数据节点之间可以自行交换数据，在每个节点上完成部分计算。这避免了协调节点成为瓶颈

在云计算兴起之前，OLAP 需要昂贵的大型数据仓库服务器（如 Teradata）。云计算出现后，数据被分散在很多廉价计算节点上，虽然计算总量更大，但分散计算的效果反而更好。

数据库系统和计算机硬件的发展结合得非常紧密。硬件的任何进步（多核CPU、SIMD、GPU等），数据库系统几乎第一时间就会加以利用。

8.3 节点内并行：多线程

在单节点、多核 CPU 的背景下，两种算子并行策略：

算子间并行（Inter-operator Parallelism）：将查询计划树中的不同算子放在不同线程/不同核上，利用 Pipeline（on the fly）方式——连接完了送给选择，选择完了送给投影，像流水线一样
算子内并行（Intra-operator Parallelism）：将数据划分为多个分区，同一算子跑在多个线程上——例如将数据分成3份，3个线程各自执行选择操作

8.4 SIMD：单指令多数据并行

SIMD（Single Instruction, Multiple Data）是CPU指令级的并行技术：

传统汇编中，一个寄存器存一个值，两个寄存器做一个加法
SIMD 中，一个寄存器变成一个向量（存放多个值，如4个），两个向量寄存器做加法时，对应的4个位置同时运算

支持的操作包括：

算术运算（加减乘除）
逻辑运算
比较运算
寄存器间的数据移动

与列存储的协同：列存数据库中，同一个列中多个连续的值的格式相同。当需要对两个列做运算时，SIMD 可以一次性同时算好几个值，效率大大提高。

8.5 GPU 在数据库中的应用

GPU 内部有大量计算单元，天然适合大规模数据并行计算
早期 GPU 的通讯带宽较弱，限制了在数据库查询中的应用效果
随着 GPU 通讯能力的提升，它在数据挖掘和数据库查询中的应用效果开始显现