Pagination with cursors

01The intuition

The problem it solves

A teacher reads out exam results to a hall of 2,000 students, 50 at a time: "names 1 to 50", then "51 to 100". Halfway through, a late result is added near the top of the list. Everyone after it shifts down by one, and the student who was 100th is now 101st and gets read out twice, while the one who was 51st is skipped. Reading "the next 50 after Rao" instead of "numbers 51 to 100" would have avoided both mistakes.

APIs that return big lists have the same choice. Page numbers (offset pagination) break the moment the list changes underneath, and they get slow deep into the list. A cursor says "continue after this exact item", which stays correct while rows are inserted and deleted and costs the same on page 1 and page 10,000.

Build it one piece at a time

Step 1: offset pagination, the naive way. GET /comments?page=3&size=50 becomes SELECT … ORDER BY created_at DESC LIMIT 50 OFFSET 100. The database must find and discard 100 rows to return 50.

Step 2: see it break. Between page 1 and page 2 a new comment arrives at the top. Every row shifts by one, so the last comment of page 1 appears again at the start of page 2, and on deletion a comment vanishes between pages.

Step 3: the cursor. The server returns the sort key of the last item it sent, usually encoded (base64 of created_at|id) so clients treat it as opaque. The next request sends it back and the query becomes a range: WHERE (created_at, id) < (?, ?) ORDER BY created_at DESC, id DESC LIMIT 50. With an index on (created_at, id) the database jumps straight to the right place.

Step 4: make the key unique. Many comments can share a timestamp, so the cursor includes a tie-breaker, the id. Without it, items with equal timestamps straddling a page boundary are skipped or repeated.

Step 5: handle the end and the extras. Return next_cursor: null when there is no more. Allow a limit up to a cap (say 100). For two-way scrolling return a prev_cursor too. For a feed that is assembled from many shards, the cursor can carry one position per shard.

Why it works, with the numbers

Offset cost grows with depth; cursor cost does not. With a B-tree index, finding the start of page k of size s costs:

offset: O(k × s) rows scanned and discarded; cursor: O(log n) to seek, then s rows read

Page 2,000 of 50 under offset scans 100,000 rows to return 50; under a cursor it reads about 20 index nodes and 50 rows. The guarantee of a cursor over a stable sort key is "no item is repeated or skipped as long as the item it points at still exists and the sort key never changes". Its failure modes: the cursor item is deleted (keep the key, not the row, so the range query still works), the sort key is editable (sort by something immutable), and a client that stores a cursor for a week on a list whose ordering rule changed (version the cursor format).

The trade-off you must say out loud

Cursors give up random access: there is no "jump to page 37" and no total count without a separate query. Say that out loud and say why it is fine for feeds, comments and logs, where nobody jumps to page 37. The interviewer may ask how a cursor works over a ranked feed whose order is recomputed; the answer is to freeze a snapshot (a materialised list or a generation number) and page through that.

Where it shows up in the 100 Google problems

• Design a comments service: a hot post gains comments every second; only cursor pagination keeps the thread readable while it grows.
• Visualize 100 million points on a map: tiles are paged by a cursor so the browser streams a viewport's points without holding them all.
• Design a social news feed: the feed cursor is a position in a precomputed timeline, not a page number.

02Used in these problems

• Design a comments service
• Visualize 100 million points on a map