🙄

MySQLにおけるjoinアルゴリズム

2023/01/24に公開約1,700字

joinアルゴリズムの種類

MySQLがサポートするJOINアルゴリズムで代表的なのはネステッド・ループ(NLJ)。

ネステッド・ループ(NLJ)とは

NESTED LOOPS JOINとは,一方の表から1行ずつ行を取り出し,もう一方の表のそれぞれの行に突き合わせて,結合条件を満たす行を取り出す入れ子型のループ処理の結合方法。
めちゃくちゃ簡易的に要約するとレコードの掛け算です。

(例)テーブルAに10行、テーブルBに10行ある場合
NLJで結合すると、10✖️10=100回程度レコードの結合が行われる。

1000✖️1000でも一気に100万回になってしまうので、これが掛け算(join)の怖さの所以ですね。

簡易コードで見るNLJ

SELECT *
FROM テーブルA 
	INNER JOIN テーブルB 
	on テーブルA.id = テーブルB.hoge_id;

上記の結合での、NLJの動きをコードに簡易的に表すと下記のようになります。

for each レコード in テーブルA {
  for each レコード in テーブルB {
    send  結合したレコード to client
  }
}

この時、外側でループしているテーブルAが駆動表、内側でループしているテーブルBを内部表と言います。

はい、これが非常に覚えにくいです。笑
駆動表は外部表とも言います。(統一してくれ...)
結合される土台となるテーブルが駆動表、駆動表、駆動表!気合で覚えてください。

いろんなサイトで見かけますが、(個人調べで)これよりわかりやすい画像はなかったです。

どうNLJと向き合うか

シンプルに算数の問題になりますけど、n✖️mの掛け算の結果をどうすれば減らせるのか。
はい、nとmの数が減ればいいのです!

メジャーなアプローチとして2つあると思います。

  1. レコードを事前に絞って、駆動表のレコード数mと内部表のレコード数nの値を減らす

    例えばこのように、whereで条件を絞っています。

SELECT *
FROM
    (  
        SELECT
            *
        FROM
            テーブルA
        WHERE
            category = 'パソコン'   -- 例としてカテゴリで絞り込み
    ) AS サブテーブルA
    INNER JOIN
        テーブルB
    ON  サブテーブルA.id = テーブルB.hoge_id;
  1. インデックスを貼って、フルテーブルスキャンしないようにする

    例えば、内部表にインデックスを貼った場合。
    内部表を、丁寧に一番頭から下までというフルテーブルスキャンは不要になります。

まとめ

NLJはシンプルに考えると、結合時にテーブル同士のレコードが掛け算される。
それゆえ、いかに掛け算のnとmの数を減らすかを考える。

参照

http://itdoc.hitachi.co.jp/manuals/3020/3020647000/W4700022.HTM

https://nishinatoshiharu.com/overview-nested-loopjoin/#:~:text=1行ずつレコードが,表)』と呼びます。

Discussion

ログインするとコメントできます