毎日温泉に入りたい♨︎

見た物や買った物、投資についてを書いてますヽ(* ॑꒳ ॑* )ノダァーッ!!

SQLの結合 NLJ

JOINのアルゴリズム

テーブル結合するSQLを実行するとRDBは内部的にテーブルを結合する処理を実行する。
アルゴリズムは知る限り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を使えば、どちらのテーブルが駆動表か内部表か調べることができるので後はよしなに

Presented by「瑣末な問題」