結合時のアルゴリズム

2021-12-18

こんにちは

どうも、僕です。

SQL アンチパターンを読んでいて、「外部結合をすると処理のコストが指数関数的に上がっていってしまいます」との記述があり、よくわからなかったので調べました。

JOIN アルゴリズム

そもそも、 SQL の JOIN には、以下の3種類のアルゴリズムが使用されることが多いです。

オラクルと、postges には全部使用されていますが、MySQL には nested loop join のみが使用されています。

nested loop join

sort/merge

hash

この中でも nested loop join のアルゴリズムについて書いていきます。

nested loop join

nested loop join、略して NLJ とも呼ばれます。

単純な NLJ は、愚直にネストした for 文を使用して実装されていて、普通に重いです。

最初に述べた

「外部結合をすると処理のコストが指数関数的に上がっていってしまいます」

というところの答えはここにあり、テーブルの数が増えるとネストするループの数が増えるため、指数関数的に増えることがわかります。

NLJ のアルゴリズム

NLJ のアルゴリズムは以下のようになります。

（[参考](https://dev.mysql.com/doc/refman/5.6/ja/nested-loop-joins.html)）

for each row in t1 matching range {
  for each row in t2 matching reference key {
    if row satisfies join conditions,
    send to client
  }
}

NLJ では、外側のループから、内側のループに、愚直に処理を渡していくため、処理が指数関数的に重くなります。

block nested loop

NLJ のループを減らすための手段として、block nested loop があります。BLN とも呼ばれます。

MySQL では、基本的にインデックスを使用することができない場合に BNL が採用され、バッファを使用することで効率化を図ります。

具体的には、外側のループで読み取られたレコードのバッファリングを使用して、内側のループでテーブルを読み取る回数を減らします。

BLN については、[Block Nested Loop 結合と Batched Key Access 結合](https://dev.mysql.com/doc/refman/5.6/ja/bnl-bka-optimization.html) に詳しくまとめられています。

BNL は元々内部結合の時のみ使用されていましたが、拡張され、ネストした外部結合を含む、外部結合と準結合操作にも使用することができるようになりました。

BNL のアルゴリズム

BNL は以下のようになります。

NLJ と同じページに書いてあるのですが、バッファがなかったら用意する処理が加わりました。

for each row in t1 matching range {
  for each row in t2 matching reference key {
    store used columns from t1, t2 in join buffer
    if buffer is full {
      for each row in t3 {
        for each t1, t2 combination in join buffer {
          if row satisfies join conditions,
          send to client
        }
      }
      empty buffer
    }
  }
}

if buffer is not empty {
  for each row in t3 {
    for each t1, t2 combination in join buffer {
      if row satisfies join conditions,
      send to client
    }
  }
}

3行目の以下の部分に注目して欲しいのですが、ここでバッファにテーブルを保存して、次回以降の参照をバッファから行うことで大幅に処理を減らすことができます。

store used columns from t1, t2 in join buffer

また、ここでのバッファのサイズは [join_buffer_size](https://dev.mysql.com/doc/refman/8.0/en/server-system-variables.html#sysvar_join_buffer_size) というシステム変数に格納されていて、このサイズによって各結合を保存するバッファのサイズが決まります。

また、バッファは、結合の実行前に割り当てられ、クエリの完了後に開放されます。結合するカラムの情報（JOIN t2 ON t1.hoge = t2.t1_hoge）の部分だけが格納されます。

まとめ

MySQL では、NLJ という最適化手法が用いられていて、さらにインデックスが貼られていない場合には BNL というアルゴリズムが使われていることがわかりました。

基本的に、結合時の処理は指数関数的に上昇していくため、あまり大きな結合は避けるべきだということがわかりました。

また、MySQL には、[Optimizing SELECT Statements](https://dev.mysql.com/doc/refman/5.6/en/select-optimization.html) という、クエリの最適化のために内部何がされているか・利用者が何をするべきかを知ることができるページがあります。ここらへんを読むのも面白いかもしれません。