Database System （七）

type

status

date

slug

summary

介绍

让我们从最简单的问题开始：什么是连接（join）？

如果你还记得那个 SQL 项目，你可能还记得写过类似这样的语句：

以及其他类似的语句。

这实际上意味着你有两个关系表，R 和 S，并基于连接条件将它们组合成一个新关系。

也就是说，对于 R 中的每一条记录 rᵢ，在 S 中找到所有满足连接条件的记录 sⱼ，然后生成一个新行 <rᵢ, sⱼ> 作为输出结果（包含 r 的所有字段和 s 的所有字段）。

SQL 课程的讲义是一个非常好的资源，可以帮助你进一步理解连接到底是什么。

在我们讨论各种不同的连接算法之前，我们需要先搞清楚：当一个新的连接关系 <rᵢ, sⱼ> 被生成时，会发生什么。

每当我们计算一个连接的代价时，我们不会考虑将连接结果写入磁盘的成本。这是因为我们假设连接的输出会被 SQL 查询中稍后的其他操作符直接消费。

很多时候，这些操作符可以直接从内存中读取连接结果，而不需要将其写入磁盘。

如果你现在觉得这有些困惑也不用担心；我们会在“查询优化”模块中重新讨论这个问题。但现在你需要记住的一点是：

最终写入成本不包括在我们的连接成本模型中！

简单的嵌套循环连接（Simple Nested Loop Join）

让我们从最简单的策略开始。假设我们有一个由 B 页组成的缓冲区，现在我们希望基于连接条件 θ 将两个表 R 和 S 连接起来。

从最朴素的策略开始，我们可以对 R 中的每条记录，去 S 中查找所有匹配的记录，然后输出所有匹配的组合。

这种策略叫做 简单嵌套循环连接（Simple Nested Loop Join，简称 SNLJ）。你可以把它想象成两个嵌套的 for 循环：

图示部分说明了：

外层循环从 R 中取出一条记录；

内层循环遍历 S 的所有记录进行匹配；

匹配成功的记录对被加入结果。

分析与成本

从表面上看这个策略很简单，但本课程关注的是查询优化，尤其是最小化 I/O 开销。从这个角度来说，这种方案其实很差。

原因是我们对 R 中的每一条记录，都要扫描 S 的每一页，去找可能的匹配项。

其 I/O 成本为：

[R] + |R| * [S]

其中：

[R] 表示 R 的页数；

|R| 表示 R 中的记录数；

[S] 表示 S 的页数。

虽然我们可能通过交换 R 和 S 的顺序稍微优化一些，但总体来说这并不是一个好策略。

注意：

SNLJ 不会带来 |R| 次的 I/O 来读取 R，因为我们每页只读一次；

实际的做法更像是：

“对 R 中的每一页 pᵣ：对该页中的每条记录 r：

对 S 中的每一页 pₛ：对该页中的每条记录 s 进行连接”。

由于读取是以页为单位进行的，我们无法只读取单条记录。

页为单位的嵌套循环连接（Page Nested Loop Join）

显然，我们不希望对 R 中的每条记录都去读取 S 的每一页。那么我们能不能做得更好？

一个改进的方法是：对 R 的每一页，读取 S 的每一页，然后将这些页中所有的记录进行匹配。也就是说，对 R 的每一页 pᵣ，取出其中所有记录，与 S 中每一页 pₛ 的所有记录进行匹配。对 R 的每一页都执行这样的过程。

这被称为 页级嵌套循环连接（Page Nested Loop Join，PNLJ）。

伪代码如下：

图示部分说明了：

外层循环以页为单位从 R 中读取；

然后内层以页为单位从 S 中读取；

然后在两页中的所有记录之间进行匹配；

匹配的记录对被加入输出结果。

成本分析：

这种方法的 I/O 成本会好一些，约为：

[R] + [R] × [S]

[R] 表示 R 的页数；

[S] 表示 S 的页数。

优化建议：

若想进一步降低成本，可以将较小的关系（R 或 S）放在外层循环中。

请记住这一点，当你被问到“如何用最低成本执行连接操作”时，它可能是解题关键。

块嵌套循环连接（Block Nested Loop Join）

页为单位的嵌套循环连接已经比之前好很多了！但我们仍然没有充分利用好我们的缓冲区。

假设我们有 B 页缓冲区，但算法实际上只用了 3 页：

一页用于 R

一页用于 S

一页作为输出缓冲区

回忆一下，我们读取 S 的次数越少越好。所以如果我们将 B-2 页留给 R，然后把 S 中的每条记录都与 R 中这个“块”（chunk）内的所有记录进行匹配，就可以大大减少 I/O 成本！

在这个连接方式中：

B - 2 页用于 R 的块

1 页用于读取 S

1 页作为输出缓冲区

这被称为 块嵌套循环连接（Block Nested Loop Join），也称为 分块嵌套循环连接（Chunk Nested Loop Join）。

核心思想：

利用缓冲区尽可能多地缓存 R 的记录块，以减少对 S 的读取次数。

因为对于每个块，我们只读取一次 S 的每一页，块越大，意味着总的 I/O 越少。

伪代码如下：

图示解释：

使用 B 页缓冲区；

其中 B-2 页缓存 R 的块；

对 S 的每一页，与整个块中所有记录做匹配；

每个匹配对会被加入结果。

成本分析：

这个算法的 I/O 成本为：

[R] + ⌈[R] / (B - 2)⌉ × [S]

这是一个大大的改进！

现在我们真正利用了 B 页缓冲区，减少了对 S 的读取次数。

Visual Comparison of Loop Joins

左：Simple Nested Loop Join（简单嵌套循环连接）

每条记录从 R 中读取；

对每条记录都完整扫描一次 S；

图中红色箭头很多，表示 S 被重复读取了很多次；

I/O 成本高：[R] + |R| × [S]

中：Page Nested Loop Join（页嵌套循环连接）

每一页从 R 中读取；

对每一页的所有记录一起扫描 S；

红色箭头减少了，每页只对应一轮对 S 的扫描；

成本更优：[R] + [R] × [S]

右：Block Nested Loop Join（块嵌套循环连接）

将 R 分成 多个块（每个块最多 B-2 页）；

每个块只扫描一次 S；

图中粗大的箭头表示用更大的内存块批量处理；

最优的 I/O 成本：

[R] + ⌈[R] / (B - 2)⌉ × [S]

总结：

连接方式	优点	I/O 成本	内存利用
Simple NLJ	实现简单	最差	低
Page NLJ	成本较低	较好	一般
Block NLJ	成本最低	最优	最好（用满 `B-2` 页）

索引嵌套循环连接（Index Nested Loop Join）

有时候，**块嵌套循环连接（Block Nested Loop Join）**并不是最好的选择。

如果我们在 S 的连接字段上有索引（也就是我们用来连接的字段），那么查找 rᵢ 在 S 中的匹配项会非常快。

这种方式被称为 索引嵌套循环连接（Index Nested Loop Join）。

伪代码如下：

I/O 成本：

I/O 成本为：

[R] + |R| ×（在 S 中查找匹配记录的成本）

这里：

[R] 是扫描 R 所需的页数；

|R| 是 R 中的记录数；

每条记录都要用索引去 S 中查找匹配的记录。

查找成本取决于使用的索引类型，例如：

替代索引结构（Alternative 1, 2, 3）

聚簇（clustered）与非聚簇（unclustered）索引的区别

如果使用的是 B+ 树索引，则查找从根节点开始，计算访问到目标记录所需的 I/O 次数。

你可以参考课程讲义中 B+ 树部分的 聚簇性（Clustering） 和 **I/O 次数估计（Counting I/O’s）**章节来进一步理解。

哈希连接（Hash Join）

在前面介绍的所有连接算法中，我们的目标都是寻找匹配的记录。而哈希表在这方面非常擅长。即使没有索引，我们也可以将 R 的记录构造为一个大小为 B-2 页的哈希表，加载到内存中，然后对 S 中的每条记录进行查找，看是否能在 R 的哈希表中匹配上。

这种策略叫做 朴素哈希连接（Naive Hash Join）。其 I/O 成本为：

[R] + [S]

这是目前介绍的策略中最优的：高效、便宜、简单。

❗ 朴素哈希连接的问题：

这种方法的前提是：R 的数据量能完全装入内存，即 R ≤ B - 2 页。而实际上很多时候做不到。

解决方案：Grace Hash Join（渐进式哈希连接）

我们将 R 和 S 多次哈希划分成多个小分区，每个分区最多 B - 2 页，这样就能把这些分区分别加载进内存执行朴素哈希连接。

步骤如下：

将 R 和 S 按相同的哈希函数分区成 R₁, R₂, ..., Rₙ 和 S₁, S₂, ..., Sₙ；

对于每对分区 (Rᵢ, Sᵢ)：

如果它们都 ≤ B-2 页，直接执行朴素哈希连接；

如果有一个分区 > B-2 页，则继续对大分区进行进一步哈希，直到可处理为止；

将较小分区加载到内存建立哈希表，与大分区进行匹配。

成本分析：

Grace Hash Join 的总成本包括：

哈希分区的成本（读所有页并将其写成多个分区）；

各子分区上进行朴素哈希连接的成本。

实际成本取决于哈希过程需要重复多少轮。

注意：键值偏斜（Key Skew）问题

当很多记录具有相同哈希键时，它们会被划分到同一个桶中，造成部分分区远大于其他分区，导致：

哈希划分不均衡；

某些分区永远无法 fit into memory；

多次哈希仍无法解决问题。

例如：如果连接字段只有 "yes" 一个值，不论用什么哈希函数，全都落在一个桶里。

Grace Hash Join 性能优异但对键值分布非常敏感，使用时必须小心处理 Key Skew 问题。

排序-合并连接（Sort-Merge Join）

在某些情况下，我们希望连接的输出是按某一列排序的。此时就可以先对两个表 R 和 S 按连接键排序，然后使用合并过程执行连接操作。

🧠 核心思想：

先对 R 和 S 进行排序；

使用两个游标分别从 R 和 S 的起始位置出发；

不断比较两侧游标指向的记录：

如果 R.sid < S.sid，前移 R；

如果 R.sid > S.sid，前移 S；

如果相等，就产生一个匹配 <rᵢ, sⱼ>，并尝试收集所有重复项。

成本分析：

Sort-Merge Join 的成本：

即：

排序阶段（两个表）；

线性合并扫描（匹配阶段）。

示例演示：

两张表：

左表 R：

右表 S：

匹配过程（图示箭头指示）：

28 = 28：输出匹配，继续前移 S，再输出一次；

31 = 31：输出所有与 31 匹配的组合：

lubber × 101

lubber × 102

lubber2 × 101

lubber2 × 102

总输出：

🔧 程序伪代码（简化版）：

一个重要优化：

合并排序优化：如果内存足够，我们可以在排序阶段直接合并；

若能为每个块分配一页缓冲区，可以边排序边合并，节省 I/O 成本；

这是 Sort-Merge Join 的常见优化策略，称为 归并排序融合（merge + join fusion）。

一个重要的优化（An Important Refinement）

在 Sort-Merge Join 中，有一个非常关键的优化点：

如果内存足够大，能为 R 和 S 的每个“有序段（run）”分配一页缓冲区，那么我们可以将排序的“归并阶段”和连接操作合并，从而节省 2×([R]+[S]) 次 I/O。

实施这个优化的步骤：

分别排序 R 和 S，使用完整的缓冲池，直到它们都“几乎排序好了”（也就是分段数量比较少）；

计算 R 和 S 的段数（runs），如果 runs(R) + runs(S) ≤ B - 1（即缓冲区能为所有段分配页），那么可以直接在归并排序中合并两表完成 join，节省 2×([R]+[S]) I/O；

如果不满足上述条件，即段数太多，我们还是可以选择只对其中一个表（较小的那个）进行完整排序，然后对另一个表做多路归并 join。

例子：只对 S 完全排序

如果我们只对 S 完全排序，那么它只有一个 run，只需要 1 页缓冲区。

只要满足：

runs(R) + 1 ≤ B - 1

那么我们就可以：

为每个 R 的段分配一页；

给 S 分配 1 页；

在 join 阶段中同时完成排序和合并操作，节省 2×[R] 次 I/O。

例子：只对 R 完全排序

类似地，如果 runs(S) + 1 ≤ B - 1，我们可以选择先将 R 完全排序，然后执行类似的优化，节省 2×[S] I/O。

无法优化怎么办？

如果两个表的段数都太多，不满足任一条件，那我们就无法做这个优化。这时候：

还是可以继续执行正常的 Sort-Merge Join；

虽然成本高一些，但仍然是可行的；

有时候我们就是必须接受无法抄近路的现实。