タイムライン的なものをSELECTだけで実装しようと思った時に、Nested LoopなクエリでUsing temporary; Using filesortが出るようなそこそこ遅いクエリになる。その時にMySQLがインデックスをどう辿っているかを知りたかったので調べてみた。MySQLバージョンは8.0.33。
あまり自信はないので、もし間違った話をしていたら教えて欲しい。
どのようなクエリを検証するか
タイムラインの取得ができるような、ユーザー・フォロー関係・投稿の3つのテーブルを作る。スキーマは次の通り。
CREATE TABLE users ( id INTEGER PRIMARY KEY AUTO_INCREMENT, name VARCHAR(100) NOT NULL ); CREATE TABLE follows ( id INTEGER PRIMARY KEY AUTO_INCREMENT, follower_id INTEGER NOT NULL, followee_id INTEGER NOT NULL, UNIQUE KEY (follower_id, followee_id), FOREIGN KEY (follower_id) REFERENCES users(id), FOREIGN KEY (followee_id) REFERENCES users(id) ); CREATE TABLE posts ( id INTEGER PRIMARY KEY AUTO_INCREMENT, user_id INTEGER NOT NULL, body TEXT NOT NULL, posted_at DATETIME NOT NULL, deleted BOOLEAN NOT NULL DEFAULT FALSE, FOREIGN KEY (user_id) REFERENCES users(id), KEY idx_user_id_posted_at (user_id, posted_at) );
このスキーマに対して、タイムラインの取得のクエリを投げて、どのようにインデックスを参照しているか検証していく。たとえばタイムラインの1ページ目を取得するような、あるユーザーがフォローしている投稿を投稿の新しい順に20件取得するというクエリは以下の通り。このクエリの場合、インデックスのみで条件を満たす20件を取得することはできないため、非常に多くの行を読み込んでfilesortを行う必要があるクエリとなっている。
SELECT posts.* FROM posts JOIN follows ON posts.user_id = follows.followee_id WHERE follows.follower_id = 1 AND deleted = FALSE ORDER BY posts.posted_at DESC LIMIT 20;
EXPLAINの内容
*************************** 1. row ***************************
id: 1
select_type: SIMPLE
table: follows
partitions: NULL
type: ref
possible_keys: follower_id,followee_id
key: follower_id
key_len: 4
ref: const
rows: 1000
filtered: 100.00
Extra: Using index; Using temporary; Using filesort
*************************** 2. row ***************************
id: 1
select_type: SIMPLE
table: posts
partitions: NULL
type: ref
possible_keys: idx_user_id_posted_at
key: idx_user_id_posted_at
key_len: 4
ref: db-range-query-perf.follows.followee_id
rows: 972
filtered: 10.00
Extra: Using where
どのようにインデックスを辿るか
先にどうインデックスを辿るかの結論を言うと、https://speakerdeck.com/a_bicky/rails-developers-meetup-2018-day-1?slide=48 の図のようにスキャンしていく。
引用元: https://speakerdeck.com/a_bicky/rails-developers-meetup-2018-day-1?slide=48
たとえば先ほどクエリでの(user_id, posted_at)のマルチカラムインデックスを使ったNested Loopの場合、次のようになる。
- followee_idとして使われる値を1つ取ってくる（例: followee_id = 1）
- B+Treeのインデックスからfollowee_id = 1の条件にマッチする1つ目のエントリを見つける。MySQL上ではread_keyと呼ばれる
- 1つ目のエントリから次のエントリを辿る。MySQL上ではread_nextと呼ばれる
- 次のエントリを辿り続ける。read_nextをひたすら繰り返す
- ある時点で条件から外れたら、そこで探索を終えて、その行を読み捨てる
- 次のfollowee_idを使って2回目のループを行う
- ...
では実際にそうなっているかを検証してみる。
大量のデータを作る
一定のデータがないと検証がしづらいので、
- 1000ユーザー
- それぞれ1000投稿。投稿日や論理削除フラグは適度にランダム性を持たせる
- それぞれ相互フォロー
というデータを10セット作る。このようなスクリプトを使ってデータを作成した。
> select count(*) from users; +----------+ | count(*) | +----------+ | 10000 | +----------+ > select count(*) from posts; +----------+ | count(*) | +----------+ | 10000000 | +----------+ > select count(*) from follows; +----------+ | count(*) | +----------+ | 10000000 | +----------+
フォローしているユーザーの投稿を投稿の新しい順に20件取得するクエリの検証
では最初に紹介したクエリから検証してみる。
SELECT posts.* FROM posts JOIN follows ON posts.user_id = follows.followee_id WHERE follows.follower_id = 1 AND deleted = FALSE ORDER BY posts.posted_at DESC LIMIT 20;
最初にEXPLAIN ANALYZEを使って、実際にどのくらいの行に触っているかを見てみよう。
-> Limit: 20 row(s) (actual time=984..984 rows=20 loops=1) -> Sort: posts.posted_at DESC, limit input to 20 row(s) per chunk (actual time=984..984 rows=20 loops=1) -> Stream results (cost=977365 rows=97258) (actual time=0.119..909 rows=998985 loops=1) -> Nested loop inner join (cost=977365 rows=97258) (actual time=0.111..791 rows=998985 loops=1) -> Covering index lookup on follows using follower_id (follower_id=1) (cost=102 rows=1000) (actual time=0.0651..0.297 rows=1000 loops=1) -> Filter: (posts.deleted = false) (cost=880 rows=97.3) (actual time=0.00224..0.756 rows=999 loops=1000) -> Index lookup on posts using idx_user_id_posted_at (user_id=`follows`.followee_id) (cost=880 rows=973) (actual time=0.00216..0.718 rows=1000 loops=1000)
この結果から以下のことが読み取れる。あるユーザーが1000フォローし、それぞれのユーザーが1000postsあると考えれば取得する行数は一致する。
- Nested loopを使ってJOINを実現している
- followsはfollower_idのインデックスを使って1回で1000行取得している
- postsの取得処理は1000ループ走り、それぞれのloopではidx_user_id_posted_atのインデックスを使って1000行取得している。さらにそれをdeletedでフィルタしている
- すべてを結合した結果が998985行(deletedを除いた分)あり、それをクイックソートし、上から20行取得している
ここからインデックスのたどり方を予想すると
- followsのread_key 1 + read_next 1000
- read_keyで1行取得 -> read_nextで残り999行取得 -> 最後のread_nextで取得した1行で条件を外れ、読み捨てる
- postsのread_key 1000 + read_next 1000 x 1000
- Nested loop1回につき、read_key 1 + read_next 999 + read_next 1(読み捨て)
- Nested loopが1000回ある
- 合計でread_keyが1001、read_nextが1001000
本当にこうなっているかを、SESSION STATUSから取得する。
FLUSH STATUS; -- クエリ実行 SHOW SESSION STATUS LIKE 'Handler%'; +----------------------------+---------+ | Variable_name | Value | +----------------------------+---------+ | Handler_commit | 1 | | Handler_delete | 0 | | Handler_discover | 0 | | Handler_external_lock | 4 | | Handler_mrr_init | 0 | | Handler_prepare | 0 | | Handler_read_first | 0 | | Handler_read_key | 1001 | | Handler_read_last | 0 | | Handler_read_next | 1001000 | | Handler_read_prev | 0 | | Handler_read_rnd | 0 | | Handler_read_rnd_next | 0 | | Handler_rollback | 0 | | Handler_savepoint | 0 | | Handler_savepoint_rollback | 0 | | Handler_update | 0 | | Handler_write | 0 | +----------------------------+---------+
予想通り合計でread_keyが1001、read_nextが1001000となっていた。
posted_atに上限を付けるとインデックスの探索を途中で終えてくれるか
タイムラインにおいて、カーソルベースのページャを使うことがある。その場合posted_atに上限が付くクエリが発行される。たとえば
SELECT posts.* FROM posts JOIN follows ON posts.user_id = follows.followee_id WHERE follows.follower_id = 1 AND posts.deleted = FALSE AND posts.posted_at <= '2023-07-01 02:41:52.000' ORDER BY posts.posted_at DESC LIMIT 20;
先ほどのインデックスのたどり方から考えると、(user_id, posted_at)はuser_id ASC -> posted_at ASCと並んでいるはずなので、それぞれのloopごとにposted_atの上限を超えたところまで辿った時点で探索を打ち切れるはずである。本当にこのようになるだろうか？
こちらも実行して試してみよう。まずEXPLAIN ANALYZEの結果を貼る。
-> Limit: 20 row(s) (actual time=814..814 rows=20 loops=1)
-> Sort: posts.posted_at DESC, limit input to 20 row(s) per chunk (actual time=814..814 rows=20 loops=1)
-> Stream results (cost=977365 rows=32416) (actual time=0.119..746 rows=737058 loops=1)
-> Nested loop inner join (cost=977365 rows=32416) (actual time=0.112..657 rows=737058 loops=1)
-> Covering index lookup on follows using follower_id (follower_id=1) (cost=102 rows=1000) (actual time=0.0629..0.265 rows=1000 loops=1)
-> Filter: (posts.deleted = false) (cost=880 rows=32.4) (actual time=0.00221..0.632 rows=737 loops=1000)
-> Index lookup on posts using idx_user_id_posted_at (user_id=`follows`.followee_id), with index condition: (posts.posted_at <= TIMESTAMP'2023-07-01 02:41:52') (cost=880 rows=973) (actual time=0.00213..0.604 rows=738 loops=1000)
ここから読み取れることは
- 先ほどのクエリと違い、postsの取得処理のidx_user_id_posted_atの利用時に、ICP最適化が行われ、posted_atの条件文が利用されている
- ソートする時に利用する行数自体が737058まで減っている
ただしICP最適化が行われたとしてもインデックスの探索を打ち切ってくれるとは限らない。そこも確認してみよう。
インデックスの探索を打ち切ってくれていたとしたら、read_keyは元々の数と同じで、read_nextの数が減っているはずである。これも試してみると、想定通りの結果となった。
+----------------------------+--------+ | Variable_name | Value | +----------------------------+--------+ | Handler_commit | 1 | | Handler_delete | 0 | | Handler_discover | 0 | | Handler_external_lock | 4 | | Handler_mrr_init | 0 | | Handler_prepare | 0 | | Handler_read_first | 0 | | Handler_read_key | 1001 | | Handler_read_last | 0 | | Handler_read_next | 738821 | | Handler_read_prev | 0 | | Handler_read_rnd | 0 | | Handler_read_rnd_next | 0 | | Handler_rollback | 0 | | Handler_savepoint | 0 | | Handler_savepoint_rollback | 0 | | Handler_update | 0 | | Handler_write | 0 | +----------------------------+--------+
この結果から、うまく条件を工夫すれば、インデックスの探索自体も途中で終わらせることができると分かった。
まとめ
今回はタイムライン取得のようなNested loopになるクエリがインデックスをどのように参照しているか、実際に動作を確認しながら検証した。また条件文をうまく指定することで、インデックス自体の探索も途中で打ち切れることも分かった。
この辺りの知識を使って、少し重いクエリでもMySQLだけで多少なりともパフォーマンスチューニングできるようにしてみたい。
参考文献
- MySQL with InnoDB のインデックスの基礎知識とありがちな間違い - クックパッド開発者ブログ
- 雑なMySQLパフォーマンスチューニング
- Rails Developers Meetup 2018 で「MySQL/InnoDB の裏側」を発表しました - あらびき日記
