Concurrent Index Builds and the Invalid Index They Can Leave Behind

Building an index on a table that is being written to is a small distributed-systems problem disguised as a maintenance command. The index must reflect every row, including rows inserted while the build runs, and the build cannot hold a lock that stops those inserts. Since the build reads the table in some order over some interval and writes arrive concurrently, there is a window in which a row is neither seen by the scan nor yet written by the inserter. Closing that window is what makes the concurrent build more expensive than the ordinary one, and it is what leaves an index in an unusable state when the process fails.

The two-scan protocol

The ordinary CREATE INDEX takes a lock that blocks writes to the table, scans the heap once, sorts the keys, and builds the tree bottom-up. Because no writes can occur, the scan’s result is complete by construction. The lock is held for the duration, which on a large table means writes stop for minutes or hours.

The concurrent form drops the write-blocking requirement and pays for it with two scans and a snapshot.

In the first phase the builder takes a lock that permits reads and writes, records a snapshot, and scans the table’s pages, collecting every live tuple visible to that snapshot and its key. It then sorts those keys and builds the index’s initial tree from them. The scan is long and reads the whole table, but it does not block writers.

During that scan, writers insert and update rows. Each such operation checks the catalogue for indexes that are in the building state and, for each, inserts an entry into the new index, either directly, or into a small pending list that the build will merge later. The check is the ongoing cost: every write on the table pays a catalogue lookup plus the index maintenance it would have paid anyway once the index exists. This is why a concurrent build makes writes slower while it runs, even though it does not block them.

The gap the snapshot leaves is the interval between the moment the snapshot was taken and the moment the in-progress index became visible to writers. A row inserted in that interval may be absent from the scan (it is newer than the snapshot) and its insertion may have missed the index (the index was not yet in the catalogue’s building set). That is the hazard the second phase exists to close.

The second phase closes that gap without blocking writes for the whole scan. The builder takes a new snapshot, scans the table again, and for each tuple probes the index for a matching entry; tuples with no entry are inserted. Concurrent writes are still captured by the building-set path, so they cannot reopen the gap. What the phase cannot do is finish while a transaction that started before the index became visible is still running, because such a transaction’s rows may already have been scanned before its insert landed. So the builder waits for those transactions to end before it marks the index valid.

That wait is where a concurrent build’s apparent hang comes from. It is not a lock conflict in the ordinary sense; the builder is waiting on the completion of transactions that hold snapshots, and a single long-running read on the table postpones the end of the build for as long as it runs. This is the same horizon effect that delays vacuum, applied to an index build, and it is why a build started during a quiet period can finish quickly while the identical build started during an analytical workload waits for hours.

The final step updates the catalogue to mark the index valid and commits. Before that commit, the index exists in the catalogue with an invalid flag, and queries do not use it.

-- does not block writes; waits for older transactions before validating
CREATE INDEX CONCURRENTLY idx_orders_customer ON orders (customer_id);

-- if it fails, the index is left behind in an unusable state
DROP INDEX CONCURRENTLY idx_orders_customer;

What “invalid” means to the planner

An invalid index is a real physical structure with a real catalogue entry that the planner refuses to consider. It consumes disk space, and while it remains in the catalogue, writes to the table continue to be checked against it and entries continue to be inserted into it, so an abandoned invalid index is not merely dead weight but an ongoing tax on every write.

The failure modes that produce one are all ordinary: a uniqueness violation discovered during the second scan, a deadlock, a lock timeout on the brief exclusive phase, a cancellation, a crash of the backend. In each case the work done so far is not rolled back, because undoing a partially built index over a large table would cost as much as building it, and the catalogue row is committed separately from the build itself. The catalogue commit that marks it valid never happens, so it stays invalid.

The repair is to drop it and retry. Dropping concurrently is itself a two-phase operation with a window in which the drop is pending, and it cannot run inside a transaction block. A retry loop that attempts the build, checks the catalogue for invalidity, drops, and retries is the standard operational wrapper; it needs a bound on attempts, because a uniqueness violation is deterministic and will fail identically forever.

A uniqueness violation deserves special note because the concurrent build’s behaviour differs from the ordinary one. The ordinary build fails before publishing anything. The concurrent build has already published the in-progress index and accepted writes into it, so a duplicate key discovered in the second phase leaves a partially populated unique index that is invalid. Its presence also means concurrent writes that would create duplicates have been failing, or will fail, at the point where the index entry is inserted, a live correctness effect that arrives before the index is usable.

The MySQL shape of the same problem

InnoDB’s online index creation is the same protocol under a different vocabulary. The operation is declared with an algorithm and a lock level, and the engine either honours the request or refuses it before doing any work: a refusal is an error rather than a silent fallback to a blocking build, which is the property that makes the request safe to issue from an automated migration.

The build reads the clustered index and writes sorted keys into temporary files, then loads them into the B-tree. Row changes that arrive during the scan are recorded in a separate log of index entries for the new index, and that log is applied to the B-tree before the index is published. The brief exclusive lock at the start and end of the operation is what keeps the window between the two from containing an unrecorded change.

The invalid-index equivalent is less visible: a failed online build rolls back its temporary files, and the index either exists complete or does not exist, because InnoDB’s data dictionary records the index only at the end. The cost of the difference is that a failed build repeats all the work, where PostgreSQL’s invalid index can in principle be inspected. The benefit is that no cleanup step is needed and no write tax is left behind.

Choosing between the two forms

The blocking build is faster and produces less log, because it writes each key once and does no verification. For a table that is not being written to, or during a maintenance window, it is the better choice.

The concurrent build is the only option for a table under continuous write load, and its total cost is roughly the single scan plus a verification scan plus the maintenance of concurrent writes. It also produces more log: every entry inserted during the build is logged as an index insertion, and the second scan logs the missing entries it finds. On a replicated primary that log volume is the operational side effect to watch, the same concern that governs the throttle on batched backfills.

Two further considerations decide the schedule. The concurrent build cannot run inside a transaction block in PostgreSQL, so a migration runner that wraps each file in a transaction must special-case it, because the statement fails outright rather than degrading. And the build takes two brief exclusive locks on the table, at its start and at its end, which means it queues behind long transactions exactly as any other DDL does. The metadata lock queue applies here too: a build that has already spent an hour scanning can then sit waiting for its final catalogue update, and every write to the table queues behind it while it waits.

Indexes that must be built together

A constraint that needs more than one index cannot be added concurrently in one step. A unique constraint backed by a unique index is a single concurrent build and is fine. A foreign key in PostgreSQL requires the referencing column’s index to exist, and the constraint itself is added with ALTER TABLE, which takes the exclusive lock; the sequence is therefore to build the index concurrently and then add the constraint under the brief exclusive lock, accepting the queue wait for the second step.

The same reasoning applies to a partitioned table: an index on the parent creates indexes on each partition, and a concurrent build on the parent builds each partition’s index in turn. A failure on one partition leaves that partition’s index invalid while others are valid, so the cleanup must be per-partition rather than a single drop on the parent.

What the build does to the rest of the system

The scan reads the entire heap, evicting whatever was in the buffer pool. On a system whose working set is smaller than the table, an index build therefore leaves the cache cold, and the queries that follow run slowly until it refills. This is a real and frequently overlooked cost of an otherwise non-blocking operation, and it is the reason large builds are scheduled away from peak traffic even when their locks are brief.

The build also holds a snapshot open for its duration, which prevents vacuum from removing tuples that the scan might still need to see. On a churning table a long build delays space reclamation for as long as it runs, which is the horizon effect described in dead tuples and vacuum reclamation. The interaction is direct: a build on a table that is already bloated both reads more pages and extends the period during which the bloat cannot be cleaned.