カーソルベースのページネーション
TL; DR
次ページ・前ページの開始地点をページ識別子として使う。
Pros
ページネーションの対象となるテーブルが大量のデータを持っていても、性能が劣化しない
Cons
「n番目のページ」のような ページ識別子 は作れない
「前のページ」と「後ろのページ」だけめくれる
実装・理解がちょっと難しい
概要
例えば、IDが投稿順に増加する tweets テーブルがあるとする。
code:sql
CREATE TABLE tweets (
id bigint NOT NULL AUTO_INCREMENT PRIMARY KEY,
text TEXT NOT NULL,
)
INSERT INTO tweets (text) VALUES ('Some tweet1') # => ID = 1
INSERT INTO tweets (text) VALUES ('Some tweet2') # => ID = 2
INSERT INTO tweets (text) VALUES ('Some tweet3') # => ID = 3
このテーブルを 10件づつページネーションする場合、以下のようなクエリを打つ。
code:sql
-- 1ページ目
SELECT * FROM tweets
ORDER BY id -- id はプライマリーキーなので、ORDER BYが高速にできる
LIMIT 10
-- 2ページ目
SELECT * FROM tweets
WHERE id > 10 -- 10は、1ページ目最後の tweet のid
ORDER BY id
LIMIT 10
-- 3ページ目
SELECT * FROM tweets
WHERE id > 20 -- 20は、2ページ目最後の tweet のid
ORDER BY id
LIMIT 10
...
これが、カーソルベースのページネーションである。
上記は最も簡単なシチュエーションであり、実際にはもう少し色々考えないといけないことが生まれてくる。
以下で詳しく解説する。
詳細解説
こういうテーブルがあるとする
code:sql
CREATE TABLE items (
id bigint NOT NULL AUTO_INCREMENT PRIMARY KEY,
category_id int unsigned NOT NULL,
updated_at datetime NOT NULL DEFAULT CURRENT_TIMESTAMP
) ENGINE=InnoDB DEFAULT CHARACTER SET utf8mb4;
一意性を表すカラムと、ソート基準のカラムが一致するページネーション
id順に頭からitemsをページネーションしつつ読みたいようなケース
これは概要で説明したものと同じ
以下のように実現できる
1ページ目を読むクエリ
code:sql
SELECT * from items ORDER BY id DESC LIMIT 10;
2ページ目を読むクエリ
code:sql
SELECT * from items WHERE id < ? ORDER BY id DESC LIMIT 10;
どちらのクエリも、プライマリーインデックスが使えるので高速に実行できる ( O(log n) )
一意性を表すカラムと、ソート基準のカラムが一致しないページネーション
updated_at順にitemsを読みたいようなケース
ただし、updated_atは、同時刻にレコードが更新された場合に重複するので、一意性を表すものとしては使えないとする
ナイーブな方法
idだけでカーソルの位置の情報量としては完全なので、原理的には上の例と似たようなクエリで実現可能だが、コストが高い
例えば、以下のようなクエリを発行すると、ORDER BY updated_atによってfilesortになってしまい、負荷が高い
code:sql
SELECT * from items WHERE id < ? ORDER BY updated_at DESC LIMIT 50;
じゃあ...ということで updated_at にインデックスを貼ったら解決しそうな気もするが、実際には解決しない。
理由を説明するために、updated_at にインデックスを貼った場合の、idをカーソルとして使うページネーションを検討する
まず、updated_atにセカンダリインデックスを貼る
1ページ目を読むクエリ
code:sql
SELECT * from items ORDER BY updated_at DESC LIMIT 50;
updated_at にインデックスが貼ってあるので、すでにソートされておりコストはとても低い
2ページ目を読むクエリ
code:sql
SELECT * from items WHERE id < ? ORDER BY updated_at DESC LIMIT 50;
これはコストが高い
オプティマイザがプライマリインデックス ( id でソートされている) を使う場合、updated_atでソートする必要があるため、id < ? を満たすレコードを全件ディスクから取得した上でソートする必要が生じる( O(n log n) + ディスクから大量に読むので遅い)
オプティマイザがセカンダリインデックス ( updated_at ) を使う場合、updated_at でソートされてはいるが、idを使ってセカンダリインデックスを引き当てることはできない。したがってセカンダリインデックスのリーフノードを先頭から舐めて、該当するIDの行を見つけるまで走査する必要があり、index full scanになる( O(n) )
そもそもこのクエリは、id が auto_increment かつ updated_at が単調増加であるという仮定を置かないと動かない気がする
コストの低い方法
カーソルとして id だけでなくupdated_atも指定し、クエリをチョット工夫することで、この問題は解決できる
コストの低いページネーションは、以下のように実現できる
まず、updated_atにセカンダリインデックスを貼る
MySQLのセカンダリインデックスの末尾にはプライマリーキーが暗黙的に付与される
そのため、実質的には (updated_at, id)のインデックスである
1ページ目を読むクエリ
code:sql
SELECT * from items ORDER BY updated_at DESC, id DESC LIMIT 50;
セカンダリインデックス上ですでにupdated_at - ID順にソートされているため、コストはとても低い
2ページ目を読むクエリ
code:sql
SELECT *
FROM items
WHERE
-- updated_atとidのplaceholderには、1ページ目の最後の行のupdated_atとidを入れる
updated_at < ?
OR (updated_at = ? AND id < ?)
ORDER BY updated_at DESC, id DESC
LIMIT 50;
これはコストが低い
まず、セカンダリインデックスを使うと、ORDER BYは低コストで実行できる
そしてWHERE句は、ORの左にも右にもupdated_atが入っているため、対応するセカンダリインデックスのエントリを O(log n) で引き当てられる
その上で、意味的にもこのクエリで所望の行を取得できる
気持ちとしてはupdated_at < ?だけで済ませたいが、そうするとupdated_atが重複したときに結果がおかしくなる
かといって、updated_at <= ?とすると、すでに返却済の行も返却してしまう
そこで、updated_at < ? OR updated_at = ? AND id < ?としておき、同じupdated_atの行を過不足なく返せるようにしつつ、より古いupdated_atの行も取得する
一意性を表すカラムやソートの基準カラムとは別にフィルタ条件があるページネーション
category_idに条件を設けつつ、updated_at順にitemsを読みたいようなケース。
例えば、category_id = 100 の条件を満たす行を、updated_at の降順で読み出したい、のようなイメージ。
このようなクエリをページネーションするには、いくつかのパターンがある。
category_id = 100 のような条件の場合
category_id, updated_at にセカンダリインデックスを貼る
1ページ目を読むクエリ
code:sql
SELECT * from items WHERE category_id = 100 ORDER BY updated_at DESC, id DESC LIMIT 50;
ORDER BYの基準に category_id が入っていないが、WHEREで同一 category_id のみが存在する範囲に絞っているので、セカンダリインデックスでソートできる
2ページ目を読むクエリ
code:sql
SELECT * FROM items
WHERE
category_key = 100 AND
(updated_at < ? OR (updated_at = ? AND id < ?))
ORDER BY updated_at DESC, id DESC
LIMIT 50;
上と同じ理由で低コストでソートできる
category_id < 100 のような条件
一般には、このたぐいのクエリでパフォーマンス良くカーソルベースのページネーションはできなさそう(たぶん)(要出典)。ただし、「ほぼすべてのレコードがこの条件を満たす」という状況であれば、それなりに低コストでページネーションできる。
やり方:
updated_at にセカンダリインデックスを貼る
1ページ目を読むクエリ
code:sql
SELECT * from items
WHERE category_id < 100
ORDER BY updated_at DESC, id DESC
LIMIT 50;
ORDER BYはセカンダリインデックスで処理できる
WHEREはセカンダリインデックスで処理できない。しかし、「ほぼすべてのレコードが category_id < 100 を満たす」という状況であれば、ディスクからレコード本体を取得してからこの判定を行っても、取得したレコードが無駄にならないため、問題とならない。
「実質的には必要ないけど、念の為 category_id もチェックしておく。万が一条件にあわなかったら、もう1件ディスクから読めばいい。」みたいな気持ち
2ページ目を読むクエリ
code:sql
SELECT * from items
WHERE
category_key < 100 AND
(updated_at < ? OR (updated_at = ? AND id < ?))
ORDER BY updated_at DESC, id DESC
LIMIT 50;
解説は省略するが、このクエリも同様の理屈で実行コストは低い
なお、updated_at, id, category_id というインデックスを貼ってもいい
この場合は、 category_id の判定をするのにディスクからレコードを読む必要がなく、インデックス上で走査が完結するという利点がある。一方で、データ挿入時のコストは(多少?)増加するため、書き込み頻度も考慮して判断するとよい。