※追記：パフォーマンス比較ですが、「インデックスちゃんとはったら良くね？」との指摘がありました。その通りです。申し訳ありません。
RESTful な API を作る時のページネーションのプラクティスが Django RESTful Framework の Pagination に良くまとまっているので、 Django 以外の別の実装のためにも汎用化したい。
レスポンスの表現方法
レスポンスで次のページを示す方法には以下の方法がある。
- JSON や XML のレスポンスに含める
-
Linkヘッダに URL で指定する -
Content-Rangeヘッダを使う
どちらをサポートしても良いし、データ量や複雑性を気にしなければ両方サポートしても良いと思う。 ただし、現状としてはヘッダはページネーションを想定して作られている気がしないので、コンテンツに含める方がオススメのような気がする。 追記：一番標準っぽいのは さらに追記： Request URI からの相対パスが使える ので、クエリ部分だけ再構築して Link ヘッダっぽいけど、 URL を返さないといけないのが冗長な感じがする。個人的にはレスポンスに含めたい。? から始まる文字列を返すのが良さそう。
When it has the form of a relative reference ([RFC3986], Section 4.2), the final value is computed by resolving it against the effective request URI ([RFC3986], Section 5).
RESTful API の話からはずれるけど Google の検索では数年前から rel=prev/next をサポートしていないらしい。検索を意識する場合は最終的に body に反映するようにしましょう。
Spring cleaning!
— Google Webmasters (@googlewmc) March 21, 2019
As we evaluated our indexing signals, we decided to retire rel=prev/next.
Studies show that users love single-page content, aim for that when possible, but multi-part is also fine for Google Search. Know and do what's best for *your* users! #springiscoming pic.twitter.com/hCODPoKgKp
リクエストの表現方法
LIMIT/OFFSET 型
?limit=100&offset=500 みたいにパラメータを付ける方法。
SQL の LIMIT 句そのままなので実装が簡単で、クライアントの自由度も高い。
ページ番号型
例えば ?page=4 のようになる。LIMIT/OFFSET 型にちょっと算数が入る程度だが、クエリのパターン数が絞られるのでキャッシュしやすくなる。事前に用意するような場合は LIMIT/OFFSET よりも簡単。
カーソル 型
開始するデータの ID を指定する方法。おそらくソートされたデータを計算中に保持しなくても良いので、データ量が大きくなった場合に効果が出てくる。例えば ?cursor=...&limit=100 のように表現する。
LIMIT/OFFSET 型に対する反対意見は、Building Cursors for the Disqus API の記事で書かれている。例えば、タイムラインのような件数の定まらない最新のものを取りたい場合などは OFFSET による特定が簡単にならない場合が出てくる。パーティションで分けて保存されていたりすると、パーティションの先頭が全データから数えて何番目か？を考える必要がなくて良い。 AWS の Dynamo DB もレスポンスの LastEvaluatedKey とリクエストの ExclusiveStartKey で動作する。
他に較べてクライアント側の戻る処理が難しくなったり、いくつかのページを飛ばしたりする処理ができなくなってしまう。その代わり、下までスクロールすると自動で伸びるページネーションが向いている。また、時間が経った後にアクセスしても、対象のデータの間に入ることが無ければ、新しい記事によって押し出されて内容が変わることも無い。ユーザがどこかにクエリ付き URL を貼ってしばらくしても、同じデータを表示することができるようになる。
まとめ
- 次のページのリクエストに必要な情報を表現する方法は、
今のところ特に決まりはないLinkヘッダが良さそう。 - データの特性によって、リクエストの表現方法を選定するべき
- DB のインデックスが許す限りは、クライアントが自由に決めれる LIMIT/OFFSET 型でも問題はない
- 事前に計算したりキャッシュする場合は、ページ番号で引くようにする方法が考えられる
- カーソル型は件数が増えてもそれほど遅くはならないが、ユーザの操作が制限されてしまう
- 新着順の URL で時間が経っても同じデータを表示できる
- DynamoDB や Cassandra などの NoSQL と相性が良さそう
以下昔の間違ってた情報。 CREATE INDEX name_id ON profiles (name, id); すれば、どちらでも 0.200[s] ぐらいになります。
カーソル型のパフォーマンス
SQL で実際に LIMIT/OFFSET 型と比較してみた。
CREATE TABLE profiles (
id CHAR(36) PRIMARY KEY,
name VARCHAR(80)
);
データは 1,000,000 件。name は 疑似個人情報データ生成サービス から 100 人分生成して 10,000 回 INSERT で計 1,000,000 件。したがって、 name だけでは順序が一意に定まらないので、 (name, id) でソートする。ちなみに id はUUID。
本来はクエリを変えて何回か回したりキャッシュを消したりするべきだが、結果が十分に有意な感じがするので簡単なやつだけ。
LIMIT/OFFSET 型 (SQLite3)
コマンド：
time sqlite3 test.db "SELECT * FROM profiles ORDER BY name, id LIMIT 500000,10"
結果：
2.08s user 2.40s system 99% cpu 4.497 total
カーソル型 (SQLite3)
コマンド：
time sqlite3 test.db "SELECT p.* FROM profiles p, (SELECT name, id FROM profiles WHERE id='fffe95b6-4032-458a-bda6-cb49dc0f9261') AS v WHERE p.name>v.name OR (p.name=v.name AND p.id>v.id) ORDER BY p.name, p.id LIMIT 10"
結果：
0.25s user 0.02s system 99% cpu 0.264 total
LIMIT/OFFSET 型 (MariaDB)
コマンド：
time mysql pagination_test -u root -e "SELECT * FROM profiles ORDER BY name, id LIMIT 500000,10"
結果：
0.00s user 0.00s system 0% cpu 20.562 total
カーソル型 (MariaDB)
コマンド：
time mysql pagination_test -u root -e "SELECT p.* FROM profiles AS p WHERE (p.name, p.id)>(SELECT name, id FROM profiles WHERE id='fffe95b6-4032-458a-bda6-cb49dc0f9261') ORDER BY p.name, p.id LIMIT 10"
結果：
0.01s user 0.00s system 1% cpu 0.573 total