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

SQL実践入門──高速でわかりやすいクエリの書き方 (WEB+DB PRESS plus)

技術評論社

AmazonKindle楽天市場Yahoo!ショッピング

結合の種類

結合の種類としては、以下の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と違い、等値結合だけでなく、不等式(<.>, <=, >=)を使った結合にも利用できる

参考図書

SQLについてもう一度やり直したいと思っている方はぜひ一読されることをオススメします。

SQL実践入門──高速でわかりやすいクエリの書き方 (WEB+DB PRESS plus)

技術評論社

AmazonKindle楽天市場Yahoo!ショッピング

DB設計についてはこちらの本も！

達人に学ぶDB設計 徹底指南書 初級者で終わりたくないあなたへ

翔泳社

AmazonKindle楽天市場Yahoo!ショッピング