遅くなってしまうoffsetを早くするクエリ設計

前提

MySQL 5.6 で検証しました。

この記事を読んで学べること

• ページネーションにおけるSQLのパフォーマンス改善

発生した問題

とあるAPIのレスポンスのうち、1％程度のLatencyがかなり遅い。
原因はSlowQueryだが、当該のクエリのWhere句のColumnにはIndexが付与されている。
当該のクエリは OFFSET でページネーションされている。

まずは実際のパフォーマンスを計測

クエリを調査するためには事象が起きている同じ状態でEXPLAINコマンドを行うことでおおよその状況を判断することができます。

EXPLAINコマンドではMySQLのオプティマイザがその当時の状況を統計学的に判断した実行計画がわかります。
（InnoDBの統計学情報はテーブル全体から一部の情報をランダムに選び出し、全体を推測する方法を用いているらしい）
レコード数 や 検索条件のパラメータの値 が異なるだけで 実行計画が変わる みたいなので、頭の片隅に置いておいた方が良さそうです。

本番環境で以下のクエリを実行してみます

EXPLAIN SELECT * FROM items WHERE items . user_id = ? AND items . category_id = ? AND items . type_id = ? ORDER BY items . id ASC LIMIT ? OFFSET ?

id	select_type	table	type	possible_keys	key	key_len	ref	rows	Extra
1	SIMPLE	items	ref	xxx, yyy, zzz	yyy	z	const,const,const	390812	Using where

実行計画確認時点で何が起きていそうと推測ができるか

• 期待しているインデックス以外にも使われる可能性のあるインデックスがいくつか存在する
  • EXPLAIN実行段階では yyy の実行が予測されているが、実際の実行では、非効率に思われるインデックスが使われる（インデックス自体使われないこともあるらしい？）こともあるらしいので要注意です。
• 処理には必要なさそうなすべてのフィールドの値を取得している
  • インデックスに使われていないすべての値をロードすると処理は遅くなるようです。
  • 無駄にオーバーヘッドが増加してしまい、よくはなさそうです。
• なめているレコード数が多い（今回はこれが怪しい）
  • たとえ、効果的なインデックスを使ってクエリを実行できていたとしても、Executorによってソートの対象となるレコード数が多すぎる(390812レコード)とクエリは遅くなります。

改善案

1. 特定のインデックスの使用を強制する（非推奨）
2. 必要な情報のみSELECTする
3. テーブルを最適化する
4. シーク法を使う
   • SQLで頑張る
   • APISpecをoffsetからfrom/limit方式に変更する方法

1. MySQLのオプティマイザには頼らず、使用するインデックスを強制する

SELECT items . * FROM items USING(使いたいインデックス) WHERE items . user_id = ?  AND items . category_id = ? AND items . type_id = ? ORDER BY items . id ASC LIMIT ? OFFSET ?

期待していないインデックスが選択されることが問題かどうかを区別することができるようになります。
クエリオプティマイザーによるインデックスの選択を受け入れないことで、スロークエリが発生することもあり得るので、あまり推奨できません。

2. 必要な情報のみSELECTする

無用なメモリを使わず、I/Oも減るため、速度改善は見込めそうです。
(Netflixさん？がまとめ記事出してますよね)

3. テーブルを最適化する

レコードの追加と削除が頻繁に行われるようなテーブルではデータがフラグメンテーションを起こし、パフォーマンスに影響を与えることがあります。そのようなテーブルには OPTIMIZE TABLE table_name クエリを発行すれば最適化が行われ、実データも縮小します。

これはクエリの挙動が色々変わってしまいそうで怖いですが、やるとしたら、メンテナンスモードにしてテーブルに対するアクセスがない時間にやると良さそうですね。

4. シーク法を使う

自分が一番怪しいと思った箇所はインデックスを使って取得したレコード数自体の母数がかなりあるので、offset処理が実行される時にmysqlのexecutorの処理で遅くなっている気がしています。
なので、executorが処理するレコードの母数を減らすことができると良さそうです。

the seek method, you remember the primary/unique key value for the last row read from the previous page.
Whichever method you use, if people page back and forward in the results often for data that change regularly, customers will see unexpected results. But the seek method is generally "less wrong" and faster.

SQLで頑張る

incremental な id を offset に使います。

1. インデックスを使ってoffsetの値のレコード分までidのみ取得
2. 2回目のクエリで1で取得したid以降のレコードを指定件数まで取得する

検索条件の結果が数万件に及ぶ場合はoffsetによってexecutorにカウントさせるよりも、全件取得する方がクエリ自体は早いこともあるみたいです（環境によって要検証）
なので、1回目は2回目のため条件となるクエリを取得して
2回目のクエリでセカンダリインデックスにクラスターインデックスがマージされたインデックスを効かせることでパフォーマンスが出せます。

イメージ

-- 1
SELECT items .id FROM items WHERE items . user_id = ? AND items . category_id = ? AND items . type_id = ?  ORDER BY items . id ASC LIMIT {offsetで指定された値}

-- 2
SELECT items .* FROM items WHERE items . user_id = ? AND items . open_flag = ? AND items . transaction_status = ? AND items.id > {1で取得した最後のレコードのid} ORDER BY  items . id ASC LIMIT {limitで指定している件数}

クエリキャッシュある可能性があって断言できないですが、
offset35000＋limit 1000が約5secかかったのに対して
idのみlimit 35000が0.025secで取得完了しました。

APISpecをoffsetからfrom/limit方式に変更する

前ページの最後のidをfromの値として受け取るAPI Specに変えてしまい、クライアントからidを受け取る。

この方法なら、リクエストを受ける側としては実装が簡単なのですが、APIの破壊的な変更は要注意です。

採用したほうほう

シーク法を用いてレイテンシーを改善しました。
スロークエリになっていたパラメータで当該のエンドポイントにリクエストしたところ、速度が 100分の1に改善されました。

-- 元のクエリ
SELECT SQL_NO_CACHE items.* FROM items WHERE items . user_id = ? AND items . category_id = ? AND items . type_id = ? ORDER BY items . id ASC limit 100 OFFSET 60000

-- 改善したクエリ
SELECT SQL_NO_CACHE items.* FROM items
JOIN (
  (
    SELECT items.id FROM items where items.id > (
      SELECT MAX(id) FROM (
        SELECT items.id FROM items WHERE items . user_id = ? AND items . category_id = ? AND items . type_id = ?  ORDER BY items . id ASC limit 60000
      ) AS id
    ) AND items . user_id = ? AND items . category_id = ? AND items . type_id = ?  ORDER BY items.id ASC limit 100
  ) as result
) ON result.id = items.id ORDER BY items.id ASC

参考URL群

https://www.slideshare.net/yoku0825/mysql-57449062
https://blog.cybozu.io/entry/2018/08/08/080000
https://dev.mysql.com/doc/refman/5.6/en/optimize-table.html
https://use-the-index-luke.com/sql/partial-results/fetch-next-page