MySQLでIN句の中に大量の値の入ったクエリがフルスキャンを起こす話

こんにちは、freee Developers Advent Calendar 2021、19日目のid:shallow1729です。昨日はtdtdsさんで【マジで】サイバー演習シナリオの作り方【怖い】でした!障害訓練後に攻撃方法を解説された時はリアリティの高さに驚きました。

僕はMySQLを使っていて発生した不思議な挙動の調査の話をしようと思います。

今回問題となったクエリ

今回話題にするクエリは以下のようなシンプルなものです。 SELECT * FROM hoge WHERE id IN (...)

MySQLのパラメーター次第ですが、デフォルトの設定だとこのIN句の中の値の数が数万になると適切なインデックスが用意されていてもフルスキャンが発生する事がありました。このクエリがテーブルのほとんどのレコードを網羅するような場合や高速でレコードを大量にinsertして統計情報が追いつかないケースなど、正常に動いていてもフルスキャンになりそうなケースは思いつきますがいずれにも当てはまらなかったので詳細に調べる事にしました。

オプティマイザーの挙動に関するドキュメントの記載

適切なインデックスの選択のようなクエリの実行計画を作るのはオプティマイザーの仕事です。今回問題になっているDBはAmazon Aurora MySQLなので厳密にはOSSのMySQLとは違う挙動の事もあると思いますが、基本的にはMySQLと同じと考えて大丈夫だと思います。今回のようなIN句の取り扱いはrange optimizerが行うようです。詳細はドキュメントを読んでいただけたらと思いますが、以下に今回のクエリに関係ありそうな記述をまとめます。

  1. range optimizerはIN句の中の値一つずつを別々の等価範囲として取り扱う
  2. 等価範囲の数がeq_range_index_dive_limit未満の場合、index diveを用いて各インデックスを用いた場合に走査する行数の正確な見積もりを行う
  3. 等価範囲の数がeq_range_index_dive_limit以上の場合、統計情報を用いた見積もりを行う
  4. range optimizerの使用するメモリ量がrange_optimizer_max_mem_sizeを超えるとフルスキャンなどを用いるようになる。range optimizerは候補になるインデックスが一つの場合範囲一つあたり約230byteのメモリを使う*1

まず、一つ目の記述は例えばSELECT * FROM hoge WHERE id IN (1, 2, 3)だと範囲が三つあるとして扱うという事です。範囲には大なり小なりを用いたものもありますがIN句のように一致を見るようなクエリの場合を特に等価範囲と呼びます。ちなみにunique keyやprimary keyを用いて検索する場合は高々値一つに対してレコードは一つなので範囲と言うと違和感がありますが、そうでない場合と同様に範囲として扱われます。今回のようにIN句の中に値が2万個入っていると範囲が2万個あるということになります。

次に範囲の数によるオプティマイザーの挙動の変化が解説されています。まずindex diveについて説明すると、等価範囲の両端にアクセスする事でそこからその範囲のレコード数を見積もるというものです。このindex diveは範囲毎に行われるので範囲の数が多すぎると時間がかかりすぎるので、eq_range_index_dive_limit以上になると統計情報を 用いた見積もりに変更します。なので、IN句の値の数が増えると適切なインデックスが選ばれなくなる原因の一つに、index diveが行われなくなったからという説はありそうです。

もう一つオプティマイザーがIN句の値の数で挙動を変えそうなものとして、range optimizerの使うメモリ量が多すぎるとrange optimizerでの実行計画の作成を諦めてフルスキャンなどを選択するという記述もありました。range optimizerの実装を見たところ、確かにrange optimizerは範囲毎で見積もりをするたびにヒープ領域を取りに行こうとして、使用しているメモリ量がrange_optimizer_max_mem_sizeを超えるとドキュメントに書いてあるように以下のようなwarningを吐いてrange optimizerでの処理をやめるような作りになっていました。

Memory capacity of N bytes for
'range_optimizer_max_mem_size' exceeded. 
Range optimization was not done for this query.

今回についてはこちらのメモリ量の問題である事が分かったので、range_optimizer_max_memsizeの上限を変える方針にしました。

range optimizerのメモリ使用量を調べる

range_optimizer_max_memsizeの値を0にすれば上限無くrange optimizerが動くようになるのですが、さすがにちょっと怖かったのでIN句の中の値がどの程度になるかや現状のクエリ量を元にどの程度の上限値を考えれば良いかを見積もる事にしました。当初はドキュメント通り単純にIN句の中の値の数を230で掛けた値で良いと思っていたのですが、実験をしてみると誤差とは言えないレベルでそれより大きい量のメモリを使用していました。この後詳細を書きますが、実験や調査を行ったところ以下のような事が分かりました。

  • range optimizerのメモリ使用量は5.7.12のリリース、Auroraだと2.10.0という比較的新しいバージョンで修正が入れられている。(Bug #79450, Bug #22283790)

  • 候補になるインデックスの数に比例してメモリの使用量が増える。

以下ではこれらの結果の詳細を説明します。

実験方法

  • 使用したのはAWS Aurora MySQL 2.07.2(修正前)と2.10.0(修正後)
  • range_optimizer_max_memsizeを230万(範囲約1万個分)に設定する
  • 約200万レコードをinsertしたhogeというテーブルに対してEXPLAIN SELECT * FROM hoge WHERE id IN (約1万個の値)というクエリを実行し、EXPLAINの結果がフルスキャンを計画しているかを確認する。IN句の中の値を調節してフルスキャンになる境界を探す事でメモリ使用量を見積もる。
  • クエリの対象のテーブル設計は以下の通り(SHOW CREATE TABLEの結果です)
CREATE TABLE `hoge` (
  `id` bigint(20) NOT NULL AUTO_INCREMENT,
  `name` varchar(255) NOT NULL,
  `created_at` datetime NOT NULL,
  `updated_at` datetime NOT NULL,
  PRIMARY KEY (`id`),
) ENGINE=InnoDB AUTO_INCREMENT=2189261 DEFAULT CHARSET=utf8mb4
  • インデックス数によるメモリ使用量の変化については候補となるインデックス(possible keys)の数のみが影響する事がわかったので(id,created_at)のようなidが先頭に来るインデックスを追加していく事で今回のクエリで候補となるインデックス数をコントロールしました。

バージョンによるメモリ使用量の違い

  • possible keysが1つの場合の範囲一つあたりのメモリ使用量
    • 2.07.2: 約800byte
    • 2.10.0: 約238byte
  • possible keysが4つの場合の範囲一つあたりのメモリ使用量
    • 2.07.2: 約1000byte
    • 2.10.0: 約625byte

これらの結果から以下の事が分かりました。

  • バージョンによらずpossible keysが増えるとメモリ使用量が増える。
  • 修正でとても改善している。すごいですね!
  • ドキュメントの記載は修正後のpossible keysが一つのみの場合に対応したものである。

possible keysの数によるメモリ使用量の変化

2.10.0の場合についてのみ、possible keysを1から4まで増やして実験しました。

  • 1つの場合: 約238byte
  • 2つの場合: 約285byte
  • 3つの場合: 約500byte
  • 4つの場合: 約625byte

このようにpossible keysが増えるに従って比較的線形にメモリ使用量も増える事が分かりました。

最後に

今回はIN句でSELECTするだけの単純なクエリがフルスキャンを起こす原因の解説と、range optimizerのメモリ使用量の調査結果をまとめました。ドキュメントやソースコードを追うのも大事ですが、やっぱり動かさないと分からない事もあるなーと感じました。何はともあれ原因が分かってよかったです。 明日はくましゅんさんです。社外登壇した時の話をしてくださるそうです!!

*1:追記: range_optimizer_max_mem_sizeのデフォルト値は5.7.12以降だと8388608なのでIN句の中が4万くらいになるとフルスキャンなどを選ぶようになります。