【SQL】結合 NLJ

JOINのアルゴリズム

テーブル結合するSQLを実行するとRDBは内部的にテーブルを結合する処理を実行する。コレがjoin。
アルゴリズムは知る限り3種類あり、当たり前ですが記述によりパフォーマンスが異なります。

・Nested Loop Join(NLJ)
・Hash Join
・Merge Join

知るかぎりMySQLはNested Loop Joinとその変形系しか無いはず…

Nested Loop Join

取り出す表を「外部表」または「駆動表」

突合せる表を「内部表」

とし、外部表から内部表にあるものを1行ずつ取り出し突き合わせていきます。

内部表のindexを利用し結合条件を評価すると処理効率が良くなる。

しかし、結合条件の全ての列がindexに含まれていない場合、評価が判定できず表データとの突合せが発生するため処理効率が悪くなる。

超平たく書けばNested Loop Joinは外部表と内部表を都度結合していく感じです。

前回と結合keyが同じ場合、内部表へのアクセスを省略するような動作が見受けられるため、結合keyのカーディナリティが低い場合は外部表のアクセス結果をソートすることで処理時間短縮化につながる可能性があります。

 

NLJにおいてオプティマイザが判断している事は2つ

・どのインデックスを用いてJOINを実行するか
・どのテーブルから先にJOINするか

考えうるJOIN順序のバリエーションと、行の絞込みや結合条件として使用するindexの組み合わせから、最も効率の良いものを選ぶのがオプティマイザの課題。

インデックスの検索は、必要な行だけをフェッチできるので行数が少ない場合には効率的だが、テーブルの大半をフェッチしなければいけないような場合には、ランダムアクセスなので効率が低下します。

テーブルスキャンはシーケンシャルアクセスなので、テーブルのほとんどのレコードをフェッチする場合には高速になる。

オプティマイザは実行計画のコストを計算、最低コストなものを選択することですね。

結合のパフォーマンス

外部表のアクセス時間＋(内部表のアクセス時間*外部表の抽出行数)
Nested Loop Joinが他の結合方式よりも早くなるのは以下のような条件になります。

・外部表の抽出件数が少ない
・内部表へのアクセス方法がINDEX UNIQUE SCAN、または少件数に絞れるINDEX RANGE SCAN等少ないブロック読み込みで済むアクセス
・Nested Loop Joinは物理読込みが多いとパフォーマンス劣化が激しいため、内部表のキャッシュヒット率が高いと早くなる

駆動表のレコード数をn

内部表のレコード数をm

とした時SQLを工夫してnとmを小さくすることが挙げられ、

適切にインデックスを作ってそのn*m個を高速にフェッチできるようにすることを考えます。

EXPLAINを使えば、どちらのテーブルが駆動表か内部表か調べることができる