数据库查询处理：从 SQL 到可执行的数据流

云帆零售平台每天接收门店、移动端和客服系统提交的查询。同一条“查找华东区近七天已支付订单及其商品名称”的 SQL，看起来只有筛选、连接和排序，执行器却必须回答一连串更具体的问题：从哪里读订单，先筛选哪张表，连接用索引、排序还是哈希，中间结果是否落盘，内存不够时又该怎样继续。

查询处理就是把声明式要求变成一组可以运行的物理操作。SQL 只说明“想得到什么”，执行计划还要说明“按什么顺序、用什么算法、分多少内存、读取哪些页”。一个可靠的计划既要结果正确，也要在当前数据规模和硬件条件下控制 I/O、CPU、内存与网络消耗。

图：解析、翻译、优化与执行依次把 SQL 变成带有访问路径和算法的物理计划。

查询怎样从 SQL 走到执行计划

解析、翻译、优化与执行

查询进入数据库后，通常经历四个相连的环节。

解析器先检查语法和名称。它要确认表、列、函数是否存在，调用者是否有相应权限，类型能否参与比较。对于视图，系统会把普通视图展开成定义它的查询表达式；已经保存结果的物化视图则可以像关系一样直接访问。

翻译器随后生成内部表达式。关系代数树是一种常见表示：叶节点是表或索引扫描，内部节点是选择、投影、连接、分组和排序。下面这条查询的逻辑目标可以写成“先筛订单，再连接订单明细，最后只保留需要的列”：

SELECT o.order_id, i.product_name
FROM orders AS o
JOIN order_items AS i ON i.order_id = o.order_id
WHERE o.region = '华东' AND o.status = '已支付';

逻辑表达式只描述等价运算，还没有决定怎样读数据。例如，选择可以用全表扫描，也可以走（region, status）索引；连接可以用嵌套循环、归并或哈希。把算子与具体算法、索引和输入顺序绑定后，才得到执行原语。一组按依赖关系连接的执行原语构成查询执行计划。

优化器会枚举或搜索若干等价方案，使用统计信息估计每个方案的成本。统计信息包括表页数、行数、不同值数量、直方图、空值比例、索引高度和列之间的相关性。优化器通常寻找估计资源消耗较低的方案，而不是要求用户通过 SQL 写法暗示算法。

执行引擎读取最终计划，驱动各算子产生元组或向量批次，并把根节点输出交给客户端。执行期间还会涉及缓冲池、工作内存、临时文件、并发调度和取消信号。

逻辑计划与物理计划的边界

以“华东区已支付订单”为例，region='华东' 和 status='已支付' 是逻辑谓词；“使用复合 B+ 树索引，从等值前缀开始扫描”是物理选择算法。orders ⋈ order_items 是逻辑连接；“以筛选后的 orders 为外表，对 order_items.order_id 做索引嵌套循环连接”是物理连接算法。

这一区分很重要。两个计划的关系代数可能相同，但物理代价相差几个数量级；两个 SQL 写法也可能不同，优化后却落到同一棵物理算子树。

用一个贯穿全文的订单查询

后文统一使用四张表：

核心任务是：筛出华东区近七天已支付订单，连接明细和商品，按门店汇总销售额，并按销售额降序返回前若干门店。选择、连接、聚合和排序都能在这个查询中找到实际位置。

成本模型怎样比较真实资源

块传输与随机访问

设某个操作传输 $b$ 个存储块，发起 $S$ 次随机访问；传输一个块的平均时间是 $t_T$，从请求发出到首字节到达的平均访问延迟是 $t_S$。一个简化的 I/O 成本是：

机械磁盘上的随机访问包含寻道和旋转等待，$t_S$ 往往远大于 $t_T$。固态存储没有机械寻道，但每个 I/O 请求仍有启动延迟，所以大量离散小读依然可能输给少量连续大读。内存中也有类似层级：主存按缓存行进入 CPU 缓存，缓存未命中的延迟远高于已在缓存中的读取。

块数和随机访问次数必须分开估计。二级索引可能只命中 2,000 行，却把这些行分散在 1,600 个数据页上；顺序扫描可能读取 8,000 页，但只有少量连续访问。哪一个更快，取决于 $t_S/t_T$、缓存命中和并发负载，而不是只看“读取页数”。

模型还可以区分读与写。写入可能需要校验、擦除或额外的持久化协议，单位成本不一定等于读取。单算子成本常暂时不计最终结果写出，因为结果可能直接进入下一个算子；计划级估算则必须为物化边和最终落盘补上写成本。设备部署后应通过顺序传输与随机请求测试校准 $t_T$ 和 $t_S$，不能把某类硬件的常数永久写死。

图：同一计划会同时消耗存储 I/O、CPU、内存和网络，设备特性会改变各项权重。

CPU、内存与网络不能长期忽略

数据已经在缓冲池或 SSD 上时，CPU 可能成为瓶颈。执行器要为每条元组计算表达式、比较键、计算哈希、解析变长字段和调用函数。实用成本模型会设置每元组 CPU 成本、每索引项成本以及每个运算符或函数的成本，再乘以预计处理次数。

工作内存会直接改变算法形态。排序若能把全部输入放入内存，只需一次读取和内存排序；内存不足就要生成有序段并多趟归并。哈希连接的构建端若能常驻内存，只需一次构建和一次探测；装不下时必须分区、写临时文件，甚至递归分区。

分布式执行还要计算网络成本。把一张小维表广播到所有节点，可能比按连接键重分布两张大表便宜；若中间结果行很宽，网络字节数会进一步放大。投影下推能减少行宽，选择下推能减少行数，这两类优化变换常常同时减少网络、内存和 CPU。

响应时间与总资源量不总是一致

并行读取多个设备可能缩短墙钟时间，却消耗更多总 I/O 和 CPU。单个查询在空闲系统中看似更快，高并发时却可能让所有请求都变慢。因此优化器通常以总资源消耗为稳定目标，再结合并行度和限额估计响应时间。

估算也不等于实测。优化时无法准确知道哪些页已经在缓存、运行时会有多少竞争、列值是否存在相关性。统计误差会沿算子树放大：若选择率少估十倍，下游连接的构建端大小、哈希分区数和输出量都可能估错。

选择操作怎样选择访问路径

线性扫描是可靠的基线

线性扫描从文件开头连续读取所有数据页，在内存中检查每条记录。它不要求数据有序，也不要求索引，任何选择谓词都能执行。若关系 $r$ 有 $b_r$ 个页，忽略文件碎片时，完整扫描的成本约为：

若条件是唯一键等值查询，扫描找到目标后可以停止，平均传输约 $b_r/2$ 页；最坏情况下仍要读完整个文件。对于小表或会返回大量行的条件，线性扫描经常是合理方案。

聚簇索引与非聚簇索引

索引提供从搜索键到记录的访问路径。聚簇索引的键顺序与记录的物理顺序接近，匹配同一值或范围的记录集中在连续页中。非聚簇索引的相邻键可能指向分散的数据页，因此回表行数一多，随机访问就会迅速增加。

设 B+ 树高度为 $h_i$，匹配记录占 $b$ 个连续数据页：

• 聚簇索引上的键等值查询，通常需要下降索引并读一个数据页，约为 $(h_i+1)(t_S+t_T)$。
• 聚簇索引上的非唯一等值或范围查询，约为 $$。

实际系统常假定 B+ 树内部节点已经在缓冲池，只为叶节点下降计一次随机 I/O。这个假设能让成本更贴近频繁访问的索引，但叶页和数据页是否命中仍会改变结果。

图：全表扫描连续读取；聚簇索引先定位再连续取页；非聚簇索引可能产生分散回表。

比较谓词与位图式折中

聚簇有序文件处理 A >= v 时，可用索引定位第一个符合条件的元组，再顺序读到文件末尾。处理 A < v 时，直接从文件开头读到边界即可，索引下降未必带来收益。

非聚簇有序索引能扫描范围内的叶项，但取回记录仍可能随机。若命中数量估计不稳定，可以先扫描索引，把命中记录所在的数据页标进位图，再按数据页号顺序读取每个页一次。这样既避免同一页被重复读取，也把随机指针访问转化为更接近物理顺序的页访问。最坏情况只比全表扫描多一些索引与位图工作，最好情况又能跳过大量无关页。

合取、析取与否定

对于 region='华东' AND status='已支付' AND created_at>=...，常见方法有三类：

1. 选成本最低的单个索引先取候选记录，再在内存中检查其余条件。
2. 使用属性顺序匹配的复合索引，一次缩小候选范围。
3. 分别扫描多个索引，求记录标识符集合的交集，再按页号排序回表。

对于 OR 条件，只有每个分支都有可用访问路径时，才适合分别取记录标识符再求并集。只要有一个分支必须全表扫描，通常直接扫描全表并逐行检查整个析取谓词更省事。否定条件要按 SQL 三值逻辑处理：谓词为 UNKNOWN 的空值行既不属于 TRUE，也不能简单当成 FALSE 的补集。

外排序怎样突破工作内存

为什么不能只沿索引读出排序结果

ORDER BY 可以沿有序索引读取，但若索引非聚簇，索引顺序与数据页顺序不同，取完整记录时可能“一行一次随机读”。当结果多、需要的列也多时，物理排序往往更合算。

输入能全部放进内存时，可以直接使用内存排序。输入比工作内存大时，要使用外部归并排序。设待排序关系占 $B$ 个块，排序可用内存为 $M$ 个块。

图：先把每批内存数据排成有序段，再用输入缓冲与输出缓冲逐趟合并。

生成初始有序段

执行器反复读取至多 $M$ 个块，在内存中排序，再把结果写成一个有序段。初始有序段数量为：

这一步完整读取并写回输入，产生约 $2B$ 次块传输。若排序同时承担去重或分组，内存排序阶段就可以先合并相同键，减少后续有序段大小。

多路归并与归并趟数

若每个输入段和输出都只分配一个缓冲块，$M$ 个缓冲块最多支持 $M-1$ 路输入归并。为了减少每次切换有序段的随机访问，可以给每个段分配 $b_b$ 个缓冲块，此时单趟扇入数是：

所需归并趟数为：

每一趟把所有块读一遍并写一遍。若最终归并直接把元组交给下游算子，不把排序结果单独写回磁盘，忽略少数未参与某趟归并的段，块传输数约为：

式中的“$+1$”表示生成初始段时的一次读，生成初始段的写以及中间归并的读写由 $2P$ 部分覆盖；若最终结果也必须物化，还要再加约 $B$ 次写。

初始段生成要分别定位每批输入和输出；中间归并按 $b_b$ 块成批读写。忽略段尾的少量额外定位，随机访问次数可估为：

最后一趟若不落盘，只计读侧定位，所以括号中是 $2P-1$。这条式子也解释了为什么增大每段缓冲能减少随机访问，但可能降低归并扇入。

缓冲分配决定的是另一层成本

增加每段缓冲块数 $b_b$ 会降低随机访问次数，却会降低扇入 $F$，有时因此增加归并趟数。好的参数需要同时观察“每次连续读多长”和“总共需要几趟”，不能只把缓冲做大。

双缓冲还可以让 CPU 在一个缓冲区参与比较和输出时，异步填充或写出另一个缓冲区。它不减少理论块数，但能重叠计算与 I/O，缩短等待。

连接算法怎样匹配数据形态

先认识内外关系

连接把两边满足条件的元组配成结果。嵌套循环中，外关系控制外层循环，内关系会被反复扫描或探测。哈希连接中，构建端用来建立哈希表，探测端逐条查找匹配。角色选择会直接改变 I/O 与内存。

图：条件类型、输入规模、索引、有序性和工作内存共同决定连接算法。

元组嵌套循环与块嵌套循环

最直接的元组嵌套循环会比较每一对元组，适用于任意连接条件，但代价高。若 $r$ 为外关系，最坏情况下需要：

次块传输，其中 $n_r$ 是外关系元组数，$b_r,b_s$ 是两边块数。

块嵌套循环一次把外关系的一批页放进内存，再完整扫描内关系。内存共有 $M$ 个块时，通常留一块给内关系输入、一块给输出，外关系每批可装 $M-2$ 块：

当两边都放不进内存时，应让块数较小的一边做外关系，以减少内表扫描次数。若某一边能完整常驻内存，则把它放在内侧，只需各读一遍。连接键是内关系的键时，一旦找到匹配，内层也可提前停止。

图：块嵌套循环用一批外页摊薄内表扫描；索引嵌套循环为每个外元组探测内表索引。

索引嵌套循环

如果内关系的连接属性有索引，可以把反复全表扫描改成索引查找。设每个外元组在内关系上的一次选择平均成本为 $c$：

它适合外表经过选择后很小、内表索引命中很少的情况。若外表很大，或者非聚簇索引每次命中很多分散记录，$n_r c$ 会非常昂贵。即使两边都有索引，一般也让元组数较少的一边做外表。

归并连接

等值连接或自然连接的两边若已按连接键排序，可以各维护一个游标同步前进。键值不相等时推进较小的一边；键值相等时收集一侧的同键组，与另一侧同键组配对。若同键组太大无法放入内存，可对这个组局部使用块嵌套循环或临时文件。

已排序时只需顺序读取两边一次：

若输入未排序，必须加上两边外排序成本。归并连接可以在两个有序输入上同时流水执行，并把结果立刻交给上游。混合归并连接还可把一边的有序数据与另一边二级索引的叶项合并，先得到记录地址，再按地址排序后批量取记录，以减少随机回表。

哈希连接

哈希连接适合自然连接和等值连接。它用连接键上的哈希函数把两边划成对应分区；只有落入同一编号分区的元组才可能匹配。每次把构建端分区装入内存建立第二层哈希表，再用对应探测端分区查找，并检查真实键值以排除哈希冲突。

图：两边按同一分区函数落桶，构建端分区进入内存后再由探测端查找匹配。

构建端应尽量小。若构建端有 $b_s$ 个块且每个分区及其哈希索引都要装入 $M$ 个内存块，分区数至少接近 $\lceil b_s/M\rceil$。当分区数大到一次无法保留所有输出缓冲时，要换哈希函数递归分区，直到每个构建分区能装入内存。粗略地说，$M>\sqrt{b_s}$ 时通常能避免递归分区。

不需要递归、也没有溢出时，普通哈希连接会读写两边完成分区，再读两边完成构建和探测，块传输约为：

$n_h$ 是分区数量，$4n_h$ 来自各分区末尾可能存在的未满块，通常相对较小。若构建端完整放进内存，不必生成磁盘分区，成本可降到 $b_r+b_s$。

哈希倾斜、溢出与混合哈希

同一个连接键出现大量重复值，或哈希函数分布不均，会让某些构建分区大于内存。可以预留约一定比例的安全余量，增加分区数；运行时发现溢出后，对溢出分区使用新的哈希函数继续划分，并对对应探测分区做同样划分。也可以一开始生成较多小分区，再按实际大小组合出能装入内存的分区，避免构建阶段突然溢出。若一个热点键本身就超出内存，继续哈希没有意义，应对该热点分区改用块嵌套循环等算法。

混合哈希连接在分区期间把一个构建分区及其哈希表留在内存，不写临时文件。探测端落入对应分区的元组立即探测并输出；其余分区照常落盘。构建端只比内存略大时，这种方法能省掉内存驻留分区的一次写和一次读。

复杂条件与空间连接

连接条件是多个 AND 时，可以选一个可用的等值条件执行高效连接，再对产生的候选对检查其余条件。OR 条件可以分别计算各分支连接后求并集并去重。普通嵌套循环能处理任意谓词；归并和哈希要求可排序或可等值分区的连接键。

空间相交、包含或最近邻没有简单的一维排序，也无法保证相交对象哈希到同一桶。此时普通归并与哈希不适用，但可以让外表逐对象探测内表上的 R 树、k-d 树等空间索引，形成索引嵌套循环连接。

其他关系算子怎样复用排序与哈希

去重与投影

去重可以先按整行排序，让重复元组相邻，只保留一份。生成初始有序段时就能局部去重，归并时继续消除跨段重复。也可以按整行哈希分区，每个分区建立内存哈希集合，已存在的元组不再插入。

普通投影先对每条输入元组计算并保留目标列，再按 SQL 语义决定是否去重。若投影列包含输入关系的键，结果不可能因为投影而重复，可以省掉去重。SQL 默认保留重复值，只有 DISTINCT 或集合运算的语义要求才执行去重。

并、交与差

两边按同一键序排序后，可以同步扫描完成集合运算：并集遇到相同元组只输出一次，交集只输出两边都出现的元组，差集只输出左边独有的元组。输入已经排序时，扫描成本是 $b_r+b_s$。

哈希方法使用同一个函数分区两边。对每对对应分区：

• 并集：先把左分区放入哈希集合，再插入右分区中尚不存在的元组。
• 交集：建立左分区哈希集合，只输出右分区中能探测到的元组。
• 差集：建立左分区哈希集合，右分区命中时删除，最后输出剩余元组。

外连接

左外连接可以先计算普通连接，再找出左表没有参与连接的元组，为右表列补空值后追加。不过这样要保存中间关系并执行投影和差集。

更直接的方法是改造连接算法。嵌套循环为每个外元组维护“是否匹配”标志，扫描完内表仍未匹配就输出补空值行。归并连接在键序推进时能立刻识别没有对应键的行。哈希连接可以给构建端记录匹配标志，并按左、右或全外连接的方向补出未匹配行。

分组聚合

分组聚合与去重使用同一骨架，只是每个键不再保留“是否出现”，而是保存聚合状态。SUM、MIN、MAX、COUNT 可以边读边更新；AVG 保存 SUM 和 COUNT，最后相除。

图：排序与哈希是多种关系算子的共同基础，差别在于同键记录的状态更新规则。

若所有分组状态能放进内存，哈希聚合只需读输入一次，约 $b_r$ 个块传输；装不下时再按分组键分区或使用外排序。聚合状态的大小取决于分组数，而不是输入行数。十亿行若只有几百个门店分组，状态仍可能很小；几乎每行一个不同键时，状态会接近输入规模。

表达式执行怎样组织物化与流水线

物化执行

一棵多算子树可以自底向上逐个执行：先把选择结果写成临时关系，再读它做连接，把连接结果再次写出，最后读入做聚合和排序。每个中间结果都真实保存下来，这叫物化执行。

物化容易调度，也能让一个中间结果被多个父算子复用；阻塞算子还可能必须先收齐输入。代价是临时关系的写与读。若中间结果 $q$ 有 $n_q$ 条记录，每块容纳 $f_q$ 条，写出块数约为：

输出缓冲有 $b_b$ 块时，顺序批量写出的随机访问次数可估为 $\lceil b_q/b_b\rceil$。双缓冲允许一个缓冲写盘时继续填充另一个缓冲。

流水线执行

如果订单选择每产生一行就交给连接，连接每产生一行就交给投影或聚合，中间元组不需要完整落盘，这就是流水线。它减少临时文件 I/O，也能更早返回首批结果。

流水线有两种驱动方式：

• 需求驱动：根算子向子算子请求下一条结果，数据从上向下发出请求、再从下向上返回，也称拉取模型。
• 生产者驱动：下游算子主动生成数据并写入缓冲，上游算子并发消费，也称推送模型。缓冲满时生产者等待，缓冲空时消费者等待。

推送模型减少逐元组函数调用，也适合并行与持续数据流；拉取模型控制流清楚，算子容易组合，是经典实现。

迭代器模型

需求驱动算子通常实现三个接口：

open()   初始化状态，并打开子算子
next()   返回下一条结果；没有结果时返回结束标记
close()  释放缓冲、游标和临时资源

线性扫描迭代器在状态中记录读到的页和槽位，下一次 next() 从断点继续。选择迭代器反复调用子算子的 next()，直到找到满足谓词的元组。索引嵌套循环迭代器保存当前外元组与内表索引游标。归并连接迭代器保存两边游标和当前同键组。

阻塞算子与流水线阶段

并非所有边都能直接流水。完整排序必须先看完输入，才能保证第一个输出是最小值；普通分区哈希连接要先完成构建端分区和哈希表构建，才可稳定探测。这些阻塞边会把计划切成多个流水线阶段。

一个大算子也可以拆成子阶段。外排序的初始段生成可以接收上游流水输入，最终归并可以向下游流水输出，但两者之间必须等所有初始段生成完。哈希连接的两个分区子阶段可以接收输入流，构建—探测子阶段可以向聚合输出流，但分区与构建之间是阻塞边。若构建端完整驻留内存，哈希连接可以在构建完成后对探测端完全流水。

双输入都要立即响应时，可维护两边的内存哈希索引。任一边到来一条记录，就插入自身索引并探测另一边。这种双流水哈希连接要求控制内存；内存满后，新到记录可划入磁盘分区，但在落盘前仍先探测驻留分区，最后再补算磁盘分区之间的连接。

持续数据流没有“读完全部输入”

门店设备持续上报订单事件时，输入没有固定结尾，查询也会长期运行。此类连续查询必须尽量使用生产者驱动的流水算法，让新事件到达后就推动筛选、连接和聚合，不能等待“全表读完”。

聚合通常要配合时间窗口。例如滚动方式为每分钟一个互不重叠的窗口时，执行器按窗口分别维护门店销售额状态。若事件严格按时间戳到达，看到下一窗口的事件就能结束上一窗口；若事件可能乱序，数据流还要携带一个进度标记，声明未来不会再出现早于某个时间的事件。只有窗口结束时间不大于该进度标记时，系统才能安全输出最终聚合并释放窗口状态。

迟到容忍度也是内存参数。允许事件晚到越久，必须同时保留的窗口状态越多，结果延迟也越高；过早关闭窗口则可能漏算合法的迟到事件。

内存中的查询处理仍要管理层级

从工作内存到 CPU 缓存

数据进入内存后，磁盘 I/O 不再是唯一瓶颈。CPU 缓存远小于主存但快得多，数据以缓存行为单位传输。算法若频繁随机访问超过缓存容量的哈希表，会产生大量缓存未命中，处理器等待主存的时间可能超过实际计算。

内存排序可以把输入切成能放进末级缓存的小段，在缓存中排序，再顺序归并。内存哈希连接也可以继续按连接键分成缓存大小的分区，使构建分区及其哈希索引尽量驻留缓存。元组内经常一起访问的列若连续布局，一次缓存行读取能带来更多有用数据。

工作内存必须在并发算子间分配

计划里多个算子可能同时运行。给单个排序 $M$ 个块并不代表它运行时一定能独占这些内存；同一流水线中的哈希连接、聚合和排序会竞争预算，高并发查询之间也会竞争。

执行器通常为每个阻塞算子设工作内存上限，并在运行时监视实际占用。哈希表接近上限时增加分区并溢写；排序达到上限时结束当前内存段；哈希聚合装不下全部分组时切换到分区聚合。内存分配错误会产生两种坏结果：过少导致不必要的多趟 I/O，过多导致系统换页或同时运行的查询数下降。

哈希溢出的处理必须保持两边分区规则一致。构建端分区 $s_i$ 用新函数拆成 $s_{i,0},s_{i,1},\ldots$ 后，对应探测端 也要用同一函数拆分，否则可能匹配的元组会被放到不同子分区，结果不再正确。热点键过大时，继续拆分仍会落在同一桶，应识别热点并使用专门路径。

编译执行与列式批处理

解释执行会为每条元组反复调用通用函数、查询列偏移和分派算子。把物理计划编译成机器码或中间字节码，可以把列偏移固化为常量，把相邻算子融合到同一循环，减少函数调用和分支。

列式存储只读取查询涉及的列，适合订单分析中“扫描大量行但只用区域、门店和金额”的场景。连续同类型值便于压缩，也便于使用向量指令一次比较或聚合多个值。若查询需要大部分列并频繁重建整行，行式布局可能更合适。

一套可落地的算法选择顺序

面对核心订单查询，可以按下面的顺序做判断：

1. 先估计每次选择会留下多少行、多少页，以及行宽会缩到多少。
2. 检查小结果能否驱动索引嵌套循环；若不能，再比较已有序输入的归并连接和等值条件的哈希连接。
3. 根据实际工作内存判断排序趟数、哈希分区和聚合状态是否会溢出。
4. 标出阻塞边，把能连续传递的选择、投影、连接探测和增量聚合放进同一流水线阶段。
5. 在 SSD、内存和分布式环境中重新设置 CPU、随机访问、网络字节与并行度权重。
6. 用运行时行数和溢写指标检查估计偏差，必要时更新统计信息或让执行器动态切换策略。