6.1 Hash join:build 与 probe
Hash join 几乎是所有等值连接的默认实现。它把连接拆成两个不对称的阶段:先用一张表在内存里建一张哈希表,再让另一张表逐行来查。不对称是它的全部设计核心——选哪张表建表、表要多大、探测要花多少时间,这三个问题决定了一次连接是几十毫秒还是几十秒。
本节沿一条判断链走:现象是连接算子比预期慢得多,机制是 build 与 probe 的成本结构不同,账本是 12MB 哈希表、500 万次探测与 100ms,判据是 build 侧必须小到放得进内存。
两个阶段各做什么
| 阶段 | 输入 | 动作 | 输出 |
|---|---|---|---|
| build | build 侧全表 | 读行、算哈希、插入槽位 | 常驻内存的哈希表 |
| probe | probe 侧流式 | 逐行算哈希、查槽、比对键 | 匹配的拼接行 |
两个阶段的成本形态完全不同: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,000 | build 侧小表 |
| 每槽字节 | 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,000 | 100ms(用例 47) |
| 10% | 500,000(公式推导) | 5,000,000 | 100ms |
| 100% | 5,000,000(公式推导) | 5,000,000 | 100ms |
这张表最重要的一列是「探测次数」,它在三行里完全相同。匹配率从 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 join | 5,000,000 次探测(用例 46) | 等值键、build 侧可入内存 |
两者相差约 50 万倍(公式推导:2.5×10¹² ÷ 5×10⁶)。这不是常数优化,而是算法级替换:哈希把「对每一行扫描整张表」变成「对每一行查一个槽」。
哈希表的容量与装填因子
12MB ÷ 24 字节 = 500,000 槽(公式推导),正好一行一槽。实际实现通常会开更多槽以降低冲突,装填因子控制在 1 以下。下表按装填因子 1.0 与 0.5 两种假设推导:
| 装填因子(假设) | 槽数 | 冲突链 | 内存 |
|---|---|---|---|
| 1.0 | 500,000(公式推导) | 较长,平均链长上升 | 12MB(用例 45) |
| 0.5 | 1,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[输出匹配和所需未匹配行]
上游实现参照
本节 lab
在 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。
继续阅读
探索更多技术文章
浏览归档,发现更多关于系统设计、工具链和工程实践的内容。