Design Cursor Pagination for a Large Dataset

# Design Cursor Pagination for a Large Dataset API Design an API that reads a very large database-backed dataset for a user interface. Compare offset pagination with a cursor based on the last returned record, define a stable cursor contract, and choose supporting indexes. Address concurrent inserts or updates, filters, authorization, and malformed or stale cursors. ### Constraints & Assumptions - Clients request bounded pages and may apply supported filters. - The dataset is too large for deep `OFFSET` scans. - Sort keys are not necessarily unique. - Rows can be inserted or updated while a client paginates. - Cursor contents must not let a client bypass authorization. ### Clarifying Questions to Ask - What sort orders and filters must be supported? - Is a snapshot-consistent traversal required, or is a live feed acceptable? - Can fields used for ordering change? - Must clients navigate backward as well as forward? ### What a Strong Answer Covers - A total deterministic order with a unique tie-breaker - Opaque, validated keyset cursors bound to query scope - Matching composite indexes and bounded `LIMIT` queries - Clear consistency behavior under inserts, deletes, and sort-key updates - Page metadata, authorization, expiry, and operational limits ### Follow-up Questions 1. How would you support reverse pagination? 2. What happens when the primary sort field changes between requests? 3. How would you give the user an exact total count without slowing every page? ```hint Put the last sort tuple in the cursor Seek strictly after a complete, unique ordering tuple rather than asking the database to discard all preceding rows. ```