database - 哈希完全外连接如何工作？

Question

我知道哈希左外连接的算法是在右表上构建一个哈希表，然后遍历左表并在哈希表中搜索是否有匹配项，但是完整的外连接如何工作？扫描完左表中的值后，您仍然需要一种方法来获取右表中左侧没有匹配项的元组。

Answer 1

在遍历探测记录时，您会记录哪些正确的元组在构建表中找到了匹配项。您只需将每个匹配的布尔值设置为 true。作为算法的最后一步，您扫描构建表并输出之前不匹配的所有元组。

据我所知，RDBMS 中没有使用另一种策略：构建左右元组的组合哈希表。将该表视为从哈希键到左元组列表和右元组列表的映射。通过遍历两个输入表将所有元组添加到哈希表来构建该表。在使用完所有元组之后，遍历哈希表一次并相应地输出等式组（所有左元组或所有右元组或等式组中所有左元组和所有右元组的叉积）。

后一种算法非常适合内存中的工作负载（例如在客户端应用程序中）。前者适用于极大（或不可预测）的大探针输入，因此 RDBMS 使用那个。