Skip to content

CONCEPT Cited by 1 source

Offset pagination cost

The runtime cost of SELECT … ORDER BY key LIMIT N OFFSET M in most relational databases is proportional to M + N, not N. OFFSET is implemented as fetch the first M+N rows in order, then discard the first M — not as a seek into a sorted structure. This means every page the user paginates past has to be fully materialised by the database to be thrown away, and the work the database does for "page 100" is ~100× the work it does for "page 1."

(Source: sources/2026-04-21-planetscale-introducing-fastpage-faster-offset-pagination-for-rails-apps.)

Why the cost scales with M + N, not N

On a row-store database like MySQL with InnoDB's clustered-index layout:

SELECT * FROM posts
ORDER BY created_at DESC
LIMIT 25 OFFSET 100;

The execution is:

  1. Walk the secondary index on created_at in descending order.
  2. For each index entry, take the primary-key pointer in the index leaf and descend the clustered index to hydrate the full row (SELECT *).
  3. Discard the first 100 hydrated rows.
  4. Return the next 25.

The database paid for 125 secondary-index walks + 125 clustered-index lookups + 125 full-row hydrations to return 25 rows. For offset N, the count is M + N. At OFFSET 100,000 LIMIT 25 the database hydrates 100,025 full rows, throws away 100,000, and ships 25.

Empirical measurement

Coutermarsh's FastPage post benchmarks on a ~1M-row Rails Post table:

Query Time
Post.all.order(created_at: :desc).limit(25).offset(100) 1,228.7 ms
Same query with deferred join rewrite ~457.3 ms

The slow version is the baseline: it hydrates 125 full rows from the clustered index. The fast version hydrates only 25 — exactly the page size — after a thin index-only pre-scan to select the correct primary keys.

Coutermarsh's 2000-page benchmark sweep shows the baseline cost climbing steeply with depth while the deferred-join rewrite stays near-flat. The gap widens superlinearly because the unoptimised query's hydration cost is itself a function of offset depth.

Why this is counterintuitive

Developers tend to reason about LIMIT 25 OFFSET 100 as "give me 25 rows starting at position 100" and assume the database seeks to position 100. That intuition is wrong for most row stores:

  • There is no sorted structure to seek into unless there's an index whose order matches the ORDER BY.
  • Even with such an index, OFFSET is the skip-count operator, not a seek-key operator. The database still walks the index M + N entries.
  • Seeking by sort key — WHERE created_at < $last_seen_timestamp ORDER BY created_at DESC LIMIT 25 — is the operation the developer wanted, but that's cursor pagination, not offset pagination.

Three standard mitigations

  1. Cap the max page — many applications forbid paginating past page 100 (OFFSET 10,000) to bound worst-case cost. Simple but sacrifices UX for deep catalogs.
  2. Rewrite to cursor pagination — O(1) at any depth, but loses skip-to-arbitrary-page-N capability.
  3. Rewrite to deferred join — preserves offset UX, turns the full-row hydration cost into an index-only scan for the first M + N rows. Still O(M + N) but with a much smaller constant because no full rows are hydrated until the final LIMIT N.

The choice depends on the UX constraint:

UX needed Solution
"Next" / "Previous" buttons only cursor pagination (best)
"Go to page 47" (random access) deferred join (middle ground)
No deep pagination at all cap max page

Relationship to indexes

The cost can sometimes be reduced — not eliminated — by index design:

  • Covering index for the sort: if the sort column is indexed and the SELECT list is narrow, the query planner may avoid clustered-index lookups. This is the exact mechanism the deferred join forces when SELECT * precludes a natural covering-index plan.
  • Composite index matching the predicate + sort order: for WHERE owner = ? ORDER BY created_at DESC LIMIT N OFFSET M, a composite index on (owner, created_at) lets the planner walk a narrow contiguous slice of the index rather than scanning the whole created_at index and post-filtering by owner. The deferred-join first query leans on this.
  • Still O(M + N): none of these tricks change the asymptotic cost; they only lower the constant. For very deep pagination (OFFSET > 100k) you need a fundamentally different mechanism.

Seen in

Last updated · 378 distilled / 1,213 read