MySQL 億単位データのページネーション
会社の事業が拡大するにつれて、データ量も急激に増えていきます。MySQL はコミュニティ版が無料のオープンソースデータベースですが、数百万件のデータのページネーションを limit だけに頼るのは現実的ではありません。もちろん MySQL を貶めるつもりはありません。MySQL はプラガブルなストレージエンジンを持つオープンソースデータベースとして、大部分のアプリケーションシーンの要求をすでに満たせますし、MySQL で 100TB を管理することも問題ではありません。しかし、その使い方こそが問題なのです。
ページネーションはほぼすべての管理画面のリストページに標準装備される機能で、データ量が少ないうちはどう書いても動きます。問題が表面化するのは、たいていテーブルが数百万行に膨らんだ後です。最初の数ページはミリ秒で返ってくるのに、後ろへめくるほど遅くなり、最後の数ページではタイムアウトすることさえあります。この記事に記録するのは、私が会社の会計テーブルで遭遇した深いページネーション（deep pagination）の問題と、一歩ずつ最適化していった過程です。
limit はなぜ遅いのか
limit は 1 つまたは 2 つの数値パラメータを受け取ります。パラメータは整数の定数でなければなりません。2 つのパラメータを与えた場合、1 つ目は最初に返すレコード行のオフセットを、2 つ目は返すレコード行の最大数を指定します。
鍵はオフセットの実装方式にあります。MySQL は 10 万行目へ「ジャンプ」することはできず、前方の offset 行をすべて読み出してから捨て、最後の数件だけを返します。つまり limit 100000, 20 は実際には 100020 行のデータを読んでいるのです。クエリ対象のカラムがインデックスに含まれていなければ、各行はさらに主キーでクラスタインデックスへ戻って完全なレコードを取得（回表）する必要があり、読む行数が多いほどこのコストは増幅されます。
limit はオフセットが 10 万未満のうちは性能がなんとか許容範囲ですが、オフセットが大きくなるにつれて性能は急激に低下します。
会社の単一テーブルの会計データはすでに 230 万件に達しており、limit でページネーションして最後のページのデータを取得すると、20 秒はかからないと結果が返ってこないでしょう。もちろん具体的な時間は、インデックスの有無、カラム数、データ内容、クエリ条件によって変わります。
サブクエリでまず主キーを特定する
ページネーションの効率問題を解決するために私が採用した方式は、まずサブクエリで主キー id だけを取得し、その id で行全体のデータを取りに行くというものです。
-- サブクエリでは主キー id だけを取得し、where 条件を付ける
-- インデックスのスキャンだけで完結し、行全体を取りに戻る必要がない
select id from table limit 100000,20
（where 条件を付けてサブクエリにします）
主キー id はもともと主キーインデックスなので、limit の速度・効率は非常に高くなります。さらに条件カラムを複合インデックスに含めることで、効率は質的に向上します。このステップが速い理由は、id だけを取得する場合、クエリ全体がインデックス上で完結し、インデックスのレコード 1 件あたりのサイズが小さいため、同じ offset のスキャン量でも IO コストが行全体をスキャンするよりはるかに低いからです。
ただしソートがある場合、性能はやはり大きく低下します。目測では 30 万件のデータを id や時刻でソートすると 1〜2 秒かかります。
最良の方法は、limit のオフセットをきっぱり捨てて where id > xxx を使い、目的のデータの id 位置をより高速に特定し、その後ソートして limit 20 件を取ることです。これなら百万件レベルでも基本的に耐えられます。この書き方は一般にカーソルページネーション（あるいは keyset ページネーション）と呼ばれます。ページをめくるたびに前のページの最後の 1 件の id を持ってきて、where id > xxx でインデックス上から直接開始位置を特定するので、何ページ目までめくってもスキャンする行数は常に 20 行程度で固定されます。代償として順方向のページ送りしかできず、任意のページへのジャンプはサポートされません。フィード型の一覧やエクスポートのような場面に向いています。
id リストで行全体のデータを取得する
まず必要な id を取得し、その後条件なしの in idList クエリを実行します：
-- 第 2 ステップ：前のステップで得た id リストで全カラムを取得する
-- where 条件は付けず、ソートはそのまま残す
select 字段 from table where id in (idList)
（条件は付けません。ソートがあればソートは残しますが、データ量がすでに少ないので問題ありません。外部ソートになっても十分速いです）
リストのクエリでは where in id だけで十分です。その他の条件は select id の時点ですでに適用済みなので、リストデータの取得時に条件を付ける必要は一切ありません。ただしソートは付ける必要があります。
これで非常に高速なページネーションクエリができます。さらにリストのカラム数が少なければカバリングインデックスにでき、クエリ効率はもう一段上がります。しかし一般にリストのカラムは多く、10 数個や 20 数個は普通です。これらすべてにインデックスを張るのは得策ではありません。インデックスのサイズが大きくなりすぎ、データの追加・更新時にインデックスのメンテナンスで効率が下がり、かえってテーブルの性能を落とすことになりかねません。ですからクエリを設計するときは、カラム数、ソート規則、条件の数、インデックスの種類、どのカラムにインデックスを張るかを天秤にかける必要があります。
テーブル結合（JOIN）のような操作は、大量データのもとでは基本的に使用を考えません。冗長カラムを持たせるのが最善です。大きなテーブルでの join は、駆動テーブルの各行ごとに被駆動テーブルへの検索が発生することを意味し、データ量が増えると増幅効果が顕著になります。よく使う関連カラムをメインテーブルに冗長化して持たせ、書き込み時に一部余分に保存する代わりにクエリ時の結合を一回減らすのは、読み込みが多く書き込みが少ないリスト系の場面では通常割に合います。
explain で実行計画を検証する
最適化は勘に頼ってはいけません。SQL を変更したら実行計画を見て確認します。
クエリ SQL を explain で確認し、実行過程を見ます。インデックスを使っているか、インデックスの種類は何か、回表（テーブルへの再アクセス）が発生しているか、スキャンした行数はどれくらいかなどの重要な情報を把握してこそ、データベースの性能は質的に向上します。
-- クエリ文の前に explain を付ければ実行計画を確認できる
-- 注目すべきは type（インデックスの種類）、key（実際に使われたインデックス）、
-- rows（推定スキャン行数）、Extra（Using index でカバリングインデックスかどうか）
explain select id from table where 条件 limit 100000,20;
テストの結果、このページネーション方式なら 100 万件・1 ページ 20 件のデータで基本的に 1 秒以内にレスポンスが返り、おおよそ 600ms 程度のリクエスト時間になりました。
単一テーブルの先にある道
ページネーションの最適化が解決するのは単一テーブルのクエリ効率ですが、テーブルは今後も成長し続けるので、アーキテクチャの面でも先手を打って逃げ道を用意しておくべきです。
単一テーブルのデータ量がすでに 500 万件を超えているなら、水平分割（シャーディング）を検討してよい段階です。
ビジネスロジックの観点では、単一データベースの性能を高めるために、リード・ライト分離（マスターに書き込み、スレーブから読み込み、複数スレーブなど）を検討できます。
ビジネスに応じてデータベースを垂直分割し、ホットデータとコールドデータを分離してサーバーリソースを配分します。
ハマりどころと注意点
1）サブクエリ方式の前提は、where 条件のカラムに適切な複合インデックスがあることです。そうでなければ第 1 ステップの select id 自体がフルテーブルスキャンに退化し、最適化が無駄になります。
2）where id > xxx のカーソルページネーションは、ソートキーが単調かつ一意であることを要求します。時刻でソートしていて時刻に重複値がある場合、ページ送り時にデータの取りこぼしや重複が起こり得るため、通常は「時刻 + id」の複合ソートで保険をかける必要があります。
3）in (idList) のリストの長さは 1 ページあたりの件数と同じで、一般に 20 件なら問題ありません。ただしこの書き方を一度に数千個の id を渡すような場面に広げてはいけません。
4）explain が示す rows は推定値であり、統計情報が不正確なときはズレが生じます。判断に迷うときはスロークエリログと実際の実行時間を併せて判断してください。
本番環境でページネーション SQL を変更する前に、まずスレーブやテスト環境で実データ量を使って実行計画を検証してください。深いページネーションの問題は、小さいデータ量では再現できません。
まとめ
深いページネーションが遅い根本原因は、limit のオフセットが行を 1 件ずつスキャンして捨てなければならず、データ量が大きいほどコストが高くなることです。解決の考え方は、スキャンを最小のデータセット上で行わせること。まずインデックス内で主キーを特定してから行全体を取得し、カーソルページネーションが使えるならオフセットを捨てる。変更後は explain でインデックスが本当に効いているかを検証します。単一テーブルで支えきれなくなったら、テーブル分割、リード・ライト分離、ホット・コールド分離といったアーキテクチャの手段を検討しましょう。
COMMENTS