Pagination
背景
ページング は、閲覧対象のデータが大量にある場合に、それをページという単位に分割してユーザに向けて描画する方法。これは、ユーザには一度に大量のデータを見せられても見きれなかったりだとか、データ一覧にフッターを設けてそれがユーザに見えるようにしておきたいだとかの UX 的な問題と、大量のデータを一度にフェッチしようとするとバックエンド/通信/フロントエンドに負荷がかかるといったパフォーマンス的な問題があり、大抵問題となるのは後者。
ページングの種類
Offset 方式
Offset を利用してページネーションを行う方式は、もっとも広く使われている方式の１つ。クライアントは、以下を要求する。
オフセット値
ページあたりの表示数
ページあたりの表示数は、アプリケーションによっては固定の場合がある。そのような場合は前者だけでもよい。実際の API は以下のようになる。
REST posts?limit=100&offset=500, posts?page=1
GraphQL posts(first: 100, offset: 500), posts(page:1)
https://gyazo.com/ec2799c08f80cee84dc2403974028423
これは、SQL のようなデータベースだと非常に素直に実装できる。以下は、user_id が $id である posts を検索した場合に発行される SQL。"LIMIT" が 10 なのでページあたりの表示数は 10。"OFFSET" が 20 ということは、"WHERE" で絞り込んだ中の 21 件目から 30 件目までを取得することになるので、ページ数でいうと 3 ページ目に描画すべきデータを問い合わせていることがわかる。
code:sql
SELECT * FROM posts WHERE user_id = $id LIMIT 10 OFFSET 20;
また、場合によっては "総ページ数" を表示したり、"次ページが存在しているか？" の判定を行い、それを UI に反映するようなシステムもある。そのような場合には、ページあたりのデータのみでなく、本来描画するはずだった全データの件数を取得する必要がある。SQL だと "SQL_CALC_FOUND_ROWS" や "COUNT()" が利用される。
"SQL_CALC_FOUND_ROWS" は、"LIMIT" つきのクエリでも "LIMIT" なし時の件数を返してくれる "SELECT" 文の拡張機能。
code:sql
/* SQL_CALC_FOUND_ROWS */
SELECT SQL_CALC_FOUND_ROWS * FROM posts ORDER BY created_at LIMIT $limit OFFSET $offset;
SELECT FOUND_ROWS();
/* COUNT() */
SELECT COUNT(*) FROM posts LIMIT 3;
Offset 方式の利点
ユーザは、検索結果として、全データ中何件が検索にヒットしたかがわかる
ユーザは、検索結果の内任意のページにジャンプできる
開発者は、クエリ上明示されていれば任意のソートを簡単に実装できる
Offset 方式の問題点
この方式は、対象とするデータセットが小規模である場合には問題なく動作する。が、データセットが大規模になってくると パフォーマンスの問題 が生じる恐れがある。MySQL の InnoDB エンジンだと、"OFFSET" を N に設定した場合、その N 件までイテレーションする。ので、オフセット値に比例して遅くなる。指定された "OFFSET" 値に存在するレコードがどのようなものであるか？を知る方法は、このようにイテレーションする方法しかない (AUTO_INCREMENT された ID があったとしても、途中に抜けがあったりすると動作しない)。
適当に 30 万件くらいデータを用意して実際に試してみると、LIMIT した結果が一緒でも、OFFSET の値が大きい方が遅くなっていることがわかる。データ量自体はそこまで多くないので大きな差は出ていないが、参考程度に。また、ID は PK になっている。
code:sql
mysql> SET profiling = 1;
/* どちらも、取得件数は 10 件 */
mysql> SELECT * FROM test.item WHERE ID > 10 LIMIT 10 OFFSET 0;
mysql> SELECT * FROM test.item WHERE ID > 10 LIMIT 10 OFFSET 299980;
/* 結果は、OFFSET 値が大きい方が遅い */
mysql> SHOW PROFILES;
+----------+------------+--------------------------------------------------------------+
| Query_ID | Duration | Query |
+----------+------------+--------------------------------------------------------------+
| 1 | 0.00042000 | SELECT * FROM test.item WHERE ID > 10 LIMIT 10 OFFSET 0 |
| 2 | 0.12443300 | SELECT * FROM test.item WHERE ID > 10 LIMIT 10 OFFSET 299980 |
+----------+------------+--------------------------------------------------------------+
2 rows in set, 1 warning (0.00 sec)
また、"SQL_CALC_FOUND_ROWS" や "COUNT" にもパフォーマンス上の問題がある。"SQL_CALC_FOUND_ROWS" は、内部的には "LIMIT" なしの状態での検索結果全てのレコードに対してイテレーションしているので、"LIMIT" しなかった場合と同等の遅さになる。つまり、検索結果のレコード数に比例して重くなる。"COUNT" も同様に、検索結果のレコードを全てイテレーションするため遅い。一応改善方法はある ようだが、結局 検索結果のレコード数に比例して遅くなる 先ほどと同様に実際に試してみると、検索結果のレコード数に応じてクエリが重くなっていることがわかる。
code:sql
mysql> SET profiling = 1;
mysql> SELECT * FROM test.item WHERE ID > 10 LIMIT 3;
/* 結果 299990 件 */
mysql> SELECT SQL_CALC_FOUND_ROWS * FROM test.item WHERE ID > 10 LIMIT 3;
mysql> SELECT FOUND_ROWS();
mysql> SELECT COUNT(*) FROM test.item WHERE ID > 10 LIMIT 3;
/* 結果 9 件 */
mysql> SELECT SQL_CALC_FOUND_ROWS * FROM test.item WHERE ID =< 10 LIMIT 3;
mysql> SELECT COUNT(*) FROM test.item WHERE ID =< 10 LIMIT 3;
mysql> SHOW PROFILES;
+----------+------------+--------------------------------------------------------------------+
| Query_ID | Duration | Query |
+----------+------------+--------------------------------------------------------------------+
| 1 | 0.01025100 | SELECT * FROM test.item WHERE ID > 10 LIMIT 3 |
| 2 | 0.13320100 | SELECT SQL_CALC_FOUND_ROWS * FROM test.item WHERE ID > 10 LIMIT 3 |
| 3 | 0.00018600 | SELECT FOUND_ROWS() |
| 4 | 0.07463900 | SELECT COUNT(*) FROM test.item WHERE ID > 10 LIMIT 3 |
| 5 | 0.00046100 | SELECT SQL_CALC_FOUND_ROWS * FROM test.item WHERE ID =< 10 LIMIT 3 |
| 6 | 0.00043100 | SELECT COUNT(*) FROM test.item WHERE ID =< 10 LIMIT 3 |
+----------+------------+--------------------------------------------------------------------+
6 rows in set, 1 warning (0.00 sec)
さらに、静的なページ毎のページネーションは、対象のデータがあまり動的に変化しない場合はうまく動作する。が、検索対象のデータが頻繁に更新される場合には、以下のような問題を引き起こす恐れがある。
ページ遷移時にデータをスキップして表示してしまう
ページ遷移時にデータを重複して表示してしまう
問題は、ページ遷移の間に動的にデータが書き換わった場合 に起こる。例えば、ページ 1 を取得してからページ 2 を取得するまでの間に新たにデータが挿入されると、本来表示すべきデータのスキップ、もしくは前ページのデータの重複表示が発生してしまう。
https://gyazo.com/bc6f757cadb836bea61bf87e39f02d9d
Cursor 方式
Cursor 方式は、まずデータ取得の始点 (Cursor) を指定して、そこを起点にいくつデータを取得したいか、を指示する。この方式では、クライアントは以下を要求する。
開始位置 (Cursor)
データの取得数
Cursor 方式の場合、この時のデータの取得数が Offset 方式でいうページあたりの表示数と同様なる。実際の API は以下のようになる。
REST posts?after="a"&first=500
GraphQL posts(after: "a", first: 500)
SQL で記述すると、以下のようになる。$after には Cursor 値、LIMIT にはデータの取得数を指定する。下記のケースでは、Cursor 値としてデータの作成日時を利用している (ただし、作成日時は頻繁にデータの挿入を行なっている場合にはかぶることもあるので、利用する場合にはユニークキー制約を DB 側でかける等の対策が必要になる)。
created_at にインデックスが効いている場合には、created_at が $after である箇所はすぐに発見できる。そのため、Offset 方式と違い高速な取得が可能になる。
code:sql
SELECT * FROM posts WHERE created_at < $after ORDER BY created_at LIMIT 10;
Relay Cursor Connections Specification
また、GraphQL の文脈でいうと、まず Facebook には GraphQL の元になった？と思われる GraphAPI というものがあり、そこで Cursor 方式が利用されていて、その後 GraphQL が OSS となり、GraphQL のクライアントサイドフレームワークである Facebook 製の Relay でも、GraphAPI の Cursor 方式を踏襲したと思われるような方式が採用されているようにみえる (割と推測が含まれているので要出典)。
Cursor 方式の利点
Offset 方式に比べて高速
ページ遷移時のデータのスキップや重複の恐れがない
Cursor 方式の問題点
Cursor 方式には、以下のような特徴/制約がある。
Cursor 値はユニークかつシーケンシャルである必要がある
総ページ数や、検索結果件数等の概念はない
ユーザは、特定のページにジャンプすることはできない
また、Cursor となるカラムはユニークである必要があり、ソートを行いたい場合には、そのソートするカラムを Cursor とする必要があるため、任意のカラムでソートしづらい という問題がある。また、場合によっては ORDER BY でインデックスが利用されず重くなる 場合もある。この解決策としては 自己結合を利用する というものがある。 まとめ
table:比較
方式 ソート リアルタイム パフォーマンス
Offset ◯ × △
Cursor △ ◯ ◯