【CMU 15-445】11 Joins 算法

Slides
Notes

1. Joins 连接

好的数据库设计的目标是将信息重复量降至最低。这就是我们基于规范化理论编写表的原因。因此，重建原始表需要连接。

Operator Output

对于在联接属性上匹配的元组 r∈R 和元组 s∈S ，联接运算符会将 r 和 s 连接到一个新的输出元组中。

实际上，连接操作符生成的输出元组的内容各不相同。它取决于DBMS的处理模型、存储模型和查询本身：

• 数据：将外部表和内部表中属性的值复制到元组中，并将其放入仅用于该操作符的中间结果表中。这种方法的优点是，查询计划中的未来运算符永远不需要返回到基表来获取更多数据。缺点是这需要更多的内存来物化整个元组。
• 记录ID：DBMS只复制连接 key 和匹配元组的记录ID。这种方法非常适合列存储，因为DBMS不会复制查询不需要的数据。这就是所谓的后期物化。

Cost 分析

我们将用来分析不同联接算法的 cost 指标将是用于计算 joins 的磁盘I/O数量。这包括从磁盘读取数据以及将中间数据写出磁盘所引起的I/O。

本课程使用的变量：表 R 中有 M 个页面，M 个元组；表 S 中 N 个页面，N 个元组。

2. Nested Loop Join 嵌套循环连接

在high-level 上，这种类型的联接算法由两个嵌套的for循环组成，这两个循环迭代两个表中的元组并比较每个唯一的元组。如果元组与连接谓词匹配，则输出它们。外部for循环中的表称为外部表，而内部for循环中的表称为内表。

DBMS总是希望使用“较小”的表作为外部表。较小的可以是元组的数量或页面的数量。DBMS还希望在内存中缓冲尽可能多的外部表。如果可能，利用索引在内部表中查找匹配项。

Simple Nested Loop Join

对于外部表中的每个元组，将其与内表中的每个元组进行比较。这是最糟糕的情况，假设每个元组都有一个磁盘I/O要读取(即没有缓存或访问局部性)。Cost：M+(m×N)

Block Nested Loop Join

对于外部表中的每个块，从内表中获取每个块，并比较这两个块中的所有元组。该算法执行的磁盘访问较少，因为我们针对每个外部表块而不是每个元组扫描内部表。Cost：M+(M×N)

如果DBMS具有可用于计算联接的B个缓冲区，则它可以使用B−2个缓冲区来扫描外部表。它将使用1个缓冲区来保存来自内部表的一个块，并使用1个缓冲区来存储连接的输出。

Index Nested Loop Join

以前的嵌套循环连接算法执行得很差，因为DBMS必须执行顺序扫描来检查内表中的匹配。但是，如果数据库已经为连接键上的一个表建立了索引，则可以使用该索引来加快比较速度。外层的表将是没有索引的表。内表将是带有索引的表。

假设每个索引探测器的成本是每个元组的某个常量值C。成本：M+(m×C)

3. Sort-Merge Join

High-level是根据这两个表的 join key 对它们进行排序。然后对已排序的表执行顺序扫描，以计算联接。如果一个或两个表已按联接属性排序，则此算法非常有用。

此算法的最坏情况是两个表中所有元组的联接属性包含相同的值。这在真实的数据库中不太可能发生。

• 阶段1-排序：首先根据连接属性对两个输入表进行排序。
• 阶段2-合并：并行扫描两个已排序的表，并发出匹配的元组。

假设DBMS有B个缓冲区可用于该算法：

4. Hash Join

哈希联接算法的high-level思想是使用哈希表根据它们的联接属性将元组分割成更小的块。这减少了DBMS计算联接时每个元组需要执行的比较次数。哈希联接只能用于完整联接键上的等联接 equi-joins。

如果元组 r∈R 和元组 s∈S 满足联接条件，则它们的联接属性值相同。如果该值被hash为某个值i，则R元组必须在桶 ri 中，而S元组必须在桶 si 中。因此，只需要将桶 ri 中的R个元组与桶 si 中的S个元组进行比较。

Basic Hash Join

• 阶段1-Build：扫描外部关系并使用连接属性上的hash函数 h1 填充hash表。哈希表中的key 是联接属性。该值取决于实施情况。
• 阶段2-Probe：扫描内部关系，对每个元组使用哈希函数 h1，跳到哈希表中的某个位置，找到匹配的元组。由于哈希表中可能存在冲突，因此DBMS将需要检查联接属性的原始值，以确定元组是否真正匹配。
  如果DBMS知道外部表的大小，则联接可以使用静态哈希表。如果它不知道大小，则联接必须使用动态哈希表或允许溢出页面。

Grace Hash Join / Hybrid Hash Join (Grace哈希连接/混合哈希连接)

当表不能放入主内存时，您不希望缓冲池管理器不断地调入和调出表。Grace Hash Join是基本Hash Join的扩展，它还将内部表 hash 到写到磁盘的分区中。Grace 这个名字来自20世纪80年代在日本开发的格蕾丝数据库机器。

• 阶段＃1-构建：扫描外部表和内部表，并使用连接属性上的哈希函数 h1 填充哈希表。散列表的桶根据需要写入磁盘。如果单个桶不适合内存，则用户使用第二个散列函数h2（其中h1！=h2）进行分区以进一步划分该桶。
• 阶段＃2-探测：对于每个桶级，检索外部和内部表的相应页面。然后在这两页中对元组执行嵌套循环连接。页面将适合内存，因此此加入操作将很快。
  分区阶段Cost：2×(M+N) —— 两次：从磁盘中读数据 和将数据写出到磁盘

探测阶段Cost：(M+N)

总Cost：3×(M+N)