# Join Algorithms

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

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

![](https://1008303647-files.gitbook.io/~/files/v0/b/gitbook-legacy-files/o/assets%2F-LMjQD5UezC9P8miypMG%2F-La5GNw04x8dghkKNnFu%2F-La5Hn2OiSCiZACMwgAE%2FScreen%20Shot%202019-03-16%20at%207.37.39%20PM.jpg?alt=media\&token=702a2000-55f9-4927-8f8b-e5c829688e17)

查询时我们就需要通过 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：

![](https://1008303647-files.gitbook.io/~/files/v0/b/gitbook-legacy-files/o/assets%2F-LMjQD5UezC9P8miypMG%2F-La5GNw04x8dghkKNnFu%2F-La5Jfak-pG08NtJc37P%2FScreen%20Shot%202019-03-16%20at%207.45.54%20PM.jpg?alt=media\&token=4d5793e5-1035-4331-bc4d-95f8e235bb9c)

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

* query processing model
* storage model
* query

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

![](https://1008303647-files.gitbook.io/~/files/v0/b/gitbook-legacy-files/o/assets%2F-LMjQD5UezC9P8miypMG%2F-La5GNw04x8dghkKNnFu%2F-La5KYkuE3zEy5hImXRs%2FScreen%20Shot%202019-03-16%20at%207.49.45%20PM.jpg?alt=media\&token=5d9c0b76-0bd8-4224-b105-52edd6b2cb79)

也可以在 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

![](https://1008303647-files.gitbook.io/~/files/v0/b/gitbook-legacy-files/o/assets%2F-LMjQD5UezC9P8miypMG%2F-La89KlvadrrXRPkyto_%2F-La89XKahCxHQe6jJVj7%2FScreen%20Shot%202019-03-17%20at%209.00.27%20AM.jpg?alt=media\&token=60009ac5-df37-46ca-bf73-3b8068f6ec6f)

对 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

![](https://1008303647-files.gitbook.io/~/files/v0/b/gitbook-legacy-files/o/assets%2F-LMjQD5UezC9P8miypMG%2F-La89KlvadrrXRPkyto_%2F-La8DMcn5GbaMxELxDGb%2FScreen%20Shot%202019-03-17%20at%209.17.06%20AM.jpg?alt=media\&token=6c416e55-2162-448f-ad17-94e9bbf92d7f)

每次取 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 上有索引或者临时建一个索引 (只需全表扫描一次)：

![](https://1008303647-files.gitbook.io/~/files/v0/b/gitbook-legacy-files/o/assets%2F-LMjQD5UezC9P8miypMG%2F-La89KlvadrrXRPkyto_%2F-La8He_2aMDqo6wagz7O%2FScreen%20Shot%202019-03-17%20at%209.35.57%20AM.jpg?alt=media\&token=cfa58f87-199b-49e3-8a49-c5812009f7d2)

此时 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

算法如下：

![](https://1008303647-files.gitbook.io/~/files/v0/b/gitbook-legacy-files/o/assets%2F-LMjQD5UezC9P8miypMG%2F-La89KlvadrrXRPkyto_%2F-La8JVXSXIBk4By71Kwa%2FScreen%20Shot%202019-03-17%20at%209.44.00%20AM.jpg?alt=media\&token=58d3a726-ca06-4c79-8aa5-d9f3de63f75c)

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)

![](https://1008303647-files.gitbook.io/~/files/v0/b/gitbook-legacy-files/o/assets%2F-LMjQD5UezC9P8miypMG%2F-La89KlvadrrXRPkyto_%2F-La8OluaWQMtpd0-wPPn%2FScreen%20Shot%202019-03-17%20at%2010.07.03%20AM.jpg?alt=media\&token=a98dcc9a-4af7-4bea-9b61-249235bd2ff0)

这里明确 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

![](https://1008303647-files.gitbook.io/~/files/v0/b/gitbook-legacy-files/o/assets%2F-LMjQD5UezC9P8miypMG%2F-La89KlvadrrXRPkyto_%2F-La8RpW98dA7RvGFMYhB%2FScreen%20Shot%202019-03-17%20at%2010.20.23%20AM.jpg?alt=media\&token=ff044cd3-2e57-4b04-bd82-a76d942ac4c8)

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

![](https://1008303647-files.gitbook.io/~/files/v0/b/gitbook-legacy-files/o/assets%2F-LMjQD5UezC9P8miypMG%2F-La89KlvadrrXRPkyto_%2F-La8SCV9GrYuISXphOsN%2FScreen%20Shot%202019-03-17%20at%2010.22.02%20AM.jpg?alt=media\&token=8753d09f-345f-4dfa-8d46-bc74bf56d46c)

成本分析：

假设我们有足够的 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](https://15445.courses.cs.cmu.edu/fall2018/slides/12-joins.pdf)