UPDATE, DELETE and Dead Tuples

An UPDATE accounts SET balance = 80 WHERE id = 7 does four things. It takes the row lock by writing its xid into the old tuple's xmax (with the lock bits, as The Lock Manager describes). It builds the new tuple with xmin = its xid. It inserts that tuple — into the same page if the free space allows, otherwise into a page the free space map suggests. And it sets the old tuple's t_ctid to the new address and clears the lock-only bits so the xmax now means "superseded". The old tuple is untouched otherwise; the new one is a full copy of the row, changed columns and unchanged columns alike. A one-byte change to a 2 KB row writes 2 KB.

Then the indexes. Every index entry is (key → tuple address). The new tuple has a new address, so each index needs a new entry — including indexes on columns whose values did not change, because the address did. Each such insert may split an index page, and each leaves behind an entry pointing at the old version that will be dead once the horizon passes. This is the write amplification in Why Is This Query Slow? Indexes seen from below: an UPDATE costs one heap write plus one write per index, not because of the changed column but because of the changed address.

If the update changes no indexed column and the new version fits on the same page, PostgreSQL performs a heap-only tuple update. The new tuple is written on the page, the old one's t_ctid points at it as usual, and *no index entry is written*: the indexes keep pointing at the old slot, marked as the head of a HOT chain. A lookup arrives at the old slot, sees the chain, and follows t_ctid within the page to the visible version. Since everything stays on one page, following the chain costs no extra I/O.

HOT chains have a second gift: pruning. When a later access finds the page more than a certain fraction full, it can, without VACUUM and without touching indexes, collapse dead chain members — the line pointer that the index points at is turned into a *redirect* to the live version and the dead tuples' space is freed in-page. A hot row that is updated a thousand times a second on a page with spare room can cycle through versions indefinitely at almost no cost. That is why fillfactor = 70 on an update-heavy table is a standard tuning: leaving 30% free per page keeps updates HOT.

A DELETE writes the deleting transaction's id into the tuple's xmax (or, on undo-based engines, sets a delete-mark and writes an undo record). The tuple stays. It must: a transaction whose snapshot predates the delete is entitled to see it, and after a ROLLBACK the row must simply reappear, which it does because an aborted xmax reads as "not deleted". Index entries stay too; there is nothing in an index to say "deleted" — a lookup finds the entry, fetches the tuple, applies the visibility rule and discards it.

So the row becomes *invisible* at commit but *reclaimable* only later, when the oldest active snapshot postdates the deleting transaction. That gap — between invisible and reclaimable — is where dead tuples live, and its length is the age of the oldest snapshot in the system.

A dead tuple is a version no current or future snapshot can see: its xmax committed before the oldest snapshot still open started, or its xmin aborted. The threshold is the system's oldest xmin horizon: the minimum over every active snapshot's xmin, every replication slot's retained xmin, and every prepared transaction. One session that ran BEGIN four hours ago and is now idle sets the horizon four hours in the past; every version superseded since then, in every table, is invisible to everyone yet unreclaimable, because that one snapshot might still ask for it. The practical lesson MVCC: Multi-Version Concurrency Control calls this "idle in transaction"; here is the number it pins.

Dead tuples cost on every read. A sequential scan reads pages that are mostly dead versions, applies the visibility rule to each, and keeps a fraction. An index scan follows entries to tuples it then discards. The table's size in pages — what the planner's cost estimates use — no longer reflects its live rows. Performance Internals: Why the Slow Node Is Slow sees this as "the same query, slower every week, with no change in row count".

VACUUM is the pass that turns dead into free. It scans the heap — skipping pages the visibility map marks all-visible — and collects the addresses of dead tuples below the horizon into a work array. When the array fills or the scan ends it walks every index and bulk-deletes entries pointing at those addresses; then it returns to the heap, marks the collected slots unused, and defragments each page so the free bytes are contiguous. It records each page's free space in the free space map (FSM), a small side file with one byte per heap page arranged as a tree of maxima, which INSERT and non-HOT UPDATE consult to find a page with room. Finally it sets all-visible bits in the visibility map for pages with no dead tuples (which also lets index-only scans skip heap fetches) and, if the last pages of the file are entirely empty, truncates them.

Autovacuum runs this automatically: a launcher wakes every autovacuum_naptime (1 min), and a worker vacuums any table whose dead-tuple count from the statistics collector exceeds autovacuum_vacuum_threshold + autovacuum_vacuum_scale_factor × reltuples — 50 rows plus 20% of the table by default, which is far too lazy for a small hot table and roughly right for a large one. Workers throttle themselves with autovacuum_vacuum_cost_delay so as not to saturate I/O, which on a busy system can mean they never catch up. Per-table settings (ALTER TABLE … SET (autovacuum_vacuum_scale_factor = 0.01)) are the standard fix for hot tables.

Bloat is the space a table or index occupies beyond what its live data needs. It comes from dead tuples VACUUM has not yet removed, from free space VACUUM has reclaimed but inserts have not refilled, and — in indexes — from pages that emptied but cannot be merged. Ordinary VACUUM never returns space to the filesystem except by truncating empty trailing pages, so a table that once held ten million rows and now holds ten thousand keeps its ten-million-row file until someone rewrites it: VACUUM FULL (which takes an exclusive lock and rewrites into a new file) or pg_repack (which does the same online). Indexes bloat separately and are fixed by REINDEX CONCURRENTLY.

The growth pattern to recognise: row count flat, table size climbing, n_dead_tup climbing, last_autovacuum recent but ineffective — that is a pinned horizon, and the cure is finding the session or slot holding it, not tuning autovacuum. Row count flat, size climbing, last_autovacuum old — that is autovacuum unable to keep up, and the cure is the scale factor and cost delay. The challenge on table bloat walks one of these.

InnoDB reaches the same place by a different road. DELETE sets a delete-mark bit on the record — in the clustered index and in each secondary index — and writes an undo record so the delete can be rolled back and so older read views can still see the row. UPDATE of a secondary-index column delete-marks the old index entry and inserts a new one; UPDATE of a non-indexed column changes the row in place with the old image in undo. Nothing is physically removed by the statement.

Purge is InnoDB's vacuum: background threads walk the history list — undo records of committed transactions, oldest first — and for each one whose transaction is older than every open read view, physically remove the delete-marked records and free the undo. The measure of pending work is History list length in SHOW ENGINE INNODB STATUS; a long-running transaction with an open read view stops purge at its position, the list grows into the millions, the undo tablespace grows on disk, and every read of a hot row has to walk a longer undo chain. The symptoms — disk growing, reads slowing, one old transaction — are the PostgreSQL bloat story with the garbage in undo space instead of in the table.