database - ハッシュ完全外部結合はどのように機能しますか？

Question

ハッシュ左外部結合のアルゴリズムは、右側のテーブルにハッシュテーブルを作成してから、左側のテーブルをループしてハッシュテーブルを検索し、一致するものがあるかどうかを確認することですが、完全外部結合はどのように機能しますか？左側のテーブルの値をスキャンした後でも、左側に一致するものがなかった右側のテーブルのタプルを取得する方法が必要になります。

Answer 1

プローブレコードをループしながら、ビルドテーブルで一致するものを見つけた正しいタプルを記録します。一致したものごとにブール値をtrueに設定するだけです。アルゴリズムの最後のパスとして、ビルドテーブルをスキャンし、以前に一致しなかったすべてのタプルを出力します。

私の知る限り、RDBMSでは使用されていない別の戦略があります。左右のタプルの結合されたハッシュテーブルを作成します。そのテーブルを、ハッシュキーから左タプルのリストと右タプルのリストへのマップとして扱います。両方の入力テーブルをループして、すべてのタプルをハッシュテーブルに追加することにより、そのテーブルを作成します。すべてのタプルが消費された後、ハッシュテーブルを1回繰り返し、それに応じて等式グループを出力します（等式グループ内のすべての左タプルまたはすべての右タプル、またはすべての左タプルとすべての右タプルの外積）。

後者のアルゴリズムは、（クライアントアプリケーションのように）メモリ内のワークロードに適しています。前者は、非常に（または予測できない）大きなプローブ入力に適しているため、RDBMSはそれを使用します。