🙄

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

2023/01/24に公開

MySQL

初心者

入門

tech

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の数が減ればいいのです！

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

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

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

SELECT *
FROM
    (  
        SELECT
            *
        FROM
            テーブルA
        WHERE
            category = 'パソコン'   -- 例としてカテゴリで絞り込み
    ) AS サブテーブルA
    INNER JOIN
        テーブルB
    ON  サブテーブルA.id = テーブルB.hoge_id;

インデックスを貼って、フルテーブルスキャンしないようにする

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

まとめ

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