database - 散列全外连接如何工作？

Question

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

Answer 1

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

据我所知，有一种替代策略未在 RDBMS 中使用:构建一个左右元组的组合哈希表。将该表视为从哈希键到左元组列表和右元组列表的映射。通过遍历两个输入表将所有元组添加到哈希表来构建该表。在所有元组都被消耗完后，遍历哈希表一次并相应地输出相等组(所有左元组或所有右元组或相等组中所有左元组和所有右元组的叉积)。

后一种算法适用于内存中的工作负载(如客户端应用程序)。前者适用于极(或不可预测)大的探针输入，因此 RDBMS 使用该输入。