minne MySQL パフォーマンスチューニング Rails

ORDER BY id DESC が招くインデックス誤選択 — 直近のレコードを N 件取り出すクエリを実測 約 658 倍に高速化

minne MySQL パフォーマンスチューニング Rails

はじめに

「ある所有者の直近のレコード（注文・投稿・取引など）から、最新の N 件を取りたい」というユースケースは、Web アプリケーションを書いていれば頻出するパターンです。Rails 風に書けば次のような形になります。

current_user.orders
  .where.not(id: @order.id)    # 自分自身は除外する
  .order(id: :desc)            # 「直近」を id 降順で表現
  .limit(n)

このパターンが、minne では特定のユーザーで安定的に MySQL のクエリタイムアウトを起こしていました。

Mysql2::Error: Query execution was interrupted, maximum statement execution time exceeded

調査の結果、原因は ORDER BY id DESC + LIMIT N の組み合わせによる MySQL optimizer のインデックス誤選択 で、worst case で 2,300 万行をスキャン して max_statement_time を踏み抜いていることが判明しました。ORDER BY のカラムを既存インデックスに合わせて変えるだけで、

  • スキャン推定行数: 23,297,383 行 → 65,024 行（約 358 倍削減）
  • 実測実行時間: 56.6ms → 0.086ms（約 658 倍高速化）

まで縮みました。本記事では、その原因分析と修正アプローチを EXPLAIN ANALYZE とあわせて紹介します。「直近のレコードを N 件取り出す」クエリを書くすべての人に還元できる知見となることを願っています。

  1. はじめに
  2. 何が起きていたか
  3. 原因 — ORDER BY id DESC + LIMIT N で optimizer が PRIMARY を選ぶ
    1. 「LIMIT を外せば直る」のではない
  4. 修正 — ORDER BY を既存インデックスのソート順に揃える
    1. 補足: id DESC と ordered_at DESC の意味的な差
  5. 比較サマリ
  6. 学び
  7. 参考

何が起きていたか

問題のあったコードは、ある作家の 直近の注文を N 件取り出す ためのクエリでした。本筋に関係しない部分を削ぎ落とすと、概形は次のようになります。

current_user.orders
  .where.not(id: @order.id)    # 自分自身は除外する
  .order(id: :desc)            # 「直近」を id 降順で表現
  .limit(n)

current_user（作家）の注文のうち、現在のレコード自身を除いて id 降順に N 件取るだけ。発行される SQL もざっくり次のような形です。

SELECT sales.* FROM sales
WHERE sales.creator_id = ? AND sales.id != ?
ORDER BY sales.id DESC
LIMIT N;

一見、creator_id で絞って id 降順に N 件取るだけのシンプルなクエリです。注文数が少ない作家では即座に返ります。 ところが累計数万件規模の注文を持つような作家では、このクエリが安定してタイムアウトしていました。

原因 — ORDER BY id DESC + LIMIT N で optimizer が PRIMARY を選ぶ

sales テーブルには (creator_id, ordered_at) の複合インデックス index_sales_on_creator_id_ordered_at が張ってあります。(creator_id, id) のインデックスはありません。

実際の作家（sale 約 6.5 万件保有）で EXPLAIN ANALYZE を取った結果が次のとおりです。なお EXPLAIN ANALYZE は通常の EXPLAIN と違って クエリを実際に実行した上で 実測値を返すため、本番 DB に対して使う場合は負荷影響が伴います。本記事の計測も、実行タイミングや対象クエリを選ぶなど 影響範囲が最小となるよう注意した上で 取得しています。

EXPLAIN ANALYZE SELECT sales.* FROM sales
WHERE sales.creator_id = xxxxx AND sales.id != yyyyy
ORDER BY sales.id DESC
LIMIT 10;

-> Limit: 10 row(s)  (cost=66636 rows=10) (actual time=6.26..56.6 rows=10 loops=1)
   -> Filter: ((sales.creator_id = xxxxx) and (sales.id <> yyyyy))  (cost=66636 rows=34158) (actual time=6.26..56.6 rows=10 loops=1)
       -> Index range scan on sales using PRIMARY over (id < yyyyy) OR (yyyyy < id) (reverse)
          (cost=66636 rows=23.3e+6) (actual time=0.0213..54.1 rows=27907 loops=1)

possible_keys には PRIMARY と index_sales_on_creator_id_ordered_at の両方が挙がっていましたが、optimizer は PRIMARY 逆順スキャン を選択しました。ORDER BY id DESC LIMIT 10 を満たすのに「PRIMARY を逆順に舐めて、creator_id にヒットした行が 10 件揃ったところで打ち切る」プランを最も低コストと見積もったわけです。

これは MySQL が ORDER BY ... LIMIT の組み合わせに対して行う最適化（書籍『MySQL運用・管理［実践］入門』では ORDER BY LIMIT 最適化 と呼ばれています）が裏目に出たケースです。同書第 4 章「ロックとクエリ実行計画」では、ORDER BY Population DESC LIMIT 10 のような単純なケースについてこう説明されています。

idx_population によって Population はすでに昇順（暗黙のソート順は ASC）にソートされており、B+Tree 形式をしているためこのインデックスを昇順にたどるのと逆順にたどるのはほぼ等価に可能です（よってインデックスを使って逆順に処理したことを示す Extra: Backward index scan が追加されています）。

——『MySQL運用・管理［実践］入門』p.93

MySQL 8.0 で導入された Backward index scan によって、ORDER BY id DESC は PRIMARY を逆順に辿ればファイルソート無しに満たせます。さらに LIMIT N が付くと「途中で N 件揃った時点で打ち切れる」という早期終了が見込めるため、optimizer の目には PRIMARY 逆順スキャンが極めて魅力的なプランに映る、というわけです。

なぜこれが罠になるかは、sales の PRIMARY が 全作家の注文が時系列にミックスされた 1 本の列 だと考えると見えてきます。「PRIMARY を逆順に少し舐めれば N 件揃う」という見立ては、暗黙のうちに 対象作家の注文行が PRIMARY の最新側に十分密集している ことを前提にしています。

  • 直近で注文を捌いている作家: 最新側の id 帯に自分の注文行が頻繁に現れる → 数千行のスキャンで N 件揃う
  • 直近で注文を出していない作家: 最新側にはほぼ存在せず、自分の注文行が出てくる id 帯まで遡る必要がある → スキャン量が膨大に

これは『MySQL運用・管理［実践］入門』が示す ORDER BY LIMIT 最適化の 最悪ケース に相当します。

最悪ケースは Continent=’Asia’ を満たす行が確定する前にインデックスフルスキャンが終わるケース（すべて Continent にヒットしない）。

——『MySQL運用・管理［実践］入門』p.94

書籍は Continent='Asia' でフィルタにヒットせずインデックスを最後まで舐めきるケースを挙げていますが、本記事の事例は creator_id = xxxxx でヒットする行が PRIMARY 末尾に十分量現れない、という述語の差があるだけで構造は同じです。WHERE 列と ORDER BY 列のインデックスが分離している限り、optimizer は filtered の見積もりに基づいて「フィルタは早期に効くだろう」と楽観視し、それが外れた瞬間にスキャン量がテーブル全体まで線形に伸びていきます。

23.3M はあくまで rows 推定の上限値で、上のテスト作家では actual 27,907 行で済んでいます。一方で本番では、最新側に行が少ない作家のケースで max_statement_time を実際に踏み抜いていました。テーブルが伸びるほど worst case のスキャン量も線形に増えていく、という構造になっていたわけです。

「LIMIT を外せば直る」のではない

ここで自然な疑問は「じゃあ LIMIT を外せば PRIMARY 誘導は回避できるのでは？」というものです。実際 LIMIT を外すと optimizer の選択は変わります。

EXPLAIN ANALYZE SELECT sales.* FROM sales
WHERE sales.creator_id = xxxxx AND sales.id != yyyyy
ORDER BY sales.id DESC;

-> Sort: sales.id DESC  (cost=63195 rows=65024) (actual time=257..270 rows=35353 loops=1)
   -> Index lookup on sales using index_sales_on_creator_id_ordered_at (creator_id=xxxxx),
      with index condition: (sales.id <> yyyyy)  (cost=63195 rows=65024) (actual time=0.0305..209 rows=35353 loops=1)

(creator_id, ordered_at) インデックスが採用されて creator スコープに閉じる代わりに、id DESC で並べ直すための filesort（Sort ノード）が必要になります。実測 270ms。LIMIT 有りでの 56.6ms より遅く、テーブルが伸びれば線形に悪化します。

つまり罠の核心は LIMIT ではなく、WHERE 列と ORDER BY 列が別インデックスにまたがるクエリの組み立て方 そのものです。LIMIT の有無で optimizer は別の悪い選択肢に逃げるだけです。

  • LIMIT N + id DESC: PRIMARY 逆順スキャン誘導 → テーブル全体に対する worst case
  • LIMIT 無し + id DESC: (creator_id, ordered_at) + filesort → creator の sale 件数に対する線形コスト

『MySQL運用・管理［実践］入門』は次のように結論しています。

なお、WHERE と ORDER BY LIMIT 最適化を同時に満たすインデックスは、INDEX(Continent, Population) でこれが最速になります。

——『MySQL運用・管理［実践］入門』p.95

本件に当てはめれば (creator_id, id) の複合インデックスを足すのが理論的な最速解で、両方の問題を一気に解消できます。ただし数千万行規模の sales テーブルへの index 追加は運用コストが大きく、なるべく避けたいところです。本記事の修正は 既存の (creator_id, ordered_at) を活かす形にアプリ側のクエリを寄せる というアプローチを取りました。

修正 — ORDER BY を既存インデックスのソート順に揃える

修正の本丸は ORDER BY id DESC を ORDER BY ordered_at DESC に切り替えることです。これだけで (creator_id, ordered_at) インデックスが WHERE と ORDER BY の両方 で使えるようになり、optimizer の選択が劇的に変わります。

SELECT sales.* FROM sales
WHERE sales.creator_id = ? AND sales.id != ?
ORDER BY sales.ordered_at DESC
LIMIT N;

同じ作家で EXPLAIN ANALYZE を取り直したのが次の結果です。

EXPLAIN ANALYZE SELECT sales.* FROM sales
WHERE sales.creator_id = xxxxx AND sales.id != yyyyy
ORDER BY sales.ordered_at DESC
LIMIT 10;

-> Limit: 10 row(s)  (cost=63494 rows=10) (actual time=0.0296..0.0863 rows=10 loops=1)
   -> Filter: (sales.id <> yyyyy)  (cost=63494 rows=32512) (actual time=0.0288..0.0848 rows=10 loops=1)
       -> Index lookup on sales using index_sales_on_creator_id_ordered_at (creator_id=xxxxx) (reverse)
          (cost=63494 rows=65024) (actual time=0.0277..0.0827 rows=10 loops=1)

(creator_id, ordered_at) を逆順に index lookup し、LIMIT 10 で 本当に 10 行だけ読む 計画になりました。filesort も無く、actual rows が 10。実測 0.086ms です。

参考までに、LIMIT を外した場合の EXPLAIN ANALYZE も載せておきます。

EXPLAIN ANALYZE SELECT sales.* FROM sales
WHERE sales.creator_id = xxxxx AND sales.id != yyyyy
ORDER BY sales.ordered_at DESC;

-> Filter: (sales.id <> yyyyy)  (cost=60713 rows=32512) (actual time=0.0286..213 rows=35353 loops=1)
   -> Index lookup on sales using index_sales_on_creator_id_ordered_at (creator_id=xxxxx) (reverse)
      (cost=60713 rows=65024) (actual time=0.0273..209 rows=35353 loops=1)

LIMIT を外しても Sort ノードは現れず、(creator_id, ordered_at) を順に舐めるだけのプランです。actual rows は creator スコープの 35,353 行で、実測 213ms。これは「対象 creator の sale を一通り読む」コストそのものであり、旧クエリのようにテーブル全体の 23M 行を舐めにいくのとは性質がまったく違います。

修正前後の違いを 4 通りの実験で見える化すると次のようになります（同じ作家・同じ条件で測定）。

Query 採用 key filesort actual rows actual time
id DESC + LIMIT 10 PRIMARY no 27,907 56.6 ms
id DESC（LIMIT なし） ..._ordered_at YES 35,353 270 ms
ordered_at DESC + LIMIT 10 ..._ordered_at no 10 0.086 ms
ordered_at DESC（LIMIT なし） ..._ordered_at no 35,353 213 ms

ordered_at DESC 系は LIMIT 有無に関わらず filesort 無しで (creator_id, ordered_at) 一本で完結しています。LIMIT 有りの場合は早期打ち切りも効いて actual rows = 10、文字どおり「N 件だけ読む」状態になっています。

補足: id DESC と ordered_at DESC の意味的な差

旧実装は id 降順、新実装は ordered_at 降順なので、厳密には「並び順」の意味が変わります。sales.ordered_at が NULL なレコードや、バックフィルなどで ordered_at と id が逆転するレコードでは、選ばれる注文が変わる可能性があります。

今回のユースケースでは「直近の傾向に近いものが取れていれば十分」だったため許容しましたが、厳密に id の最大を取りたい場合は単純な置き換えはできない 点には注意が必要です。(creator_id, id) のインデックスを足すか、(creator_id, ordered_at) の上で取った後に再度 id で並べ替える、といった選択肢があります。

比較サマリ

項目 旧 (ORDER BY id DESC + LIMIT 10) 新 (ORDER BY ordered_at DESC + LIMIT 10)
採用 index PRIMARY index_sales_on_creator_id_ordered_at
スキャン推定行数 23,297,383 65,024（約 358 倍削減）
実 scan 行数 27,907 10
filesort 無し（PRIMARY backward） 無し（index backward）
実測実行時間 56.6 ms 0.086 ms（約 658 倍高速化）
追加 index – –

既存 index の活用に閉じているため、sales テーブルに追加負担は発生せず、巨大テーブルへの DDL を一切避けられました。

学び

今回の改善から得た学びを 3 つに整理します。

  • 罠は LIMIT 単独でも id DESC 単独でもなく、WHERE 列 と ORDER BY 列 が別インデックスにまたがるクエリの組み立て方: LIMIT 有り → 別インデックス（PRIMARY）誘導、LIMIT 無し → filesort、どちらにしても遅くなる。fix は ORDER BY を WHERE 列と組になっている既存インデックスのソート順に揃える こと
  • EXPLAIN を取るまで「速いはず」は信用しない: creator_id で絞っているから速いだろう、ではなく、possible_keys と key を見て optimizer の実際の選択を確認する。本件も possible_keys には正解の index が出ていたが、key は PRIMARY だった。EXPLAIN ANALYZE まで取ると actual rows / actual time も見えて、見積もりとの乖離も追える（ただし EXPLAIN ANALYZE はクエリを実際に走らせるため、本番で取るなら影響範囲が最小となるよう注意するのが基本）
  • 巨大テーブルへの index 追加に頼らず、まずクエリ形を既存インデックスに寄せる: 数千万行規模のテーブルへの index 追加は運用コストが大きい。(creator_id, ordered_at) のような既存複合インデックスを活かす形にアプリ側のクエリを寄せるだけで、追加コストゼロで大幅改善が得られるケースは意外と多い

これらの観点は、minne のように長く運用されるサービスで巨大テーブルと付き合う上で、繰り返し効いてくる考え方だと感じています。同じような「特定ユーザーで突然タイムアウトする」現象に出会った方の参考になれば幸いです。

参考

関連記事

書いた人