データベースの結合のイメージがいまいち掴めていなかったため、「SQL実践入門」を読んで、結合のアルゴリズムをまとめておく。

結合の種類

結合の種類としては、以下の3種類が存在する。

  • Nested Loops
  • Hash
  • SortMerge

Nested Loops

入れ子のループを使うアルゴリズム。

外側のループの対象となるテーブル(Table_A)を駆動表(driving table)もしくは、外部表(outer table)と呼ぶ。

結合の流れ

  1. 駆動表の1行に対して、内部表を1行ずつスキャンして、結合条件にマッチするものを返却する。
  2. 駆動表の全ての行に対して繰り返す。

Table_A、Table_Bの結合対象の行数をそれぞれR(A)、R(B)とすると、アクセスする行数はR(A)×R(B)となる。

どちらのテーブルを駆動表にするか?

一見、どちらのテーブルを駆動表にしてもアクセス行数は、R(A)×R(B)R(B)×R(A)で変わらないように思われるが、駆動表の選択はNested Loopsの性能において重要な意味を持つ。

⇛「駆動表が小さいほど、Nested Loopsの性能は良い」

ここで重要な点は、内部表の列にインデックスが存在すること。

内部表の結合キーの列にインデックスが存在する場合、そのインデックスをたどることによって、DBMSは駆動表の1行に対して内部表を馬鹿正直にループする必要がなくなる。

理想的なケースとして、駆動表のレコード1行に対して内部表のレコードが1行に対応していれば、内部表のインデックスをたどることでループすることなく1行を特定できる。その結果、アクセス行数は、R(A)×2となる。

内部表のループをどれだけスキップできるかがポイント

  • 内部表が結合キーで一意だと内部ループを完全にスキップ可能
  • 内部表が結合キーで一意にならないと内部ループが残る

SQLチューニングの基本

  1. 駆動表の小さなNested Loops
  2. 内部表の結合キーにインデックス

Hash

  • 結合テーブルからハッシュテーブルを作成するため、Nested Loopsと比べるとメモリを多く消費する
  • メモリ内にハッシュテーブルが収まらないとストレージを使用して、遅延が発生する ⇛  「Temp落ち」
  • 出力となるハッシュ値は、入力値の順序性を保存しないため、等値結合でしか使用できない

Hash Joinが有効なケース

  • Nested Loopsで適切な駆動表(相対的に十分に小さいテーブル)が存在しない場合
  • 駆動表として小さいテーブルは指定できるが、内部表のヒット件数が多い場合
  • Nested Loopsの内部表にインデックスが存在しない場合

SortMerge

  • 対象テーブルをどちらもソートする必要があるため、Nested Loopsよりも多くのメモリを消費する
  • Hashと違い、等値結合だけでなく、不等式(<.>, <=, >=)を使った結合にも利用できる

参考図書