Concrete scenario
An orders API must browse deep pages while new orders arrive.
Mechanics
Use a unique deterministic order such as (created_at,id) and encode the last tuple in an opaque cursor. The index seek costs roughly O(log N) plus the page scan; work is largely independent of page depth, not literally constant.
Failure mode
Updating a sort key or deleting unseen rows changes later results, and a cursor without all tie-breakers can skip or duplicate records. Arbitrary page-number jumps are not directly available.
Trade-off
Keyset pagination gives stable deep-page performance and handles inserts ahead of the cursor well. Offset pagination is simpler for small data and random page jumps but scans and discards deeper prefixes.
Worked example: page 5,000 of an orders feed
Consider a table of 100M orders with 20 rows per page.
- OFFSET:
ORDER BY created_at DESC LIMIT 20 OFFSET 100000must walk and discard 100,000 index entries (and often fetch their heap rows) to return 20. Page 1 takes about 1 ms and page 5,000 might take 100-300 ms. A crawler walking every page does O(n^2) total work. - Keyset:
WHERE (created_at, id) < ('2026-09-01 10:00:00', 98231) ORDER BY created_at DESC, id DESC LIMIT 20with index(created_at DESC, id DESC)seeks directly. That is about 1 ms at any depth.
Portable form (when row-value comparison is not indexed)
WHERE created_at < :ts OR (created_at = :ts AND id < :id)
PostgreSQL uses the index for the row-value form (a, b) < (x, y) directly. MySQL historically optimized it poorly, so the OR form is safer there.
Comparison
| Aspect | Offset | Keyset (cursor) |
|---|---|---|
| Cost of page k | O(k x pagesize) | O(log N + pagesize) |
| Jump to page 57 | Yes | No (only next/previous, or from a known key) |
| Total count and page numbers | Easy (but COUNT(*) is itself expensive) | Usually omitted |
| Inserts during browsing | Rows shift, causing duplicates or skips | Stable: new rows ahead of the cursor do not affect later pages |
| Sort by arbitrary column | Any | Needs a matching index plus a unique tie-breaker |
| Sharded data | Very expensive (each shard returns offset + limit rows) | Each shard seeks, then merge top-k |
Cursor design
- Encode
{"ts": "2026-09-01T10:00:00Z", "id": 98231, "dir": "next"}as base64url and optionally sign it with an HMAC. - Include the sort and filter parameters in the cursor, or reject a cursor used with different filters.
- Return
next_cursor: nullwhen fewer thanlimitrows come back.
Who uses it: the Stripe API (starting_after), the Slack API (next_cursor), GitHub GraphQL (Relay connection cursors), and Twitter/X timelines (max_id and since_id, where Snowflake IDs double as cursors).