Pagination, Part 2: Tokens and Key-Based Cursors

This is part two of our Pagination series. Part 1 set up the model, an ordered sequence $x_{1} < \dots < x_{n}$ sliced by a function $f (θ)$ , and showed that page and offset slices address rows by position, which is exactly what moves when the data moves. Cursors fix that by addressing rows by key.

Opaque tokens

The simplest cursor is one the client never interprets. Each response carries a token $t^{'}$ that encodes, in whatever way the server likes, where the next slice starts:

f (t, s) \to ([x_{a}, \dots, x_{b}], t^{'})

The client relays $t^{'}$ back unchanged. The first request has no token at all, and the walk ends when the server stops handing one out, or on an empty page for a server that always populates the field:

t ← none
loop:
  rows, t' ← f(t, s)
  yield rows
  if rows is empty or t' is absent:  stop
  t ← t'

An opaque token chain: each response carries the token the next request relays back, until the server stops handing one out.

Because the token is opaque, the client cannot reason about it, and two things follow. First, the walk cannot be resumed from the middle by anything but a stored token, and a token whose server-side meaning has expired is a failed walk with no recovery. Second, the terminator has to be learned per endpoint: some servers omit the token on the last page, others return one that points past the end and answer it with an empty page. Both are fine, but a client that assumes the first and gets the second makes one extra request, while a client that assumes the second and gets the first stops one page early.

What the token usually encodes, though, is a key. That is why this method survives appends: a token meaning the rows after $k = 17$ keeps meaning that however many rows arrive above it.

Key-based cursors

Make the key explicit and the client can compute the cursor itself. A key-based cursor returns the first $s$ rows past a key value $c$ :

f (c, s) = [x : k (x) > c]_{1.. s}

and the next cursor is the largest key on the page, $c^{'} = max_{x \in rows} k (x)$ . Nothing here mentions a position, so an appended row, wherever the server sorts it, is either past the cursor and reachable or below it and already yielded:

c ← c₀                                   # the caller's lower bound, or none
loop:
  rows ← f(c, s)
  yield rows
  if rows is empty:  stop
  c ← max k(x) for x in rows

Taking the maximum rather than the last row's key matters: it makes the walk independent of the order rows arrive in within a page, and servers do not always sort a page the way their documentation says.

A key cursor: the slice is the first three rows whose key exceeds c = 8, and the next cursor is the largest key on the page. No position is involved.

For an id cursor (fromId, idLessThan, lastId) this is the whole story, because an id is unique per row. The key that is not unique is time, and most history endpoints are keyed by time.

The boundary problem

Suppose $k$ is a millisecond timestamp and several fills share one. The strict inequality above loses rows: a page that ends in the middle of a run of equal keys, followed by a request for $k > c$ , never sees the rest of the run.

Replace the strict inequality with an inclusive one, $k (x) \geq c$ , and the run is re-fetched. Now the client has to drop the rows it already yielded for that key, and it has to recognise them by identity, an id or the full row content, since their key is by construction the same. Call the rows already yielded at key $c$ the carried set $C$ :

Two rows share key 2 and the page boundary falls between them. A strict cursor skips x4 for good; an inclusive cursor re-fetches x3, drops it by identity, and reaches x4.

c ← c₀; C ← ∅
loop:
  rows ← f(c, s)                          # inclusive: k(x) ≥ c
  fresh ← rows − C                        # by identity
  yield fresh
  c' ← max k(x) for x in rows
  if |rows| < cap:               stop     # short page: nothing more past c
  if c' = c:                     raise    # a full page all at one key: the rest is unreachable
  c ← c'; C ← { x ∈ rows : k(x) = c' }

Two things this version needs that the strict one did not. It needs a cap, the true maximum rows per response, because a short page is the only way to tell "exhausted" from "the run at $c$ is longer than one page". And it needs to refuse the case where a full page shares one key: the server has no way to express the rest of the rows at $c$ , so the walk stops loudly rather than skip them. That case is rare (it needs more identical keys than the page can hold) but it is real on busy venues at millisecond resolution, and the alternative is a silent hole.

A server can make the whole problem disappear by exposing a secondary key, or by keying on a unique id and letting time be a filter. Most do not.

Four rows share key 2 and the cap is 3. The inclusive request from c = 2 returns three rows all at key 2, so the cursor cannot advance and x5 is unreachable. The walk raises instead of skipping it.

What survives mutation

Under append-only data, a key cursor walk has no duplicates and no gaps in either direction: a new row is either past $c$ or before it. Under arbitrary mutation two things can still go wrong. A row that changes between requests (an order whose status updates, a candle that is still open) defeats content-based identity, so a carried row appears to vanish and a walk that checks for that raises spuriously; prefer an id for the carried set wherever one exists. And a row deleted from the carried run simply does not come back, which is correct.

	$n$ fixed	append, either order	arbitrary mutation
no duplicates	yes	yes	yes, given identity
no gaps	yes	yes	yes, except rows deleted mid-walk

Compared with Part 1's table, the newest-first column has stopped being a problem. That is the entire reason to prefer a key cursor over an index.

Closing

A key cursor is a lower bound the client moves upward, one page at a time. Many APIs give the client two bounds, a start and an end, and truncate whatever falls between them to $s$ rows. Which end they truncate from is the subject of Part 3, and it is the least documented fact in this whole field.