ネステッド・ループ結合 (NESTED LOOP JOIN)

ネステッドループ結合とは、もっとも基本的な結合である。例えば2つの表におけるネステッドループ結合を2重ループした繰り返し処理のプログラムを想像するとシンプルに理解できる。

SELECT t1.colA, t2.colB FROM t1, t2 
WHERE
        t1.key1 = t2.key2
and     t1.colA = 'A'
and     t2.colB = 'B'

という SQL について考えてみる。
テーブル t1 は配列 a1、テーブル t2 を配列 a2 と置き換えると

探索する アルゴリズム (A)

準備

  1. 変数 conditionA に条件 'A' を代入する
  2. 変数 conditionBに条件 'B' を代入する

変数 conditionAconditionB を引数に以下の処理を呼び出す

処理の内容

  1. 配列 a1 を 1 〜 n (配列にサイズ) まで ループ変数 i でループする (for)
  2. 配列 a1[i].colA が 引数 conditionA と違う値なら (1) のループの最初に戻る (continue) … (処理 1)
  3. 配列 a1[i].key1 を取り出し、変数 joinKey に代入する。
  4. 変数 joinKeyconditionB を引数に以下の処理を呼び出す
    1. 配列 a2 を 1 〜 m (配列にサイズ) まで ループ変数 j でループする (for)
    2. 配列 a2[j].key2 が 変数 joinKey と違う値なら (i) のループの最初に戻る (continue) … (処理 2-1)
    3. 配列 a[i].colB が conditionB と違う値なら (i) のループの最初に戻る (continue) … (処理 2-2)
    4. ループの終端
  5. ループの終端

のようなプログラムになる。(インデックス抜きに考えると、こんな雰囲気 ;) ということで…)

外部表(駆動表)と内部表:ネステッド・ループ結合を効率良くする

外部表の選択レコード数が少ないとパフォーマンスが向上する

上記の、「アルゴリズム(A)」 を使用したネステッドループ結合において、配列データの内容をあらかじめ知っている場合には処理を効率よくするために書き換えることができる。

例えば、配列 a1 の colA には 'A' が大量にあり、配列 a2 の colB には 'B' が存在しない場合には (処理 2-2) が処理されるまで判別できない。
逆に 配列 a1 の colA には 'A' が存在せず、配列 a2 の colB には 'B' が大量に存在する場合には (処理 1) の処理だけで済んでしまう。
このように、作業前に配列 a1 と配列 a2 の要素の特性を調べておくことで処理の順序を変化させ、劇的にパフォーマンスをアップすることができる。(=統計情報の収集とコストベースオプティマイザの働き)

このときループの外部に配置する表を 外部表(駆動表)、内部に配置する表を 内部表 という。
外部表の選択は、オプティマイザ が SQL の条件と 統計情報 を利用することで最適(※注意参照)と思われる表を選択する。

※注意 ここまで読んで、それぞれの 有効なカーディナリティ が少ない表を外部表にすれば良いのか…という結論に辿りついてしまった方は、うまくミスリードにかかってしまっている。(このまま、続きをお読みください)

外部表のカーディナリティが少なくてもパフォーマンスが向上しない?

基本的に 有効なカーディナリティ が少ない表を外部表に選択すると「処理回数」は減少するのは間違いないが、トータルレスポンスは上記、アルゴリズム(A) の (処理 1) の処理と (処理 2-1) 、 (処理 2-2) に到達するまでの処理コストが同程度という前提があってのことである。(似た内容でも中身は月とスッポンの可能性)

仮に外部表と内部表のどちらか一方のみインデックスによるアクセスが許されるという制約があった場合、もし外部表にインデックスを使用すると外部表で選択された分だけ内部表に対してテーブル・フルスキャンをすることになる。(念のため、フルスキャンとインデックススキャンは相当に違います。)

と言いつつ、データベースの設計をしている技術者は適切に結合因子(結合条件となるキー)には プライマリキー、または、インデックスを設置していることの方が多いので表面化することが少ない。(それゆえにミスリーディングもされやすい)

 

ちなみにネステッド・ループ結合において、インデックスの無いキャッシュされた 小規模表 とインデックスでアクセスできる大規模表においては、フルスキャンであってもメモリ上にある小規模表を内部表にした方がパフォーマンスが良い。⇒ ハッシュ結合 への進化

ネステッド・ループ結合のコスト

ヒント句で制御する場合には、外部表における 有効なカーディナリティ が全てではなく、外部表にアクセスするためのコスト、および、内部表にアクセスするためのコストもパフォーマンスを向上させる点において重要な要因である。

また、Oracle にとってネステッド・ループ結合が表の結合の唯一の手段ではない。
ネステッド・ループ結合が苦手とする結合になる場合は ソートマージ結合 や ハッシュ結合 が選択されることで、ネステッド・ループ結合に比べ、より優れたパフォーマンスを出す。
現在のサーバー環境では、高速な CPU を多数載せ、大量のメモリを搭載したハードウェアはハッシュ結合に一層有利に働き、かなり重要な位置を占めるまでになっている。(と思う。さらに補足:ルールベースオプティマイザ ではハッシュ結合は利用できない。)



日本オラクル
■ 日本オラクル 株式会社
■ オラクルマスター資格 (オラクルマスターとは
■ オラクルサポートセンター