ThinkLab

Mindmap

mindmap

一、引言

关系数据库设计通常利用规范化理论来减少冗余，因此查询中经常需要通过连接（Join）来恢复逻辑上的“原始表”。在实际系统中，最核心也最需要优化的是等值连接（Equijoin），尤其是自然连接。

连接算法众多，没有单一算法在所有场景中都最优，因此现代 DBMS 会根据数据规模、索引情况、排序情况、内存大小等动态选择策略。

二、连接算子的构成与输出

连接算子位于查询执行树中间位置，其输出会成为后续算子的输入。连接两个元组 r ∈ R 与 s ∈ S 时，典型的输出是将二者拼接为新的元组。

（一）数据输出方式：Early vs. Late Materialization

数据方式（Data Approach，早物化）

输出完整的新元组（包含所有属性的拷贝）。
后续算子不需回访原表。
更适用于行存储系统（Row Store）。

示例： 假设要连接 Students(id, name, major) 与 Enroll(id, course, grade)，若连接结果还需 GROUP BY，那么提前物化能减少重复回表读取。

记录 ID 方式（Record-ID Approach，晚物化）

仅输出连接键与 record IDs。
更适合列存储系统（Column Store），避免不必要列加载。

示例： 在分析型数据库中，只需要 join key + RID，后续算子会按需从列存取真正需要的列，减少 I/O。

三、基于磁盘 I/O 的连接成本模型

设：

外表 R：M 个数据页，m 条元组
内表 S：N 个数据页，n 条元组

注意：输出结果的 I/O 不计入比较，因为所有算法输出量相同。

四、嵌套循环连接（Nested Loop Join）

（一）朴素嵌套循环（Naïve NLJ）

对外表每个元组，扫描内表所有元组。

成本： [ M + mN ]

示例： 外表 1 万条数据，内表 100 万条数据，则需要比较约 (10^4 \times 10^6 = 10^{10}) 次，非常低效。

（二）块嵌套循环（Block NLJ）

基于数据页而非元组比较，将外表按“页块”加载，从而减少内表扫描次数。

成本： [ M + M \times N ]

若使用 B 个 buffer frame，并把外表缓存成 B−2 页块： [ M + \left\lceil \frac{M}{B-2} \right\rceil N ]

示例：

外表 R = 1000 页
内表 S = 500 页
Buffer = 100 页 [ \left\lceil\frac{1000}{98}\right\rceil = 11 ] 总成本： [ 1000 + 11\times 500 = 6500\ \text{I/O} ] 比朴素 NLJ 高频节省。

（三）索引嵌套循环（Index NLJ）

若内表 join key 上已有索引，则外表逐条查 probe。

成本： [ M + mC ] 其中 C = 每次索引查找成本。

示例： 若内表 S 的 join key 有 B+Tree 索引，并假设一次查找平均需 3 I/O，则 m=10万时需 30万次 I/O，远小于扫描式的 m×N。

五、排序归并连接（Sort-Merge Join）

（一）算法步骤

按 join key 对 R 和 S 排序（多路外排序）
同步扫描两个有序表，对齐 join key

（二）成本

排序成本（外排序算法）：

对于 R： [ 2M\left(1 + \left\lceil \log_{B-1} \left\lceil \frac{M}{B} \right\rceil \right\rceil \right) ] 对于 S：同理

合并成本： [ M + N ]

**最坏情况：**若所有 join key 完全相同，则退化为 M×N，因为每页都需与对方全部比较。

（三）示例

若 R=1000 页，S=500 页，B=100：

排序 R 成本：4000 I/O 排序 S 成本：2000 I/O 合并成本：1500 I/O 总计：约 7500 I/O

适合以下场景：

数据已经排序
输出结果需要排序（GROUP BY 之前等）
数据分布较均匀

六、哈希连接（Hash Join）

（一）基本哈希连接（Basic Hash Join）

步骤

Build 阶段：对外表 R 按 hash function h1 构建哈希表。
Probe 阶段：将内表 S 的元组用 h1 映射到对应 bucket，逐条匹配。

注意： 只适用于 equi-join，因为哈希函数依赖相等性。

（二）优化：Bloom Filter

在构建阶段同时构造 Bloom Filter，用于过滤不可能匹配的内表元组，减少无效 I/O。

示例： 如果外表 join key 仅包含某些 ID 范围，Bloom Filter 可直接让许多内表元组无需磁盘读取。

（三）分区哈希连接（Grace Hash Join）

当内存不足以容纳整个外表哈希表时，需要分区处理。

步骤

使用 h1 将 R 和 S 分区为多个 bucket（可能需要递归分区 h2）。
对每对对应 bucket 执行基本哈希连接。

成本

[ 3(M+N) ]

示例： R 和 S 各 1GB，内存仅 100MB，则需将数据分为多个 100MB 以下的分区，并逐个处理。

（四）偏斜处理（Skew Handling）

若某些 join key 过于频繁（热点 key），可保留热点 bucket 在内存中即时处理，避免多次溢写到磁盘。

七、算法性能比较与适用场景

算法	成本（I/O）	适用场景
简单 NLJ	M + mN	小表与大表 join，小表作为外表
块 NLJ	M + ⌈M/(B−2)⌉N	无索引、中等规模表
索引 NLJ	M + mC	内表 join key 有索引
Sort-Merge Join	M+N+排序开销	数据已排序或结果需要排序
Hash Join	3(M+N)	最常见最稳定的 equi-join 方案

示例解读： 在课堂示例（M=1000，N=500 …）中，哈希连接是最快的（0.45 秒），sort-merge 次之（0.75 秒），NLJ 最慢。

八、总结

连接算法是数据库系统性能的关键环节，各算法有其最优场景：

数据已排序 → Sort-Merge 更优
Join key 有索引 → Index NLJ 最佳
大多数 OLAP / 多表 equi-join → Hash Join 主力
内存不足 → Grace Hash Join 处理大规模数据
小表连接大表 → 小表作为外表的 NLJ 有时足够快

现代 DBMS（如 PostgreSQL、MySQL、DuckDB）会根据统计信息自动选择最优策略，并在必要时使用混合技术（如哈希 + Bloom Filter）。

15445-12-JoinAlgorithms