Pagination Strategies

1. What Is It?

Pagination is the technique of returning a subset of a large result set per request rather than all rows at once. Without pagination, listing endpoints on large tables become slow, memory-intensive, and unusable — fetching millions of rows to display 20 is both wasteful and dangerous.

There are two fundamentally different approaches: offset-based pagination (LIMIT/OFFSET) and cursor-based pagination (keyset/seek pagination). They have different performance profiles, consistency guarantees, and implementation complexity. Choosing correctly matters at scale.

2. How It Works

Offset-Based Pagination (LIMIT/OFFSET)

Copy
-- Page 1: items 1–20
SELECT id, title, created_at
FROM posts
ORDER BY created_at DESC
LIMIT 20 OFFSET 0;

-- Page 2: items 21–40
SELECT id, title, created_at
FROM posts
ORDER BY created_at DESC
LIMIT 20 OFFSET 20;

-- Page N:
SELECT id, title, created_at
FROM posts
ORDER BY created_at DESC
LIMIT 20 OFFSET (page - 1) * 20;

How it works internally: the database sorts all matching rows, skips the first OFFSET rows, then returns LIMIT rows. At OFFSET 0 this is fast. At OFFSET 10000, the database still scans and sorts 10,020 rows to return just 20.

Cursor-Based Pagination (Keyset / Seek Method)

Instead of saying "skip N rows," you say "give me rows after this specific row."

Copy
-- First page (no cursor)
SELECT id, created_at, title
FROM posts
ORDER BY created_at DESC, id DESC
LIMIT 20;

-- Next page: client sends back the created_at and id of the last row seen
SELECT id, created_at, title
FROM posts
WHERE (created_at, id) < ('2024-03-15 10:30:00', 42891)
ORDER BY created_at DESC, id DESC
LIMIT 20;

The composite WHERE (created_at, id) < (...) clause skips directly to the right starting point using an index. The database doesn't scan rows it already returned.

-+ResetFullscreen

3. What SDEs Actually Need to Know

OFFSET performance degrades with depth. Offset pagination at page 500 (OFFSET 10000) is meaningfully slower than page 1, even with indexes. The database must still locate and discard 10,000 rows. For most applications, users never go past page 10 — so offset pagination is fine. For feeds, API consumers, or data exports that page through millions of rows, it's a scalability problem.

Cursor pagination requires a stable sort order with a unique tiebreaker. If two rows have identical created_at values, the cursor WHERE created_at < X is ambiguous. Always include a unique column (usually id) as a secondary sort key:

Copy
ORDER BY created_at DESC, id DESC
-- Cursor: (created_at, id) < (cursor_time, cursor_id)

Row instability with offset pagination. If new rows are inserted while a user is paginating, rows can shift:

• Insert before the current page → user sees a row twice (it shifted into the previous page range)
• Delete from the current range → user skips a row

Cursor pagination is immune to this: the cursor references an absolute position in the sort order.

Total count queries are expensive. Many UIs show "Page 3 of 47". The SELECT COUNT(*) to compute total pages scans the entire table (or a large index). At scale this is slow enough to disable. Options:

• Drop the total count entirely (infinite scroll, "load more")
• Cache the count with a TTL (accept staleness)
• Use approximate counts (pg_class.reltuples in PostgreSQL for rough estimates)

Implementing cursor encoding. Cursors are usually opaque to the client — a base64-encoded string containing the sort values. The server decodes the cursor and constructs the WHERE clause. Never expose raw column values in the cursor if they reveal sensitive internal details.

Copy
import base64, json

def encode_cursor(created_at, id):
    payload = json.dumps({"created_at": created_at.isoformat(), "id": id})
    return base64.urlsafe_b64encode(payload.encode()).decode()

def decode_cursor(cursor_str):
    payload = base64.urlsafe_b64decode(cursor_str).decode()
    return json.loads(payload)

4. Tradeoffs & Decisions

When to use offset pagination:

• Admin UIs where users rarely go past page 5
• Small tables (< 100k rows)
• You need "jump to page N" functionality
• Simplicity is valued over performance

When to use cursor pagination:

• Public APIs (feeds, timelines, notification lists)
• Tables that grow continuously (logs, events, messages)
• Any paginated query that might go deep (data export, bulk processing)
• Real-time feeds where inserts happen between page requests

Hybrid approaches: Some systems use offset for the first few pages (fast and simple) and switch to cursor for deeper pages. This is an optimization added only when offset latency is measured as a problem.

5. Interview Cheat Sheet

Key sentences:

• "Offset pagination requires scanning and discarding OFFSET rows; cursor pagination seeks directly to the starting point using an index — constant time regardless of depth."
• "Cursor pagination requires a stable sort key with a unique tiebreaker to avoid ambiguity at the cursor boundary."
• "Offset pagination shows rows shifting when data is inserted between requests; cursor pagination is stable because the cursor references an absolute sort position."
• "I avoid SELECT COUNT(*) for total page counts on large tables — I prefer infinite scroll or a cached/approximate count."

Common follow-ups:

Q: How do you handle bidirectional pagination with cursors (next page AND previous page)? A: Store both a "next" and "previous" cursor. For the previous cursor, reverse the ORDER BY direction and swap the comparison operator. Some implementations maintain a cursor for the first item on the current page (for previous) and the last item (for next), both encoded separately.

Q: What happens when you delete a row that was used as a cursor? A: The cursor still works correctly — the WHERE clause finds rows that would have sorted after the deleted row, regardless of whether the row still exists. The cursor is a sort position, not a row reference.

Q: How would you paginate a query with no natural sort order? A: Add ORDER BY id as a tiebreaker. Every table with a surrogate integer PK has a stable sort order. Avoid ORDER BY RANDOM() or no ORDER BY clause — results are non-deterministic and will show different rows on each request.