SQL結合のアルゴリズムNested Loopsとは？

結合のアルゴリズムには大きく次の3つがある。

• Nested Loops

• Hash

• Soft Merge

Nested Loopsは結合アルゴリズムの基礎となるアルゴリズムで、どのDBMSでもサポートされている。（正確にはNested Loopsの派生バージョンをサポートしている）

※　MySQL は、Nested Loops アルゴリズムまたはそのバリエーションを使用してテーブル間の結合を実行する。PostgreSQLは3つのアルゴリズムすべてをサポートしている。

Nested Loopsとは

入れ子のループを使うアルゴリズム。for文が入れ子になっているイメージ。

SQLでは、1度につき2つのテーブルしか結合しないため実質二重ループ。

Table_AとTable_Bを結合する場合、元となるテーブルを外部表、駆動表（Table_A）といい、もう一方のテーブルを内部表（Table_B）という。

Nested Loopsは、次の1と2を駆動表（Table_A）のすべての行に対して繰り返し行う。

Nested Loopsの特徴

Nested Loopsの特徴は、

どちらを駆動表にするべきか？

どちらを駆動表にしても、アクセスする行数は 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の回数は増えるが、企業の規模（商品数）に影響されることなく、常に一定のパファーマンスを出すことができる。

参考図書