Is it true that Adding an index on the sorted column makes `OFFSET 100000` fast?

Indexes speed up the ordering, but the database must still count and traverse past the first 100,000 indexed pointers before returning records. B-Tree indexes do not contain row-position offsets; traversing 100,000 entries requires $O(N)$ index-block reads.

Is it true that Cursor pagination makes it easy to jump directly to an arbitrary page, like page 42?

Cursor pagination only supports sequential traversal (next and previous relative to a known boundary). Without scanning or knowing intermediate row identifiers, the system cannot compute where page 42 begins without an offset.

Is it true that Sorting by `created_at` with a cursor is sufficient for deterministic pagination?

Non-unique sort keys produce duplicate or missing records across pages unless a unique column like `id` is included as a secondary sort key. Multiple rows can share the exact same timestamp down to the millisecond, causing the `>` or `<` boundary to skip rows sharing that timestamp.

Pagination

Offset vs cursor — and why page 5000 of your admin table times out.

25 minDifficulty 2/5api · performanceAI-written

Before this

REST API Design — Resources, not verbs — designing an interface another team can use without asking you questions.

Why this exists

Fetching page one with `LIMIT 20 OFFSET 0` is instantaneous, but fetching page 5,000 with `OFFSET 100000` causes database timeouts. Relational databases must scan and discard all 100,000 preceding rows before returning the 20 you asked for. In high-write systems, offset pagination also causes duplicate or skipped records when rows are inserted or deleted while a user navigates.

The mental model

Offset pagination is like opening a book by counting every single page from page one until you reach page 500. Cursor pagination is like dropping a bookmark at page 500 so you can flip directly to it next time.

How it works

The Cost of Offset Scanning

SQL queries using `OFFSET N` force the engine to traverse the index or table to find $N$ rows, materialize them, and then discard them before reading the target `LIMIT`. As $N$ grows, execution time scales linearly with $O(N)$ read overhead and excessive disk I/O.

Pagination Drift Under Concurrent Writes

Offset pagination is stateless across requests. If a new row is inserted at index 0 while a user moves from page 1 (`OFFSET 0`) to page 2 (`OFFSET 10`), the item previously at index 9 shifts to index 10 and appears again on page 2. Conversely, deletions cause rows to be skipped.

Keyset and Cursor Pagination

Cursor-based pagination (keyset pagination) replaces offsets with a `WHERE` condition on a sequential, indexed column, such as `WHERE id > :last_seen_id ORDER BY id ASC LIMIT 20`. The database utilizes the B-Tree index to seek directly to the cursor in $O(\log N)$ time, ignoring preceding rows entirely.

Opaque Tokens and Multi-Column Cursors

To prevent clients from coupling to database schema details, APIs serialize cursor criteria (e.g., `created_at` timestamp and tie-breaker `id`) into opaque strings (like base64-encoded JSON). If sorting by non-unique columns, the cursor must include a unique tie-breaker column to guarantee deterministic order.

The mechanism

1. Client makes an initial request: `GET /api/items?limit=20`. 2. Server executes `SELECT * FROM items ORDER BY created_at DESC, id DESC LIMIT 21` (fetching `limit + 1` to check for a next page). 3. Server returns 20 items, generates an encoded cursor from the 20th item's `(created_at, id)`, and sets `has_more = true`. 4. Client requests page 2: `GET /api/items?limit=20&cursor=eyJjcmVhdGVkX2F0Ijox...`. 5. Server decodes the cursor and queries: `SELECT * FROM items WHERE (created_at, id) < (:last_created_at, :last_id) ORDER BY created_at DESC, id DESC LIMIT 21` using a composite index `(created_at, id)`. 6. The database performs an index seek directly to the tuple boundary, returning results in constant time regardless of total table depth.

sequenceDiagram
  autonumber
  Client->>Server: GET /items?limit=20
  Server->>Database: SELECT * FROM items ORDER BY id ASC LIMIT 21
  Database-->>Server: 21 rows
  Server-->>Client: 20 items + next_cursor ("id:20")
  Client->>Server: GET /items?limit=20&cursor=id:20
  Server->>Database: SELECT * FROM items WHERE id > 20 ORDER BY id ASC LIMIT 21
  Database-->>Server: 21 rows (via Index Seek)
  Server-->>Client: 20 items + next_cursor ("id:40")

Diagram source for Pagination.

What people get wrong

Adding an index on the sorted column makes `OFFSET 100000` fast.: Indexes speed up the ordering, but the database must still count and traverse past the first 100,000 indexed pointers before returning records. B-Tree indexes do not contain row-position offsets; traversing 100,000 entries requires $O(N)$ index-block reads.
Cursor pagination makes it easy to jump directly to an arbitrary page, like page 42.: Cursor pagination only supports sequential traversal (next and previous relative to a known boundary). Without scanning or knowing intermediate row identifiers, the system cannot compute where page 42 begins without an offset.
Sorting by `created_at` with a cursor is sufficient for deterministic pagination.: Non-unique sort keys produce duplicate or missing records across pages unless a unique column like `id` is included as a secondary sort key. Multiple rows can share the exact same timestamp down to the millisecond, causing the `>` or `<` boundary to skip rows sharing that timestamp.

When not to use it

Admin tables requiring jumping directly to arbitrary page numbers (e.g., 'Go to Page 15').: Offset pagination (with strict max limits like page <= 100) or estimated total counts.
Static or small lookup tables (e.g., fewer than 1,000 rows) with no concurrent writes.: Standard offset pagination or loading the entire dataset into client memory.
Complex multi-facet search systems where sort orders change dynamically across dozens of unindexed attributes.: Search engines like Elasticsearch using `search_after` tokens or point-in-time (PIT) snapshots.

Terms

Offset Pagination: — A pagination technique that skips a specified number of records using database offset clauses before returning the requested page size.
Cursor / Keyset Pagination: — A pagination technique that fetches records after a specific known reference value (such as an ID or timestamp) using an indexed filter.
Index Seek: — A database operation where the engine navigates a B-Tree index directly to matching rows in O(log N) time rather than scanning through multiple records.
Pagination Drift: — The phenomenon where items are duplicated or skipped across pages due to concurrent inserts or deletes during pagination.

Can you recall it?

Why does `OFFSET 50000 LIMIT 10` perform poorly in relational databases, and how does keyset pagination resolve it?

Show the answer and its key points

OFFSET forces O(N) scanning and discarding of previous rows
High disk I/O and CPU overhead at high offsets
Keyset pagination uses WHERE clauses on indexed columns
Enables O(log N) direct B-Tree index lookups

Offset requires the database to scan and discard 50,000 rows before returning 10. Keyset pagination replaces the offset with an indexed filter condition (e.g., `WHERE id > last_seen_id`), allowing the database to seek directly to the starting row in logarithmic time.

Indexes & Query Plans — Why one query is 2ms and the identical-looking one is 8 seconds — read the plan.