データベース・SQL

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

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

  • Nested Loops

  • Hash

  • Soft Merge

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

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

ポイント

Nested Loopsを理解していれば、JOINするときにどのテーブルを元にSQL文を組み立てれば良いかがわかる!!

Nested Loopsとは

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

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

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

nested loops 図

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

  1. 駆動表(Table_A)を1行スキャンする

  2. 駆動表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の回数は増えるが、企業の規模(商品数)に影響されることなく、常に一定のパファーマンスを出すことができる。

 

参考図書

こんな人にオススメ

パファーマンスを意識したSQL文を書けるようになりたい人

イチオシ記事

1

自己紹介 フリーランスエンジニアをしているヨノと申します。 独学でプログラミングを学び、ソシャゲ・SaaS開発などを経て、2018年からフリーランスエンジニアとして活動しています。 主にバックエンド中 ...

2

はじめまして、フリーランスエンジニアのヨノと申します。 自己紹介 独学でプログラミングを学び、ソシャゲ・SaaS開発などを経て、2018年からフリーランスエンジニアとして活動しています。 主にバックエ ...

3

ネット上で色々言われているフリーランスエンジニア....。「本当はどうなの?」と思っている人は多いでしょう。 そこで本記事ではフリーランスエンジニア5年生の私が、ネット上の意見も引用しながら実態を解説 ...

-データベース・SQL