Posted inMySQL

MySQLで数百万件のページネーションを最適化：OFFSETをSeek Methodで置き換える

MySQL tutorial - IT technology blog
MySQL tutorial - IT technology blog

usersテーブルをproductionにデプロイした当初は、すべてが快調でした。しかしテーブルが1000万行を超えたころ、スロークエリログにSELECT文の実行時間が3〜5秒に達するエントリが現れ始めました。しかもそのほとんどが、LIMIT x OFFSET y形式のページネーションクエリでした。そこで初めて、この問題を真剣に調査する必要性を痛感しました。

実際の問題：OFFSETが大きいほどクエリが遅くなる

誰もが一度は書いたことのあるクエリです：

-- 1ページ目
SELECT id, username, email, created_at
FROM users
ORDER BY created_at DESC
LIMIT 20 OFFSET 0;

-- 500ページ目
SELECT id, username, email, created_at
FROM users
ORDER BY created_at DESC
LIMIT 20 OFFSET 9980;

1ページ目は10ms未満で返ります。500ページ目は2〜3秒かかります。1000ページ目は5〜6秒。そしてこれは終わりではありません。

以下は、created_atにインデックスを張った1000万行のテーブルで実際に計測したベンチマークです：

OFFSET 0         →   8ms
OFFSET 100,000   →  420ms
OFFSET 500,000   →  2.1s
OFFSET 1,000,000 →  4.3s

原因分析：MySQLは内部で何をしているのか？

OFFSETが大きいクエリにEXPLAINを実行して、実際に何が起きているか確認してみましょう：

EXPLAIN SELECT id, username, email, created_at
FROM users
ORDER BY created_at DESC
LIMIT 20 OFFSET 500000;

MySQLは500,000行目に直接ジャンプするわけではありません。代わりに、以下の処理を順番に行います：

  1. 先頭からcreated_atインデックスをスキャンする
  2. ディスクまたはバッファプールから500,020行を読み込む
  3. 最初の500,000行を破棄する
  4. 残りの20行を返す

OFFSET 500,000の場合、たった20行を取得するためにMySQLが50万行を処理しなければなりません。ショートカットは存在しません — これはMySQLのバグではなく、標準SQLの設計上の特性です。

さらに別の問題もあります。テーブルがidのクラスタードインデックスを持ちながらcreated_atでソートする場合、MySQLはダブルルックアップを行います：セカンダリインデックスを読み込む → 主キーを取得する → クラスタードインデックスから行を再取得する。このI/Oを50万回繰り返すとなれば、なぜクエリがこれほど遅いのかは自明です。

解決策

方法1：Late Row Lookup — 素早い最適化でAPIを変更不要

アイデアはシンプルです：クエリを2段階に分けます。まずサブクエリでidだけを取得し（インデックスのスキャンのみなので非常に軽い）、その後JOINで必要なカラムをすべて取得します：

SELECT u.id, u.username, u.email, u.created_at
FROM users u
INNER JOIN (
    SELECT id FROM users
    ORDER BY created_at DESC
    LIMIT 20 OFFSET 500000
) AS tmp ON u.id = tmp.id;

500,020行分のフルデータ（username、emailなど）を読み込む代わりに、MySQLはインデックスをスキャンしてコンパクトなid値500,020件を取得するだけで、実際のデータはJOINで取得します。I/Oが大幅に削減されます。

実測結果：このクエリは約2.1秒から約600msに短縮されました。クライアント側のロジックを変更せずに改善できます — 引き続き通常のページ番号をそのまま使えます。

方法2：Seek Method（Keyset Pagination）— 根本的な解決策

Seek Methodは特定の位置に「ジャンプ」しません。前ページの最後の行の値をカーソルとして使い、そこから続けてクエリします。ロジックは根本的に変わります：

-- 最初のページ（カーソル不要）
SELECT id, username, email, created_at
FROM users
ORDER BY created_at DESC, id DESC
LIMIT 20;

-- 次のページ：前ページ最後の行のcreated_atとidを渡す
-- 最後の行：created_at = '2024-03-15 10:30:00', id = 9876543 とする
SELECT id, username, email, created_at
FROM users
WHERE (created_at < '2024-03-15 10:30:00')
   OR (created_at = '2024-03-15 10:30:00' AND id < 9876543)
ORDER BY created_at DESC, id DESC
LIMIT 20;

MySQLが効率的にレンジスキャンできるよう、複合インデックスを作成します：

CREATE INDEX idx_users_created_id ON users (created_at DESC, id DESC);

同じ1000万行のテーブルでのベンチマーク比較：

-- 変更前（OFFSET）
OFFSET 0         →  8ms
OFFSET 500,000   →  2.1s

-- 変更後（Seek Method）
最初のページ      →  8ms
25,000ページ目   →  9ms  ← ページ数に関係なく！

効果的な理由：先頭からスキャンして行を破棄する代わりに、MySQLはWHERE条件を使ってインデックスレンジスキャンを行い、必要な20行だけを読み込みます。クエリ時間はほぼ一定で、ページの深さに依存しません。

Pythonでの実装

def get_users_page(db, cursor_created_at=None, cursor_id=None, limit=20):
    """
    cursor_created_at: 前ページの最後の行のdatetime文字列
    cursor_id: 前ページの最後の行のid
    戻り値: {"data": [...], "next_cursor": {...} またはNone}
    """
    if cursor_created_at is None:
        # 最初のページ
        query = """
            SELECT id, username, email, created_at
            FROM users
            ORDER BY created_at DESC, id DESC
            LIMIT %s
        """
        params = (limit,)
    else:
        query = """
            SELECT id, username, email, created_at
            FROM users
            WHERE (created_at < %s)
               OR (created_at = %s AND id < %s)
            ORDER BY created_at DESC, id DESC
            LIMIT %s
        """
        params = (cursor_created_at, cursor_created_at, cursor_id, limit)

    rows = db.execute(query, params)

    # 最後の行のカーソル — クライアントが次ページ取得に使用
    next_cursor = None
    if rows:
        last = rows[-1]
        next_cursor = {"created_at": str(last["created_at"]), "id": last["id"]}

    return {"data": rows, "next_cursor": next_cursor}

使い分けの指針

本番環境でページネーションを少なくとも3回マイグレーションしてきました。そこから得た知見を共有します：

  • 通常のOFFSET：10万行未満のテーブル — 最適化不要、過剰設計は禁物。
  • Late Row Lookup：ページ番号による表示を維持したい、APIの契約を変えたくない、今すぐ改善したいケース。
  • Seek Method：無限スクロール、「もっと見る」ボタン、またはカーソルベースのREST APIを構築する場合。長期的なパフォーマンス最優先の選択肢。

Seek Method実装でよくある落とし穴

  • 任意のページにジャンプできない：ページ1→2→3と順番に辿る必要があり、ページ1から50へ直接ジャンプはできません。無限スクロールには向いていますが、「1 2 3 … 50」式の番号付きページネーションには不向きです。
  • カーソルはユニークでなければならない：重複値のカラムでソートする場合、複合カーソルに必ずidを追加してください。そうしないと行が欠落します。
  • INSERT/DELETE時にOFFSETより堅牢：2回のリクエスト間に新しい行が追加されるとOFFSETは「ずれ」ます。Seek Methodはこの問題が起きません — リアルタイムデータには大きなメリットです。
  • COUNT(*)はキャッシュが必要：大きなInnoDBテーブルでは、SELECT COUNT(*)はフルスキャンが必要です（MyISAMとは異なります）。リクエストのたびに実行せず、TTL 5〜10分でキャッシュしてください。
-- この結果をキャッシュする（TTL 5〜10分）、リクエストのたびに実行しない
SELECT COUNT(*) FROM users WHERE status = 'active';

まとめ

LIMIT x OFFSET yはコーディング初期には便利ですが、データ量が増えると本物のパフォーマンスの落とし穴になります。真夜中にユーザーから「一覧ページがいつまでもロードされない」と報告を受けてから、これを痛い経験で学びました。

新しい機能を設計中ですか？最初からSeek Methodを採用して、技術的負債を作らないようにしましょう。すでにOFFSETベースのページネーションがありますか？まずLate Row Lookupに移行してください — breaking changeが最も少なく、改善はほぼ即座です — 条件が整ったら徐々にカーソルベースへ移行しましょう。

Share:
Tags: