How PostgreSQL Runs a Query

One process per connection, one heap per table

This page runs the same table and the same four statements as How MySQL Runs a Query, so the two can be compared step by step. The big differences are where a table's rows live (a heap, not a B-tree), how old versions are kept (in the heap itself, not in an undo log), and how they are cleaned up (VACUUM).

CREATE TABLE users (id int PRIMARY KEY, name text, age int);   -- also creates index users_pkey
CREATE INDEX idx_age ON users (age);

From text to plan

1. Backend process. The postmaster forks a new OS process for every client connection. Each backend has its own memory (work_mem for sorts and hashes) and shares only shared memory: shared buffers, WAL buffers, the lock table and pg_xact. A fork per connection is costly, which is why connection poolers such as PgBouncer are common.
2. Parser and analyzer. The grammar builds a raw parse tree; the analyzer resolves names against the system catalogs (pg_class, pg_attribute) and produces a Query tree. Opening a table takes a table-level lock: AccessShareLock for reads, RowExclusiveLock for writes. They only conflict with things like ALTER TABLE.
3. Rewriter. Applies rules: a view is replaced by its query here, and row-level security policies are added.
4. Planner. Enumerates paths (Seq Scan, Index Scan, Bitmap Heap Scan, Index Only Scan, join orders and methods) and costs them with the statistics ANALYZE keeps in pg_statistic. EXPLAIN prints the winner.
5. Executor. Runs the plan tree; each node pulls tuples from its children. It takes a snapshot first.

The heap and TIDs

A PostgreSQL table is a heap: a file of 8 KB blocks in which tuples are placed wherever there is room (the free space map knows where). A tuple's address is its TID, (block, line pointer), shown as ctid. The primary key is not special: users_pkey is an ordinary B-tree whose entries map id → TID, exactly like idx_age maps age → TID. So any index lookup costs an index descent plus one heap visit, and a query with no usable index is a Seq Scan through the blocks in order. (In InnoDB, by contrast, the table is the primary-key B-tree and secondary indexes store the key.)

MVCC with xmin and xmax

Every heap tuple carries two transaction ids: xmin, the transaction that created this version, and xmax, the one that deleted or replaced it (0 if none). Whether those transactions committed is recorded once per xid in pg_xact (the commit log, CLOG), two bits each. A snapshot lists which xids were still running when it was taken. A tuple is visible if its xmin committed before the snapshot and its xmax did not.

• INSERT writes a tuple with xmin = its xid.
• DELETE only sets xmax. Setting xmax is also the row lock: another writer that finds an xmax from a running transaction waits on that transaction's transactionid lock. No per-row lock is kept in memory.
• UPDATE = delete + insert: xmax on the old version, a complete new tuple with the new values, and the old tuple's t_ctid pointing to it. PostgreSQL even writes a new version when no value changes.
• COMMIT flips the xid to committed in pg_xact; ROLLBACK or an error flips it to aborted. No data page is touched either way, and there is no undo: a failed transaction leaves its tuples behind, invisible. Run Demo: failed INSERT.

Readers never block writers and writers never block readers, as in InnoDB. The price is that old versions pile up in the table and its indexes until VACUUM removes them.

Indexes do not know about visibility

An index entry has no xmin/xmax. An index may hold several entries for the same key, one per row version, and the executor must visit the heap to find out which one, if any, the snapshot can see. That is also why a unique index checks for duplicates by visiting the heap (_bt_check_unique). An Index Only Scan can skip the heap only for blocks the visibility map marks all-visible, and only VACUUM sets those bits.

HOT updates

A plain update needs a new entry in every index, even those whose columns did not change, because the new version has a new TID. That is the main cost of PostgreSQL's design for write-heavy tables. The fix is the heap-only tuple (HOT): if no indexed column changes and the new version fits on the same block, no index entry is written. The old version's t_ctid forms a chain inside the block (» in the animation), and index lookups follow it. Later, pruning replaces the dead start of the chain with a redirect line pointer. Compare Demo: UPDATE (age is indexed: two new index entries) with Demo: HOT update (name is not: none). Leaving free space in blocks with fillfactor (e.g. 90) makes HOT updates more likely.

WAL, commit and checkpoints

Every change to a page is described by a WAL record in the WAL buffers before the page may be written (write-ahead logging). At commit the backend adds a COMMIT record and flushes WAL up to it with fsync (synchronous_commit = on); data pages stay dirty in shared buffers. The checkpointer later writes them, then logs a checkpoint whose REDO point is where crash recovery will start. Because an 8 KB page write can be torn by a crash, the first change of each page after a checkpoint logs the full page image (full_page_writes), the +FPI in the animation, which is why WAL volume jumps right after a checkpoint. InnoDB solves the same problem with its doublewrite buffer.

The WAL is also the replication stream: the walsender ships it to standbys, which replay it. There is no separate binlog, and so no two-phase commit between two logs.

VACUUM

Dead tuples (xmax committed, or xmin aborted) stay until VACUUM, normally run by autovacuum, removes them in three passes:

1. Prune the heap. Dead heap-only tuples are freed at once; a dead chain start becomes a redirect to the live version; other dead tuples become LP_DEAD stubs, because index entries still point at them.
2. Clean the indexes. Each index is scanned and the entries pointing at LP_DEAD TIDs are removed.
3. Free the line pointers. The stubs become unused; the free space map and visibility map are updated.

The freed space is reused by later inserts and updates, but the file does not shrink (only VACUUM FULL rewrites it, under an exclusive lock). VACUUM can only remove versions that no snapshot can still see, so a long-running transaction, or one left "idle in transaction", holds back every table's cleanup and causes bloat. VACUUM also freezes old tuples, which is essential: xids are 32-bit and wrap around after about 2 billion transactions.

Crash recovery

On restart the startup process reads pg_control, finds the REDO point of the last checkpoint and replays every WAL record after it. A page's first record carries a full-page image that replaces whatever is on disk, and later records are applied on top. Commit status comes from the replayed COMMIT and ABORT records; a transaction that has neither simply counts as aborted. Because nothing needs undoing, there is no undo phase. Recovery ends with a checkpoint. Run the last demo: the delete of id 3 was never written to the data file, yet after the crash it is still gone.

PostgreSQL and MySQL/InnoDB side by side

	PostgreSQL	MySQL / InnoDB
Connections	a process each	a thread each
Table storage	heap (unordered); every index points to a TID	clustered B-tree on the primary key; secondary indexes hold the key
Old row versions	in the heap, next to the new ones	in the undo log; the row is updated in place
UPDATE of a non-indexed column	new tuple; HOT if it fits on the block, otherwise new entries in every index	in place; secondary indexes untouched
Commit status	pg_xact, two bits per xid	transaction state in the undo/redo logs
Rollback	instant: mark the xid aborted	apply the undo records
Cleanup	VACUUM / autovacuum (heap and indexes)	purge threads (undo and delete-marked records)
Logs	WAL only, also used for replication	redo log + binlog, two-phase commit
Torn-page protection	full-page images in WAL	doublewrite buffer
Page size	8 KB	16 KB

What the animation leaves out

• Other sessions, isolation levels, lock waits and deadlocks; explicit BEGIN … COMMIT/ROLLBACK (every statement commits by itself here).
• Hint bits: the first reader after a commit records "xmin committed" in the tuple itself, so a plain SELECT can dirty a page.
• Page splits and the relation growing: here the heap has 3 blocks of 9 line pointers and each index leaf 14 entries, and autovacuum runs early to make room.
• Opportunistic pruning during reads, B-tree bottom-up deletion, TOAST for large values, the background writer, WAL segment recycling and group commit.

Practical consequences

• Watch n_dead_tup and last_autovacuum in pg_stat_user_tables; tune autovacuum per table for hot tables.
• Keep transactions short and avoid "idle in transaction" sessions: they hold back VACUUM everywhere.
• Don't index columns you update often unless you need to: every extra index turns HOT updates into ordinary ones. n_tup_hot_upd shows how many updates were HOT.
• Use EXPLAIN (ANALYZE, BUFFERS) to see shared-buffer hits and reads for a query.
• Pool connections: each one is a process.

See also How MongoDB Runs a Command (the same data in a document store: WiredTiger update chains, journal, oplog and write concern).

References

Concurrency Control: MVCC (PostgreSQL documentation)

Heap-Only Tuples (HOT)

Routine Vacuuming

Write-Ahead Logging

The Internals of PostgreSQL (Hironobu Suzuki)