Hash Join（ハッシュ結合）

📌

Hash Joinとは

Hash Join（ハッシュ結合）は、小さい方のテーブルからインメモリのハッシュテーブルを構築（Build）し、大きい方のテーブルの各行でハッシュテーブルを検索（Probe）する2フェーズのJOINアルゴリズムです。計算量は O(N + M) で、ソートを必要とせず、等価結合において最も高速なアルゴリズムの一つです。

電話帳で名前を探す場面を想像してください。まず50音順の索引ページ（ハッシュテーブル）を作ります。次に、探したい名前のリストを上から順番に、索引を使って素早く該当ページを開きます。一つの名前につき索引を1回引くだけなので、名簿を最初から最後まで探す必要がありません。この「O(1)ルックアップ」がHash Joinの効率の源です。

PostgreSQLではHash Joinとして実装されており、等価結合のデフォルトとして最も頻繁に選ばれるアルゴリズムです。EXPLAINで Hash Join と表示されればこのアルゴリズムが使われています。ハッシュテーブルの構築にはwork_memが使われ、メモリに収まらない場合はディスクにスピルします。

-- 等価結合（=）でインデックスなし → Hash Joinが最適
SELECT e.name, d.dept_name
FROM employees e JOIN departments d ON e.dept_id = d.id;

-- PostgreSQLのEXPLAINで確認
EXPLAIN SELECT e.name, d.dept_name
FROM employees e JOIN departments d ON e.dept_id = d.id;
-- → "Hash Join" + "Hash" と表示されればHash Joinが使われている

図1: ビルドフェーズ — ハッシュテーブルの構築

小さい方のテーブル（departments）の各行を結合キー（id）でハッシュし、バケットに格納します。ハッシュ関数により、同じキーは常に同じバケットに入ります。

図2: プローブフェーズ — ハッシュテーブルの検索

大きい方のテーブル（employees）の各行でハッシュテーブルを検索します。O(1)でバケットにアクセスし、マッチ/ミスを判定します。

図3: ハッシュテーブルの構造

ハッシュテーブルは結合キーをハッシュ関数に通してバケット番号を決定します。同じキーは同じバケットに入り、O(1)でアクセスできます。