SQL

SQL INDEXつきテーブルを結合する際の駆動表は小さく!

結合順序により速度が変わる話。

INDEXをつけているカラムの値がちゃんとばらついていれば、レコード数が少ないテーブルを駆動表に選ぶことでスキャンレコード数を減らせます。


前置き

テーブルを結合するアルゴリズムの一つに、Nested Loopがあります。

テーブルのレコードごとに、もう一方のテーブルのレコードを一つずつ見に行く2重ループのアルゴリズムです。

NestedLoop.jpg

左の最初にスキャンするテーブルAは駆動表、右のテーブルBは内部表と呼ばれます。テーブルAとテーブルBのレコード数をそれぞれR(A)R(B)とすると、スキャンするレコードの数は単純に計算してR(A) × R(B)。上図の場合は12になります。結合順序を変えても同じ。

しかしINDEXが張られてるとスキャンレコード数は減ります。


INDEXとスキャンレコード数の関係

内部表の結合キーのカラムにINDEXが張られていると、内部表でスキャンするレコード数が減ります。駆動表のレコード1件に対し、INDEXをたどって内部表のスキャンレコードを絞れるからです。主キーを結合キーに指定した場合は、内部表のスキャンレコード1件になります。

kudo1.jpeg

上図ではテーブルAの3番目のレコードの結合キーに対応するテーブルBのレコードがなかったため、全体のスキャンレコード数は7になっています。

もしR(B) < R(A)であれば、テーブルBを駆動表に選ぶことでスキャン数をR(B) × 2に減らせます。

kudo2.jpg

上図では先ほどの結合対象がないレコードのスキャンが減っているので、全体のスキャンレコード数は6に減っています。

仮に駆動表が大きくなるような順番でクエリを書いていても、オプティマイザがいい感じに順番を入れ替えてくれます。


ユースケース

パッとは思いつかなかった。。

完全に想像ですが、転職サービスなどで以下の感じでデータ管理してる場合、いいユースケースになりそうです。



  • USERテーブル


    • 会員情報を入れる。主キーはUSER_ID




  • CAREER_SHEETテーブル


    • 会員ごとの経歴シート情報を入れる。経歴シート作成時にユーザーごとのレコードが作られるので、常にUSERよりもレコード数は少ない(会員登録だけして経歴シート未記入の人もいるため)。



これらのテーブルをUSER_IDをキーにして結合する場合は、レコード数のCAREER_SHEETを駆動表に選択するのが正解ですね。


注意

INDEXが張られているカラムの値が十分にばらついてない場合は、駆動表が小さくても結局内部表のループがたくさん残ってしまうので、期待した効果は出ないです。


参考資料

SQL実践入門──高速でわかりやすいクエリの書き方