合并连接算法

Merge Join 用于对给定的关系 r 和 s 执行自然连接和等值连接。我们使用一种称为Merge Join 算法的算法来执行合并连接。它也被称为Sort-Merge-Join 算法。

合并连接算法

Merge Join 算法如下：

pr = address of first tuple of relation r;
ps = address of first of relation s;
while (ps!=null && pr!=null) do begin
	 ts = tuple to which ps points;
	 Ss = {ts};
	set ps to point the next tuple of relation s;
	done = false;
	while (!done && ps!=null) do begin
		ts? = tuple to which ps points;
		 if (ts?[JoinAttrs] = ts[JoinAttrs])
		   begin
			Ss = Ss U {ts?};
			set ps to point the next tuple of relation s;
			end
		else
		    done = true;
	end 
   tr = tuple to which pr points;
   while (pr !=null && tr [JoinAttrs] < ts[JoinAttrs]) do begin
	for each ts in Ss do begin
	      add ts   ⋈    tr to result;
	  end
	set pr to point nest tuple of r;
          tr = tuple to which pr points;
         end

在算法中，使用了各种术语：

JoinAttrs（连接属性）：它表示关系r ꓵ s的交集中的属性。

r ꓵ s： r ꓵ s 指的是关系 r 和 s 中共同的属性。

t_s ⋈ t_r： t_s 和 t_r 元组属性的连接表达式。在此之后，将投影出重复的属性。

t_s 和 t_r： 这是两个具有相同 JoinAttrs 值的元组。

S_s： 它读取关系中具有相同值的元组组的那些连接属性。

在 Merge Join 算法中，它将每个关系关联一个指针。最初，指针指向关系的第一个元组，然后随着算法的进行而移向下一个。此外，该算法要求每个元组集 S_s 适合内存，即使关系 s 的大小很大。但是，如果对于某些属性值，S_s 似乎大于可用内存大小，我们可以对其执行块嵌套循环连接。如果给定的输入关系 r 和 s 未按连接属性排序，或者其中一个未排序，我们需要在应用 Merge Join 算法之前对其进行排序。

Merge Join 算法的成本分析

如果关系已排序，并且具有连接属性上相同值的元组连续放置。那么我们只需要读取每个元组一次，因此块也将被读取一次。因此，

块传输次数 = b_r + b_s

此外，两个文件中的块传输次数相等。

磁盘寻道次数 = [b_r/b_b] + [b_s/b_b]

这里，b_r 和 b_s 是给定关系 r 和 s 的块数。术语 b_b 表示我们假设为两个关系分配了 b_b 个缓冲区块。但是，我们知道数据传输比磁盘寻道便宜，因此我们应该为每个给定的关系分配多个块。因此，它也将提供额外的内存空间。

混合 Merge Join 算法

混合 Merge Join 与 Merge Join 不同。在 Merge Join 操作中，我们看到在应用 Merge Join 技术之前必须对给定关系进行排序。但是，如果两个连接属性都包含二级索引，那么我们也可以对未排序的元组执行 Merge Join 操作的变体。为此，应用的 Merge Join 算法将通过索引扫描记录，这将能够以排序的方式检索记录。因此，此类 Merge Join 操作的变体会导致一个明显的缺点，即：

• 记录可能位于不同的文件块中。这意味着它们可能散布在文件的多个块中。因此，为了访问每个元组，我们还需要访问特定的文件块，这是一个昂贵的步骤。

为了避免这种昂贵的访问，我们使用一种称为“混合 Merge Join”的新技术。混合 Merge Join 操作将索引与 Merge Join 相结合。

为了理解混合 Merge Join 操作，让我们举个例子：

假设我们有两个关系，其中一个关系已排序，另一个关系未排序。但是未排序的关系在连接属性上具有二级 B⁺ 树索引。

在这种情况下，最初，混合 Merge Join 过程将合并或组合已排序的关系与二级 B⁺ 树索引的叶条目。然后结果文件将包含来自已排序关系的元组以及未排序关系的元组的地址。此外，结果文件将根据未排序关系的元组地址再次排序，以便在物理存储顺序中高效检索相应元组以完成连接。这种方法称为混合 Merge Join 方法。