テーブル結合のアルゴリズム

1. Nested Loop Join

2つのテーブルをジョインする際に、外側のテーブルの各行に対して内側のテーブルをスキャンする方法。最も基本的なジョイン方法で、小さなテーブルやインデックスが適用される場合に有効。

実行計画例

Nested Loop Join
    -> Seq Scan on orders o
    -> Index Scan on customers c
        Index Cond: (c.customer_id = o.customer_id)

特徴

• シンプルで理解しやすい。
• 小さなテーブルやインデックスが適用される場合に効果的。
• 大きなテーブル同士のジョインには非効率。

2. Hash Join

ハッシュテーブルを使用して2つのテーブルをジョインする方法。通常、大きなテーブル同士のジョインに適している。

実行計画例

Hash Join
    -> Seq Scan on orders o
    -> Hash
        Seq Scan on customers c

特徴

• 大きなテーブル同士のジョインに適している。
• メモリを多く使用する。
• ハッシュテーブルの作成に時間がかかる場合がある。

3. Merge Join

ソートされた2つのテーブルをマージする方法。両方のテーブルがジョインキーでソートされている場合に効果的。

実行計画例

Merge Join
    -> Sort
        -> Seq Scan on orders o
    -> Sort
        -> Seq Scan on customers c

特徴

• ソートされたテーブル同士のジョインに適している。
• ソートが必要な場合、追加のコストがかかる。
• メモリ使用量が少ない。

補足

データベースのクエリオプティマイザがクエリの実行計画を生成する際に、最適なジョイン方法を選択する。以下のような基準で選択されるらしい。

1. テーブルのサイズ
   • 小さなテーブル：小さなテーブル同士のジョインや小さなテーブルと大きなテーブルのジョインでは、Nested Loop Joinが選ばれることが多い。
   • 大きなテーブル：大きなテーブル同士のジョインでは、Hash JoinやMerge Joinが選ばれることが多い。
2. インデックスの有無
   • インデックスがある場合：インデックスがある場合、Nested Loop Joinが効率的に動作することがある。インデックスを使用して内側のテーブルを効率的にスキャンできる。
   • インデックスがない場合：インデックスがない場合、Hash JoinやMerge Joinが選ばれることが多い。
3. 統計情報
   • 統計情報：データベースはテーブルの統計情報（行数、カラムの分布、カーディナリティなど）をもとに、最適なジョイン方法を選択する。統計情報が最新でない場合、最適でないジョイン方法が選択される場合がある。
4. クエリの複雑さ
   • 複雑なクエリ：複雑なクエリでは、複数のジョインが含まれるため、クエリオプティマイザが最適なジョイン順序とジョイン方法を選択する。このため、同じクエリでも異なるジョイン方法が選ばれることがある。