6.2 Sort-merge join 与 spill
Sort-merge join 是 hash join 的对照面。它不在内存里建表,而是把两张表都按连接键排好序,然后像拉链一样并行推进:键小的一侧前进,键相等就输出,键大了就等另一侧追上来。它把内存压力换成了排序成本,而排序在数据超出内存时必须落盘。
本节沿一条判断链走:现象是 hash join 因内存不足退化、或输入本来就有序,机制是排序加归并,账本是 26.5754 秒排序、13 个 run 与 2400MB IO,判据是内存紧张或输入有序时选 sort-merge。
三步:排序、归并、输出
| 步骤 | 输入 | 动作 | 成本形态 |
|---|---|---|---|
| 排序 | 两张表各自全量 | 按连接键做外部排序 | n log2 n 次比较,可能溢写 |
| 归并 | 两个有序流 | 双指针推进、比对键 | 线性扫描 |
| 输出 | 相等的键组 | 笛卡尔拼接同键行 | 由匹配率决定 |
排序是唯一的重成本。归并本身只是顺序读两个流,成本与行数成正比且常数很小;输出成本由匹配率决定,和 hash join 一样。因此判断 sort-merge 贵不贵,等价于判断「这两张表排序要花多少」。
排序成本是 n log2 n,不是 n
lab 用例 49 的场景是两表各 1 亿行、每次比较 5ns。排序的比较次数不是行数,而是行数乘以 log2 行数:
// 用例 49:两表排序成本(秒)
double comparisons = 100_000_000L * (Math.log(100_000_000L) / Math.log(2));
// 1e8 × 26.5754 ≈ 2,657,540,000 次/表
double seconds = 2.0 * comparisons * 5L / 1_000_000_000.0;
// 2 × 2.65754e9 × 5ns = 26.5754s
| 量 | 取值 | 来源 |
|---|---|---|
| 每表行数 | 100,000,000 | 统一场景 |
| log2(1 亿) | 26.5754 | 公式推导 |
| 比较次数/表 | 2,657,540,000 | 公式推导 |
| 每次比较 | 5ns | 用例 49 参数 |
| 两表排序成本 | 26.5754 秒 | 用例 49 |
26.5754 秒只是排序,还没算归并和输出。这个数字说明了一件事:sort-merge 的成本下限由「表有多大」和「比较多贵」共同决定,1 亿行量级下它是秒级开销,而不是毫秒级的常数。
内存不足:800MB 切成 13 个 run
内存排序要求其工作集可放进内存。输入超过可用预算时,外部排序把数据切成若干段,每段在内存内排好写回磁盘,这叫一个 run。lab 用例 50 的口径是向上取整:
run 数 = ceil(数据量 ÷ 内存上限)
= ceil(800MB ÷ 64MB)
= ceil(12.5)
= 13 个 run
| 量 | 取值 | 说明 |
|---|---|---|
| 数据量 | 800MB | 待排序数据 |
| 内存上限 | 64MB | 单个排序缓冲区 |
| 整除结果 | 12.5 | 公式推导 |
| run 数 | 13 | 用例 50,向上取整 |
13 而不是 12,是因为最后半个 run 也要落盘。前 12 个 run 各 64MB,第 13 个只剩 32MB(公式推导:800 − 12×64)。向上取整这个细节看着小,但它决定了归并的扇入数,也决定了归并阶段要同时打开多少个文件。
外部排序的 3 倍 IO:2400MB
溢写不是免费的,数据要被写出去、再读回来。lab 用例 51 把外部排序的 IO 拆成三段:
总 IO = 写 run + 归并读 + 归并写
= 800MB + 800MB + 800MB
= 2400MB
| 阶段 | IO 量 | 方向 |
|---|---|---|
| 生成 run | 800MB | 写盘 |
| 归并读取 | 800MB | 读盘 |
| 归并输出 | 800MB | 写盘 |
| 合计 | 2400MB | 用例 51 |
2400MB 是数据量的 3 倍。这个倍数是最理想的单趟归并:如果 run 数太多、一趟归并扇入不够,还要多趟归并,IO 会继续翻倍。所以控制 run 数(加大排序缓冲区、减少溢写)比优化归并算法更有效。
已排序输入:成本为 0
sort-merge 真正的杀手锏在输入已经有序的时候。lab 用例 52 直接断言这个场景的额外排序成本为 0:
| 输入状态 | 额外排序成本 | 归并成本 | 适用性 |
|---|---|---|---|
| 已按连接键有序 | 0(用例 52) | 线性扫描 | 最优 |
| 未排序、能入内存 | 内存排序,无 IO | 线性扫描 | 可接受 |
| 未排序、超出内存 | 26.5754 秒级 + 2400MB IO(用例 49、51) | 线性扫描 | 代价高 |
「已排序」不是运气,而是可以设计的:如果上游算子本来就按连接键分区并排序(比如同一列上的聚簇存储、或前一个算子输出了有序流),sort-merge 就退化成一次线性归并,比 hash join 还省——它连 12MB 的哈希表都不用建。
归并阶段为什么便宜
归并是双指针顺序推进:两个流各持一个当前行,比较键,小的一侧前进一行,相等就输出同键组。它不需要随机访存,读的是两个顺序流,缓存友好。
| 阶段 | 访存模式 | 相对成本 |
|---|---|---|
| 排序 | 随机(比较与交换) | 高,n log2 n |
| 归并 | 顺序(双指针) | 低,线性 |
| hash 探测 | 随机(查槽) | 中,每行一次 |
归并的低成本来自顺序访问:这正是 hash join 的 probe 阶段最贵的地方。两者在「匹配」这一步上的差距,本质是顺序流与随机查表的差距。
与 hash join 的取舍
两种算法没有绝对优劣,只有适用条件:
| 维度 | hash join | sort-merge join |
|---|---|---|
| 内存 | 需容纳 build 侧哈希表 | 排序缓冲 + 常量归并状态 |
| 主要成本 | probe 随机访存 | 排序 n log2 n |
| 输入已有序 | 无额外收益 | 排序成本为 0 |
| 非等值连接 | 不适用 | 可退化为范围归并 |
| 输出顺序 | 无序 | 按连接键有序 |
| 溢出行为 | 分区哈希,多一轮 IO | 外部排序,3 倍 IO |
输出有序是一个常被忽略的收益:如果连接结果后面还要按连接键聚合或排序,sort-merge 的输出现成就是有序的,能省掉下游一次排序。hash join 的输出则必须再排一遍。
判据:什么时候选 sort-merge
| 条件 | 结论 |
|---|---|
| 两表都远大于内存 | 优先 sort-merge,避免分区哈希的额外 IO |
| 输入已按连接键有序 | 首选 sort-merge,排序成本为 0 |
| 需要范围或非等值连接 | sort-merge 可退化支持 |
| 下游需要按连接键有序 | sort-merge 顺带满足 |
| 小表可入内存、追求低延迟 | 仍选 hash join |
判据可以压成一句:谁能把成本压到「线性扫描」,就选谁。输入有序时 sort-merge 做到了;build 侧能入内存时 hash join 做到了。两者都做不到时,比的是谁的溢写更便宜——通常排序的 3 倍 IO 比分区哈希的两轮 IO 更可预测。
run 的扇入与多趟归并
13 个 run 不可能一次全读进内存归并,引擎要限制同时打开的归并路数(扇入)。扇入不够时,归并要分多趟做:
| run 数 | 扇入 | 归并趟数 | IO 特征 |
|---|---|---|---|
| 13 | 13 | 1 | 3 倍数据量(用例 51) |
| 13 | 4 | 2 | 前一趟再读写一遍(公式推导) |
| 13 | 2 | 4 | 接近翻倍再翻倍(公式推导) |
每多一趟归并,数据就要多读写一轮。用例 51 的 2400MB 对应单趟归并:写 run 800MB、归并读 800MB、归并写 800MB。如果扇入只能到 4,13 个 run 得分两趟,IO 就不再是 3 倍。
控制 run 数是控制 IO 的唯一杠杆:加大排序缓冲区,run 数下降,归并趟数下降,IO 倍数才可能维持在 3 倍附近。调归并算法本身收益有限,因为它已经是线性扫描。
排序键与比较成本
用例 49 里每次比较 5ns 是模型参数,真实成本取决于键的类型与比较函数:
| 键类型 | 相对比较成本 | 原因 |
|---|---|---|
| 定长整数 | 最低 | 一条比较指令即可 |
| 定长多列 | 逐列累加 | 先比第一列,相等再比下一列 |
| 变长字符串 | 较高 | 长度检查、前缀比较、可能越界读 |
5ns 是定长整数键的量级。换成变长字符串,比较次数不变,但 26.5754 秒会被实际比较成本放大。宽键场景下,先把键规范化成定长整数(比如字典编码),往往比换算法更有效。
排序键与连接键不一致时还要多付一次「取键」的成本:排序按连接键比较,但输出需要原始行,中间要么存行指针、要么存整行,前者多一次随机回表,后者撑大排序数据量。
分布式 sort-merge 的分区
分布式执行时,sort-merge 通常先按连接键分区,再在各分区内排序归并,保证两侧同键落到同一分区:
| 分区方式 | 优点 | 缺点 |
|---|---|---|
| 范围分区 | 分区内近似有序,输出可拼接 | 热点键导致倾斜 |
| 哈希分区 | 分布均匀 | 分区内仍需完整排序 |
范围分区能把「分区」和「排序」两件事合成一件:按范围切完,分区之间天然有序,只需分区内排序。代价是倾斜——某个范围里键特别密,单个分区就会变成长尾。哈希分区均匀,但省不掉分区内的排序。
工程上常见的折中是先哈希分区保证均匀,再在分区内排序;如果数据本身有聚簇性质,则优先范围分区,并对热点范围单独拆分。
归并中的重复组与缓冲
外部排序先形成有序 run,多路归并可以逐批交给 join。两个输入都出现重复键时,需要对同键组进行笛卡尔积式的配对;一侧可缓冲的同键组很大时,还要按实现重读或 spill。总 I/O 受多路归并扇入、额外归并趟数和是否物化最终 run 影响。普通等号不会让两个 NULL 匹配,NULL-safe 连接需用相应比较语义。
三个常见误解
误解一:sort-merge join 只是排个序再连,排序是小开销。 真相:两表各 1 亿行、每次比较 5ns 时排序要 26.5754 秒,是整个连接的主要成本。
误解二:内存不够就多给点内存,溢出只是慢一点。 真相:800MB 数据在 64MB 内存下切成 13 个 run,外部排序的总 IO 是数据量的 3 倍即 2400MB。
误解三:既然 hash join 更快,sort-merge 没有存在价值。 真相:输入已按连接键有序时排序成本为 0,且 sort-merge 内存只需常量、天然支持范围连接并输出有序结果。
一句话总结本节
Sort-merge join 用排序换内存:两表各 1 亿行、每次比较 5ns 时排序要 26.5754 秒;800MB 数据在 64MB 内存下切成 13 个 run,外部排序写 run、归并读、归并写共 2400MB,是数据量的 3 倍。它的结构性优势是输入已有序时排序成本为 0,此时只剩一次线性归并;内存紧张、需要范围连接或要求输出有序时,它比 hash join 更稳。
外部排序和归并连接
内存预算不足时形成 runs。归并遇到大同键组还需要独立缓冲或溢写。
flowchart LR
A[左右两份未排序输入] --> B[按各自预算切批排序]
B --> C[(左右两组有序 runs)]
C --> D[多路归并获得两个有序流]
D --> E[比较当前连接键]
E -->|同键| F[缓冲或 spill 重复组并配对]
E -->|不同键| G[推进较小键一侧]
F --> H[输出结果]
G --> E
本节 lab
在 bd-engine-lab 中验证排序连接的成本与溢出账本:
- 源码:
src/operator/Operator.java与src/operator/OperatorSuite.java。 - 运行:
cd bd-engine-lab && mkdir -p out && javac -d out $(find src -name '*.java') && java -cp out lab.RunAll。 - 断言:用例 49 验证「两表各 1 亿行、每次比较 5ns,排序成本 26.5754 秒」;用例 50 验证「800MB 数据、64MB 内存切 13 个 spill run」;用例 51 验证「外部排序总 IO 为 800MB × 3 = 2400MB」;用例 52 验证「输入已有序时额外排序成本为 0」。
- 整卷 runner 的预期汇总为
TOTAL: 116 passed, 0 failed。
对应本节判断链:hash join 因 build 侧放不下而退化 → 换成排序加归并 → 算出 26.5754 秒排序、13 个 run、2400MB IO → 输入已有序或内存紧张时选 sort-merge,否则仍用 hash join。
继续阅读
探索更多技术文章
浏览归档,发现更多关于系统设计、工具链和工程实践的内容。