はじめに
こんにちは。アメリカに住みながら独学でエンジニアを目指しているTairaです。
現在、SQLを勉強しており、その中でも内部結合や外部結合などを学習しています。
これらの結合では、Nested Loops、Hash、Sort Merge といったアルゴリズムが採用されることがあります。
本記事では、その中でもSort Mergeについて解説していきます。
Sort Merge結合とは？
Sort Merge結合（Sort Merge Join）は、SQLにおける結合アルゴリズムの一種です。特に、結合対象のデータ量が多く、結合条件に不等号（<、>、<=、>=）を含むようなケースで有効となることがあります。
アルゴリズムの流れ
Sort Merge結合は、大きく以下の2つのステップで構成されます。
- AテーブルとBテーブルを結合キーでソートする
- ソート済みの2つのテーブルをマージ処理でマッチングさせる
マージ処理では、ソート済みのデータを先頭から順に比較していくため、線形的な効率で結合処理を進められます。
特徴
- 両テーブルをソートする必要があるため、Nested Loops結合よりも多くのメモリを消費する傾向があります。
- Hash結合と比較すると、Hash結合は片方のテーブルのみをハッシュ化するため、状況によってはSort Mergeの方がメモリ消費が多くなる可能性があります。
- メモリ不足が発生すると、一時ファイル（TEMP）をディスクに書き出す「TEMP落ち」が起こり、ディスクI/Oによる遅延が発生するリスクがあります（これはHash結合と同様）。
- 等値結合（=）だけでなく、不等号（<、>、<=、>=）を使った結合**にも対応しています（Hash結合では不可）。ただし、**否定条件（<>）には対応していません。
- テーブルがすでに結合キーでソート済みであれば、ソートステップをスキップすることができます。ただし、SQLはテーブルの物理的配置に依存しないため、これはDBMSの実装依存となります。
- ソートされたデータを使用するため、一方のテーブルを全スキャンした時点で、結合を終了することができます。
Sort Mergeが有効なケース
- 結合する行数が多い場合でも、マージ処理自体は高速に行えます。
- 結合キーでソート済みのテーブルが存在する場合、ソート処理をスキップできれば大きなメリットになります。
- 不等号による結合条件が含まれている場合、Hash結合では対応できないため、Sort Mergeが選ばれることがあります。
ただし注意点
- 通常は、Nested Loops結合やHash結合の方が優先されます。特に、インデックスが使える場合のNested Loopsは非常に効率的です。
- ソート処理には時間とリソースを要するため、テーブルが未ソートの場合はパフォーマンス上のコストが大きくなります。
まとめ
Sort Merge結合は、特定の条件下で非常に有効な結合方法ですが、メモリやソートコストの面で注意が必要です。特に以下のようなケースで有力な選択肢になります：
- 結合キーがすでにソートされている
- 不等号を使った結合条件が必要
- 対象データが非常に大きい
普段のSQLチューニングでは、まずNested LoopsやHash結合のパフォーマンスを確認し、必要に応じてSort Merge結合を検討するのが良いでしょう。