Start here

Life of a DELETE

A DELETE does not erase the row. It stamps the row with its own transaction ID, logs that to WAL, and commits. The space is reclaimed later by pruning and VACUUM.

In plain words

When you delete a row, PostgreSQL does not wipe it from the disk straight away. It writes a small stamp on the row saying "deleted by transaction 1718". The row stays on its page, invisible to anyone who starts reading after the delete commits.

Why keep it? Other sessions that started earlier may still need to see the old row. This is MVCC: readers see a consistent picture without being blocked by writers.

Before the delete counts as done, a short note about it is written to the write-ahead log (WAL) on disk, so it survives a crash. Later, when no one can see the old row any more, VACUUM (usually autovacuum) removes it and makes the space reusable. The table file normally does not shrink; the freed space is reused by new rows.

For DBAs and operators

What actually changes

Locks: the table and its indexes get RowExclusiveLock, and each deleted row is locked at row level by setting its xmax. A second session trying to update or delete the same row waits for this transaction to finish.
Transaction ID: the first write in a transaction assigns it an XID. The heap tuple keeps its data; only its header changes: t_xmax is set to that XID.
Indexes: nothing is removed from them. The index entry still points at the dead tuple until VACUUM (or, for B-tree, opportunistic deletion of known-dead entries) removes it.
WAL: one heap record per deleted row, as pg_waldump shows: rmgr: Heap ... desc: DELETE xmax: 1718, off: 3, infobits: [KEYS_UPDATED], …. If this is the first change to the page since the last checkpoint, the record carries a full-page image.
Commit: a COMMIT WAL record is flushed (with the default synchronous_commit = on), then the transaction is marked committed in pg_xact and the client receives DELETE 1.
Statistics: n_tup_del and n_dead_tup in pg_stat_user_tables go up, which is what autovacuum watches.

Cleaning up

Once no snapshot can still see the row, it is a dead tuple. The next session that reads the page sets the "xmax committed" hint bit, and page pruning may reclaim the tuple's space on that page. VACUUM removes the index entries, marks the line pointer unused, records the free space in the free space map and updates the visibility map. Only VACUUM FULL or a tool like pg_repack rewrites the table to return space to the operating system (plain VACUUM can only truncate empty pages at the very end of the table).

Things support engineers see

Big deletes create bloat: deleting 50% of a table does not shrink it. Consider partitioning and DROP/DETACH PARTITION, or TRUNCATE when removing everything.
Long-running transactions block cleanup: an old open transaction or replication slot keeps dead rows "possibly visible", so VACUUM cannot remove them.
Foreign keys: ON DELETE actions run as extra work; an unindexed referencing column turns every parent delete into a scan of the child table.

-- with the pageinspect extension
SELECT lp, t_xmin, t_xmax, t_ctid
  FROM heap_page_items(get_raw_page('acc', 0));
--  lp | t_xmin | t_xmax | t_ctid
--   3 |   1717 |   1718 | (0,3)   ← still there, stamped as deleted

SELECT n_live_tup, n_dead_tup, last_autovacuum
  FROM pg_stat_user_tables WHERE relname = 'acc';

For developers: inside the source

Call flow

parse analysis: setTargetTable() → RowExclusiveLock on the table
planner:        get_relation_info() opens indexes in the same mode
ExecModifyTable() → ExecDelete()           executor/nodeModifyTable.c
  ExecDeletePrologue()   BEFORE ROW triggers
  ExecDeleteAct() → table_tuple_delete() → heapam_tuple_delete()
                → heap_delete()           access/heap/heapam.c
  ExecDeleteEpilogue()   AFTER ROW triggers
CommitTransaction() → RecordTransactionCommit()

Inside heap_delete()

GetCurrentTransactionId() assigns the XID on first write (AssignTransactionId() → GetNewTransactionId() in varsup.c).
The page is locked with LockBuffer(buffer, BUFFER_LOCK_EXCLUSIVE) and HeapTupleSatisfiesUpdate() decides: if another transaction is updating the row (TM_BeingModified) the backend takes the tuple lock (heap_acquire_tuplock()) and sleeps in XactLockTableWait() until that XID ends.
compute_new_xmax_infomask() works out the new xmax and infomask bits (a MultiXact if the row is also share-locked).
In a critical section: PageSetPrunable() sets pd_prune_xid, the all-visible flag and visibility-map bit are cleared, HeapTupleHeaderSetXmax() stamps the tuple, MarkBufferDirty(), then XLogInsert(RM_HEAP_ID, XLOG_HEAP_DELETE) with an xl_heap_delete payload and PageSetLSN().
pgstat_count_heap_delete() bumps the counters autovacuum later reads.

See heap_delete(). The table AM indirection (TableAmRoutine.tuple_delete in tableam.h) is what lets a custom table access method replace all of this.

Commit order

RecordTransactionCommit() writes the commit record with XactLogCommitRecord(), calls XLogFlush() (or only XLogSetAsyncXactLSN() with synchronous_commit = off), then TransactionIdCommitTree() updates pg_xact, then SyncRepWaitForLSN(). Only afterwards does ProcArrayEndTransaction() make the XID look finished to new snapshots.

Observe and test

pageinspect (heap_page_items(), bt_page_items()), pgrowlocks (rows locked through xmax), pg_walinspect (pg_get_wal_records_info()), pg_visibility after VACUUM.
Concurrency behaviour is pinned down by isolation specs such as src/test/isolation/specs/lock-update-delete.spec and delete-abort-savept.spec.
READMEs: heap/README.tuplock (xmax, MultiXacts, tuple locks), heap/README.HOT (pruning).

Parameters that shape this

synchronous_commit lock_timeout autovacuum autovacuum_vacuum_scale_factor autovacuum_vacuum_threshold full_page_writes