《大规模分布式计算深入解析》9.1 join 实现:hash/sort/broadcast

join 的本质是「按 key 把两侧数据对上」,对上的方式有三种:广播小表做哈希查找、两侧 shuffle 后哈希匹配、shuffle 后排序归并。本节比较三种实现的网络、内存与磁盘成本,给出选择依据,并说明为什么「小表能不能广播」往往决定 join 快不快。

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 少一次排序,但要求「一侧的单个分区能放进内存」。代价模型会在三者之间按估算选择。

三种实现的对照

维度BroadcastHashJoinShuffledHashJoinSortMergeJoin
网络广播小表一侧 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。

本章实现对照

Spark SQL Join 与 AQE

本节 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 的策略选择与归并就是这条链。

继续阅读

探索更多技术文章

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

全部文章 返回首页

「books」更多文章

  1. 《大规模分布式计算深入解析·向量数据库与 AI 检索内核》 · 目录与学习路径(45 篇)
  2. 《大规模分布式计算深入解析》15.3 自研向量引擎:可执行骨架与工程缺口
  3. 《大规模分布式计算深入解析》14.1 Milvus:组件架构、段管理与检索链路