《大规模分布式计算深入解析》6.1 Hash join:build 与 probe

解释 Hash Join 的 build 与 probe 阶段、计算预算、重复键与 NULL 比较,以及分区溢写。

6.1 Hash join:build 与 probe

Hash join 几乎是所有等值连接的默认实现。它把连接拆成两个不对称的阶段:先用一张表在内存里建一张哈希表,再让另一张表逐行来查。不对称是它的全部设计核心——选哪张表建表、表要多大、探测要花多少时间,这三个问题决定了一次连接是几十毫秒还是几十秒。

本节沿一条判断链走:现象是连接算子比预期慢得多,机制是 build 与 probe 的成本结构不同,账本是 12MB 哈希表、500 万次探测与 100ms,判据是 build 侧必须小到放得进内存。

两个阶段各做什么

阶段输入动作输出
buildbuild 侧全表读行、算哈希、插入槽位常驻内存的哈希表
probeprobe 侧流式逐行算哈希、查槽、比对键匹配的拼接行

两个阶段的成本形态完全不同:build 是一次性的,随 build 行数线性增长;probe 是流式的,随 probe 行数线性增长,且每一行都要做一次随机访存。整条连接的耗时约等于两者相加,通常 probe 占大头,因为 probe 侧一般是大表。

build 侧:50 万行 × 24 字节 = 12MB

lab 用例 45 的口径很直接:哈希表内存等于行数乘以每槽字节数。

// 用例 45:build 侧哈希表内存
long bytes = Operator.hashTableBytes(500_000L, 24);
// 500,000 × 24 = 12,000,000 字节 = 12MB
量取值说明
build 行数500,000build 侧小表
每槽字节24键、指针与行定位信息
哈希表内存12,000,000 字节用例 45,即 12MB

24 字节一槽不是随便定的:一个槽要放键的哈希值或键本身、一个指向行数据的引用,再加上对齐填充。槽越小,同样内存能装的表越大;槽越大,探测时一次读入的缓存行里有效信息越少。

12MB 这个数字的意义在于它和缓存层级的关系:它已经明显超出 L2,但仍可能落在 L3 里。表能不能留在缓存里,直接决定后面 probe 阶段每次探测的实际延迟。

probe 侧:500 万次探测,每次 20ns

probe 阶段的次数没有悬念:probe 侧有多少行,就有多少次探测。lab 用例 46 与用例 47 把这个账算完整:

探测次数 = probe 行数 = 5,000,000 次        (用例 46)
单次探测成本 = 20ns                          (用例 47 参数)
probe 总成本 = 5,000,000 × 20ns
             = 100,000,000ns
             = 100ms                          (用例 47)
量取值来源
probe 行数5,000,000统一场景
探测次数5,000,000用例 46
每次探测20ns用例 47
probe 成本100ms用例 47

20ns 一次探测,比一次 L1 命中的几个纳秒贵了一个数量级,原因不是哈希计算本身,而是随机访存:哈希把键打散到 12MB 的表里,相邻两行几乎必然落在不同缓存行,每次探测都可能是一次 cache miss。这也解释了为什么把表做得更大并不能换来更快的探测——表越大,访问越随机。

匹配率只决定输出,不决定探测

一个很容易算错的量是输出行数。lab 用例 48 设定外键匹配率 1%,输出就是 5 万行:

输出行数 = probe 行数 × 匹配率 = 5,000,000 × 1% = 50,000 行
匹配率输出行数探测次数probe 成本
1%50,000(用例 48)5,000,000100ms(用例 47)
10%500,000(公式推导)5,000,000100ms
100%5,000,000(公式推导)5,000,000100ms

这张表最重要的一列是「探测次数」,它在三行里完全相同。匹配率从 1% 涨到 100%,probe 的计算成本一分不少,变的只是输出多少行、以及输出阶段要复制多少数据。所以「连接选择性高所以很快」这句话只对了一半:省下的是输出与下游处理,不是探测本身。

build 侧为什么常选择较小输入

把两侧的角色对调,账本立刻变形。如果 build 侧是 500 万行,哈希表内存按同样 24 字节一槽就是 120MB(公式推导:5,000,000 × 24 字节):

build 侧哈希表内存是否可能常驻内存后果
50 万行12MB(用例 45)可以一次建表,直接探测
500 万行120MB(公式推导)取决于内存上限可能被迫分区或溢写

选小表建表不是习惯,是硬约束:表一旦放不进可用内存,hash join 就得退化成分区哈希——先按哈希把两侧都切成分区,再逐个分区建表探测,多出一轮写盘与读盘。这个代价在 6.2 的 spill 账里会具体展开。

与嵌套循环的差距有多大

为了看清 hash join 省了什么,把它和最朴素的嵌套循环放在一起比。probe 侧 500 万行、build 侧 50 万行:

算法比较次数前提
嵌套循环5,000,000 × 500,000 = 2.5×10¹²(公式推导)无
hash join5,000,000 次探测(用例 46)等值键、build 侧可入内存

两者相差约 50 万倍(公式推导:2.5×10¹² ÷ 5×10⁶)。这不是常数优化,而是算法级替换:哈希把「对每一行扫描整张表」变成「对每一行查一个槽」。

哈希表的容量与装填因子

12MB ÷ 24 字节 = 500,000 槽(公式推导),正好一行一槽。实际实现通常会开更多槽以降低冲突,装填因子控制在 1 以下。下表按装填因子 1.0 与 0.5 两种假设推导:

装填因子(假设)槽数冲突链内存
1.0500,000(公式推导)较长,平均链长上升12MB(用例 45)
0.51,000,000(公式推导)较短24MB(公式推导)

装填因子是内存与探测成本之间的旋钮:因子高,表小、缓存更友好,但冲突链变长,一次探测可能退化成多次比对;因子低,冲突少,但表大、随机访存的范围更大。多数引擎取中间值,而不是追求某一端的极值。

成本账本与判据

把两段的账合成一张表,能看清哪一项会随数据增长失控:

成本项触发频率本节数值是否随规模失控
build 建表每 build 行一次12MB 表(用例 45)线性,但只做一次
probe 探测每 probe 行一次100ms(用例 47)线性,随大表增长
输出复制每匹配行一次5 万行(用例 48)由匹配率决定

判据可以写得很短:

条件结论
等值连接,build 侧能放进内存首选 hash join
build 侧过大,装不下退化为分区哈希或转 sort-merge
非等值连接(范围、不等)哈希不适用,转嵌套循环或 sort-merge
probe 侧极小、build 侧极大考虑对调角色或改用广播

核心判据只有一条:build 侧的表能不能放下。放得下,探测成本约等于大表行数乘以单次探测成本;放不下,任何哈希技巧都救不了,必须换算法或先分区。

槽的 24 字节里装了什么

24 字节不是一个随意取的值,它通常由三部分凑成:

组成典型宽度(假设)作用
哈希值或键前缀8 字节量级快速排除不匹配
行指针8 字节量级指回 build 侧原始行
链指针或占用标记8 字节量级冲突链与空槽判断
合计24 字节用例 45 的每槽字节

槽宽是内存与比对成本的折中:只存哈希值,探测命中后可能发现是假阳性,要回表再比一次;把完整键塞进槽里,省掉回表,但槽变宽、同样内存装的表变小。24 字节是常见折中——槽里放哈希加指针,完整比对留到哈希命中之后。

这也解释了为什么宽键连接更贵:键本身不放大槽,但哈希计算与回表比对会变慢,前者影响 build 与 probe 两侧,后者只影响真正命中的那部分行。

build 侧的插入成本

build 阶段不只是分配 12MB 内存,还要把 50 万行逐条插进去。每次插入都要算一次哈希、定位槽位、必要时处理冲突:

动作频率访存特征
算哈希每 build 行一次顺序读键
定位槽位每 build 行一次一次随机写
冲突处理冲突发生时额外随机访问

插入成本通常小于 probe 成本,因为 probe 侧行数一般远大于 build 侧,而且探测是纯读、无法批量合并。但如果 build 侧键很宽、哈希函数很贵,插入就不能忽略。

把 build 行数放大到 500 万,插入次数同步放大 10 倍(公式推导:5,000,000 ÷ 500,000)。这正是 build 侧要尽量选小表的第二层理由:它不仅决定内存,也决定插入次数。

分布式下的 build 侧选择

在分布式 shuffle hash join 里,两侧都先按连接键重分布,每个分区各自建表。此时 build 侧的选择多了一个维度:不是「全局哪张表小」,而是「每个分区里哪一侧小」。

场景build 侧原因
小表广播连接小表每个 executor 各建一份
大表 shuffle 连接分区后较小的一侧降低单分区内存
分区后仍然过大转 sort-merge哈希表放不下

全局统计会骗人:一张表全局看不大,但某个热点键分区可能远超平均值。按分区实际大小决定 build 侧,比按全局统计决定更稳;如果某个分区怎么选都放不下,就只能退回 sort-merge 或对该分区单独处理。

重复键与 NULL 改变输出数

前文 5 万行的估算假定每个命中的 probe 行只匹配一个 build 行。对内等值连接,某个非 NULL 键的贡献等于左右两侧该键行数的乘积。左右各有两个 1 和一个 NULL 时,普通等号得到四行;使用 NULL-safe 条件 IS NOT DISTINCT FROM 时,NULL 再贡献一对,共五行。Hash 冲突的候选要比较实际键,外连接还需处理未匹配行。DuckDB 对照脚本

三个常见误解

误解一:连接快慢由匹配的行数决定。 真相:探测次数恒等于 probe 行数,1% 匹配率仍是 500 万次探测、100ms,匹配率只影响输出与下游。

误解二:build 侧选哪张表都一样,反正都要建表。 真相:表大小是行数乘每槽字节,50 万行 12MB 能放下,500 万行 120MB 就可能放不下而被迫分区溢写。

误解三:哈希表开得越大,探测越快。 真相:探测成本由随机访存主导,表越大访问越散、cache miss 越多;装填因子应在冲突与局部性之间取平衡。

一句话总结本节

Hash join 用 build 阶段把 50 万行、每槽 24 字节的小表建成 12MB 哈希表,再用 probe 阶段对大表的 500 万行做 500 万次探测,按每次 20ns 计是 100ms;在 build 键唯一的示意下,1% 匹配率产出 5 万行输出,探测次数并不因此减少。通常优先选择可构建且更小的输入,一旦表放不进内存,就得换成分区哈希或 sort-merge。

分区 Hash Join 的内存状态

先明确 build 侧选择、键比较语义和单分区预算。发生溢写后要按分区协调 build 与 probe。

flowchart TD
    A[Build 输入] --> H[为分区建立哈希表]
    B[Probe 输入] --> K[计算连接键与分区号]
    H --> C{分区预算允许}
    C -->|是| D[探测时比对实际键]
    C -->|否且支持 spill| E[将 build 与 probe 对应分区落盘]
    E --> F[重读分区并重建表]
    F --> C
    K --> D
    D --> J[遍历同键记录<br/>遵循 NULL 与连接类型]
    J --> X[输出匹配和所需未匹配行]

上游实现参照

DuckDB 的连接算子实现

本节 lab

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

在 bd-engine-lab 中验证 hash join 的 build 与 probe 账本:

  • 源码: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。
  • 断言:用例 45 验证「50 万行 × 24 字节 = 12MB 哈希表」;用例 46 验证「probe 侧 500 万行需要 500 万次探测」;用例 47 验证「500 万次 × 20ns = 100ms」;用例 48 验证「1% 匹配率输出 5 万行」。
  • 整卷 runner 的预期汇总为 TOTAL: 116 passed, 0 failed。

对应本节判断链:连接比预期慢 → 拆成 build 建表与 probe 探测两段 → 算出 12MB 表与 100ms 探测成本 → build 侧放得进内存就用 hash join,放不下转分区哈希或 sort-merge。

继续阅读

探索更多技术文章

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

全部文章 返回首页

「books」更多文章

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