Pagination and N+1

Why OFFSET gets slower every page, keyset pagination, and replacing many small queries with one.

Draft. This page is new and has not yet been reviewed by a second person. Every query output on it was produced by a real run on PostgreSQL 18.6 (PGlite 0.5.9). If something looks wrong, report it.

Before thisB-tree indexes
On this page
  1. OFFSET pagination gets slower every page
  2. Keyset pagination stays fast
  3. At production scale
  4. The N+1 query problem
  5. In MySQL
  6. Sources

Two patterns make otherwise reasonable applications slow in exactly the same way: they ask the database to do work it then throws away, or to do the same small job hundreds of times. Both are invisible on a developer's laptop with ten rows and obvious in production with ten million.

OFFSET pagination gets slower every page#

The usual way to show page n of a list is LIMIT 20 OFFSET 20 × n. OFFSET does not jump: the database produces every skipped row and discards it. Even with an index on the sort column, page 2,500 walks 50,000 index entries first.

sql
create index orders_created_at_idx on orders (created_at);
sql
select id, created_at, total from orders
order by created_at desc
limit 20 offset 50000;
Plan, executed real output from PostgreSQL 18.6 (PGlite 0.5.9). Timings depend on the machine; the shape and the row counts do not
Limit  (cost=1708.79..1709.48 rows=20 width=18) (actual time=33.333..33.351 rows=20.00 loops=1)
  Buffers: shared hit=406 read=139
  ->  Index Scan Backward using orders_created_at_idx on orders  (cost=0.29..3417.29 rows=100000 width=18) (actual time=0.020..23.182 rows=50020.00 loops=1)
        Index Searches: 1
        Buffers: shared hit=406 read=139
Planning:
  Buffers: shared hit=17 read=1
Planning Time: 0.228 ms
Execution Time: 33.375 ms

Keyset pagination stays fast#

Instead of counting rows, remember where the last page ended and ask for the rows after it. With an index on the sort key this is one descent and twenty entries, whatever the page.

sql
select id, created_at, total from orders
where created_at < '2023-12-31 14:10:51+00'
order by created_at desc
limit 20;
Plan, executed real output from PostgreSQL 18.6 (PGlite 0.5.9). Timings depend on the machine; the shape and the row counts do not
Limit  (cost=0.29..1.03 rows=20 width=18) (actual time=0.020..0.041 rows=20.00 loops=1)
  Buffers: shared hit=3
  ->  Index Scan Backward using orders_created_at_idx on orders  (cost=0.29..1835.29 rows=50000 width=18) (actual time=0.018..0.031 rows=20.00 loops=1)
        Index Cond: (created_at < '2023-12-31 14:10:51+00'::timestamp with time zone)
        Index Searches: 1
        Buffers: shared hit=3
Planning Time: 0.134 ms
Execution Time: 0.064 ms

At production scale#

At production scale: Half way through ten million orders, by OFFSET and by keyset 2,000,000 users and 10,000,000 orders, recorded on PostgreSQL 18.3 on 2026-10-21. Each plan is the second of two runs, so the data was already in memory.
create index orders_created_at_idx on orders (created_at);

OFFSET 5,000,000

select id, created_at, total from orders
order by created_at desc
limit 20 offset 5000000;
Limit  (cost=170298.93..170299.62 rows=20 width=18) (actual time=987.701..987.707 rows=20.00 loops=1)
  Buffers: shared hit=54118
  ->  Index Scan Backward using orders_created_at_idx on orders  (cost=0.43..340597.43 rows=10000000 width=18) (actual time=0.044..828.924 rows=5000020.00 loops=1)
        Index Searches: 1
        Buffers: shared hit=54118
Planning Time: 0.081 ms
JIT:
  Functions: 4
  Options: Inlining false, Optimization false, Expressions true, Deforming true
  Timing: Generation 0.219 ms (Deform 0.079 ms), Inlining 0.000 ms, Optimization 0.155 ms, Emission 1.928 ms, Total 2.302 ms
Execution Time: 988.022 ms

The same page by keyset

select id, created_at, total from orders
where created_at < '2023-12-31 14:00:10.3+00'
order by created_at desc
limit 20;
Limit  (cost=0.43..1.17 rows=20 width=18) (actual time=0.034..0.044 rows=20.00 loops=1)
  Buffers: shared hit=4
  ->  Index Scan Backward using orders_created_at_idx on orders  (cost=0.43..182597.33 rows=4994394 width=18) (actual time=0.032..0.039 rows=20.00 loops=1)
        Index Cond: (created_at < '2023-12-31 14:00:10.3+00'::timestamp with time zone)
        Index Searches: 1
        Buffers: shared hit=4
Planning Time: 0.151 ms
Execution Time: 0.068 ms

Half way through ten million orders, OFFSET walked 5,000,020 index entries over 54,118 pages to return 20 rows, which took about a second. The keyset query read 4 pages in less than a tenth of a millisecond, exactly what it costs on the first page. OFFSET's cost keeps growing with the page number; keyset's does not.

Rules for keyset pagination:

  • The sort key must be unique. If it is not, add the primary key to it and compare both: where (created_at, id) < ($1, $2) order by created_at desc, id desc. PostgreSQL compares such row values element by element, and an index on (created_at, id) serves it directly.
  • You get "next" and "previous", not "jump to page 2,500". For a feed, an inbox or an infinite scroll that is what users do anyway.
  • It is stable. New rows arriving while someone pages do not shift every later page by one, which OFFSET does.

The N+1 query problem#

Code that loads a list and then, for each item, issues another query makes 1 + N round trips:

text
users = query("select id, email from users where country = 'NG' limit 50")
for user in users:
    orders = query("select count(*) from orders where user_id = ?", user.id)

Each query may be fast, but 50 round trips to the database, each with its own network latency, parsing and planning, add up. The database cannot help: it only ever sees one small query at a time. ORMs produce this pattern easily when they load related objects lazily.

Ask for everything in one query instead, with a join:

sql
select u.id, u.email, count(o.id) as orders
from users u
left join orders o on o.user_id = u.id
where u.country = 'NG'
group by u.id, u.email
order by u.id
limit 50;
Plan, executed real output from PostgreSQL 18.6 (PGlite 0.5.9). Timings depend on the machine; the shape and the row counts do not
Limit  (cost=2562.47..2562.60 rows=50 width=33) (actual time=55.340..55.377 rows=50.00 loops=1)
  Buffers: shared hit=1019
  ->  Sort  (cost=2562.47..2563.43 rows=383 width=33) (actual time=55.339..55.354 rows=50.00 loops=1)
        Sort Key: u.id
        Sort Method: top-N heapsort  Memory: 23kB
        Buffers: shared hit=1019
        ->  HashAggregate  (cost=2545.92..2549.75 rows=383 width=33) (actual time=54.969..55.158 rows=383.00 loops=1)
              Group Key: u.email
              Batches: 1  Memory Usage: 72kB
              Buffers: shared hit=1019
              ->  Hash Right Join  (cost=463.79..2536.34 rows=1915 width=29) (actual time=2.535..53.789 rows=1896.00 loops=1)
                    Hash Cond: (o.user_id = u.id)
                    Buffers: shared hit=1019
                    ->  Seq Scan on orders o  (cost=0.00..1810.00 rows=100000 width=8) (actual time=0.004..23.816 rows=100000.00 loops=1)
                          Buffers: shared hit=810
                    ->  Hash  (cost=459.00..459.00 rows=383 width=25) (actual time=2.508..2.509 rows=383.00 loops=1)
                          Buckets: 1024  Batches: 1  Memory Usage: 23kB
                          Buffers: shared hit=209
                          ->  Seq Scan on users u  (cost=0.00..459.00 rows=383 width=25) (actual time=0.014..2.353 rows=383.00 loops=1)
                                Filter: (country = 'NG'::text)
                                Rows Removed by Filter: 19617
                                Buffers: shared hit=209
Planning:
  Buffers: shared hit=12
Planning Time: 0.303 ms
Execution Time: 55.435 ms

Or, when the code already holds the ids, fetch the related rows for all of them in one query with = any(array):

sql
create index orders_user_id_idx on orders (user_id);
sql
select user_id, count(*) from orders
where user_id = any(array[383, 1907, 2401, 5160, 7711])
group by user_id;
Plan, executed real output from PostgreSQL 18.6 (PGlite 0.5.9). Timings depend on the machine; the shape and the row counts do not
GroupAggregate  (cost=0.29..26.14 rows=21 width=12) (actual time=0.086..0.124 rows=5.00 loops=1)
  Group Key: user_id
  Buffers: shared hit=5 read=6
  ->  Index Only Scan using orders_user_id_idx on orders  (cost=0.29..25.82 rows=21 width=4) (actual time=0.059..0.097 rows=33.00 loops=1)
        Index Cond: (user_id = ANY ('{383,1907,2401,5160,7711}'::integer[]))
        Heap Fetches: 0
        Index Searches: 5
        Buffers: shared hit=5 read=6
Planning:
  Buffers: shared hit=7 read=1
Planning Time: 0.362 ms
Execution Time: 0.160 ms

Index Searches (PostgreSQL 18) shows one descent per id, all inside one query and one round trip.

The same thing happens inside SQL when a subquery in the select list runs once per row; the subquery per row exercise shows it. ORMs have fixes for it under names like eager loading, includes, select_related / prefetch_related or JOIN FETCH.

In MySQL#

Not run here; from the MySQL reference manual. LIMIT offset, count has the same cost as in PostgreSQL: the skipped rows are still read. Keyset pagination and row-value comparisons such as (created_at, id) < (?, ?) work in MySQL too, and the N+1 problem is a property of the application, not of the database.

Sources#

Esc
↑ ↓ to move↵ to open