Cursor-Based vs Keyset Pagination for Large Backfills

The backfill started at 4,000 rows per second and was supposed to finish in three hours. Twelve hours in it is crawling at 200 rows per second, the table is only 60% processed, and EXPLAIN on the batch query shows the database scanning and discarding millions of rows to fetch the next thousand. Nothing is locked, replication is healthy, the batch size has not changed — yet every page costs more than the last. The cause is almost always the pagination strategy: a loop that walks the table with LIMIT :n OFFSET :m degrades quadratically, because reaching offset m means re-scanning all m rows that precede it on every single page. Switching to keyset (cursor) pagination — WHERE id > :last_id ORDER BY id LIMIT :n — makes each page cost the same regardless of how deep into the table you are.

This page explains why OFFSET collapses on large tables, what keyset pagination requires from your indexes, and how to convert an existing backfill safely. It pairs with Tuning Backfill Batch Size Against Replication Lag: keyset gives you stable per-page cost, lag-aware batching keeps that cost from overwhelming replicas.

Symptom / Error Signatures

There is no error string. The signature is performance that decays as the job progresses.

• Per-batch latency rises monotonically — early batches return in milliseconds, later batches take seconds, even though batch size is constant.
• EXPLAIN (ANALYZE) on the batch query shows a large Rows Removed by Filter or a high actual rows on the scan node far exceeding the LIMIT, with the planner reading and discarding everything up to the offset.
• PostgreSQL plans show a Seq Scan or an index scan whose cost climbs with offset; MySQL EXPLAIN shows rows in the millions for a query that returns a thousand.
• Total backfill runtime balloons far past a linear extrapolation of the first hour.
• Rows get skipped or processed twice when concurrent writes shift offsets between pages — a correctness bug, not just a speed one.

The skip/duplicate symptom is the one that should alarm you most: OFFSET is not just slow, it is unstable under concurrent inserts and deletes, so a backfill that uses it can silently miss rows.

Root Cause Analysis

LIMIT :n OFFSET :m asks the database to produce the first m + n rows in order and then throw away the first m. There is no general way to “jump” to offset m — the engine must walk the ordering from the start each time. On page one it discards 0 rows; on page 10,000 with a batch of 1,000 it discards roughly 10,000,000 rows to return 1,000. The work per page grows linearly with depth, so the total work across the whole table grows quadratically. That is the entire performance story.

Keyset pagination replaces “skip m rows” with “start after the last key I saw.” Because the ordering column is indexed, the engine seeks directly to last_id in the index and reads forward n entries. It never re-scans the rows already processed. Every page costs one index seek plus n sequential index reads — constant, regardless of depth.

Keyset also fixes correctness. Because it anchors on a value (id > 84211) rather than a position (OFFSET 84000), inserts and deletes elsewhere in the table cannot make it skip or repeat rows. That stability is what lets a keyset backfill pause and resume safely, the same resumability the parent Backfill Optimization section depends on.

Immediate Mitigation

If a long-running OFFSET backfill is degrading right now, you do not have to discard the progress already made.

1. Find where it has reached. Identify the highest key value already processed — for an OFFSET loop this is the last row of the most recent committed batch.

2. Restart from that key with a keyset query. Convert the loop in place; the new query resumes from the recorded last_id.

-- PostgreSQL · run as the backfill role · safe to repeat; reads forward from a key
-- Requires an index on id (the primary key already provides one).
SELECT id, /* columns to backfill */
FROM   orders
WHERE  id > :last_id
ORDER  BY id
LIMIT  :batch;
-- After processing, set :last_id to the MAX(id) returned, then loop.

-- MySQL · run as the backfill role · same shape; PK index drives the seek.
SELECT id
FROM   orders
WHERE  id > :last_id
ORDER  BY id
LIMIT  :batch;

3. Persist last_id after every committed batch so a crash or a pause resumes exactly where it stopped, rather than recomputing an offset.

4. Verify the plan is a seek, not a scan. Confirm the engine is using the index before you let the job run unattended.

-- PostgreSQL · read-only · confirm an Index Scan with a low cost, no large discard
EXPLAIN (ANALYZE, BUFFERS)
SELECT id FROM orders WHERE id > 8400000 ORDER BY id LIMIT 1000;

5. Keep the lag controls. Faster pages mean a faster write rate, so the throttling from Tuning Backfill Batch Size Against Replication Lag matters more, not less, once keyset removes the artificial slowdown.

Permanent Fix / Long-Term Pattern

Make keyset the default shape for every backfill and bulk-iteration job. The loop carries a cursor, the query compares against it, and the cursor advances to the last key returned.

# Keyset backfill loop. Context: single worker, post-deploy, idempotent upsert per batch.
last_id = 0
BATCH   = 2000
while True:
    rows = db.query(
        "SELECT id FROM orders WHERE id > %s ORDER BY id LIMIT %s",
        (last_id, BATCH))
    if not rows:
        break
    upsert_region_code(rows)          # idempotent write
    last_id = rows[-1]["id"]          # advance the cursor
    persist_cursor(last_id)           # durable resume point

The index requirement is strict and easy to get wrong: the ORDER BY and the WHERE comparison must be on the same column(s), and that column must be indexed with the same ordering. A single-column cursor on the primary key is the simplest case — the PK index already satisfies it. If you must paginate by a non-unique column such as created_at, the cursor becomes a composite of (created_at, id) to break ties deterministically, and you need a matching composite index:

-- PostgreSQL · run in a low-write window · index supports keyset on (created_at, id)
-- CREATE INDEX CONCURRENTLY must run OUTSIDE a transaction; requires table owner.
CREATE INDEX CONCURRENTLY IF NOT EXISTS idx_orders_created_id
  ON orders (created_at, id);

-- The composite keyset comparison (PostgreSQL and MySQL 8.0 both support row values):
SELECT created_at, id
FROM   orders
WHERE  (created_at, id) > (:last_created, :last_id)
ORDER  BY created_at, id
LIMIT  :batch;

Pair keyset iteration with idempotent writes so a resumed batch never double-applies, exactly as Making Data Backfills Idempotent With Upserts prescribes. Together, keyset pagination and idempotent upserts give you a backfill that is fast at any depth, safe to pause, and safe to retry — the foundation the Optimizing Backfill Scripts for Zero-Downtime Deploys guide builds on.

Verification Checklist

• The batch query uses WHERE key > :last_key ... ORDER BY key LIMIT :n, with no OFFSET anywhere in the loop.
• An index exists on the cursor column(s) matching the ORDER BY, confirmed via EXPLAIN showing an index scan, not a sequential scan with a large discard.
• Per-batch latency is flat across the run — page one and page ten-thousand take the same time.
• The cursor is persisted after each committed batch so the job resumes from the exact key after a pause or crash.
• For non-unique sort columns, the cursor is a composite (sort_col, id) with a matching composite index, so no rows are skipped on ties.
• Each batch write is idempotent, so resuming and reprocessing the boundary row causes no duplicates.

Frequently Asked Questions

Why is OFFSET so much slower at the end of the table than the start? Because OFFSET m forces the database to generate and discard the first m ordered rows before returning the page. At offset zero it discards nothing; deep into the table it discards millions per page. The discarded work grows with depth, so total cost over the whole table is quadratic, while keyset stays linear by seeking straight to the last key.

Can keyset pagination skip rows if new rows are inserted during the backfill? No, and that is its advantage over OFFSET. Keyset anchors on a key value (id > 84211), so an insert with a higher id is simply picked up on a later page and an insert with a lower id was already processed. OFFSET anchors on a position, so a concurrent insert or delete shifts every subsequent page and can skip or duplicate rows.

What if there is no single unique column to paginate on? Use a composite cursor of the sort column plus a unique tiebreaker, typically (created_at, id), with a matching composite index and a row-value comparison (created_at, id) > (:last_created, :last_id). The unique tail guarantees a total ordering so the cursor never stalls or skips on duplicate sort values.

Does keyset pagination need a different index than my queries already use? It needs an index whose leading columns match the cursor’s ORDER BY. The primary key index covers an id-based cursor for free. Paginating by another column requires a dedicated index on that column (plus the unique tiebreaker), built with CREATE INDEX CONCURRENTLY or ALGORITHM=INPLACE so the build itself does not block traffic.