Appearance
7.3.1 — Pages, Files and the Buffer Pool
Ask most engineers where a row lives and the honest answer is a shrug shaped like a text file: rows underneath each other, one per line, and WHERE id = 42 finds line 42.
Nothing about that is true, and the truth explains a long list of otherwise arbitrary behaviours — why an index helps, why an UPDATE can make a table bigger, why the first query after a restart is slow, why column order affects table size, and why "the database is slow" is usually a memory question rather than a disk question.
1. A table is a set of files, and a file is a set of pages
A PostgreSQL database is a directory. Each table and each index is one or more files, and each file is split into fixed-size pages (also called blocks) of 8 KB. InnoDB uses 16 KB, SQL Server 8 KB, Oracle 8 KB by default.
The page is the unit of everything. The engine never reads one row from disk; it reads the 8 KB page containing it. It never writes one row; it writes the page. The buffer pool caches pages. The write-ahead log records changes to pages. Once you know the page is the atom, most of the rest follows.
Why a fixed-size page at all? Because storage hardware has no concept of a row. A disk transfers sectors, an SSD reads and erases in pages and blocks of its own, and the operating system's file cache works in 4 KB units (Chapter 2.5). Reading a fixed, aligned chunk matches what the hardware is going to do anyway. A fixed size also makes addressing trivial: page 517 starts at byte 517 × 8192, computed rather than looked up.
Why 8 KB and not 512 bytes or 1 MB? It is a compromise between two costs. Smaller pages waste less space when you only want one row, but need more of them to hold a table and make indexes taller. Larger pages amortise the read but drag in data you did not want and make each write bigger. 8–16 KB is where the industry settled and nobody argues about it much.
Very large tables are split into 1 GB segment files (12345, 12345.1, 12345.2), which exists purely so that no single file has to be enormous — a historical filesystem constraint that stayed because it also makes copying and repairing easier.
2. Inside a page
Four regions:
The header — 24 bytes holding the page's log sequence number (which write-ahead log record last touched it, Chapter 7.3.3), checksum, and where free space starts and ends.
The line pointer array — one small entry per row, each holding an offset and a length. This is the slotted page design, and the indirection is the point: a row can be moved within its page to compact free space, and only the pointer changes. Every index entry points at (page number, slot number), never at a byte offset, so reorganising inside a page breaks nothing.
Free space in the middle, shrinking from both ends as rows are added.
The rows themselves, written from the end of the page backwards.
A row's address is therefore a pair. PostgreSQL calls it ctid and you can select it: SELECT ctid, id FROM orders LIMIT 1 gives something like (0,1) — page 0, slot 1. That pair is what every index entry ultimately resolves to.
Two consequences fall out immediately.
A row cannot exceed a page. PostgreSQL's answer is TOAST (the oversized-attribute storage technique): values over roughly 2 KB are compressed, and if still too large, split into chunks stored in a hidden side table, with a pointer left in the row. This is why a table with big text columns often shows a small main table and a huge TOAST table, and why SELECT * on such a table costs far more than selecting the three columns you wanted — the large column is fetched and de-TOASTed only if you ask for it.
Column order affects table size. Fixed-width columns are aligned to their natural boundaries, so bool, bigint, bool, bigint pads each boolean out to 8 bytes and wastes 14 bytes per row. Ordering as bigint, bigint, bool, bool packs them. On a hundred million rows that is over a gigabyte, for free. It is a micro-optimisation, and it is the only one on this page that costs nothing to apply.
3. Heap tables versus clustered indexes
This is the biggest structural difference between engines, and it explains behaviours people wrongly attribute to speed or quality.
PostgreSQL uses a heap. Rows are stored in no particular order, wherever there is room. Every index — including the primary key's — is a separate structure holding key → ctid. All indexes are equal; there is no privileged one.
InnoDB (MySQL) and SQL Server use a clustered index. The table is a B+ tree keyed on the primary key, with the whole row stored in the leaf. There is no separate heap. Secondary indexes store key → primary key value, not a physical address.
| Heap (PostgreSQL) | Clustered (InnoDB) | |
|---|---|---|
| Primary key lookup | Index scan, then fetch the row | Row is in the index leaf |
| Secondary index lookup | Index, then row | Index → PK → second tree walk |
| Rows physically ordered | No | By primary key |
| Range scan on PK | Random reads | Sequential |
| Cost of a big PK | One copy | Repeated in every secondary index |
Read the last two rows carefully, because they are the practical consequences.
In InnoDB, a secondary index lookup costs two tree traversals — one to find the primary key, one to find the row. So a covering secondary index (Chapter 7.3.2), which avoids the second traversal, matters more in MySQL than in PostgreSQL.
And in InnoDB every secondary index stores the primary key inside it. A 36-character string primary key is copied into every entry of every secondary index. This is the mechanism behind the UUID warning in Chapter 7.2.4 — it is not folklore, it is a measurable multiplication of index size.
Neither design is better. The heap makes all indexes equal and updates cheap to place; the clustered index makes primary-key range scans sequential and primary-key lookups a single traversal.
4. The buffer pool: where performance actually lives
Reading a page from an SSD takes on the order of 100 microseconds. Reading it from memory takes about 100 nanoseconds — a thousand times faster (Chapter 1.6 has the full hierarchy). So the engine keeps a large in-memory cache of pages.
That cache is the buffer pool (shared_buffers in PostgreSQL, innodb_buffer_pool_size in MySQL), and it is the single most important configuration value in a database.
How a read works, end to end. The query needs the row at page 517. Is page 517 in the buffer pool? If yes — a buffer hit — the work is done in nanoseconds. If not, the engine picks a victim page to evict, reads page 517 from the operating system (which may itself have it cached), places it in the pool, and pins it while it is used.
How a write works, and why this is the surprising part. An UPDATE modifies the page in memory and marks it dirty. It is not written to the data file at that moment. What is written immediately, before the transaction can commit, is the write-ahead log record describing the change (Chapter 7.3.3). Dirty pages are flushed later, in bulk, by a background writer and at checkpoints.
That is why a database can be fast and durable at the same time. The durable write is a small sequential append to a log; the expensive random writes to data files are deferred, batched, and often absorbed entirely — a page updated fifty times before the next checkpoint is written once.
Eviction. Textbooks say LRU. Real engines do not use plain LRU, because a single large sequential scan would evict the entire working set — the pattern called cache pollution. PostgreSQL uses a clock sweep with usage counts, and reads a large sequential scan through a small ring buffer so it cannot flush the pool. InnoDB uses a midpoint-insertion LRU: new pages enter at the middle of the list, and only get promoted to the hot end if they are read again after a short delay.
Sizing. PostgreSQL's usual guidance is 25% of system memory, because it also relies on the operating system's page cache, so a page is often cached twice and giving PostgreSQL everything wastes memory. MySQL's guidance is the opposite — 70–80% of memory to InnoDB, because it uses direct I/O and bypasses the OS cache. Copying one engine's advice to the other is a common and expensive mistake.
Hit ratio. SELECT sum(blks_hit) * 100.0 / sum(blks_hit + blks_read) FROM pg_stat_database; A well-fitted OLTP system reads almost everything from memory. But treat the ratio as a symptom, not a target — a 99% hit ratio on a query running a million times is still 10,000 disk reads, and a low ratio during a nightly report is completely normal. EXPLAIN (ANALYZE, BUFFERS) from Chapter 7.2.3 tells you about your query, which is what you can act on.
The working set is the number that matters. If the pages you actually touch fit in the buffer pool, the system is fast. When the table grows past that point, performance does not degrade gently — it falls off a step, because reads start hitting storage. Almost every "the database suddenly got slow at 3 million rows" story is the working set crossing the buffer pool, and no amount of query tuning changes it. That is also the real reason the random-UUID key from Chapter 7.2.4 hurts: it makes the working set the entire index rather than its recent end.
5. Free space, fill factor and why an UPDATE grows a table
In PostgreSQL, an UPDATE does not modify a row in place. It writes a new version of the row and marks the old one dead. That is the MVCC design in Chapter 7.4.2, and it has a direct storage consequence.
If the new version fits on the same page, the engine can use a HOT update (heap-only tuple), where the old row's line pointer redirects to the new one and no index needs updating at all. That is a big saving: a table with five indexes normally pays five index writes per update.
If the page is full, the new version goes on another page, and every index must be updated to point at it.
Fill factor is the knob for this. ALTER TABLE orders SET (fillfactor = 85); tells the engine to leave 15% of each page empty when filling it, so future updates have somewhere local to go. It is worth setting on heavily updated tables and pointless on append-only ones, where you want pages full.
The old versions are the reason VACUUM exists. They stay in the page, occupying space, until vacuum marks them reusable. Without it the table bloats — the same live rows spread over more and more pages, so every scan reads more. This is the storage-level explanation of the warning in Chapter 7.2.3.
InnoDB updates in place where it can and keeps old versions in a separate undo log, so the shape of the problem differs — but the same purge process must run, and the same growth happens if it falls behind.
Index pages have the same story with a different name. When a B+ tree leaf is full and a key must be inserted in the middle, the page splits into two half-full pages. Random insertion order causes constant splitting and leaves indexes half empty; sequential insertion appends and packs tightly. That is the third and final explanation of the sequential-versus-random key question, now from the index's side.
6. Where the time actually goes
Putting the layers together for SELECT total FROM orders WHERE id = 42:
- Parse and plan — microseconds, and often skipped entirely by a prepared statement.
- Walk the index. Three or four page reads for a tree over a few million rows (Chapter 4.13.3 has the fanout arithmetic). Upper levels are almost always in the buffer pool.
- Resolve to a page and slot, and fetch that page. Hit or miss.
- Check visibility. Is this row version visible to my transaction (Chapter 7.4.2)?
- Return the row across the network.
In a healthy system every one of those steps is memory-speed, and the network round trip is the largest single cost. That is worth stating clearly, because it reframes optimisation: once the working set fits in memory and the indexes are right, the wins move to fewer round trips — which is exactly why N+1 (Chapter 7.2.4) dominates real applications.
Row-oriented storage is assumed throughout this page. Everything here puts a whole row together in a page, which is right when queries touch a few rows and most of their columns. Analytical queries touch millions of rows and three columns, and want the opposite layout entirely. Chapter 7.8.1 makes that case.
What the interviewer will push on
"How is a table stored on disk?" As a set of files split into fixed-size pages, typically 8 or 16 KB, each page slotted: header, line pointers, free space, rows growing backwards. The tell is naming the indirection — an index points at (page, slot), so a row can move within its page without touching any index.
"What is the buffer pool and why does it matter more than the disk?" It caches pages in memory, and memory is about a thousand times faster than an SSD. The real answer is the working set: while the pages you touch fit in the pool the system is fast, and when it stops fitting performance falls off a step. Most "suddenly slow at N rows" incidents are that crossing, not a query problem.
"Why is a write fast if it is also durable?" Because commit writes a small sequential record to the write-ahead log, while the data page is modified in memory and flushed later at a checkpoint. Sequential append instead of random write, and repeated updates to one page collapse into a single flush.
"What is the difference between a heap and a clustered index?" In a heap all indexes are equal and point at a physical location; in a clustered index the table is the primary key's B+ tree and secondary indexes point at the primary key, costing a second traversal. Then draw the consequence: in InnoDB the primary key is copied into every secondary index, so a large random key multiplies index size — which is the mechanism behind the UUID advice, rather than folklore.
"Why does an UPDATE make a table bigger?" MVCC writes a new row version and leaves the old one dead until vacuum reclaims it. If the new version fits on the same page it can be a HOT update with no index writes; if not, every index must be updated. Fill factor reserves space so updates stay local.
"How would you size shared_buffers?" About 25% of memory in PostgreSQL, because the operating system's page cache is also used and you would otherwise cache pages twice; 70–80% for InnoDB, which uses direct I/O. Volunteering that the guidance is opposite between the two engines is the answer that shows real operational exposure.
One thing to volunteer: mention that column order changes table size because of alignment padding — bool, bigint, bool, bigint wastes 14 bytes a row that bigint, bigint, bool, bool does not. It is small, it is free, and it demonstrates that you know what a row physically looks like rather than what it looks like in a diagram.
Recall
- A table is files split into fixed-size pages (8 KB PostgreSQL, 16 KB InnoDB). The page is the unit of reading, writing, caching and logging — the engine never touches a single row on disk.
- A page is slotted: header, line pointers, free space, rows growing backwards. An index points at (page, slot), so a row can move inside its page without any index changing. Values too big for a page are pushed out via TOAST.
- Heap versus clustered index is the main engine difference. PostgreSQL heaps make all indexes equal; InnoDB stores the row in the primary key's leaf, so secondary lookups cost two traversals and the primary key is copied into every secondary index.
- The buffer pool caches pages; memory is ~1,000× faster than SSD. The working set fitting in it is the performance cliff — falling off it is the usual cause of a sudden slowdown at a data-size threshold.
- Writes modify pages in memory and mark them dirty; durability comes from the sequential write-ahead log, and dirty pages flush later at checkpoints. That is how fast and durable coexist.
- Real engines do not use plain LRU — a big sequential scan would evict everything. PostgreSQL uses a clock sweep plus a ring buffer for large scans; InnoDB uses midpoint-insertion LRU.
shared_buffers≈ 25% of memory (PostgreSQL relies on the OS cache too); InnoDB ≈ 70–80% (it bypasses the OS cache). The advice is opposite; copying one to the other is expensive.- An
UPDATEwrites a new row version. Fill factor reserves page space so it can stay local as a HOT update with no index writes; otherwise every index is rewritten. Dead versions need vacuum or the table bloats.
Self-test: Why does an index point at a slot number rather than a byte offset? · What is the working set, and what happens when it exceeds the buffer pool? · Why is a durable commit cheap? · Name two consequences of InnoDB's clustered index · What is a HOT update and what does it save? · Why is plain LRU the wrong eviction policy for a database?
Next: 7.3.2 builds the structure that turns "find page 517" from a scan into three reads — indexes, what a composite index's column order really means, and why adding one is never free.