Katkat
Back

Design Cursor Pagination for a Large Dataset

Wells FargoSoftware Engineer · Technical Screen
MediumSoftware EngineerTechnical ScreenSystem Design

Last updated

This problem tests the ability to design a performant, stable pagination system for large datasets using cursor-based navigation instead of offset-based pagination.

Problem Statement

Design a RESTful API endpoint for a high-volume financial transaction ledger that supports cursor-based pagination. The system must handle millions of rows and ensure that records are not skipped or duplicated even if new transactions are inserted while a user is paginating through results.

Functional Requirements

  • Provide a way to fetch the first page and subsequent pages.
  • Support sorting by transaction_timestamp (descending) and transaction_id (as a tie-breaker for deterministic ordering).
  • The API must be performant and scale to high concurrency.

Non-Functional Requirements

  • Avoid the O(N) performance penalty of OFFSET queries.
  • Ensure stability: new records added to the database should not affect the current page view during traversal.
  • Maintain low latency for deep-page queries.

Deliverables

  1. Propose an API request/response format.
  2. Define the database schema (columns and index strategy).
  3. Explain the query logic to retrieve the next set of results given a cursor.
  4. Discuss how to handle authorization checks (e.g., ensuring a user only sees their own transactions) in the context of keyset pagination.

Example

GET /transactions?limit=20&cursor=eyJ0cyI6IDE2MjUwMDAwMDAsICJpZCI6IDEwNDV9

The cursor is a base64-encoded string representing the last seen record's timestamp and ID. The server decodes this to perform: WHERE (timestamp, id) < (1625000000, 1045) ORDER BY timestamp DESC, id DESC LIMIT 20.

Hints

Hint 1

Consider why standard offset-based pagination (LIMIT/OFFSET) performs poorly on large datasets as the offset increases.

Hint 2

Think about how combining a timestamp with a unique, immutable ID allows you to create a total ordering that satisfies the criteria for a keyset cursor.

Hint 3

Evaluate how to incorporate user-specific filters into your query without breaking index efficiency.

Follow-up questions

  • How would you handle the cursor if the sorting criteria were changed to include a field that is not unique or is potentially nullable?
  • What are the trade-offs of using an opaque string (base64) for the cursor versus returning the cursor components explicitly in the JSON response?
  • If you needed to support jumping to a specific page number (e.g., 'Go to page 50'), how would you implement that, and what are the limitations?