Cursor Pagination and the Cost of Deep Offsets

Any list endpoint eventually meets a client that wants the next page. The obvious implementation is LIMIT with an OFFSET, and it is the wrong one for deep pages in two independent ways: the database does more work as the offset grows, and the result set shifts underneath the client as rows are inserted and deleted. Cursor pagination, usually implemented as a keyset predicate, fixes both. It also gives up random access, changes what a client can display, and pushes a surprising amount of design into the cursor value itself.

The distinction is between addressing a page by its position in a result set and addressing it by the last element already seen. Position is easy to express and expensive to resolve. The last element is a value that can be compared against an index, which makes the cost of the hundredth page roughly the cost of the first.

OFFSET is a scan with a discard

OFFSET n tells the database to produce the ordered result and discard the first n rows. The rows still have to be found, ordered, and materialised up to the offset point. With an index that matches the sort order, the engine can walk the index and skip entries, so the work is proportional to n plus the page size, but it is still n index entries touched. With a sort that no index supports, the engine must read the whole candidate set, sort it, and then discard n rows, which makes every page cost the same as the first but at the price of the full sort.

The second problem is worse than the cost. A page is defined against the state of the table at the moment the query runs, and nothing holds that state still between requests. If a row is inserted before the current offset, every later page shifts by one and the client sees a duplicate at the boundary. If a row is deleted before the offset, a row is skipped. Neither is a bug in the database; OFFSET has no notion of a stable window.

There are also hard limits. Offset values are integers, and a very large offset is both slow and easy to request, so a public endpoint needs a cap. Deep pagination is usually a sign that the client is exporting data, which is better served by a dedicated export with streaming or a stored job than by ten thousand page requests.

Keyset predicates need a total order

Keyset pagination replaces the offset with a predicate on the sort columns: return rows that come strictly after the last row of the previous page.

SELECT id, created_at, total
FROM orders
WHERE (created_at, id) < ($1, $2)
ORDER BY created_at DESC, id DESC
LIMIT 51;

The row comparison is lexicographic: created_at < $1, or created_at = $1 AND id < $2. PostgreSQL can use an index on (created_at DESC, id DESC) for this, and the seek lands directly on the boundary, so the cost of fetching the next page is the cost of an index seek plus the page size, independent of how deep the page is. Other engines support row constructors or require the predicate expanded by hand; the expansion is semantically equivalent and may be what the optimiser needs to see.

The tie-breaker is not optional. A sort on created_at alone is not a total order when two rows share a timestamp, and the database is free to return tied rows in any order, including a different order between two executions. Page boundaries then become nondeterministic, and a row can appear twice or vanish. Appending the primary key gives a unique total order, at the cost of forcing the sort to include that column. An index on (created_at, id) serves the common case; if the API also offers sorting by total, a second index on (total, id) is required, and the cursor must record which sort was used.

Ascending and descending pages need mirrored comparisons. For a descending sort the predicate is (sort_key, id) < (last_key, last_id); for an ascending sort it is >. Reversing the order of the result set for a “previous” link means running the query with the opposite comparison and the opposite ORDER BY, then reversing the rows in the application before returning them, because the client expects the page in sort order.

What an opaque cursor has to carry

A cursor is a token that encodes the position. It should be opaque to clients, which discourages hand-construction and allows the server to change the format. Base64url encoding of a compact JSON or binary payload is the usual shape, and a signature or MAC over the payload prevents clients from forging positions that bypass authorization filters.

The minimum payload is the last row’s sort values, the sort direction, and some binding to the query parameters that produced it. The binding matters because a client that takes a cursor from ?status=open and applies it to ?status=closed produces a boundary that means nothing in the new result set. Hashing the normalised filter set and rejecting a cursor whose hash does not match turns a silent wrong answer into a 400, and the error model should name the mismatch rather than reporting a generic bad request. The cursor may also carry an expiry timestamp, which bounds the lifetime of any snapshot semantics and prevents an old cursor from being replayed after a schema change.

Cursor size is a real constraint. URL handling tooling often assumes a ceiling in the low thousands of characters, a legacy browser limit that some proxies also enforce, and a signed token carrying several string sort values can approach it. If the cursor grows past a few hundred bytes, storing it server-side and returning a short random identifier is worth considering, at the cost of a lookup and a state store.

Page size belongs in the request, not the cursor, but the response should echo the effective size. A server that caps page size at some maximum must apply the cap before computing the next boundary, or the client will stitch pages together with a gap. Fetching one extra row is the standard trick for detecting whether another page exists without a COUNT query: request LIMIT 51 for a page size of 50, return 50 rows, and set the next cursor only if the fifty-first row was present.

Consistent pages versus stable pages

A keyset cursor gives stable page boundaries under insertion, but not a snapshot. If a row is inserted with a sort value before the cursor position, it will never appear in any subsequent page, because the client has already passed that position. If a row is updated so its sort value moves ahead of the cursor, it appears twice. Keyset pagination guarantees no duplicates for rows whose sort values do not change during the traversal, and no skips for rows that existed at the start, provided no row moves behind the cursor.

Applications that need a fixed view, such as exports or reconciliation reports, need snapshot isolation: a transaction held open for the traversal, a repeatable-read snapshot, or a materialised result keyed by a job identifier. Each has a cost. A long-running transaction blocks vacuum in PostgreSQL and pins old row versions, so the retention window of the snapshot is a design parameter, not an implementation detail. A materialised result costs storage proportional to the result size and requires a cleanup policy.

The middle ground, used widely, is a cursor that includes a high-water mark: the maximum sort value at the time the first page was requested. Every page then filters on sort_key <= high_water, which excludes later insertions and gives a stable set for rows that are not deleted or re-sorted. The high-water mark is cheap, requires no transaction, and does not protect against deletions, which is usually acceptable for a feed and not acceptable for a ledger.

Contract details that clients depend on

The response should provide the next cursor explicitly rather than expecting the client to construct one, and should signal the end with an absent field or an explicit null rather than an empty string, so that a client cannot loop forever on a falsy-but-present value. The cursor should be treated as invalid when the sort parameters change, and the server should document that the ordering is not stable across cursor generations.

Random access is gone. A client that wants page 7 must walk six cursors, and a UI that shows page numbers cannot be built honestly on top of keyset pagination. Offset pagination remains reasonable for small, slowly changing result sets, for administrative interfaces where jumping to the last page is a requirement, and for cases where the total size is bounded by a filter. Many APIs offer both: offset for bounded collections, cursors for feeds.

HTTP has a standard way to express the navigation links, in RFC 8288. A response can carry Link: <https://api.example.com/orders?cursor=abc>; rel="next" alongside the body, which lets generic clients paginate without knowing the JSON shape. The same header supports rel="prev" and rel="first", and the next relation is defined for exactly this purpose. Emitting it costs nothing and makes the endpoint usable by tooling that never learned the API’s cursor field name.

The remaining sharp edge is total counts. COUNT(*) over a large filtered set is a full scan, and including it in every list response multiplies the cost of the cheapest request. Approximate counts, counts capped at some threshold, or a separate endpoint that reports progress are the usual compromises. A response that includes an exact total for an unbounded collection is either expensive or wrong, and often both.

Changing a default sort order is a breaking change for every outstanding cursor, which is why the sort and direction belong inside the token and are checked on use. The same reasoning applies to schema evolution: a field that a cursor depends on cannot be removed without invalidating the cursors that encode it, and an unrecognised cursor should produce a clear error rather than a page from a different query.