読み方：ソートマージけつごう

ソートマージ結合【sort-merge join】マージ結合

概要

ソートマージ結合とは、リレーショナルデータベース（RDB）でテーブルの結合（JOIN）処理を行うアルゴリズムの一つで、結合条件に用いる列の値で両テーブルの行を同じ順序に並べ替えた上で、先頭から順に照合・結合していく方式。

リレーショナルデータベースでは、共通の意味を持つ列を介して複数のテーブルをSQLのJOIN句で結合し、一つの結果セットにまとめる操作が頻繁に行われる。ソートマージ結合はその実行手順の一つであり、データベース管理システム（DBMS）がクエリの実行計画を立てる際に選択する結合アルゴリズムの一つでもある。

まず、両テーブルをそれぞれ結合キーとなる列の値で昇順または降順にソート（並べ替え）する。対象列にインデックスが存在する場合はこのソート処理を省略できるため、より高速に次の段階へ進める。その後、整列済みの両テーブルを先頭から順に走査し、結合条件を満たす行同士を結合していく。両テーブルとも同じ順序に整列されているため、一方のポインタを戻す必要がなく、各行を原則として一度ずつ走査するだけで結合を完了できる。

ソートマージ結合は、等価条件（一致）だけでなく、大小比較を伴う範囲条件（以上・未満・上限と下限の範囲内など）の結合にも対応できる。また、処理対象のデータ量がメモリ容量を超える場合でも、一時的にストレージへデータを退避させながらソートを行うことで安定して処理を完遂できる。

一方、結合条件が等価条件のみの場合は、事前のソートが不要な「ハッシュ結合」のほうが一般に高速なため、多くのDBMSはそちらを優先的に選択する。ソートマージ結合が採用されやすいのは、ハッシュ結合では対応できない範囲条件による結合の場合や、結合キーの列が既にソート済みである場合、あるいはメモリが不足する大規模なデータ処理においてハッシュ結合よりも安定した性能が求められる場合などである。

(2026.6.21更新)