Nested Loop結合は、実際にはネストしたループではない


某書を読むと、Nested Loop結合がこう説明されていた。

どのような場合でも適用できる反面、高い性能を得るのは難しい。
以降で述べるような、より効率の高いほかの方法が使えない場合にこの方法を使うことになる。
...
ネストループ結合では、それぞのテーブルのカラムを1つずつ比較して総当りで調べていく。
...
繰り返しの回数は、2つのテーブルのカラムの数の積になる。

これはちょっと怪しい説明じゃないだろうか。
「総当りで比較する」というのは概念の話であって、オプティマイザはめったにそんな実行計画を立てない。


オプティマイザが Nested Loop を選択するのは、ふつうは内部表の結合カラムにインデックスがある場合で、この場合内部表はランダムアクセスされる。
結合カラムにインデックスがない場合は、多分 Hash Join が選択されるだろう。ほんとに二重ループする Nested Loop 結合の実行計画を出現させるのはなかなか難しい*1
「Nested Loopは二重ループを実行するから遅い・劣っている」みたいな書き方はミスリーディングだと思う。

*1:さっき手元のSQL Server 2005で試してみたら、結合カラムにインデックスがなくてもNested Loopが選択されるケースがまれにあることが判明した。びっくりした