Merge Join
マージ結合は、両表が結合列でソート済みであることを前提に、同期走査しながら一致する行を統合する結合である。ソート済みデータやソート後の結合に適する。
目的
整列データに対する効率的な結合アルゴリズムを理解し、ソートコストとのトレードオフを分析する。
メカニズム
両表を結合列でソートした後、現在行を比較しながら同期走査する。等しければ一致を出力し、小さい方を進める。計算量は O(N+M) だがソートに O(N log N + M log M) がかかる。ソート済みインデックスがあればソートは不要で極めて効率的である。
ユースケース
- ソート済み結合の最適化
- 結合アルゴリズムの選択
- 実行計画（クエリープラン）の分析