嵌套循环连接算法

在前一节中，我们学习了连接以及各种类型的连接。在本节中，我们将了解嵌套循环连接算法。

嵌套循环连接是一种包含一对嵌套 for 循环的连接。为了执行对两个关系 **r** 和 **s** 的嵌套循环连接，即 θ 连接，我们使用一种称为**嵌套循环连接算法**的算法。计算如下：

r ⋈ _θ s

其中 r 被称为连接的**外层关系**，s 被称为**内层关系**。这是因为 r 的 for 循环包含了 s 的 for 循环。

嵌套循环连接算法

让我们讨论一下嵌套循环连接算法。

for each tuple tr in r do begin
        for each tuple ts in s do begin
              test pair (tr, ts) to test if they satisfy the given join condition ?
              if test satisfied
                 add tr . ts to the result;
      end inner loop
end outer loop

在算法中，t_r 和 t_s 分别是关系 r 和 s 的元组。符号 t_r. t_s 是通过连接元组 t_r 和 t_s 的属性值而构建的一个元组。

通过算法，我们理解了以下几点：

• 嵌套循环连接不需要像线性文件扫描那样对数据进行任何索引访问。
• 嵌套循环连接不关心给定的连接条件。它适用于每个给定的连接条件。
• 嵌套循环连接算法本质上是昂贵的。这是因为它会计算并检查给定两个关系中的每一对元组。

嵌套循环连接算法的成本分析

为了分析嵌套循环连接算法的成本，我们考虑元组对的数量为 n_r * n_s。这里，n_r 表示关系 r 中的元组数量，n_s 表示关系 s 中的元组数量。为了计算成本，对关系 s 执行完整扫描。因此：

最坏情况下的总块传输次数 = n_r * b_s + b_r

最坏情况下的总寻道次数 = n_r + b_r

这里，b_s 和 b_r 分别是包含关系 r 和 s 元组的块的数量。

在最佳情况下，关系 r 和 s 都有足够的内存同时容纳。因此，每个块只读取一次。因此：

最佳情况下的总块传输次数 = b_r + b_s。

所需的总寻道次数 = 2(n_r + b_r)

如果给定的关系中的任何一个能完全放入内存，那么必须将其用作内层关系。这是因为我们将只读取内层关系一次。因此：

这种情况下的总块传输次数 = b_r + b_s

所需的总寻道次数 = 2(n_r + b_r)

块嵌套循环连接

块嵌套循环连接是嵌套循环连接的一个变体，其中内层关系的每个块都与外层关系的每个块配对。在缓冲区大小不足以将整个关系容纳到内存中的情况下，块嵌套循环连接通过基于每块而不是每元组处理关系来大大节省块访问。在每个块对中，块嵌套循环连接将一个块中的每个元组与另一个块中的每个元组配对，以产生所有元组对。它只配对满足给定连接条件的元组，并将它们添加到结果中。

块嵌套循环连接算法

用于执行块嵌套循环连接的算法称为**块嵌套循环连接算法**。我们将在此算法中使用相同的关系 r 和 s。

           for each block br of r do begin
             for each block bs of s do begin
               for each tuple tr in br do begin
                 for each tuple ts in bs do begin
                   test pair (tr, ts) to determine if they pass the given join condition
                    if test passed
                   add tr . ts to the result;
             end
           end
        end
   end

块嵌套循环连接算法的成本分析

块嵌套循环连接和嵌套循环连接算法的成本之间存在主要区别。在块嵌套循环连接的最坏情况下，内层关系 s 中的每个块仅为外层关系 r 中的每个块读取一次。另一方面，嵌套循环连接为外层关系 r 中的每个元组读取内层关系 s 中的每个元组一次。因此，在块嵌套循环连接中：

最坏情况下的总块传输次数 = b_r * b_s+ b_r

所需的总寻道次数 = 2 * b_r

这里，b_r 和 b_s 分别是包含给定关系 r 和 s 记录的块的数量。此外，s（内层关系）的每次扫描只需要一次寻道，而 r（外层关系）需要每个块一次寻道。在最佳情况下，内层关系完全放入内存。因此：

最佳情况下的总块传输次数 = b_r + b_s

所需的总寻道次数 = 2(n_r + b_r)

在给定的关系 r 和 s 都无法完全放入内存的情况下，将内层关系即 s 用作外层关系是更有效的。

改进嵌套循环和块嵌套循环连接的性能

在理解了两种连接后，我们评估可以进一步提高这两种连接的性能

1. 如果在等值连接或自然连接中，连接属性构成了给定内层关系 s 的一个键，那么一旦找到第一个匹配项，内层循环就会为每个外层关系元组终止。
2. 在块嵌套循环连接算法中，我们不使用磁盘块，而是可以使用可以放入内存的最大尺寸，并且还留出足够的空间用于内层关系 s 的缓冲区及其输出。结果是，这将减少内层关系的扫描次数并最小化成本。
3. 我们可以以交替的方式沿正向和反向方向扫描内层循环。这种方法通过保持磁盘块请求的顺序来减少磁盘访问的需求。请求的顺序也有助于重用上一次扫描后留在缓冲区中的数据。
4. 如果内层循环的连接属性上存在索引，我们可以用高效的索引查找来代替文件扫描。这种类型的连接方法称为**索引嵌套循环连接**。索引嵌套循环连接可以与现有索引或为连接求值而创建的临时索引一起使用。这是一种优化技术，用于提高嵌套循环连接的性能。