CMU15-445 数据库系统播客：数据库系统 Join 算法与原理

一个优秀的数据库系统会智能地运用这些算法。这正是 SQL 这种声明式语言的强大之处：用户只需描述“需要什么”，而无需关心“如何获取”，底层的数据库系统会负责选择最高效的路径来执行查询。

在关系型数据库系统中，连接（Join）操作是核心且至关重要的一环。数据库通过规范化（Normalization）将数据拆分到不同表中以减少信息冗余。然而，当我们需要获取跨多个表的综合信息时，就必须使用 Join 操作，将被拆分的表重新组合，以重建数据间的逻辑关系，确保信息完整。

连接操作的核心概念

在深入探讨具体算法之前，我们首先需要理解评估和执行连接操作的一些基本原则。

连接的评估基准：I/O 成本

一个查询在执行时会被数据库的查询优化器转换成一个“查询计划树”。这个树的叶子节点代表对数据表的访问，而中间节点则是各种操作符，Join 就是其中最重要的一种。

评估 Join 算法优劣的主要标准是其磁盘 I/O 成本。因为磁盘的读写速度远慢于内存，I/O 操作往往是数据库性能的最大瓶颈。为了量化分析，我们通常设定如下变量：

表 R：占用M个磁盘页（Page），包含m条元组（Tuple）。表 S：占用N个磁盘页，包含n条元组。

在后续的成本分析中，我们主要关注 Join 操作本身的 I/O 开销，而不计算最终结果输出的开销，因为后者对于所有算法来说都是相同的。

外层表与内层表的选择：为何“小表驱动大表”？

在执行 Join 时，查询计划会指定一个外层表（Outer Table，或称驱动表）和一个内层表（Inner Table，或称被驱动表）。在查询计划树中，左侧输入通常是外层表，右侧是内层表。

一个核心的优化原则是：尽可能选择小表作为外层表。这里的“小”通常指占用磁盘页（Blocks/Pages）较少，或者在某些算法中指元组数量（Rows）较少。

为什么这个选择如此重要？我们可以通过一些基础的 Join 算法 I/O 公式来直观理解：

对于块嵌套循环连接（Block Nested Loop Join），其 I/O 成本公式为：外层表 I/O + (外层表块数 × 内层表 I/O)。

大表 R (1000页) 作外层，小表 S (500页) 作内层：成本为M + (M × N) = 1000 + (1000 × 500) = 501,000次 I/O。小表 S (500页) 作外层，大表 R (1000页) 作内层：成本为N + (N × M) = 500 + (500 × 1000) = 500,500次 I/O。 在此算法中，总 I/O 差别不大，但外层表越小，外层循环次数越少。

对于索引嵌套循环连接（Index Nested Loop Join），其成本与外层表的元组数量密切相关。其 I/O 成本公式为：外层表 I/O + (外层表元组数 × 内层表索引查找成本)。

大表 R (m=100,000) 作外层：成本为M + (m × C) = 1000 + (100,000 × C)。小表 S (n=40,000) 作外层：成本为N + (n × C) = 500 + (40,000 × C)。

其中C是单次索引查找的成本。显然，外层表的元组数越少，对内层表的索引“探测”次数就越少，总 I/O 成本也显著降低。

结论：外层表扮演着“驱动”的角色，它的每一行（或每一块）都会触发一次对内层表的操作。选择小表作为外层表，可以有效减少驱动次数，从而大幅降低对内层表的扫描或查找总成本，这是 Join 优化的一个基础出发点。

连接的输出方式：物化 vs. 记录 ID

连接操作符找到匹配的元组后，如何将结果传递给上层操作符？主要有两种方式：

数据物化 (Materialization)：将匹配元组中所有需要的属性值复制出来，形成一个全新的输出元组。

优点：后续操作符无需再访问原始表，因为所有信息都已备齐。缺点：如果涉及的属性很多，生成的元组会很“宽”，占用大量内存且复制成本高。

延迟物化 (Late Materialization)：只输出连接键和匹配元组的记录 ID（Tuple ID）。

优点：输出的中间结果非常小，节省内存。这在列式存储数据库中尤其高效，因为它避免了提前读取查询最终不需要的列。缺点：当上层操作符需要其他属性时，必须根据记录 ID 回溯到原始数据页去获取，这可能引入额外的随机 I/O。如果连接的选择性很低（即匹配的元组很多），回溯成本可能会非常高昂。

三大主流连接算法

数据库系统主要实现了三类连接算法：嵌套循环连接、排序合并连接和哈希连接。

嵌套循环连接 (Nested Loop Join)

这是最基础、最直观的连接算法，其思想类似于编程中的嵌套for循环。

简单嵌套循环 (Simple/Stupid Nested Loop Join)

对于外层表的每一条元组，遍历内层表的所有元组进行比较。这种方式性能极差，因为会导致对内层表的重复全盘扫描。

块嵌套循环 (Block Nested Loop Join)

这是对简单版本的巨大改进。算法按块（Page/Block）进行循环，而不是按元组。对于外层表的每一块，遍历内层表的所有块。

索引嵌套循环 (Index Nested Loop Join)

如果内层表的连接键上存在索引，系统就可以利用该索引来避免全表扫描。对于外层表的每一条元组，使用其连接键值去探测 (Probe)内层表的索引，快速定位匹配的元组。

适用场景： 在OLTP (联机事务处理)场景中极为常见，因为外键列上通常建有索引。动态索引： 即使预先没有索引，如果优化器判断创建临时索引的成本低于全表扫描的成本，它甚至可以在查询执行期间动态创建索引，查询结束后再丢弃。

排序合并连接 (Sort-Merge Join)

此算法通过预先排序来优化连接过程，分为两个阶段：

排序阶段 (Sort Phase)：如果数据尚未排序，使用外部归并排序（当数据大于内存时）或快速排序（当数据可载入内存时）分别对两个表按连接键进行排序。合并阶段 (Merge Phase)：使用两个指针（游标）同步地扫描两个已排序的表。比较指针处的键值，移动键值较小的那个指针。如果键值相等，则找到一个匹配，输出结果。此时，需要特别处理重复键。例如，当内层表有多个与外层表当前元组匹配的键时，需要固定外层表指针，移动内层表指针直到不匹配。如果外层表下一条元组的键值仍然相同，内层表的指针需要回溯到重复键的起始位置，以确保所有组合都被找到。

优势场景：

数据已序：当一个或两个表已经按连接键排序（例如，连接键上存在聚簇索引），可以免去排序成本。结果需排序：当查询包含ORDER BY子句，且排序键恰好是连接键时，此算法可以直接产出有序结果，避免了额外的排序操作，实现“一举两得”。最坏情况：如果所有元组的连接键都相同，合并阶段会退化成类似嵌套循环的行为，性能急剧下降。但这种情况在现实中极为罕见。

哈希连接 (Hash Join)

哈希连接是现代数据库系统中最快、最主流的连接算法，它利用哈希函数“分而治之”。如果两个元组的连接键相等，那么它们的哈希值也必然相等。因此，我们只需在哈希到同一位置的元组“桶”内进行比较即可。

基本哈希连接算法

构建阶段 (Build Phase)：选择外层表（通常是小表），扫描它并使用哈希函数h1在内存中构建一个哈希表。哈希表的键是连接键的哈希值，值通常是元组本身或其引用。探测阶段 (Probe Phase)：扫描内层表，对每一条元组的连接键计算相同的哈希值，然后去哈希表中查找（探测）。如果找到，再比较原始连接键值以确认精确匹配（处理哈希冲突）。

优化：布隆过滤器 (Bloom Filter)

在构建哈希表的同时，可以额外构建一个布隆过滤器。这是一种高效的概率型数据结构（本质是一个位图），用于快速判断一个元素是否可能在一个集合中。

特性：它绝不会漏报（False Negative，如果它说“无”，就一定没有），但可能误报（False Positive，如果它说“有”，可能实际没有）。它体积小、速度快，可以完全放入 CPU 缓存。工作方式：在探测内层表时，先用布隆过滤器检查。如果过滤器返回“无”，则该元组一定不匹配，可直接跳过，避免了访问内存或磁盘中的哈希表。这被称为旁路信息传递 (Sideways Information Passing)。

Grace 哈希连接 (处理大数据)

当外层表太大，无法在内存中为其完整构建一个哈希表时，基本哈希连接就会因频繁的磁盘交换而失效。Grace 哈希连接（或称分区哈希连接）解决了这个问题。

分区阶段 (Partition Phase)：使用一个哈希函数h1，将两个表都散列成多个分区（Partitions），并写入磁盘。h1的选择要保证同一连接键的元组一定进入相同的分区对（例如，R表的分区i和 S表的分区i）。连接阶段 (Join Phase)：依次将每一对分区（如 R 的分区1 和 S 的分区1）加载到内存中。因为每个分区都足够小，可以为其构建内存哈希表，然后在该分区内部执行基本的哈希连接。递归分区：如果分区后某个分区依然过大，无法载入内存，系统会对该分区再次使用一个新的哈希函数h2进行递归分区，直到所有子分区都足够小。此方法巧妙地将随机 I/O 转换为了高效的顺序 I/O。

算法选择与总结

现代数据库的查询优化器内置了成本估算模型，它会综合考虑表大小、数据分布特征、内存可用性、索引情况和查询需求（如是否需要排序）等因素，为每个查询动态选择最优的 Join 算法。

下表总结了我们示例中不同算法的性能对比：

（注：示例基于 R 表 M=1000页, m=100k元组; S 表 N=500页, n=40k元组；索引查找成本 C=2 IO）

核心结论

在大多数情况下，哈希连接是性能最佳的选择，尤其对于大规模数据的等值连接。排序合并连接在特定场景下有奇效：当数据已排序或查询结果需要按连接键排序时，它可能是最优选。此外，对于不等值连接（如>或<）和范围连接，排序合并连接通常优于哈希连接。索引嵌套循环连接是OLTP轻量级查询的首选，特别是当外层表结果集很小且内层表有可用索引时。

一个优秀的数据库系统会智能地运用这些算法。这正是 SQL 这种声明式语言的强大之处：用户只需描述“需要什么”，而无需关心“如何获取”，底层的数据库系统会负责选择最高效的路径来执行查询。这些经典的算法思想不仅在单机数据库中至关重要，在分布式数据库中也同样适用，只是将磁盘 I/O 成本替换为了开销更高的网络 I/O 成本。