Storage engine: disk layout, pages, and slotted records

Where this sits in the engine

Hold the course's running query in your head:

SELECT name FROM emp WHERE salary > 75000 ORDER BY name;

In week 1 we watched that string fall through five components to the bottom of the stack. This week is the bottom. When the executor's scan asks the buffer pool for a page, and the buffer pool reads that page off disk, this layer is what those bytes mean. The storage manager hands the layer above a fixed-size page; inside that page, the layout we build here lets it find each emp row, pull out the name and salary columns, and decide whether salary > 75000.

What gets handed in, and what gets handed down:

• From above (the buffer pool, week 4): a request for a page by id, and later a frame of memory holding that page's exact bytes.
• Down to the device: a read or write of one fixed-size block. The disk knows nothing about rows. It moves blocks.

So the storage engine's whole job is to be the translator between "rows and columns" up top and "fixed blocks of bytes" down below. Next week (heap files and free space) zooms out from one page to the file of many pages: where a new row goes, and what a delete leaves behind. This week we stay inside a single page.

The problem, stated honestly

Three facts about persistent storage force everything below.

First, the device is block-addressable, not byte-addressable. To read one salary you cannot pull one number; the hardware drags in a whole block. The CMU storage notes put it bluntly: to read a value at some offset "the program first has to load the 4 KB page into memory" [CMU 15-445 L03]. So the unit of work is the page, never the byte.

Second, disk is slow on a scale that is hard to feel. If an L1 cache reference took one second, the same notes say, an SSD read would take about 4.4 hours and a spinning disk about 3.3 weeks. Every design choice below is about cutting the number of block transfers a query needs.

Third, rows have variable length and you will delete them. That last fact is what kills the obvious design.

Three things called "page"

The word page is overloaded across three layers, and the gap between them is where a real bug lives.

• Hardware page, usually 4 KB. The device guarantees that a write of this size is all-or-nothing.
• OS page, typically 4 KB, the unit of virtual memory.
• Database page, commonly 1 to 16 KB; PostgreSQL fixes 8 KB at compile time, SQLite defaults to 4 KB.

When the database page (8 KB) is bigger than the hardware page (4 KB), one logical write is two atomic writes. A crash in between leaves a torn page: half the new version, half the old. PostgreSQL defends against this by writing the full page image to the write-ahead log the first time it is touched after a checkpoint, which is also why every page header carries pd_lsn, the log position of its last change. We meet that machinery properly in week 14; for now, just notice the header field is there for crash safety, not for finding rows.

The slotted page

The slotted page is the layout almost every disk database uses inside a page. The shape is simple and the reason for the shape is the whole lesson.

Read the structure top to bottom:

1. A header at the top with bookkeeping: where free space starts, where it ends, the crash-recovery LSN.
2. A slot array just below it, one small fixed-size entry per row, growing downward as you insert.
3. Free space in the middle, shrinking from both ends.
4. Tuple data at the bottom, growing upward, with the newest tuple nearest the free gap.

The two halves close toward each other. In PostgreSQL the header field pd_lower marks the end of the slot array and pd_upper marks the start of tuple data; free bytes are pd_upper - pd_lower [PG page layout].

Try it: a slotted page you can edit

This is one page. Insert rows of a chosen length, delete by slot, and watch the slot array and tuple data close toward each other. Delete a middle row and you get a hole; press compact and the tuples slide together while the record ids in the slot column stay put. Toggle MAXALIGN to see padding inflate every row, and reorder the demo columns to watch a badly ordered row waste pad bytes that a good order avoids.

Slotted page byte editor insert, delete, compact; watch ids stay stable while bytes move

What a record id actually is

When the index in week 6 returns a match for salary > 75000, it does not return a row. It returns a record id, called a TID (tuple id) in PostgreSQL: the pair (page id, slot number). To fetch the row the access method reads that page, indexes into the slot array at that slot number, follows the stored offset, and decodes the bytes. One page read, then constant-time arithmetic.

PostgreSQL's line pointer, exactly

PostgreSQL's slot is a 4-byte line pointer (ItemIdData) packed as bitfields [itemid.h]:

typedef struct ItemIdData {
    unsigned lp_off:15,   /* byte offset of the tuple within the page */
             lp_flags:2,  /* state: UNUSED, NORMAL, REDIRECT, DEAD */
             lp_len:15;   /* length of the tuple in bytes */
} ItemIdData;

Two details matter for the exam. The four lp_flags states are LP_UNUSED (free for reuse), LP_NORMAL (points at a live tuple), LP_REDIRECT (forwards to a newer version on the same page, used by HOT update chains, which you meet in week 13), and LP_DEAD (the tuple is gone, the slot awaits reclamation by VACUUM, week 3). And lp_off is 15 bits, so it can address offsets up to 2¹⁵ = 32768. That is why a PostgreSQL heap page cannot exceed 32 KB: the line pointer simply cannot name a byte past that.

Inside one tuple

A tuple is "essentially a sequence of bytes" that only the DBMS knows how to decode. The schema lives in the catalog, not in the row. A heap tuple in PostgreSQL carries, in order: a fixed header, an optional NULL bitmap, then the column data.

NULLs are a bitmap, not a value

How do you store NULL? Not as zero, and not as a sentinel, because any sentinel you pick could be a legal value someone actually stored. PostgreSQL keeps one bit per column in the header (present only when the HEAP_HASNULL flag is set): the bit says present or null, and a null column then occupies no bytes at all in the data area [PG page layout].

Alignment makes column order matter

CPUs read aligned words faster, and some architectures require it, so the DBMS pads fields to natural boundaries. In PostgreSQL the rule is MAXALIGN, typically 8 bytes. The consequence is concrete and testable: the same columns in a different order can take a different number of bytes on disk.

Same three columns, two orders. The pad bytes are the whole difference.

Order	Layout	Pad	Row bytes (data area)
bad	bool (1) , bigint (8) , name	7 after the bool	larger
good	bigint (8) , bool (1) , name	0 interior	smaller

Put the 1-byte bool first and the 8-byte bigint must start on an 8-byte boundary, so 7 pad bytes are wasted between them. Put the bigint first and the gap vanishes. Multiply by millions of rows and it is real disk. The simulator's "Swap column order" button shows exactly this.

Deeper: the 24-byte page header and the 23-byte tuple header

PostgreSQL's PageHeaderData is 24 bytes. The fields that matter here: pd_lsn (8 bytes, last WAL change, gates flushing), pd_lower (2 bytes, end of the line pointer array), pd_upper (2 bytes, start of tuple data), plus checksum, flags, special-space offset, and version. Free space is exactly pd_upper - pd_lower, which is the slotted invariant written as two header fields [PG docs].

The heap tuple header (HeapTupleHeaderData) has a documented minimum of 23 bytes: t_xmin and t_xmax (4 each, the inserting and deleting transaction ids, where t_xmax is the tombstone you will study next week), t_ctid (6 bytes, pointer to this or a newer version), t_infomask2 and t_infomask (2 each, flags including HEAP_HASNULL), and t_hoff (1 byte, the offset to user data, itself a multiple of MAXALIGN). The NULL bitmap, when present, sits right after this fixed header and before user data.

Costs of the slotted operations

Why this layout is fast where it needs to be.

Operation	Cost	Why
Fetch by record id	1 page read + O(1)	index the slot array, follow the offset
Insert (room exists)	O(1)	append data at pd_upper, append a slot at pd_lower
Delete	O(1)	mark the slot dead, leave the bytes for later
Compact	O(tuples on page)	slide live tuples, rewrite their slot offsets

Check yourself

Active recall