Keyset Pagination for Web Applications

## Part 1: Why Do We Need Keyset Pagination in Web Applications? Every list in a web application is a promise to deliver a large answer in small pieces. The database, however, keeps no memory of the pieces it has already handed you — by default each page request is a fresh question, answered from the beginning of the result set. `LIMIT 20 OFFSET 10000` does not mean "give me page 501"; it means "produce the first 10,020 rows in order, throw away 10,000 of them, and keep the rest." Keyset pagination — the practice of paginating by *where you stopped* rather than by *how many rows you skipped* — is where we stop paying for the pages the reader has already read. In this section we'll talk about how offset pagination, bigger pages on faster hardware, and keyset cursors differ — and why remembering the last row instead of counting from the first is what keeps deep pages as fast as shallow ones. ### Offset Pagination: Intuition The simplest paging strategy is arithmetic. The database sorts the matching rows, counts forward to where the page begins, and returns the next slice: > Query → sort all matching rows → discard the first m → return the next k This works when readers stay near the front. But it assumes: - Readers rarely go deep — page 2 is common, page 500 is theoretical. - The result set is stable between requests, so page boundaries keep meaning the same thing. - Discarding m rows is cheap enough at your request rate. For a settings screen with forty rows, these assumptions hold comfortably. For an activity feed, an infinite-scroll mobile client, or a partner integration walking an export endpoint, none of them do. ### Bigger Pages and More Replicas: Guiding with Brute Force An obvious fix is to make the problem smaller by making the machines bigger: raise the page size, add replicas, spread the reads. If page 501 is slow, why not serve fewer, fatter pages from more hardware? > Same discarded rows × more machines → the same wasted work, in parallel This approach buys headroom, but it breaks down quickly: - Each request still materializes and discards m rows — you multiplied capacity, not efficiency; page 501 is exactly as expensive as before. - Larger pages hide the symptom by reducing request count while making each request heavier and each payload slower to render. - A result set that shifts between requests still duplicates and drops rows, and no amount of hardware makes an unstable boundary correct. Page size and replicas are throughput tools, not depth tools. The question becomes: why is page 501 producing pages 1 through 500 again? ### Keyset Cursors: Remember Where You Stopped A keyset cursor [2] answers that question by carrying the boundary in the request. Instead of counting from the front, the client sends back the sort key of the last row it saw, and the database: 1. **Anchor**: interpret the cursor as a position in the sort order — the tuple of key values the previous page ended on. 2. **Seek**: descend the index to that position and read forward k rows, never touching what came before [4]. This approach: - Replaces O(m + k) skipping with O(log N + k) seeking — page 500 costs what page 1 costs. - Rides the same index that already satisfies the ORDER BY, so no sort node and no discarded rows appear in the plan. - Stays correct while rows are inserted and deleted, because the boundary is a value in the data rather than an ordinal that shifts underneath it. ### The Common Feeling: "Isn't This Just WHERE id > ?" Many developers (myself included, at first) find keyset pagination anticlimactic. If you squint, it looks like we just: - Replaced `OFFSET 10000` with `WHERE id > 10000`. - Asked the client to hold on to one number for us. Isn't that just a slightly awkward `OFFSET`? In practice, yes — that is exactly the right mental model. But conceptually, there are two crucial differences: 1. **Unit of state:** - Offset: the boundary is an ordinal — "row number 10,000" — which points somewhere different every time the table changes. - Keyset: the boundary is a *value* that exists in the data, so it identifies the same place before and after a write. 2. **Cost contract:** - An offset query's cost is set by how far into the result set you are. - A keyset query's cost is set by how many rows you *ask for* — and you pay for that by giving up random page access, which is now an explicit trade. It's a subtle but important shift: from paying for the pages you skipped to paying for the page you asked for. ### Why the Distinction Matters in Real Applications This difference is especially sharp for the endless lists of modern products: activity feeds, audit logs, message history, and any endpoint an integration reads from end to end. - **Offset setup:** A feed of 10 million events. Serving page 501 counts through 10,000 rows to return 20 — and a client that scrolls to the end makes the database discard millions of rows over one session. - **Keyset setup:** A cursor holding (created_at, id) descends the index, lands exactly where the last page ended, and reads 20 entries. Page 501 and page 1 issue the same amount of work. Formally, the row-touch costs compare as: > cost_offset ≈ log_B(N) + m + k vs cost_keyset ≈ log_B(N) + k Where N is the result-set size, B is the index's branching factor, m is the offset, and k is the page size. For m = 10⁴ and k = 20, that is roughly 10,020 rows touched versus about 20 — and the gap widens with every page the reader turns. This is why deep pagination shows up in slow-query logs as a curve rather than a constant: the same endpoint gets slower the longer someone stays engaged with it. ### Advanced Variants: Beyond the Single-Column Cursor When the sort key is not unique, or when clients need to page backwards, a single-column cursor stops being enough. Richer designs address this: - **Composite cursors**: compare the whole sort tuple at once — `(created_at, id) < (:ts, :id)` — so rows sharing a timestamp still have a deterministic order [5]. - **Opaque cursors**: encode the tuple into one base64 token, so clients treat it as a position rather than as a queryable field [6]. - **Bidirectional cursors**: expose both ends of a page, so the client can seek forward or backward without ever reintroducing an offset [6]. The guidance is structural: the cursor is designed around the sort order, not around the primary key. ### Intuition - Offset: "Count from the beginning every time." - Bigger pages: "Count from the beginning, just less often." - Keyset: "Keep a finger in the book — the last line you read is the bookmark." ### Conclusion Keyset pagination can feel, at first, like a clumsier `OFFSET` that leaks implementation details into the API. But the shift in cost contract — paying for the page instead of the prefix — is what separates it from buying faster hardware to do the same wasted work. For short, stable lists, offsets are sufficient. For deep, growing result sets, cursors keep latency flat. For endpoints that get read exhaustively, composite and opaque cursors show the full potential: the database seeks once per page and never revisits what the reader already saw. That's why keyset pagination — in one form or another — is the default in the pagination contracts of APIs built to be walked to the end [7][8]. ## Part 2: How to Design Correct Keyset Cursors This is a recap of my working notes from migrating a handful of offset-based list endpoints onto cursors, cross-checked against Markus Winand's treatment of paging [1][2] and the GraphQL cursor connections specification [6]. If you find this interesting, I highly recommend going through both. ### Pagination Setup in the API Context - Result set (R): the rows matching the filter, in a defined order - Sort key (K): the columns in the ORDER BY that define that order - Tie-breaker (t): a unique column appended to K so no two rows can compare equal - Cursor (c): the encoded key values of the last row delivered - Page size (k): how many rows one request returns - Index (I): the ordered structure that turns the cursor into a seek instead of a scan [4] Unlike offset paging, a cursor moves the page boundary out of the query and into the client's hands — the request carries its own position, which is precisely what lets the database skip the prefix instead of producing it. ### Naive Cursors: Paginate on the Timestamp Alone The simplest cursor is the obvious one: remember the last row's `created_at` and ask for everything older. The implied contract is: > next page = WHERE created_at < :last_seen ORDER BY created_at DESC LIMIT k Interpretation: hope that timestamps are unique enough to serve as positions. - If the sort key is genuinely unique (a monotonic id, a sequence), this works. - If several rows can share a value — which is every timestamp column under concurrent writes — this loses data silently. This is like bookmarking a book by the date printed on the page and hoping no two pages share it. The problems: - **Ties drop rows**: with `<`, every row sharing the boundary timestamp is skipped; with `<=`, those rows are delivered twice. Neither is correct. - **Unstable order**: two requests may order tied rows differently, so a row can appear on page 3 and again on page 4 without anything having been written. - **Leaked semantics**: a raw timestamp in the API invites clients to construct cursors themselves, which freezes your sort order into your public contract. As I noted while migrating those endpoints: a cursor is only as correct as the total order behind it. If the ORDER BY has ties, the pagination has bugs — they are just waiting for enough traffic to surface. ### Tuple-Driven Cursors: Designing from the Sort Order To paginate correctly, start from the sort order and derive the cursor. The design rules: - **Total order or nothing**: append a unique tie-breaker to every sort key, so (created_at, id) admits exactly one valid ordering [5]. - **Compare the tuple, not the columns**: `(a, b) < (:a, :b)` is one comparison the optimizer understands; the hand-expanded `a < :a OR (a = :a AND b < :b)` form is easy to get subtly wrong. - **Index the cursor's shape**: the index must match the sort tuple, direction included, or the "seek" quietly degrades into a sort over the whole result set. - **Encode, don't expose**: hand back one opaque token, so the sort key stays an implementation detail you can still change. Intuition: don't paginate rows; paginate positions in a total order. The cursor should read like the ORDER BY it came from. ### The Cursor Design Algorithm Algorithm: Keyset Cursor Design 1. Write down the endpoint's sort order as the client experiences it — direction included 2. Append a unique tie-breaker to make that order total; confirm no two rows can compare equal 3. Define the cursor as the sort tuple of the last delivered row, and nothing else 4. Build the query as a single tuple comparison plus LIMIT k, keeping the ORDER BY identical to step 2 5. Create or confirm an index on the full sort tuple, in the same direction 6. Verify with EXPLAIN that the plan is an index scan with no sort node and no discarded rows 7. Encode the cursor opaquely, and validate it on the way back in — a cursor is untrusted client input #### Key insights: - Step 2: The tie-breaker is not a detail — it is the difference between pagination that works and pagination that drops rows under concurrency. - Step 4: Direction must agree across the comparison, the ORDER BY, and the index; one mismatched DESC turns a seek back into a sort. - Step 7: Cursors round-trip through the client, so decode defensively — a malformed cursor is a 400, never an unbounded query. ### The Role of Tie-Breakers and Page Size In cursor design, the tie-breaker and the page size each serve distinct roles in balancing correctness against cost: **Tie-Breakers** - Defined by uniqueness: appending a primary key or sequence makes the order total, so every row has exactly one position. - Used to decide where a page ends — without one, "the last row" is ambiguous whenever values repeat. - Intuition: "A bookmark has to point between two pages, not into a stack of identical ones." **Page Size** - Typically 20-100 rows for interactive lists, with a hard cap for machine consumers. - Why? Because k sets both the per-request work and the number of round trips a full walk costs — and it is the one parameter a client can inflate. - Intuition: "Small enough that one page is cheap, large enough that reading everything isn't a denial-of-service on yourself." **Why Both Matter** - A total order ensures every row is delivered exactly once; a bounded page size ensures every request costs about the same. - A cursor without a tie-breaker is worse than an offset: it is fast and quietly wrong, which takes far longer to discover. - Too small a page turns a full walk into thousands of round trips; too large a page recreates the latency spikes you migrated away from. ### Analogy to Indexing Indexing (see Database Indexing for Web Applications) also removes wasted row-touches, but the two work on different halves of the problem: - **Indexing**: makes finding a position cheap — the database seeks instead of scanning. - **Keyset pagination**: makes sure you only need to find a position once per page, instead of re-walking the prefix. In practice they are inseparable: a cursor without a matching index is still a scan, and no index can rescue a query whose plan is defined by how many rows it throws away. ### TL;DR: - Tie-Breakers: Turn an ambiguous boundary into a real position → append a unique column to every sort key. - Page Size: Bounds per-request cost and total round trips → a comfortable default for humans, a hard cap for machines. ### A Toy Example: The Activity Feed Let's walk through a simple toy environment: a 10-million-row events table, and the feed endpoint an infinite-scroll client walks to the end. #### Schema and the Offset Version ```sql CREATE TABLE events ( id bigint PRIMARY KEY, actor_id bigint NOT NULL, kind text NOT NULL, created_at timestamptz NOT NULL ); -- Page 501, the offset way: SELECT id, actor_id, kind, created_at FROM events WHERE actor_id = 42 ORDER BY created_at DESC, id DESC LIMIT 20 OFFSET 10000; ``` #### The Keyset Version The cursor is the sort tuple of the last row delivered, compared as a tuple: ```sql CREATE INDEX idx_events_feed ON events (actor_id, created_at DESC, id DESC); -- The same page, anchored instead of counted: SELECT id, actor_id, kind, created_at FROM events WHERE actor_id = 42 AND (created_at, id) < (:cursor_created_at, :cursor_id) ORDER BY created_at DESC, id DESC LIMIT 20; ``` #### Encoding the Cursor ```python import base64, json def encode(row): payload = {"t": row["created_at"].isoformat(), "i": row["id"]} return base64.urlsafe_b64encode(json.dumps(payload).encode()).decode() def decode(cursor): payload = json.loads(base64.urlsafe_b64decode(cursor)) return payload["t"], payload["i"] # validate types, then bind as parameters ``` #### Verifying the Plan ```sql EXPLAIN (ANALYZE, BUFFERS) ; -- Offset: Index Scan using idx_events_feed -- rows=10,020 fetched, 10,000 discarded, ~48 ms -- Keyset: Index Scan using idx_events_feed -- rows=20 fetched, 0 discarded, ~0.3 ms ``` The plan tells the whole story: same rows returned, same index, two orders of magnitude less work — and unlike the offset version, the keyset numbers do not change on page 5,000. ### Conclusions - Cursor shape vs correctness: A cursor over a total order delivers every row exactly once; a cursor over a non-unique key is fast and silently lossy. - Plan verification: EXPLAIN is the contract — the target is an index scan with zero discarded rows, at any depth. - Trade-offs: Cursors give up random page access and cheap total counts. If a screen genuinely needs "jump to page 47," offset is the honest answer there. - Scaling: The toy example is one feed, but production pagination involves cursor versioning, per-client page caps, stable ordering across replicas, and deciding what a cursor means once its anchor row is deleted. Faster machines and fatter pages only make the same discarded rows arrive sooner. A cursor removes the discarding itself, at every depth at once. While toy demos like "the activity feed" are simple, the mechanics mirror how cursor-based pagination keeps real API endpoints answering in milliseconds whether the client is on page 1 or page 50,000. ## References 1. Winand, M. "SQL Performance Explained: Everything Developers Need to Know about SQL Performance." (2012). 2. Winand, M. "Use The Index, Luke!: Paging Through Results." (2011). 3. Selinger, P., et al. "Access Path Selection in a Relational Database Management System." SIGMOD (1979). 4. Graefe, G. "Modern B-Tree Techniques." Foundations and Trends in Databases (2011). 5. PostgreSQL Global Development Group. "PostgreSQL Documentation: Row and Array Comparisons." (2024). 6. GraphQL Foundation. "GraphQL Cursor Connections Specification." (2018). 7. Stripe. "Stripe API Reference: Pagination." (2024). 8. Slack. "Slack Web API: Pagination." (2024).