Skip to content

Pagination Strategy

1. Decision

Choose Cursor-Based (Seek) Pagination for high-scale, real-time, or continuously updated datasets to guarantee \(O(1)\) query performance and prevent duplicate/skipped items; choose Offset-Based Pagination (LIMIT/OFFSET) for small static datasets or internal admin tables where direct page jumping (e.g. "Go to Page 5") is mandatory.

2. 30-Second Answer

Pagination splits large database result sets into manageable chunks. Offset-Based Pagination (LIMIT 20 OFFSET 100) is simple to implement and allows UI jumping to specific page numbers. However, it suffers from \(O(N)\) database degradation (the DB must read and discard \(N\) offset rows) and Data Drift (inserting/deleting rows while a user navigates shifts page boundaries, causing duplicate or skipped items). Cursor-Based (Keyset/Seek) Pagination uses a unique, sequential column value (e.g., WHERE id > cursor LIMIT 20) to seek directly to the next page. It delivers constant-time \(O(1)\) query performance, eliminates data drift, and scales seamlessly for infinite scroll feeds (Twitter/X, Instagram), but forbids jumping to arbitrary page numbers.

3. Decision Matrix

Option Best For Avoid When Latency Scalability Consistency Operational Complexity
Offset-Based (LIMIT x OFFSET y) Small static tables (<10,000 rows), internal admin dashboards, UI requiring explicit "Page 1, 2, 3" page jumping buttons Large datasets (>100k rows), real-time user feeds with high insert/delete velocity Low for page 1; High (\(O(N)\)) for deep offsets (Page 1000) Poor (Database scans and discards all preceding offset rows) Weak (Subject to Data Drift / skipped items on inserts) Low
Cursor-Based (Keyset / Seek) Real-time user feeds, social media timelines, high-volume APIs, mobile infinite scroll UI UIs requiring arbitrary page jumping ("Jump to Page 50") Sub-millisecond (\(O(1)\) indexed B-Tree seek) Extremely High (Performance independent of page depth) Strong (Immune to Data Drift on inserts/deletes) Medium (Cursor encoding/decoding)
Page-Token Pagination (Base64 Encoded) Public REST APIs (Google/Stripe APIs), GraphQL connections spec Simple internal CRUD endpoints Sub-millisecond (\(O(1)\) seek) High Strong Medium

4. Selection Rules

Requirement Best Choice Rationale / Example
Mobile Infinite Scroll Feed (Twitter/X / Instagram) Cursor-Based Seeking via WHERE id < cursor ORDER BY id DESC LIMIT 20 prevents feed item duplication
Admin Dashboard UI with Page Jump Buttons Offset-Based Admin UI displays "Page 1 2 3 ... 50"; dataset size is small (<50,000 rows)
High Performance Deep Pagination (Page 1,000+) Cursor-Based \(O(1)\) index lookup skips reading preceding 1,000,000 database rows
Public REST API Standard (Google/AWS API style) Page-Token Return next_page_token (opaque Base64 cursor encoding id + timestamp)
Keyset Sorting on Multiple Columns Composite Cursor Encode tie-breaker ID alongside sort column: (created_at, id) > (cursor_time, cursor_id)

5. Tradeoffs

  1. \(O(1)\) Keyset Seek vs \(O(N)\) Offset Disk Scan
  2. Gain (Cursor): Query execution time remains sub-millisecond whether fetching Page 1 or Page 10,000.
  3. Lose (Cursor): Cannot calculate total page count or jump directly to arbitrary page numbers.
  4. Data Drift Immunity vs Page Number UI Controls
  5. Gain (Cursor): New inserts at top of feed do not push existing items down into subsequent page requests.
  6. Lose (Cursor): Restricted to "Next" and "Previous" page navigation controls.
  7. Sequential B-Tree Index Utilization
  8. Gain (Cursor): WHERE id > cursor uses B-Tree index range scans directly.
  9. Lose (Cursor): Sort column MUST be indexed and strictly sequential/unique (or combined with primary key).
  10. Opaque Page Tokens vs Simple Integer Parameters
  11. Gain (Page-Token): Server can change internal cursor implementation without breaking client API contracts.
  12. Lose (Page-Token): Requires Base64 encoding/decoding and validation logic on every API call.
  13. Multi-Column Sorting Complexity
  14. Gain: Enables cursor pagination on non-unique columns (e.g., sort by likes_count DESC).
  15. Lose: Requires complex tuple comparison clauses WHERE (likes, id) < (cursor_likes, cursor_id).

6. Interview Counter Questions

  1. Why does OFFSET 1000000 LIMIT 20 cause severe CPU and disk I/O performance degradation in MySQL/Postgres?
  2. What is Data Drift (Page Drift) in Offset-Based pagination?
  3. How do you construct a SQL query for Cursor-Based Pagination on a non-unique column (e.g. created_at)?
  4. How does Base64 Page Token encoding work in Google and Slack APIs (next_page_token)?
  5. Why is SELECT COUNT(*) for total page count an anti-pattern on multi-million row tables?
  6. How do GraphQL Cursor Connections (Relay Specification) handle pagination?
  7. What happens in Cursor Pagination if an item referenced by the current cursor is deleted from the database?
  8. How do you implement Bidirectional Pagination (Previous & Next page navigation) using Cursors?
  9. When would you use Search After (search_after) in Elasticsearch for pagination?
  10. How do you cache paginated API responses effectively in Redis?

7. Gold Standard Answers

  1. The DB must perform a full index scan to fetch 1,000,020 rows into memory, count through 1,000,000 offset rows, discard them, and return only the last 20 rows (\(O(N)\) time & memory waste).
  2. Data Drift: If 5 new items are inserted into Page 1 while a user is viewing Page 1, navigating to Page 2 (OFFSET 20) causes the last 5 items of Page 1 to shift to Page 2, causing duplicate reads.
  3. Use a Composite Cursor with a tie-breaker Primary Key: WHERE (created_at, id) < ($cursor_time, $cursor_id) ORDER BY created_at DESC, id DESC LIMIT 20.
  4. Server serializes the internal cursor state into JSON ({"id": 1234, "ts": 177000000}), encrypts/signs it, and Base64-encodes it into an opaque string returned as next_page_token.
  5. SELECT COUNT(*) in MVCC databases (PostgreSQL) forces a full table scan of all disk tuples to verify snapshot visibility, taking seconds on large tables. Return estimated count or omit total count.
  6. Relay GraphQL spec returns edges [{ node, cursor }] and pageInfo { hasNextPage, endCursor }. Clients pass first: 20, after: "cursor_string" to fetch pages cleanly.
  7. If sorting by id > cursor_id, deleting that specific record has zero impact because the B-Tree index seek simply finds the first existing index entry greater than cursor_id.
  8. Next Page: WHERE id < $end_cursor ORDER BY id DESC LIMIT 20. Previous Page: WHERE id > $start_cursor ORDER BY id ASC LIMIT 20 (and reverse the array in application code).
  9. Elasticsearch search_after uses Lucene doc-values as a cursor to bypass the 10,000 record result window limit (index.max_result_window), delivering \(O(1)\) deep pagination across shards.
  10. Cache individual entity payloads by ID in Redis. Store paginated ordered lists of IDs in Redis Sorted Sets (ZSET), using score offsets (ZRANGEBYSCORE) for cursor-based retrieval.

8. Common Mistakes

  • Using LIMIT/OFFSET for multi-million row tables or real-time social media timelines.
  • Sorting by non-unique columns (e.g. ORDER BY status) in cursor pagination without adding id as a tie-breaker.
  • Running expensive SELECT COUNT(*) on every paginated API request just to show a "Total Pages" number.
  • Exposing raw database auto-increment IDs in public API cursors instead of opaque Base64 tokens.
  • Forgetting to add a composite database index on (sort_column, primary_key) for cursor queries.

9. Keywords

Pagination, Offset-Based, Cursor-Based, Keyset Pagination, Seek Method, Data Drift, \(O(1)\) Seek, Composite Cursor, Tie-Breaker, Base64 Page Token, next_page_token, Relay GraphQL Spec, search_after, Estimated Count.

10. Cheat Sheet

  • Offset-Based (LIMIT x OFFSET y): Use ONLY for small static tables (<10k rows) or admin UIs requiring page numbers. \(O(N)\) performance degradation & Data Drift.
  • Cursor-Based (Keyset/Seek): \(O(1)\) indexed B-Tree lookup. Use for high-scale APIs, mobile feeds, and infinite scroll. Immune to Data Drift.
  • Composite Cursor Formula: WHERE (sort_col, id) < (cursor_val, cursor_id) ORDER BY sort_col DESC, id DESC LIMIT 20.
  • Tie-Breaker Rule: Always append Primary Key (id) as a tie-breaker when sorting by non-unique columns.
  • Page Tokens: Public APIs should return Base64 encoded opaque strings (next_page_token) to hide internal DB schema details.
  • Avoid COUNT(*): Never execute SELECT COUNT(*) on multi-million row tables per page request; use estimated counts (pg_class.reltuples).

11. Related Decisions