Coding Interview Prep · レッスン

結合アルゴリズム：Nested Loop、Hash、Merge

Q: 「結合アルゴリズム：Nested Loop、Hash、Merge」で何を学びますか？

各結合方式の実行方法と、適切な使い分けを学びます。 ブラウザで直接実行するハンズオンコードでCoding Interview Prepを演習し、24時間対応のAIチューターがレッスンを進める中での質問に答えます。

各結合方式の実行方法と、適切な使い分けを学びます。

「結合アルゴリズム：Nested Loop、Hash、Merge」はCoddyKit上の無料Coding Interview Prepレッスンです。これはレッスン3/4です。下記で完全なレッスンを無料で読むことができます。その後、ブラウザ内の組み込みコードエディタと24時間対応のAIチューターでハンズオン演習できます。これはCoding Interview Prep学習パスの一部であり、ウェブとCoddyKitアプリ全体で進捗が同期されます。 Coding Interview Prepコースには全4レッスンが含まれています。

JOINは単なる構文ではなくアルゴリズムです

INNER JOINは構文としてすでにご存じでしょう。シニアレベルの面接では、データベースがJOINを物理的に実行する方法について質問されます。アルゴリズムは3つあります。

ネステッドループ結合
ハッシュ結合
マージ結合（ソートマージ）

論理的な結合タイプ（INNER、LEFT）とアルゴリズムは別物です。プランナーは、テーブルのサイズ、インデックス、ソート順に基づいてアルゴリズムを選びます。それぞれがどのような場合に有効かを知ることが、このレッスンの核心です。

ネステッドループ結合

ネステッドループは最も単純な方式です。外側のテーブルの各行について、内側のテーブルをスキャンして一致する行を探します。擬似コードでいえば、一方のループの中にもう一方のループがある形です。

単純に実行すると計算量はO(outer * inner)となり、大きなテーブルでは非常に非効率です。しかし、内側の側に結合キーのインデックスがある場合は非常に優れた方式になります。外側の各行に対して、内側のテーブル全体をスキャンする代わりに、低コストなインデックス検索を実行できるためです。

外側のテーブルが小さく、内側の結合カラムにインデックスがある場合、プランナーはこの方式を好んで選択します。

Nested Loop  (cost=0.42..120.5 rows=15 width=72)
  ->  Seq Scan on customers c  (rows=3)
  ->  Index Scan using idx_orders_cust on orders o
        Index Cond: (o.customer_id = c.id)
        (loops=3)

ネステッドループのループを読み取る

ネステッドループの決め手は、内側のノードにあるloopsです。この例でloops=3となっているのは、外側が3行を生成したため、内側のインデックススキャンが3回実行されたからです。

外側のデータが大きい場合に問題が生じます。外側が200万行を生成すると、内側は200万回実行されます。高速な0.01msの検索であっても、合計で20秒かかります。

面接では、適切なインデックスのない内側のテーブルに対してloopsが大きいネステッドループを見つけたら、遅いクエリの原因として指摘してください。

ハッシュ結合

ハッシュ結合は、ソートされていない大きなテーブルを効率よく処理できます。2つのフェーズで実行されます。

ビルド：小さい方のテーブルを読み込み、結合カラムをキーとするインメモリのハッシュテーブルに格納します。
プローブ：大きい方のテーブルをスキャンし、各行について結合キーをハッシュ化して、ハッシュテーブルを検索します。

各テーブルは1回だけ読み込まれるため、計算量はおおよそO(outer + inner)です。インデックスもソート済みの入力も必要ないため、等価条件による大規模な分析クエリのJOINでは、この方式が選ばれることが多くなります。

Hash Join  (cost=18.0..520.0 rows=900 width=72)
  Hash Cond: (o.customer_id = c.id)
  ->  Seq Scan on orders o  (rows=100000)
  ->  Hash  (rows=500)
        ->  Seq Scan on customers c  (rows=500)

ハッシュ結合の制限

ハッシュ結合について、必ず説明すべき点が2つあります。

等価結合条件でのみ機能します（a.id = b.id）。a.x < b.yのような範囲条件にはハッシュ結合を使用できません。
ビルド側はwork_memに収まらなければなりません。収まらない場合、Postgresはバッチをディスクに退避します（Batches: > 1やディスク使用量に現れます）。これによりJOINは大幅に遅くなります。

そのため、ビルド側が非常に大きいのにwork_memが小さいハッシュ結合は、実際の現場で指摘すべき性能バグです。

Hash  (actual rows=2000000 loops=1)
  Buckets: 65536  Batches: 16  Memory Usage: 4096kB

マージ結合

マージ結合（ソートマージ）では、両方の入力が結合キーでソート済みである必要があります。その後、2つのソート済みリストをマージするように、両方を並行して走査し、後れている方のポインタを進めます。

入力がすでにソート済みの場合、たとえばキー順のインデックスから直接取得できる場合には効率的です。ソート処理が不要になるためです。また、ハッシュ結合とは異なり、範囲結合や不等価結合にも対応できます。

入力があらかじめソートされていない場合、プランナーは明示的なSortノードを追加します。そのソートコストによっては、代わりにハッシュ結合の方が安くなることがあります。

Merge Join  (cost=0.85..210.0 rows=900 width=72)
  Merge Cond: (o.customer_id = c.id)
  ->  Index Scan using idx_orders_cust on orders o
  ->  Index Scan using customers_pkey on customers c

アルゴリズム選択の早見表

どのアルゴリズムがどのような場合に有効かを覚えておきましょう。

ネステッドループ：外側のテーブルが小さく、内側の結合キーにインデックスがある場合。また、ソート済みの入力がない非等価結合では、これが唯一の選択肢です。
ハッシュ結合：大きくソートされていないテーブル同士を等価条件で結合する場合。インデックスは必要ありません。
マージ結合：両方の入力がキーでソート済みの場合（多くはインデックスによるもの）、または範囲結合の場合。非常に大きなソート済みデータセットに適しています。

プランナーは各方式のコストを見積もり、行数の見積もりに基づいて最も安いものを選びます。

メモリとソートのコスト

リソースの使用状況には大きな違いがあり、面接ではこの点を詳しく聞かれます。

ネステッドループ：必要なメモリは最小限ですが、コストの大部分は内側の検索を繰り返すことによって生じます。
ハッシュ結合：ハッシュテーブル用のメモリが必要で、大きすぎるとディスクに退避します。
マージ結合：マージ自体は低コストですが、事前にソートが必要な場合は高コストになります。ソートもwork_memを使用し、収まらない場合はディスクに退避します。

したがって、work_memを増やすことで、ディスクに退避して遅くなっているハッシュ結合やソートを、メモリ上で実行できるように変えられる場合があります。これは具体的な最適化の回答になります。

ネステッドループが失敗した理由

典型的な状況は、開発環境では高速だったクエリが、本番環境では遅くなるケースです。実行計画を見ると、loops=3000000のネステッドループになっています。

プランナーが外側の行数を過小評価していました（古い統計情報では3行でしたが、実際には300万行でした）。そのため、ネステッドループが選択されました。正確な統計情報があれば、ハッシュ結合が選ばれていたでしょう。

面接での回答は次のとおりです。ANALYZEを実行して見積もりを正確にします。そうすればプランナーがハッシュ結合に切り替え、クエリの速度が大幅に向上します。

Nested Loop  (cost=0.42..50.0 rows=3 width=72)
  ->  Seq Scan on big_outer  (actual rows=3000000 loops=1)
  ->  Index Scan on inner_t  (actual rows=1 loops=3000000)

選択に影響を与える方法

通常、アルゴリズムを強制すべきではありませんが、比較のためにテストで指定することはできます。Postgresには方式ごとの切り替え設定があります。

SET enable_nestloop = off;や、enable_hashjoinおよびenable_mergejoinに対応する設定です。1つをオフにしてEXPLAIN ANALYZEを再実行し、別の方式が実際に高速かどうかを確認します。

本来の改善策は、最新の統計情報、適切なインデックス、十分なwork_mem、そして選択性の高い述語です。強制指定は診断のためだけに使用します。

SET enable_nestloop = off;
EXPLAIN ANALYZE
SELECT * FROM orders o JOIN customers c ON o.customer_id = c.id;
SET enable_nestloop = on;

大規模なJOINのまとめ

2つの大きなファクトテーブルとディメンションテーブルをidで結合する分析ワークロードについて、整理してみましょう。

ディメンションテーブルがメモリに収まる場合は、ハッシュ結合が選ばれることが多く、最適な方式である場合も多いです。
両方のテーブルがインデックスからソート済みの状態で取得される場合は、マージ結合によってハッシュテーブルの構築を回避できます。
ここでネステッドループが選ばれていたら、危険信号です。通常は、誤った見積もりが原因です。

プランナーがどの方式を選んだか、そして本当にその方式でよかったのかを読み取って判断することが、まさにこれらの質問で試されるシニアレベルの力量です。

確認問題

2つの大きくソートされていないテーブルを、等価条件a.id = b.idで結合します。どちらにも有用なインデックスがなく、統計情報は正確です。プランナーはどの結合アルゴリズムを選ぶ可能性が最も高いでしょうか。

振り返り

3つの結合アルゴリズムを整理しましょう。

ネステッドループ：外側の行ごとに内側を検索します。外側が小さく、内側のキーにインデックスがある場合は優れていますが、loopsが非常に大きい場合は危険です。
ハッシュ結合：ハッシュテーブルを構築して検索します。大きくソートされていないテーブル同士の等価結合に最適ですが、等価条件に限られ、work_memの制約を受けます。
マージ結合：ソート済みの入力を並行して走査します。データがすでにソートされている場合や、範囲結合に適しています。

プランナーはコストと統計情報に基づいて方式を選びます。loopsが非常に大きい、意外なネステッドループが見つかった場合は、ほぼ必ず行数の見積もりが間違っています。統計情報を修正してください。

よくある質問

「結合アルゴリズム：Nested Loop、Hash、Merge」レッスンは無料ですか？

はい。「結合アルゴリズム：Nested Loop、Hash、Merge」の完全なテキストはこのウェブで無料で読めます。インタラクティブに演習し（組み込みコードエディタと24時間対応のAIチューター）、Coding Interview Prepコースの残りをアンロックするには、CoddyKit PROにアップグレードしてください。 Coding Interview Prepコースには全4レッスンが含まれています。

「結合アルゴリズム：Nested Loop、Hash、Merge」で何を学びますか？

各結合方式の実行方法と、適切な使い分けを学びます。ブラウザで直接実行するハンズオンコードでCoding Interview Prepを演習し、24時間対応のAIチューターがレッスンを進める中での質問に答えます。

Coding Interview Prepを始めるのに経験は必要ですか？

事前経験は必要ありません。CoddyKitのCoding Interview Prepは初級者から上級者向けに構成されているため、ここから始めるか最初から始めて、自分のペースで進むことができます。これはレッスン3/4です。

「結合アルゴリズム：Nested Loop、Hash、Merge」レッスンにはどのくらい時間がかかりますか？

ほとんどのCoddyKitレッスンは約5～10分かかります。各レッスンはコンパクトでインタラクティブなので、着実に進歩し、ウェブとアプリ全体で正確に前回の場所から再開できます。

このCoding Interview Prepレッスンでコードを書いて実行できますか？

はい。すべてのCoding Interview Prepレッスンに組み込みコードエディタが含まれているため、ブラウザでリアルコードを書いて実行し、即座のAIフィードバックを取得できます。ローカル設定は不要です。

このコースのすべてのレッスン

← Coding Interview Prepに戻る