Keyset (Cursor) Pagination vs SQL OFFSET

This lab pages through a large list that other requests keep changing, such as a feed, an inbox, an audit log, or an API collection. Every page should be equally cheap no matter how deep the user scrolls. A row should never appear twice or go missing because of concurrent inserts or deletes.

Where it shows up

• Infinite-scroll feeds and timelines ("load more").
• Public APIs: Stripe starting_after/ending_before, Slack response_metadata.next_cursor, and GitHub GraphQL after:/endCursor.
• Batch jobs and exports that walk a whole table in chunks without long transactions.
• Search engines: Elasticsearch search_after. Deep from + size paging is capped by index.max_result_window, which defaults to 10,000.

The two queries

CREATE INDEX posts_feed_idx ON posts (created_at DESC, id DESC);

-- OFFSET: the database walks and discards :offset index entries first.
SELECT id, created_at, title FROM posts
ORDER BY created_at DESC, id DESC
LIMIT 20 OFFSET 90000;                         -- touches 90,020 rows

-- KEYSET ("seek method"): one index descent to (:c, :i), then read 21 rows.
SELECT id, created_at, title FROM posts
WHERE (created_at, id) < (:c, :i)              -- row-value comparison
ORDER BY created_at DESC, id DESC
LIMIT 21;                                      -- LIMIT n+1: extra row => hasMore

-- Same predicate, expanded, for engines without row values (SQL Server) or
-- when the columns sort in mixed directions:
WHERE created_at < :c OR (created_at = :c AND id < :i)

-- Previous page: flip the comparison and the sort, then reverse in the app.
SELECT ... WHERE (created_at, id) > (:c, :i)
ORDER BY created_at ASC, id ASC LIMIT 21;

Table in pagination.js simulates that index. Rows are kept sorted by (created_at DESC, id DESC), seek() binary-searches to the cursor the way a B-tree descent would, and rowsExamined counts the index entries each query touches.

Design and key invariants

1. Total order. created_at alone is not unique. Several rows created in the same millisecond would make the order ambiguous, and a cursor of created_at < :c skips the rest of a tie group (demo step 4, and a test). Adding the primary key as a tie-breaker makes (created_at, id) unique, so every row has exactly one position.
2. The cursor is a position, not a row. The seek is a strict < against the last row's key. It works even if that row has since been deleted (demo step 2, and a test).
3. Stable under writes. Inserts or deletes above the cursor do not shift later pages. A randomized churn test checks that there are no duplicates, that no row which existed for the whole scroll is missed, and that order is strictly descending across page boundaries.
4. Opaque, tamper-evident cursors. A cursor is base64url(JSON{v,k:[created_at,id],d,t}) + "." + base64url(HMAC-SHA256(secret, "v1\n" + scope + "\n" + payload)[:16]).
   • It is opaque so clients don't build their own cursors. That lets the server change the sort key or the encoding later (the v field).
   • It is signed so a client cannot forge a position. Treat the payload as readable, because base64 is not encryption. Use AES-GCM if the keys are sensitive.
   • The scope (route plus filters) is covered by the MAC but not sent, so a cursor minted for ?author=7 is rejected on ?author=all.
   • The check is constant-time (crypto.timingSafeEqual) and requires canonical base64url. The payload is validated again after the MAC check, as defense in depth. maxAgeMs can optionally expire cursors.

Complexity

Space: O(N) for the table. Cursors are O(1).

Failure modes and trade-offs

• OFFSET drift. An insert at the head between requests shifts rows down, so the next page repeats them (demo step 1: 2 duplicates). A delete above the window shifts rows up, so the next page skips them (demo step 2: 2 rows never shown). Over a full scroll with churn, OFFSET showed 4 duplicates and missed 6 rows. Keyset showed 0 and 0.
• No random access. Keyset cannot jump to "page 57". UIs switch to "next/prev" and infinite scroll. If you need page numbers, cap the depth, as Google and Elasticsearch do.
• New rows above the cursor are not shown while scrolling down. That is the stability you asked for. Use prevCursor from the first page, or a since query, to pick up new items.
• Mutable sort keys. If created_at (or a score) can change, a row can move across the cursor and be seen twice or not at all. Only paginate on immutable columns, or snapshot the result (Elasticsearch point-in-time, a REPEATABLE READ transaction).
• Index must match. The ORDER BY has to match an index prefix, in the same direction or fully reversed. Otherwise the database sorts the whole filtered set and the seek gains nothing. Filters such as WHERE author_id = ? should come first: (author_id, created_at DESC, id DESC).
• Secret rotation. Rotating the HMAC key invalidates every cursor that is in flight. Keep a key id in the payload and verify against the current and previous keys.

How production systems do it

• PostgreSQL: row-value comparison (a, b) < ($1, $2) becomes a single B-tree index condition on (a, b). Because B-trees scan in both directions, one ASC index serves the DESC, DESC query.
• MySQL: supports row constructors and, since 5.7, can plan them as index range scans. Older versions needed the expanded OR form.
• Stripe: starting_after=<object id> returns objects after that id in the list's order. The cursor is simply the last object's id.
• Slack Web API: opaque base64 next_cursor strings. An empty next_cursor means the end of the list.
• GitHub GraphQL: Relay connection spec. first/after return pageInfo { endCursor hasNextPage }, and cursors are opaque strings.
• Elasticsearch: search_after: [sort values...], with a unique tie-breaker field and a point-in-time (PIT) for a consistent snapshot. This is the same tuple-cursor idea.

Extension exercises

1. Add a filter, author_id, with index (author_id, created_at DESC, id DESC). Put the filter in the cursor scope and show that a cursor cannot cross authors.
2. Support a mixed-direction sort, ORDER BY score DESC, id ASC, and build the expanded OR predicate. Explain why (score, id) < (...) is wrong here.
3. Add key rotation. Put a kid in the payload, keep {current, previous} secrets, and test that old cursors keep working for one rotation.
4. Encrypt the payload with AES-256-GCM (node:crypto) instead of signing it in plaintext. What does that give you beyond HMAC, and what does it cost?
5. Generate the real SQL string with bind parameters from a (sort spec, cursor) pair, and test it against the in-memory results for random data.