cmu445_Join_Algorithm

本节主体部分介绍以下三种Join算法：

Nested Loop Join（Simple、Block、Index）
Sort-Merge Join
Hash Join

为什么进行Join操作

为了避免保存重复信息，我们一般会通过范式将表数据保存在数据库中。我们利用Join操作来还原重建原始的表数据。以课程伊始时的 table 为例，通过将 Artist 与 Album 之间的多对多关系拆成 Artist, ArtistAlbum 以及 Album 三个 tables 来规范化数据，使得数据存储的冗余减少，查询时我们就需要通过 Join 来重建 Artist 与 Album 的完整关系数据。

本课时主要讨论了Join操作的output以及I/O分析两个方面的内容。

Join 输出

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

Join 操作的结果 tuple 中除了 Join Attributes 之外的信息与多个因素相关：（1）query processing model、（2）storage model、（3）query

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

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

Join 算法以及I/O代价分析

由于数据库中的数据量通常较大，无法一次性载入内存，因此 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

Nested Loop Join

Simple Nested Loop Join

对 R 中的每个 tuple，都全表扫描一次 S，是一种暴力解法，它的成本为： $M+(m\times N)$ ,一般将小表当做Outer表，放在关系代数表达式语法树的最左边。

Block Nested Loop Join

每次取 R 中一个 block 的所有 tuples 出来，让它们同时与 S 中的所有 tuples Join 一次，它的成本为 $M+(M+N)$ 。

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

$M+\lceil (\frac{M}{B-2}) \rceil\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$ 为进行一次索引探测的成本。

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

总是选择小表作为 Outer Table、尽量多地将 Outer Table 缓存在内存中；
扫描 Inner Table 时，尽量使用索引；

Sort-Merge Join

分为两个阶段：

Phase #1: Sort
- 根据 Join Keys 对 tables 进行排序
- 可以使用外部归并排序
Phase #2: Merge
- 同时从两个 tables 的一端开始扫描，对 tuples 配对
- 如果 Join Keys 并不唯一，则有可能需要 backtrack

成本分析：可分为三部分：

Sort Cost (R): $2M\times log_B^M$
Sort Cost (S): $2N\times log_B^N$
Merge Cost: $M+N$

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 对 Join Attributes 建立 hash table T，对于T表：
- Key： Join Attributes
- Value：根据不同的查询要求及实现来变化。Full Tuple：可以避免在后续操作中再次获取数据，但需占用更多的空间；Tuple Identifier：列存储数据库的理想选择，占用最少的空间，但之后需要重新获取数据。

Phase #2: Probe

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

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

Grace Hash Join

当两个 table 都无法放入 memory 时，我们可以使用Grace hash join，其过程为

Phase #1: Build

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

Phase #2: Prob

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

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

成本分析：

Partitioning Phase:

Read + Write both tables
2(M+N) I/Os

Probing Phase

Read both tables
(M+N) I/Os

总结

算法	I/O成本	时间举例
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 会是更好的选择，DBMS在执行查询时，可能使用其中的一种到两种方法。

转载自：https://zhenghe.gitbook.io/open-courses/cmu-15-445-645-database-systems/join-algorithms