Postgres Internals
I've been digging into how Postgres actually stores things on disk, and a bunch of stuff I'd taken for granted suddenly clicked. Four words carry most of the weight: page, tuple, heap, index. Everything below is those four things talking to each other.
A table is just a file
Say I have a table called items. On disk, that table is a file. One file per table.
That file isn't one long blob of rows. It's an array of fixed-size pages, each one 8 kB.
8 kB is the unit Postgres works in. It never reads "a row" off the disk. It reads the entire page that row happens to live in. Every page starts with a small header, so Postgres knows what's inside a page without reading through it, and can jump straight to the one it wants.
Inside a page: line pointers and tuples
A row in Postgres is called a tuple. If items has the fields (item_id, price, vendor), then (10, $10, vendor a) is one tuple.
A page gets built from both ends at once. The header sits at the top, and an array of line pointers grows downward from there. The actual tuple data gets written from the bottom of the page upward. Whatever's left in the middle is free space.
The line pointer is the piece that makes everything else work. It's a tiny entry that says "the tuple you want starts at byte X in this page." Because of it, Postgres can shuffle a tuple around inside its page and only the pointer needs updating. Nothing outside the page has to know.
That's also what gives every row an address: the ctid, which is just a pair of (page number, line pointer index). It's not hidden, you can select it:
SELECT ctid, * FROM items;
ctid | item_id | price | vendor |
|---|---|---|---|
(0, 1) | 10 | 10 | vendor a |
(0, 2) | 20 | 15 | vendor b |
... | ... | ... | ... |
(0,1) means page 0, line pointer 1. That is the physical location of that row on disk.
All of these pages of raw table data together are called the heap. So when you see "postgres goes to the heap," it means it goes and reads the real row data.
Indexes: skipping the scan
Without an index, finding item_id = 10 means reading every page of the heap and checking every tuple in it. Fine for a hundred rows. Terrible for ten million.
An index on item_id is a B-tree, and the easiest way to think about it is a sorted key-value store. Key is the column value. Value is the ctid.
B-trees are shallow and wide, so even with millions of rows you're a handful of hops from the leaf. You land on the leaf, read the ctid, and now you know exactly which page and which line pointer to go read.
Worth saying out loud, because it took me a while: the index doesn't hold your data. It holds pointers to it. You almost always end up going back to the heap anyway.
Hold onto that, because the next section bends it in an interesting way.
The part that surprised me: updates don't update
UPDATE items SET price = 20 WHERE item_id = 10;
Postgres does not find that tuple and overwrite the price. It writes a new tuple, a second version of the same row, and leaves the old one sitting right where it was.
In the good case the new version goes into the same page. So now that page has two tuples both claiming item_id = 10, one with $10 and one with $20.
Here's what that costs, and it connects straight back to the last section. The new version has a new ctid, so every index on the table needs an entry pointing at it. Not just the index on the column you changed. Every index, including ones on columns you never touched, because they all point at physical locations and the physical location just moved. One logical update turns into one heap write plus N index writes. Remember that number, it comes back at the end.
Which also raises the obvious question. When I query for that item, how does Postgres know which version to hand me?
xmin and xmax
Every tuple carries two extra bits of metadata:
xmin: the transaction id that created this version
xmax: the transaction id that deleted or replaced it (
0means nothing has, it's still current)
Also not hidden:
SELECT ctid, xmin, xmax, item_id, price FROM items;
Let's walk the example. Two rows, inserted by transactions 1 and 2:
(0,1) item_id 10 price $10 xmin 1 xmax 0
(0,2) item_id 20 price $15 xmin 2 xmax 0
Now transaction 3 runs that update. Postgres stamps xmax = 3 onto the old tuple and writes a new one with xmin = 3:
Nothing got overwritten. The old version is physically still there, taking up space. This is MVCC, multi-version concurrency control, and it's the reason readers in Postgres don't block writers.
Reading it back
Now I run SELECT price FROM items WHERE item_id = 10; from transaction 5, which started after that update committed. The B-tree lookup finds two entries for item_id = 10, pointing at (0,1) and (0,3). Both get followed into the heap, and each tuple gets checked against my snapshot.
(0,1): created by txn 1, killed by txn 3. Txn 3 had already committed by the time I took my snapshot, so this version is dead as far as I'm concerned. Skip.
(0,3): created by txn 3, which had committed. xmax is 0, so nothing has replaced it. That's my row. Return $20.
Now the interesting case. Somewhere else there's a long-running transaction that opened before txn 3 committed and is still going. Same query, same two tuples, different answer:
(0,1): created by txn 1, which committed long ago, fine. Killed by txn 3, but txn 3 hadn't committed yet when this reader took its snapshot. So as far as it's concerned, nothing has killed this row. Return $10.
(0,3): created by txn 3, which hadn't committed at snapshot time either. This version simply doesn't exist yet from where it's standing. Skip.
So who cleans up the dead rows?
Nobody, right away. That's the tradeoff you're making: cheap non-blocking writes in exchange for garbage piling up in your pages. A background process called vacuum deals with it. It looks for tuples that no open transaction could still possibly need, and frees that space so new tuples can reuse it.
A plain VACUUM never compacts a page. It marks the dead tuples' space reusable inside the page and moves on. There is one bit of disk it hands back though: if vacuum ends up with wholly empty pages at the end of the file, it truncates them off and returns those to the OS. So the file can shrink a little, but only from the tail, and only when the tail happens to be empty.
VACUUM FULL is the one that actually rewrites the whole table into a fresh, tightly packed file and returns the space properly. It also holds an exclusive lock the entire time, so it isn't something you casually run on a live table.
When vacuum can't keep up, or one long-running transaction keeps old versions alive for hours, you get bloat. Tables and indexes much bigger than the data actually in them, and slower queries because every scan is reading past dead tuples to find live ones.
One optimization worth knowing
Remember those N index writes from earlier? Avoiding them is exactly why this next thing exists. Earlier I said the new version ideally lands in the same page. There's a real name for that: a HOT update (heap-only tuple).
If the new version fits in the same page and you didn't touch any indexed column, Postgres skips the indexes entirely. It leaves the old line pointer where it is, chains it forward to the new tuple inside the page, and index lookups follow that chain the rest of the way. The index never learns anything moved, because from its side nothing did. It's still pointing at the same line pointer it always was.
So the two paths are:
normal update: new ctid, and every index on the table gets a new entry
HOT update: same line pointer, chained inside the page, indexes untouched
Which is a pretty good argument for not slapping indexes on columns you update constantly. Every index you add is another write on every non-HOT update, forever.
Resources
interdb.jp
youtube.com