同样两张 5000 行的表做连接，嵌套循环要比较 2500 万次，哈希连接只需要 5000 次探测——5000 倍的差距。数据库里的三种连接算法（嵌套循环、哈希连接、归并连接）不是教科书上的并列知识点，而是各自统治一种特定场景。本文实现三种算法的完整可运行版本，用三组实验回答：它们各自快在哪、慢在哪、优化器凭什么在它们之间做选择。

一、三种算法的本质差异

二、完整可运行实现（Python 3，约 110 行）

下面的程序用同一份随机数据跑三种算法并互验结果一致，再演示预排序输入和哈希表溢出两个关键场景：

#!/usr/bin/env python3
"""连接算法模拟：NLJ / Hash Join / Merge Join 成本对比
   与 Grace Hash 分区溢出"""
import random
random.seed(11)

PAGE = 100          # 每页 100 行
MEM_PAGES = 50      # 内存可容纳 50 页

def make_tables(n_l, n_r, dup=1):
    L = [random.randrange(n_r * dup) for _ in range(n_l)]
    R = [random.randrange(n_r * dup) for _ in range(n_r)]
    return L, R

def nlj(L, R):
    cmp = 0
    pairs = 0
    for l in L:
        for r in R:
            cmp += 1
            if l == r:
                pairs += 1
    return cmp, pairs

def hash_join(L, R):
    table = {}
    cmp = 0
    pairs = 0
    for r in R:                        # build 侧建哈希表
        table.setdefault(r, []).append(r)
    for l in L:                        # probe 侧探测
        cmp += 1
        if l in table:
            pairs += len(table[l])
    return cmp, pairs

def merge_join(L, R):
    """重复键按块做多对多配对"""
    L = sorted(L)
    R = sorted(R)
    i = j = 0
    cmp = 0
    pairs = 0
    while i < len(L) and j < len(R):
        cmp += 1
        if L[i] == R[j]:
            key = L[i]
            ni = i
            while ni < len(L) and L[ni] == key:
                ni += 1
            nj = j
            while nj < len(R) and R[nj] == key:
                nj += 1
            pairs += (ni - i) * (nj - j)   # 块级笛卡尔配对
            i, j = ni, nj
        elif L[i] < R[j]:
            i += 1
        else:
            j += 1
    return cmp, pairs

print('=== 连接算法对比模拟 ===')
print('--- 实验 1: 5000 行 ⋈ 5000 行 ---')
L, R = make_tables(5000, 5000)
c1, p1 = nlj(L, R)
c2, p2 = hash_join(L, R)
c3, p3 = merge_join(L, R)
print('结果行数（三者必须一致）: %d / %d / %d' % (p1, p2, p3))
assert p1 == p2 == p3
print('嵌套循环: 比较 %d 次' % c1)
print('哈希连接: 探测 %d 次（建表 %d 次插入）' % (c2, len(R)))
print('归并连接: 比较 %d 次（另有排序成本）' % c3)
print('NLJ 与 Hash 的比较次数比: %.0f 倍' % (c1 / c2))

print()
print('--- 实验 2: 输入已有序时归并连接的逆袭 ---')
Ls = sorted(make_tables(5000, 5000)[0])
Rs = sorted(make_tables(5000, 5000)[1])
c3s, p3s = merge_join(Ls, Rs)
print('预排序输入下归并连接: 仅 %d 次比较 + 0 次排序'
      '（索引扫描天然有序）' % c3s)
print('哈希连接仍需全量建表 %d 次插入 + %d 次探测'
      % (len(Rs), len(Ls)))

print()
print('--- 实验 3: 哈希表装不下内存时（Grace Hash Join） ---')
def grace_hash(n_l, n_r, mem_pages):
    l_pages = n_l // PAGE
    r_pages = n_r // PAGE
    hash_pages = r_pages // 5       # 哈希表开销约 1/5 数据量
    if hash_pages <= mem_pages:
        return l_pages + r_pages, 0
    io = 2 * (l_pages + r_pages)    # 分区写出 + 读回
    return l_pages + r_pages, io

for scale in [(2000, 2000), (20000, 20000), (200000, 200000)]:
    base_io, spill_io = grace_hash(scale[0], scale[1], MEM_PAGES)
    print('  %6d ⋈ %-6d 行: 基础 I/O %6d 页, 溢出 I/O %6d 页 %s'
          % (scale[0], scale[1], base_io, spill_io,
             '(内存够，一趟完成)' if spill_io == 0
             else '(哈希表溢出，分区两趟)'))
print('结论: 哈希表超过内存 -> Grace 分区把随机溢出'
      '变成顺序批处理')

三、真实运行输出与解读

以上代码在 Python 3 下原样运行（零依赖），输出如下：

=== 连接算法对比模拟 ===
--- 实验 1: 5000 行 ⋈ 5000 行 ---
结果行数（三者必须一致）: 5093 / 5093 / 5093
嵌套循环: 比较 25000000 次
哈希连接: 探测 5000 次（建表 5000 次插入）
归并连接: 比较 5606 次（另有排序成本）
NLJ 与 Hash 的比较次数比: 5000 倍

--- 实验 2: 输入已有序时归并连接的逆袭 ---
预排序输入下归并连接: 仅 5735 次比较 + 0 次排序（索引扫描天然有序）
哈希连接仍需全量建表 5000 次插入 + 5000 次探测

--- 实验 3: 哈希表装不下内存时（Grace Hash Join） ---
    2000 ⋈ 2000   行: 基础 I/O     40 页, 溢出 I/O      0 页 (内存够，一趟完成)
   20000 ⋈ 20000  行: 基础 I/O    400 页, 溢出 I/O      0 页 (内存够，一趟完成)
  200000 ⋈ 200000 行: 基础 I/O   4000 页, 溢出 I/O   8000 页 (哈希表溢出，分区两趟)
结论: 哈希表超过内存 -> Grace 分区把随机溢出变成顺序批处理

四、理论分析

4.1 优化器的选择决策树

连接算法选择归结为三个判断：右表有无可用索引？有且左表小 → NLJ（每次探测走索引，O(L × log R)）。无索引但小的一侧装得下内存？装得下 → 哈希连接。输入已有序或输出需有序？是 → 归并连接（省掉排序）。三者都不满足时退化为 Grace 分区哈希或块嵌套循环。这与本专栏查询优化器一文中的代价公式完全对应——连接算法选择就是代价模型在三套公式间取最小值。

4.2 哈希连接的 build 侧选择

哈希表建在内存里，所以 build 侧必须选估计行数更小的一侧——选反了，哈希表撑爆内存触发分区溢出，代价翻倍。这就是为什么基数估计的准确性直接决定连接性能：优化器估错 10 倍行数，build/probe 选反，一次连接可能从秒级变分钟级。

4.3 向量化与 SIMD 加速

现代分析型数据库（ClickHouse、DuckDB、Arrow 系）把哈希连接做成了缓存友好的艺术：build 侧哈希表按缓存行对齐、probe 侧按 1024 行的向量批次处理、键比较用 SIMD 指令一次比 16 个。同样的 O(L+R) 算法，向量化实现比逐行实现快 5~10 倍——算法决定复杂度量级，实现决定常数，两者在数据库内核里同等重要。

五、工程应用

六、常见误区

七、参考文献

  1. G. Graefe (1993). Query Evaluation Techniques for Large Databases. ACM Computing Surveys.（连接算法实现的百科全书式综述）
  2. L. Shapiro (1986). Join Processing in Database Systems with Large Main Memories. VLDB.（Grace Hash Join 时代的主存哈希连接奠基工作）
  3. P. Boncz et al. (2005). MonetDB/X100: Hyper-Pipelining Query Execution. CIDR.（向量化执行的开山之作）
  4. PostgreSQL Documentation: Chapter 14 中 join 算子与 work_mem 相关说明。
  5. MySQL Documentation: Hash Join Optimization（8.0.18+）与 Block Nested-Loop Join 章节。
← 返回文章列表