ソートマージJOIN

ソートマージJOINとは、関係データベース管理システムなどのデータ処理において、2つ以上のテーブルやデータセットを効率的に結合するための代表的なアルゴリズムの一つです。あらかじめ結合キーによって昇順または降順にソートされた2つの入力データを用意し、それぞれのデータを先頭から順に走査しながら一致するキーを探し出して結合を行います。データの順序が保証されているため、一方のデータを毎回先頭から全件走査し続ける必要がなくなります。これにより、不要な比較処理を省略しながら効率的に結合を進めることができる点が、この仕組みの基本的な特徴となっています。ハッシュJOINやネステッドループJOINなどと並び、データベースのクエリ最適化において極めて重要な役割を果たす結合方式として広く知られており、商用からオープンソースまで多くのデータベースエンジンに実装されています。