My VitePress Site

Appearance

下面把 Join operation 按“为什么难、到底在比什么、每种算法什么时候用、题目怎么做”讲清楚。你先抓住一句话：

Join 的本质是：从两个关系中找出满足连接条件的 tuple pair。难点不是逻辑，而是怎样避免把两张表所有 tuple 两两比较。本章 PPT 中 Join 主要比较 Nested-loop、Block nested-loop、Indexed nested-loop、Merge join、Hash join 的代价和适用条件。

1. Join 到底在做什么？ ​

假设有两个关系：

text
depositor(customer_name, account_number)
customer(customer_name, street, city)

查询：

sql
select *
from depositor natural join customer;

意思是：

找出 depositor.customer_name = customer.customer_name 的 tuple pair，然后拼接输出。

逻辑上非常简单：

text
对 depositor 中每一行 d
    找 customer 中 customer_name 相同的行 c
    输出 d 和 c 的拼接

问题是：如果两张表很大，不能真的粗暴两两比较。

2. Join 算法的核心分类 ​

本章 Join 算法可以按“借助什么信息”分类：

算法借助什么适用连接条件核心思想
Nested-loop join什么都不借助任意 join condition每条 tuple 两两比较
Block nested-loop join利用 block 批量处理任意 join condition每次拿一批外表 block，减少内表扫描次数
Indexed nested-loop join利用 inner 表索引equi-join / natural join外表每条 tuple 去 inner 表索引查
Merge join利用排序equi-join / natural join两边按 join key 排序后线性归并
Hash join利用哈希分区equi-join / natural join相同 join key 必在同一分区，只在对应分区内连接

你可以先记住：

text
任意条件：Nested-loop / Block nested-loop
等值连接：Indexed nested-loop / Merge join / Hash join

3. Join 题目中最重要的符号 ​

考试题一般会给这些量：

符号含义
r, s两个关系
nrrelation r 的 tuple 数
nsrelation s 的 tuple 数
brrelation r 的 block 数
bsrelation s 的 block 数
M可用内存 block 数
HiB+ tree index 高度
c对 inner relation 做一次索引查找的代价

最容易错的是：

n 是 tuple 数，b 是 block 数。
Nested-loop 用 tuple 数；Block nested-loop 用 block 数。

4. Nested-Loop Join：最笨但最通用 ​

是什么 ​

普通嵌套循环连接：

text
for each tuple tr in r:
    for each tuple ts in s:
        if tr and ts satisfy join condition:
            output tr ⋈ ts

为什么需要 ​

它不要求索引、不要求排序、不要求等值连接。只要能判断 join condition，就能用。

直观理解 ​

就是暴力双重循环。

如果 r 有 5000 条，s 有 10000 条，就要检查：

text
5000 * 10000 = 50,000,000

对 tuple pair。

代价公式 ​

设 r 是 outer relation，s 是 inner relation。

worst case：

text
block transfers = nr * bs + br
seeks = nr + br

为什么是 nr * bs + br？

  • 先读一遍 outer relation：br

  • 对 outer 的每个 tuple，都扫描一遍 inner relation：nr * bs

典型例子 ​

PPT 中：

text
depositor: nr = 5000, br = 100
customer:  ns = 10000, bs = 400

若 depositor 做 outer：

text
BT = nr * bs + br
   = 5000 * 400 + 100
   = 2,000,100

若 customer 做 outer：

text
BT = 10000 * 100 + 400
   = 1,000,400

所以普通 nested-loop 中，不一定让 block 少的表做 outer，而是要看：

text
outer tuple 数 * inner block 数 + outer block 数

易错点 ​

错误正确
用 br * bs + br 算普通 nested-loop那是 block nested-loop
以为普通 nested-loop 一定让小表 outer要比较 nr * bs + br
忘记它支持任意 join condition它最通用，但通常最慢

5. Block Nested-Loop Join：把外层 tuple 换成 block ​

是什么 ​

普通 nested-loop 是：

text
每次拿 outer 的一条 tuple

Block nested-loop 是：

text
每次拿 outer 的一个 block 或一批 blocks

伪代码：

text
for each block Br in r:
    for each block Bs in s:
        compare tuples inside Br and Bs

为什么更快 ​

普通 nested-loop 中，outer 每条 tuple 都要扫描一遍 inner。

Block nested-loop 中，outer 每个 block 才扫描一遍 inner。

如果一个 block 中有很多 tuple，就能减少很多次 inner 扫描。

M = 3 时的代价 ​

设 r 是 outer，s 是 inner：

text
block transfers = br * bs + br
seeks = 2 * br

为什么？

  • 读 outer：br

  • 对 outer 的每个 block，扫描一次 inner：br * bs

改进版本：M > 3 ​

如果内存有 M 个 block：

  • M - 2 个 block 放 outer chunk；

  • 1 个 block 读 inner；

  • 1 个 block 放 output。

代价：

text
block transfers = ceil(br / (M - 2)) * bs + br
seeks = 2 * ceil(br / (M - 2))

典型例子 ​

仍然用：

text
depositor: br = 100
customer:  bs = 400

M = 3，depositor 做 outer：

text
BT = 100 * 400 + 100
   = 40,100

相比普通 nested-loop：

text
2,000,100

已经小很多。

如果 M = 10，outer 仍是 customer，inner 是 depositor：

text
br = 400
bs = 100
M - 2 = 8
text
BT = ceil(400 / 8) * 100 + 400
   = 50 * 100 + 400
   = 5,400

内存越大，outer 被分成的 chunk 越少，inner 被重复扫描的次数越少。

什么时候选谁做 outer？ ​

Block nested-loop 通常让 block 数较少的关系做 outer。

因为代价主要是：

text
ceil(br / (M - 2)) * bs + br

outer 的 block 数 br 决定要扫描 inner 多少轮。

易错点 ​

错误正确
把 M - 2 写成 M - 1要留 inner buffer 和 output buffer，所以是 M - 2
用 tuple 数计算 block nested-loopBlock nested-loop 用 block 数
一律让 tuple 少的表做 outer这里重点看 block 数
忘记加 + brouter 本身也要读一遍

6. Indexed Nested-Loop Join：外表逐条查 inner 索引 ​

是什么 ​

如果 inner relation 的 join attribute 上有索引，就不用每次扫描 inner 全表。

做法是：

text
for each tuple tr in outer r:
    use index on inner s to find matching tuples

适用条件 ​

必须满足：

  1. join 是 equi-join 或 natural join；

  2. inner relation 的 join attribute 上有 index。

例如：

sql
select *
from depositor d join customer c
on d.customer_name = c.customer_name;

如果 customer.customer_name 上有索引，可以让：

text
outer = depositor
inner = customer

然后对 depositor 的每条记录去 customer 索引查。

代价公式 ​

text
Cost = nr * c + br

其中：

符号含义
nrouter relation 的 tuple 数
brouter relation 的 block 数
c对 inner 做一次 index lookup 并取出匹配记录的代价

如果 inner 上是 B+ tree key index，高度为 Hi：

text
c = Hi + 1

所以：

text
Cost = nr * (Hi + 1) + br

PPT 例子 ​

text
depositor: n = 5000, b = 100
customer:  n = 10000, b = 400

customer 在 customer_name 上有 primary B+ tree index，高度为 3。

让 depositor 做 outer：

text
nr = 5000
br = 100
c = 3 + 1 = 4

所以：

text
Cost = 5000 * 4 + 100
     = 20,100

这比 block nested-loop 的 40,100 还低。

如果两边都有索引，怎么选 outer？ ​

通常选 tuple 数较少 的关系做 outer。

因为公式是：

text
nr * c + br

核心受 nr 影响。

易错点 ​

错误正确
索引在 outer 上也能用Indexed nested-loop 要用 inner 上的索引
选 block 少的表做 outer这里通常看 tuple 数少的表
忘记扫描 outer 的 br公式要加 + br
非等值连接也能用通常只适合 equi-join / natural join

7. Merge Join：两边排序后像拉链一样合并 ​

是什么 ​

也叫 sort-merge join。

先让两张表都按 join attribute 排序，然后从头到尾线性扫描。

例如两边按 customer_name 排序：

text
depositor:  A, B, D, H
customer:   A, A, C, D, H

扫描过程类似合并两个有序数组。

适用条件 ​

只适用于：

text
equi-join
natural join

因为它依赖“相等的 join key 会排在一起”。

核心思想 ​

排序后：

  • 如果 r.key < s.key，移动 r；

  • 如果 r.key > s.key，移动 s；

  • 如果相等，输出匹配组合。

输入已经有序时的代价 ​

text
BT = br + bs

因为每个 relation 顺序读一遍。

如果输入没有排序，需要加 external sort-merge 的代价。

优点 ​

  • 输入已有序时非常快；

  • 顺序 I/O；

  • 可以顺便产生有序输出；

  • 适合之后还有 order by 或 group by 的情况。

缺点 ​

  • 只适合等值连接；

  • 未排序时要先排序，排序成本可能很高；

  • 如果某个 join key 有大量重复值，需要小心处理一组 tuple 的组合。

易错点 ​

错误正确
Merge join 可以处理 <, > join主要用于 equi/natural join
只算 br + bs前提是两边已经有序
排序 fan-in 用 Mexternal sort-merge 用 M - 1

8. Hash Join：把可能匹配的 tuple 分到同一个桶 ​

是什么 ​

Hash join 是大表等值连接的常用算法。

它利用一个关键事实：

如果两个 tuple 的 join key 相等，那么对 join key 做相同 hash function 后，它们一定进入同一个 partition。

所以不需要全表互相比较，只需要对应分区之间连接。

适用条件 ​

只适用于：

text
equi-join
natural join

因为 hash 只能保证相等值进入同一桶，不能处理 <, >, != 这类条件。

两个阶段 ​

阶段 1：Partition ​

对两个关系用同一个 hash function h 按 join attribute 分区。

text
r → Hr0, Hr1, ..., Hrn
s → Hs0, Hs1, ..., Hsn

如果：

text
h(r.key) = i

则 tuple 进入 Hri。

如果两个 tuple 的 key 相等，它们一定进入同编号分区：

text
Hri 与 Hsi

所以只需要做：

text
Hr0 ⋈ Hs0
Hr1 ⋈ Hs1
...
Hrn ⋈ Hsn

阶段 2：Build and Probe ​

通常选较小关系 s 做 build input。

对每个分区 i：

text
1. 把 Hsi 读入内存
2. 在 Hsi 上建内存 hash index
3. 扫描 Hri
4. 对每个 tuple 去内存 hash index 中查匹配

为什么 build input 要选小表？ ​

因为 build partition 要放入内存。

如果 build relation 太大，partition 放不下，就要 recursive partitioning，代价上升。

无递归分区时的代价 ​

PPT 给出：

text
BT = 3(br + bs) + 4 * nh

通常忽略 partially filled blocks 时：

text
BT ≈ 3(br + bs)

为什么是 3 倍？

  1. partition 阶段：

    • 读 r、s 一遍：br + bs

    • 写 r、s 分区：br + bs

    • 合计 2(br + bs)

  2. join 阶段：

    • 再读各分区一遍：br + bs

总计：

text
3(br + bs)

如果 build input 整个能放入内存 ​

那就不用 partition，直接：

text
1. 把 build relation 读入内存建 hash table
2. 扫描 probe relation

代价：

text
BT = br + bs

这是 hash join 最理想情况。

是否需要 recursive partitioning？ ​

关键条件：

text
每个 build partition ≤ M - 2

如果平均分区后：

text
bs / (M - 1) > M - 2

就可能需要递归分区。

近似记忆：

text
bs > (M - 1)^2 时，可能需要递归分区

PPT 例子 ​

text
M = 20
depositor: b = 100
customer:  b = 400

选 depositor 做 build input：

text
bs = 100
M - 2 = 18

要让每个 build partition 不超过 18 blocks：

text
ceil(100 / 18) = 6

所以分成 6 个 partitions。

每个 depositor partition 大约：

text
100 / 6 ≈ 17

能放进内存，不需要递归分区。

忽略 partially filled blocks：

text
BT = 3(100 + 400)
   = 1500

比 indexed nested-loop 的 20100 小很多。

易错点 ​

错误正确
Hash join 可用于任意 join只适合 equi/natural join
build input 随便选应选较小关系
只要总 build relation 大于 M 就不能用关键是每个 partition 能否放入内存
分区 hash 和内存 hash index 是同一个通常使用不同 hash function
hash join 一定最快skew、overflow、内存不足会让代价上升

9. 五种 Join 算法怎么选？ ​

可以用这张决策表。

场景优先考虑
任意 join condition，例如 <, >, !=Block nested-loop join
equi-join，inner join attribute 有索引，outer 较小Indexed nested-loop join
equi-join，两边已经按 join key 排序Merge join
equi-join，两边无序，大表连接Hash join
build relation 能全部进内存In-memory hash join，代价约 br + bs
内存很小，无索引，无排序Block nested-loop join
查询还需要有序输出Merge join 可能更合适
secondary index 匹配很多记录小心 indexed nested-loop，可能随机 I/O 很贵

10. Join 算法代价总表 ​

算法适用条件Block transfer cost
Nested-loop join任意 joinnr * bs + br
Block nested-loop join, M=3任意 joinbr * bs + br
Block nested-loop join, M>3任意 joinceil(br/(M-2))*bs + br
Indexed nested-loop joinequi/natural，inner 有索引nr * c + br
Indexed NLJ with B+ treeinner B+ tree lookupnr * (Hi+1) + br
Merge join, already sortedequi/naturalbr + bs
Merge join, unsortedequi/naturalsort(r) + sort(s) + br + bs
Hash join, no recursionequi/natural3(br + bs)，简化版
Hash join, build in memoryequi/naturalbr + bs

注意：

  • 表中 r 默认是 outer relation；

  • s 默认是 inner 或 build relation，具体看算法；

  • 不同算法中 r/s 的角色含义不完全一样，做题时要先标清楚。

11. 做 Join 计算题的固定套路 ​

遇到 Join 题，按这个流程做。

Step 1：写清楚统计量 ​

例如：

text
R: nr = 10000, br = 400
S: ns = 5000, bs = 100
M = 10

Step 2：判断 join 类型 ​

text
是否 equi-join / natural join？

如果不是等值连接：

text
不能用 indexed NLJ / merge join / hash join
通常考虑 nested-loop 或 block nested-loop

Step 3：判断有什么物理条件 ​

text
有没有索引？
索引在哪个 relation？
relation 是否已经排序？
内存 M 多大？
build partition 能否放进内存？

Step 4：确定角色 ​

不同算法角色不同：

算法角色选择
Nested-loop比较 nr*bs+br
Block nested-loop通常 block 少的做 outer
Indexed nested-loop有索引的 relation 做 inner
Hash join小 relation 做 build input
Merge join两边对称，关键看是否已排序

Step 5：代入公式 ​

不要混淆 tuple 和 block。

12. 用同一组数据横向比较 ​

假设：

text
depositor:
    nr = 5000
    br = 100

customer:
    ns = 10000
    bs = 400

12.1 Nested-loop join ​

depositor 做 outer：

text
BT = 5000 * 400 + 100
   = 2,000,100

customer 做 outer：

text
BT = 10000 * 100 + 400
   = 1,000,400

12.2 Block nested-loop join ​

depositor 做 outer：

text
BT = 100 * 400 + 100
   = 40,100

customer 做 outer：

text
BT = 400 * 100 + 400
   = 40,400

所以 depositor 做 outer 稍好。

12.3 Indexed nested-loop join ​

假设 customer 在 join attribute 上有 B+ tree index，高度为 3。

depositor 做 outer，customer 做 inner：

text
BT = 5000 * (3 + 1) + 100
   = 20,100

12.4 Hash join ​

假设 depositor 做 build input，且不需要 recursive partitioning：

text
BT = 3(100 + 400)
   = 1500

12.5 已排序 merge join ​

如果两边已经按 join key 排序：

text
BT = 100 + 400
   = 500

但如果没排序，要加排序成本。

13. 最重要的直觉排序 ​

在理想条件下，代价大致可能是：

text
已排序 merge join / build in-memory hash join
    < hash join
    < indexed nested-loop join
    < block nested-loop join
    < tuple nested-loop join

但这不是绝对排序。

反例：

  • 如果两边没排序，merge join 要先排序，可能不划算；

  • 如果 indexed nested-loop 的 outer 很大，且 inner 的 secondary index 导致随机 I/O，可能很慢；

  • 如果 hash join 有严重 skew，可能 overflow；

  • 如果一个表非常小，nested-loop 也可能足够好。

14. 最容易考的判断题 ​

判断 1 ​

“Hash join 可以用于任意 theta join。”

错误。

Hash join 主要用于 equi-join / natural join。

判断 2 ​

“Block nested-loop join 一定比 indexed nested-loop join 慢。”

错误。

如果索引选择性差，或者 secondary index 导致大量随机 I/O，indexed nested-loop 也可能慢。

判断 3 ​

“Merge join 的代价总是 br + bs。”

错误。

只有两边已经按 join attribute 排序时才是。否则要加排序成本。

判断 4 ​

“Indexed nested-loop join 要求 outer relation 上有索引。”

错误。

要求 inner relation 的 join attribute 上有索引。

判断 5 ​

“Hash join 中 build input 应该选较大的 relation。”

错误。

通常选较小 relation，因为 build partition 要放入内存。

15. 一句话总结每个 Join ​

text
Nested-loop:
    最通用，最暴力，按 tuple 两两比较。

Block nested-loop:
    用 block 批处理，减少扫描 inner 的次数。

Indexed nested-loop:
    outer 每条 tuple 去 inner 的索引里查。

Merge join:
    两边按 join key 排序，然后线性归并。

Hash join:
    两边按 join key 哈希分区，只连接对应分区。

真正做题时，先问四个问题：

text
1. 是不是 equi-join？
2. inner 上有没有索引？
3. 两边是否已经排序？
4. 内存 M 是否足够支持 hash join 或 block nested-loop 优化？

这四个问题问完，Join operation 基本就能选算法、套公式、算代价。