Handling Large Values Across Pages

The problem: values bigger than a page

A slotted page is a fixed 4096-byte box. Most rows fit comfortably — an integer, a short string. But what about a value that's 50KB? SQLite calls this a "TOOAST" problem informally (Postgres literally calls its mechanism TOAST — The Oversized-Attribute Storage Technique); every disk-backed engine needs an answer for values that simply don't fit in one page. The answer is overflow pages: when a cell doesn't fit, store as much as fits in the original page, and chain the rest across additional pages reserved just for that value.

The overflow chain

Think of it like a linked list of pages instead of a linked list of nodes:

[main page]                [overflow page 1]        [overflow page 2]
 key | local_bytes | next -> raw_bytes | next   ->    raw_bytes | next=NULL

• The main page's cell stores the key, some prefix of the value (however much fits alongside the header/pointer overhead), and a pointer (page ID) to the first overflow page.
• Each overflow page is almost entirely payload — a big flat byte array — plus a small header holding a pointer to the next overflow page (or a sentinel/NULL if it's the last one).
• Reading the value means following the chain: read the local bytes from the main page, then keep appending each overflow page's bytes until you hit the end of the chain, then concatenate everything back into the original value.

function get_large_value(page, key):
    cell = find_cell(page, key)
    result = cell.local_bytes
    next = cell.overflow_pointer
    while next != NULL:
        ovf = load_page(next)
        result += ovf.payload
        next = ovf.next_pointer
    return result

Building INSERT_LARGE

1. Compute how many bytes of the value can live in the main page's cell alongside its key and required metadata (this is local_bytes, and can be zero — some designs store no value bytes in the main page, only key + first overflow pointer, to keep every case uniform).
2. Slice the remainder into chunks, one per overflow page, each chunk sized to fit that page's payload capacity.
3. Allocate an overflow page per chunk, write the chunk, and link each one to the next via its next-pointer.
4. Store the main page's cell with the key, local bytes, and a pointer to the first overflow page.
5. Track how many overflow pages exist so PAGE OVERFLOW_COUNT can report it — either a running counter you increment on allocation and decrement on delete/reclaim, or a live count derived by walking every chain (simpler to reason about correctness-wise, but slower — either is fine for this exercise as long as it stays accurate after inserts and any deletes you support).

Edge cases

• Value exactly at the boundary — one byte smaller than the overflow threshold should stay entirely in the main page (no overflow pages allocated); one byte larger should trigger exactly the minimum number of overflow pages needed, not one more.
• Value spanning many pages — make sure your chain-following loop terminates correctly and reassembles bytes in the right order (this is where off-by-one slicing bugs show up: a chunk boundary computed wrong either drops bytes or duplicates them).
• Multiple large values in the same page — each cell's chain is independent; don't let one value's overflow pointer get confused with another's.
• PAGE OVERFLOW_COUNT after inserting several large values — should be the sum across all chains, not just the most recent one.

Why this matters beyond "big blobs"

Overflow pages are the mechanism that lets a database advertise "no practical limit on row size" while every individual page on disk stays a fixed, predictable size — which is exactly what makes the page cache (previous lesson) and the B-tree (earlier chapter) tractable: every page-level operation can assume a fixed page size, and overflow chains are the escape hatch for the rare oversized value, invisible to everything above the storage layer.