Pagination That Doesn’t Fall Apart at Page 50,000: Keyset Cursors Done Right

Posted on

Almost every API starts its pagination life with LIMIT 20 OFFSET 40. It’s the pattern every ORM hands you, it supports “jump to page 3”, and it works fine on the demo dataset. Then the table grows to ten million rows, someone opens page 500, and the database is asked to walk and discard 9,980 rows before returning twenty. Offset pagination is the rare anti-pattern that is simultaneously a performance problem, a correctness problem, and a UX problem — and the fix has been standard SQL for decades.

Keyset (cursor) pagination replaces “skip N rows” with “start after this value.” It turns page fetches into indexed range scans that cost the same at page 1 and page 50,000, it stops rows from shuffling between pages when inserts land mid-scroll, and it’s the mechanism behind nearly every infinite-scroll feed you use. This post covers why offset degrades, how to build cursors that survive multi-column sorts and ties, how to encode them safely for API responses, and where offset still earns its keep.

Why OFFSET punishes depth

OFFSET has exactly one parameter: a row count. The SQL standard defines its semantics as “sort the rows, then drop the first N.” The database cannot seek past them — it must produce and discard all N rows before emitting the ones you asked for. With an index, that means traversing N index entries; without one, it can be worse. The cost grows linearly with page depth, so doubling the offset doubles the work regardless of page size.

There’s a second, quieter failure: page drift. Row numbers are assigned from scratch on every query. If a new row is inserted between two page fetches — and on any live table, one will — every subsequent offset shifts by one. Users see the row that ended page 1 appear again at the top of page 2, or rows silently vanish. Any API that pages by “row number” inherits these anomalies, because a bare count carries no information about which rows were already shown.

The keyset recipe

Keyset pagination uses the values of the last row on the previous page as a lower bound for the next query. The simplest version, on a single unique sortable column:

-- page 1
SELECT id, title, created_at
  FROM posts
 ORDER BY id DESC
 LIMIT 20;

-- next page: pass the last id from page 1
SELECT id, title, created_at
  FROM posts
 WHERE id < $1
 ORDER BY id DESC
 LIMIT 20;

The WHERE id < $1 predicate turns the query into an index range scan: the database seeks directly to the position after the last-seen value and reads twenty rows. Cost is constant no matter how deep you are — there is nothing to skip. Inserts before the cursor don’t shift anything, because the cursor names a value, not a position. On PostgreSQL, a matching B-tree index makes each page a 20-row index scan; on MySQL and SQL Server the same recipe works unchanged.

Measured on real hardware, the gap is not subtle. Community benchmarks on million-row tables routinely show 10–20× speedups at deep pages — a page 50,000 request that takes ~700 ms with offset completes in tens of milliseconds with a keyset seek, and the keyset time doesn’t move as depth grows.

Sorting by something other than the primary key

Real feeds sort by created_at DESC, score DESC, or similar — and those columns are not unique. A naive WHERE created_at < $last breaks on ties: if fifty rows share the same timestamp, the predicate skips all of them, losing rows that were never shown. The fix is a composite cursor: append a unique tiebreaker and express the filter as a row-wise comparison.

SELECT id, title, created_at
  FROM posts
 ORDER BY created_at DESC, id DESC
 LIMIT 20;

-- next page, using (created_at, id) of the last returned row
SELECT id, title, created_at
  FROM posts
 WHERE (created_at, id) < ($1, $2)
 ORDER BY created_at DESC, id DESC
 LIMIT 20;

The row-wise form (created_at, id) < ($1, $2) is SQL-standard row-value comparison: it means “sorts strictly before the tuple,” which is exactly the keyset condition. PostgreSQL supports row-value comparisons natively and will use an index on (created_at, id) for them. A few practical notes:

  • The ORDER BY columns and the cursor columns must correspond exactly, including direction. If you sort created_at DESC, id ASC, the predicate mixes operators: (created_at < $1) OR (created_at = $1 AND id > $2).
  • The tiebreaker must be unique. The primary key is the default choice; a random UUIDv4 works but scatters index locality — an identity or time-ordered ID keeps range scans contiguous.
  • The index must cover (sort_col, tiebreaker) in the same order as the ORDER BY, or each page degrades to a sort over the filtered set.

One property worth knowing: a composite keyset filter is expressible as a pure B-tree range over the concatenated key. The seek method works on any engine that can use composite indexes for range predicates — which is all of them — even where row-value syntax needs expanding to the equivalent boolean form:

WHERE created_at < $1
   OR (created_at = $1 AND id < $2)

Encoding cursors for an API

Handing raw SQL values back to clients leaks schema details and invites tampering with the predicate. Production APIs encode the cursor. A common, adequate approach: JSON payload, base64-encoded, with an HMAC so clients can’t forge values. In Go:

package cursor

import (
	"crypto/hmac"
	"crypto/sha256"
	"encoding/base64"
	"encoding/json"
	"errors"
	"time"
)

var secret = []byte("replace-with-managed-secret")

type Cursor struct {
	CreatedAt time.Time `json:"created_at"`
	ID        int64     `json:"id"`
}

func Encode(c Cursor) (string, error) {
	payload, err := json.Marshal(c)
	if err != nil {
		return "", err
	}
	mac := hmac.New(sha256.New, secret)
	mac.Write(payload)
	sig := mac.Sum(nil)
	raw := make([]byte, 0, 16+len(payload))
	raw = append(raw, sig[:16]...) // truncated MAC: 128 bits is plenty here
	raw = append(raw, payload...)
	return base64.RawURLEncoding.EncodeToString(raw), nil
}

func Decode(s string) (Cursor, error) {
	var c Cursor
	raw, err := base64.RawURLEncoding.DecodeString(s)
	if err != nil {
		return c, errors.New("invalid cursor")
	}
	if len(raw) < 16 {
		return c, errors.New("invalid cursor")
	}
	sig, payload := raw[:16], raw[16:]
	mac := hmac.New(sha256.New, secret)
	mac.Write(payload)
	if !hmac.Equal(sig, mac.Sum(nil)[:16]) {
		return c, errors.New("invalid cursor")
	}
	if err := json.Unmarshal(payload, &c); err != nil {
		return c, errors.New("invalid cursor")
	}
	return c, nil
}

The response envelope follows the same convention used by relay-style GraphQL APIs: an opaque cursor per item, plus one for the page boundary:

{
  "items": [ ... 20 posts ... ],
  "next_cursor": "eyJjcmVhdGVkX2F0IjoiMjAyNi0xMC0yNlQwOTozMDowMFoiLCJpZCI6OTgxMjM0fQ",
  "has_more": true
}

Design choices that matter in review: the cursor must carry every ORDER BY column (plus tiebreaker), and ideally the sort direction too, so a client can’t request page 2 of a feed sorted one way with a cursor minted for another. Some teams sign the whole query context — sort key, direction, filter — into the cursor to make it self-validating.

Correctness under concurrent writes

Keyset pagination’s stability guarantee comes from the filter being value-based, but there are edge cases worth naming:

  • Inserts after the cursor (newer than the last-seen value, in a descending feed) never disturb the current scroll — exactly the property offset can’t offer.
  • Updates to sort columns can move a row across the cursor boundary. A post whose created_at is edited may reappear once. If sort keys are immutable (created timestamps, auto-increment ids), this entire class disappears.
  • Deletes simply shrink a page; the next cursor still comes from the last row actually returned, so nothing skips.
  • Transaction visibility: each page runs in its own query/snapshot. If you need a frozen view of the whole result set (exports, consistent batches), that’s a job for a single query with a repeatable-read snapshot or a materialized cut — not pagination.

When OFFSET is still fine

Keyset pagination has one real cost: no random access. “Jump to page 7” requires walking pages 1–6, because “page 7” has no meaning without knowing where pages 1–6 end — and where they end changes as data changes. Consequences:

  • Admin back-offices with page-number links and modest tables: offsets are fine. At a few thousand rows, the linear scan is imperceptible.
  • Total counts: SELECT count(*) on a large table is its own scan. Cursor APIs typically return has_more (fetch limit+1 rows and check) instead of a total — a deliberate UX shift, not a limitation to apologize for.
  • Bidirectional scroll works by minting a second, reversed cursor (the first row of the page, with flipped comparison operators) — cheap to add if the client needs a “back” affordance.

The migration path is also low-risk: keep the offset endpoint for existing clients, add ?cursor= support to the same route, and return next_cursor in every response. New clients use cursors; old ones age out.

Keyset pagination is one of those techniques that changes a problem from “we should optimize this someday” to “this can’t get slow no matter how big the table gets.” The composite-cursor pattern plus one matching index covers essentially every list endpoint: constant cost at any depth, stable pages under concurrent inserts, and an opaque token that fits cleanly into API contracts. The next time an endpoint accepts offset=, ask what happens at row ten million — then ship the cursor.

Leave a Reply

Your email address will not be published. Required fields are marked *