Question and context
This question tests whether a backend engineer can handle deep-page performance, stable ordering under concurrent writes, and an explicit cursor contract at the same time. Assume a client browses orders or a changing feed in descending time order, 50 rows per page, with new rows arriving continuously; it mostly needs the next page rather than arbitrary page jumps.
It fits backend, data-service, and platform roles. Do not announce that a cursor is always faster. First clarify ordering, page jumps, exports, consistency, deletion semantics, replicas, and indexes because each constraint changes the choice.
What the interviewer is evaluating
A strong answer explains why deep OFFSET scans and discards earlier rows, why a non-unique sort key drifts under concurrent writes, and why keyset pagination needs a stable total order and matching index. It also separates a stateless keyset token from a database cursor that holds a transaction, and proposes tests for duplicates, gaps, a deleted boundary row, and forged tokens.
Clarifying questions to ask
- Must users jump to page N or see a total count? Pure keyset pagination does not provide that directly.
- What is the sort order? Is the timestamp unique and immutable, or does it need a unique ID tie-breaker?
- Does the client want a live view or a snapshot for one traversal? Inserts and deletes look different under each.
- Does the query span replicas, shards, or tenant filters? The index and token must bind those conditions.
- Can clients decode, modify, or replay a cursor? That determines signing, expiry, and versioning.
A 30-second answer framework
“I first clarify ordering, page jumps, and consistency semantics. For a large changing list I would use keyset pagination with a unique tie-breaker, such as created_at DESC, id DESC, backed by a matching composite index; the next request carries the last row’s sort keys instead of a deep OFFSET. The cursor encodes filters, sort version, and boundary, then is signed and given an expiry. If the traversal needs a fixed snapshot, I would consider a timestamp or transactional database cursor and explain its resource cost. I would validate the contract with concurrent inserts, deletes, duplicate timestamps, and tampered tokens.”
Step-by-step answer
Step 1: Define the pagination contract
Specify the limit cap, default order, nextcursor, hasmore, and filters. Stable ordering requires a total order; ordering only by created_at is ambiguous when rows share a timestamp, so add an immutable unique ID. If the client needs a previous page, design the reverse comparison and boundary handling explicitly instead of simply reversing the next-page query.
Step 2: Explain OFFSET performance and drift
OFFSET k LIMIT n commonly requires the database to locate and skip k preceding rows, so deep-page work grows with k. If an insert or delete occurs before an already-read page, later offsets move and can produce duplicates or gaps. A small, mostly static admin list that needs page jumps may accept OFFSET, but cap its depth and verify the cost with an execution plan.
Step 3: Implement keyset over a stable total order
For descending (created_at, id), the first page has no boundary and the next page uses the last row’s keys:
-- first page
SELECT id, title, created_at
FROM posts
ORDER BY created_at DESC, id DESC
LIMIT 50;
-- next page: boundary comes from the last returned row
SELECT id, title, created_at
FROM posts
WHERE (created_at, id) < (:last_created_at, :last_id)
ORDER BY created_at DESC, id DESC
LIMIT 50;The query seeks from an index boundary and scans a bounded number of rows instead of skipping every earlier page. Composite-index column order, filters, and direction must match the query; otherwise a theoretically good keyset query can still scan a large range.
Step 4: Design a verifiable cursor token
Do not treat an internal offset as a cursor. Include boundary keys, a filter digest, sort version, and expiry; sign the token or use authenticated encryption so clients cannot modify it. On receipt, validate the version, tenant, and filters against the request. If ordering changes, reject the old version or restart explicitly rather than interpreting the same token under a different order.
Step 5: Choose live or snapshot semantics
Live keyset pagination lets new rows appear at the top; rows already beyond the boundary normally do not repeat. Deleting the boundary row does not make it reappear, although the total count changes. For an export or audit that needs a fixed set, include a read timestamp, snapshot version, or database cursor in the contract. A database cursor can hold a transaction and resources, so it is not automatically suitable for long-lived HTTP pagination.
Step 6: Handle replicas, shards, and boundary rows
Replica lag can temporarily hide a row that was returned by the primary. Pin the route, carry a confirmed time boundary, or document eventual consistency. Across shards, each shard can produce a local keyset and the service can perform a cursor-aware k-way merge. Test deletion of the final boundary row, equal timestamps, and filter changes.
Step 7: Verify performance and correctness
Performance checks include deep-page row scans, P95 latency, and index usage. Correctness tests insert, delete, and update rows between requests and assert the promised duplicate and gap behavior. Log each page’s filters, sort version, first and last keys, and token version so production drift can be mapped to a concrete boundary.
Example of a strong answer
“I would first clarify whether users need page jumps, total counts, or a fixed snapshot, and whether the sort field is unique. For a continuously written list that is mostly browsed forward, I would choose keyset pagination: use immutable created_at plus unique id for a total order and composite index, then use the last row’s two keys as the next range boundary. Deep pages do not scan and discard all previous rows, and an insert before the boundary does not shift every later page.
I would encode filters, sort version, boundary keys, and expiry in a signed token, then require the token’s tenant and filters to match the request. Under live semantics new rows appear at the top; for audit-level fixed results I would consider a timestamp or controlled transactional cursor and explain long-transaction costs. With replicas I would pin routing or document the visibility boundary.
Finally, I would verify execution plans and concurrency tests covering deep scans, duplicate timestamps, inserts, deletes, updates to boundary rows, replica lag, and token tampering. A small admin list that must jump pages can keep OFFSET, but I would cap depth and monitor latency.”
Common mistakes
- Claiming cursors are always faster → ignores jumps and long-transaction cost → compare OFFSET, keyset, and database cursors by constraint.
- Sorting only by time → ties have unstable order → add an immutable unique ID.
- Putting an offset number in the token → deep pages still drift and cost more → carry the sort boundary and filter digest.
- Leaving live/snapshot undefined → clients cannot interpret inserts or deletes → state visibility semantics in the API contract.
- Ignoring index direction and filters → keyset still scans many rows → verify the composite index with an execution plan.
- Accepting any client cursor → tenants or stale boundaries can be forged → sign, validate the version, and expire tokens.
Follow-up questions and answers
Follow-up 1: Users must jump to page 500. What do you do?
For a small or mostly static admin list, bounded OFFSET is reasonable. For a large list, use precomputed page boundaries or search and sort filters so users locate the desired region instead of promising low latency at arbitrary depth. Document the cost and consistency limits of either choice.
Follow-up 2: created_at can be edited. Is the cursor stable?
No. Use immutable creation time plus a unique ID, or freeze the mutable sort field in a snapshot version. If the business must sort by a mutable field, accept movement in a live view or use a fixed version with additional storage and read cost.
Follow-up 3: A lagging replica makes the next page short. How do you handle it?
Pin reads to the primary or the same replica according to the consistency requirement, or carry a “not earlier than time/LSN” boundary and return an explicit state after a wait timeout. Do not silently treat missing rows as end-of-list; distinguish temporary invisibility from has_more=false.
Follow-up 4: How do you prove there are no duplicates or gaps?
Build controlled concurrency tests: read page one, insert before the boundary, delete the boundary row, insert equal sort keys, and update rows; then inspect the unique-ID set, ordering, and promised visibility. Log page boundaries, token versions, and snapshot identifiers so a failure can be reproduced at the exact boundary.