跳到主要内容

数据库查询处理

15.1 概述​

查询处理(Query Processing)指从数据库中提取数据所涉及的一系列活动,包括:将高层查询语言(SQL)翻译成物理层可直接执行的表达式、执行代价的评估以及查询的实际执行。整体流程可以概括为下面三个阶段:

  • 语法分析与翻译:将 SQL 语句解析成语法树,随后翻译成等价的关系代数表达式。系统会检查表名、列名及权限。
  • 优化:同一个关系代数表达式可以有多个等价物;每个等价表达式的算子还可以选择不同实现算法(顺序扫描、索引扫描、散列连接、归并连接等),从而组合出大量的执行计划。优化器根据统计信息估计代价,选择代价最低的一个。
  • 执行:执行引擎按选定计划读取数据、计算结果并返回给用户。

一个执行计划由算子(operator)构成的树表示,叶子是关系(可能是文件扫描或索引扫描),内部结点是选择、投影、连接、聚集、排序等算子,每个算子还带有一个"实现方式"注解,例如"σA=v\sigma_{A=v} using B+-tree index"。


15.2 查询代价的度量​

查询代价可以用 CPU 时间、I/O 次数、通信开销、内存使用等度量。传统磁盘数据库中,I/O 通常是主导因素,因此代价度量一般写成:

cost=b⋅tT+S⋅tS\text{cost} = b \cdot t_T + S \cdot t_S

其中:

  • bb:传送的块数(block transfers);
  • SS:磁盘寻道次数(seeks);
  • tTt_T:单块传输时间;
  • tSt_S:一次寻道时间。

在分析各算法时,为简单起见常常只统计 bb,并忽略 CPU 与结果输出的代价。设:

  • brb_r:关系 rr 占用的磁盘块数;
  • nrn_r:关系 rr 的元组数;
  • lrl_r:每个元组的字节数;
  • frf_r:每块可容纳的元组数(block factor);
  • V(A,r)V(A, r):rr 中属性 AA 的不同取值个数;
  • MM:查询可用的内存缓冲区块数。

代价模型中,"最坏情况"通常假设缓冲区仅够放下当前操作最小需要的页,"最好情况"则假设整张表可以缓存到内存。


15.3 选择运算​

15.3.1 文件扫描的使用和索引的选择​

对形如 σA=v(r)\sigma_{A = v}(r) 的选择,有若干可能实现:

  • A1 线性扫描 (linear search):顺序读取每一块,检查每个元组。代价为 brb_r 次块传输、11 次寻道;若 AA 是主键且仅有一个匹配元组,平均代价约 br/2b_r/2。这是最通用但也是最慢的方法。
  • A2 主索引 (primary index) 等值查询:若在 AA 上有 B+ 树主索引且 AA 是候选键,代价为 (hi+1)⋅(tT+tS)(h_i + 1) \cdot (t_T + t_S),其中 hih_i 为索引高度。
  • A3 主索引,A 非候选键:可能匹配多条记录,但由于文件按 AA 排序,匹配记录在磁盘上是连续的。代价 ≈hi+⌈b/fr⌉\approx h_i + \lceil b/f_r \rceil。
  • A4 辅助索引 (secondary index):等值查询,若 AA 是候选键,代价与 A2 相当;若非候选键,每条匹配记录可能位于不同块中,代价可达 (hi+n)⋅(tT+tS)(h_i + n) \cdot (t_T + t_S),其中 nn 是匹配的元组数,可能比线性扫描还慢。

15.3.2 涉及比较的选择​

对 σA≤v(r)\sigma_{A \le v}(r) 或 σA≥v(r)\sigma_{A \ge v}(r):

  • A5 主索引比较查询:若文件按 AA 排序,则对于 ≥v\ge v,先用索引定位第一个满足的元组,再顺序读取直到末尾;对于 ≤v\le v,则从起始位置顺序读到第一个不满足的元组,无需索引。
  • A6 辅助索引比较查询:使用索引找到范围内的每个键,再随机读对应的元组;当结果元组数较多时,代价常常高于线性扫描。此时优化器可能弃用索引。

15.3.3 复杂选择的实现​

对合取 σθ1∧θ2∧⋯∧θn(r)\sigma_{\theta_1 \land \theta_2 \land \dots \land \theta_n}(r):

  • A7 用一个索引的合取选择:选择选择性最好的 θi\theta_i 用索引,其余条件在读到的元组上应用。
  • A8 用组合索引的合取选择:若某几个属性上有组合索引,可以直接用组合索引处理其对应的合取条件。
  • A9 用记录标识符集合的交的合取选择:对每个 θi\theta_i 都通过辅助索引取出满足条件的记录 ID,再对多个 ID 集合求交,最后按剩余 ID 读磁盘。

对析取 σθ1∨θ2∨⋯∨θn(r)\sigma_{\theta_1 \lor \theta_2 \lor \dots \lor \theta_n}(r),只有当每个 θi\theta_i 都能利用索引时才使用 A10 记录标识符集合的并的析取选择;否则退回线性扫描。取反 σ¬θ(r)\sigma_{\neg \theta}(r) 通常直接线性扫描。


15.4 排序​

排序在数据库中出现在多种场景中:显式的 ORDER BY、DISTINCT 的去重、按分组键排序的聚集、归并连接等。若关系能全部装入内存,任何内存排序算法(如快速排序)即可;否则必须使用外排序(external sorting)。

15.4.1 外排序-归并算法​

外排序-归并(external sort-merge)分为两个阶段:

  1. 生成初始归并段(run):反复读取 MM 块进入内存,在内存中排序后写回磁盘,得到若干长度为 MM 的初始 run。若关系有 brb_r 块,则得到 ⌈br/M⌉\lceil b_r / M \rceil 个初始 run。
  2. 多路归并:每一轮把最多 M−1M-1 个 run 合并成一个更大的 run,每个 run 占用一个输入缓冲,另一块作输出缓冲。反复归并直到只剩一个 run。

15.4.2 外排序-归并的代价分析​

设初始 run 数为 ⌈br/M⌉\lceil b_r / M \rceil。每一轮归并把 run 数缩小 M−1M-1 倍,因此归并轮数为:

⌈log⁡M−1(br/M)⌉\lceil \log_{M-1}(b_r / M) \rceil

再加上生成初始 run 的一遍读写,总的遍数(pass):

passes=⌈log⁡M−1(br/M)⌉+1\text{passes} = \lceil \log_{M-1}(b_r/M) \rceil + 1

每一遍都要把整个关系读出并写回一次,所以总的块传输代价:

br⋅(2⌈log⁡M−1(br/M)⌉+1)b_r \cdot (2 \lceil \log_{M-1}(b_r/M) \rceil + 1)

若 MM 相对 brb_r 足够大,通常一遍生成 run + 一遍归并即可完成。若考虑寻道次数,每个 run 的输入/输出块可以采用块缓冲(buffer block)bbb_b,将寻道次数从 2br2 b_r 降到 2⌈br/bb⌉2 \lceil b_r / b_b \rceil,代价:

2⌈br/bb⌉⋅(⌈log⁡⌊M/bb⌋−1(br/M)⌉+1)2 \lceil b_r / b_b \rceil \cdot (\lceil \log_{\lfloor M / b_b \rfloor - 1}(b_r/M) \rceil + 1)

15.5 连接运算​

连接是查询中最昂贵也最复杂的算子。设有关系 rr(brb_r 块、nrn_r 元组)和 ss(bsb_s 块、nsn_s 元组),且连接条件为 θ\theta。

15.5.1 嵌套-循环连接​

对每一个 tr∈rt_r \in r,扫描一遍 ss,输出所有满足 θ\theta 的 (tr,ts)(t_r, t_s):

for each tuple tr in r:
for each tuple ts in s:
if θ(tr, ts): output (tr, ts)

最坏情况下每读一个 rr 的元组都要扫描一遍 ss:

costNLJ=nr⋅bs+br(块传输)\text{cost}_{\text{NLJ}} = n_r \cdot b_s + b_r \quad (\text{块传输})

若整个 ss 能装入内存(bs≤M−2b_s \le M - 2),则只需 br+bsb_r + b_s 块传输。选择较小的关系作为内表总是有利的。

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)

代价:

costBNLJ=br⋅bs+br\text{cost}_{\text{BNLJ}} = b_r \cdot b_s + b_r

若可以为外循环缓冲 M−2M - 2 块,则可进一步降为:

⌈br/(M−2)⌉⋅bs+br\lceil b_r / (M-2) \rceil \cdot b_s + b_r

块嵌套-循环连接是最通用的连接算法之一:对任意连接条件都有效,且不需要索引。

15.5.3 索引嵌套-循环连接​

若在 ss 的连接属性上有索引,则可将内循环替换为索引查找:

for each tuple tr in r:
use index on s to find matching tuples ts
output (tr, ts) for each match

设一次索引查找的平均代价为 cc(B+ 树查找+读取匹配记录),则:

costINLJ=br+nr⋅c\text{cost}_{\text{INLJ}} = b_r + n_r \cdot c

当外表 rr 较小、内表 ss 上又有可用索引时,索引嵌套-循环通常远优于块嵌套-循环。

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
// 相等则输出所有匹配组合,然后推进指针

若两者已经排序,代价为 br+bsb_r + b_s;否则加上排序代价:

costSMJ=br+bs+sort cost(r)+sort cost(s)\text{cost}_{\text{SMJ}} = b_r + b_s + \text{sort cost}(r) + \text{sort cost}(s)

归并连接仅适用于等值连接或自然连接。它对已经排序的输入(如索引扫描输出)尤为高效。

15.5.5 散列-连接​

Hash Join 适用于等值连接。基本思想是使用同一个散列函数 hh 将两个关系按连接属性划分成 nhn_h 个分区,使得只有同一分区的元组才可能匹配:

  1. 建 (build) 阶段:读入较小的关系 ss,按 hh 分区,得到 s0,s1,…,snh−1s_0, s_1, \dots, s_{n_h - 1};
  2. 划 (partition) 阶段:对 rr 用同一 hh 分区,得到 r0,…,rnh−1r_0, \dots, r_{n_h - 1};
  3. 探测 (probe) 阶段:对每一对 (ri,si)(r_i, s_i),把 sis_i 载入内存建散列表,再逐块扫描 rir_i 做探测。

若每个 sis_i 恰好能装入内存,则代价:

costHJ=3(br+bs)\text{cost}_{\text{HJ}} = 3(b_r + b_s)

要满足此条件需要 nh≥⌈bs/M⌉n_h \ge \lceil b_s / M \rceil,一般再乘以避免哈希冲突的裕量因子(如 1.2)。若某个分区仍超出内存,则需要递归划分(recursive partitioning),代价升为:

2(br+bs)⌈log⁡M−1(bs)−1⌉+br+bs2(b_r + b_s) \lceil \log_{M-1}(b_s) - 1 \rceil + b_r + b_s

当内存足够大到 M>bsM > \sqrt{b_s},一次划分即可完成。

混合散列连接(hybrid hash join) 保留第一个分区 s0s_0 常驻内存,可跳过一次写回,进一步降低代价。

15.5.6 复杂连接​

对不等值连接、条件为多个谓词的连接,可组合基本算法:例如把等值条件用散列/归并连接实现,剩余条件在结果上过滤;也可以拆分为等值连接的并集、笛卡尔积后过滤等。

15.5.7 空间数据上的连接​

对空间关系(如包含 RR-树索引的点、多边形集合),连接谓词往往是"相交"、"包含"、"距离小于 dd"等。常用算法包括:

  • 索引嵌套-循环空间连接:对外表每个几何对象用 RR-树查内表;
  • 空间散列连接:使用格网 (grid) 或 Z-order 曲线的哈希分区;
  • RR-树-RR-树同步遍历:两棵 RR-树同时下降,仅在包围盒相交处继续深入。

15.6 其他运算​

15.6.1 去重​

DISTINCT 与集合运算需要去重。两种典型实现:

  • 基于排序:先外排序,然后线性扫描消除相邻重复;
  • 基于散列:将元组散列到多个桶中,再在内存中对每桶去重。

15.6.2 投影​

关系代数的投影 ΠL(r)\Pi_L(r) 是集合语义(去重),SQL 的 SELECT 默认是多重集语义(不去重)。若需去重,可在投影后接一个去重算法;否则只需在读取时丢弃不相关的列。

15.6.3 集合运算​

UNION、INTERSECT、EXCEPT 均可基于排序或散列实现:

  • 排序法:先对两个关系排序,再线性扫描;
  • 散列法:对第一个关系建散列表,再扫描第二个关系判断是否在表中。

UNION ALL 无需去重,代价最低。

15.6.4 外连接​

  • 左外连接 rr ⟕ ss:对 rr 中未匹配的元组补 NULL;
  • 右外连接 rr ⟖ ss:对 ss 中未匹配的元组补 NULL;
  • 全外连接 rr ⟗ ss:两侧都补。

可以在内嵌于任何连接算法的基础上,跟踪每个元组是否匹配来实现。

15.6.5 聚集​

GROUP BY + 聚集函数可以基于排序或散列:

  • 排序法:按分组键排序,然后一次线性扫描累加;
  • 散列法:以分组键为散列码,一边扫描一边在内存中维护累加器。

对可增量计算的聚集(SUM、COUNT、AVG、MIN、MAX),只需存储少量中间状态;对 MEDIAN 等则需保留全部值。


15.7 表达式执行​

对复杂的表达式(多个算子构成的树),执行策略主要有两种:

15.7.1 物化​

物化(materialization) 自底向上执行算子树:先执行叶子上的算子,把结果写到临时关系;再以临时关系为输入执行上层算子。

  • 优点:每个算子实现独立、易于优化;
  • 缺点:中间结果需要额外的磁盘 I/O。若中间结果的块数为 bib_i,则额外代价至少为 ∑bi\sum b_i(写入)加 ∑bi\sum b_i(读取)。

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 交集/并集。
  • 排序若无法一次装入内存,采用外排序-归并,遍数为 ⌈log⁡M−1(br/M)⌉+1\lceil \log_{M-1}(b_r/M) \rceil + 1。
  • 连接算法有嵌套-循环、块嵌套-循环、索引嵌套-循环、归并-连接、散列-连接;理解各自的代价公式与适用条件是选出高效计划的基础。
  • 表达式执行有物化与流水线两种模型,实际系统通常混合使用。
  • 内存数据库时代,缓存感知算法、查询编译与列存已成为高性能查询引擎的标配。

核心公式速查:

算子主要代价(块传输)备注
线性扫描选择brb_r无索引时通用
主索引等值选择hi+1h_i + 1候选键
辅助索引比较查询hi+nh_i + nnn 大则退回扫描
外排序-归并2br(⌈log⁡M−1(br/M)⌉+1)2 b_r (\lceil \log_{M-1}(b_r/M) \rceil + 1)遍数 =⌈log⁡M−1(br/M)⌉+1= \lceil \log_{M-1}(b_r/M) \rceil + 1
嵌套-循环连接nr⋅bs+brn_r \cdot b_s + b_r最通用
块嵌套-循环连接br⋅bs+brb_r \cdot b_s + b_r优化后 ⌈br/(M−2)⌉bs+br\lceil b_r/(M-2)\rceil b_s + b_r
索引嵌套-循环连接br+nr⋅cb_r + n_r \cdot c内表要有索引
归并-连接br+bs+sortb_r + b_s + \text{sort}仅等值连接
散列-连接(无递归)3(br+bs)3(b_r + b_s)M≥bsM \ge \sqrt{b_s}

选择连接算法的经验规则:

  1. 一小一大:优先索引嵌套-循环连接,把小表作为外表;
  2. 都已排序:归并-连接几乎无额外开销;
  3. 等值连接、无排序、有充足内存:散列-连接通常最快;
  4. 无索引且都很大:块嵌套-循环连接作为兜底方案;
  5. 复杂谓词(不等值、函数谓词):拆分成等值部分 + 后置过滤。

理解代价公式与算法适用条件后,就能理解 EXPLAIN 输出中的算子选择,从而在必要时通过创建索引、调整连接顺序或提示(hint)介入优化器决策。