最終更新日:2026年11月8日
fe fe-technology database sql
まず結論
DBMSの結合アルゴリズムとは、SQLで指定された複数の表の結合を、DBMS内部でどのような手順で実行するかという方法です。
科目Aでは、次の動作で見分けます。
| 方式 | 最初に思い浮かべる動作 |
|---|---|
| ソートマージ結合(Sort-Merge Join) | 結合キーで両方を整列し、順に突き合わせる |
| ハッシュ結合(Hash Join) | 一方の表からハッシュ表を作り、他方の行を照合する |
| ネステッドループ結合(Nested Loop Join) | 外側の各行について内側の表を探索する |
| インデックスを使うネステッドループ結合 | 外側の各行のキーで内側の表の索引を引く |
どれも同じ結合結果を得られますが、途中の探し方が違います。
直感的な説明
社員番号と社員名を持つ表、社員番号と申請内容を持つ表から、誰が何を申請したのかを調べたいとします。
| 社員表:社員番号 | 氏名 |
|---|---|
| 12 | 青木 |
| 4 | 伊藤 |
| 7 | 佐々木 |
| 申請表:社員番号 | 申請内容 |
|---|---|
| 7 | 出張 |
| 12 | 休暇 |
| 9 | 備品 |
社員番号が等しい行を組み合わせます。例えば、社員番号12なら「青木・休暇」です。
SELECT e.name, r.request_name
FROM employees AS e
JOIN requests AS r
ON e.employee_id = r.employee_id;
SQLのJOINは「何を結合するか」を指定します。しかし、「どう探して結合するか」はDBMSが選ぶ実行計画によって変わります。
この例の内部結合(INNER JOIN)の結果は次の2行です。
| 氏名 | 申請内容 |
|---|---|
| 佐々木 | 出張 |
| 青木 | 休暇 |
社員番号4と9は相手が見つからないので結果に含まれません。結合結果の行順は、SQLでORDER BYを指定しない限り保証されません。
定義・仕組み
1. ソートマージ結合:並べ替えてから突き合わせる
まず両方の表を結合キー(ここでは社員番号)で昇順に整列します。
| 整列済み社員表 | 整列済み申請表 | ||
|---|---|---|---|
| 4 | 伊藤 | 7 | 出張 |
| 7 | 佐々木 | 9 | 備品 |
| 12 | 青木 | 12 | 休暇 |
その後、それぞれの表の比較位置を先頭から動かします。
| 手順 | 社員側 | 申請側 | 比較した結果と次の動き |
|---|---|---|---|
| 1 | 4 | 7 | 4は小さい → 社員側を進める |
| 2 | 7 | 7 | 等しい → 佐々木と出張を結合し、次へ |
| 3 | 12 | 9 | 9は小さい → 申請側を進める |
| 4 | 12 | 12 | 等しい → 青木と休暇を結合 |
社員表(昇順) 4 → 7 → 12
│ │
申請表(昇順) 7 → 9 → 12
↑ ↑
一致 一致
小さい値の側を進めると、まだ見ていない行に一致する可能性を残しつつ、先頭から順番に比較できます。これがソートマージ結合の基本イメージです。
ただし、この単純な例では各キーが一度しか現れません。結合キーに重複があれば、一致するキーの行の組合せをすべて出力する処理が必要です。単に両側を一行ずつ進めるだけではありません。
また、ソートマージ結合は、入力がすでに索引などにより結合キー順で読み出せる場合、追加の並べ替えが不要なこともあります。
2. ハッシュ結合:ハッシュ表を使う
一方の表の結合キーを使ってハッシュ表を作り、もう一方の表の各行から照合します。
社員表の社員番号からハッシュ表を作る
↓
申請表の行を1行ずつ読み込む
↓
社員番号でハッシュ表を探す
↓
一致するキーか確認して結合
ハッシュ値が同じでも別のキーであることがあるため、ハッシュ値だけで同じ行だと判断するのではなく、結合条件を確認する必要があります。
3. ネステッドループ結合:一方の各行ごとに探す
外側の表の1行を取り出し、内側の表で一致する行を探します。これを外側の全行について繰り返します。
社員表から1行取り出す
└→ 申請表を調べて一致する行を結合
社員表から次の1行を取り出す
└→ 申請表を調べて一致する行を結合
……
基本的な方式では、内側の表を繰り返し走査します。行数が多いと比較回数が増える場合があります。
4. インデックス結合:索引で相手を探す
ネステッドループ結合の内側にインデックス(索引)があると、毎回内側の表を最初から読む代わりに、外側の行のキーを使って必要な行に近づけます。
社員表の1行(社員番号 12)
↓
申請表の社員番号インデックスで 12 を検索
↓
一致した申請行を結合
これは別の関係代数の結合ではなく、インデックスを利用するネステッドループ結合の実行方法です。インデックスの仕組みも参照してください。
科目Aでどう出る?
用語の特徴を示す文章から方式を選ぶ問題では、次の判断が有効です。
| 説明のキーワード | 判断する方式 |
|---|---|
| 並べ替えた両表を先頭から順に突き合わせる | ソートマージ結合 |
| ハッシュ表を作って相手を探す | ハッシュ結合 |
| 一方の行を順に取り出し、もう一方を繰り返し調べる | ネステッドループ結合 |
| 相手の表の索引を使って一致する行を探す | インデックスを使うネステッドループ結合 |
特に、「インデックスがある」と「ソート済み」は同じ意味ではありません。ソートマージ結合でも索引を使って整列済みの順序で読み出せる場合があります。選択肢が「結合相手を索引で繰り返し探す」と言っているのか、「整列した行を順に突き合わせる」と言っているのかに注目しましょう。
オリジナル確認問題
次のように、2つの表の結合キーが整列されているとします。
- 表A:2、5、8
- 表B:3、5、9
ソートマージ結合で最初に2と3を比較したら、次に進めるべき側はどちらでしょうか。
- A. 表A側
- B. 表B側
- C. 両方とも末尾まで飛ばす
答えと解説を表示する
正解:A(表A側)
2は3より小さいため、表A側を次の値5へ進めます。その後、5と3を比べて表B側を5へ進めれば、5同士が一致して結合できます。
どんな場面で使う?
これらの結合方式は、SQLでJOINを使うときにDBMSが選択する実行方法の候補です。
どの方式が効率的かは、表のサイズ、結合キーの並び順、索引の有無、利用できるメモリ、データの分布などによって変わります。どれか1方式が常に最速というわけではありません。
実行方法を評価・選択する役割はSQLオプティマイザの記事で整理しています。このページは、選ばれる候補の実際の結合手順を扱っています。
より詳しい処理方式は、PostgreSQL公式ドキュメント:EXPLAINでも確認できます。
よくある誤解・混同
ソートマージ結合は、いつも最初にソート処理を実行する?
いいえ。最初から必要な順序で読み出せる場合、明示的なソート処理を省けることがあります。大切なのは結合キー順の2つの入力を突き合わせる点です。
同じキーが複数行あっても、1組だけ結合すればよい?
いいえ。内部結合では、条件を満たす行の組合せを出力する必要があります。重複キーがある場合は、対応する行の組合せを取りこぼさない処理が必要です。
SQLのJOINの書き方を変えないと方式を選べない?
一般にはDBMSのオプティマイザが実行計画を選びます。同じSQLでもデータ量や索引などの条件で選択が変わる場合があります。
マージソートとソートマージ結合は同じ?
違います。マージソートはデータを整列するアルゴリズムで、ソートマージ結合は結合キー順のデータを使って2つの表を結合するアルゴリズムです。
まとめ(試験直前用)
- ソートマージ結合=結合キー順に整列した両表を順に突き合わせる
- ハッシュ結合=ハッシュ表を作って一致するキーを探す
- ネステッドループ結合=外側の各行について内側を探索する
- インデックス利用=内側の表を索引で効率よく探せる場合がある
- JOINは欲しい結果、結合アルゴリズムはDBMS内部の実行手順