散列连接算法

哈希连接算法用于执行自然连接或等值连接操作。哈希连接算法背后的概念是将每个给定关系的元组划分到集合中。划分是根据连接属性上的相同哈希值完成的。哈希函数提供哈希值。在算法中使用哈希函数的主要目标是减少比较次数，提高完成关系连接操作的效率。

例如，假设有两个元组a和b，它们都满足连接条件。这意味着它们在连接属性上具有相同的值。假设元组a和b都包含哈希值i。这意味着元组a应该在a_i中，元组b应该在b_i中。因此，我们只需比较a_i中的元组a与b_i中的元组b。我们不需要比较任何其他分区中的元组b。因此，哈希连接操作就是这样工作的。

散列连接算法

//Partition s//
for each tuple ts in s do begin
i = h(ts [JoinAttrs]);
Hsi = Hsi U {ts};
end
//Partition r//
for each tuple tr in r do begin
i = h(tr[JoinAttrs]);
Hri = Hri U {tr};
end
//Perform the join operation on each partition//
for i= 0 to nh do begin
	read Hsi and build an in-memory hash index on it;
	for each tuple tr in Hri do begin
               probe the hash index on Hsi to locate all tuples 
	       such that ts[JoinAttrs] = tr[JoinAttrs];
	    for each matching tuple ts in Hsi do begin
		add tr ⋈ ts to the result;
	    end
	end
end

这是哈希连接算法，我们计算了两个给定关系r和s的自然连接。算法中使用了各种术语

t_r ⋈ t_s：它定义了元组t_r和t_s的属性连接，然后通过投影去除重复属性。

t_r 和 t_s：它们分别是关系r和s的元组。

让我们通过以下步骤理解哈希连接算法

步骤1：在算法中，首先我们对关系r和s进行了分区。

步骤2：分区后，我们对每个分区对i（使用for循环i = 0到n_h）执行单独的索引嵌套循环连接。

步骤3：为了执行嵌套循环连接，它首先在每个s_i上创建一个哈希索引，然后用r_i中的元组进行探测。在算法中，关系r是探测输入，关系s是构建输入。

使用哈希连接算法有一个好处，即si上的哈希索引是内置在内存中的，因此为了获取元组，我们不需要访问磁盘。将较小的输入关系用作构建关系是很好的。

哈希连接中的递归分区

递归分区是指系统重复对输入进行分区，直到构建输入的每个分区都适合内存。当n_h的值大于或等于内存块的数量时，需要递归分区。由于缓冲区块可能不足，一次性拆分关系变得困难。因此，最好通过重复的传递来拆分关系。在一次传递中，我们可以将输入拆分为几个分区，因为有足够的块可用作输出缓冲区。每个通过传递构建的桶都单独读取，并在下一个传递中进一步分区以创建更小的分区。此外，在不同的传递中，哈希函数是不同的。因此，最好使用递归分区来处理这种情况。

哈希连接中的溢出

哈希表中的溢出条件发生在构建关系s的任何分区i中，原因如下：

情况1：当s_i上的哈希索引大于主内存时，发生溢出条件。

情况2：当构建关系中有多个元组在连接属性上具有相同的值时。

情况3：当哈希函数不具备随机性和均匀性特征时。

情况4：当某些分区比平均值有更多元组而其他分区有更少元组时，这种类型的分区称为倾斜。

处理溢出

我们可以使用各种方法处理哈希表溢出。

• 使用调整因子

我们可以通过使用调整因子增加分区数量来处理少量倾斜。调整因子是一个小值，它增加了分区数量。因此，它将有助于减少每个分区的预期大小，包括它们的哈希索引小于内存大小。不幸的是，使用调整因子使用户对分区大小保守。因此，溢出仍然可能发生。然而，使用调整因子适用于处理小溢出，但不足以处理哈希表中的大溢出。

因此，我们还有两种处理溢出的方法。

1. 溢出解决

溢出解决方法在构建阶段检测到哈希索引溢出时应用。溢出解决的工作方式如下：

它找到任何分区i的s_i，如果其大小大于内存大小。它再次通过不同的哈希函数将此类构建关系s_i划分为更小的分区。同样，它通过新的哈希函数对探测关系r_i进行分区，并且只连接那些具有匹配分区的元组。但是，这是一种不太谨慎的方法，因为这种方法等待这种情况发生，然后采取必要的措施来解决问题。

2. 溢出避免

溢出避免方法在分区时采用谨慎的方法，以避免在构建阶段发生溢出。溢出避免的工作方式如下：

它首先将构建关系s划分为几个小分区，然后合并其中一些分区。这些分区以每个合并分区都适合内存的方式进行合并。同样，它将探测关系r划分为s上的合并分区。但是，在这种方法中，r_i的大小无关紧要。

如果s中的大量元组在连接属性上具有相同的值，则溢出解决和溢出避免方法都可能在某些分区上失败。在这种情况下，最好使用块嵌套循环连接，而不是应用哈希连接技术来完成这些分区上的连接操作。

哈希连接的成本分析

为了分析哈希连接的成本，我们假设哈希连接中没有发生溢出。我们只考虑两种情况：

1. 不需要递归分区

我们需要完全读取和写入关系r和s以对其进行分区。为此，总共需要2(b_r + b_s)块传输。术语b_r和b_s是包含关系r和s记录的块数。两个关系都读取每个分区一次以获得更多的b_r + b_s块传输。然而，这些分区可能比b_r + b_s占用了稍微更多的块，这导致部分填充的块。访问这些部分填充的块可能包括大约每个关系2n_h的开销。因此，哈希连接成本估计需要：

块传输次数 = 3(b_r + b_s) + 4n_h

在这里，我们可以忽略4n_h的开销值，因为它远小于b_r + b_s值。

磁盘寻道次数 = 2(Γb_r/b_bꓶ + Γb_s/b_bꓶ) + 2n_h

在这里，我们假设每个输入缓冲区分配了b_b块，并且构建和探测阶段对于关系的每个n_h分区只需要一次寻道，因为我们可以顺序读取每个分区。

2. 需要递归分区

在这种情况下，每个传递将每个分区的大小减少M-1的预期因子，并且传递重复直到每个分区的大小最多为M块。因此，为了分区关系s，我们需要：

传递次数 = Γlog_M-1(b_s) - 1ꓶ

构建和探测关系分区所需的传递次数相同。因为在每个传递中，s的每个块都被读取和写入，并且需要总共2b_sΓlog_M-1(b_s) - 1ꓶ块传输来拆分关系s。因此，哈希连接成本估计需要：

块传输次数 = 2(b_r + b_s)Γlog_M-1(b_s) - 1ꓶ + b_r + b_s

磁盘寻道次数 = 2(Γb_r/b_bꓶ + Γb_s/b_bꓶ)Γlog_M-1(b_s) - 1ꓶ

在这里，我们假设为每个分区分配b_b块进行缓冲。此外，我们忽略了构建和探测阶段相对较少的寻道次数。

因此，如果主内存的大小增加或很大，哈希连接算法可以进一步改进。

混合哈希连接

这是一种哈希连接类型，适用于执行内存大小相对较大但构建关系仍无法完全放入内存的连接操作。因此，混合哈希连接算法解决了哈希连接算法的缺点。