Part 4 — Fast at scale › Chapter 30

Pagination that scales

OFFSET 100000 reads a hundred thousand rows in order to throw them away. Keyset pagination does not.

No advert asked for this

In no advert; in every application. Page 5 000 of a report is where OFFSET stops being acceptable.

Why OFFSET degrades

🧒 Simple

To read page 500 of a book with no page numbers, you count pages from the beginning. Every time. Page 1 is instant, page 500 takes five hundred times as long — and you throw away everything you counted.

Offset pagination, and the arithmetic that makes page 5001 slow.
SELECT * FROM orders ORDER BY placed_at DESC    -- sort the whole table…
OFFSET 100000 ROWS FETCH NEXT 20 ROWS ONLY;     -- …then discard the first 100 000
-- Reads 100 020 rows to return 20. Page 1 is instant; page 5001 is not.
Why the cost grows with the page number
  • OFFSET is not a seek. The engine has no way to jump to the hundred-thousandth row of a sorted result without producing the hundred thousand rows before it.
  • So the cost is proportional to how deep the page is, and everything counted is thrown away. Page 500 costs five hundred times page 1.
  • There is a correctness problem too: if a row is inserted while the user reads page 3, everything shifts by one and page 4 shows a row they already saw — or hides one they never did.
🎓 Professional

OFFSET n is not a seek. The engine must produce the first n rows in order and discard them, so the cost is O(offset + limit) and grows linearly with page number. Page 1 is free, page 5 000 is a table scan with extra steps. Worse, the cost is paid on every page, so a user paging through results makes it slower as they go — which is exactly the opposite of what they expect.

Keyset pagination

🧒 Simple

Instead of counting from the front, use a bookmark: “carry on from where I left off”. Turning to a bookmark costs the same whether it is page 2 or page 900.

Keyset pagination: “carry on from where I left off”, at the same cost for every page.
-- Page 1: no bookmark yet, so just take the first twenty.
SELECT id, placed_at, total_cents FROM orders   -- the columns the list needs
ORDER BY placed_at DESC, id DESC                -- the sort, with a tie-breaker
LIMIT 20;                                       -- one page

-- Every subsequent page: remember the LAST ROW of the page you just showed
-- (placed_at = :last_at, id = :last_id) and ask for what comes after it.
SELECT id, placed_at, total_cents FROM orders   -- the same columns…
WHERE (placed_at, id) < (:last_at, :last_id)    -- ROW-VALUE comparison: the bookmark
ORDER BY placed_at DESC, id DESC                -- the SAME sort — it must match exactly
LIMIT 20;                                       -- the next page, at constant cost
The row-value comparison, and why the tie-breaker is mandatory
  • (placed_at, id) < (:last_at, :last_id) compares the pair lexicographically: earlier placed_at, or the same placed_at and a lower id. Writing it as placed_at <= :last_at AND id < :last_id is a different, wrong condition.
  • Without id in both the sort and the bookmark, two orders sharing a timestamp straddle a page boundary: one is shown twice and one never. The tie-breaker must be unique, which is why it is the primary key.
  • PostgreSQL, MySQL and SQLite support the row-value form. SQL Server does not — write the expanded equivalent there, and check the plan, because the expansion is easy to get subtly wrong.
  • Inserts no longer disturb the paging: the bookmark refers to a row, not to a position.
🎓 Two things make this work
  1. The tie-breaker. placed_at alone is not unique, so two orders with the same timestamp would be skipped or repeated across the page boundary. Adding id makes the sort total, which is what makes the bookmark unambiguous.
  2. The row-value comparison. (a, b) < (x, y) is lexicographic and — crucially — sargable against an index on (a, b). Expanding it by hand into a < x OR (a = x AND b < y) is logically identical and typically not optimised into a single seek. PostgreSQL, MySQL and Oracle support the tuple form; SQL Server does not, so write the expanded form there and check the plan.
The index that makes keyset pagination constant-cost.
CREATE INDEX ix_orders_page ON orders (placed_at DESC, id DESC);  -- the sort, materialised
-- Now every page is ONE seek plus twenty sequential index entries.
-- Page 5 000 costs exactly what page 1 costs.
Why the index must match the ORDER BY
  • The index stores the rows in exactly the order the query asks for, so the engine seeks to the bookmark and walks forward. No sort step appears in the plan — check for its absence.
  • The declared DESC is mostly cosmetic for a single-column index, since a B-tree can be read backwards. For a mixed sort — placed_at DESC, id ASC — the directions in the index must match, or the engine sorts anyway.
  • This is the same index that serves “most recent orders” on the dashboard. One index, two features, which is what good index design looks like.
OFFSET versus keyset pagination cost by page number The cost of OFFSET pagination rises linearly with page number, while keyset pagination stays flat. page number → rows read OFFSET — O(offset + limit) keyset — O(limit), flat
Same query, same index, same result rows. Different amount of work discarded.

What keyset pagination cannot do

⚠ Be honest about this in an interview
  • No “jump to page 47”. You can only go forward and back from where you are. For infinite scroll and “next page” that is fine; for a numbered pager it is not.
  • No total page count without a separate COUNT(*), which on a large filtered set is itself expensive. Approximate counts (reltuples, sys.dm_db_partition_stats) or "showing 1–20 of many" are the usual compromises.
  • The sort must be total, and the sort columns must be stable — you cannot keyset-paginate by a column that changes while the user is paging.
✔ Keyset has one advantage nobody mentions

It is correct under concurrent inserts. With OFFSET, a row inserted before your position while you are reading shifts everything down by one, so page 2 repeats the last row of page 1 — and a deleted row skips one entirely. Users report it as "duplicates in the list" and nobody can reproduce it. Keyset pagination anchors on a value, not a count, so this cannot happen.

API cursors are keyset pagination with a wrapper

An API cursor is a keyset bookmark with a wrapper around it.
-- Encode the bookmark opaquely, so clients cannot construct one and so you can
-- change the sort order later without breaking them.
{ "items": [...],
  "nextCursor": "eyJhdCI6IjIwMjYtMDMtMTRUMDk6MTIiLCJpZCI6ODgxfQ" }
-- base64 of {"at":"2026-03-14T09:12","id":881}
How to read this, and the security note that comes with it
  • A JSON response, not SQL. nextCursor is the last row's sort key, base64-encoded so it reads as an opaque token.
  • Opaque is an API-design win: clients treat it as a token rather than as ?page=37, so you can change the sort or add a tie-breaker without a breaking change.
  • Opaque is not a security boundary. Base64 is encoding, not encryption: anyone can decode it, edit the values and re-encode. If the cursor carries anything a client should not choose — a tenant id, a permission scope — sign it or encrypt it, or they can page through data they should not see.
Sign it, or at least treat it as untrusted

A cursor is user input that goes straight into a WHERE clause. Base64 is not encryption — anyone can decode, edit and re-encode it. Bind it as a parameter like any other input (chapter 34), and if the cursor carries filter state as well as position, sign it, or a client can page through data they should not see.

Compare what each has to read, in the playground.
-- Offset: the engine produces everything up to the offset and discards it.
EXPLAIN QUERY PLAN                                              -- ask for the plan…
SELECT * FROM orders ORDER BY placed_at DESC, id DESC           -- …of the offset version…
LIMIT 20 OFFSET 1500;                                           -- …fifteen hundred rows in

-- Keyset: the engine seeks straight to the bookmark.
EXPLAIN QUERY PLAN                                              -- the same request…
SELECT * FROM orders                                            -- …for the keyset version
WHERE (placed_at, id) < ('2025-06-01T00:00:00Z', 0)             -- the bookmark…
ORDER BY placed_at DESC, id DESC LIMIT 20;                      -- …same sort, same page size
What to look for in the two plans
  • The offset version shows a full SCAN and a temporary sort; the keyset version shows a SEARCH using the index. That difference is the entire chapter.
  • On 1800 rows both are instant. The point is the shape of the plan: one grows with the offset, the other does not.
  • '2025-06-01T00:00:00Z' is a text literal compared to a text column — SQLite stores these timestamps as ISO-8601 strings, and ISO-8601 sorts chronologically as text. In PostgreSQL or SQL Server the same comparison would be against a real timestamp type.
  1. OFFSET n costs O(offset + limit): it produces and discards every earlier row.
  2. Keyset pagination anchors on the last row's sort values and costs the same on every page.
  3. The sort must be total — add a unique tie-breaker such as the primary key.
  4. Row-value comparison (a, b) < (x, y) is sargable; the hand-expanded OR form usually is not.
  5. SQL Server has no row-value comparison. Write the expanded form and verify the plan.
  6. Index on exactly the sort columns, in the sort direction.
  7. Keyset cannot jump to an arbitrary page and cannot cheaply give a total count. Say so.
  8. Keyset is also correct under concurrent inserts; OFFSET silently duplicates and skips rows.
  9. An API cursor is untrusted user input. Parameterise it, and sign it if it carries filter state.

Interview questions this chapter answers

Why is page 5 000 slow?

Because OFFSET is not a seek — the engine has to generate the first 100 000 rows in sorted order and throw them away. The cost is proportional to the offset, so it grows as the user pages. Keyset pagination replaces the count with a value comparison and is flat.

Implement keyset pagination.

Order by a total sort — the display column plus a unique tie-breaker — and filter with a row-value comparison against the last row of the previous page, with an index matching the sort. And I would say what it costs: no jumping to page 47, and no cheap total count.

A user reports seeing the same record on two consecutive pages. Why?

Either the sort is not total, so equal-valued rows come back in a different order each query, or rows are being inserted while they page and OFFSET is shifting the window. Both are fixed by a stable total sort, and the second is fixed properly by keyset pagination.