Expand-and-contract has added a nullable `tax_basis` column to a 420 million-row Postgres table, and the contract step cannot start until every row is populated. A single UPDATE would hold locks and bloat the table for hours. Estimate how long a batched backfill takes, and say which assumption dominates the error.

The assumptions, stated

• 420M rows, batch of 1,000 rows per transaction, sub-batches of 100 so a single statement is short.
• Each batch costs roughly 50–100 ms of database work including index maintenance.
• The table has four secondary indexes, two of which contain the updated column's row.
• The migration runs continuously but yields whenever the database says it is unhealthy.

The arithmetic

At one batch of 1,000 rows every 100 ms with no pauses, throughput is 10,000 rows/s and the job takes 420M / 10,000 = 42,000 s, about 12 hours.

That is the ceiling, and no production backfill achieves it, because the throttle is the point. Postgres updates are copy-on-write: each updated row writes a new heap tuple plus entries in every index whose value or page changes, so a 2 kB row can generate several kilobytes of WAL. At 10,000 rows/s that is tens of megabytes a second of WAL on top of normal traffic, which is where replicas start falling behind and autovacuum starts chasing dead tuples.

With a 50% duty cycle — the job paused half the time by health checks — the figure is 24 hours. At 2,000 rows/s sustained, 420M rows is 210,000 s, about 2.4 days.

The number and its range

Half a day in the best case, two to three days realistically, a week if the table is hot and the replica budget is tight. Plan for days and instrument it rather than predicting it.

Which assumption dominates

Not the per-batch cost. The duty cycle dominates, and the duty cycle is set by whichever health signal trips first. GitLab's documented batched background migration framework is a usable reference for what to watch: it pauses a migration when indicators trip — pending WAL, autovacuum running against the affected table, and the database apdex falling below its SLO — resumes after a wait, and resizes batches from the recent jobs' observed durations, with GitLab.com running several such migrations in parallel. The second-order effect is index count: adding one index to the updated row's write set can cut throughput by a third.

What the number rules out

A backfill measured in days cannot be a step inside a deployment, which is the mistake this estimate exists to kill. It is a background job with its own progress record, resumable from a cursor, writing idempotently so a retried batch is harmless. It also means the dual-shape window stays open for days to weeks, so scheduling the contract step in the same release is wrong: readers, batch consumers and mobile clients all have to be on the new shape first.

When not to backfill at all

When the new column can be derived on read. A COALESCE(tax_basis, legacy_expression) in the query, plus population on next write, removes the backfill entirely and costs a slightly more complex read path until the old rows age out. Choose the backfill when the column must be indexed or aggregated, when the derivation is expensive, or when a regulator needs the stored value. If none of those hold, the cheapest migration is the one you do not run.