第九讲 Join 算法

1. 为什么我们需要 Join

我们对关系数据库中的表【tables】进行规范化【normalize】，这样我们就减少了信息的冗余和浪费的空间，但是现在我们为了可以响应传入的查询【Query】，我们必须把这些分离的东西重新组合在一起，以重建原始元组，而不会丢失任何信息，这就是 Join 要做的。

2 Join 算法

我们本节将重点关注使用内等联接算法【inner equijoin algorithms】执行二元连接（两个表）。

可以调整这些算法以支持其他连接。
多路【Multi-Way】连接主要存在于研究文献中。

一般来说，我们希望较小的表始终是查询计划【QueryPlan】中的左表【Left Tabe】（左指的是它位于 Join 操作符的左边）（“外部表【outer table】”）。

优化器在生成物理计划【physical plan】时将（尝试）解决这个问题。

3. Join 操作符

在前面讲排序算法时，我们认识了查询计划。并且也看到了 SQL 被转换为查询计划的操作符树。

在 Join 的操作符实现中，我们有两个方面需要考虑：

考虑点 1：输出【Output】：连接运算符【Join Operator】向查询计划树中的父操作符发送哪些数据？
考虑点 2：成本分析标准：我们如何确定两种算法中，那种连接算法最优？

3.1 操作符输出

对于在连接属性【join attributes】上匹配的元组 r ∈ R 和元组 s ∈ S，将 r& s 连接在一起形成一个新元组。

输出内容可能有所不同：

取决于处理模型【processing model】，比如如果是排序-归并 Join【Sort Merge Join】，那么数据是有序的，但是如果是哈希 Join，那么数据就是无序的
取决于存储模型【storage model】，比如行存储还是列存储，数据的组织是不同的
取决于查询【Query】中的数据要求

3.1.1 操作符输出：DATA（直接输出数据）

提前物化【Early Materialization】：将外部元组和内部元组中的属性值复制到新的输出元组中。

缺点：在表非常宽的时候，我们将有非常多的属性，我们拷贝了很多用不到的属性
优点：查询计划中的后续操作符永远不需要返回基表来获取更多数据，因为连接操作符返回的数据就是完整的。

3.1.2 操作符输出：Record ID

延迟物化【Late Materialization】：仅复制连接键【Join Keys】以及匹配元组的Record ID。

优点：非常适合列存储，因为 DBMS 不会复制查询不需要的数据。
缺点：后面进行映射操作时，可能需要回基表

3.2 成本分析标准【Cost Analysis Criteria】

假定：

表 R 占据 M 个页面，R 表中有 m 个元组
表 S 占据 N 个页面，S 表中有 n 个元组

成本指标：用于计算连接【Join】所使用的 IO 数量。

我们将忽略计算机计算的成本，我们也忽略操作符的输出成本【output cost】，因为这取决于数据，而我们尚无法计算。

3.2.1 Join VS Cross Product

我们这里区分一下 Join 和笛卡尔积的区别：

R⨝S 是最常见的运算，因此必须仔细优化。
R×S 后进行选择【selection】的效率很低，因为笛卡尔积很大。

有很多降低连接成本的算法，但没有一种算法可以在所有场景下都有效。

注：很少有系统回采用笛卡尔积，因为它太慢了，除非是查询指定进行笛卡尔积操作。

3.2.2 Join 算法

嵌套循环连接【Nested Loop Join】

Simple / Stupid
Block
Index

排序合并连接【Sort Merge Join】
哈希连接【Hash Join】

3.2.2.1 嵌套循环连接【Nested Loop Join】

愚蠢的嵌套循环连接

我们首先认识左表/外表和右表/内表，我们要做的就是，为外表中的每一个元组，我们遍历内表中的每一个元组，如果它满足连接匹配的条件，那么我们就将其写入输出（我们暂不考虑输出的方式是 DATA 还是 Record ID）。

注：我们在查询计划汇总，将外表放在左侧，这是约定。

问：为什么这个算法很愚蠢？
答：对于 R 中的每个元组，它扫描 S 一次

Cost = M + (m ∙ N)

例子：

Table R: M = 1000, m = 100,000

Table S: N = 500, n = 40,000

假设页大小为 4 KB pages → 大约总占用 6 MB

Cost Analysis: → M + (m ∙ N) = 1000 + (100000 ∙ 500)

= 50,001,000 IOs

假定 0.1 ms/IO

Total time ≈ 1.3 hours

那如果将小表作为外表呢？

Cost Analysis: → N + (n ∙ M) = 500 + (40000 ∙ 1000)

= 40,000,500 IOs

假定 0.1 ms/IO

Total time ≈ 1.1 hours

块嵌套循环连接

对于每一个外表中的块【block】或者页【page】，我们从内表中加载出一块【block】/页【page】，然后对于每个外表块中的元组，我们遍历内表块中的每一个元组，如果它满足连接匹配的条件，那么我们就将其写入输出。

该算法执行较少的磁盘访问，对于 R 中的每个块，它扫描 S 一次

Cost: M + (M ∙ N )

在这种算法中，我们需要三个 Buffer Page，两个用于输入，一个用于输出。

例子

Table R: M = 1000, m = 100,000

Table S: N = 500, n = 40,000

Cost Analysis: → M + (M ∙ N) = 1000 + (1000 ∙ 500)

= 501,000 IOs

假设 0.1 ms/IO

Total time ≈ 50 seconds

如果说我们的 Buffer Pool 有 B 个页可以用呢？？

那么我们使用 B-2 个页来扫描外表
使用一个页用于内表
使用一个页用于输出

因为我们使用 b-2 个缓冲来扫描外表 R ,因此：

Cost: M + ( M / (B-2) ∙ N)

如果外表完全可以被内存容纳呢？？即(B > M+2)

Cost: M + N = 1000 + 500 = 1500

假设 0.1 ms/IO

Total time ≈ 0.15 seconds

索引嵌套循环连接

为什么基本的嵌套循环连接如此糟糕？

答：对于外表中的每个元组，我们必须执行顺序扫描以检查内表中的匹配项。

因此，我们可以通过使用索引来查找匹配的内表来避免顺序扫描。

假设每个索引探测的成本是每个元组的常数 C 倍（C 依赖于索引）：

Cost: M + (m ∙ C)

3.2.2.2 排序归并连接算法【Sort Merge Join】

第一阶段：排序【sort】

根据连接键【Join Keys】对两个表进行排序。
我们可以使用上节课谈到的外部归并排序算法，当然其他算法也是可以的。

第二阶段：合并【merge】

使用游标遍历两个已排序的表（我们在这里是同时遍历两个表），并输出匹配的元组。
根据连接类型【Join Type】，可能需要回溯【backtrack】。

例子：

SELECT R.id, S.cdate

FROM R JOIN S ON R.id = S.id

WHERE S.value > 100

1️⃣ 首先是我们第一个步骤，排序，连接键是各自表的id

2️⃣ 排序后产生的输出

3️⃣ 然后开始第二步骤，归并，首先我们分别获取各自表上最开始处的游标，

4️⃣ 然后按照连接键条件进行对比，然后我们将连接的元组，放到我们的输出缓冲区中

5️⃣ 然后我们增长内部表的游标向下滑动，然后排序后的 S 表的第二个元素依然匹配连接条件，将其写入输出缓冲区，

6️⃣ 增长内部表的游标，现在rid = 100 ,sid = 200，rid < sid ，我们增长 rid 的游标

7️⃣ 然后 rid = sid = 200，将连接元组输出到缓冲区

8️⃣ 我们继续增长外部表的游标，sid = 400，而 rid = 200，因此需要再增长 rid

9️⃣ 此时，我们发现 rid 再次等于 200 了，基于我们记录的一些元数据，我们内部表需要回溯到 sid = 200处

🔟 现在我们继续比较，并将连接元组写到输出缓冲区

继续循环往复，指导内外表遍历完。

排序归并连接算法的成本：

Sort Cost (R): 2M ∙ (1 + ⌈ logB-1 ⌈M / B⌉ ⌉)

Sort Cost (S): 2N ∙ (1 + ⌈ logB-1 ⌈N / B⌉ ⌉)

Merge Cost: (M + N) 这里假设无回溯

Total Cost: Sort + Merge

合并阶段最坏的情况是两个关系【Relation】中所有元组的连接属性【Join Keys】包含相同的值。
Total Cost = (M ∙ N) + (排序成本)

Table R: M = 1000, m = 100,000

Table S: N = 500, n = 40,000

With B =100 buffer pages

both R and S can be sorted in two passes:

Sort Cost (R) = 2000 ∙ (1 + ⌈log99 1000 /100⌉)

= 2000 ∙ 2

= 4000 IOs

Sort Cost (S) = 1000 ∙ (1 + ⌈ log99 500 / 100⌉)

= 1000 ∙ 2

= 2000 IOs

Merge Cost = (1000 + 500) = 1500 IOs →

Total Cost = 4000 + 2000 + 1500 = 7500 IOs →

假定 0.1 ms/IO

Total time ≈ 0.75 seconds