How PostgreSQL stores rows: the heap

Jayesh Karli 14 min read

Part of the series Data structures behind databases

Where the rows go

The last two articles in this series were about indexes. A B-tree or B+ tree finds a key in three or four page reads. But an index on id only tells you where the row with that id is. The row itself has to live somewhere.

In PostgreSQL, it lives in the heap. This article covers what the heap looks like on disk, what happens to it on every insert, update, delete and search, and how indexes connect to it.

A note on names. “Heap” here has nothing to do with the binary heap from algorithms courses, the tree used for priority queues. In database writing, a heap file is the textbook term for a table stored as an unordered pile of rows: a new row goes wherever there is room. PostgreSQL uses the name directly. Its default table storage is called the heap access method. What follows is PostgreSQL’s own version of the idea, with its own page layout and its own rules for row versions.

This is the first of three articles on table storage. The next one covers the same operations in MySQL, and the third compares the two.

Pages, line pointers and tuples

A PostgreSQL table is a file on disk, split into pages of 8 kB each. PostgreSQL also calls them blocks, and numbers them from 0. A page is the unit PostgreSQL reads and writes, just like a node in a B-tree.

Inside a page, each row is stored as a tuple. A page looks like this:

+-------------+----+----+----+-------------------------+---------+---------+---------+
| page header | p1 | p2 | p3 |  -->  free space  <--   | tuple 3 | tuple 2 | tuple 1 |
+-------------+----+----+----+-------------------------+---------+---------+---------+
                 |    |    |                                ^         ^         ^
                 |    |    +--------------------------------+         |         |
                 |    +-----------------------------------------------+         |
                 +--------------------------------------------------------------+
  • The page header (24 bytes) records, among other things, where the free space starts and ends.
  • The line pointers (p1, p2, p3) are a small array that grows from the front. Each one is 4 bytes and holds the offset and length of one tuple.
  • The tuples grow from the back of the page towards the front.
  • When the two meet in the middle, the page is full.

The line pointers are the important part. A row’s address is the pair (page number, line pointer number), called a TID (tuple identifier). PostgreSQL exposes it as a hidden column named ctid. Because the address points at the line pointer and not at the tuple’s byte offset, PostgreSQL can move a tuple around inside its page, for example to close gaps, without changing the row’s address.

Nothing in this layout keeps rows in any order. A row goes on whichever page has room, at the next free line pointer. That is what makes it a heap.

Every tuple is a version

Each tuple starts with a header of about 23 bytes. Three fields in it explain almost everything else in this article:

  • xmin: the ID of the transaction that created this tuple.
  • xmax: the ID of the transaction that deleted or replaced it, or 0 if no transaction has.
  • t_ctid: the TID of the newer version of this row, or the tuple’s own TID if it is the newest.

A tuple is not “the row”. It is one version of the row. When a transaction reads the table, it uses a snapshot, a record of which transactions had committed when it started, and checks xmin and xmax against it to decide whether this version is visible to it. Several versions of the same row can sit in the heap at once, and different transactions can see different ones.

This approach is known as MVCC (multi-version concurrency control). MVCC is an industry term for a family of designs, not one specific algorithm. PostgreSQL’s version keeps every row version in the heap itself, and that choice shapes every operation below. MySQL also uses MVCC but stores old versions elsewhere, which the next article covers.

A table to follow along with

The examples below use one small table. To look inside its pages, they use the pageinspect extension, which ships with PostgreSQL but needs superuser rights. Run it on a local test database, not in production.

CREATE EXTENSION pageinspect;

CREATE TABLE accounts (
    id      int PRIMARY KEY,
    owner   text,
    balance int
);

The PRIMARY KEY creates a B-tree index named accounts_pkey. PostgreSQL calls this index type “B-tree”, but as the B+ tree article explains, it is a modified B+ tree.

Transaction IDs in your own output will differ from the ones shown here.

Insert

INSERT INTO accounts VALUES
    (1, 'atom eve', 100),
    (2, 'invincible', 200),
    (3, 'omni-man', 300);

SELECT ctid, xmin, xmax, * FROM accounts;
 ctid  | xmin | xmax | id |   owner    | balance
-------+------+------+----+------------+---------
 (0,1) |  750 |    0 |  1 | atom eve   |     100
 (0,2) |  750 |    0 |  2 | invincible |     200
 (0,3) |  750 |    0 |  3 | omni-man   |     300

All three rows landed on page 0, at line pointers 1, 2 and 3. Transaction 750 created all of them, and nobody has deleted them yet.

An insert does this:

  1. Find a page with room. PostgreSQL keeps a free space map, a small side file that records roughly how much space each page has left. It asks the map for a page that can hold the new tuple. If no page has room, it adds a new page at the end of the file.
  2. Write the tuple into that page, with xmin set to the current transaction and xmax set to 0.
  3. Add an entry to every index on the table. Each entry holds the indexed key and the new tuple’s TID.

Step 3 is where the cost of indexes shows up. A table with five indexes does one heap write and five index inserts for every new row. Each index insert is a full B-tree descent, and sometimes a page split.

There is also nothing in step 1 about the primary key. The heap does not care about key order, so rows with id 1, 2 and 3 can land on any pages at all. Only the index is sorted.

Update

Now change Invincible’s balance:

UPDATE accounts SET balance = 250 WHERE id = 2;

SELECT ctid, xmin, xmax, * FROM accounts;
 ctid  | xmin | xmax | id |   owner    | balance
-------+------+------+----+------------+---------
 (0,1) |  750 |    0 |  1 | atom eve   |     100
 (0,3) |  750 |    0 |  3 | omni-man   |     300
 (0,4) |  751 |    0 |  2 | invincible |     250

Invincible’s row has moved from (0,2) to (0,4), and it now comes back last. A query without ORDER BY returns rows in whatever order it finds them, and in a heap that order changes as rows are updated.

Look at the raw page to see what happened:

SELECT lp, lp_flags, t_xmin, t_xmax, t_ctid
FROM heap_page_items(get_raw_page('accounts', 0));
 lp | lp_flags | t_xmin | t_xmax | t_ctid
----+----------+--------+--------+--------
  1 |        1 |    750 |      0 | (0,1)
  2 |        1 |    750 |    751 | (0,4)
  3 |        1 |    750 |      0 | (0,3)
  4 |        1 |    751 |      0 | (0,4)

The old version is still there at line pointer 2. An update in PostgreSQL never changes a tuple in place. It does two things:

  1. Writes a complete new tuple with the new values and xmin = 751. Every column is copied, not only the one that changed.
  2. Marks the old tuple with xmax = 751 and points its t_ctid at the new version, (0,4).

So an update is, in effect, an insert plus a delete. Transactions that started before 751 committed still see balance 200 at (0,2). Transactions that start after see 250 at (0,4).

What happens to the indexes

The new tuple has a new TID. An index entry that still says id 2 → (0,2) now points at the old version. There are two ways PostgreSQL handles this.

A normal update adds a new entry to every index on the table, pointing at the new TID. It does this even for indexes whose columns did not change. Update one column of a table with five indexes and you get one new heap tuple and five new index entries. The old entries stay in the indexes until VACUUM removes them. This extra work is often called write amplification, and it is the main cost of PostgreSQL’s update design.

A HOT update (heap-only tuple) skips the indexes entirely. PostgreSQL can use it when both of these hold:

  • No indexed column changed. No index on the table uses any of the columns the update changed. From PostgreSQL 16 on, BRIN indexes do not count against this.
  • The new version fits on the same page as the old one.

Then PostgreSQL adds no index entries at all. The index keeps pointing at the old TID, and a reader that arrives there follows the t_ctid link along the page to the newest version. The chain of versions is called a HOT chain, and it never leaves the page.

The update above was a HOT update. balance is not indexed, and page 0 had plenty of room. You can check it in the primary key index, where id 2 still points at (0,2):

SELECT itemoffset, ctid, data
FROM bt_page_items('accounts_pkey', 1);
 itemoffset | ctid  |          data
------------+-------+-------------------------
          1 | (0,1) | 01 00 00 00 00 00 00 00
          2 | (0,2) | 02 00 00 00 00 00 00 00
          3 | (0,3) | 03 00 00 00 00 00 00 00

(Block 0 of a B-tree index is a metadata page, so in a table this small, block 1 is the root and only leaf.)

To see how many of a table’s updates were HOT:

SELECT n_tup_upd, n_tup_hot_upd
FROM pg_stat_user_tables
WHERE relname = 'accounts';

If the new version does not fit on the same page, PostgreSQL asks the free space map for another page, writes the tuple there, and does a normal update with new entries in every index. The old tuple’s t_ctid then points across to the other page.

Delete

DELETE FROM accounts WHERE id = 3;

A delete is the smallest operation of the four. PostgreSQL finds the tuple and sets its xmax to the deleting transaction, 752 here. That is all. The tuple stays on the page, every index entry pointing at it stays in its index, and no space is freed. Transactions with an older snapshot can still see Omni-Man’s row, which is exactly what MVCC needs.

The row only stops taking up space once no running transaction could still see it. Something then has to come along and clear it out. That job belongs to VACUUM.

VACUUM: cleaning up old versions

Updates and deletes both leave behind tuples that will never be visible to anyone again. PostgreSQL calls them dead tuples. They take up space in the heap, and their index entries take up space in every index. VACUUM finds and removes them:

  1. Scan the heap and collect the TIDs of dead tuples. A side file called the visibility map marks pages where every tuple is visible to everyone, and VACUUM skips those pages.
  2. Remove the index entries for those TIDs, from every index on the table.
  3. Free the line pointers in the heap, so new tuples can reuse them, and record each page’s new free space in the free space map.

You rarely run it by hand. The autovacuum background process runs VACUUM on a table once enough of its rows have changed. After running it on the example table:

VACUUM accounts;

SELECT lp, lp_flags, t_xmin, t_xmax, t_ctid
FROM heap_page_items(get_raw_page('accounts', 0));
 lp | lp_flags | t_xmin | t_xmax | t_ctid
----+----------+--------+--------+--------
  1 |        1 |    750 |      0 | (0,1)
  2 |        2 |        |        |
  3 |        0 |        |        |
  4 |        1 |    751 |      0 | (0,4)

lp_flags is the state of each line pointer: 0 is unused, 1 is a normal tuple, 2 is a redirect and 3 is dead.

  • Line pointer 3 was Omni-Man’s deleted row. Its index entry is gone, so the line pointer is free (0) for the next insert.
  • Line pointer 2 was the old version of Invincible’s row. Its tuple is gone too, but the line pointer survives as a redirect (2) to line pointer 4. The primary key index still says (0,2), so this redirect is what keeps that entry working. HOT chains are why this can happen without touching the index.

HOT chains have one more advantage: PostgreSQL can clean them up without waiting for VACUUM. When a query reads a page that is nearly full, it can prune the page on the spot, removing dead tuples that no transaction can see and turning line pointers into redirects. Pruning cannot remove index entries, so line pointers that indexes still point to stay behind as dead (3) until VACUUM does step 2.

VACUUM has another job that this article only mentions: transaction IDs are 32-bit numbers that eventually wrap around, so VACUUM also freezes old tuples, marking them as visible to everyone forever. That is why autovacuum must never be turned off, even on tables that are rarely updated.

Every query has to get from “which rows match?” to the tuples themselves, and check each one’s xmin and xmax against its snapshot. PostgreSQL has four main ways to do it.

Sequential scan. Read every page of the heap from start to end, and check every tuple. There is no order to exploit, so this is the only option without a usable index. It is also the fastest option when a query needs a large share of the table, because it reads pages one after another.

Index scan. Search the B-tree for the key, get a TID, then read that heap page and check the tuple. For a range of keys, it walks the index leaves in order and fetches each TID’s heap page as it goes. The index lookup itself is a few page reads. The heap fetch is one more, and it can land on any page of the table.

That last point matters. Index entries do not store xmin or xmax, so the index cannot say whether a version is visible. Every index scan has to visit the heap to check. For a range scan over 1,000 keys, that can mean 1,000 heap pages read in random order, because the heap is not sorted by the index key.

Bitmap heap scan. For queries that match many rows, PostgreSQL first collects all matching TIDs from the index, sorts them by page number, and then reads each heap page once, in file order. It is a middle ground between an index scan and a sequential scan, and it can combine several indexes, for example WHERE a = 1 OR b = 2.

Index-only scan. If every column a query needs is in the index, PostgreSQL can answer without the heap, but only for pages the visibility map marks as all-visible. For those pages, every tuple is visible to everyone, so there is nothing left to check. For other pages, it still has to fetch the tuple. A table that VACUUM has kept up with gets the full benefit. A table with many recent changes does not.

EXPLAIN (ANALYZE) SELECT id FROM accounts WHERE id BETWEEN 1 AND 2;

On a larger table, look for Heap Fetches in the output of an index-only scan. It counts the tuples that had to be checked in the heap after all.

Every index is a secondary index

Putting it all together: in PostgreSQL, the table is the heap, and every index is a separate structure that maps keys to TIDs. The primary key index is no different from any other index. It just has a unique constraint and a NOT NULL on its columns.

Two industry terms describe this. A secondary index is an index that points to rows stored somewhere else. A clustered index is one where the table’s rows are stored inside the index itself, in key order. In those terms, every PostgreSQL index is secondary, and PostgreSQL has no clustered index.

PostgreSQL does have a CLUSTER command, which can be confusing given the name. It rewrites the heap once in the order of an index, which raises that column’s correlation. It does not keep the order: rows inserted or updated afterwards go wherever there is room, as usual.

This design has consequences in both directions:

  • Indexes are cheap to point. A TID is 6 bytes, the same size whatever the primary key looks like. A long text primary key does not make the other indexes any bigger.
  • Every lookup through an index costs a heap fetch, unless an index-only scan can avoid it.
  • A row’s TID changes whenever it is updated outside a HOT chain, which is why a normal update has to touch every index. It is also why you should never store ctid as a row identifier: an update or a VACUUM FULL will change it.

PostgreSQL’s B-tree indexes have features to soften the update cost. Deduplication (PostgreSQL 13) stores a key that repeats, such as many versions of the same row, once with a list of TIDs. Bottom-up index deletion (PostgreSQL 14) removes entries for dead versions when a leaf page is about to split, which slows the growth of indexes on tables with many normal updates. Index scans also flag an index entry as dead once they find its tuple is dead for everyone, so later scans can skip it.

Summary

Operation Heap Indexes
Insert New tuple on any page with room, found through the free space map New entry in every index
Update (normal) New tuple. The old one gets xmax and a link to the new one New entry in every index, even for unchanged columns
Update (HOT) New tuple on the same page, linked into a HOT chain Nothing. Indexes keep pointing at the start of the chain
Delete Sets xmax. The tuple stays Nothing until VACUUM
Search Every match is checked against the snapshot in the heap Index gives TIDs. Index-only scans skip the heap for all-visible pages
VACUUM Frees dead tuples and line pointers, updates free space and visibility maps Removes entries pointing at dead tuples

The heap’s design comes down to one choice: never overwrite a row, write a new version instead, and clean up later. That makes inserts, deletes and rollbacks cheap and lets readers and writers work without blocking each other. The price is paid in updates that touch every index, in dead tuples that pile up until VACUUM runs, and in index scans that always go back to the heap.

The next article in this series looks at the same four operations in MySQL’s InnoDB storage engine, which makes the opposite choice: the table is stored inside its primary key index. The article after that compares the two designs side by side.