Vacuum - PostgreSQL way of clearing it's Debt

PostgreSQL uses MVCC (Multi-Version Concurrency Control): an UPDATE never overwrites a row in place, and a DELETE doesn't immediately erase the row. Instead:

• An UPDATE inserts a brand-new tuple version and sets the xmax on the old one; the old version stays on disk so that concurrent transactions with an older snapshot can still see it.

• A DELETE sets the xmax to the transaction ID that deleted the row, but the row itself is not cleared from disk either. Transactions that started before the deleting transaction can still see this row.

Once no active transaction or snapshot can possibly need a tuple version anymore, it becomes dead – wasted space that nothing will ever look at again. That's the debt VACUUM exists to collect.

Part 1: Why VACUUM Exists?

Every write operation i.e., UPDATE or DELETE in PostgreSQL creates a debt that must eventually be paid. For example:

INSERT → writes 1 new tuple
       → debt: none (yet)

UPDATE → writes 1 new tuple version
       → marks old tuple dead (xmax set)
       → writes 1 new index entry per index (assume N indexes)
       → marks old index entries dead
       → debt: 1 dead heap tuple + N dead index entries

DELETE → marks tuple dead (xmax set)
       → marks index entries dead
       → debt: 1 dead heap tuple + N dead index entries

This debt accumulates on every page, and dead tuples cause:

• Wasted space: pages fill with unreachable data

• Slower scans: every scan reads and discards dead tuples

• Blocked index-only scans: the all_visible bit cannot be set while dead tuples exist

• Wraparound risk: old xmin values must be frozen before the XID space/range is exhausted

Part 2: What VACUUM Does?

VACUUM is the debt collector, whose responsibility is to clear all the debt created above:

• Reclaims space occupied by dead tuples (and their index entries) so that space can be reused by future inserts/updates.

• Freezes old transaction IDs so PostgreSQL doesn't run into transaction ID wraparound. XIDs are 32-bit and comparisons are circular, so an unfrozen tuple can appear to be "from the future" once wraparound occurs.

• Updates the visibility map and free space map so future scans/vacuums can skip work.

• Optionally truncates trailing empty pages and updates planner statistics.

Part 3: How VACUUM Works – The Three-Phase Design

We can divide the process into three phases:

• Scan, Prune, and Freeze

• Index Vacuuming

• Heap Vacuuming

Phase 0 below covers the entry point into the heap access method – it sits before the three phases proper, which are Phase 1 through Phase 3.

Phase 0: Entry – from the VACUUM Command Down to the Heap AM (Access Method)

When a VACUUM command is executed, PostgreSQL calls ExecVacuum(), which is the primary entry point for ANALYZE as well.

Code flow:

void ExecVacuum(ParseState *pstate, VacuumStmt *vacstmt, bool isTopLevel) {
   // ..... parse options into VacuumParams

   vacuum(newrels, &params, bstrategy, ...); => {

      // ..... loop over relations
      vacuum_rel(vrel->oid, vrel->relation, &params, bstrategy); => {
         Relation rel;

         // ..... open/lock relation, permission checks
         if (params->options & VACOPT_PROCESS_MAIN) {
            if (params->options & VACOPT_FULL) {
               cluster_rel(rel, InvalidOid, &cluster_params); // VACUUM FULL: different path entirely (cluster.c)
               rel = NULL;
            }
            else {
               // OUR AREA OF INTEREST — plain/lazy VACUUM
               table_relation_vacuum(rel, params, bstrategy); => {
                  // src/include/access/tableam.h:1674
                  rel->rd_tableam->relation_vacuum(rel, params, bstrategy);

                  // ======================================
                  // rel->rd_tableam->relation_vacuum is a function pointer to the table access method's vacuum implementation.
                  // heap AM wires this straight to heap_vacuum_rel:
                  //   .relation_vacuum = heap_vacuum_rel  (heapam_handler.c:2656)
                  heap_vacuum_rel(rel, params, bstrategy); => {
                     LVRelState *vacrel = palloc0(sizeof(LVRelState));
                     
                     // ..... set up error callback, open indexes, copy names
                     vacrel->aggressive = vacuum_get_cutoffs(rel, params, &vacrel->cutoffs); // computes OldestXmin/FreezeLimit/MultiXactCutoff
                     vacrel->rel_pages = RelationGetNumberOfBlocks(rel);
                     vacrel->vistest = GlobalVisTestFor(rel);
                     dead_items_alloc(vacrel, params->nworkers); // TID store, bounded by maintenance_work_mem

                     lazy_scan_heap(vacrel);        // === STAGE 1 ===
                     // (lazy_scan_heap internally calls lazy_vacuum() === STAGE 2+3 === when TID store fills or scan ends)

                     // ..... final index cleanup, truncate, update relfrozenxid/relminmxid, pgstat report
                     return;
                  }
               }
            }
         }
         // ..... close relation
      }
   }
}

Phase 1: Scan, Prune, and Freeze

Entry point: lazy_scan_heap()

The driver loop reads blocks via a ReadStream, and for each block:

• heap_vac_scan_next_block() decides whether a block can be skipped using the visibility map. Pages that are already all-visible (or all-frozen) don't need scanning, unless this is an aggressive vacuum or eager scanning wants to freeze them anyway.

• It takes a cleanup lock and calls lazy_scan_prune, which delegates the real work to heap_page_prune_and_freeze.

• heap_page_prune_and_freeze walks every line pointer on the page. For each tuple, it calls HeapTupleSatisfiesVacuumHorizon, which returns one of the following:

  • HEAPTUPLE_DEAD – deletable now

  • HEAPTUPLE_RECENTLY_DEAD – dead, but some snapshots might still see it, so it's kept

  • HEAPTUPLE_LIVE

  • HEAPTUPLE_INSERT_IN_PROGRESS / HEAPTUPLE_DELETE_IN_PROGRESS

• HOT-chain pruning: Heap-Only Tuple chains are collapsed i.e., intermediate dead tuple versions are removed. The root tuple's line pointer is turned into LP_REDIRECT, pointing straight to the latest live version. This way, index entries pointing at the root stay valid without needing an index update.

• Freezing: if a tuple's xmin is older than FreezeLimit, it's rewritten with a frozen XID so it's permanently visible without needing to look up the CLOG. Here, FreezeLimit = nextXID - vacuum_freeze_min_age.

• Dead item pointers (LP_DEAD) whose tuples were removed are recorded into the TID store – a memory-efficient, radix-tree-like structure capped at maintenance_work_mem, which will be used later for index cleanup.

• If the entire page ends up fully visible/frozen, the relevant bit(s) are set in the visibility map.

lazy_scan_heap(LVRelState *vacrel) { 
   ReadStream *stream = read_stream_begin_relation(READ_STREAM_MAINTENANCE, vacrel->bstrategy,
                                                    vacrel->rel, MAIN_FORKNUM,
                                                    heap_vac_scan_next_block, vacrel, sizeof(uint8)); => {
      // called back per block: decides skip vs scan using the Visibility Map
      // OUR AREA OF INTEREST — this is what lets normal vacuums skip all-visible/all-frozen pages
   }

   while (true) {
      // ..... check TID-store fullness -> if full, call lazy_vacuum() (Stage 2+3) mid-scan, then resume
      Buffer buf = read_stream_next_buffer(stream, &per_buffer_data);
      if (!BufferIsValid(buf)) break;

      blkno = BufferGetBlockNumber(buf);
      vacrel->scanned_pages++;
      visibilitymap_pin(vacrel->rel, blkno, &vmbuffer);

      got_cleanup_lock = ConditionalLockBufferForCleanup(buf);
      // ..... lazy_scan_new_or_empty() short-circuit for new/empty pages

      // OUR AREA OF INTEREST
      lazy_scan_prune(vacrel, buf, blkno, page, vmbuffer,
                       all_visible_according_to_vm, &has_lpdead_items, &vm_page_frozen); => {
         PruneFreezeResult presult;
         int prune_options = HEAP_PAGE_PRUNE_FREEZE;
         if (vacrel->nindexes == 0)
            prune_options |= HEAP_PAGE_PRUNE_MARK_UNUSED_NOW;

         // OUR AREA OF INTEREST — the real per-page workhorse
         heap_page_prune_and_freeze(rel, buf, vacrel->vistest, prune_options,
                                     &vacrel->cutoffs, &presult, PRUNE_VACUUM_SCAN,
                                     &vacrel->offnum,
                                     &vacrel->NewRelfrozenXid, &vacrel->NewRelminMxid); => {
            for (offnum = maxoff; offnum >= FirstOffsetNumber; offnum = OffsetNumberPrev(offnum)) {
               ItemId itemid = PageGetItemId(page, offnum);
               // ..... LP_UNUSED / LP_DEAD / LP_REDIRECT items handled directly

               // classify each normal tuple:
               prstate.htsv[offnum] = heap_prune_satisfies_vacuum(&prstate, &tup, buffer); => {
                  //  calls HeapTupleSatisfiesVacuumHorizon()
                  // returns HEAPTUPLE_DEAD / RECENTLY_DEAD / LIVE / INSERT_IN_PROGRESS / DELETE_IN_PROGRESS
               }

               if (!HeapTupleHeaderIsHeapOnly(htup))
                  prstate.root_items[prstate.nroot_items++] = offnum;
               else
                  prstate.heaponly_items[prstate.nheaponly_items++] = offnum; // HOT chain member
            }

            // ..... walk HOT chains: collapse dead intermediate versions,
            //       rewrite root line pointer as LP_REDIRECT to the surviving tuple

            // for each surviving tuple, consider freezing:
            if (prstate->freeze) {
               // OUR AREA OF INTEREST
               heap_prepare_freeze_tuple(htup, prstate->cutoffs, &prstate->pagefrz,
                                          &prstate->frozen[prstate->nfrozen],
                                          &totally_frozen); => {
                  // heapam.c — decides if xmin/xmax older than FreezeLimit/MultiXactCutoff
                  // must be rewritten frozen; feeds presult.all_frozen for the VM bit
               }
               prstate->frozen[prstate->nfrozen++].offset = offnum;
            }

            // ..... apply all changes (redirect/dead/unused/frozen arrays) to the page,
            //       WAL-log via log_heap_prune_and_freeze(), set presult.all_visible/all_frozen
         }

         if (presult.lpdead_items > 0) {
            qsort(presult.deadoffsets, presult.lpdead_items, sizeof(OffsetNumber), cmpOffsetNumbers);
            // OUR AREA OF INTEREST — feeds Stage 2/3
            dead_items_add(vacrel, blkno, presult.deadoffsets, presult.lpdead_items); => {
               // vacuumlazy.c:3538 — inserts TIDs into the bounded TidStore
            }
         }

         // ..... if presult.all_visible, set VM bit(s) via visibilitymap_set()
      }
   }
}

Phase 2: Index Vacuuming

Once the TID store fills up (or the heap scan finishes), lazy_vacuum calls each index's bulk-delete routine (e.g., btree's btbulkdelete) with the TID store, so all index entries pointing at now-dead heap tuples are removed. This can run in parallel across indexes.

lazy_vacuum(LVRelState *vacrel) { 
   // ..... bypass-optimization check (skip index vacuuming if lpdead_item_pages is near zero)

   else if (lazy_vacuum_all_indexes(vacrel)) => {
      
      for (int idx = 0; idx < vacrel->nindexes; idx++) {
         Relation indrel = vacrel->indrels[idx];
         IndexBulkDeleteResult *istat = vacrel->indstats[idx];

         // OUR AREA OF INTEREST
         vacrel->indstats[idx] = lazy_vacuum_one_index(indrel, istat, old_live_tuples, vacrel); => {
            IndexVacuumInfo ivinfo = { .index = indrel, .heaprel = vacrel->rel, /* ..... */ };

            istat = vac_bulkdel_one_index(&ivinfo, istat, vacrel->dead_items,
                                           vacrel->dead_items_info); => {
               // OUR AREA OF INTEREST — calls into the *index* AM, e.g. btree's btbulkdelete
               istat = index_bulk_delete(ivinfo, istat, vac_tid_reaped, dead_items); => {
                  // indrel->rd_indam->ambulkdelete(...)
                  // walks the index, for each entry asks vac_tid_reaped(TID)
                  // whether that TID is in vacrel->dead_items (the TidStore from Stage 1),
                  // and deletes the matching index tuples
               }
            }
            return istat;
         }
      }
   }
   // ..... on success, proceeds straight into Stage 3 below
}

Phase 3: Heap Vacuuming

lazy_vacuum_heap_rel / lazy_vacuum_heap_page revisit each page recorded in the TID store and finally flip LP_DEAD line pointers to LP_UNUSED, actually freeing the slot for reuse. This can only happen after Phase 2 guarantees no index still references those TIDs – otherwise you'd get index entries pointing at garbage or reused tuples, a classic corruption bug.

lazy_vacuum_heap_rel(vacrel) { 
   // ..... TidStoreIterate over every blkno recorded in Stage 1's dead_items

   lazy_vacuum_heap_page(vacrel, blkno, buffer, deadoffsets, num_offsets, vmbuffer); => {
     
      Page page = BufferGetPage(buffer);
      START_CRIT_SECTION();

      for (int i = 0; i < num_offsets; i++) {
         ItemId itemid = PageGetItemId(page, deadoffsets[i]);
         Assert(ItemIdIsDead(itemid) && !ItemIdHasStorage(itemid));
         // OUR AREA OF INTEREST — the actual space reclamation
         ItemIdSetUnused(itemid);   // slot is now free for reuse by future inserts
         unused[nunused++] = deadoffsets[i];
      }

      PageTruncateLinePointerArray(page);   // shrink the line-pointer array if possible
      MarkBufferDirty(buffer);

      if (RelationNeedsWAL(vacrel->rel))
         log_heap_prune_and_freeze(vacrel->rel, buffer, InvalidTransactionId, false,
                                    PRUNE_VACUUM_CLEANUP, /* ..... */
                                    unused, nunused);
      END_CRIT_SECTION();

      // ..... recheck heap_page_is_all_visible() now that dead items are gone,
      //       set VM bit if so
   }
   // ..... FreeSpaceMapVacuumRange() makes the freed space visible to future inserters
}

Phase 4: Finishing Up

• FreeSpaceMapVacuumRange propagates newly freed space up the FSM tree.

• If trailing pages are entirely empty, the relation is truncated.

• relfrozenxid/relminmxid in pg_class are advanced to vacrel->NewRelfrozenXid/NewRelminMxid, and stats (pg_stat_user_tables, pg_class.reltuples) are updated.

Conclusion

MVCC is what makes PostgreSQL's concurrency model work – readers never block writers, and writers never block readers – but that guarantee isn't free. Every UPDATE and DELETE leaves behind a dead tuple, a set of stale index entries, and eventually an unfrozen XID, and none of that debt clears itself.

VACUUM is the mechanism that pays it down, and the three-phase design exists specifically so that payoff can happen safely and efficiently:

• Scan, Prune, and Freeze finds what's dead and rewrites what's old enough to freeze, using the visibility map to skip pages that don't need the work.

• Index Vacuuming clears every index's references to those dead tuples first — this ordering is what keeps the next phase safe.

• Heap Vacuuming only then flips the now-unreferenced line pointers to LP_UNUSED, actually handing the space back for reuse.

That ordering – indexes before heap – is the detail worth remembering above all else. Reclaim heap space before indexes are cleaned up, and you get index entries pointing at tuples that no longer mean what they used to: exactly the class of corruption bug the two-phase split (Phase 2 then Phase 3) is built to prevent.

The freezing work matters just as much as the space reclamation, if not more — it's not an optimization, it's what keeps the 32-bit XID counter from wrapping around and making old, unfrozen rows look like they were written in the future. Skip VACUUM long enough, and that's the failure mode you eventually hit, not just table bloat.