入れ子ループ結合とは？

入れ子ループ結合の意味

外側の表を1行ずつ読み、その1行ごとに内側の表を走査して結合条件に合う行を探す方式。

入れ子ループ結合の具体例

外側が小さく、内側の結合列に索引があるときに有利。

入れ子ループ結合は試験でどう引っ掛けられる？

索引がなく総当たりになると、双方の件数の積に比例する計算量（nの2乗オーダー）になる。

入れ子ループ結合と関連する用語

• ソートマージ結合
• ハッシュ結合

入れ子ループ結合が出た過去問

• 関係データベースにおいて、タプル数nの表二つに対する結合操作を、入れ子ループ法によって実行する場合の計算量はどれか。

  正解：O(n^2)

  要点：入れ子ループ結合は総当たりでO(n^2)

  入れ子ループ法は外側の表の各行について内側の表を全件走査して突き合わせる方式である。どちらの表もタプル数がnなら、比較回数はn×nに比例するので計算量はO(n^2)となる。索引が使える場合は内側の走査を減らせるが、単純な入れ子ループでは総当たりになる。

  出典：平成29年度 春期 データベーススペシャリスト試験 am2 問19（IPA）

• 関係データベースにおいて、タプル数nの表二つに対する結合操作を、入れ子ループ法によって実行する場合の計算量はどれか。

  正解：O(n²)

  要点：入れ子ループ結合は総当たりでO(n^2)

  入れ子ループ法は外側の表の各行に対して内側の表を全件走査して突き合わせる。両方の表のタプル数がnであれば比較回数はn×nに比例するので、計算量はO(n^2)になる。索引が使える場合を除き、単純な総当たりになる点が特徴である。

  出典：令和1年度 春期 データベーススペシャリスト試験 am2 問16（IPA）

• 関係データベースにおいて、タプル数nの表二つに対する結合操作を、入れ子ループ法によって実行する場合の計算量はどれか。

  正解：O(n^2)

  要点：入れ子ループ結合の計算量はnの2乗オーダー

  入れ子ループ法は、外側の表の1行ごとに内側の表を全走査して結合条件を確かめる方式である。どちらもn行なら比較回数はn×nに比例するので、計算量はnの2乗のオーダーになる。よってエが正しい。

  出典：令和3年度 秋期 データベーススペシャリスト試験 am2 問15（IPA）