Lec 12 Join Algorithms：Nested Loop、Sort-Merge、Hash

0. 代价模型与基本记号

这讲主要讨论两个表 R 和 S 的二元 inner equi-join。

记号如下：

M：R 的页数
N：S 的页数
m：R 的 tuple 数
n：S 的 tuple 数
B：可用 buffer page 数
C：一次 index probe 的平均代价

主要优化目标是 I/O 成本。

这里暂时忽略：

结果输出成本
CPU 成本
网络成本

如果从 CPU / 算法复杂度角度看，一个有用的粗略直觉是：

naive join 本质上是在做大量 tuple 对比较
hashing 在期望情况下接近线性
sort-merge 通常是“排序代价 + 一次 merge 扫描”，但在重复值极多时会退化

1. Join Operator 输出什么

当 r ∈ R 与 s ∈ S 在 join key 上匹配时，join operator 要决定往上游输出什么。

Early Materialization

立刻把所需字段拼成新的输出 tuple。
后续算子更容易消费。
复制成本更高。

Late Materialization

只输出 join key 加 record id / tuple reference。
对列存和宽表更友好。
把真正的 tuple 重建延后到更晚阶段。

2. 为什么 Join 选择很重要

直接做 R × S 再过滤，通常会非常昂贵。

没有哪一种 join 算法在所有场景下都最好，选择取决于：

内存大小
是否已有可用索引
输入是否已经按 join key 排序
数据分布是否偏斜
哪一边更小

只要算法允许，较小的那一侧通常应该作为 outer side 或 build side。

3. Nested Loop Join 家族

3.1 Naive Nested Loop Join

算法形式：

for each tuple r in R:
  for each tuple s in S:
    if r and s match:
      emit

代价：

\[ M + (m \cdot N) \]

从 tuple 对比较角度看，它的复杂度是：

\[ \Theta(mn) \]

为什么差：

R 中每个 tuple 都要把 S 全部页再扫一遍
更像教学上的基线算法

3.2 Block Nested Loop Join

改进办法是：一次把 outer table 的一个 block 放进内存。

如果有 B 个 buffer：

B-2 个 buffer 放 outer block
1 个 buffer 扫 inner relation
1 个 buffer 作为输出

代价：

\[ M + \left\lceil \frac{M}{B-2} \right\rceil \cdot N \]

从 tuple 比较数量看，它仍然是：

\[ \Theta(mn) \]

它真正省下来的不是比较次数，而是磁盘上反复扫描 inner relation 的次数。

关键经验：

outer 应该按页数更小，而不是按 tuple 数更小
如果 outer 能完全放进内存，成本会接近 M + N

这是 nested loop 家族里第一个在工程上比较常用的版本。

一个常见判断式是：

\[ M \leq B-2 \implies \text{outer fits in memory} \]

此时代价会接近：

\[ M + N \]

3.3 Index Nested Loop Join

如果 inner side 在 join key 上已有索引：

1
2
3

for each tuple r in R:
  probe index on S using join key of r
  emit matches

代价：

\[ M + (m \cdot C) \]

从 CPU 角度看，可以近似理解成：

扫 outer 一次
对 outer 的每个 tuple 做一次 index probe
主导项更接近 m 次 probe，而不是 mn 次 tuple 比较

它在下面场景会很好：

索引本来就存在
probe 成本低、选择性好

如果 probe 带来大量随机 I/O，它也会变得很差。

4. Sort-Merge Join

Phase 1：Sort

先把两个输入都按 join key 排序。
可以使用任意合适的排序算法，包括 external merge sort。

Phase 2：Merge

同步扫描两个有序输入。
谁的 key 小就推进谁。
key 相等时输出所有匹配组合。

代价

如果两边都需要先排序：

\[ \text{Sort}(R) = 2M \cdot \left(1 + \left\lceil \log_{B-1}\left\lceil \frac{M}{B} \right\rceil \right\rceil \right) \]

\[ \text{Sort}(S) = 2N \cdot \left(1 + \left\lceil \log_{B-1}\left\lceil \frac{N}{B} \right\rceil \right\rceil \right) \]

\[ \text{Merge Cost} = M + N \]

总成本：

\[ \text{Sort}(R) + \text{Sort}(S) + (M+N) \]

如果忽略重复值极多时的退化，CPU 复杂度大致是：

\[ O(m \log m + n \log n + m + n) \]

什么时候合适

一边或两边本来就按 join key 排好序
输出本身也需要按 join key 排序
排序结果还可以被其他算子复用

重要缺点

最坏情况是：两边大量 tuple 都有同一个 join key。

此时 merge 阶段可能退化到接近：

\[ (M \cdot N) + \text{sort cost} \]

也就是说，重复值特别多时，sort-merge join 可能没有看起来那么美好。

5. Hash Join

Hash join 依赖一个关键观察：

如果 r 和 s 在 join key 上相等，那么它们哈希后一定会落到同一个 bucket / partition。

5.1 Simple Hash Join

Build Phase

扫描较小的一侧。
按 join key 把 tuple 插入内存 hash table。
课程里提到实践上简单的 open addressing，例如 linear probing，经常就很好用。

Probe Phase

扫描另一侧。
对 join key 做哈希。
去 hash table 里 probe 匹配项。

只要 build side 能放进内存，这个方案通常非常强。

一个常用的经验判断是：

\[ \min(M, N) \lesssim B-2 \]

这里先忽略 hash table 元数据和输出 buffer 的开销。

期望 CPU 复杂度：

\[ O(m + n) \]

当然，极端哈希冲突或严重 skew 时，最坏情况仍然会恶化。

Probe Filter 优化

在 build hash table 的同时，也构建一个 Bloom filter：

probe 前先查 Bloom filter
过滤掉很多不可能命中的 probe
减少真正访问 hash table 的次数

这也是典型的 sideways information passing。

5.2 Partitioned Hash Join（GRACE Hash Join）

如果 build side 放不进内存，就先把两边都分区。

Partition Phase

把 R 按哈希函数分到 k 个 bucket
把 S 用同一个哈希函数分到对应的 k 个 bucket
bucket 满了就 spill 到磁盘

Probe Phase

对每一对对应分区：

选择更小的一边建内存 hash table
扫描另一边去 probe

如果 不需要递归重分区，成本是：

\[ 3(M + N) \]

原因：

partition 阶段要把两边都读一遍、写一遍：2(M+N)
probe 阶段再把所有分区读回来一遍：M+N

一个常见的“分区后能放下”条件是：

\[ \left\lceil \frac{\min(M, N)}{B-1} \right\rceil \leq B-2 \]

也就是分区后，每个 build partition 都要能装进内存。

在分区均衡、递归次数不多的情况下，期望 tuple 工作量仍然接近：

\[ O(m + n) \]

5.3 边界情况与优化

Recursive Partitioning

如果某个分区第一次分完仍然太大：

用另一个哈希函数继续重分区
重复直到 build partition 能放进内存

数据倾斜 / Hot Key

如果某个 join key 出现次数太多，导致对应分区依然装不下：

可以只对这个重 key 退化成 block nested loop join
用更多顺序 I/O 换掉大量随机 I/O

Hybrid Hash Join

如果内存比“刚好够分区”更多一些：

在第一阶段直接保留一个分区在内存中
当场完成这部分 join
只把剩余分区 spill 到磁盘

这样可以比普通 partitioned hash join 少一些 I/O。

一个重要观察

probe side 可以很大；真正必须装进内存的是 build hash table，或者至少每次的一块 build partition。

6. 选型指南

场景	优先方案	原因
没索引、内存一般、想要稳妥基线	Block nested loop	简单、代价可预测
inner side 上已有好索引	Index nested loop	避免反复全表扫描
输入已排序或输出也要排序	Sort-merge join	可以复用排序收益
较小一侧能放进内存	Simple hash join	通常非常快
两边都大且不关心顺序	Partitioned hash join	I/O 行为最好

7. 复杂度总结

算法	CPU / tuple 复杂度	I/O 成本
Naive nested loop	`\Theta(mn)`	`M + (m \cdot N)`
Block nested loop	`\Theta(mn)`	`M + \left\lceil \frac{M}{B-2} \right\rceil \cdot N`
Index nested loop	大致是 `m` 次 index probe	`M + (m \cdot C)`
Sort-merge join	期望 `O(m \log m + n \log n + m + n)`	`\text{Sort}(R) + \text{Sort}(S) + (M+N)`
Sort-merge 最坏情况	重复值处理可退化到 `O(mn)`	`(M \cdot N) + \text{sort cost}`
Simple hash join	期望 `O(m+n)`	扫描 + build/probe，前提是 build side 能装进内存
Partitioned hash join	期望 `O(m+n)`	若无递归重分区，则 `3(M+N)`

8. 快速总结

Naive nested loop join 主要是教学基线。
Block nested loop join 一旦能缓存 outer block，就会实用很多。
Index nested loop join 的上限完全取决于 index probe 的质量。
Sort-merge join 适合“排序本来就有价值”的场景。
对大规模等值连接来说，hash join 往往是默认主力算法。