Overflow Pages — Large Value Handling

What happens when a single row's data is larger than a page? You can't just store it — a 4096-byte page with headers leaves roughly 4000 bytes for data. A TEXT column containing a 10KB document won't fit.

The Overflow Problem

Consider a table with a large text column:

CREATE TABLE docs (id INTEGER, content TEXT)
INSERT INTO docs VALUES (1, '<10KB of text...>')

The content is 10KB but a page is 4KB. The row must span multiple pages.

Overflow Page Chains

The solution is overflow pages — a linked list of pages for data that won't fit:

Primary Page (4096 bytes)
+---------------------------+
| Header                    |
| Cell: id=1, content=      |
|   [first 3800 bytes...]   |
|   overflow_page → Page 42 |
+---------------------------+

Overflow Page 42 (4096 bytes)
+---------------------------+
| Next overflow → Page 43   |
| [next 4080 bytes...]      |
+---------------------------+

Overflow Page 43 (4096 bytes)
+---------------------------+
| Next overflow → 0 (end)   |
| [remaining 2120 bytes...] |
+---------------------------+

Threshold Decision

Not every large value needs overflow pages. Databases use a threshold:

If cell_size <= (page_size - header_overhead) / 4:
    Store inline (on the primary page)
Else:
    Store first portion inline, rest in overflow pages

SQLite uses a complex formula: if the payload exceeds (page_size - 35) * 64/255 - 23 bytes, it overflows. The goal is to fit at least 4 cells per page.

Reading Overflow Data

To read a value that spans overflow pages:

1. Read the inline portion from the primary page
2. Follow the overflow pointer to the first overflow page
3. Read data, follow the next pointer
4. Continue until next pointer is null (0)
5. Concatenate all pieces

This is a linked list traversal, and each step is a page read. Large values require multiple I/O operations.

Trade-offs

How PostgreSQL Handles Large Values (TOAST)

PostgreSQL uses TOAST (The Oversized-Attribute Storage Technique). Large values are:

1. Compressed with LZ compression
2. Sliced into 2KB chunks
3. Stored in a separate TOAST table

TOAST is automatic and transparent. It also enables deferred loading — large columns are only fetched when actually accessed.

Your Task

Implement overflow page handling for values that exceed the page size, with commands to insert large values and verify they can be read back correctly.