Pagination Performance

Definition

This topic ties together LIMIT/OFFSET (13.4-13.5) and Keyset Pagination (13.6) into a direct performance comparison, to build intuition for why one degrades with depth and the other doesn't.

Why OFFSET Gets Slower With Depth

Conceptually, LIMIT n OFFSET m asks the database to:

1. Produce the ordered stream of matching rows.
2. Walk past (and discard) the first m of them.
3. Return the next n.

Step 2's cost is proportional to m. So on a products-like table with, say, 5,000,000 rows:

sql
-- Page 1: cheap. Skip 0 rows.
SELECT id, name FROM products ORDER BY id LIMIT 20 OFFSET 0;

-- Page 50,000: expensive. Must walk past 999,980 rows first.
SELECT id, name FROM products ORDER BY id LIMIT 20 OFFSET 999980;

Even with an index on id making the scan itself efficient, the engine still has to traverse and count off nearly a million index entries before it can start emitting the 20 you want. Roughly speaking, OFFSET-based pagination cost grows linearly (O(m)) with the offset, so time-per-page keeps climbing the deeper a user pages in — noticeable as "page 1 loads instantly, page 500 takes 3 seconds."

Why Keyset Pagination Stays Fast

Keyset pagination instead asks:

sql
SELECT id, name FROM products
WHERE id > 999980
ORDER BY id
LIMIT 20;

With an index on id, WHERE id > 999980 is answered by an index seek directly to the right leaf position — roughly O(log m) to locate the start point, then a cheap sequential read of just the 20 rows needed. It costs about the same whether 999980 represents page 2 or page 50,000, because the seek doesn't need to touch any of the rows before the target — it jumps straight there via the index structure, unlike OFFSET which must pass through each one.

Side-by-Side Intuition

Practical Guidance

• For small tables, or UIs that only ever show the first few pages (typical search results), LIMIT/OFFSET is simple and perfectly fine.
• For large tables, deep pagination, infinite scroll, or APIs consumed by other systems (which often page through everything), prefer keyset pagination.
• Always pair pagination with ORDER BY on an indexed column — an unindexed sort column makes both approaches slow, since the engine must first sort the entire table before it can apply LIMIT/OFFSET or the keyset filter efficiently.

Key Takeaways

• Q: What is the rough time complexity of LIMIT/OFFSET as OFFSET grows?

A: Roughly linear (O(m)) in the offset value — cost grows with how many rows must be skipped.

• Q: What is the rough time complexity of keyset pagination as depth grows?

A: Roughly constant regardless of depth (an O(log m) index seek to the start point, then a small, fixed read) — it doesn't degrade the deeper you page.

• Q: What single factor most determines whether either pagination style performs well?

A: Whether the sort/filter column is indexed.