Join Algorithms

在关系型数据库中，我们常常通过规范化 (Normalization) 设计避免信息冗余；因此查询时，就需要通过 Join 将不同 table 中的数据合并来重建数据。

以课程伊始时的 table 为例，通过将 Artist 与 Album 之间的多对多关系拆成 Artist, ArtistAlbum 以及 Album 三个 tables 来规范化数据，使得数据存储的冗余减少：

查询时我们就需要通过 Join 来重建 Artist 与 Album 的完整关系数据。

Join Algorithms

本课主要讨论 join 两个 tables 的过程。首先需要讨论的是：

• Join 的输出

• Join 的成本分析

Join Operator Output

逻辑上 Join 的操作的结果是：对任意一个 tuple $r \in R$ 和任意一个在 Join Attributes 上对应的 tuple $s \in S$ ，将 r 和 s 串联成一个新的 tuple：

Join 操作的结果 tuple 中除了 Join Attributes 之外的信息与多个因素相关：

• query processing model

• storage model

• query

我们可以在 Join 的时候将所有非 Join Attributes 都放入新的 tuple 中，这样 Join 之后的操作都不需要从 tables 中重新获取数据：

也可以在 Join 的时候只复制 Join Attributes 以及 record id，后续操作自行根据 record id 去 tables 中获取相关数据。对于列存储数据库，这是比较理想的处理方式，被称为 Late Materialization。

I/O Cost Analysis

由于数据库中的数据量通常较大，无法一次性载入内存，因此 Join Algorithm 的设计目的，在于减少磁盘 I/O，因此我们衡量 Join Algorithm 好坏的标准，就是 I/O 的数量。此外我们不需要考虑 Join 结果的大小，因为不论使用怎样的 Join Algorithm，结果集的大小都一样。

以下的讨论都建立在这样的情景上：

• 对 R 和 S 两个 tables 做 Join

• R 中有 M 个 pages，m 个 tuples

• S 中有 N 个 pages，n 个 tuples

本节要介绍的 Join Algorithms 罗列如下：

• Nested Loop Join

  • Simple

  • Block

  • Index

• Sort-Merge Join

• Hash Join

不同的 Join Algorithms 有各自的适用场景，需要具体问题具体分析。

Nested Loop Join

Simple Nested Loop Join

对 R 中的每个 tuple，都全表扫描一次 S，是一种暴力解法，它的成本为：

$$M + (m \times N)$$

举例：

假设：

• M = 1000， m = 100,000

• N = 500, n = 40,000

成本：

$M + (m\times N) = 1000 + (100000 \times 500) = 50,000,100 \ I/Os$

假设 0.1 ms/IO，则总时长约为 1.3 小时

如果我们使用小表 S 作为 Outer Table，那么：

$N + (n\times M) = 500 + (40000 \times 1000) = 40,000,500 \ I/Os$

则总时长约为 1.1 小时。

Block Nested Loop Join

每次取 R 中一个 block 的所有 tuples 出来，让它们同时与 S 中的所有 tuples Join 一次，它的成本为：

$$M + (M \times N)$$

举例：

假设：

• M = 1000, m = 100,000

• N = 500, n = 40,000

成本：

使用大表 M 作为 Outer Table，成本为：

$M + (M \times N) = 1000 + (1000 \times 500) = 501,000 \ I/Os$

总共用时约 50 秒。

使用小表 S 作为 Outer Table，成本为：

$N + (N \times M) = 500 + (1000 \times 500) = 500,500 \ I/Os$

以上的计算都假设 DBMS 只为 Nested Loop Join Algorithm 分配 3 块 buffers，其中 2 块用于读入，1 块用于写出；若 DBMS 能为算法分配 B 块 buffers，则可以使用 B-2 块来读入 Outer Table，1 块用于读入 Inner Table，1 块用于写出，此时，成本为：

$$M + (ceil(M / (B-2)) \times N)$$

如果 Outer Table 能够直接放入内存中，则成本为 $M + N$ 。

Index Nested Loop Join

之前的两种 Nested Loop Join 速度慢的原因在于，需要对 Inner Table 作多次全表扫描，若 Inner Table 在 Join Attributes 上有索引或者临时建一个索引 (只需全表扫描一次)：

此时 Join 的成本为：

$$M + (m \times C)$$

其中 C 为 index probe 的成本。

小结：

从上面的讨论中，我们可以导出以下几个结论：

• 总是选择小表作为 Outer Table

• 尽量多地将 Outer Table 缓存在内存中

• 扫描 Inner Table 时，尽量使用索引

Sort-Merge Join

Sort-Merge Join 顾名思义，分为两个阶段：

• Phase #1: Sort

  • 根据 Join Keys 对 tables 进行排序

  • 可以使用外部归并排序

• Phase #2: Merge

  • 同时从两个 tables 的一端开始扫描，对 tuples 配对

  • 如果 Join Keys 并不唯一，则有可能需要 backtrack

算法如下：

Sort Merge 的成本分析如下：

• Sort Cost (R): $2M \times (log M / log B)$
• Sort Cost (S): $2N \times (log N / log B)$
• Merge Cost: $M + N$

举例：

假设：

• M = 1000, m = 100,000

• N = 500, n = 40,000

• B = 100

• 0.1ms/IO

成本：

• Sort Cost (R): $2000 \times (log 1000 / log 100) = 3000 \ I/Os$
• Sort Cost (S): $1000 \times (log 500 / log 100) = 1350 \ I/Os$
• Merge Cost: $1000 + 500 = 1500 \ I/Os$
• Total Cost = $3000 + 1350 + 1500 = 5850 \ I/Os$
• Total Time = 0.59 secs

Sort-Merge Join 的最坏情况就是当两个 tables 中的所有 Join Keys 都只有一个值，这时候 Join 的成本变为： $M \times N + sort \ cost$

小结：

Sort-Merge Join 适用于：

• 当 tables 中的一个或者两个都已经按 Join Key 排好序，如聚簇索引

• SQL 的输出必须按 Join Key 排好序

Hash Join

核心思想：

如果分别来自 R 和 S 中的两个 tuples 满足 Join 的条件，它们的 Join Attributes 必然相等，那么它们的 Join Attributes 经过某个 hash function 得到的值也必然相等，因此 Join 的时候，我们只需要对两个 tables 中 hash 到同样值的 tuples 分别执行 Join 操作即可。

Basic Hash Join Algorithm

本算法分为两个阶段：

• Phase #1: Build

  • 扫描 Outer Table，使用 hash function $h_1$ 对 Join Attributes 建立 hash table $T$
• Phase #2: Probe

  • 扫描 Inner Table，使用 hash function $h_1$ 获取每个 tuple 在 T 中的位置，在该位置上找到配对成功的 tuple(s)

这里明确 T 的定义：

• Key：Join Attributes

• Value：根据不同的查询要求及实现来变化

  • Full Tuple：可以避免在后续操作中再次获取数据，但需要占用更多的空间

  • Tuple Identifier：是列存储数据库的理想选择，占用最少的空间，但之后需要重新获取数据

但 Basic Hash Join Algorithm 有一个弱点，就是有可能 T 无法被放进内存中，由于 hash table 的查询一般都是随机查询，因此在 Probe 阶段，T 可能在 memory 与 disk 中来回移动。

Grace Hash Join

当两个 table 都无法放入 memory 时，我们可以：

• Phase #1: Build

  • 将两个 tables 使用同样的 hash function 进行 partition，使得可能配对成功的 tuples 进入到相同的Partition

• Phase #2: Prob

  • 对两个 tables 的每一对 partition 分别进行 Join

如果每个 partition 仍然无法放入内存中，则可以递归地使用不同的 hash function 进行 partition，即 recursive partitioning：

成本分析：

假设我们有足够的 buffers 能够存下中间结果：

• Partitioning Phase:

  • Read + Write both tables

  • 2(M+N) I/Os

• Probing Phase

  • Read both tables

  • M+N I/Os

举例：

假设：

• M = 1000, m = 100,000

• N = 500, n = 40,000

• 0.1ms/IO

计算：

• $3 \times (M + N) = 4,500 \ I/Os$
• 0.45 secs

如果 DBMS 已经知道 tables 大小，则可以使用 static hash table，否则需要使用 dynamic hash table

Summary

Algorithm	IO Cost	Example
Simple Nested Loop Join	$M + (m \times N)$	1.3 hours
Block Nested Loop Join	$M + (M \times N)$	50 secs
Index Nested Loop Join	$M + (m \times C)$	20 secs
Sort-Merge Join	$M + N + (sort \ cost)$	0.59 secs
Hash Join	$3(M + N)$	0.45 secs

总结

Hash Join 在绝大多数场景下是最优选择，但当查询包含 ORDER BY 或者数据极其不均匀的情况下，Sort-Merge Join 会是更好的选择，DBMSs 在执行查询时，可能使用其中的一种到两种方法。

参考

slides