数据库查询处理
15.1 概述
查询处理(Query Processing)指从数据库中提取数据所涉及的一系列活动,包括:将高层查询语言(SQL)翻译成物理层可直接执行的表达式、执行代价的评估以及查询的实际执行。整体流程可以概括为下面三个阶段:
- 语法分析与翻译:将 SQL 语句解析成语法树,随后翻译成等价的关系代数表达式。系统会检查表名、列名及权限。
- 优化:同一个关系代数表达式可以有多个等价物;每个等价表达式的算子还可以选择不同实现算法(顺序扫描、索引扫描、散列连 接、归并连接等),从而组合出大量的执行计划。优化器根据统计信息估计代价,选择代价最低的一个。
- 执行:执行引擎按选定计划读取数据、计算结果并返回给用户。
一个执行计划由算子(operator)构成的树表示,叶子是关系(可能是文件扫描或索引扫描),内部结点是选择、投影、连接、聚集、排序等算子,每个算子还带有一个"实现方式"注解,例如" using B+-tree index"。
15.2 查询代价的度量
查询代价可以用 CPU 时间、I/O 次数、通信开销、内存使用等度量。传统磁盘数据库中,I/O 通常是主导因素,因此代价度量一般写成:
其中:
- :传送的块数(block transfers);
- :磁盘寻道次数(seeks);
- :单块传输时间;
- :一次寻道时间。
在分析各算法时,为简单起见常常只统计 ,并忽略 CPU 与结果输出的代价。设:
- :关系 占用的磁盘块数;
- :关系 的元组数;
- :每个元组的字节数;
- :每块可容纳的元组数(block factor);
- : 中属性 的不同取值个数;
- :查询可用的内存缓冲区块数。
代价模型中,"最坏情况"通常假设缓冲区仅够放下当前操作最小需要的页,"最好情况"则假设整张表可以缓存到内存。
15.3 选择运算
15.3.1 文件扫描的使用和索引的选择
对形如 的选择,有若干可能实现:
- A1 线性扫描 (linear search):顺序读取每一块,检查每个元组。代价为 次块传输、 次寻道;若 是主键且仅有一个匹配元组,平均代价约 。这是最通用但也是最慢的方法。
- A2 主索引 (primary index) 等值查询:若在 上有 B+ 树主索引且 是候选键,代价为 ,其中 为索引高度。
- A3 主索引,A 非候选键:可能匹配多条记录,但由于文件按 排序,匹配记录在磁盘上是连续的。代价 。
- A4 辅助索引 (secondary index):等值查询,若 是候选键,代价与 A2 相当;若非候选键,每条匹配记录可能位于不同块中,代价可达 ,其中 是匹配的元组数,可能比线性扫描还慢。
15.3.2 涉及比较的选择
对 或 :
- A5 主索引比较查询:若文件按 排序,则对于 ,先用索引定位第一个满足的元组,再顺序读取直到末尾;对于 ,则从起始位置顺序读到第一个不满足的元组,无需索引。
- A6 辅助索引比较查询:使用索引找到范围内的每个键,再随机读对应的元组;当结果元组数较多时,代价常常高于线性扫描。此时优化器可能弃用索引。
15.3.3 复杂选择的实现
对合取 :
- A7 用一个索引的合取选择:选择选择性最好的 用索引,其余条件在读到的元组上应用。
- A8 用组合索引的合取选择:若某几个属性上有组合索引,可以直接用组合索引处理其对应的合取条件。
- A9 用记录标识符集合的交的合取选择:对每个 都通过辅助索引取出满足条件的记录 ID,再对多个 ID 集合求交,最后按剩余 ID 读磁盘。
对析取 ,只有当每个 都能利用索引时才使用 A10 记录标识符集合的并的析取选择;否则退回线性扫描。取反 通常直接线性扫描。
15.4 排序
排序在数据库中出现在多种场景中:显式的 ORDER BY、DISTINCT 的去重、按分组键排序的聚集、归并连接等。若关系能全部装入内存,任何内存排序算法(如快速排序)即可;否则必须使用外排序(external sorting)。
15.4.1 外排序-归并算法
外排序-归 并(external sort-merge)分为两个阶段:
- 生成初始归并段(run):反复读取 块进入内存,在内存中排序后写回磁盘,得到若干长度为 的初始 run。若关系有 块,则得到 个初始 run。
- 多路归并:每一轮把最多 个 run 合并成一个更大的 run,每个 run 占用一个输入缓冲,另一块作输出缓冲。反复归并直到只剩一个 run。
15.4.2 外排序-归并的代价分析
设初始 run 数为 。每一轮归并把 run 数缩小 倍,因此归并轮数为:
再加上生成初始 run 的一遍读写,总的遍数(pass):
每一遍都要把整个关系读出并写回一次,所以总的块传输代价:
若 相对 足够大,通常一遍生成 run + 一遍归并即可完成。若考虑寻道次数,每个 run 的输入/输出块可以采用块缓冲(buffer block),将寻道次数从 降到 ,代价:
15.5 连接运算
连接是查询中最昂贵也最复杂的算子。设有关系 ( 块、 元组)和 ( 块、 元组),且连接条件为 。
15.5.1 嵌套-循环连接
对每一个 ,扫描一遍 ,输出所有满足 的 :
for each tuple tr in r:
for each tuple ts in s:
if θ(tr, ts): output (tr, ts)
最坏情况下每读一个 的元组都要扫描一遍 :
若整个 能装入内存(),则只需 块传输。选择较小的关系作为内表总是有利的。
15.5.2 块嵌套-循环连接
按块而非按元组做外循环:
for each block Br of r:
for each block Bs of s:
for each tr in Br, ts in Bs:
if θ(tr, ts): output (tr, ts)
代价:
若可以为外循环缓冲 块,则可进一步降为:
块嵌套-循环连接是最通用的连接算法之一:对任意连接条件都有效,且不需要索引。
15.5.3 索引嵌套-循环连接
若在 的连接属性上有索引,则可将内循环替换为索引查找:
for each tuple tr in r:
use index on s to find matching tuples ts
output (tr, ts) for each match
设一次索引查找的平均代价为 (B+ 树查找+读取匹配记录),则:
当外表 较小、内表 上又有可用索引时,索引嵌套-循环通常远优于块嵌套-循环。
15.5.4 归并-连接
也称 sort-merge join。要求两个关系都按连接属性排序,然后并行扫描:
sort r on join attribute
sort s on join attribute
ptr_r = start of r; ptr_s = start of s
while ptr_r != end and ptr_s != end:
compare tr and ts on join attribute
// 相等则输出所有匹配组合,然后推进指针
若两者已经排序,代价为 ;否则加上排序代价:
归并连接仅适用于等值连接或自然连接。它对已经排序的输入(如索引扫描输出)尤为高效。
15.5.5 散列-连接
Hash Join 适用于等值连接。基本思想是使用同一个散列函数 将两个关系按连接属性划分成 个分区,使得只有同一分区的元组才可能匹配:
- 建 (build) 阶段:读 入较小的关系 ,按 分区,得到 ;
- 划 (partition) 阶段:对 用同一 分区,得到 ;
- 探测 (probe) 阶段:对每一对 ,把 载入内存建散列表,再逐块扫描 做探测。
若每个 恰好能装入内存,则代价:
要满足此条件需要 ,一般再乘以避免哈希冲突的裕量因子(如 1.2)。若某个分区仍超出内存,则需要递归划分(recursive partitioning),代价升为:
当内存足够大到 ,一次划分即可完成。
混合散列连接(hybrid hash join) 保留第一个分区 常驻内存,可跳过一次写回,进一步降低代价。
15.5.6 复杂连接
对不等值连接、条件为多个谓词的连接,可组合基本算法:例如把等值条件用散列/归并连接实现,剩余条件在结果上过滤;也可以拆分为等值连接的并集、笛卡尔积后过滤等。
15.5.7 空间数据上的连接
对空间关系(如包含 -树索引的点、多边形集合),连接谓词往往是"相交"、"包含"、"距离小于 "等。常用算法包括:
- 索引嵌套-循环空间连接:对外表每个几何对象用 -树查内表;
- 空间散列连接:使用格网 (grid) 或 Z-order 曲线的哈希分区;
- -树--树同步遍历:两棵 -树同时下降,仅在包围盒相交处继续深入。
15.6 其他运算
15.6.1 去重
DISTINCT 与集合运算需要去重。两种典型实现:
- 基于排序:先外排序,然后线性扫描消除相邻重复;
- 基于散列:将元组散列到多个桶中,再在内存中对每桶去重。
15.6.2 投影
关系代数的投影 是集合语义(去重),SQL 的 SELECT 默认是多重集语义(不去重)。若需去重,可在投影后接一个去重算法;否则只需在读取时丢弃不相关的列。
15.6.3 集合运算
UNION、INTERSECT、EXCEPT 均可基于排序或散列实现:
- 排序法:先对两个关系排序,再线性扫描;
- 散列法:对第一个关系建散列表,再扫描第二个关系判断是否在表中。
UNION ALL 无需去重,代价最低。
15.6.4 外连接
- 左外连接 ⟕ :对 中未匹配的元组补 NULL;
- 右外连接 ⟖ :对 中未匹配的元组补 NULL;
- 全外连接 ⟗ :两侧都补。
可以在内嵌于任何连接算法的基础上,跟踪每个元组是否匹配来实现。
15.6.5 聚集
GROUP BY + 聚集函数可以基于排序或散列:
- 排序法:按分组键排序,然后一次线性扫描累加;
- 散列法:以分组键为散列码,一边扫描一边在内存中维护累加器。
对可增量计算的聚集(SUM、COUNT、AVG、MIN、MAX),只需存储少量中间状态;对 MEDIAN 等则需保留全部值。
15.7 表达式执行
对复杂的表达式(多个算子构成的树),执行策略主要有两种:
15.7.1 物化
物化(materialization) 自底向上执行算子树:先执行叶子上的算子,把结果写到临时关系;再以临时关系为输入执行上层算子。
- 优点:每个算子实现独立、易于优化;
- 缺点:中间结果需要额外的磁盘 I/O。若中间结果的块数为 ,则额外代价至少为 (写入)加 (读取)。
15.7.2 流水线
流水线(pipelining) 让上层算子在下层算子产生一个元组时立刻消费,避免写入临时关系。可以看作生产者-消费者模型:
- 需求驱动(demand-driven, pull):上层算子调用下层算子的
next()一次拿一个元组,也称 火山模型(Volcano/iterator model); - 生产者驱动(producer-driven, push):下层算子主动向上推送元组,适合并行流水线与 SIMD 化。
物化 vs 流水线对比:
| 维度 | 物化 | 流水线 |
|---|---|---|
| 中间结果 | 写入磁盘 | 保留在内存流中 |
| I/O | 高 | 低 |
| 内存 | 低 | 高(需缓冲多个算子) |
| 阻塞算子 | 自然支持 | 排序、聚集、散列建表阶段不能纯流水线 |
| 实现难度 | 简单 | 复杂,需协调调度 |
当计划中出现阻塞算子(blocking operator)(如排序、去重、聚集)时,需要在此断开为流水线段。
15.7.3 对于连续流数据的流水线
对流处理系统(如传感器数据、点击流),数据源无穷、不能物化,只能纯流水线执行,且很多算子要改为增量式版本:如滑动窗口聚集、增量连接。为限制资源,往往对时间/元组窗口进行限定,并对无法在窗口内匹配的元组丢弃或降级处理。
15.8 内存中的查询处理
当整个数据库或热点数据能常驻内存时,I/O 不再是瓶颈,CPU 反而成为主导。这催生了一套不同的优化技术。
15.8.1 高速缓存感知算法
现代 CPU 上,L1/L2/L3 高速缓存缺失的代价可能相当于几十甚至几百个 CPU 周期。缓存感知(cache-conscious) 算法会:
- 使用列组织或**分块(tiling)**提升空间局部性;
- 采用较小的散列表、大小与 L2 缓存对齐;
- 用向量化(vectorized execution) 一次处理一小批元组,摊薄函数调用开销;
- 尽量避免链式指针追逐(pointer chasing),改用连续数组。
15.8.2 查询编译
查询编译(query compilation) 把执行计划编译成机器代码(或 LLVM IR、Java 字节码),去除火山模型中每个 next() 调用的解释开销。HyPer、Impala、SingleStore 等系统都采用此策略,可以将吞吐率提升数倍。
15.8.3 面向列的存储
面向列(column store) 只读需要的列、按属性紧凑存放,配合字典编码、位打包和 RLE 压缩,可大幅减少扫描字节数并允许 SIMD 批量计算。C-Store/Vertica、MonetDB、ClickHouse、Parquet/ORC 都属于列存范式,在 OLAP 场景下性能远优于行存。
15.9 总结
- 查询处理包括语法分析、优化和执行三大阶段;执行计划是带算子实现注解的关系代数树。
- 代价度量以块传输与寻道次数为主,各算子的公式见本章。
- 选择运算根据条件形式和索引的可用性选择线性扫描、主/辅助索引、组合索引或记录 ID 交集/并集。
- 排序若无法一次装入内存,采用外排序-归并,遍数为 。
- 连接算法有嵌套-循环、块嵌套-循环、索引嵌套-循环、归并-连接、散列-连接;理解各自的代价公式与适用条件是选出高效计划的基础。
- 表达式执行有物化与流水线两种模型,实际系统通常混合使用。
- 内存数据库时代,缓存感知算法、查询编译与列存已成为高性能查询引擎的标配。
核心公式速查:
| 算子 | 主要代价(块传输) | 备注 |
|---|---|---|
| 线性扫描选择 | 无索引时通用 | |
| 主索引等值选择 | 候选键 | |
| 辅助索引比较查询 | 大则退回扫描 | |
| 外排序-归并 | 遍数 | |
| 嵌套-循环连接 | 最通用 | |
| 块嵌套-循环连接 | 优化后 | |
| 索引嵌套-循环连接 | 内表要有索引 | |
| 归并- 连接 | 仅等值连接 | |
| 散列-连接(无递归) |
选择连接算法的经验规则:
- 一小一大:优先索引嵌套-循环连接,把小表作为外表;
- 都已排序:归并-连接几乎无额外开销;
- 等值连接、无排序、有充足内存:散列-连接通常最快;
- 无索引且都很大:块嵌套-循环连接作为兜底方案;
- 复杂谓词(不等值、函数谓词):拆分成等值部分 + 后置过滤。
理解代价公式与算法适用条件后,就能理解 EXPLAIN 输出中的算子选择,从而在必要时通过创建索引、调整连接顺序或提示(hint)介入优化器决策。