SQL - JOIN 执行过程算法分解

数据库如何执行 JOIN？Nested Loop、Hash Join、Merge Join 三种算法的原理和选择策略。

建议先阅读：SQL JOIN 执行过程深度拆解

算法快速对比

算法	最佳复杂度	最坏复杂度	适用场景	关键条件
Nested Loop	O(M × log N)	O(M × N)	小表 JOIN 大表	大表有索引
Hash Join	O(M + N)	O(M + N)	两个大表	内存能容纳小表
Merge Join	O(M + N)	O(M log M + N log N)	已排序数据	有排序索引或预排序

M = 驱动表行数，N = 被驱动表行数

想象你在电影数据库里查询”每部电影有哪些演员”。movies 表 4 行，actors 表 6 行。数据库会如何完成这个 JOIN？答案取决于它选择的算法。

Nested Loop：最朴素的双层循环

这是最容易理解的方式，就像你用笔在纸上对比两张表。

for each row in movies:              # 外层循环（驱动表）
    for each row in actors:          # 内层循环（被驱动表）
        if movies.id == actors.movie_id:
            output (movies.title, actors.name)

取第一部电影 “Inception”，扫描 actors 表全部 6 行，找到 Leonardo DiCaprio 和 Anne Hathaway。再取第二部电影 “The Dark Knight”，又扫描 actors 表全部 6 行，找到 Christian Bale。如此反复。

成本：4 × 6 = 24 次比较

但如果 actors.movie_id 有索引呢？

1. 取 movies[0] (Inception, id=1)
   → 索引查找 actors.movie_id = 1（log(6) ≈ 2-3 次） → 找到 2 个
2. 取 movies[1] (id=2)
   → 索引查找（log(6) ≈ 2-3 次） → 找到 1 个
...

成本降至：4 × log(6) ≈ 10 次比较

索引让 Nested Loop 从灾难变成可用。没有索引时，它是 O(M × N) 的噩梦；有索引时，它变成 O(M × log N) 的优雅方案。

Hash Join：用空间换时间

两张表都很大，内存又足够，数据库会选择另一种策略。

Build Phase：先把小表 movies 全部读入内存，构建一个哈希表：

Hash Table (以 movies.id 为 key):
┌─────┬─────────────────────────────┐
│ Key │ Value                       │
├─────┼─────────────────────────────┤
│ 1   │ { title: 'Inception' }      │
│ 2   │ { title: 'The Dark Knight' }│
│ 3   │ { title: 'Interstellar' }   │
│ 4   │ { title: 'Tenet' }          │
└─────┴─────────────────────────────┘

Probe Phase：遍历 actors 表，每一行直接查哈希表（O(1) 时间）：

1. Leonardo DiCaprio (movie_id=1) → hash[1] = 'Inception' ✅
2. Christian Bale (movie_id=2) → hash[2] = 'The Dark Knight' ✅
3. Matthew McConaughey (movie_id=3) → hash[3] = 'Interstellar' ✅
4. Anne Hathaway (movie_id=3) → hash[3] = 'Interstellar' ✅
5. Anne Hathaway (movie_id=1) → hash[1] = 'Inception' ✅
6. Tom Hardy (movie_id=NULL) → hash[NULL] 不存在 ❌

成本：4 次构建 + 6 次探测 = 10 次操作，O(M + N) 线性复杂度

不需要索引，不需要反复扫描，每张表只读一遍。代价是内存：小表必须能完整装入哈希表。

Merge Join：双指针的优雅舞步

如果两张表已经排序（或有排序索引），数据库会选择最省内存的方案。

两张表先按 JOIN 键排序：

movies 按 id 排序：
[1-Inception, 2-The Dark Knight, 3-Interstellar, 4-Tenet]

actors 按 movie_id 排序：
[1-Leonardo, 1-Anne, 2-Christian, 3-Matthew, 3-Anne, NULL-Tom]

然后用两个指针同时往前走：

pointer_m = movies[0]  (id=1, Inception)
pointer_a = actors[0]  (movie_id=1, Leonardo)

迭代 1：movies.id (1) == actors.movie_id (1) ✅
  → 输出 (Inception, Leonardo)
  → pointer_a++

迭代 2：movies.id (1) == actors.movie_id (1) ✅
  → 输出 (Inception, Anne)
  → pointer_a++

迭代 3：movies.id (1) < actors.movie_id (2)
  → pointer_m++
  现在 movies.id=2, actors.movie_id=2

迭代 4：movies.id (2) == actors.movie_id (2) ✅
  → 输出 (The Dark Knight, Christian)
  → pointer_a++

... 继续扫描直到两个指针都到达末尾

成本：4 + 6 = 10 次操作，O(M + N) 线性复杂度

像拉链一样合并两个有序数组，不需要哈希表，内存占用小。但前提是数据已排序，否则排序本身会花费 O(M log M + N log N) 的时间。

数据库如何选择算法

优化器（Optimizer）像一个经验丰富的导演，评估现场条件后选择最佳方案：

条件	选择算法	关键因素
小表 JOIN 大表 + 有索引	Nested Loop	O(M × log N)，索引是救命稻草
两个大表 + 内存足够	Hash Join	O(M + N)，用空间换时间
有排序索引	Merge Join	O(M + N)，最省内存
什么都没有	Nested Loop 全表扫描	O(M × N)，祈祷吧 ☠️

优化器会评估：表大小、是否有索引、是否已排序、可用内存、JOIN 列的数据分布，然后选择预估成本最低的算法。这就是为什么同一条 SQL，数据量变化后可能走不同算法。

Holly

Explorer