Paging a collection that keeps growing

The idea

Offset paging asks the database to skip a number of rows: give me four, starting after the first eight. That question only has a stable answer if nobody writes to the collection in between.

On a live feed they do. Two posts arrive between page one and page two, every existing row shifts down two places, and rows you already delivered slide back into the window. Delete something instead and the shift goes the other way — a row slips past the window and is never returned at all.

A cursor asks a different question: give me the four rows immediately after this one. That answer stays true no matter what happens above it, because it names a value in the sort order rather than a position in a list.

Watch it drift

Both strategies deliberately ignore the items that arrive at the head during the traversal — a client that started reading at 09:24 isn't expecting 09:31. You surface those by re-fetching the head, not by disturbing a scan in flight.

How it works

1. Choose a total, stable sort order. The order must be deterministic: a sort column plus a unique tiebreak. created_at DESC alone is not an order — rows sharing a second may come back in any sequence, and that alone will duplicate and skip rows at page boundaries.

2. Return the page, plus the sort key of its last row.

-- page 1, no cursor
SELECT id, created_at, body
FROM   posts
WHERE  feed_id = 42
ORDER  BY created_at DESC, id DESC
LIMIT  4;

-- last row of page 1 →  created_at = 09:21,  id = 121

3. Ask for the next page by value, not by position. Use a row-value comparison so the tiebreak is applied correctly:

-- page 2, keyset
SELECT id, created_at, body
FROM   posts
WHERE  feed_id = 42
  AND (created_at, id) < ('09:21', 121)   -- strict: excludes the anchor itself
ORDER  BY created_at DESC, id DESC
LIMIT  4;

Compare that with what offset paging does once three rows are inserted at the head:

page 1  OFFSET 0 LIMIT 4  → rows at index 0,1,2,3   = #124 #123 #122 #121
        + 3 inserts at the head: every row moves down 3
page 2  OFFSET 4 LIMIT 4  → rows at index 4,5,6,7   = #123 #122 #121 #120
                                                       ^^^^^^^^^^^^ already sent

8 rows delivered, 5 distinct, 3 repeats, net progress = 1 row.
Delete a row above the window instead and the shift is −1: index 3
is never read, and #120 is skipped for good.

4. Index to match the order exactly, or the database sorts the whole partition on every page:

CREATE INDEX posts_feed_created_id
    ON posts (feed_id, created_at DESC, id DESC);

Keyset paging then costs one index seek plus LIMIT rows — page 5,000 is as cheap as page 1. OFFSET 100000 LIMIT 20 makes the database produce and throw away 100,000 rows first.

5. Make the cursor opaque. Encode the state, then base64url it:

payload   {"v":1,"k":["2024-05-06T09:21:00Z",121],
           "s":"created_at:desc,id:desc","f":{"feed_id":42}}
token     base64url(payload)          (+ HMAC if forgery matters)

response  {"items":[...],
           "next_cursor":"eyJ2IjoxLCJrIjpbIjIw...",
           "has_more":true}

It must carry every sort key value including the tiebreak, the sort direction, the filter set it was minted under, and a version. Opaque because it is your implementation detail: the moment a client parses it, your sort key is frozen into their code forever. Validate it on arrival and return 400 if the filters or sort don't match — never silently return nonsense.

6. Give the "I need every row" customer a different door. Cursor paging over a mutating feed is eventually complete, not transactionally consistent. If someone needs a true snapshot, offer an export: an async bulk job that reads inside one repeatable-read transaction (or from a snapshot / replica at a fixed LSN) and hands back a file, or a changes since feed — keyset by (updated_at, id) with tombstones for deletes — so they can reconcile incrementally. A plain keyset scan by primary key is the cheapest full-table walk you can give them.

When to use it

The trade-off: a cursor buys stability and constant-time depth, and gives up random access. No page numbers, no "page 12 of 340", no cheap total count, and the sort key must be indexed and effectively immutable for the life of the traversal.

Watch out for

• A sort key that isn't unique. ORDER BY created_at DESC with a hundred rows in the same second: the database may order those rows differently on each query, so the page boundary lands somewhere new every time — a duplicate here, a lost row there. Always append a unique tiebreak and put it in the cursor.
• created_at < ? AND id < ? is not a row comparison. With the anchor ('09:21', 121), that predicate silently drops every older row whose id happens to be above 121 — potentially most of the table. Use (created_at, id) < ('09:21', 121), or spell out the disjunction: created_at < ? OR (created_at = ? AND id < ?).
• Sorting on a mutable column. Keyset on updated_at, score, or popularity and a row can move across the cursor while you page — seen twice, or never seen. Either sort on something immutable for the traversal, or accept it and document that clients should de-duplicate by id.
• Offset depth as a latency cliff. OFFSET 100000 reads 100,020 rows to return 20. It doesn't show up in the median; it shows up as a p99 that belongs to your most engaged users and your crawlers.
• Bolting total_count onto a cursor response. It's a second full scan of the same predicate, usually the most expensive part of the request, and it's stale the instant you compute it. Make it opt-in, approximate, or absent.

Worked example

"Design the timeline endpoint for a social product." Start with the shape: GET /v1/feeds/42/posts?limit=20 returns items and next_cursor. The order is created_at DESC, id DESC, backed by an index on (feed_id, created_at DESC, id DESC). The last row of page 1 is post 121 at 09:21, so the server mints a cursor over ["09:21", 121] together with the sort spec and feed_id, base64url-encodes it, and hands it back. Page 2 arrives as ?limit=20&after=eyJ2Ijox… and becomes (created_at, id) < ('09:21', 121) LIMIT 21 — one extra row, cheaply, to set has_more without a count.

Then say what happens under writes, because that's the question underneath the question: three posts land at 09:22 while the reader is on page 2. With offset they'd get post 121 back a third time and never reach 09:10; with the cursor the new posts sit above the anchor and page 2 is untouched. The client picks them up by refreshing the head — a separate before cursor built from the newest row it holds — which is also how you drive an unread badge without disturbing a scan in flight.

Finish with the escape hatch. When the interviewer says "our data partner needs the whole archive nightly", don't raise the offset ceiling. Offer GET /v1/exports: an async job that keyset-scans by primary key inside one repeatable-read transaction, writes a compressed file, and returns a URL — plus a ?updated_since= feed with tombstones for the days in between. That answer separates the read pattern from the API and is usually the thing they were listening for.

Check yourself