Batching a Backfill Without Holding Locks or Losing Restarts

A backfill that rewrites a column on ten million rows cannot run as one statement. A single UPDATE over the whole table holds row versions for every row it touches until commit, generates write-ahead log in proportion to the table, blocks vacuum from reclaiming anything for the duration, and holds its locks for as long as it takes. If it fails two hours in, the rollback is as expensive as the update was.

The alternative is to walk the table in key order, committing every few thousand rows, recording progress so that an interruption resumes rather than restarts. Each of those choices, the key order, the batch size, the commit frequency, and the progress record, has a failure mode that only shows up on a table large enough to matter.

Walk by key, not by offset

The natural batch boundary is a range of primary key values: read the next N keys greater than the last processed key, update those rows, record the new high-water mark, commit. The next batch starts from the recorded mark, so an interruption loses at most one batch of work.

The alternative, LIMIT n OFFSET m, degrades badly because the offset is not a position in the table’s storage but a count that must be skipped. Each batch rescans everything the previous batches already covered, so the total work is quadratic in the number of batches. It is also unstable: an insert or delete shifts every subsequent row’s offset, so the walk can skip rows or process them twice. Keyset pagination over an indexed, unique, immutable key avoids both problems.

A surrogate integer primary key is ideal for this. A UUIDv4 primary key is usable but hostile: the key order is random relative to physical order, so consecutive key ranges touch pages scattered across the whole file, defeating read-ahead and turning a sequential scan into a random one. If the primary key is random, batching by a different indexed column, a creation timestamp for instance, restores locality, at the cost of handling ties within the same timestamp value.

The query needs an index that supports the range and an ordering guarantee. In PostgreSQL, an index on the batching key gives an index scan whose ordering is deterministic for a given set of rows, and the update must be constrained to a key range rather than to a materialised list of identifiers, which would grow with the batch size.

-- step one: find the batch's boundaries, in key order
SELECT min(id), max(id)
  FROM (SELECT id FROM ledger_entries
         WHERE id > $1
         ORDER BY id
         LIMIT $2) AS batch;

-- step two: update exactly that range, skipping rows already correct
UPDATE ledger_entries
   SET currency_code = upper(currency_code)
 WHERE id > $1
   AND id <= $3                 -- max(id) from step one
   AND currency_code <> upper(currency_code);

Two statements rather than one because the boundaries are needed for the progress record: the batch commits with $3 written as the new high-water mark, so the next batch starts strictly after the last row this one touched. Keys need not be contiguous, so a range that spans gaps still covers every row that exists between its endpoints.

The trailing predicate does two things. It makes the batch cheap when it encounters rows that are already correct (the common case after a restart that re-processes the last batch) and it makes the statement idempotent, since running it twice produces the same result. Without it, every row in the range is written on every pass, doubling the write volume and the log.

Batch size is a lock-duration decision

The batch size sets how long each transaction holds its row locks, how much log a single transaction produces, and how much work a crash discards. There is no universally correct value; the reasoning that picks one is about lock contention with the application.

A backfill that touches rows the application also writes will conflict with it. Each conflicting pair means one side waits, and if the backfill’s transaction is long, the application waits for the whole transaction. Small batches bound that wait: a batch of a thousand rows holds its locks for the time it takes to update a thousand rows, which on an indexed range is milliseconds to a low number of seconds depending on the conversion’s cost. A batch of a million holds them for minutes and produces exactly the stall that the batching was meant to avoid.

Small batches, conversely, increase total overhead. Each transaction pays commit cost, a log flush in the default configuration, and each batch re-descends the index to find its starting point. A throughput-maximising batch is larger than a contention-minimising one, and the operational choice is the smaller of the two, adjusted by observing lock waits rather than by picking a number in advance.

The commit frequency should equal the batch frequency: one transaction per batch, committed immediately. Holding several batches in one transaction defeats the purpose of batching, since the row locks and the log volume accumulate across all of them.

Throttling, and what it actually protects

A backfill running flat out will consume I/O bandwidth and buffer pool space that the application needs, and on a replicated primary it will push a volume of log that the standbys must apply. The same log volume is what makes an idle replication slot expensive, as described in replication slots and WAL retention. Three throttles address different parts of the load.

A pause between batches bounds the duty cycle: sleeping for the same duration as the batch took halves the average load. It is crude but predictable, and it is the only throttle that works when the bottleneck is on a resource the database cannot measure, such as a shared storage layer’s throughput budget.

A replication-lag check pauses when standbys fall behind a threshold. On a streaming-replication system the primary can read the current replay position of each standby and compare it with its own write position; when the gap exceeds the threshold, the backfill sleeps. This is the throttle that matters most, because a backfill’s log volume is its main side effect on the rest of the system.

A statement timeout bounds any single batch’s execution, converting a pathological batch, such as an unexpectedly slow conversion or a lock wait, into a retryable failure. Combined with a retry limit per range, it prevents one bad batch from wedging the job.

Progress, restarts, and the concurrency window

The progress record can be a row in a job table, a separate small table keyed by job name, or an external store. Wherever it lives, it must be written in the same transaction as the batch it describes, or the two can disagree: a crash after the update but before the progress write re-runs a batch (harmless if idempotent), while a crash after the progress write but before the update skips a range permanently. The second failure is silent and unrecoverable without a verification pass, so the progress write belongs inside the batch’s transaction.

The concurrency window is the interval between the batch’s read and its write, during which the application can modify the same rows. Three cases arise, and they need different handling.

A row updated by the application between the read and the write receives the backfill’s value, which was computed from the pre-update contents. If the application’s write also set the target column correctly, the backfill’s write is wrong. Restricting the update to rows whose source column is unchanged by comparing the old value in the WHERE clause, closes the window at the cost of a predicate on every batch.

A row inserted during the backfill with a key below the current high-water mark is never visited. This happens with random keys, with backdated timestamps, and with any key the application can choose. Either the backfill’s range covers the whole key space at the end with a verification pass, or the application writes the target column itself from the moment the backfill starts, which is the dual-write phase of expand and contract and is the reason the two mechanisms are always used together.

A row deleted during the backfill is simply absent from the next read, which is correct and requires no handling.

Verifying that the backfill finished

The job’s own progress record says it reached the end of the key space. That is not the same as every row being correct, because of the concurrency window and because a failed batch may have been skipped after exceeding its retry limit.

The check is a count of rows that still violate the target invariant: rows where the source column has a value and the target does not match its conversion. On a large table this count is itself a full scan, which is why it runs as a separate pass after the backfill and after traffic has quieted, and why it is the operation that most benefits from being run on a replica rather than the primary. A non-zero count is then repaired by re-running the backfill with the range narrowed to the offending keys, which is the same code with a different starting point.

The invariant to check must be expressible as a predicate the database can evaluate in one pass. If the conversion is a function the database cannot compute, such as a transformation implemented only in application code, then verification requires reading every row out, which changes the cost model entirely and usually argues for expressing the conversion as a database expression in the first place.

The pattern that generalises

The same shape applies to any bulk data operation that must run against a live system: deleting a large fraction of a table’s rows, moving rows to a new partition, populating a materialised column, or rewriting a value in place. The components are always a stable ordered key, a bounded batch, a transaction per batch, a progress record inside that transaction, a throttle tied to the resource that is actually scarce, and a verification pass that does not trust the progress record. What changes is the predicate and the index that supports it, and whether the batch can be made idempotent at all, which for some operations, notably appends and counter increments, it cannot without an additional record of what has already been done.