OFFSETページネーションをやめてp95を77ms→6msにした話（1000万行で実測）

はじめに

「1000万行のテーブルに対して、フィルタ・ソート・ページングが効くAPIを p95 < 100ms で作る」という個人課題をやってみました。

最初は何も考えず OFFSET でページングを実装したんですが、これがページを深く進むほど遅くなる。原因を EXPLAIN で追いかけて、Keyset Pagination（カーソル方式）＋複合インデックスに作り替えたら、何ページ目でも数ミリ秒で返るようになりました。

この記事は、その過程で「予測 → 実測 → なぜズレたか」を記録した学習ログの抜粋です。環境は PostgreSQL 16 / Rails 8.1、データは orders 1000万行（status分布: paid60% / shipped20% / pending13% / cancelled6% / refunded1%）です。

題材のクエリ

「paidの注文を新しい順に20件」という、よくあるページングです。

SELECT * FROM orders
WHERE status = 1
ORDER BY created_at DESC
LIMIT 20 OFFSET ?;

1. インデックス無しの地獄（ベースライン）

まずインデックスを張らずに測ります。

EXPLAIN (ANALYZE, BUFFERS)
SELECT * FROM orders WHERE status = 1 ORDER BY created_at DESC LIMIT 20 OFFSET 0;

結果（warm）:

OFFSET	実行時間	Buffers	Sort方式
0	314ms	hit=73,602	top-N heapsort 27kB（メモリ内）
100,000	583ms	hit=73,602 + temp書込	external merge Disk 88MB（ディスク退避）
1,000,000	662ms	hit=73,602 + temp書込	external merge Disk 94MB

ここで学んだこと2つ：

• Buffers: hit=73,602 が OFFSET によらず一定。つまり「20行返すために毎回テーブル全体（約574MB）を読んでいる」。
• OFFSET が増えると、ソートが work_mem（16MB）を超えてディスクに退避する断崖がある。OFFSET 0 はメモリ内（top-N heapsort）で収まるのに、深くなると external merge Disk に落ちる。

時間は環境やキャッシュで桁が動くので、ブロック数(Buffers)で考えるのが安定した指標、というのが地味に大事な気づきでした。

2. インデックスの「列順」で結果が変わる

3パターン張って比較しました。

CREATE INDEX idx_a ON orders (created_at DESC);                      -- ソート列だけ
CREATE INDEX idx_b ON orders (created_at DESC, status);              -- 列順が逆
CREATE INDEX idx_c ON orders (status, created_at DESC, id DESC);     -- 正解

paid(60%)・1ページ目だと、どれも Sort が消えて 314ms → 0.015ms。……が、これだけ見ると優劣が分かりません。楽な条件だと悪い設計が紛れ込む、という罠。

そこで少数派の refunded(1%) で測り直すと差が爆発しました。

パターン	Buffers	Rows Removed by Filter
A (created_at)	2,527	2,498 ← Filter爆発
B (created_at, status)	32	0（Index Cond）
C (status, created_at, id)	24	0（Index Cond）

A は created_at 順にしか並んでいないので、refunded を探すのに「新しい順にたどっては status 違いを捨てる」を繰り返す（2,498行の空振り）。一方 C は status が先頭なので「refunded の棚」に直行でき、その中はもう created_at 順。

結論：等値条件 → ソート/範囲条件 → 一意列 の順

• status（等値）を先頭 → B-tree内でその範囲が連続し、中が created_at 順に並ぶ → Sort が消える
• created_at（ソート/範囲）を次に
• id（一意）を末尾に → 後述のカーソルのタイブレーク用

おまけ：DESC指定は必須じゃない

(status, created_at, id) を全部ASCで作っても、ORDER BY created_at DESC, id DESC は Index Scan Backward（逆読み）で Sort 無しで使えます。DESC明示が要るのは created_at DESC, id ASC のように方向が混在するときだけ（このとき Incremental Sort が出ます）。

3. 本題：Keyset Pagination

OFFSET をやめ、「前ページの最後の値より続きをN件」という取り方にします。

SELECT * FROM orders
WHERE status = 1
  AND (created_at, id) < ('2026-08-10 04:48:35.679074', 8172635)  -- カーソル
ORDER BY created_at DESC, id DESC
LIMIT 20;

行値比較 (a, b) < (?, ?) が決定的

ポイントは (created_at, id) < (?, ?) という行値比較で書くこと。これが Index Cond に落ちます。

Index Cond: ((status = 1) AND (ROW(created_at, id) < ROW('2026-08-10 ...', 8172635)))
Buffers: shared hit=27

一方、論理的に等価なOR手書きだと Filter になってしまい、カーソルより新しい10万件を全部読んで捨てます。

-- NG: Index Cond に落ちず Filter になる
WHERE created_at < ? OR (created_at = ? AND id < ?)

書き方	Buffers	実行時間
行値比較 (a,b)<(?,?)	27	0.2ms
OR手書き	100,518	4,637ms

同じ意味なのに約3,700倍。これが今回いちばん実用的な知識でした。

そして Keyset の本質は、カーソルが何ページ目でも Buffers が一定なこと（浅い27 ↔ 深い24）。OFFSET のように「先頭から数えて捨てる」をしないからです。

カーソルの時刻精度は iso8601(6) が生命線

カーソルをBase64で包んで返すんですが、時刻を to_s（秒精度）に丸めると、同一秒に複数行があるページ境界で取りこぼし・重複が起きます。マイクロ秒まで保持する iso8601(6) が必須。

実際、テストで iso8601(6) → to_s に変えたら、200件のはずが1000件取れて（同じ行を無限に再読込）落ちました。データが少ないと再現しない、本番でだけ出るバグの典型です。

4. COUNTの壁

クエリ本体を 0.02ms にしても、画面に「全600万件」を出す COUNT(*) が warm でも約200ms かかって台無しになります（選択率60%だと index より Seq Scan が選ばれる）。

回避策は3つ試しました：

1. 総件数を出さない（LIMIT 21 して21件目の有無で「次あり」判定）。無限スクロールならこれで十分
2. 近似値（EXPLAIN の Plan Rows を使う。0.27ms・誤差0.01%）
3. カウンタテーブル（正確だが更新の整合性コストを払う）

一番の学びは「正確な総件数が本当に要るのか、を要件側と相談するのが実は一番効く」こと。技術で殴らない解法もある。

5. p95で判断する

OFFSET版とKeyset版で、散らばった位置を200回叩いて分布を取りました。

方式	p50	p95	p99	max
OFFSET	~40ms	~77ms	~100ms	単発で6,527ms
Keyset	1-5ms	1.5-6.3ms	7-10ms	~16ms

平均やp50だけ見ると差は9倍くらいですが、遅い側の5%（p95）を見ると桁が違う。ユーザー体験を壊すのはこの裾なので、p95で判断する意味があります。

「裾は最初の1回だけでは？」への回答

max 6527ms は単発の外れ値（コールド等）で、ここは「最初だけ」が正しい。だからmaxは指標に使わない。

でも p95≈77ms は毎回起きます。深いOFFSETをクエリキャッシュOFF（uncached）で5回測ると、全部74-79ms。EXPLAINを見ると Buffers が全部hit（キャッシュ済）なのに77ms＝I/OじゃなくCPUで20万件を舐めている。だからキャッシュが温まっても消えない。「深いページは構造的に毎回遅い」わけです。

おまけ：DB内が速くてもアプリ層が残る

StackProfで見ると、Keysetの数msのうち SQL実行(PG::Connection#exec)は約10%だけで、残りはRuby側（ActiveRecordのオブジェクト生成・GC）でした。「遅い＝SQLが悪い」とは限らない。

余談：行値比較はDB・バージョンで挙動が違うらしい

今回PostgreSQLで「行値比較＝Index Cond / OR手書き＝Filter」を確認しましたが、調べるとMySQLでは逆の歴史があるようです（※ここは手元未検証の伝聞）。

• MySQL 5.7 あたり: 行値比較は range 最適化されず、OR手書きの方がインデックス(range)を使えた
• MySQL 8.0 の途中（8.0.14頃）: 行値比較も range 最適化が入り、両方使えるように

MySQLのEXPLAINに Index Cond という表記は無く、type: range で見ます。用語はDBごとに違うので注意。

「論理的に等価＝性能も同じ」とは限らないし、DBやバージョンにも依存する。結局 EXPLAINで実際にどう実行されるか見るしかない、というのが締めの学びでした。

まとめ

• OFFSETは深いページで毎回遅い（先頭から数えて捨てるから）。Keysetは何ページ目でも一定
• インデックスは 等値→ソート→一意 の列順。Sort が消えるかが命
• カーソルは 行値比較 (a,b)<(?,?) で書く（OR手書きはFilter落ちで激遅）
• 時刻カーソルは マイクロ秒精度 を保つ
• 性能は 平均でなくp95 で判断する
• そして全部、EXPLAINで測ってから直す

ここまで読んでいただきありがとうございました。