嵌套循环连接算法

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

嵌套循环连接是包含一对嵌套for循环的连接。在两个关系上执行嵌套循环连接，即θr和年代，我们使用的算法叫做嵌套循环联接算法。计算过程如下:

r⋈_θ年代

这里r被称为外部关系s是内部关系连接的。这是因为r的for循环包含了s的for循环。

嵌套循环连接算法

我们来讨论一下嵌套循环连接的算法:

对于每个元组tr在r中，对每个元组t开始年代在s中开始test pair (t)rt年代)来测试它们是否满足给定的连接条件?如果测试满足，则加tr。t年代结果;结束内循环结束外循环

在算法中，t_r和t_年代分别是关系r和关系s的元组。符号t_r。t_年代元组是通过连接元组的属性值来构造的吗_r和t_年代。

在算法的帮助下，我们理解了以下几点:

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

嵌套循环连接算法的代价分析

为了分析嵌套循环连接算法的开销，考虑若干对元组为n_r* n_年代。在这里,n_r指定关系r和n中元组的个数_年代指定关系s中元组的个数。为了计算开销，对关系s执行一次完整扫描。

最坏情况下的块传输总数= n_r* b_年代+ b_r

在最坏情况下所需的查找总数= n_r+ b_r

在这里,b_年代和b_r分别为保存关系r和关系s元组的块的数量。

在最好的情况下，关系r和s都有足够的内存，可以同时放入内存中。因此，每个块只读取一次。因此,

在最佳情况下，块传输总数= b_r+ b_年代。

所需的搜索总数= 2(n)_r+ b_r)

如果给定的任何一个关系完全符合记忆，则必须使用该关系作为内部关系。这是因为我们只会阅读一次内部关系。因此,

在这种情况下，块传输的总数= b_r+ b_年代

所需的搜索总数= 2(n)_r+ b_r)

块嵌套循环连接

块嵌套循环连接是嵌套循环连接的一种变体，其中内部关系的每个块与外部关系的每个块配对。块嵌套循环连接在缓冲区大小小到足以将整个关系保存到内存中的情况下节省了主要块访问。它通过基于每个块而不是基于每个元组处理关系来实现这一点。在每对块中，块嵌套循环连接将一个块中的每个元组与另一个块中的每个元组配对，以生成所有对元组。它只将满足给定连接条件的元组与结果配对。

块嵌套循环连接算法

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

对于每个block brr开始于每个块b年代对于每个元组t，都是s开始的r在br是否为每个元组开始年代在b年代开始测试对(trt年代)来确定它们是否通过了给定的连接条件(如果test通过了)r。t年代结果;结束结束结束结束

块嵌套环联接算法的代价分析

块嵌套循环连接和嵌套循环连接算法的开销有很大的区别。在块嵌套循环连接的最坏情况下，对于外部关系r中的每个块，内部关系s中的每个块只读取一次。另一方面，对于外部关系r中的每个元组，嵌套循环连接读取内部关系s中的每个元组一次。因此在块嵌套循环连接中，

最坏情况下的块传输总数= b_r* b_年代+ b_r

请求的总次数= 2 * b_r

在这里,b_r和b_年代分别为保存给定关系r和s的记录的块的数目。此外，每次扫描s(内部关系)只需要一次寻道，而r(外部关系)每个块需要一次寻道。在最好的情况下，内部关系完全适用于记忆。因此,

在最佳情况下，块传输总数= b_r+ b_年代

所需的搜索总数= 2(n)_r+ b_r)

如果给定的关系r和s都不能完全装入内存，则使用内部关系(即s)作为外部关系是有效的。

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

在了解了这两个连接之后，评估了这两个连接的性能可以进一步提高:

1. 如果在对等连接或自然连接中，连接属性在给定的内部关系上形成一个键，那么只要找到第一个匹配，就终止每个外部关系元组的内部循环。
2. 代替在块嵌套循环连接算法中使用磁盘块，我们可以使用内存中可以容纳的最大大小，并为内部关系及其输出的缓冲区留出足够的空间。因此，它将减少内部关系的扫描次数，并将成本降至最低。
3. 我们可以用一种交替的方式在正向和反向对内环进行扫描。这种方法通过保持对磁盘块的请求的顺序来减少磁盘访问需求的数量。对请求进行排序还有助于重用上次扫描后留在缓冲区中的剩余数据。
4. 如果在内部循环的join属性上存在索引，我们可以用高效的索引查找替换文件扫描。这种类型的连接方法称为索引嵌套循环连接。索引嵌套循环连接既可以与现有索引一起使用，也可以与临时索引一起使用，临时索引是为计算连接而创建的。它是提高嵌套循环连接性能的一种优化技术。