はじめに
こんにちは。アメリカに住みながら独学でエンジニアを目指しているTairaです。
現在、SQLを勉強しており、その中でも内部結合や外部結合などを学習しています。
これらの結合では、Nested Loops、Hash Join、Sort Merge Joinといったアルゴリズムが採用されることがあります。
本記事では、その中でもNested Loopsについて解説していきます。
なお、本記事は4/5に投稿されるはずでしたがtagのエラーにより4/10は2つ記事を投稿しています。
Nested Loopsとは？
Nested Loops（ネストループ結合）は、SQLの結合処理における最も基本的なアルゴリズムの一つです。
特に、片方のテーブルにインデックスが存在する場合や、結合対象の行数が少ない場合に効果的です。
処理の流れ
- 駆動表（driving table / outer table）として選ばれたテーブル（Table_A）を1行ずつスキャンします。
- 各行に対して、もう一方のテーブル（Table_B、内部表 / inner table）をスキャンします。
- 結合条件に一致する行があれば、それを結果として返します。
- 上記の処理を駆動表の全行に対して繰り返します。
イメージとしては、外側のループがTable_A、内側のループがTable_Bという構造です。
特徴
- 処理行数の関係：Table_Aの行数をR(A)、Table_Bの行数をR(B)とした場合、最大でR(A) × R(B)行の比較が行われます。
- メモリ使用量が少ない：一度に大量のデータを保持しないため、Hash JoinやSort Merge Joinに比べてメモリ消費が少ない傾向があります。
- DBMSの汎用性：すべての主要なDBMSでサポートされています。
パフォーマンスに関する注意点
駆動表は小さい方が良い
Nested Loopsでは、駆動表の行数に比例して内部表へのアクセス回数が増えるため、駆動表が小さいほど性能が良くなります。
特に、インデックスを活用する場合にはこの傾向が顕著です。
インデックスがある場合のアクセス数
内部表の結合キーにインデックスが存在する場合、アクセス回数は以下のように見積もられます：
- 通常、インデックスによる検索はB-tree構造を用いるため、1検索あたり log₂(R(B)) 回のステップで目的のキーに到達します。
- 実際のDBでは、インデックスアクセスに加えて、実データ取得（テーブルアクセス）が1回行われるため、
アクセス数 ≒ R(A) × (log₂(R(B)) + 1)
これはあくまで理論モデルですが、実行計画のコスト見積もりの参考になります。
どうすれば効率よく結合できるの？
上記を踏まえて、効率的に結合を行うには、駆動表を小さくし、内部表には一意性のあるインデックスを設定することがポイントです。
まとめ
| 項目 | 内容 |
|---|---|
| アルゴリズムの種類 | 基本的な結合アルゴリズム（すべてのDBMSで対応） |
| 駆動表の最適化 | 小さいほど良い（ループ回数削減）、内部表にインデックスを設定するのが望ましい |
| アクセス数（最適化時） | R(A) × (log₂(R(B)) + 1) |
| メモリ使用量 | 少なめ。大規模なデータにも対応しやすい |
Nested Loopsはシンプルでありながら、インデックスやキャッシュの使い方によって大きく性能が変わる、基本かつ重要な結合手法です。