Edited at

RESTful API のページネーションで考えるべきこと

※追記:パフォーマンス比較ですが、「インデックスちゃんとはったら良くね?」と指摘されました。その通りです。申し訳ありません。

RESTful な API を作る時のページネーションのプラクティスが Django RESTful Framework の Pagination に良くまとまっているので、 Django 以外の別の実装のためにも汎用化したい。


レスポンスの表現方法

レスポンスで次のページを示す方法には以下の方法がある。

どちらをサポートしても良いし、データ量や複雑性を気にしなければ両方サポートしても良いと思う。 ただし、現状としてはヘッダはページネーションを想定して作られている気がしないので、コンテンツに含める方がオススメのような気がする。 追記:一番標準っぽいのは Link ヘッダっぽいけど、 URL を返さないといけないのが冗長な感じがする。個人的にはレスポンスに含めたい。 さらに追記: Request URI からの相対パスが使える ので、クエリ部分だけ再構築して ? から始まる文字列を返すのが良さそう。


リクエストの表現方法


LIMIT/OFFSET 型

?limit=100&offset=500 みたいにパラメータを付ける方法。

SQL の LIMIT 句そのままなので実装が簡単で、クライアントの自由度も高い。


ページ番号型

例えば ?page=4 のようになる。LIMIT/OFFSET 型にちょっと算数が入る程度だが、クエリのパターン数が絞られるのでキャッシュしやすくなる。


カーソル 型

開始するデータの ID を指定する方法。おそらくソートされたデータを保持しなくても良いので、データ量が大きくなった場合に効果が出てくる。例えば ?cursor=...&limit=100 のように表現する。

LIMIT/OFFSET 型に対する反対意見は、Building Cursors for the Disqus API の記事で書かれている通り、 OFFSET による特定が簡単にならない場合が出てくる。パーティションで分けて保存されていたりすると、パーティションの先頭が全データから数えて何番目か?を考える必要がなくて良い。 AWS の Dynamo DB もレスポンスの LastEvaluatedKey とリクエストの ExclusiveStartKey で動作する。

他に較べてクライアント側の戻る処理が難しくなったり、いくつかのページを飛ばしたりする処理ができなくなってしまう。その代わり、下までスクロールすると自動で伸びるページネーションが向いている。また、時間が経った後にアクセスしても、対象のデータの間に入ることが無ければ、新しい記事によって押し出されて内容が変わることも無い。


まとめ


  • 次のページのリクエストに必要な情報を表現する方法は、 今のところ特に決まりはない Link ヘッダが良さそう。

  • データの特性によって、リクエストの表現方法を選定するべき


    • DB のインデックスが許す限りは、クライアントが自由に決めれる LIMIT/OFFSET 型でも問題はない

    • 事前に計算したりキャッシュする場合は、ページ番号で引くようにする方法が考えられる

    • カーソル型は件数が増えてもそれほど遅くはならないが、ユーザの操作が制限されてしまう

    • 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