ネステッドループ結合(nested loop join)とは

複数のテーブルを結合するSQLを実行すると、ORACLEはネステッドループ、ハッシュ、マージの3種類のいずれかの結合方法を選択した実行計画を立てます。
本ページではネステッドループ結合の特徴やパフォーマンスについて記載します。


ネステッドループ結合の特徴

ネステッドループ結合は最初にアクセスする表(外部表、駆動表とも呼ばれる)をフェッチし、そのフェッチしたデータと結合可能なデータを内部表から検索する処理をループして結合します。 以下のような特徴があります。

RBO、CBO共に選択可能
統計情報取得やダイナミックサンプリング等をせずとも選択可能です。(統計情報を取得しなくても良いというわけではありません。あくまで選択可能というだけです)

等価結合だけでなく非等価、範囲条件の結合も可能
以下のいずれもネステッドループ結合が選択可能です。

select * from tab1 a,tab2 b where a.col1=b.col1
select * from tab1 a,tab2 b where a.col1>b.col1
select * from tab1 a,tab2 b where a.col1<>b.col1

フェッチが始まるまでの時間が他の結合方法よりも早い
ハッシュ結合やマージ結合は結合する2表の外部表側を抽出し終えた後で内部表にアクセスして結合を始めますが、 ネステッドループの場合は外部表と内部表を都度結合していくため最初にフェッチが始まるまでの時間はほとんどの場合ネステッドループが早くなります。 このためオンライン処理等最初に数十件を戻したタイミングで件数制限で処理を中断する可能性があるようなプログラムに適しています。

外部結合の場合結合順序が固定される
以下のsqlをネステッドループで結合する場合はヒントで変えようとしても無視され必ずtab1が外部表になります。

select * from tab1 a,tab2 b where a.col1=b.col1(+)

結合条件式から内部表の索引スキャンが可能
以下のSQLの例ではtab2が内部表ですがtab2自体には抽出条件が無いにも関わらずcol1に対する索引ユニークスキャンが選択できています。 これは外部表からフェッチしたデータのcol1を条件として内部表にアクセスできるためです。これはネステッドループの大きな利点であり、 このケースだとハッシュ結合等では索引は利用されず外部表、内部表共にテーブルフルスキャンとなります。 従って、オンライン系SQLによくある外部表が数件~数十件程度に絞られ、内部表にユニークスキャンできるようなSQLだとその他結合よりも優位性があります

UGAの使用量が少なく一時表領域は使用しない
ハッシュ結合やソートマージ結合はある程度の結合処理が終わるまで結果を戻すことができないため結合途中のデータをメモリ(UGA。足りなくなった場合は一時表領域に書き出し)上に留めておく必要があり 結合データが多いと大きな一時領域が必要になります。 これに対してネステッドループは上述の通り全件結合が終わらない段階で順次結果を戻していくため必要とする一時領域が少ないという特徴があります。

TEST@orcl102 > select * from tab1 a ,tab2 b where a.col1 = b.col1;


実行計画
----------------------------------------------------------
Plan hash value: 2308043903

----------------------------------------------------------------------------------------
| Id  | Operation                    | Name    | Rows  | Bytes | Cost (%CPU)| Time     |
----------------------------------------------------------------------------------------
|   0 | SELECT STATEMENT             |         |     1 |    52 |     3   (0)| 00:00:01 |
|   1 |  NESTED LOOPS                |         |     1 |    52 |     3   (0)| 00:00:01 |
|   2 |   TABLE ACCESS FULL          | TAB1    |     1 |    26 |     2   (0)| 00:00:01 |外部表(駆動表)
|   3 |   TABLE ACCESS BY INDEX ROWID| TAB2    |     1 |    26 |     1   (0)| 00:00:01 |内部表
|*  4 |    INDEX UNIQUE SCAN         | PK_TAB2 |     1 |       |     0   (0)| 00:00:01 |
----------------------------------------------------------------------------------------

Predicate Information (identified by operation id):
---------------------------------------------------

   4 - access("A"."COL1"="B"."COL1")

11g以降のネステッドループ結合について

11g以降、ネステッドループはDISK I/O待ち時間の削減を目的とした新機能が追加されており10gまでとは異なる実行計画が選択される場合があります。 以下のようにネステッドループが2重になっていることが特徴で、内部表へのアクセスは索引までで止めておき、表ブロックに関しては複数一括で取得する動作となるようです。 この実行計画が選択された場合、テーブル部分へのrowidアクセス部分の待機イベントがマルチブロックリード(db_file_scattered_read)になるケースがあります。 (従来のネステッドループではdb file sequential readまたはdb file parallel readとなる。 また、10gR2までであってもバッファのプリウォーム機能の関連でdb_file_scattered_readになる場合もあります)
TEST@ORCL112 > select * from tab1 a,tab2 b where a.col1=b.col1;

実行計画
----------------------------------------------------------
Plan hash value: 1300327366

----------------------------------------------------------------------------------------
| Id  | Operation                    | Name    | Rows  | Bytes | Cost (%CPU)| Time     |
----------------------------------------------------------------------------------------
|   0 | SELECT STATEMENT             |         |     1 |    12 |     4   (0)| 00:00:01 |
|   1 |  NESTED LOOPS                |         |       |       |            |          |
|   2 |   NESTED LOOPS               |         |     1 |    12 |     4   (0)| 00:00:01 |
|   3 |    TABLE ACCESS FULL         | TAB1    |     1 |     6 |     3   (0)| 00:00:01 |
|*  4 |    INDEX UNIQUE SCAN         | PK_TAB2 |     1 |       |     0   (0)| 00:00:01 |
|   5 |   TABLE ACCESS BY INDEX ROWID| TAB2    |     1 |     6 |     1   (0)| 00:00:01 |
----------------------------------------------------------------------------------------

Predicate Information (identified by operation id):
---------------------------------------------------

   4 - access("A"."COL1"="B"."COL1")

ネステッドループ結合の内部最適化機能

上述の通りネステッドループは外部表と内部表を都度結合していく動作が特徴ですが、 前回と結合キーが同じ場合内部表へのアクセスを省略するような動作が見受けられます。 (内部的にキーブレイクのようなロジックが実装されていると思われる) したがって、結合キーのカーディナリティが低い場合は外部表のアクセス結果をソートすることで処理時間短縮化につながる可能性があります。

ネステッドループ結合のパフォーマンス

ネステッドループのcostや処理時間は基本的には以下のように考えられます。

外部表のアクセス時間+(内部表のアクセス時間*外部表の抽出行数)

つまり、ネステッドループが他の結合方式よりも早くなるのは以下のような条件を満たす場合となります。

・外部表の抽出件数が少ない
・内部表へのアクセス方法がユニークスキャンか、少件数に絞れるレンジスキャン等少ないブロック読み込みで済むアクセス方法になっている。
・内部表のキャッシュヒット率が高い(理由は後述)

HASH結合と比較した場合のパフォーマンス

HASH結合と比較した場合、一般的に結合する件数が多くなるほどHASH結合のほうが早くなる可能性が高くなります。 この最も大きな要因は「ネステッドループ結合は物理読み込みが多いとパフォーマンス劣化が激しい」為です。 ネステッドループ結合は外部表へ基本的に索引アクセスとなるため1ブロックずつ物理読み込みをして結合を進めていきます(例外としてパラレルでシングルブロックリードするケースあり)。 これに対しHASH結合+FULLスキャンでは物理読み込みがマルチブロックリードになることから同じ量の物理読み込みに要する時間はネステッドループよりも圧倒的に短くなります。

マニュアル

概要
パフォーマンス・チューニングガイド
★ORACLE案件承ります