Deletion is two events

4. Multi-version concurrency control

Multi-version concurrency control (MVCC) lets reads and writes proceed without locking each other (Reed, 1978; Bernstein and Goodman, 1983). When a transaction starts, it takes a snapshot of the database's consistent state at that moment and runs all its reads against that snapshot. When a record is updated or deleted, the database doesn't overwrite the current version; it creates a new one and keeps the old. A snapshot taken before the update has to go on seeing the record as it was.

So in an MVCC database every update and every deletion leaves behind a version that has been declared invalid but can't yet be reclaimed. PostgreSQL calls these dead tuples, InnoDB undo records, Cassandra tombstones. In PostgreSQL the process that cleans them up is called vacuum.

The name goes back to Stonebraker's (1987) design of the POSTGRES storage system. Records were never overwritten, and old versions were moved to archival storage by a process called the "vacuum cleaner". The aim was not to erase history but to be able to query past versions (time travel). The feature was removed in PostgreSQL 6.2 (1997) on grounds of performance and storage cost, and vacuum turned from a process that archived old versions into one that reclaims their space.

The same distinction shows up on two levels at once in SQLite, which The anatomy of data languages used as its example of a recursive interpretation stack. To the file system an SQLite database is a single file; from the inside it holds tables and rows. When a row is deleted in SQLite, its bytes aren't removed from the file: the space is marked free within the page, and pages that become entirely empty go onto the file's freelist. The structure is the same as FAT32 marking a directory entry and freeing its clusters, one level up, inside a file. Unless PRAGMA secure_delete is on, deleted content stays in the file, and the file only shrinks when SQLite's own VACUUM command rewrites it.

5. The vacuum horizon

Vacuum can't clean up every dead version, only those that no active snapshot can still see. That line is called the vacuum horizon. The term has two parts:

• Vacuum is the process that finds dead versions and reclaims their space.
• Horizon is the line that sets how far that process may go: no active reader can see, or will ever see, a version older than this line.

Keeping the two apart matters in practice. Vacuum not keeping up is a configuration problem, a matter of how often it runs, how many workers it has and its cost limits. A horizon that doesn't move is not a configuration problem: however often vacuum runs, it can't clean up anything ahead of the horizon.

Formally:

horizon = min { s : s is the snapshot of an active reader }

The deciding element of the definition is min. The horizon is not an average of the readers but their minimum. A single long-running reader therefore sets the horizon regardless of how long the others take. That the vast majority of readers in the system finish in milliseconds changes nothing.

6. An example: a transaction left idle

On a Friday at 18:40 an analyst connects to the database for a report, starts a transaction, runs a single SELECT and stops working without closing the client. In PostgreSQL the session stays in the idle in transaction state. The transaction holds no locks, writes nothing and consumes no resources; but because its snapshot is active, it pins the horizon at 18:40.

Over the weekend every update to the orders table creates a new version and leaves the old one behind. Autovacuum runs on schedule but can clean up none of them, because a snapshot taken at 18:40 could, in principle, still see them. On Monday morning the table has grown from 30 GB to 210 GB; the number of rows has barely changed.

The output of VACUUM (VERBOSE) (PostgreSQL 15 and later) shows this directly:

tuples: 0 removed, 1204117 remain, 1198320 are dead but not yet removable
removable cutoff: 88213410, which was 4120331 XIDs old when operation ended

"Dead but not yet removable" says the versions to be cleaned up were found, but the horizon kept them from being removed.

7. The same line in other systems

The same structure exists in every system that keeps several versions of a record at once, or that has to free shared data while readers may still be using it. It goes by different names in different systems and papers: the xmin horizon in PostgreSQL, the GC safe point in TiDB, garbage collection driven by the oldest active transaction in Hekaton (Diaconu et al., 2013), and most often the low watermark in work on in-memory MVCC systems (Böttcher et al., 2019).

The systems in the table are the ones The anatomy of data languages sorted into separate categories called file system, database and message queue, though all of them are naming programs working on the same bytes. Their deletion rules are therefore not separately invented mechanisms but answers to the same problem at different depths. Every one of them asks the same question: which is the oldest active reader? What differs is what counts as a reader. A good share of horizon problems in practice come from components the operator doesn't think of as readers: a replication slot whose consumer is gone, a PREPARE TRANSACTION abandoned halfway through a two-phase commit, a long-running backup. None of them shows up in pg_stat_activity as a long-running query.

In Cassandra the structure takes a different form. What delays the reclamation of a tombstone is not a reader but a replica that has not yet received the deletion. If the tombstone is removed before every replica has been brought in line by repair, the replica that missed the deletion still holds the old data, and at the next synchronisation the deleted record reappears. This is known as data resurrection. The structure is the same again: a record declared invalid can't be reclaimed until the last party that hasn't heard of it has.

11. A passing cause, a lasting effect

When the transaction holding the horizon back closes, the horizon moves and the next vacuum pass cleans up the accumulated dead versions. But that doesn't reduce the space the table takes on disk.

In PostgreSQL, vacuum doesn't return the space it reclaims to the operating system; it only marks it reusable within the table's pages. The file can only shrink by completely empty pages at the end of the table. The table in the example still takes about 210 GB after the dead versions are cleaned up, and sequential scans go on reading those pages. Really getting the space back takes VACUUM FULL (which rewrites the table and holds an ACCESS EXCLUSIVE lock throughout) or a tool such as pg_repack. pg_repack rewrites the table online and takes the exclusive lock only briefly at the start and the end; in exchange it needs free disk space of about twice the size of the table and its indexes.

Nor is the effect confined to the table:

• Indexes grow with entries pointing to dead versions, and the same query reads more pages.
• HOT (heap-only tuple) updates become rarer. When pages have no free space left, updates have to rewrite the indexes too, and growth speeds up.
• Freezing depends on the same horizon. If it stays put long enough, protection against transaction ID wraparound kicks in. First come aggressive freezing passes and warnings; in the worst case the database refuses commands that need a new transaction ID. Read-only queries keep working, but writes stop.

So watching the horizon is not the same as watching for long-running queries. When the long read ends, the cause is gone, but the effect remains.

12. Diagnosis and prevention

To find what is holding the horizon back in PostgreSQL, every source that counts as a reader has to be checked separately:

-- Open transactions
SELECT pid, usename, state, xact_start, age(backend_xmin) AS xmin_age
FROM pg_stat_activity
WHERE backend_xmin IS NOT NULL
ORDER BY age(backend_xmin) DESC;

-- Replication slots (including inactive ones)
SELECT slot_name, active, xmin, catalog_xmin
FROM pg_replication_slots;

-- Prepared transactions
SELECT gid, prepared, owner FROM pg_prepared_xacts;

-- Standbys sending feedback
SELECT application_name, backend_xmin FROM pg_stat_replication;

In InnoDB the corresponding indicator is the History list length in the output of SHOW ENGINE INNODB STATUS. A value that keeps rising means purge is being held back by a read view.

In a system with an observed horizon, the basic remedy is to limit how long readers can last; that is, to apply the declared-horizon approach on the reader's side. In PostgreSQL the relevant settings are:

• idle_in_transaction_session_timeout: ends open transactions that sit idle after a set time. It directly prevents an idle transaction from pinning the horizon for hours.
• transaction_timeout (PostgreSQL 17 and later): limits the total duration of a transaction.
• statement_timeout: limits the duration of a single statement; it doesn't cover transactions sitting idle.

Replication slots whose consumers are gone also have to be watched and dropped; slots are not removed together with their consumers.

All of these measures move part of the cost from storage to the reader. Here too the cost can't be removed; only who bears it can be decided in advance.