Vacuum Horizons, Dead Version Collection, and Table Bloat

Multi-version storage produces garbage by construction. Every update leaves a version that some snapshot may still need, and every delete leaves a version that some snapshot may still see. None of it can be removed at the moment of the update, because removal is only safe once no reader can reach it. The mechanism that decides “no reader can reach it” is a horizon, and the horizon is the single most consequential number in an MVCC engine.

Three horizons, not one

The oldest snapshot in the system defines the boundary below which nothing can be collected. If a reader took a snapshot when transaction 5000 was the next identifier to be assigned, then any version created by a transaction below 5000 is either visible to that reader or was already invisible to everyone. A version deleted by a transaction below 5000 is either already invisible or will be invisible to that reader once it advances past the deletion.

So the collection horizon is the minimum, over all active snapshots, of the snapshot’s low watermark. That is the oldest reader horizon.

A second horizon exists for a different reason. A version whose inserting transaction aborted must be removed regardless of snapshots, because no snapshot may see it. But an aborted transaction’s identifier may still be referenced by in-progress transactions’ snapshots, and until the abort is durably recorded, the version’s status is ambiguous. The engine therefore needs a horizon for “aborts older than this are certainly recorded”, which is typically much newer than the oldest reader.

A third horizon governs the identifier space itself. Identifiers are 32 bits and comparison is modular, so a version carrying an identifier within about two billion of the current counter becomes dangerous: an old version could compare as newer than a recent one. The mechanism that avoids this is freezing, which rewrites a version’s xmin to a special value meaning “older than everything” once it is old enough that no snapshot can distinguish it. The horizon for freezing is the oldest identifier that any live version might carry, and it advances independently of the collection horizon.

Why one old snapshot stalls everything

Because the collection horizon is a minimum over all active snapshots, a single long-lived transaction with an old snapshot sets the horizon for the whole database.

Consider a read-only transaction that begins a report and runs for an hour. Its snapshot’s low watermark is the oldest in the system, so for that hour no version created after that point can be collected anywhere, in any table, regardless of whether the report ever touches those tables. The report pays no validation cost and takes no locks, which is why snapshot isolation reads are described as free. The cost is deferred and paid by storage.

This is not a flaw in the implementation; it is a consequence of the definition. A snapshot is a promise that a particular set of committed states remains readable, and the engine cannot know which tables the promise will be exercised against. It must therefore keep everything that any snapshot below the horizon might reach.

The practical shape of the problem is that bloat accumulates in proportion to the update rate multiplied by the duration of the oldest snapshot. A table updated a thousand times a second with a snapshot held for an hour has three and a half million dead versions waiting. If the rows are wide, that is a large amount of disk and a large amount of scanning work for the eventual collection pass.

There are mitigations, all of which trade one cost for another. The engine can refuse to let a snapshot live beyond a configured age, aborting the transaction with an error rather than allowing unbounded retention. It can isolate the horizon per table rather than per database, so that a report on one table does not stall collection on another; this requires tracking the set of tables each snapshot has touched and is a real implementation choice in some engines. It can maintain a separate, compacted history store for old versions, so that retention does not consume heap space.

What collection actually does

A collection pass scans pages, identifies versions that are dead by the horizon test, and makes their space reusable. The details determine the cost.

In an engine that stores versions in the heap, collection cannot simply remove bytes from a page. A page is a dense array of line pointers into a tuple area, and removing a tuple in the middle would require shifting everything after it. The pass therefore marks the line pointer as dead and leaves the tuple bytes in place, so the space becomes reusable only when the page is compacted or when a new tuple of the same or smaller size happens to fit into the gap.

This is why a table can show substantial dead space that collection has already processed. The dead tuples are gone as far as visibility is concerned, and the free space map knows the page has room, but the physical layout still carries the old bytes. A subsequent insert of a small enough row can reuse the space without any page reorganization; a wide row cannot.

Collection also has to update the visibility map, the structure that records which pages contain only versions visible to every snapshot. The map is what allows an index-only scan to skip the heap entirely, and it is what allows collection to skip pages that need no work. A page that becomes all-visible after collection is marked, and a page that receives a new uncommitted version loses the mark. The map is therefore a cache of the horizon’s effect, and its accuracy determines whether reads can avoid heap access.

-- Dead versions are visible before collection, absent after it.
SELECT n_live_tup, n_dead_tup, last_vacuum, last_autovacuum
FROM pg_stat_user_tables
WHERE relname = 'orders';

-- The per-table horizon: how far behind the identifier counter this table is.
SELECT relname, age(relfrozenxid) AS xid_age
FROM pg_class
WHERE relkind = 'r'
ORDER BY age(relfrozenxid) DESC
LIMIT 5;

The second query is the one that matters operationally. age(relfrozenxid) reports how many identifiers have been consumed since the table’s oldest unfrozen version, and it is the number that approaches the wrap limit.

Freezing and the identifier counter

The 32-bit identifier space holds about four billion values, and comparison is defined modulo that space. A version with identifier 100 created when the counter is at 4,294,967,000 would compare as newer than everything, because the difference wraps. To prevent this, an engine that stores identifiers in tuples must periodically replace old identifiers with a frozen marker.

Freezing a version means marking it as inserted by a transaction older than any that will ever be compared. After freezing, the version is visible to every snapshot without consulting the in-progress list, and its identifier no longer consumes space in the modular ordering. The cost is that the original identifier is lost, which is why freezing can only be done once no snapshot needs to distinguish it from other old versions.

The rate at which freezing must happen is set by the number of identifiers consumed, not by time. A system that assigns identifiers quickly reaches the wrap horizon quickly, so the freeze horizon advances faster than the collection horizon and is the binding constraint for tables that are read but never written. A table that has not been modified in months still accumulates identifiers against its freeze horizon, because the counter advances for transactions elsewhere in the database.

The failure mode when freezing falls behind is severe: the engine refuses new transactions rather than risk misordering versions. This is why collection cannot be treated as optional housekeeping. The distinction between the two horizons is the reason a table with no updates can still require maintenance.

The cost of collection and where it lands

A collection pass reads pages and writes them back if anything changed, which means it consumes I/O and generates write-ahead log records that must be replicated. On a primary with replicas, the collection work is replicated work, so a large collection pass produces a burst of log traffic and a burst of replica apply work.

The pass is also not free of contention. It takes a lightweight lock per page while processing, which conflicts with concurrent writers to that page for the duration of the processing. A pass over a large table therefore slows concurrent writes to that table, in proportion to the number of pages it touches and the rate at which it touches them.

The mitigation is to spread the work. A rate-limited background pass that processes a bounded number of pages per cycle keeps the contention bounded and lets the horizon advance steadily, at the cost of possibly not keeping up with a high update rate. The alternative — a full pass triggered when dead space crosses a threshold — produces a burst of contention at an unpredictable time.

Detecting the problem before it is a problem

The observable signals are three. Dead tuple counts rising while the live count is stable indicate that collection is not keeping up. A horizon age that grows without bound indicates that a snapshot is pinned, usually by an idle-in-transaction session that opened a transaction and stopped issuing statements; the snapshot remains valid, so the horizon cannot advance, and the session may be doing nothing at all.

The third signal is the ratio rather than the absolute. A table with a stable live count and a growing dead count is accumulating versions faster than they are collected. A table with both counts growing is growing, and the dead versions are a fraction of the total.

The mechanism that ties these together is the one described in snapshot acquisition and commit ordering: the horizon is a minimum over live read views, and a read view’s lifetime is controlled by the application, not the engine. A connection pool that returns a session to the pool without ending its transaction holds a read view for as long as the connection lives. That is the most common cause of a stalled horizon, and it is invisible in the transaction log because nothing is happening.

The versions being retained are the ones described in heap tuple headers and visibility, and the same accounting applies to the undo-based design in undo records and version reconstruction, where the retained structure is an undo segment rather than a heap page and the failure mode is a snapshot-too-old error rather than bloat. Both designs answer to the same horizon logic; only the storage that grows differs.