双管道连接算法

在上一节中，我们了解了流水线以及系统创建和实现流水线以通过按需驱动或生产者驱动的流水线来评估多个操作的方法。

在这里，我们将讨论一种用于实现流水线的评估算法。

在从任何特定系统访问数据时，会使用几种操作。其中一些操作本质上是阻塞操作，而另一些则不是。阻塞操作是指在检查完所有输入元组之前不输出任何结果的操作。

例如，像哈希连接这样的操作是一个阻塞操作，因为它在输出任何结果之前，需要完全获取并分区其两个输入。另一方面，索引嵌套循环可以在其外部关系获得元组后立即输出结果元组。因此，它在其外部关系上是流水线的，在其索引输入上是阻塞的。这是因为在执行索引嵌套循环之前，索引已完全创建。

但在某些情况下，我们希望对两个输入执行连接操作。然而，这两个输入尚未排序，并且我们需要将它们放入连接操作的流水线中。在这种情况下，我们使用一种称为双流水线连接的替代方法。双流水线连接技术使用一种称为双流水线连接算法的评估算法来实现流水线。

双流水线连接算法

下面我们描述了双流水线连接算法

doner = false;
dones = false;
r = Ø;
s = Ø;
result = Ø;
while !doner or !dones do
      begin
              if queue is empty, wait until it is not empty;
              t = top entry in the queue;
              if t = Endr then 
                 doner = true
else if t = Ends then
                dones = true
           else if t is from input r
             then
                 begin
                       r = r U {t};
                       result = result U ({t} ⋈ s);
             end
          /* t is from input s */
          else
             begin
                 s = s U {t};
                result = result U (r ⋈ {t});
              end 
end

上述算法在两个输入关系 r 和 s 上执行。假设这两个关系的输入元组是流水线的。提供给 r 和 s 关系的元组被排队在一个队列中进行处理。在算法中，End_r 和 End_s 是特殊队列，它们是文件结束标记。这些特殊队列仅在生成完关系 r 和 s 的所有元组后才被插入到队列中。此外，随着更多元组被添加到关系 r 和 s 中，应该在两个关系上建立适当的索引。保持索引最新可以提高操作的效率。

在此算法中，我们还假设两个输入都适合内存。但是，双流水线连接技术也支持两个输入的大小超过内存大小的情况。这是因为双流水线连接方法可以正常工作，直到可用内存满为止。当内存满时，到那时为止到达的 r 和 s 关系的元组可以分别被视为位于 r₀ 和 s₀ 分区。随后到达的 r 和 s 关系的元组被分配到 r₁ 和 s₁ 分区。尽管分配给 r₁ 和 s₁ 分区的元组不包含在内存索引中，但它们被写入磁盘。此外，在将分配给 r₁ 和 s₁ 的元组写入磁盘之前，它们用于探测 r₀ 和 s₀ 分区。结果，它还以流水线方式完成了 r₁ 与 s₀ 以及 s₀ 与 r₁ 的连接。在完全处理完关系 r 和 s 后，我们计算 r₁ 元组与 s₁ 元组的连接，以完成连接操作。此外，我们可以使用任何连接操作或方法来执行 r₁ 分区与 s₁ 分区的连接。

注意：如果我们通过在任何关系 r 和 s 上使用哈希索引来实现流水线，则这种方法称为双流水线哈希连接方法。