結合のアルゴリズムには大きく次の3つがある。
-
Nested Loops
-
Hash
-
Soft Merge
Nested Loopsは結合アルゴリズムの基礎となるアルゴリズムで、どのDBMSでもサポートされている。(正確にはNested Loopsの派生バージョンをサポートしている)
※ MySQL は、Nested Loops アルゴリズムまたはそのバリエーションを使用してテーブル間の結合を実行する。PostgreSQLは3つのアルゴリズムすべてをサポートしている。
ポイント
Nested Loopsを理解していれば、JOINするときにどのテーブルを元にSQL文を組み立てれば良いかがわかる!!
Nested Loopsとは
入れ子のループを使うアルゴリズム。for文が入れ子になっているイメージ。
SQLでは、
Table_AとTable_Bを結合する場合、元となるテーブルを外部表、駆動表(Table_A)といい、もう一方のテーブルを内部表(Table_B)という。
Nested Loopsは、次の1と2を駆動表(Table_A)のすべての行に対して繰り返し行う。
-
駆動表(Table_A)を1行スキャンする
-
駆動表1行について、内部表を1行ずつスキャンして、結合条件に一致すればそれを返却
Nested Loopsの特徴
Nested Loopsの特徴は、
-
Table_A, Table_Bの結合対象の行をR(A), R(B)とすると、アクセスされる行数は
R(A) x R(B)
となる。実行時間はこの行数に比例する -
1つのステップで処理する行数が少ないため、HashやSoft Mergeよりメモリ消費が少ない
-
どのDBMSでもサポートされている
どちらを駆動表にするべきか?
R(A) x R(B)
なので変わらないように思われる。
理由は、内部表の結合キーにインデックスが存在すれば、インデックスを使って内部表のループをスキップできるから。(駆動表1行に対して正直に内部表をループしなくて済む。)
最も理想的なケースは、駆動表1レコードに対して内部表1レコードが一意に決まり、インデックスが存在する状態。この場合、内部表のインデックスをたどることでループすることなく1行を特定できるためアクセスする行数は`R(A) x 2
となる。
内部表の結合キーにインデックスが存在していたとしても、ヒットする内部表のレコード数が多いときにはあえて大きなテーブルを駆動表にした方が良いこともある。
例えば、在庫管理システムを作っているとします。
companyテーブル(企業テーブル)とitemテーブル(商品テーブル)があり、itemテーブルは外部キーcompany_id
を持っていて、インデックスが貼られているとする。
companyテーブルの方がレコード数が圧倒的に少ないはずなので、companyテーブルを駆動表にすれば良いと思われる。
SELECT * FROM company INNER JOIN item ON company.id = item.company_id;
しかし、もし大企業がいくつか存在して数百万個の商品を扱っているとしたら....。一つのcompanyのレコードに対して、数百万件のitemテーブル(内部表)のレコードがヒットしてしまうので、ループ回数が多くなってしまう。
さらに、たちの悪いことに中小企業であれば商品数が少ないのでレスポンスは速いが、大企業が含まれているときのみレスポンスが遅くなってしまうといった状態になる。
こういった場合にあえて駆動表に大きなテーブルを選ぶと良い。
SELECT * FROM item INNER JOIN company ON item.company_id = company.id;
itemテーブルを駆動表にすると、companyテーブル(内部表)へのアクセスは主キー(comapny_id)で行われ、これは一意に定まる。outer loopの回数は増えるが、企業の規模(商品数)に影響されることなく、常に一定のパファーマンスを出すことができる。
参考図書
こんな人にオススメ