Vacuum Implementation

There are two primary sets of internal structures that serve as input and output from data vacuuming.

On the input side, each database row includes status flags called hint bits that track whether the transaction that updated the xmin or xmax values is know to be committed or aborted yet. The actual commit logs (pg_clog and sometimes pg_subtrans) are consulted to confirm the hint bits transaction state if they are not set yet. Vacuum also writes to these hint bits, part of the row itself, as it confirms the known state has changed.

Besides updating the data pages themselves, the additional output from vacuum is the updated information in the free space map.

Regular vacuum

Vacuum does a scan of each table and index looking for rows that can no longer be visible. The row hint bits are updated to reflect any information discovered, and newly freed space is inserted into the free space map.

Once the free space map for a table has entries on it, new allocations...