[SQL]JOINの3種類のアルゴリズムについて

SQLのJOINには3種類のアルゴリズムあるということを最近知ったのでまとめてみる。

JOINのアルゴリズム

1. Nested Loop
2. Sort/Merge
3. Hash

基本知識

DBMSごとの実装状況

• Oracle
  • 3種類全部
• MySQL
  • Nested Loopのみ
• PostgreSQL
  • 3種類全部

外部表(駆動表)と内部表

• 外部表(駆動表)
  • JOINするときのベースになる表。以下のSQLでいえば、table1
• 内部表
  • 外部表にくっつける表。以下のSQLでいえば、table2

SELECT *
FROM table1 t1 INNER JOIN table2 t2 on t1.id = t2.id;

最初、なんで外部と内部っていうんだろうと思ったけど、二重のforループと考えると納得いった（合ってるかは不明、でもNested Loopだし・・・）

for(){
  // 外部表を回す外側のループ -> 外側なので外部表
  for(){
    // 外側のループに対する内部のループ -> 内側なので内部表
  }
}

特徴

Nested Loop Join

• 外部表にある全行に対して、内部表から結合キー列の値がマッチするものを探して結合する
• 上記に関連して、外部表にあるレコードが少ないほうがループ数を少なくできるため高速にできる
• 内部表の結合キー列にインデックスがある場合、インデックスを用いて検索できるため高速に処理できる

Sort Merge Join

• 外部表と内部表を結合キー列でソートする
• ソートしたあとに上から結合キー列が一致するものを結合する。(それぞれの値をインクリメントしつつ比較)
• インデックスなしのNested Loop Joinより高速になる
• ソートが重い処理になりがちなので、インデックスがあると高速化が見込める
• Hash Joinと違って不等価結合でも使える

Hash Join

手順がちょっと長いので手順、特徴に分けて記載する。

• 手順

1. オプティマイザが結合する表の件数を比較して、小さい方の表を全件読み取る
2. 1.で選択された表の結合条キー列の値をハッシュ関数にかけてハッシュテーブルを作成する
3. 外部表の結合キー列を同じハッシュ関数で変換->作成したハッシュテーブルを検索
4. ハッシュが同じ列同士を結合する

• 特徴

• 結合キー列にインデックスがなくても高速に結合できる

• 対象件数が増えても結合の負荷が増えにくい（が、ハッシュ表を作成・保存できるだけのメモリは必要）

• ハッシュ関数で処理する都合上、等価結合(=)の場合のみ使用可能

この知識をどう応用するか？

基本的にはDB側で統計情報等をもとにいい感じにしてくれるみたいだけど、上記を知っておくことで業務でスロークエリを改善するような場面があったときに、観点を持って調べることができるはず。

• 実行計画をみて表に合った適切なJOINが使われているか？
• インデックスが適切に使われているか？
• 無駄なJOINをしていないか？
• サブクエリを利用してテーブルを小さくした上でJOINできないか？

※ 前提として遅いクエリで使われているテーブルの特徴を把握する必要はありそう。ドメイン知識というか、ビジネス部分を理解しておくとよい。どのテーブルが件数が多いとか、このカラムはカーディナリティが高いとか。

参考

• 失敗から学ぶRDBの正しい歩き方 Software Design plus
• SQLの苦手を克服する本　データの操作がイメージできれば誰でもできる Software Design plus