Skip to content

Pagination Strategies#

Problem statement (interviewer prompt)

A feed API must return a list of items in a stable order, allowing clients to fetch subsequent pages. Compare the three common implementations (offset, keyset, cursor) on correctness with concurrent writes, latency at deep pages, and ease of caching.

Three common ways to paginate:

flowchart LR
  subgraph Offset[Offset / LIMIT]
    O[LIMIT 20 OFFSET 1000<br/>scans 1020 rows]
  end
  subgraph Keyset[Keyset / seek]
    K[WHERE id > last_id<br/>LIMIT 20<br/>O log N]
  end
  subgraph Cursor[Cursor-based]
    C[?cursor=opaque-token<br/>server decodes position]
  end

    classDef service fill:#fef3c7,stroke:#92400e,stroke-width:1px,color:#0f172a;
    class O,K,C service;

    classDef client fill:#dbeafe,stroke:#1e40af,stroke-width:1px,color:#0f172a;
    classDef edge fill:#cffafe,stroke:#0e7490,stroke-width:1px,color:#0f172a;
    classDef service fill:#fef3c7,stroke:#92400e,stroke-width:1px,color:#0f172a;
    classDef datastore fill:#fee2e2,stroke:#991b1b,stroke-width:1px,color:#0f172a;
    classDef cache fill:#fed7aa,stroke:#9a3412,stroke-width:1px,color:#0f172a;
    classDef queue fill:#ede9fe,stroke:#5b21b6,stroke-width:1px,color:#0f172a;
    classDef compute fill:#d1fae5,stroke:#065f46,stroke-width:1px,color:#0f172a;
    classDef storage fill:#e5e7eb,stroke:#374151,stroke-width:1px,color:#0f172a;
    classDef external fill:#fce7f3,stroke:#9d174d,stroke-width:1px,color:#0f172a;
    classDef obs fill:#f3e8ff,stroke:#6b21a8,stroke-width:1px,color:#0f172a;

Offset is the default but degrades at large offsets and is brittle under inserts. Keyset is fast and correct but requires a monotonic key. Cursor wraps keyset in an opaque token for API stability.

Pagination is the boundary between "scan everything" and "scan what the user can see". Picking the right mechanism prevents the slow-page bug and the duplicate/missing-row bug.

Offset / LIMIT#

SELECT * FROM posts ORDER BY created_at DESC LIMIT 20 OFFSET 1000;
  • Pros: trivial; jump to any page; works on any sortable column.
  • Cons:
  • DB scans OFFSET + LIMIT rows before returning. Page 1000 scans 20,020 rows.
  • Inserts at the head shift items: page 2 may repeat or skip a row vs page 1.

Acceptable for: small datasets, admin UIs, single-user dashboards.

Keyset (seek) pagination#

SELECT * FROM posts
WHERE created_at < :last_created_at
  AND (created_at < :last_created_at OR id < :last_id)
ORDER BY created_at DESC, id DESC
LIMIT 20;
  • Pros:
  • Constant-time per page; index seek instead of scan.
  • Resilient to inserts; you always continue from where you left off.
  • Cons:
  • No jump-to-page-N.
  • Requires a strictly monotonic sort key (timestamp+id tiebreak).
sequenceDiagram
  participant C as Client
  participant API
  participant DB
  C->>API: GET /posts
  API->>DB: WHERE id < INF LIMIT 20
  DB-->>API: [p20, p19, ..., p1], last_id=p1
  API-->>C: items + next_cursor=p1
  C->>API: GET /posts?cursor=p1
  API->>DB: WHERE id < p1 LIMIT 20
  DB-->>API: [pre_p1, ...]

Cursor-based (opaque token)#

The server packages the seek state into an opaque, signed, base64 token:

{ "after": "WyJjcmVhdGVkX2F0IiwgIjIwMjQtMDEtMDEiLCAiYWJjMTIzIl0=" }
  • Pros:
  • Schema can change without breaking clients (the token's contents are private).
  • Can encode multiple sort fields, filters, even fairness state.
  • Works for non-DB data sources (search results, sharded fan-out).
  • Cons:
  • Cursors expire when underlying data shifts dramatically.
  • Operators can't inspect at a glance what page a client is on.

Comparison#

Property Offset Keyset Cursor
Deep-page latency O(N) O(log N) O(log N)
Insert stability low high high
Jump to arbitrary page yes no no
Requires monotonic key no yes yes (hidden)
Schema-change tolerant n/a medium high
Common in admin UIs DB queries public APIs

Sorting trade-offs#

Sort by a non-unique column (e.g. score) needs a tiebreak:

ORDER BY score DESC, id DESC

Without the tiebreak, two rows with the same score can flicker between pages or skip entirely.

Caching pages#

  • Offset: easy CDN cache by URL; invalidates on every insert.
  • Keyset: easy to cache because the URL pins the slice. Slice contents never change unless that slice is mutated.
  • Cursor: same as keyset; an opaque token is a stable cache key.

Total-count problem#

SELECT COUNT(*) over millions of rows is expensive. Strategies:

  • Show "page 1 of many"; don't compute exact total.
  • Materialized count (write-time counter), refreshed periodically.
  • Approximate with EXPLAIN-derived row estimate.
  • Probabilistic with HyperLogLog.

Real-world examples#

API Pattern
GitHub REST Page + per_page (offset-like) with Link header
Stripe Cursor (starting_after, ending_before)
Twitter / X Cursor (since_id, max_id)
Shopify Cursor (page_info)
Elastic search_after Keyset over _score + _id

Where pagination shows up#

flowchart TB
  PG((Pagination<br/>strategies))
  REST[REST API design<br/>exposes to clients]
  DBS[Database sharding<br/>scatter-gather merge]
  CACHE[Caching strategies<br/>keyset is cache-friendly]
  SRCH[Search internals<br/>search_after pattern]
  REST --> PG
  PG --> DBS
  PG --> CACHE
  PG --> SRCH

    classDef client fill:#dbeafe,stroke:#1e40af,stroke-width:1px,color:#0f172a;
    classDef edge fill:#cffafe,stroke:#0e7490,stroke-width:1px,color:#0f172a;
    classDef service fill:#fef3c7,stroke:#92400e,stroke-width:1px,color:#0f172a;
    classDef datastore fill:#fee2e2,stroke:#991b1b,stroke-width:1px,color:#0f172a;
    classDef cache fill:#fed7aa,stroke:#9a3412,stroke-width:1px,color:#0f172a;
    classDef queue fill:#ede9fe,stroke:#5b21b6,stroke-width:1px,color:#0f172a;
    classDef compute fill:#d1fae5,stroke:#065f46,stroke-width:1px,color:#0f172a;
    classDef storage fill:#e5e7eb,stroke:#374151,stroke-width:1px,color:#0f172a;
    classDef external fill:#fce7f3,stroke:#9d174d,stroke-width:1px,color:#0f172a;
    classDef obs fill:#f3e8ff,stroke:#6b21a8,stroke-width:1px,color:#0f172a;
    class PG service;
    class REST,DBS,CACHE,SRCH datastore;

Glossary & fundamentals#

Tag Concept What it is Page
LLD REST API design where pagination lives in API design rest-api-design
HLD Database sharding pagination across shards needs scatter-gather database-sharding
HLD Caching strategies which strategies cache cleanly caching-strategies
HLD Search internals search_after and rank pagination search-internals

Quick reference#

Three patterns#

Pattern Best for Caveat
Offset Small data, admin UI O(N) deep pages; insert flicker
Keyset Large feeds, infinite scroll No jump-to-page-N
Cursor (opaque) Public APIs Operators can't introspect

Keyset recipe#

ORDER BY created_at DESC, id DESC
WHERE (created_at, id) < (:last_created_at, :last_id)
LIMIT n
Tiebreak on id to avoid flicker on equal timestamps.

Cursor token#

Sign + base64 the seek state. Server-only contract.

Total count#

  • Show "many" not exact
  • Materialized counter, refreshed periodically
  • Approx via EXPLAIN
  • HLL for unique-counts

Cross-shard#

Scatter-gather: query each shard with LIMIT n, merge top-n at coordinator. Cursor encodes per-shard position.

API conventions#

API Style
GitHub page+per_page, Link header
Stripe starting_after / ending_before
Twitter since_id / max_id
Shopify page_info
Elastic search_after

Refs#

  • Markus Winand - "no-offset"
  • Stripe pagination docs
  • Slack engineering - Evolving API pagination

FAQ#

Offset vs keyset pagination?#

Offset scans and discards rows up to the offset, getting slow on deep pages. Keyset uses a WHERE on the last sort key, running in O(log N) and staying fast at any depth.

What is cursor pagination?#

Cursor pagination returns an opaque token that encodes the position. The server decodes it on the next page so clients never compute offsets and pages stay stable under writes.

Why is offset pagination unstable?#

If a new row is inserted before the current offset between calls, the next page shifts and the user sees duplicates or skips. Keyset pagination avoids this entirely.

How do you paginate over multi-column sorts?#

Encode every column in the sort tuple as the keyset. The WHERE clause becomes a lexicographic compare, like (created_at, id) > (last_created_at, last_id).

Which strategy fits an infinite scroll feed?#

Cursor or keyset. Offset is unfit for endless scroll because deep pages get slower and the feed shifts under writes, breaking the user experience.

Further reading#