The Heap,
Byte by Byte

It started with a simple question I couldn't answer: when I insert a row into a PostgreSQL table, what exactly gets written, and where?

I read the docs. I read blog posts. They all showed the same box-and-arrow diagram of a "page" and moved on. But I wanted to know what the actual bytes look like — where a NULL goes, why ALTER TABLE ADD COLUMN on a huge table can finish instantly, how an index finds a row. At some point I accepted the truth every engineer eventually meets: if you can't build it, you don't understand it.

So I built HeapProbe: my own storage engine, written in Rust. It is not a toy drawing of PostgreSQL — it stores tables as real 8192-byte arrays with PostgreSQL's exact on-disk layout: the same 24-byte page header at the same offsets, the same bit-packed line pointers, the same tuple header flags with the same bit values, the same null bitmap rules. When HeapProbe shows you a byte, that's genuinely the byte, decoded on demand — never a mock-up. Where I deliberately left something out (and I left out some big things — transactions, crash recovery, TOAST), I'll tell you exactly what PostgreSQL does there instead. That side-by-side is the whole point of this post.

And you don't have to take my word for any of it: HeapProbe runs live in your browser at heapprobe.tuttrue.sh. Open it in another tab, insert some rows, and inspect every byte this post talks about — for real, as you read.

Before we start, seven words you'll meet constantly. Skim them now, come back whenever:

Everything below follows one path: from the whole table, down into a single page, down into a single row, down into single bits — then back up to watch a query travel the whole structure. Let's dig.

Here's the first thing that surprised me: a PostgreSQL table is, physically, just a plain file on disk — and that file is nothing more than an array of fixed-size 8 KB pages, glued end to end. This pile of pages is the heap.

There is no ordering, no clustering, no cleverness at this level. Rows get placed wherever there happens to be room. Page 0 is bytes 0–8191 of the file, page 1 is bytes 8192–16383, and so on. When every page is full, PostgreSQL appends a fresh one to the end of the file. HeapProbe works the same way: a table is literally a Vec (a growable array) of 8192-byte pages.

 users table  =  base/16384/24576  (one file on disk)

 ┌─────────────┬─────────────┬─────────────┬─────────────┬─ ─ ─ ─
 │   page 0    │   page 1    │   page 2    │   page 3    │  ...
 │  8192 bytes │  8192 bytes │  8192 bytes │  8192 bytes │
 └─────────────┴─────────────┴─────────────┴─────────────┴─ ─ ─ ─
 byte 0        8192          16384         24576

Because pages are fixed-size, any row in the entire table can be named with just two numbers: which page, and which slot within that page. That pair is the tuple identifier (TID). This isn't hidden trivia — you can ask any real PostgreSQL table for it right now via the hidden ctid column:

SELECT ctid, * FROM users;

  ctid  | id | name
--------+----+-------
 (0,1)  |  1 | ada      -- page 0, slot 1
 (0,2)  |  2 | grace    -- page 0, slot 2
 (3,7)  | 99 | edsger   -- page 3, slot 7

Hold on to this idea, because it's the spine of everything that follows: every index in PostgreSQL — B-tree, GIN, all of them — ultimately hands back one of these (page, slot) pairs, and then the database goes to the heap to fetch the actual row. Understand the heap page, and you understand where every query finally lands.

Inside those 8192 bytes, a tidy little economy runs. Bookkeeping grows down from the top of the page; row data grows up from the bottom; and the free space is whatever's left in the middle, getting pinched from both ends.

 byte 0
 ┌──────────────────────────────────────────────────────┐
 │ PageHeaderData (24 B)                                │
 ├──────────────────────────────────────────────────────┤
 │ linp1 │ linp2 │ linp3 │ →  line pointers grow DOWN   │
 ├───────┴───────┴───────┴──────────────────────────────┤
 │            ▲ pd_lower                                │
 │                                                      │
 │                  f r e e   s p a c e                 │
 │                                                      │
 │                                 pd_upper ▼           │
 ├──────────────────────────────────────────────────────┤
 │   ← tuple3  │  ← tuple2  │  ← tuple1 (grow UP)       │
 ├─────────────┴────────────┴───────────────────────────┤
 │ "special space" (0 B on heap pages)      pd_special ▲│
 └──────────────────────────────────────────────────────┘
 byte 8192

Four kinds of tenant share the page:

1. The page header — 24 bytes of metadata at the very start. Chapter 03 dissects it field by field.
2. Line pointers — a tiny 4-byte directory entry for each row, appended just after the header. The "slot" in a TID is a position in this directory. Chapter 04 explains why this indirection is one of the smartest choices in the whole design.
3. Tuples — the rows themselves, packed from the end of the page backwards, each one's start rounded to a multiple of 8 bytes (a rule called MAXALIGN — CPUs read 8-byte-aligned data faster).
4. Special space — a reserved tail. Heap pages leave it empty; B-tree index pages (which reuse this same page format!) stash their metadata there.

Reading about this is one thing — watching it move is another. The figure below is a live heap running HeapProbe's actual insertion logic. Insert rows and watch pd_lower creep down and pd_upper creep up until they meet:

Try this: insert jumbo rows until the page refuses one, then insert a narrow row. It squeezes into the leftover gap on the old page. Which raises a question — how does the database find a page with enough room, without checking them all?

The first 24 bytes of every page are PageHeaderData — the page's passport. Eight fields, fixed offsets, little-endian (multi-byte numbers stored least-significant-byte first, like almost every CPU you own). HeapProbe writes this header with the same fields at the same offsets as PostgreSQL. Hover (or tap) each field below to decode it.

Between the header and the free space sits an array of line pointers (PostgreSQL calls the struct ItemIdData): one 4-byte directory entry per row. A TID like (0,2) never points at a tuple directly — it points at line pointer #2, which holds the tuple's actual byte offset.

When I first implemented this I thought the extra hop was wasteful. Then I implemented DELETE and understood. The answer is stability: tuples get shuffled around inside a page (compaction after deletes — chapter 08), but indexes all over the database hold TIDs. With the indirection, a tuple can move freely within its page: only its line pointer's offset field changes, and every index in the database stays valid without being touched.

Here's the part that made me respect the format: all three fields are bit-packed into a single 32-bit integer — the C bitfield lp_off:15, lp_flags:2, lp_len:15. Why 15 bits? Because 2¹⁵ = 32768 comfortably addresses any offset or length inside an 8192-byte page, and 15 + 2 + 15 = 32 exactly. Nothing wasted. I packed mine with the same shifts and masks — try it yourself:

The two flag bits give four states:

Follow a line pointer and you land on a heap tuple — the row itself. It has three parts: a small header, an optional null bitmap, and then the column values packed one after another. Here is the layout HeapProbe writes:

 offset 0   t_infomask2   u16   attribute count in the low 11 bits
 offset 2   t_infomask    u16   flag bits: HEAP_HASNULL | HEAP_HASVARWIDTH | …
 offset 4   t_hoff        u8    where the user data starts (MAXALIGNed)
 offset 5   t_bits        ceil(natts / 8) bytes — ONLY if HEAP_HASNULL
 ⋮          (zero padding up to t_hoff)
 t_hoff     column data, one after another; NULL columns take 0 bytes

Three header fields do a lot of work — let me introduce each:

1. t_infomask2 — the low 11 bits store natts, the number of columns this tuple was written with. Note the phrasing: not the table's current column count, the count at write time. Eleven bits allow 2047, comfortably above PostgreSQL's 1600-column limit. This little number is the entire secret behind instant ALTER TABLE (chapter 07).
2. t_infomask — a row of yes/no flags. HEAP_HASNULL (0x0001) says "a null bitmap follows"; HEAP_HASVARWIDTH (0x0002) says "at least one variable-width value inside". I used PostgreSQL's exact bit values. PostgreSQL packs many more MVCC hint bits in here.
3. t_hoff — the offset where column data begins, rounded up to a multiple of 8. The gap between the bitmap and t_hoff is zero padding — and that padding has a delightful consequence in the next chapter.

Then come the values — with no per-column headers, no names, no types. An int4 is 4 raw bytes; a float8 is 8; a text is a varlena ("variable-length attribute"): a 4-byte length word followed by the characters. The tuple is meaningless without the table's schema, which lives in the system catalogs — the schema says "the first 4 bytes are id, then comes name…" and the decoder walks the bytes left to right. Here's a complete tuple, annotated byte by byte:

-- INSERT INTO users VALUES (7, true);          -- (id int4, ok bool)
-- the tuple HeapProbe writes, annotated:
02 00        t_infomask2 = 2 (this row has 2 attributes)
00 00        t_infomask  = 0 (no nulls, no varwidth)
08           t_hoff = 8   (maxalign(5), no bitmap)
00 00 00     padding to t_hoff
07 00 00 00  id = 7   (int4, little-endian)
01           ok = true (bool, 1 byte)
             → 13 bytes total; stored as 16 after MAXALIGN

This was my favorite thing to implement. How do you store nothing? The naive answer is a placeholder — 4 or 8 wasted bytes per NULL. PostgreSQL's answer: a NULL column occupies zero data bytes. Its existence is recorded in exactly one bit, in the null bitmap (t_bits) at the front of the tuple. HeapProbe implements the same rules, and they answer the "how is the bitmap sized?" question precisely:

1. One bit per column — so the bitmap needs ceil(natts / 8) bytes (that's "divide by 8 and round up", since 8 bits fit in a byte). 1–8 columns ⇒ 1 byte; 9–16 ⇒ 2 bytes; 17–24 ⇒ 3 bytes. Leftover bits in the last byte are padding.
2. Bit convention: bit set (1) = value present; bit clear (0) = NULL. Column i lives at byte i/8, bit i%8.
3. The bitmap only exists if at least one value is NULL. A row with no NULLs skips it entirely and clears HEAP_HASNULL — rows that never use NULL never pay for it.
4. Decoding skips NULLs: the reader walks columns left to right; on a cleared bit it emits NULL and advances zero bytes through the data.

Toggle columns below and watch the bitmap, t_hoff, and the data bytes react:

And here's the delightful consequence I promised. Because t_hoff is rounded up to a multiple of 8 anyway, the bitmap often hides inside bytes that would have been padding — costing literally nothing:

This is why the common advice "NULLs are cheap in PostgreSQL" is true: a nullable column that is NULL in most rows costs one bit per row — and frequently zero bytes — not a 4- or 8-byte placeholder.

Here's a magic trick that motivated this whole project: ALTER TABLE users ADD COLUMN score float8 on a billion-row table returns in milliseconds. A billion rows lack the new column — how can that be free? Answer: none of them is touched. Not one page byte changes. I didn't believe it until I implemented it in HeapProbe and watched my own pages stay bit-for-bit identical.

The trick is that little natts from chapter 05. Each tuple permanently records how many columns existed when it was written. When the table gains a column, only the schema (in the catalogs) changes; when a row is later read, the decoder follows this rule:

for att in 0..schema.natts:
    if att >= tuple.natts:        → column added after this row: implicit NULL ("missing")
    elif bitmap bit att is clear: → explicit NULL stored with the row
    else:                         → decode the next bytes as this column's value

Old rows simply run out of columns early, and every column past their own natts decodes as NULL. New rows record the larger natts and store the column for real — or as a bitmap-bit NULL, which is a genuinely different thing on disk, as you're about to see. Step through it:

Deleting a row from the middle of a page leaves a hole in the tuple area — free bytes, but stranded away from the main free space, where they're useless for a new row. The fix is compaction: slide the surviving tuples toward the end of the page, update each one's line pointer offset, and the free space is one contiguous block again. And here the line-pointer indirection pays off completely: slots never move, so every TID — and every index entry in the database — stays valid.

When can you actually do this? This is where HeapProbe and PostgreSQL diverge the most, and the reason is the deepest idea in this post:

Now everything assembles into one story. Take SELECT * FROM users WHERE id = 21, with a unique index on id. In HeapProbe I made the engine expose the whole journey as explicit steps precisely so it could be replayed slowly — run it below.

Read the step list once more, slowly. An index never returns a row — it returns a TID, and the heap does the rest. That second trip is why PostgreSQL grew index-only scans, visibility maps, and covering indexes: a whole optimization industry exists to avoid, or cheapen, the right half of this figure.

Building HeapProbe taught me as much through what I skipped as what I wrote. Here is the full, honest ledger — everything PostgreSQL does that my engine doesn't, and what each omission is really about. Every row of this table is a door into a deeper PostgreSQL subsystem.

The heap is not a black box. It's 8192 bytes with a 24-byte passport, a directory that grows down, rows that grow up, and a handful of beautiful conventions — bit-set-means-present, align-to-eight, count-your-own-columns — that make NULLs free, ALTER TABLE instant, and forty years of relational databases possible. I know this now because I built it. You know it because you just watched it run. Now open heapprobe.tuttrue.sh and go read a page header in the wild.