Design query pagination for large datasets

Scenario

You are building an API that returns a paginated list of records from a very large dataset (millions+ rows). Clients can specify:

• Filters (e.g., status, date range)
• Sort order (e.g., created_at desc , possibly tie-breaking by id )
• Page size (limit)

Example endpoint:

• GET /items?status=OPEN&sort=created_at_desc&limit=50&cursor=...

Requirements

1. Support fast pagination for deep pages (e.g., user keeps scrolling).
2. Results should be stable : users should not see duplicates or missing items while paginating, even if new records are inserted concurrently.
3. Support common relational databases (e.g., Postgres/MySQL) and typical indexes.
4. Handle common edge cases:
   • Many records share the same created_at
   • Data can be inserted/updated/deleted while the user paginates
   • Clients may change filters/sort between requests

Tasks

1. Propose a pagination strategy (e.g., offset-based, cursor/keyset-based, or hybrid) and explain the trade-offs.
2. Define the cursor format and what fields it must contain.
3. Provide example SQL queries for the first page and subsequent pages.
4. Discuss how you would ensure stability/consistency, and what guarantees you can realistically provide (e.g., “as of” snapshot vs best-effort).
5. Describe the indexing strategy and how it changes with different sort orders.