Overflow Pages for Large Values

Why this stage exists

Since the slotted leaf, a row has been limited to 1000 bytes. The limit was never about the data: it was about splitting. A leaf split must divide a full leaf plus one new cell into two halves that each fit in a page, and that is only always possible when no cell is too large. With cells of at most 1004 bytes, any four fit in an empty leaf, so every split works.

But a note, a description or a JSON document is easily longer than 1000 bytes, and refusing it is not an answer a database can give. The way out keeps the split's guarantee and drops the limit: a large row keeps a fixed-size piece of itself in its cell, and puts the rest somewhere the tree never has to divide, a chain of pages of its own. Real databases call these overflow pages. They need the free list from earlier in this part, because chains come and go with their rows.

What changes: a cell that points onward

A row of at most 1000 bytes is stored exactly as before. A larger row has a cell of 1004 bytes: the key, the row's first 996 bytes, then the number of its first overflow page. The row's own row_size, which is in those first bytes, says how long the row really is. That is how a reader knows a chain follows: a row_size over 1000 cannot fit in the cell, so the last four bytes must be a page number. No flag is needed.

An overflow page is page type 5. It says how many of the row's bytes it holds, and which page comes next, and holds those bytes from byte 16, at most 4000:

A row of s bytes has a chain of ceil((s − 996) / 4000) pages, all full but the last. The 10,013-byte row above has 9,017 bytes after its first 996, so three pages: 4000, 4000 and 1017. Follow it from the leaf:

What changes: writing, reading and freeing chains

INSERT allocates the whole chain first, first page first, and writes it, before the cell goes into its leaf and before any split. If the pages cannot all be allocated, the statement is 00602 and changes nothing: not a page of the chain, not the leaf. Reading a row puts it back together: the 996 bytes from the cell, then each page's bytes in chain order. Everything that reads rows, SELECT, WHERE, btree find, sees the whole row, as if it were in the cell.

Freeing goes through the free list. A chain is freed from its last page to its first, so its first page ends up at the head of the list, and a new chain of the same length takes the same pages back in the same order. DELETE frees a row's chain before the cell leaves its leaf. UPDATE frees the old chain and then stores the new row as INSERT would: a row that keeps its size reuses its pages, one that shrinks under 1001 bytes gives them all back, one that grows gets a chain. DROP TABLE and TRUNCATE free each leaf's chains, its rows in key order, just before the leaf itself.

The tree never sees a chain. A cell is still at most 1004 bytes, so leaves split, borrow and merge exactly as before, and a merge that moves a cell moves its page number with it.

The trade-off: how much to keep inline

996 bytes is a choice. Keep more in the cell, and fewer reads need the chain, but fewer cells fit in a leaf, the tree gets taller, and every search pays for it. Keep less, and leaves stay dense, but more rows need an extra page read to be returned. A row that needs a chain costs one more read per 4000 bytes, so a scan of a table full of large rows reads mostly overflow pages.

The prefix here is the most that keeps four cells in any leaf. Real engines make other choices for other reasons.

Real-world numbers. SQLite keeps a prefix in the cell and the rest in a chain of overflow pages, as here, with the prefix sized so at least four cells fit in a page. PostgreSQL moves large values out of the row entirely into a separate TOAST table, compressing them first, and keeps only a pointer in the row.

Output contract for this stage

The full definition is on the output contract page, section 29.

A line, and so a statement, may be up to 131072 bytes. Each VARCHAR(n) is still at most 65535 bytes. pager write still writes into one page, so text longer than 4091 bytes is 00104, and deserialize keeps its limit of 1000 bytes.

What you should see when done

With notes (id int, body varchar(65535)) on page 2, a 10,000-byte body and a short one (the long value is shortened here):

Welcome to droid!
>insert into notes (id, body) values (1, 'ahov…');
Insert statement executed successfully (1 rows)
>insert into notes (id, body) values (2, 'small');
Insert statement executed successfully (1 rows)
>btree dump 2
[BTREE] Page 2: type=LEAF num_cells=2 free_space=3042
[BTREE]   Cell 0: key=1 (10013 bytes) overflow=3 pages=3
[BTREE]   Cell 1: key=2 (18 bytes)
>delete from notes where id = 1;
Delete statement executed successfully (1 rows)
[EXEC] rows_examined=1
>db freelist
[DB] Free list: pages=3 chain=[3,4,5]
>.exit
exiting.. good bye!

Things to notice. The large cell takes 1004 bytes of the leaf, plus its slot, whatever the row's size: the leaf has 3042 bytes free. Its chain is pages 3, 4 and 5, allocated before the cell went in. Deleting the row put the chain on the free list with its first page at the head, ready for the next large row.

Common bugs in this stage

• Writing the cell before the chain. If the chain then fails to allocate, the leaf holds a cell pointing at nothing. Allocate and write the chain first, then the cell.
• Getting the chain length wrong at a boundary. A row of 1001 bytes needs one page with 5 bytes in it; one of 4996 needs exactly one full page, and 4997 needs two. Test both sides of each boundary.
• Deciding by the cell's length. A 1000-byte row and a row with a chain both have 1004-byte cells. Only row_size tells them apart.
• Leaking chains. DELETE, an UPDATE that shrinks a row, DROP TABLE and TRUNCATE must all free the chains of the rows they remove. A page lost this way is in no tree and on no list.
• Freeing the chain in the wrong order. The contract fixes it, last page first, and the free list shows it.
• Reading a chain into a fixed buffer. A row can be 65,548 bytes. Size the buffer from row_size, or grow it.

Language notes

The page above is the same for every language. These are the only language-specific hints.

• C: malloc the row from its row_size before following the chain, and remember a row is no longer guaranteed to fit on the stack.
• C++: a std::vector<uint8_t> reserved to row_size, filled with insert from each page, keeps the reassembly short.
• Rust: build the row in a Vec<u8> with with_capacity(row_size) and extend_from_slice each page's bytes.
• Zig: allocate the row with the allocator from row_size, and @memcpy each page's bytes into its place.