Tuesday, July 4, 2023

データベースページネーションにおけるデータ重複の謎と解決策
  /   No comments   

Webアプリケーションやモバイルアプリケーションを開発する上で、リスト形式で大量のデータを表示する機能は不可欠です。ブログの投稿一覧、SNSのタイムライン、ECサイトの商品リストなど、その実装は多岐にわたります。これらの機能で共通して用いられるのが「ページネーション」という技術です。しかし、このページネーションを単純な方法で実装すると、時として「次のページを開いたら、前のページで見たはずのデータがまた表示されている」という奇妙な現象に遭遇することがあります。これはユーザー体験を著しく損なうだけでなく、データの整合性に対する信頼を揺るがす深刻な問題です。本稿では、このデータ重複問題がなぜ発生するのか、その根本原因をデータベースの動作レベルで深く掘り下げ、即時可能な解決策から、より高度でパフォーマンスに優れた実装方法までを包括的に解説します。

問題の再現：OFFSETを用いたページネーションの罠

まず、問題がどのようにして発生するのかを具体的に見ていきましょう。多くの開発者が最初に学ぶページネーションの実装方法は、SQLのLIMIT句とOFFSET句を組み合わせるものです。例えば、ARTICLEというテーブルから最新の投稿を1ページあたり10件ずつ取得する場合、以下のようなクエリが考えられます。

1ページ目のクエリ：


SELECT * FROM ARTICLE
ORDER BY posted DESC
LIMIT 10 OFFSET 0; -- 最初の10件を取得

2ページ目のクエリ：


SELECT * FROM ARTICLE
ORDER BY posted DESC
LIMIT 10 OFFSET 10; -- 次の10件を取得 (10件スキップして10件取得)

※ LIMIT 10, 10 (MySQL) と LIMIT 10 OFFSET 10 (PostgreSQL, SQLite) は同義です。

この方法は直感的で理解しやすく、一見すると何の問題もないように思えます。しかし、このクエリには重大な欠陥が潜んでいます。その欠陥はORDER BY句の対象となるposted（投稿日時）カラムの値が一意でない場合に顕在化します。

根本原因：非決定的なソート順序

データベースシステムは、ORDER BY句で指定されたカラムの値が同じレコードが複数存在する場合、それらのレコード間の順序を保証しません。これを「ソートが安定でない」あるいは「非決定的である」と表現します。データベースはパフォーマンスを最適化するため、同じソートキーを持つレコード群をその時々の内部的な都合（データ格納状況、並列処理のタイミングなど）で異なる順序で返す可能性があるのです。

この非決定的な動作がページネーションでどのように問題を引き起こすか、具体的なシナリオで見てみましょう。以下のようなARTICLEテーブルがあるとします。

id (PK) title posted
25記事Y2023-10-27 12:00:00
24記事X2023-10-27 12:00:00
23記事W2023-10-27 11:59:59
.........

ここで、IDが24と25の記事は全く同じ日時に投稿されています。この状態で1ページ目のクエリを実行したとします。


-- 1回目のクエリ実行（1ページ目）
SELECT id, title, posted FROM ARTICLE
ORDER BY posted DESC
LIMIT 1;

このクエリに対して、データベースはpostedが同じであるID 24と25のどちらを先に返しても仕様上問題ありません。仮に、以下のような順序で結果セットが内部的に生成されたとしましょう。

クエリ1の内部的な全件ソート結果（仮）:
1. id: 25, posted: '2023-10-27 12:00:00'
2. id: 24, posted: '2023-10-27 12:00:00'
3. id: 23, posted: '2023-10-27 11:59:59'
...

この場合、LIMIT 1によってID 25の記事がユーザーに表示されます。次に、ユーザーが2ページ目に進むために、次のクエリが実行されます。


-- 2回目のクエリ実行（2ページ目）
SELECT id, title, posted FROM ARTICLE
ORDER BY posted DESC
LIMIT 1 OFFSET 1;

この2回目のクエリが実行される際、データベースが再びソートを行いますが、この時にID 24と25の順序が1回目のクエリと同じである保証はどこにもありません。例えば、何らかの理由で今回は逆の順序になったとします。

クエリ2の内部的な全件ソート結果（仮）:
1. id: 24, posted: '2023-10-27 12:00:00'
2. id: 25, posted: '2023-10-27 12:00:00'
3. id: 23, posted: '2023-10-27 11:59:59'
...

このソート結果に対してOFFSET 1が適用されると、1件目（ID 24）がスキップされ、2件目のID 25の記事が結果として返されます。結果として、ユーザーは1ページ目でも2ページ目でも同じID 25の記事を見ることになり、ID 24の記事は表示される機会を失ってしまいます。これがデータ重複・欠損問題の正体です。

この問題は、ミリ秒単位で投稿が行われるような高頻度の書き込みがあるシステムや、バッチ処理で多数のデータが同じタイムスタンプで登録されるようなシステムで特に顕著になります。

解決策1：ソート順序を決定的にする

この問題の根本原因が「ソート順序の非決定性」にある以上、解決策は「ソート順序を決定的にする」ことです。つまり、どのような状況で何度クエリを実行しても、全レコードの相対的な順序が常に一意に定まるようにすればよいのです。

これを実現する最も簡単で確実な方法は、ORDER BY句に一意な値を保証するカラムを第二、第三のソートキーとして追加することです。テーブルには通常、プライマリキー（主キー）としてユニークかつ非NULLなカラムが存在します。このプライマリキー（例えばid）を利用するのが一般的です。

先ほどの問題のあるクエリを以下のように修正します。


-- 修正後のクエリ
SELECT * FROM ARTICLE
ORDER BY posted DESC, id DESC
LIMIT 10 OFFSET 10;

このクエリの動作は以下のようになります。

  1. まず、postedカラムの降順（新しいものが先）でソートします。
  2. もしpostedの値が同じレコードが複数存在した場合、そのレコード群の中でのみ、次に指定されたidカラムの降順（IDが大きいものが先）でソートします。

idはプライマリキーであるため、全てのレコードで値が異なります。したがって、「postedが同じで、かつidも同じ」というレコードは存在し得ません。これにより、全てのレコードの順序が一意に確定し、ソート結果は常に決定的になります。

先ほどのシナリオにこの修正を適用してみましょう。

修正後クエリの内部的な全件ソート結果（常にこの順序）:
1. id: 25, posted: '2023-10-27 12:00:00' (postedが同じなのでidで比較。25 > 24)
2. id: 24, posted: '2023-10-27 12:00:00'
3. id: 23, posted: '2023-10-27 11:59:59'
...

この状態であれば、何度クエリを実行してもこの順序は変わりません。

  • 1ページ目 (LIMIT 1 OFFSET 0): ID 25の記事が返される。
  • 2ページ目 (LIMIT 1 OFFSET 1): ID 24の記事が返される。

このように、データが重複することなく、また欠損することもなく、正しくページネーションが機能するようになります。idを降順(DESC)にするか昇順(ASC)にするかは要件によりますが、一般的には「同じ投稿日時なら、後から登録された（IDが大きい）方を新しいものとして扱いたい」というケースが多いため、DESCがよく用いられます。

プライマリキー以外のユニークキー

プライマリキー以外にも、ユニーク制約を持つカラムであればソートキーとして利用できます。また、SQLiteのような一部のデータベースでは、テーブル作成時に明示的に指定しなくてもROWIDという内部的な一意の識別子が各行に割り当てられています。これもユニークキーとして利用可能です。


-- SQLiteの場合
SELECT * FROM ARTICLE
ORDER BY posted DESC, ROWID DESC
LIMIT 10 OFFSET 10;

重要なのは、ソート順序を最終的に一意に定めることができる「何か」をORDER BY句の末尾に追加することです。

OFFSETの限界とパフォーマンスの問題

ソート順序を決定的にすることで、データの重複・欠損問題は解決できました。しかし、OFFSETを用いたページネーションには、もう一つ別の大きな問題が潜んでいます。それはパフォーマンスの劣化です。

LIMIT 10 OFFSET 10000のようなクエリを考えてみてください。これは「10001件目から10件のデータを取得する」という意味です。この時、データベースは内部で何をしているのでしょうか。多くのデータベースシステムでは、以下のステップで処理が進められます。

  1. WHERE句に合致する全てのレコードを取得する。
  2. それらのレコードをORDER BY句に従ってソートする。
  3. 先頭からOFFSETで指定された10000件のレコードを読み飛ばす。
  4. その後ろの10件を結果として返す。

ここで重要なのは、最終的に10件しか必要ないにもかかわらず、データベースは10010件のデータをメモリ上に展開し、ソートし、そのうち10000件を破棄しているという点です。OFFSETの値が大きくなればなるほど、この無駄な処理のコストは増大し、クエリの応答時間は著しく悪化します。ユーザーがページの深い階層（例：500ページ目）にアクセスしようとすると、アプリケーションがタイムアウトしてしまう可能性さえあります。

解決策2：Keyset Pagination (Seek Method / Cursor-based Pagination)

OFFSETのパフォーマンス問題を根本的に解決し、かつデータの重複問題も発生しない、より優れたアプローチがKeyset Pagination（キーセット・ページネーション）です。これは「カーソルベース・ページネーション」や「シークメソッド」とも呼ばれます。

この方式の基本的な考え方は、「Nページ目」というオフセット（位置）でデータを取得するのではなく、「前のページの最後のレコードの次からN件」という条件でデータを取得することです。これにより、不要なデータをスキップする処理が不要になります。

実装にはOFFSETの代わりにWHERE句を使います。先ほどのORDER BY posted DESC, id DESCの例で見ていきましょう。

Keyset Paginationの実装

1ページ目の取得:
これは通常通り、単純なLIMIT句で取得します。


SELECT * FROM ARTICLE
ORDER BY posted DESC, id DESC
LIMIT 10;

このクエリの結果、最後のレコードが {id: 150, posted: '2023-10-26 18:30:00'} だったとします。この「最後のレコードのpostedとidの値」が次のページを取得するための "カーソル" となります。

2ページ目の取得:
クライアントは、1ページ目の最後に取得したレコードのpostedとidをサーバーに送ります。サーバーはそれらの値を使って、次のようなWHERE句を組み立てます。


-- 前ページの最後の値が (posted='2023-10-26 18:30:00', id=150) だった場合
SELECT * FROM ARTICLE
WHERE (posted, id) < ('2023-10-26 18:30:00', 150)
ORDER BY posted DESC, id DESC
LIMIT 10;

このクエリの意味を解説します。

  • ORDER BY posted DESC, id DESCの順序において、
  • (posted, id)のタプル（組）が、カーソルである('2023-10-26 18:30:00', 150)よりも「小さい」レコードを探しています。
  • SQLのタプル比較では、まず最初の要素（posted）が比較されます。
    • posted < '2023-10-26 18:30:00' であれば、条件に一致します。
    • posted = '2023-10-26 18:30:00' の場合は、次の要素であるidが比較され、id < 150 であれば条件に一致します。

このWHERE句は、まさに「1ページ目の最後のレコードよりも古い（またはIDが小さい）レコード」を効率的に絞り込むための条件式です。そして、この(posted, id)に複合インデックスが張られていれば、データベースはインデックスを使って目的の開始位置に直接アクセス（シーク）できるため、OFFSETのように大量のデータを読み飛ばす必要がありません。これにより、100ページ目でも10000ページ目でも、1ページ目とほぼ変わらない速度でデータを取得できます。

Keyset Paginationの利点と欠点

利点

  • 高いパフォーマンス: ページ番号が深くなってもパフォーマンスが劣化しません。大規模なデータセットに最適です。
  • 安定した結果: ページ取得の間に新しいデータが挿入されても、取得済みのページとこれから取得するページの間にデータが入り込むだけなので、ページのズレや重複が発生しません。OFFSET方式が抱える根本的な問題を解決します。
  • リアルタイム更新との親和性: いわゆる「無限スクロール」の実装に非常に適しています。

欠点

  • 特定のページへの直接ジャンプが困難: 「50ページ目に飛ぶ」といった機能の実装が複雑になります。Keyset Paginationは本質的に「次のページ」「前のページ」という相対的な移動しかサポートしないためです。
  • 実装の複雑さ: OFFSETに比べて、クライアントとサーバー間でカーソル情報（最後のレコードの値）をやり取りする必要があるため、実装がやや複雑になります。
  • 複雑なソート条件への対応: ソートキーが動的に変わるような要件では、WHERE句の構築がさらに複雑化する可能性があります。

インデックスの重要性

これまで説明してきたどの解決策を採用するにしても、パフォーマンスを最大限に引き出すためには適切なインデックス設計が不可欠です。

ORDER BY posted DESC, id DESCという句を効率化するためには、この2つのカラムを同じ順序で含んだ複合インデックスを作成することが極めて重要です。


CREATE INDEX idx_article_posted_id ON ARTICLE (posted DESC, id DESC);

このインデックスが存在することで、データベースはソート済みのデータ構造をディスク上で保持できます。クエリが実行されると、ファイル全体をソートする（Filesort）のではなく、インデックスを順に読み取るだけで済むため、処理が劇的に高速化します。これは、安定ソート版のOFFSET方式でも、Keyset Pagination方式でも同様に効果があります。特にKeyset Paginationでは、WHERE (posted, id) < (?, ?)という条件がインデックスレンジスキャンを最大限に活用できるため、その恩恵は絶大です。

まとめ：どの手法を選択すべきか

データベースのページネーションにおけるデータ重複問題とその解決策について、深く掘り下げてきました。最後に、状況に応じた最適な手法の選択指針をまとめます。

  1. 基本要件（必須）:

    どのようなページネーションを実装するにせよ、ORDER BY句には必ずプライマリキーなどのユニークなカラムを追加し、ソート順序を決定的にしてください。これを怠ると、データの重複や欠損が発生し、アプリケーションの信頼性が損なわれます。

    -- 悪い例
ORDER BY posted DESC

-- 良い例
ORDER BY posted DESC, id DESC
  2. 小規模データ・深いページへのアクセスが稀な場合:

    総レコード数が少なく、ユーザーが数ページ先までしか見ないことが想定されるアプリケーション（例：個人のブログ、小規模な管理画面）であれば、修正済みのOFFSET方式でも十分実用的です。実装が簡単というメリットがあります。

  3. 大規模データ・パフォーマンス・安定性が重要な場合:

    SNSのタイムライン、大規模なECサイトの商品リスト、ログビューアなど、データ量が膨大で、かつパフォーマンスと結果の安定性が厳しく求められる場合は、Keyset Paginationの採用を強く推奨します。これは現代的なWebアプリケーションにおけるデファクトスタンダードと言える手法です。

一見些細に見えるデータ重複の問題は、データベースの基本的な動作原理と深く結びついています。その原因を正しく理解し、OFFSETの持つ利便性と欠点を認識した上で、Keyset Paginationというより堅牢な選択肢を知ることは、スケーラブルで信頼性の高いアプリケーションを構築するための重要なステップです。安易な実装が将来の技術的負債とならないよう、データ量やユースケースを考慮した上で最適なページネーション戦略を選択してください。


0 개의 댓글:

Post a Comment