【データベース】並べ替えてから一気に突き合わせる！「ソートマージ結合法」｜情報処理問題1000本ノック
データベースの内部結合アルゴリズム第2弾。どちらのテーブルにもインデックスがない巨大なデータ同士を、最も効率よく綺麗にパズルのように組み合わせる技法を攻略しましょう。
1. 【 問題 】：関係データベースの結合アルゴリズム（ソートマージ）
【 問題 】 データベース管理システム（DBMS）が2つの表（テーブル）を結合処理（JOIN）する際の内部アルゴリズムのうち、結合の準備段階として両方の表のデータをそれぞれの「結合キー」の順にソート（並べ替え）し、その後、ソートされた双方の表を先頭から同時に順次走査（スキャン）して、キーの一致する行同士を効率的に結合していく方式はどれでしょうか？
① 入れ子ループ法 (Nested Loops Join)
② ソートマージ結合法 (Sort Merge Join)
③ ハッシュ結合法 (Hash Join)
④ インデックススキャン法 (Index Scan)
2. 正解：
正解： ② ソートマージ結合法（Sort Merge Join）
3. 解説：足並みを揃えて、上から下に一度だけ流す
入れ子ループ法は、外側の表の行数ぶんだけ内側の表を何度も何度もループして探すため、データ量が膨大でインデックスがないと最悪のスピードになってしまいます。そこで登場するのがソートマージ結合法です。
1. ソート（整列）：結合したい「表A」と「表B」を、結合キー（例：社員IDなど）の昇順（1, 2, 3...）にきれいに並べ替えます。 ← ココが問題の正解！
2. マージ（結合）：並べ替えた2つの表の先頭（1番）にそれぞれポインタ（目印）を置きます。
3. 両方のキーが一致すれば合体させます。もし「表Aが3番、表Bが2番」のようにズレたら、小さい方の表Bのポインタを次の行（3番）に進めます。これをお互いの足並みを揃えながら、最後の行に向かって一方向にスキャンしていきます。
・メリット：最初のソートさえ終われば、結合処理自体は「両方の表を上から下まで1回ずつなぞるだけ（2重ループしない）」で終わるため、インデックスがない巨大なテーブル同士を結合する際に、入れ子ループ法よりも圧倒的に高速に処理できます。
★ ① 入れ子ループ法：前回学習した、一方の表の1行に対してもう一方の表を毎回全行走査（ループ）する方式です。
★ ③ ハッシュ結合法：一方の表からメモリ上にハッシュテーブルを作って一瞬で突き合わせる方式です。並べ替え（ソート）の処理は行いません。
★ ④ インデックススキャン：これは結合のアルゴリズムではなく、インデックス（索引）を使って特定のデータを検索するアクセスメソッド（読み込み手順）の名称です。
1. 理解のコツ: 前回の「出席簿と、バラバラのテスト答案の山」の突き合わせ作業をもう一度思い出してください。
・前回は出席簿の1人ごとに、答案の山を毎回上から下までペラペラめくって探していました（入れ子ループ）。
・今回のソートマージ法は、作業を始める前に、まず「答案の山」を出席番号順（1番、2番、3番…）にきれいに並べ替えます（ソート）。出席簿も番号順に並んでいます。あとは、「出席簿の1番と答案の1番」「出席簿の2番と答案の2番」と、上から順番に1枚ずつノンストップでめくっていくだけ（マージ）です。最初の並べ替えに少し手間（コスト）がかかりますが、本番の突き合わせ作業は一瞬で終わりますよね。
2. 試験対策の視点: 「最初に両方の表をソート（並べ替え）して」「順に結合（マージ）」という、そのまんまの名前のプロセスが語られたら「ソートマージ法」が一択です。基本情報や応用情報の午前試験では、問題文の中に「あらかじめ結合キーの順に整列されている場合、最も効率的なアルゴリズムはどれか」といった形で出題されることもあります（最初からソートされているなら、ソートのコストがゼロになるためソートマージ法が超有利になります）。
4. まとめ
「インデックスのない大量のデータ同士をドッキングさせる際、最初にキー順で整列させておくことで、本番の結合処理を『上から下に1回スキャンするだけ』の超高速処理に変える職人技のような結合手法」。これがソートマージ結合法です。DBMSが裏側でデータの並び順をどう活かして計算を効率化しているかを知る、アルゴリズムの美しさが詰まった技術です。