Nested Loopとクエリチューニングの考え方

アンドパッドでDBREをしている久保です。この記事は ANDPAD Advent Calendar 2023 の 12日目の記事です。

初めに

この記事ではMySQLの結合方法の一つであるNested Loop Joinについて紹介し、具体的なクエリの処理順について例を持って紹介します。また、それを踏まえてクエリチューニングの根幹の考え方について触れていきます。ここでは、クエリチューニングそのものの具体的な方法については詳しくは紹介せず、あくまで考え方の紹介になりますのでご注意ください。

Nested Loopとは

Nested Loop Join（NLJ）とは結合アルゴリズムの一種です。これはテーブル1行1行に対して結合先のテーブルをスキャンする手法、大雑把に言えばforループのようなものになります。例えば、t1,t2,t3というテーブルに対し、結合条件以外のwhere条件なしでJOINすると、以下のような疑似コード形式で処理されます。

for each row in t1 {
  for each row in t2 matching join conditions　{
    for each row in t3 matching join conditions　{
      send to client
    }
  }
}

つまりこれは、t1の1行1行に対して結合条件にマッチするt2の行をフェッチして、更にその1行に対して結合条件にマッチするt3の行をフェッチする...といった処理ということです。よって、t1,t2,t3から取得する行数をそれぞれX,Y,Zとすると、X × Y × Zが合計取得行数になります。

ここで、ループの一番外側のテーブルを駆動表もしくは外部表、内側のテーブルを内部表と言います。上記の例でいえば、t1が駆動表、t2,t3が内部表となります。

では、適当なクエリのEXPLAINを見ながら、NestedLoopの挙動を具体的に確認していきます。

具体的な処理の流れ

あるクエリのEXPLAIN結果を見て、前節のNestedLoopの概要を踏まえて、処理の順番を理解していきます。ここではMySQL公式のテストデータベースであるworldデータベースを使って、以下のようなクエリを用意しました。

select country.Name,city.Name 
from country 
join city on country.code = city.CountryCode 
where country.Continent = 'Asia' 
and city.Population > 5000000;

なお、country.codeはcountryのPKであり、country.Continentにはインデックスが付与されていません。また、city.CountryCodeにはインデックスが付与されていますが、city.Populationにはインデックスが付与されていません。

この時、explain結果は以下のようになります。

mysql> Explain select country.Name,city.Name from country join city on country.code = city.CountryCode where country.Continent = 'Asia' and city.Population > 5000000\G
*************************** 1. row ***************************
           id: 1
  select_type: SIMPLE
        table: country
   partitions: NULL
         type: ALL
possible_keys: PRIMARY
          key: NULL
      key_len: NULL
          ref: NULL
         rows: 239
     filtered: 14.29
        Extra: Using where
*************************** 2. row ***************************
           id: 1
  select_type: SIMPLE
        table: city
   partitions: NULL
         type: ref
possible_keys: CountryCode
          key: CountryCode
      key_len: 12
          ref: world.country.Code
         rows: 17
     filtered: 33.33
        Extra: Using where
2 rows in set, 1 warning (0.00 sec)

では、このEXPLAIN結果と前節のNested Loopの挙動を踏まえて、どのような処理順となるのかを解説していきます。

countryテーブルの行の絞り込みから始まります。ここで絞り込まれた結果が次のテーブルと結合されます。
- countryの全行をフェッチ(type:ALL)＆where条件のフィルタリング(Extra:Using where)により結果的に34行ほど(rows*filtered)が絞り込まれます。
この34行のcountryレコード1件1件に対して、cityテーブルの絞り込みがなされます。
- まず、34行のうちのループの初めの1件のCodeカラム値をNと置くと、city.CountryCodeがNである行がユニークでないインデックスを用いて(type:ref)想定17行(rows)取得されます。
- 次に、その17行に対してwhere条件のフィルタリング(Extra:Using where)がなされて、結果的に想定6行ほど(rows*filtered)が絞り込まれます。
- 以上のステップを34件繰り返して結合をします。
結合結果をクライアントに返却します。

以上が具体的なNested Loopの流れとなります。これはJOIN先のテーブルが増えてもネストが増えるだけで処理順は大きく変わりません。

余談ですが、このようにクエリの処理順を書き出してみると、意外とチューニングの糸口が見つかることがよくあるのでオススメです。

どのようにすればクエリが早くなるか

では、先ほどの具体例のクエリを用いて、どのようにすればクエリが早くなるのかを考えていきましょう。なお、先ほどの具体例のクエリは規模の小さいテーブルを相手にしていた事もあり、パフォーマンスに全く難がないクエリですが、便宜上先ほどのクエリを使って説明します。

前節の処理の流れを再度振り返ってみると、countryから取得される行数は34行で、それぞれの行に対してcityから取得される行は約6件でした。つまり、合計で34回のループ×6行取得したことになります。よって、前者の34回の「ループ回数」もしくは後者の内部表の6行の「取得行数」を減らすことができれば、よりスピードが出ることが分かります。

また、前者の34行は全行239件をフェッチした結果をフィルタリングしたものであり、後者の6行はインデックスを辿って取得した結果を whereフィルタリングしたものでした。よって、それぞれの行数取得をインデックスを使って解決できれば、よりスピードが出ることが分かります。

考え方が少し分かってきたので、次の章でここまでを一般化してまとめます。

クエリチューニングの考え方

では、クエリチューニングの考え方を紹介します。駆動表t_1と内部表t_2が存在するとして、t_1,t_2取得する行数をそれぞれX,Yとします。この時、ループがX回行われて、それぞれの行に対して内部表のレコードがY行取得されます。

取得行数を減らす

前節を踏まえてチューニングの観点の１つはとにかくXもしくはYの数を減らすことです。

ループ数Xを減らすには基本的には駆動表のwhere条件の絞り込みを増やすことになります。何か他の条件で絞り込めないか要件を振り返ってみましょう。また、Yの数は1であること、すなわちユニークインデックスでの内部表の捜査(type:eq_ref)であることが最も理想的です。 JOIN順を組み替えてeq_refにならないか思案してみましょう。

場合によってはオプティマイザの見積もり違いにより、内部表の方が絞り込み精度が良かったりすることもあります。その時はより絞り込めるテーブルをfrom句に持ってきてSTRAIGHT_JOIN句でJOIN順序を固定してしまっても良いかもしれません。ただし、オプティマイザの判断を無視することになるので慎重に扱いましょう。

インデックスを使う

そしてもう一つはXとYの取得をインデックスを使って絞り込むようにすることになります。 XとYの数がこれ以上絞り込めなければ、XとY自身の取得の仕方を思案する必要があります。より絞り込めるような新規でインデックスを作成したり、既存のインデックスで使えるものがないか思案しましょう。force indexでインデックスを強制する方法もありますが、これも同様にオプティマイザの判断を無視することになるので慎重に扱いましょう。

最後に

Nested Loopの概要とクエリ処理順、チューニングの考え方を紹介しました。普段クエリチューニングに慣れていない方は是非今回紹介した考え方をもとにチューニングを是非検討してみてください。クエリチューニングには銀の弾丸はありませんが、どこに注目してチューニングを検討していくべきかを体系的に理解すれば、糸口や余地が見つかりやすくなると思います。この記事がその一助になれば幸いです。

アンドパッドでは、「幸せを築く人を、幸せに。」というミッションの実現のため、一緒に働く仲間を大募集しています。会社や事業、開発チームにご興味を持たれた方は、下記のサイトをぜひご覧ください。DBREも絶賛募集中です！

engineer.andpad.co.jp

amamanamam

データベースと仲良くなりたいです