《大规模分布式计算深入解析》6.2 Sort-merge join 与 spill

Sort-merge join 把两表排序后归并。各 1 亿行、每次比较 5ns 时排序要 26.5754 秒;800MB 数据在 64MB 内存下切 13 个 run,外部排序写读共 2400MB。输入已有序时排序成本为 0,这是它相对 hash join 的结构性优势。

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 量方向
生成 run800MB写盘
归并读取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 joinsort-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 特征
131313 倍数据量(用例 51)
1342前一趟再读写一遍(公式推导)
1324接近翻倍再翻倍(公式推导)

每多一趟归并,数据就要多读写一轮。用例 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

下载卷五 Java 8 实验 · 实验运行与版本说明

在 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。

继续阅读

探索更多技术文章

浏览归档,发现更多关于系统设计、工具链和工程实践的内容。

全部文章 返回首页

「books」更多文章

  1. 《大规模分布式计算深入解析》15.3 落地:从 Neo4j 到自研图引擎
  2. 《大规模分布式计算深入解析·图计算与图数据库内核》 · 目录与学习路径(45 篇)
  3. 《大规模分布式计算深入解析》15.2 十一卷主线:从切分到图