実運用環境のアプリケーションにおいて、ページネーション機能の実装不備は、ユーザー体験を損なうだけでなく、データの整合性に対する不信感を招く原因となります。特に、「2ページ目に遷移したのに、1ページ目のデータが再度表示される」あるいは「特定のデータが表示されずにスキップされる」という現象は、単純なバグではなく、リレーショナルデータベース（RDBMS）のソート順序の決定論的性質（Determinism）に対する理解不足から生じます。本稿では、OFFSET方式が抱える構造的な欠陥と、それを解決するための決定論的なソート戦略、そして大規模データセットに対応するためのKeyset Pagination（シーク法）への移行戦略について、アーキテクチャの観点から解説します。
1. 非決定的なソートとデータ重複のメカニズム
多くのWebフレームワークやORMがデフォルトで提供するページネーションは、SQLのLIMIT句とOFFSET句を使用します。しかし、ソートキー（ORDER BYで指定したカラム）の値が一意でない場合、RDBMSは同一キーを持つレコード間の順序を保証しません。これを「非決定的なソート（Non-deterministic Sort）」と呼びます。
例えば、以下のarticlesテーブルにおいて、created_atが同一のレコードが存在すると仮定します。
| id (PK) | title | created_at |
|---|---|---|
| 101 | Article A | 2024-01-01 12:00:00 |
| 102 | Article B | 2024-01-01 12:00:00 |
ここで、以下のクエリを実行してページングを行います。
-- 1ページ目 (LIMIT 1)
SELECT * FROM articles ORDER BY created_at DESC LIMIT 1 OFFSET 0;
-- 2ページ目 (LIMIT 1)
SELECT * FROM articles ORDER BY created_at DESC LIMIT 1 OFFSET 1;
データベースのオプティマイザや並列処理の状況、あるいは物理的な格納位置の変更（VACUUMや更新処理後）により、同一のcreated_atを持つID 101と102の返却順序は実行ごとに変わる可能性があります。
- 1ページ目実行時: [101, 102] の順と判断され、101が返却される。
- 2ページ目実行時: [102, 101] の順と判断され、オフセット1（先頭スキップ）により101が返却される。
結果として、ユーザーは1ページ目でも2ページ目でも「ID 101」を目にすることになり、ID 102は永遠に表示されません。
2. 決定論的なソートによる解決
この問題の解決策は、ソート順序を「決定的」にすることです。すなわち、いつ、何度クエリを実行しても、レコードの並び順が完全に固定されるように保証する必要があります。
最も確実な方法は、ORDER BY句の末尾に「タイブレーカー（Tie-breaker）」として一意なカラム（通常はプライマリキー）を追加することです。
-- Best Practice: PKを第2ソートキーとして指定
SELECT * FROM articles
ORDER BY created_at DESC, id DESC
LIMIT 10 OFFSET 10;
これにより、created_atが同じであっても、必ずidの順序で評価されるため、レコードの並び順は数学的に一意となります。これは追加コストがほぼゼロで即時適用可能な修正であり、全てのORDER BY句における必須の習慣とすべきです。
3. OFFSET方式のパフォーマンス限界
ソート順序を固定しても、OFFSET方式にはアーキテクチャ上の重大な欠陥が残ります。それは、ページ数が深くなるにつれてクエリのコストが線形に増加する（$O(N)$）という問題です。
LIMIT 10 OFFSET 100000というクエリを処理する際、データベースエンジンは以下の動作を行います。
つまり、深いページを表示するためには、大量の無駄なI/OとCPUサイクルを消費することになります。これが、数百万行を超えるテーブルで「後ろのページに行くと極端に重くなる」原因です。
4. Keyset Pagination (Cursor-based)
大規模データセットにおける標準的な解決策は、Keyset Pagination（別名：Seek Method, Cursor-based Pagination）です。これは「何件読み飛ばすか（OFFSET）」ではなく、「どのレコードの次から取得するか（WHERE）」を指定する方式です。
前述のORDER BY created_at DESC, id DESCというソート条件において、直前のページで取得した最後のレコードが (created_at='2024-01-01', id=50) だった場合、次のページの取得クエリは以下のようになります。
-- タプル比較を用いたシーク法の実装
SELECT * FROM articles
WHERE (created_at, id) < ('2024-01-01', 50)
ORDER BY created_at DESC, id DESC
LIMIT 10;
(col1, col2) < (val1, val2) という行値式（Row Value Constructors）の比較をサポートしており、これを効率的にインデックススキャンに変換できます。
このクエリは、直前の位置（カーソル）を起点としてインデックスをスキャンするため、何ページ目であっても計算量は$O(1)$（または取得件数に依存）となり、常に一定のパフォーマンスを維持できます。
インデックス設計の最適化
Keyset Paginationの効果を最大化するためには、ORDER BYおよびWHERE句で使用するカラムに対して、適切な複合インデックス（Composite Index）を作成する必要があります。
-- カバリングインデックスを意識した設計
CREATE INDEX idx_articles_pagination ON articles (created_at DESC, id DESC);
このインデックスが存在すれば、データベースはテーブルデータ本体にアクセスすることなく、インデックスツリーのトラバースだけで対象レコードを特定できます（Covering Index Scan）。
トレードオフと実装の選択
Keyset Paginationはパフォーマンスと整合性の面で優れていますが、銀の弾丸ではありません。以下のトレードオフを考慮して採用を決定してください。
| 比較項目 | OFFSET方式 | Keyset方式 |
|---|---|---|
| ランダムアクセス | 可能（50ページ目へジャンプ等） | 不可能（前後の移動のみ） |
| パフォーマンス | ページ深度に応じて劣化 | 常に高速・一定 |
| 実装難易度 | 低（フレームワーク標準） | 中（カーソル管理が必要） |
| データ挿入時の挙動 | ページズレが発生しやすい | 堅牢（カーソル位置は不変） |
エンジニアリング・サマリー
データ重複を防ぐための第一歩は、全てのソートクエリにユニークキーを含めることです。これは、OFFSET方式を使用し続ける場合でも必須の要件です。その上で、レコード数が数万件を超える可能性がある、あるいは無限スクロールのようなUIを提供する場合は、Keyset Paginationへの移行を設計段階から組み込むことを強く推奨します。パフォーマンス問題はデータが増えてから顕在化するため、事前のアーキテクチャ選定がシステムの寿命を左右します。
Post a Comment