《大规模分布式计算深入解析》6.3 Broadcast、嵌套循环与 runtime filter

广播、嵌套循环与 runtime filter 处理不对称或非等值连接。10MB 小表广播到 100 个 executor 是 1000MB 流量;runtime filter 用 build 键集合剪 probe,选择率 5% 时从 500 万降到 25 万,省 95%。

6.3 Broadcast、嵌套循环与 runtime filter

6.1 与 6.2 处理的都是「两侧都大」的等值连接。这一节处理另外两种现实情况:两侧极不对称,或者干脆没有等值键。前者的答案是广播,后者是嵌套循环,而 runtime filter 是在两者的基础上再加的一层剪枝——它把 build 阶段得到的键集合反过来喂给 probe 阶段。

本节沿一条判断链走:现象是 shuffle 连接把网络打满、或非等值连接只能硬算,机制是广播的流量模型与 runtime filter 的剪枝,账本是 1000MB 广播流量与 95% 的探测削减,判据是小表阈值与非等值场景。

三种策略的分工

策略前提主要成本网络流量
广播 hash join一侧小到可复制到每个 executor广播流量 + 本地建表表大小 × executor 数
shuffle hash join两侧都大,需按键重分布shuffle 两表两表数据量
嵌套循环无等值键、或一侧极小笛卡尔比较次数视是否广播而定

广播用网络换本地内存:每个 executor 都拿到一份完整小表,local join 不需要 shuffle 大表。判断它划不划算,只取决于一个乘法——表多大、要复制多少份。

广播的账:表大小 × executor 数

lab 用例 53 是最小场景:10MB 小表广播到 100 个 executor。

// 用例 53:广播总流量
long mb = Operator.broadcastMB(10L, 100);
// 10MB × 100 = 1000MB
量取值说明
小表大小10MB广播侧
executor 数100接收方数量
广播流量1000MB用例 53

10MB 听起来很小,乘上 100 就变成 1GB 流量。这个乘法是广播与 shuffle 的分水岭:shuffle 只搬一次大表(按分区打散),广播要把小表搬 executor 数那么多次。当 executor 数上升,广播的成本线性上升,而 shuffle 的成本基本不变。

表大小executor 数广播流量结论
1MB100100MB(公式推导)划算
10MB1001000MB(用例 53)临界
50MB1005000MB(公式推导)偏贵,考虑 shuffle
100MB10010000MB(公式推导)不可接受

阈值不是固定数字,而是「表大小 × 集群规模」。同一个 10MB 表,在 10 个 executor 上是 100MB,在 1000 个 executor 上就是 10GB。所以配置里的广播阈值必须结合集群规模理解,不能照抄。

嵌套循环:没有等值键时的兜底

当连接条件不是等值,而是范围或不等式,哈希就用不上了。最朴素的做法是对 probe 侧每一行扫描 build 侧整张表:

算法比较次数说明
嵌套循环5,000,000 × 500,000 = 2.5×10¹²(公式推导)probe 行 × build 行
hash join5,000,000 次探测(用例 46)仅等值

嵌套循环并非一无是处。它在三种情况下仍是最优解:一侧只有几行(比较次数退化为线性)、有 LIMIT 可以提前短路、或者连接条件根本无法哈希。真正的问题是把嵌套循环用在大表之间——那会是万亿级的比较。

runtime filter:build 之后反过来剪 probe

runtime filter 的思路是把 build 阶段的产物再用一次。build 建哈希表时顺便记下键的集合(或布隆过滤器、或最小最大值区间),然后拿这个集合去过滤 probe 侧:

build 完成 → 得到键集合 S(或布隆过滤器)
probe 每一行 → 先用 S 判断「这个键可能匹配吗」
              → 不可能则直接丢弃,不进入哈希探测

lab 用例 54 给出效果:probe 侧 500 万行、选择率 5%,过滤后只剩 25 万行:

过滤后行数 = 5,000,000 × 5% = 250,000 行
削减比例 = 1 - 5% = 95%
场景probe 行数探测次数probe 成本(按 20ns/次)
无 runtime filter5,000,0005,000,000100ms(用例 47)
有 runtime filter250,000(用例 54)250,0005ms(公式推导)

省掉的是 95% 的探测,而过滤本身几乎不花钱:布隆过滤器一次查询是几次内存访问,比一次哈希探测还便宜。这就是 runtime filter 的杠杆——用极小的过滤成本,砍掉绝大部分随机访存。

runtime filter 的两种形态

形态构建成本误判适用
布隆过滤器低,按位设置有假阳性、无假阴性键多、内存紧
IN 列表 / 区间中,需存键或边界无假阳性(精确)键少、选择率极低

两种形态都保证「不会漏掉真正匹配的行」,区别只在误判方向:布隆过滤器会把少量不匹配的行放进来(假阳性),但绝不会把匹配的行挡掉(假阴性)。这个性质是 runtime filter 能安全使用的前提——它可以少过滤,但不能错过滤。

广播 + runtime filter 的组合

广播与 runtime filter 经常一起出现:小表广播到每个 executor 后,每个 executor 先在本地建表,再向 probe 流下发一个本地过滤器。这样每个 executor 的 probe 输入在进入哈希探测前就被剪了一遍。

组合网络本地计算
仅广播表 × executor 数全量 probe 探测
广播 + runtime filter表 × executor 数 + 过滤器探测减少 95%

过滤器本身也要传播,但它的体积远小于小表:一个布隆过滤器通常只有几 MB 甚至更小。用一点额外流量换 95% 的探测削减,在 probe 侧远大于 build 侧时几乎总是划算的。

判据:三种策略怎么选

条件选择
小表 × executor 数在可接受流量内广播 hash join
两侧都大、等值连接shuffle hash join
非等值连接、一侧极小嵌套循环
build 侧选择率高、probe 侧大叠加 runtime filter
小表广播后流量超过大表 shuffle改用 shuffle

判据的第一层是连接类型:等值才有哈希的资格,非等值只能嵌套循环或排序归并。第二层是流量账:广播划不划算,算的是「表大小 × executor 数」与「大表 shuffle 一次」谁更小。runtime filter 则是第三层,在前两层确定之后再加的免费午餐——只要 build 侧能产出键集合,就该下发。

广播的实现与生命周期

广播不是一次简单复制。它包含分发、本地建表与缓存三个阶段,每个阶段都有成本:

阶段动作成本形态
分发小表传到每个 executor表大小 × 接收方数量
本地建表每个 executor 各建一份哈希表本地内存与插入开销
缓存同一小表在多个查询间复用省掉重复分发

缓存能把广播流量摊薄:同一张小表被多个查询广播时,第一次分发后留在本地,后续查询直接复用。没有缓存,每次查询都要重付 1000MB;有缓存,这笔流量只付一次。代价是失效管理——小表更新后必须让所有副本同步失效。

半连接与 bloom 下推

runtime filter 的一种严格形式是半连接:只把 build 侧的键集合发给 probe 侧,probe 先做一次存在性判断,只保留可能匹配的行。常见实现有三种形态:

形态传输内容精确性
半连接键集合完整键列表精确,无假阳性
布隆过滤器位数组有假阳性、无假阴性
min-max 区间键的上下界粗粒度,可能放行大量行

三者的共同目标都是让 probe 侧提前丢弃不可能匹配的行。精确键集合效果最好但体积最大;布隆过滤器体积小、允许少量误判;min-max 最省空间,只适合键分布集中的场景。选择哪一种,取决于「过滤器体积」与「能剪掉多少行」的比值。

runtime filter 什么时候失效

它并不是总有效,下面几种情况收益会明显下降:

场景原因结果
选择率接近 100%几乎每行都可能匹配剪不掉多少
build 侧键集合过大过滤器本身几 MB 甚至更大传输与查询成本反超收益
probe 侧很小省下的绝对探测次数有限不值得额外复杂度
键分布极偏布隆过滤器假阳性集中在热点热点行仍要探测

判断是否值得开,算的是「过滤器成本」与「省下的探测次数 × 单次探测成本」。用例 54 之所以划算,是因为 500 万次探测省掉 95%,而过滤器只是一个小位数组;如果 probe 侧只有几万行,省下的绝对时间可能还不够构造过滤器的开销。

流量之外:广播的时延

流量账看总量,时延账看长尾。1000MB 分到 100 个 executor,平均每个接收 10MB(公式推导:1000 ÷ 100),但广播是并行的,整体等待时间由最慢的那个接收方决定:

指标计算结果
总流量用例 531000MB
单节点平均接收1000MB ÷ 10010MB(公式推导)
完成时间最慢接收方受长尾与拥塞影响

一个慢节点会拖住整个广播。这也是广播比 shuffle 更怕集群不健康的原因:shuffle 的分区可以重试或迁移,广播的每一份副本都必须送到。生产上如果发现广播查询偶发变慢,先查的是节点间的带宽差异,而不是执行计划。

组合顺序:先定算法,再定分发,最后加过滤

三层决策有固定的先后,顺序错了会互相抵消:

顺序决策依据
第一步连接类型等值才考虑哈希
第二步分发方式广播流量与大表 shuffle 的比较
第三步是否加过滤build 侧键集合的收益比

顺序不能颠倒:先加 runtime filter、再选错分发方式,过滤器省下的探测会被广播流量抵消。只有算法与分发都选对了,过滤才是净收益。

三个常见误解

误解一:广播总是比 shuffle 便宜,能广播就广播。 真相:流量等于表大小乘 executor 数,10MB 广播到 100 个 executor 就是 1000MB,集群越大越容易打满网络。

误解二:runtime filter 只是个小优化,省不了多少。 真相:build 完成后用键集合剪 probe,选择率 5% 时 probe 从 500 万降到 25 万,探测成本省掉 95%。

误解三:嵌套循环已经过时,任何连接都不该用。 真相:非等值连接、一侧极小、带 LIMIT 的短路场景里,嵌套循环仍是唯一或最优选择。

一句话总结本节

广播、嵌套循环与 runtime filter 覆盖了 hash join 处理不了的两类连接:10MB 小表广播到 100 个 executor 是 1000MB 流量,成本随集群规模线性上升;嵌套循环在非等值或一侧极小时仍是兜底;runtime filter 把 build 阶段的键集合下发给 probe,选择率 5% 时把 500 万行剪到 25 万行,省掉 95% 的探测。先用连接类型定算法,再用流量账定广播是否划算。

本节 lab

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

在 bd-engine-lab 中验证广播流量与 runtime filter 的削减效果:

  • 源码: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。
  • 断言:用例 53 验证「10MB 小表广播到 100 个 executor,总流量 1000MB」;用例 54 验证「runtime filter 选择率 5%,probe 从 500 万降到 25 万,节省 95%」。
  • 整卷 runner 的预期汇总为 TOTAL: 116 passed, 0 failed。

对应本节判断链:shuffle 连接打满网络或连接没有等值键 → 广播把小表复制到每个 executor、嵌套循环兜底非等值 → 算出 1000MB 广播流量与 95% 的 probe 削减 → 按连接类型与流量账选策略,能剪 probe 就叠加 runtime filter。

继续阅读

探索更多技术文章

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

全部文章 返回首页

「books」更多文章

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