Pagination: offset, keyset & cursors

The same comment, twice

The bug report is one line: "On the election thread, a comment from marta_v shows up at the bottom of page 1 and again at the top of page 2." The thread has 12,000 comments. Sending them all in one response would mean megabytes of JSON and a phone parsing comments nobody will scroll to, so the API sends 50 at a time, newest first, and answers GET /threads/88/comments?page=2 with this query:

SELECT * FROM comments WHERE thread_id = 88 ORDER BY created_at DESC LIMIT 50 OFFSET 50

That is offset pagination: sort the list, skip the first N rows, return the next 50. The query looks fine. The bug comes from what happened between two requests.

A page number points at a moving list

1. The reader loads page 1: the 50 newest comments, with marta_v's comment at position 50.
2. Another user posts a comment, which becomes the newest, at position 1.
3. Every older comment moves down one place, and marta_v's is now at position 51.
4. The reader asks for page 2, and OFFSET 50 starts at position 51: marta_v's comment, again.

A deletion does the opposite: every older comment moves up one place, the 51st slides onto page 1, which the reader has already read, and they never see it. The offset counts positions in a list that keeps changing under it.

Deep pages add a second cost. OFFSET 10000 does not jump anywhere: the database finds the first 10,050 rows in order, throws away 10,000 and returns 50. Even with an index on (thread_id, created_at), that is 10,000 index entries walked for nothing, and the waste grows with every page. How such an index is laid out, and how to see the walk in a query plan, is in Indexing & query optimisation.

Continue after the last row you sent

The fix is to remember a value instead of a position. Page 1's last comment was created at 14:02:07.311, so page 2 is the 50 comments created before that: WHERE thread_id = 88 AND created_at < :c ORDER BY created_at DESC LIMIT 50, with :c bound to that timestamp. This is keyset pagination, also called the seek method: each page continues after the sort key of the last row the client received. A new comment sorts before that key, so it pushes nothing onto the next page, and a deleted one shifts nothing, even if it is the row the client stopped at, because the query compares values and does not need that row to exist.

Ties break it. A bulk import, or a clock that keeps only milliseconds, gives two comments the same created_at. If page 1 ends on the first of them, < skips the second and <= repeats the first. The order needs a tie-breaker, a unique column, so that no two rows sort equal: order by created_at DESC, id DESC, keep both values of the last row, and ask for rows strictly after that pair. PostgreSQL, MySQL and SQLite accept this as a row-value comparison, (created_at, id) < (:c, :i), but not every engine does, and not every planner turns it into an index seek. The expanded form means the same everywhere, created_at < :c OR (created_at = :c AND id < :i), but many planners apply it only as a filter, so add created_at <= :c in front of it to give the index a range to seek.

For the seek to be cheap, an index has to match the order, here (thread_id, created_at, id): the database goes straight to the position and reads the next entries, so page 201 costs about what page 1 costs.

The guarantee has a condition. If the sort key is unique (a total order) and no row's key changes while the reader pages, every row that exists for the whole session is returned exactly once. Comments posted after the reader started normally carry a newer created_at, so they sort before the cursor and appear on the next fresh load. Sort by updated_at instead, and an edited comment moves, so the condition fails. Each page is also its own query against the thread as it is then, not a snapshot taken at page 1; a comment list rarely needs one consistent view across requests, which is a Transactions & isolation levels question.

The cursor the client carries

The client should not need to know that a position is a timestamp and an id. The API packs both into a cursor, an opaque string such as eyJjIjoiMjAyNi0x..., and answers { comments: [...], next_cursor: "..." }; the client sends it back unchanged for the next page. To know whether there is one, the API asks the database for 51 rows: if the 51st exists, it is dropped and next_cursor is built from the 50th, the last row sent; if not, next_cursor is null and the client stops.

Opaque buys freedom: the server can later add the sort order or a filter to the cursor, and no client breaks, because no client ever built one. Opaque is not secret, though. Base64 decodes in a second, so a client can edit or forge a cursor. Decode it as untrusted input: check the types, check that the thread and sort order it records match this request, pass its values as bound parameters and never as SQL text, and sign it with an HMAC if a tampered cursor should be rejected outright. Cap the page size on the server too, at 100 for instance, or limit=1000000 is the whole thread again.

What a cursor cannot do

A cursor knows where the last page ended, not where page 37 starts. Keyset pagination offers next, and previous (the same seek from the page's first row, with the comparison and the order reversed, rows flipped back), but no jump to page 37. A total, as in "page 3 of 240", is a separate count under either method, and a COUNT(*) with the same filters on every request reads every matching row or index entry, so its cost grows with the list, while a keyset page with a matching index costs about the same at any depth. A common answer is a comment_count on the thread row, updated as comments are posted and removed, and shown as "12k comments".

Offset still suits a short list that rarely moves and needs page numbers, such as a moderation queue of 300 reports, with a cap on how deep the page number may go.

Sorting by votes

The thread also has a "Top" tab, sorted by score DESC, id DESC, with a score and an id in the cursor. The guarantee above needed a key that does not change, and a score changes with every vote:

1. The reader loads page 1, which ends on a comment with score 40.
2. A comment with score 38, about to open page 2, gets six upvotes and now scores 44.
3. A comment on page 1 with score 45 gets ten downvotes and now scores 35.
4. The reader asks for page 2, everything ranked after the score-40 comment: the first comment is not in it, and the second appears again.

No cursor over a value that changes while the reader pages can rule out both skips and repeats; the design picks which to tolerate. The client can drop comments whose id it already shows, which removes repeats and nothing else. To remove skips as well, freeze the ranking: on the first request, store the ordered list of ids for this reader, in Redis with a TTL for instance, and make the cursor a position in it. That costs memory per reader and shows a ranking that ages while they read. Accepting the rare skip is often the better trade, because the reader came for the best comments, not for every one.

One last trap: if the API fetches 50 rows and then drops the ones moderation hid, a page comes back with 41, and a client that reads a short page as the end stops early. Filter in the query, with an index that matches the filter, such as (thread_id, visibility, created_at, id) for visibility = 'visible', and signal the end only with a null next_cursor.

Page the thread

The Comment System Challenge asks for threads rendered "with pagination and sorting". A Grid cannot run SQL, so draw the read path: the index the seek uses in the store's title, the cursor on the client's edge. Then decide the Top tab in a note: what its cursor holds, and whether a reader may miss a comment or see one twice.