PostgreSQLの内部結合アルゴリズムについて

PostgreSQLでは、テーブルの結合を行う際に、以下の3つの内部結合アルゴリズムを使用します：

Nested Loop Join
Hash Join
Merge Join

これらのアルゴリズムは、それぞれの特性に応じて最適なシナリオで使用されます。以下にそれぞれの詳細と使用シナリオを説明します。

1. Nested Loop Join

Nested Loop Join は、最も基本的でシンプルな結合アルゴリズムです。これは、外部テーブルの各行に対して内部テーブルを一行ずつスキャンします。計算量は O(M * N) で、Mは外部テーブルの行数、Nは内部テーブルの行数を表します。

適している場合
- 小さなテーブルと大きなテーブルの結合
- 内部テーブルに効率的なインデックスがある場合
特徴
- 小さなデータセットに対して効率的
- 大きなデータセットでは非効率になる可能性がある

2. Hash Join

Hash Join は、小さい方のテーブルからハッシュテーブルを作成し、大きい方のテーブルの各行とマッチングします。計算量は O(M + N) です。

適している場合
- 大きなデータセットの結合
- 等価結合（=）の場合
特徴
- メモリを多く使用する
- 大規模なデータセットに効果的

3. Merge Join

Merge Join は、両方のテーブルをソートし、ソートされた順序でマージします。計算量は、ソートの有無により異なります。ソートが必要な場合は O(M log M + N log N), ソート済みの場合は O(M + N) です。

適している場合
- 両方のテーブルが既にソートされている、またはインデックスがある場合
- 大きなデータセットの結合
特徴
- ソートのオーバーヘッドがある
- ソート済みのデータに対して非常に効率的

結合アルゴリズムの選択

PostgreSQLのクエリプランナーは、クエリの実行時に最適な結合アルゴリズムを自動的に選択します。
実行計画を確認することで、どの結合アルゴリズムが使用されているかを知ることができます。

以下のコマンドで実行計画を確認できます：
- EXPLAIN クエリ;
- EXPLAIN ANALYZE クエリ;

実行計画の変更

通常、エンジニアが直接結合アルゴリズムを指定することは推奨されません。
ただし、一応ヒント句というものがあります。
これは、実行計画を制御することができます。
PostgreSQLでは、pg_hint_planという拡張があり導入可能です。
今回詳しくは取り上げませんが、こちらのサイトを参考にしてみてください。
https://www.fujitsu.com/jp/products/software/resources/feature-stories/postgres/article-index/pg-hint-plan/