Online Schema Change at Scale — Expand-Contract, Batched Backfill & Shadow Tables

An online schema change works because you never ask the database to do one big, blocking thing on a live table. You decompose the change into steps that are each either metadata-only (a catalog edit that touches no rows) or bounded and interruptible (a small batch, or a scan that does not block writes). The naive single statement — ALTER TABLE users ADD COLUMN ... NOT NULL DEFAULT (something) ; CREATE INDEX ... — fails not because it is slow, but because of how it is slow: it grabs a lock that sits at the head of the table's lock queue and blocks every reader and writer behind it while it rewrites or scans hundreds of millions of rows. The whole discipline below exists to keep every lock either instant or short, and every scan off the critical path.

The mechanism you must be able to draw: lock-queue amplification

A rewriting or scanning DDL statement in PostgreSQL takes an ACCESS EXCLUSIVE lock on the table — the strongest lock there is, conflicting with every other lock mode, including the ACCESS SHARE that a plain SELECT takes. On its own that would only block for as long as the rewrite runs. The real danger is subtler and is what turns a "quick migration" into an outage.

Lock requests are granted roughly FIFO, and — this is the crucial rule — a new request must wait behind any already-waiting request that conflicts with it. So picture a reporting SELECT that has been scanning users for 40 seconds, holding ACCESS SHARE. Your ALTER arrives, requests ACCESS EXCLUSIVE, conflicts with that SELECT, and parks at the head of the queue. Now every query that arrives after your ALTER — even a 1 ms primary-key lookup that would happily run alongside the reporting SELECT — must queue behind the waiting ALTER, because it conflicts with that. One long-running read plus one DDL statement silently freezes the entire table. Connections pile up, the pool exhausts, and the application starts erroring everywhere, even though your DDL "should" have been instantaneous.

Two independent failure axes fall out of this, and you must separate them: (1) how long the lock is held (a table rewrite or non-concurrent index build holds it for the whole operation — minutes), and (2) how long the DDL waits to acquire the lock (which, if unbounded, lets it park at the head of the queue and amplify). A safe migration attacks both: pick statement forms that hold the lock only momentarily, and always cap the wait with lock_timeout so a blocked DDL fails fast and retries rather than freezing the table.

Expand–contract (parallel change): the shape of every safe migration

The governing idea is to keep the old and new schema shapes coexisting so that at no instant does a running application version depend on a change that hasn't fully landed. You only ever add before you remove, and you sequence it so each step is independently deployable and reversible:

1. Expand — make purely additive schema changes: add the new nullable column (or the new table shape), add the new index. Nothing reads the new structure yet; old code is untouched.
2. Backfill — populate the new column for existing rows in bounded, throttled batches (below). This is the long part, but it runs entirely off the lock critical path.
3. Dual-write / start populating — deploy application code that writes both old and new (or a DB default / trigger keeps the new column current), so new rows and updates stay correct while the backfill catches the tail. Once backfill + dual-write overlap, the new column is fully trustworthy; now you can validate constraints and flip NOT NULL.
4. Contract — swap reads to the new column, then, in a later deploy, drop the old column / old table / temporary constraint. Destructive steps come last, after you are certain nothing reads the old shape.

The reason this is safe is that every arrow between phases is a separate, small, reversible deploy. If phase 3 misbehaves you roll back the app without touching the schema; if you abort entirely, the additive column is harmless.

PostgreSQL specifics — which statement form is cheap, and why

The whole game in native Postgres is choosing forms that stay metadata-only or off the write path. The four you must know cold:

• ADD COLUMN with no default, or a non-volatile constant default, is metadata-only (PG 11+). Postgres records the default in the catalog (attmissingval) and materializes it lazily on read; no table rewrite. So ADD COLUMN flag boolean NOT NULL DEFAULT false is fast even on 500M rows. But a volatile default rewrites the whole table under ACCESS EXCLUSIVE: ADD COLUMN id uuid DEFAULT gen_random_uuid() or ... DEFAULT clock_timestamp() must compute a distinct value per row, so every row is rewritten. Same trap for ALTER COLUMN ... TYPE that isn't binary-coercible.
• CREATE INDEX CONCURRENTLY builds the index without an ACCESS EXCLUSIVE lock — it takes only SHARE UPDATE EXCLUSIVE, so reads and writes continue throughout. The cost: it does two passes over the table and waits out concurrent transactions, so it is slower in wall-clock and cannot run inside a transaction block. If it fails midway (e.g., a unique violation or a cancelled session) it leaves an INVALID index behind that still consumes write overhead; you must DROP INDEX CONCURRENTLY and rebuild. Always check pg_index.indisvalid after.
• ADD CONSTRAINT ... NOT VALID then VALIDATE CONSTRAINT splits a foreign key or check constraint into a cheap part and a slow part. ADD ... NOT VALID takes a brief lock and only enforces the constraint on new/changed rows. VALIDATE CONSTRAINT then scans existing rows under SHARE UPDATE EXCLUSIVE — slow, but it does not block reads or writes. Doing it in one step instead scans the whole table under ACCESS EXCLUSIVE.
• Always set a short lock_timeout for DDL: SET lock_timeout = '2s'; (and often a matching statement_timeout). This is the single most important operational habit — it converts "park at the head of the queue and freeze the table" into "fail fast, release, retry in a moment." Wrap DDL in a retry loop that backs off and re-attempts; each attempt only grabs the lock when the table is momentarily quiet.

Adding NOT NULL without a full-table lock

Setting NOT NULL on an existing column naively (ALTER COLUMN ... SET NOT NULL) forces a full sequential scan to prove no nulls exist — under ACCESS EXCLUSIVE the whole time. On a 500M-row table that is a multi-minute outage. The safe path (PG 12+) launders the scan through a validated check constraint:

-- 1. cheap: only new/changed rows are checked, brief lock
ALTER TABLE users ADD CONSTRAINT ev_not_null
  CHECK (email_verified IS NOT NULL) NOT VALID;

-- 2. slow scan, but SHARE UPDATE EXCLUSIVE — reads & writes keep flowing
ALTER TABLE users VALIDATE CONSTRAINT ev_not_null;

-- 3. now SET NOT NULL can reuse the proven constraint and SKIP the scan;
--    it still takes ACCESS EXCLUSIVE, but only for an instant
ALTER TABLE users ALTER COLUMN email_verified SET NOT NULL;

-- 4. optional: drop the now-redundant check constraint
ALTER TABLE users DROP CONSTRAINT ev_not_null;

Batched backfill: the template that won't take the database down

The backfill is where an unwary engineer causes the most damage — not with a lock, but with one enormous UPDATE. A single UPDATE users SET email_verified = ... over 500M rows is one giant transaction that (a) generates enormous WAL and table bloat (MVCC leaves 500M dead tuples), (b) holds the xmin horizon open for its entire duration, which stalls autovacuum cluster-wide so dead tuples pile up everywhere, and (c) ships as one huge chunk to replicas, blowing replication lag into minutes. It may also just run out of disk on WAL.

The fix is to walk the primary key in bounded ranges — keyset pagination, never OFFSET (OFFSET re-scans and re-discards a growing prefix each batch, turning an O(n) job into O(n²)). Each batch is its own short transaction; between batches you sleep and check replication lag so the backfill yields to production traffic and lets autovacuum reclaim the dead tuples you just made:

-- one batch: bounded, resumable from :last_id, idempotent
WITH batch AS (
    SELECT id
    FROM   users
    WHERE  id > :last_id
      AND  email_verified IS NULL      -- only untouched rows → re-runnable
    ORDER  BY id
    LIMIT  5000                        -- bound txn size, not by OFFSET
)
UPDATE users u
SET    email_verified = (u.confirmed_at IS NOT NULL)
FROM   batch b
WHERE  u.id = b.id
RETURNING u.id;                        -- driver takes MAX(id) as next :last_id

last_id = 0
loop:
    rows = run_batch(last_id)          # the query above
    if rows is empty: break            # done — no rows > last_id remain
    last_id = max(r.id for r in rows)  # keyset cursor advances
    sleep(50ms)                        # throttle: give prod traffic air
    while replication_lag() > 5s:      # bound lag; let replicas catch up
        sleep(1s)

Four properties make this safe and operable: bounded transaction size (5k rows → small WAL chunks, short-lived snapshots, autovacuum keeps up), keyset cursor (index-seek to id > :last_id, no re-scan), idempotent + resumable (the IS NULL guard means a crashed backfill restarts from last_id and re-running a batch is a no-op), and throttled (the sleep + lag check turn a stampede into a background trickle you can pause or speed up by tuning the two knobs).

Worked example: add NOT NULL email_verified BOOLEAN + an index to a 500M-row users table, at 3pm, no downtime

Say email_verified must be true where the existing confirmed_at is set, and you need an index on (email_verified, created_at) for a new query.

The naive plan and exactly how it fails:

ALTER TABLE users ADD COLUMN email_verified boolean NOT NULL DEFAULT false;
UPDATE users SET email_verified = true WHERE confirmed_at IS NOT NULL;
CREATE INDEX idx_users_ev ON users (email_verified, created_at);

• Line 1 is actually fine on modern Postgres (constant default = metadata-only) — but with no lock_timeout, if a long report is running it parks at the queue head and freezes the table (the diagram above).
• Line 2 is the killer: one UPDATE over ~half the rows = one giant transaction → xmin horizon pinned, autovacuum stalls, 250M dead tuples, WAL flood, replicas minutes behind.
• Line 3 (CREATE INDEX, non-concurrent) takes a SHARE lock and holds it for the entire multi-minute build — it conflicts with ROW EXCLUSIVE, so all writes to users block the whole time (reads, which need only ACCESS SHARE, still run). For a write-heavy table that is still an effective outage.

The safe plan, step by step, with the lock each step holds:

No step holds a strong lock for more than milliseconds, and no step is one giant transaction. The 500M-row work (backfill, index build, validation) all happens under weak locks that let production keep serving.

Shadow-table tools: gh-ost and pt-online-schema-change

MySQL's native online DDL is patchier than Postgres's (some ALTERs still copy the table under lock, behavior varies by engine and version), so the ecosystem built external tools that make the copy explicit and controllable. Both pt-online-schema-change (Percona Toolkit) and gh-ost (GitHub) follow the same shape:

1. Create an empty shadow (ghost) table with the new schema already applied.
2. Keep it in sync with live writes to the original — this is where they differ: pt-osc installs triggers (AFTER INSERT/UPDATE/DELETE) on the original that mirror every change into the shadow table synchronously; gh-ost tails the binlog instead, applying changes asynchronously with no triggers on the hot path.
3. Backfill existing rows into the shadow table in chunks, throttling on replica lag.
4. When the shadow table has caught up, do an atomic RENAME cutover (original → _old, shadow → original in one statement), then drop the old table.

The difference matters operationally. pt-osc's triggers add synchronous write amplification to every production write for the whole migration and can interact badly with existing triggers; gh-ost's binlog approach keeps the hot path clean, throttles more gracefully, and can be paused/tested against a replica — but requires row-based binlog and a bit more setup. Both have foreign-key limitations: FKs referencing the table being changed are notoriously fragile under the rename swap, and often need manual handling or an --alter-foreign-keys-method workaround. You reach for these when you are on MySQL, or when even Postgres's native path is awkward (e.g., a type change that would rewrite, on a table too large to babysit).

Pitfalls checklist (each has caused a real outage)

• Volatile / computed default rewrites the table. A constant default is free; gen_random_uuid(), now(), or a per-row expression rewrites all rows under ACCESS EXCLUSIVE. Add the column nullable, then backfill.
• Plain CREATE INDEX blocks writes for the entire build. Use CONCURRENTLY; verify the result is VALID; be ready to DROP INDEX CONCURRENTLY and retry on failure.
• One giant backfill UPDATE pins the xmin horizon, stalls autovacuum cluster-wide, bloats the table, and blows replication lag. Always batch + throttle.
• SET NOT NULL directly forces a full scan under the strongest lock. Route it through CHECK ... NOT VALID → VALIDATE → SET NOT NULL.
• Forgetting lock_timeout lets even a "metadata-only" DDL park at the queue head behind a long read and freeze everything. Set it, and retry with backoff.
• Running DDL inside a big transaction holds the lock for the whole transaction, not just the DDL — and CREATE INDEX CONCURRENTLY refuses to run there at all.

Selection & trade-offs: native expand–contract vs shadow tools vs a maintenance window

Native expand–contract (Postgres) is the default and the cheapest operationally: no extra moving parts, no trigger overhead, no second copy of the table's disk footprint, and full control. It wins whenever the engine gives you metadata-only and concurrent forms for what you need — which on modern Postgres is almost everything except a handful of in-place type changes. Cost: it's a multi-step choreography you must sequence and deploy carefully, and a few operations (some type changes) still have no non-rewriting native form.

Shadow-table tools (gh-ost / pt-osc) win when the native engine can't do the change online — the MySQL case, or a Postgres type change on a table too big to rewrite. They give you a rebuilt table with any schema, plus pause/throttle/test-on-replica controls. Costs: an entire extra copy of the table (double the disk during the migration), trigger write-amplification (pt-osc) or binlog plumbing (gh-ost), fragile foreign-key handling, and a genuinely scary atomic cutover. More power, much more operational surface.

Just take a maintenance window — run the blocking ALTER during a planned downtime — is not always the wrong answer. If the table is small enough that the rewrite is seconds, or the product genuinely tolerates a 2am window, a single locking statement is far simpler and less error-prone than orchestrating expand–contract, and simplicity has real value. It loses the moment the table is large (the window blows past its budget) or the system is 24/7 with no acceptable downtime — which is exactly the 500M-row-at-3pm scenario, where a window isn't on the table and you must use one of the online approaches above.

Takeaways

• The enemy is not slowness but the ACCESS EXCLUSIVE lock at the head of the queue: it makes every later query — even fast reads — wait behind it, so one long read + one DDL freezes the whole table. Separate "how long the lock is held" from "how long the DDL waits for it," and attack both.
• Decompose every change into metadata-only or bounded-and-interruptible steps via expand–contract: add before you remove, backfill in throttled keyset batches, and make destructive steps the last, separate, reversible deploy.
• Know the cheap Postgres forms cold: constant-default ADD COLUMN, CREATE INDEX CONCURRENTLY, CHECK ... NOT VALID → VALIDATE → SET NOT NULL, and an always-on short lock_timeout with retry.
• Reach for gh-ost / pt-osc when the engine can't go online natively (MySQL, or a rewriting type change) — accepting the extra copy, trigger/binlog overhead, and FK/cutover risk — and don't be too proud to take a maintenance window when the table is small or downtime is genuinely acceptable.

Sources

• PostgreSQL documentation — Explicit Locking (lock modes & conflict matrix), ALTER TABLE (which forms rewrite / take which lock), and CREATE INDEX (CONCURRENTLY semantics, INVALID index on failure).
• gh-ost documentation (GitHub) — triggerless binlog-based online schema change; throttling and cut-over design.
• pt-online-schema-change documentation (Percona Toolkit) — trigger-based shadow table + atomic rename; foreign-key handling.
• Kleppmann, Designing Data-Intensive Applications, ch. on encoding & evolution (schema evolution, backward/forward compatibility).
• Engineering write-ups on zero-downtime migrations — GitHub's gh-ost announcement and Braintree's "PostgreSQL at Scale: Database Schema Changes Without Downtime."