课程 5.9: 连接算法 — 数据库如何执行连接

在之前的课程中，我们编写了 SQL 连接，并关注它们返回的 数据。但是数据库实际上是如何在底层 执行 连接的呢？理解引擎使用的物理算法是编写在大型数据集上表现良好的查询的关键。

三种主要的连接算法是：

1. 嵌套循环连接
2. 哈希连接
3. 合并连接（也称为排序合并连接）

查询规划器会根据表的大小、可用索引和内存自动选择其中一种。我们不能在标准 SQL 中强制使用特定算法，但理解权衡可以让我们编写查询并创建索引，引导规划器朝着最佳选择前进。

1. 嵌套循环连接

工作原理

嵌套循环连接是最简单的算法。数据库选择一个表作为 外部（驱动）表，另一个作为 内部 表。然后，它遍历外部表中的每一行，并为每一行在内部表中搜索匹配项——本质上是两个嵌套的 for 循环。

概念伪代码：

for each row R1 in outer_table:
    for each row R2 in inner_table:
        if R1.key = R2.key:
            output(R1, R2)

当内部表的连接列上存在 索引 时，内部扫描变为快速的索引查找，而不是全表扫描。这种变体称为 索引嵌套循环连接，是可能的最有效的执行路径之一。

规划器使用它的情况

• 外部（驱动）表是 小 的。
• 内部表的连接列上存在索引。
• 连接使用 非等式 条件（<、>、BETWEEN）—— 哈希连接和合并连接需要等式，因此在这种情况下嵌套循环是唯一的选择。

优缺点

2. 哈希连接

工作原理

哈希连接分为两个阶段：

1. 构建阶段： 数据库读取 较小 的表，并在连接列上构建一个内存中的哈希表。
2. 探测阶段： 数据库扫描 较大 的表，并为每一行查找哈希表以找到匹配的行。

概念伪代码：

-- 构建阶段
hash_table = {}
for each row R1 in smaller_table:
    hash_table[ hash(R1.key) ].append(R1)

-- 探测阶段
for each row R2 in larger_table:
    for each match in hash_table[ hash(R2.key) ]:
        if R2.key = match.key:
            output(R2, match)

这使得整体复杂度为 O(N + M)——在两个表大小上都是线性的——使其比未索引的嵌套循环连接更具可扩展性。

规划器使用它的情况

• 在 等式 条件下连接两个 大 表。
• 连接列上没有有用的索引。
• 有足够的内存来容纳哈希表（PostgreSQL 中的 work_mem）。

优缺点

注意：在 PostgreSQL 中，您可以通过 work_mem 设置控制内存预算。增加它可以减少在大型哈希连接中昂贵的磁盘溢出机会。

3. 合并连接（排序合并连接）

工作原理

合并连接要求两个输入表在连接列上 排序。然后，它同时合并两个已排序的流——非常像经典的合并排序算法的最后一步——通过每个流推进指针以找到匹配项。

概念伪代码：

sort outer_table by key   -- 如果使用有序索引则跳过
sort inner_table by key   -- 如果使用有序索引则跳过

p1 = outer_table 的开始
p2 = inner_table 的开始

while not end of either stream:
    if outer[p1].key = inner[p2].key:
        output matching rows and advance both pointers
    elif outer[p1].key < inner[p2].key:
        advance p1
    else:
        advance p2

关键优化：如果可以通过 有序索引 扫描表，则排序步骤是免费的，合并连接成为可用的最有效算法之一。

规划器使用它的情况

• 两个表都是 大 的，并且连接条件是 等式。
• 两个表已经排序，或者两个表都可以通过有序索引扫描。
• 查询已经要求在连接列上使用 ORDER BY 或 GROUP BY（无论如何都会进行排序）。

优缺点

4. 选择正确的算法

查询规划器会自动选择算法。您可以通过创建正确的索引和调整内存设置间接影响其决策。

实用提示：

• 在经常连接的外键列上创建索引——这可以启用快速的索引嵌套循环和合并连接。
• 如果哈希连接溢出到磁盘，请考虑增加 work_mem 或查看查询是否可以重构。
• 使用 EXPLAIN ANALYZE 检查规划器实际选择了哪个算法以及每个步骤花费了多少时间：

EXPLAIN ANALYZE
SELECT a.first_name, a.last_name, f.title
FROM actor AS a
INNER JOIN film_actor AS fa ON a.actor_id = fa.actor_id
INNER JOIN film AS f ON fa.film_id = f.film_id;

在输出计划中查找诸如 Hash Join、Merge Join 或 Nested Loop 的关键字，以识别所选算法及其成本。

本课的关键要点

• 嵌套循环连接 在嵌套循环中迭代行——对于具有支持索引的小表快速，对于大型未索引表非常慢；是唯一支持非等式条件的算法。
• 哈希连接 从较小的表构建内存中的哈希表并进行探测——对于基于等式连接的大型未索引表高效，但内存密集。
• 合并连接 同时读取两个预排序的流——当数据已经按顺序排列（例如通过索引）且连接为等式时理想；作为额外好处以排序顺序生成结果。
• 所有三种算法都支持 等式 连接；只有嵌套循环也支持 范围 条件。
• 您通过 索引、内存设置（work_mem）和 查询结构 影响规划器的选择——而不是通过在 SQL 中指定算法。
• 始终使用 EXPLAIN ANALYZE 验证实际使用的是哪个算法以及时间花费在哪里。