Lecture#11 Joins Algorithms

1 Joins

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

本课关注双表的内等值连接。原则上我们希望，连接时将小表放到左侧 (作为外表)。

首先要讨论的是：Join 的输出和成本分析。

1.1 Operator Output

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

现实中，Join 操作输出元组内容还取决于 processing model, storage model 和 query 本身。下面列举了几种输出元组的内容：

1️⃣ Data：Join 时，将内表和外表的所有非 Join Attributes 的属性都复制到输出元组中。

又称 提前物化。优点是：Join 之后的操作都无需从原表中重新获取数据；缺点是：需要更多地内存。

2️⃣ Record Ids：Join 时，只将内外表的 Join Attributes 及 record id 复制到输出元组，后续操作自行根据 record id 去原表中获取相关数据。

又称 推迟物化(Late Materialization)。适用于列存储数据库，因为这样 DBMS 不需要复制对于查询没用的属性。

1.2 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

下面介绍的连接算法都有各自的适用场景，没有一个算法可以在所有场景下表现良好，需要具体问题具体分析。

2 Nested Loop Join

也就是暴力循环算法。

总体上来看，这个嵌套循环算法主要由 2 个 for 嵌套，每个 for 分别迭代一个表，如果两个元组符合连接谓词，就输出它们。

在外循环的表叫做外表，在内循环的表叫做内表。以下的讨论中 \(R\) 表是外表，\(S\) 表是内表。

DBMS总是希望小表当做外表，这里的“小”是指占用的页数或者元组个数。DBMS 希望在内存中缓存尽量多的外表，在遍历内表时也可以使用索引加速。

2.1 Simple Nested Loop Join

傻瓜式暴力两层大循环嵌套。

对于外表 \(R\) 的每一个元组，都遍历一遍 \(S\) 表，没有任何缓存机制，没有利用任何局部性。

磁盘 I/O Cost：\(M + (m × N)\)

\(M\) 是读入外表 (\(R\)) 的 I/O 次数，然后对于 \(R\) 表的 \(m\) 个元组，每个都扫描一遍内表 (\(S\))。