How Do You Design a Stable Cursor Pagination API?

Problem and Scope

A multi-tenant order service uses PostgreSQL. Its orders table contains 200 million rows and receives continuous inserts and status changes. An operations console filters orders by tenant and status, always sorts by createdat DESC, id DESC, and returns at most 50 rows per page. Both createdat and id are non-null and immutable after creation; id is unique. The product needs next-page and previous-page navigation but does not require a direct jump to page 500.

Design the pagination API, cursor payload, queries, and index. The design must handle identical creation timestamps, deep pagination, inserts and deletes between requests, changing status membership, cursor tampering, and navigation in both directions. It must also distinguish live traversal from a fixed snapshot.

The 200 million rows and 50-row page size are interview assumptions. The core skill is translating API semantics into a database access path, concurrency boundary, and verification plan, so this is a backend question. Cross-region replication, sharding, and client-side list state are outside the first-round scope.

What the Interviewer Is Evaluating

The first signal is whether the candidate defines consistency before choosing an algorithm. “No duplicates or omissions” needs an object: does it mean avoiding the shifts caused by offset pagination, or must an entire browsing session behave like one database snapshot? A normal cursor can resume after an ordering boundary; it does not freeze deletes, status changes, or other filter fields.

The second signal is a total order. If the query sorts only by created_at, several orders may tie and the database may arrange them arbitrarily. A unique id as the second sort key, with both values in the cursor, precisely identifies the position after the previous page's last row.

The third signal is whether the query, index, and cursor implement the same order. tenantid and status are equality filters. createdat and id form the range boundary and sort order. A candidate B-tree index is therefore (tenantid, status, createdat DESC, id DESC). Replacing the word “offset” with “cursor” is incomplete without the comparison predicate, index, and reverse query.

Finally, the interviewer should hear a concrete contract and test plan. A strong answer binds filters and authorization scope into a signed cursor, caps the page size, and tests concurrent inserts, deletion of the boundary row, tied timestamps, and forward/backward round trips. It also keeps offset pagination as a valid option for small, stable data sets that require page-number jumps instead of treating one technique as universally correct.

Clarifying Questions

• Is this a live list or a fixed snapshot? A live list may reflect some changes on later pages. A fixed snapshot requires the traversal to see one set, usually through versioned data, a materialized result, or a snapshot mechanism that survives across requests. The costs and expiry policies differ.
• Must users jump to arbitrary pages? Keyset pagination is good at sequential next and previous navigation, but “page 500” alone does not reveal a key boundary. If page jumps are mandatory, retain offset for a bounded depth or precompute anchors.
• Can sort or filter fields change? createdat and id must remain stable. Sorting by mutable updatedat, price, or score allows a record to cross an already visited boundary. Status changes also alter result membership and must be part of the public contract.
• Does the product need an exact total and a last page? Fetching one extra row can determine hasNextPage; exact totalCount is a separate aggregation cost. A load-more interface should not force a full count on every page.
• How long may a cursor remain valid? Schema changes, filter-rule changes, signing-key rotation, and snapshot retention all affect validity. The server needs an expiry error and an explicit way to restart from the first page.
• Can tenant access or permissions change while paging? A cursor never replaces authentication and authorization for the current request. Every page rechecks the current principal, and the cursor is bound to normalized filters and scope so that it cannot be reused across tenants.

30-Second Answer

“I would first confirm that this is a live ordered traversal, not a database snapshot across requests. I would use immutable createdat DESC, id DESC, with the unique ID breaking timestamp ties. A next-page cursor carries the previous page's last two values, a version, and a filter fingerprint, then uses URL-safe encoding and an HMAC signature. The query applies (createdat, id) < (cursortime, cursorid), the same descending order, and LIMIT 51; it returns 50 rows and uses the extra row for hasNextPage. The matching index is (tenantid, status, createdat DESC, id DESC). For the previous page, I reverse the comparison and database order, then reverse the response. Newer inserts do not shift later pages, but deletes and status changes are not frozen. Strict snapshots need versioned data or a materialized session. I would test tied timestamps, concurrent writes, boundary deletion, cursor tampering, and deep-page plans.”

Step-by-Step Solution

Start by defining the API contract. The first page has no cursor. Forward navigation accepts after; backward navigation accepts before; a request cannot contain both. The default page size is 50, with a server-enforced range of 1 through 100. A response can use this shape:

{
  "data": [],
  "pageInfo": {
    "startCursor": "...",
    "endCursor": "...",
    "hasNextPage": true,
    "hasPreviousPage": false
  }
}

startCursor and endCursor come from the first and last returned rows. Request 51 rows and return only 50 to determine hasNextPage. If the opposite-direction flag must be exact, run a small indexed EXISTS query from the other boundary. Inferring it only from the presence of an after parameter can be wrong after all preceding rows have been deleted.

Replace Positional Offsets with a Compound Boundary

The first-page query is:

SELECT id, created_at, total_cents, status
FROM orders
WHERE tenant_id = $1
  AND status = $2
ORDER BY created_at DESC, id DESC
LIMIT 51;

For the next page, place the previous page's final (created_at, id) pair in a strict less-than predicate:

SELECT id, created_at, total_cents, status
FROM orders
WHERE tenant_id = $1
  AND status = $2
  AND (created_at, id) < ($3, $4)
ORDER BY created_at DESC, id DESC
LIMIT 51;

PostgreSQL compares row constructors from left to right and stops at the first unequal pair. That matches the lexicographic boundary of the two descending sort keys. Defining both columns as non-null avoids the unknown result that a row comparison can produce when it reaches NULL. The id does not have to encode time; it only has to provide a unique, stable tie-break within one created_at value.

The matching index is:

CREATE INDEX CONCURRENTLY orders_tenant_status_created_id_idx
ON orders (tenant_id, status, created_at DESC, id DESC);

The leading equality columns restrict the scan to one tenant and status. The final two columns provide the boundary and order. Whether to add response fields as included columns depends on measured row width, heap fetches, and write amplification; copying every response field into INCLUDE is not a default. Frequent status changes also maintain this index, so measure write latency, WAL volume, and index size.

Make the Cursor Evolvable and Tamper-Evident

The cursor is an opaque protocol, not a request for the client to assemble a created_at value. Its logical payload could be:

{
  "v": 1,
  "createdAt": "2026-07-16T02:30:00.123Z",
  "id": "ord_01J...",
  "filterHash": "sha256:...",
  "expiresAt": "2026-07-17T02:30:00Z"
}

The server applies URL-safe encoding to a canonical payload and attaches an HMAC. Base64 is encoding, not confidentiality. If the boundary values are sensitive, do not expose them in the client token; store them server-side under a random cursor ID instead. filterHash should cover at least the ordering version, status filter, and an authorization-scope identifier. Every request is authorized against the current principal before the server verifies the signature, version, expiry, and filter fingerprint. Any mismatch returns a stable invalid_cursor response and requires a restart from the first page; it must not silently apply the cursor to new filters.

The version field permits future ordering or encoding changes. During key rotation, the verifier may accept both the current and previous verification keys for the maximum cursor lifetime while signing new cursors only with the current key. Logs record the error category and cursor version, not the full cursor or clear-text filters.

Implement the Previous Page Symmetrically

The current page's first row is the boundary for navigating toward newer records. Change the predicate to > and query in ascending order so the database first returns the 50 rows closest to that boundary:

SELECT id, created_at, total_cents, status
FROM orders
WHERE tenant_id = $1
  AND status = $2
  AND (created_at, id) > ($3, $4)
ORDER BY created_at ASC, id ASC
LIMIT 51;

After removing the 51st probe row, the server reverses the result and returns the public descending order. Keeping descending order with LIMIT would select the first 50 rows in the entire result set, not the page immediately before the boundary. Both directions must share the same filter fingerprint and ordering version.

State the Guarantees Under Concurrent Changes

Under live semantics, the cursor means “continue with rows strictly below this immutable boundary.” If 100 newer orders arrive after the user reads page one, page two still resumes from the old boundary. The new rows do not push page one's final row onto page two. Deleting the boundary row afterward also does not break traversal because the cursor retains values; the query does not need to find that row again.

This is not a fixed snapshot. An unread order that changes from another status into the selected status may appear later if its sort position is below the current boundary. An order that leaves the filter set will not appear. Deletions can reduce the rows observed by the traversal. Putting “first-page start time” in the cursor only fences newer inserts; it does not freeze deletes or status changes.

If an export, reconciliation, or audit must contain every member of one fixed set, one option is a short-lived materialized result that stores matching order IDs and their order. Another is a read against versioned data with time-travel support. A controlled background job can also retain one database snapshot. Each choice adds storage, transaction-lifetime, or cleanup cost and needs a session expiry. Live keyset traversal usually fits an interactive list; audit workloads deserve a separate snapshot workflow.

Keep Offset Pagination Within Its Useful Boundary

Offset pagination is simple, supports direct page jumps, and maps naturally to page numbers. It works for small, stable administrative tables or an already frozen search result. Its costs are twofold: PostgreSQL must still compute and discard the rows before the OFFSET, so deeper offsets generally require more work; concurrent inserts and deletes also change position numbers, which can repeat or skip a row.

Keyset pagination anchors work to an indexed value boundary, so a deep page does not scan and discard every preceding row merely because the offset number is large. It cannot jump to an arbitrary page without an anchor. The decision rule is direct: use keyset for deep sequential traversal over changing data; use offset for bounded page-number navigation over small or frozen data; add a snapshot mechanism, independently of either pagination style, when the entire set must remain fixed.

Prove the Contract with Adversarial Cases

Verify membership and order before measuring latency:

1. Insert 120 orders with the same created_at. Confirm that the unique id prevents duplicates across pages and that the combined traversal is strictly descending.
2. Read page one, then insert 100 newer orders. Reproduce the positional shift with offset and confirm that keyset page two does not repeat a page-one row.
3. Delete page one's last row before continuing and confirm that the stored boundary still returns the correct next page.
4. Change an unread order's status between requests and confirm that the result follows the documented live semantics rather than being reported as a snapshot.
5. Modify one cursor byte, reuse it across tenants, change the status filter, and submit an expired version. Every request should be rejected.
6. Move forward three pages and backward three pages, checking IDs and order. Include result sizes of 0, 1, 50, and 51.
7. Run EXPLAIN (ANALYZE, BUFFERS) for the first page, second page, and a deep boundary. Confirm the expected compound index, a scanned-row count close to the page size, and record read p95, write p95, WAL volume, and index size.

Example of a Strong Answer

“I would bound the guarantee first. This operations list needs live sequential browsing, no direct page jump, and no database snapshot across several HTTP requests. I would therefore use keyset pagination rather than offset.

The order is immutable createdat DESC, id DESC. ID is the unique tie-breaker; without it, orders created in the same millisecond have no stable order. I fetch 51 rows and return 50. The next cursor stores the last row's timestamp and ID, and the next query uses (createdat, id) < (?, ?) with exactly the same order. Equality filters come first in (tenantid, status, createdat DESC, id DESC). For the previous page, the current first row is the boundary; I use >, query ascending for the nearest 51 rows, then reverse the response.

The cursor contains a version, the two boundary values, a filter fingerprint, and an expiry. It is URL-safe encoded and HMAC-signed. The server authorizes every page again and rejects a tampered, expired, or filter-mismatched cursor. It does not depend on the boundary row still existing, so deleting that row does not stop navigation.

For consistency, I promise to avoid duplicates caused by offset shifts. Newer orders inserted after page one do not enter later pages, but status changes and deletes can still alter the unread set. If reconciliation needs a fixed snapshot, I would create a materialized export session or read versioned data; adding a timestamp to an ordinary cursor is not a complete snapshot.

Finally, I would test tied timestamps, concurrent inserts, boundary deletion, status changes, cursor tampering, and forward/backward round trips. I would then compare plans for page one, page two, and a deep boundary, plus the new index's effect on write latency and WAL.”

Common Mistakes

• Base64-encoding a page number → The server still executes OFFSET, so neither performance nor positional drift changes → Make the cursor represent an indexed ordering boundary.
• Using only created_at → Tied timestamps do not form a total order and can be repeated or skipped → Add a unique, stable id to both the query and cursor.
• Using a predicate that disagrees with the sort order → The boundary no longer represents the public order, creating overlaps or gaps → Derive ORDER BY, comparison operators, and the index from one lexicographic order.
• Treating Base64 as tamper protection → A client can alter the timestamp, ID, or filter scope → Use an HMAC for integrity and rerun current authorization.
• Leaving filters out of the cursor binding → Reusing a pending-order cursor for a paid-order query creates unexplained gaps → Include normalized filters, ordering version, and scope in the signed fingerprint.
• Keeping descending order for a previous-page LIMIT → The query returns the head of the entire set instead of the segment next to the boundary → Reverse the database order, trim, and reverse the response.
• Claiming keyset is a complete snapshot → Deletes, status changes, and mutable sort keys still alter membership → Publish live semantics; add versioned or materialized snapshots when strict consistency is required.
• Counting the full result on every page → Pagination gets faster while totalCount becomes the new slow path → Treat count as a separate, cacheable, or approximate product capability.
• Testing only the first page → The compound boundary is first exercised on page two, where an index mismatch may surface → Inspect plans for the first two pages, deep pages, and both directions.

Follow-Up Questions

What if the product must sort by mutable total_cents?

The compound cursor can become (total_cents, id), but that only breaks ties. It does not stop an edited amount from moving a row across an already visited boundary. If live reordering is acceptable, document possible duplicates or omissions and deduplicate by ID on the client. If stability is mandatory, freeze the sort value for the browsing session, materialize the ID list, or make edits create new versions. The immutable-key guarantee no longer applies.

What if users must jump directly to page 500?

Keyset pagination does not know page 500's boundary. First ask whether the real need is a date, order number, or a page label; dates and order numbers can become indexed search anchors. If numeric pages are mandatory, cap the jump depth and use offset within that range, or store periodic page anchors and keyset from the nearest one. Anchors also age under live data, so they need a version or snapshot identifier.

Can this API export all 200 million rows?

An interactive API's short-lived cursor and live semantics are a poor fit for a long audit export. Create a background export job, read a fixed snapshot or version boundary in chunks of an immutable primary key, write to object storage, and persist checkpoints and validation counts. Retries, expiry, resource limits, and completion checks then have their own lifecycle instead of binding one HTTP cursor indefinitely to the online index and signing format.

How do you rotate signing keys during pagination?

Include a version or key identifier in the cursor. For the maximum cursor lifetime, the verifier retains the current and previous verification keys while new cursors are signed only with the current key. Delete the old key after that window. If a security incident requires immediate revocation, return invalid_cursor consistently and restart the client at page one instead of accepting a compromised key for seamless navigation.

Why does deleting the boundary row work while changing its sort key does not?

The next query needs only the two values stored in the cursor; it never has to find the boundary row again, so deletion does not change the strict less-than predicate. Editing a sort key moves the same record from one side of the boundary to the other. It may re-enter a future range or jump from an unread range to a visited one. Stable ordering values are a correctness requirement; continued existence of the boundary row is not.