9.1 join 实现:hash/sort/broadcast
第 8 章讲了物理计划的选择,这一节把最常用的 join 展开。join 解决的问题很简单——把两张表按 key 对上——但「对上」的方式有三种,成本差别很大。
join 的本质
A join B on A.k = B.k
要得到结果,必须让「k 相同的行」走到一起。数据分布在多个分区上,所以要么移动数据,要么复制数据:
| 方式 | 做法 |
|---|---|
| 移动大表 | 按 key shuffle,两侧都重分区 |
| 移动小表 | 把小表广播到每个节点 |
| 都不动 | 两侧已按同一分区器分区(协同分区) |
join 的所有实现,都是这三种方式的组合。
广播哈希 join
一侧很小的时候,最优解是把它广播出去:
1. 小表广播到每个 Executor
2. 每个 Executor 把广播表建成哈希表
3. 大表的每个分区本地扫描,逐行查哈希表
| 维度 | 成本 |
|---|---|
| 网络 | 广播小表(一次) |
| 磁盘 | 无(不 shuffle 大表) |
| 内存 | 小表大小的哈希表 |
lab 的 MiniCatalyst.joinStrategy(10, 1000, 1000) 返回 “broadcast”(用例 8):小表 10 ≤ 阈值 1000,选广播。广播 join 没有 shuffle,通常是最快的 join。
它的前提是「小表真的小」:小到能放进每个 Executor 的内存。如果小表其实是 5GB,广播会撑爆 Executor——这时优化器会改选 sort-merge。
排序合并 join
两侧都大时,用排序合并:
1. 两侧都按 join key shuffle 到相同分区
2. 每个分区内部按 key 排序
3. 两个有序流做归并,key 相同的输出
lab 的 MiniCatalyst.joinStrategy(10000, 20000, 1000) 返回 “sortmerge”(用例 9):两边都大,走排序合并。归并的算法就是 ShuffleEngine.sortMerge——两个有序序列线性扫描(4.2 用例 5)。
| 维度 | 成本 |
|---|---|
| 网络 | 两侧全量 shuffle |
| 磁盘 | 排序 spill + shuffle 文件 |
| 内存 | 排序缓冲 |
sort-merge 的优点是「稳」:不要求表能放进内存,数据再大也能跑。缺点是「贵」:两侧都要 shuffle,还要排序。
哈希 join:一个折中
还有一种介于两者之间的实现:
1. 一侧按 key shuffle 到分区
2. 每个分区把这一侧建成哈希表
3. 另一侧流式扫描匹配
| 维度 | 成本 |
|---|---|
| 网络 | 一侧 shuffle |
| 内存 | 一侧分区大小的哈希表 |
| 适用 | 一侧中等大小(放得进单分区内存) |
它比 broadcast 少一次广播、比 sort-merge 少一次排序,但要求「一侧的单个分区能放进内存」。代价模型会在三者之间按估算选择。
三种实现的对照
| 维度 | BroadcastHashJoin | ShuffledHashJoin | SortMergeJoin |
|---|---|---|---|
| 网络 | 广播小表 | 一侧 shuffle | 两侧 shuffle |
| 排序 | 无 | 无 | 有 |
| 内存要求 | 小表 | 一侧分区 | 排序缓冲 |
| 最适合 | 一侧很小 | 一侧中等 | 两侧都大 |
| 倾斜敏感 | 低 | 中(哈希表倾斜) | 高(排序倾斜) |
选择顺序通常是:能 broadcast 就 broadcast,否则 sort-merge,shuffled-hash 视内存而定。
join 与数据倾斜
join 是所有操作里最容易受倾斜影响的:
| 倾斜形态 | 后果 |
|---|---|
| 某个 key 在两侧都很多 | 该分区数据量爆炸 |
| 小表里有热点 key | 广播后每次查都命中同一桶 |
| 大表某 key 极多 | sort-merge 的某个分区特别慢 |
倾斜的解法在第 12 章:加盐打散、拆分热点 key、单独处理。这里先记住一点:join 的慢,常常不是「join 算法选错」,而是「某个 key 的数据太多」。优化器选择再准,也解决不了数据分布问题。
协同分区:消灭 shuffle
如果两张表已经用「同一个分区器、同样的分区数」分区,join 可以完全不要 shuffle:
A 与 B 都按 k 哈希分到 100 个分区
→ 分区 i 的 A 只可能与分区 i 的 B 匹配
→ 每个分区本地 join
这叫协同分区(co-partitioning),把宽依赖改写成窄依赖(2.2)。它适合「同一份数据被反复 join」的场景,代价是要提前按 join key 分区,且分区器要一致。
半连接与反连接
两种特殊 join 只有一侧出现在结果里:
| 类型 | 语义 | 输出 |
|---|---|---|
| 半连接(semi) | 左表里「在右表出现过」的行 | 只有左表的列 |
| 反连接(anti) | 左表里「没在右表出现过」的行 | 只有左表的列 |
它们的实现可以更省:半连接只需要知道「有没有匹配」,不需要真正取右表的列;反连接甚至只需要右表的一列(或者一个布隆过滤器)。优化器常把 WHERE EXISTS / NOT EXISTS 改写成半/反连接,就是因为它们的中间结果比完整 join 小得多。
怎么确认实际用了哪种 join
不要靠猜测,看物理计划:
df.join(dim, "k").explain()
→ BroadcastHashJoin / SortMergeJoin / ShuffledHashJoin
| 计划里看到 | 说明 |
|---|---|
BroadcastHashJoin | 小表被广播,无 shuffle |
SortMergeJoin | 两侧 shuffle + 排序 |
ShuffledHashJoin | 一侧 shuffle + 哈希表 |
SortMergeJoin 外还有 Exchange | 确实发生了 shuffle |
验证比配置更重要:spark.sql.autoBroadcastJoinThreshold 调过之后,是否真的走 broadcast,必须看计划确认。广播阈值设得过大,可能出现「计划是广播,运行却 OOM」的情况——这时该调的是阈值,而不是继续加内存。
三个常见误解
误解一:join 一定慢。 真相:广播 join 几乎没有 shuffle,可以很快;慢的往往是 sort-merge + 倾斜。
误解二:broadcast 越大越好。 真相:广播表要放进每个 Executor 内存,太大就 OOM;优化器有阈值限制。
误解三:join 慢就是算法选错。 真相:先看是否倾斜;倾斜的 join 换哪种算法都慢。
一句话总结本节
join 的本质是让相同 key 的行走到一起,方式有三种:广播小表做哈希查找(无 shuffle,最快)、两侧 shuffle 后哈希匹配(一侧中等大)、两侧 shuffle 后排序归并(两侧都大,最稳)。选择顺序是「能广播就广播,否则 sort-merge」;协同分区可以让 join 完全免 shuffle。join 的慢常常来自数据倾斜而非算法选择——换算法治不了热点 key。
本章实现对照
本节 lab
下载 bd-spark-lab 源码 · 实验运行与版本说明
在 bd-spark-lab/ 中复现 join 策略与归并:
- 源码:
src/catalyst/MiniCatalyst.java(joinStrategy)、src/shuffle/ShuffleEngine.java(sortMerge)与src/catalyst/CatalystSuite.java、src/shuffle/ShuffleSuite.java。 - 运行:
javac -d out $(find src -name '*.java') && java -cp out lab.RunAll。 - 断言:
CatalystSuite用例 8-9 验证「小表广播、大表排序合并」;ShuffleSuite用例 5 验证排序合并的归并过程。 - 整卷 runner 的预期汇总为
TOTAL: 109 passed, 0 failed。
对应本节判断链:按 key 对上 → 移动大表/广播小表/协同分区 → 三种实现按代价选择 → 倾斜另解——lab 的策略选择与归并就是这条链。
继续阅读
探索更多技术文章
浏览归档,发现更多关于系统设计、工具链和工程实践的内容。