【データベース】2重ループでデータを突き合わせる！「入れ子ループ法」｜情報処理問題1000本ノック
データベースが裏側でSQLの「JOIN（結合）」をどうやって処理しているか。最もシンプルで、インデックスの有無によって劇的に速度が変わる結合アルゴリズムを攻略しましょう。
1. 【 問題 】：関係データベースの結合アルゴリズム
【 問題 】 データベース管理システム（DBMS）が2つの表（テーブル）を結合処理（JOIN）する際の内部アルゴリズムのうち、一方の表（外部表／駆動表）からデータを1行（組）ずつ取り出し、その行の結合キーに対応するデータを、もう一方の表（内部表）のすべての行から走査（検索）して結合相手を見つけ出すという処理を、外部表のすべての行に対して繰り返す方式はどれでしょうか？
① ソートマージ結合法 (Sort Merge Join)
② ハッシュ結合法 (Hash Join)
③ 入れ子ループ法 (Nested Loops Join)
④ クロス結合法 (Cross Join)
2. 正解：
正解： ③ 入れ子ループ法（Nested Loops Join）
3. 解説：プログラミングでお馴染みの「2重for文」
SQLで「AテーブルとBテーブルを結合して」と命じたとき、DBMSの内部（ストレージエンジンなど）では、泥臭い行の突き合わせ作業が行われます。その最も基本的なやり方が入れ子ループ法です。
1. まず、外側のループとなる「表A（外部表）」から1行目を取り出します。
2. その1行目を持ったまま、内側のループとなる「表B（内部表）」の1行目から最後の行まで順番に見ていき、結合条件が一致するものを探して合体させます。
3. 表Bを最後まで見終わったら、次は表Aの2行目を取り出し、再び表Bを上から下まで全行走査します。この2重ループを繰り返します。 ← ココが問題の正解！
・特徴と対策：この方式は、内側の表Bに「インデックス（索引）」が用意されていると劇的に速くなります。インデックスがあれば、表Bを上から下まで全行走査する（ループする）必要がなくなり、ピンポイントで相手を見つけられるため、外部表（表A）のデータ件数が少ない場合に最強のパフォーマンスを発揮します。
★ ① ソートマージ結合法：2つの表をあらかじめ結合キーの順番で「ソート（並べ替え）」し、端から同時に「マージ（足並みをそろえてスキャン）」していく方式です。どちらの表もインデックスがない巨大なデータ同士の結合に向いています。
★ ② ハッシュ結合法：一方の表の結合キーからメモリ上に「ハッシュテーブル（検索用のマップ）」を構築し、もう一方の表のキーをハッシュ化して一瞬で突き合わせる方式です。インデックスがない大量データ結合の最終兵器です。
★ ④ クロス結合法：条件に関係なく、2つのテーブルのすべての行の組み合わせ（直積）を単純に出力する結合のことです。
1. 理解のコツ: 「出席簿と、集められたテストの答案の束」を突き合わせる作業に例えてみましょう。
・出席簿の上から順に「1番：青木くん」の名前（外部表の組）を見ます。次に、シャッフルされた答案の束（内部表）を上から1枚ずつめくって走査し、「青木」の答案を探します。見つかったら点数を転記します。
・次に「2番：飯田くん」の名前を見て、また答案の束を上から1枚ずつめくって探します……。この、1名ごとに毎回リスト全体をペラペラめくって探す2重のループ作業が、まさに入れ子ループ法です。
2. 試験対策の視点: 「一方の表のそれぞれの組に対して」「もう一方の表の組を走査して結合する」という、2重ループの挙動そのものの説明があれば「入れ子ループ法（Nested Loops Join）」が一択です。基本情報や応用情報の午前試験では、データベースの性能（チューニング）に関する問題として、「インデックスがある時に有効な結合アルゴリズムはどれか」といった実践的な切り口でもよく狙われます。
4. まとめ
「一方の表を基準（親ループ）とし、その1行ごとに、もう一方の表（子ループ）をくまなく探して結合条件に合うデータをドッキングしていく、DBMSの最も基本的かつ直感的な結合手法」。これが入れ子ループ法です。シンプルだからこそ、インデックス設計の恩恵を最も受けやすい、インフラエンジニアやプログラマーにとっても超重要な処理メカニズムです。