Hash Join、Merge Join、Nested Loop
3つの主要な結合戦略、それぞれのコスト特性、そしてプランナーがどの状況で最適と判断するかを理解します。
「Hash Join、Merge Join、Nested Loop」はCoddyKit上の無料SQL Academyレッスンです。 これはレッスン3/4です。 下記で完全なレッスンを無料で読むことができます。その後、ブラウザ内の組み込みコードエディタと24時間対応のAIチューターでハンズオン演習できます。 これはSQL Academy学習パスの一部であり、ウェブとCoddyKitアプリ全体で進捗が同期されます。 SQL Academyコースには全4レッスンが含まれています。
3 つの結合方式
PostgreSQL には、物理的な結合アルゴリズムが 3 つあります。
- Nested Loop — 外側の各行について、内側をスキャンします
- Hash Join — 内側のハッシュを作成し、外側の行で検索します
- Merge Join — 両側をソートし、並行してマージします
Nested Loop
最も単純な方式で、outer × inner です。内側に適切なインデックスがあり、外側が小さい場合に高速です。
EXPLAIN ANALYZE
SELECT * FROM users u JOIN orders o ON o.user_id = u.id
WHERE u.id = 42;
-- Nested Loop
-- -> Index Scan on users where id = 42 (rows=1)
-- -> Index Scan on orders_user_id_idx (rows=5)Nested Loop が有利な場合
外側の行数が少なく、内側に結合キーのインデックスがある場合、Nested Loop は非常に高速です。最悪計算量は O(outer × inner) です。
Hash Join
一方の側（通常は小さい側）にハッシュテーブルを作成し、もう一方の側の行で検索します。結合キーに有効なインデックスがない状態で、大きなテーブル同士を結合する場合に適しています。
EXPLAIN ANALYZE
SELECT * FROM big_a a JOIN big_b b ON a.key = b.key;
-- Hash Join (cost=10000..50000)
-- -> Seq Scan on big_a
-- -> Hash
-- -> Seq Scan on big_bHash Join が有利な場合
中規模から大規模のテーブルが 2 つあり、結合キーに適切なインデックスがない場合や、Planner が多数の行を必要とする場合に適しています。メモリの制約があり、ハッシュテーブルが work_mem に収まらないとディスクに退避されます。
Merge Join
両側を結合キーでソートし、同時にたどります。両側がすでにソート済みの場合（たとえば、適合するインデックスによるソート）は特に適しています。
EXPLAIN ANALYZE
SELECT * FROM big_a a JOIN big_b b ON a.key = b.key
ORDER BY a.key;
-- Merge Join
-- -> Index Scan on big_a (a.key ASC)
-- -> Index Scan on big_b (b.key ASC)Merge Join が有利な場合
大規模で、あらかじめソートされた入力が 2 つある場合に適しています。線形スキャンのため、必要なメモリも少なくて済みます。ただしソートのコストが重要です。両側を明示的にソートする必要がある場合は、通常 Hash Join の方が有利です。
方式の選択基準
Planner は次の情報に基づいて選択します。
- 推定行数
- 利用可能なインデックス
- メモリ（
work_mem） - postgresql.conf のコスト定数
方式の強制（診断専用）
デバッグ目的で、方式を無効にできます。
SET enable_hashjoin = off;
SET enable_mergejoin = off;
SET enable_nestloop = off;
-- Re-run EXPLAIN to see what the planner picks instead.
-- NEVER persist these in production.ディスクへの退避
ハッシュテーブルまたはソートが work_mem を超えると、演算子は一時ファイルをディスクに退避します。その結果、大幅に遅くなります。work_mem を増やすか、クエリを書き換えてください。
並列結合
PostgreSQL は Hash Join と Merge Join（および seq/index scan）を並列化できます。EXPLAIN では、Workers Planned とともに Parallel Hash Join として表示されます。
選択結果を読む
EXPLAIN ANALYZE では、結合ノードの名前から方式が分かります。選択はほとんどの場合適切です。適切でない場合も、方式を強制する前に統計情報とインデックスを確認してください。
まとめ
3 つの結合方式は、それぞれ異なるデータの形に適しています。
- Nested Loop：小さい外側 + インデックス付きの内側
- Hash：大きなテーブル同士で、有効なインデックスがない場合
- Merge：あらかじめソートされた入力
確認問題
インデックスのない列で、1,000 万行のテーブル 2 つを結合するとします。Planner はどの結合アルゴリズムを選ぶ可能性が高いでしょうか。
よくある質問
「Hash Join、Merge Join、Nested Loop」レッスンは無料ですか？
はい。「Hash Join、Merge Join、Nested Loop」の完全なテキストはこのウェブで無料で読めます。インタラクティブに演習し（組み込みコードエディタと24時間対応のAIチューター）、SQL Academyコースの残りをアンロックするには、CoddyKit PROにアップグレードしてください。 SQL Academyコースには全4レッスンが含まれています。
「Hash Join、Merge Join、Nested Loop」で何を学びますか？
3つの主要な結合戦略、それぞれのコスト特性、そしてプランナーがどの状況で最適と判断するかを理解します。 ブラウザで直接実行するハンズオンコードでSQL Academyを演習し、24時間対応のAIチューターがレッスンを進める中での質問に答えます。
SQL Academyを始めるのに経験は必要ですか？
事前経験は必要ありません。CoddyKitのSQL Academyは初級者から上級者向けに構成されているため、ここから始めるか最初から始めて、自分のペースで進むことができます。 これはレッスン3/4です。
「Hash Join、Merge Join、Nested Loop」レッスンにはどのくらい時間がかかりますか？
ほとんどのCoddyKitレッスンは約5～10分かかります。各レッスンはコンパクトでインタラクティブなので、着実に進歩し、ウェブとアプリ全体で正確に前回の場所から再開できます。
このSQL Academyレッスンでコードを書いて実行できますか？
はい。すべてのSQL Academyレッスンに組み込みコードエディタが含まれているため、ブラウザでリアルコードを書いて実行し、即座のAIフィードバックを取得できます。ローカル設定は不要です。
このコースのすべてのレッスン
- EXPLAINとEXPLAIN ANALYZEの読み方
- シーケンシャルスキャンとインデックススキャン
- Hash Join、Merge Join、Nested Loop
- 遅いクエリの特定と修正