Slotted Pages

Why this stage exists

A Core Engine leaf finds cell i by multiplication: every cell is 64 bytes, so cell i starts at 14 + 64 × i. The previous stage made rows variable, and that multiplication stops working. Rows of 21, 39 and 15 bytes cannot be found by position, and a row that grows cannot stay where it was.

The answer every real database gives is the slotted page. The page keeps a small directory of fixed-size slots at its front. Each slot says where one record is and how long it is. The records themselves live at the other end of the page, packed wherever there was room. To find record 2, read slot 2: it is always at the same place, because slots all have the same size, and it tells you where the record is.

That one level of indirection buys a lot. A record can move, to close a hole or to make room, and nobody who knows it as "slot 2" needs to hear about it. Records of any length share a page with no padding. And the page knows exactly how much room is left.

This stage builds the slotted page on its own, with page commands on pages you allocate yourself, before any B+Tree uses it. The B+Tree still stores the Core Engine's leaves until varlen-btree-leaf, where each leaf becomes a slotted page, and every SQL statement behaves as before.

What changes: two ends and a gap

Here is page 1 after page init 1 and three inserts: alpha, bravo charlie and delta.

The header is 16 bytes. Its first 14 are the Core Engine's node header, the same fields in the same places, and the last 2 are new: the record start, the offset of the lowest record. Slot i is the 4 bytes at 16 + 4 × i: the record's offset, then its length, 2 bytes each, little-endian like everything else in the file.

The fields a slotted page made by page init does not use yet are zero. They are where they are so that a B+Tree leaf can be a slotted page without a second layout: in varlen-btree-leaf the type becomes 1, is_root, parent and link get their Core Engine meanings, and the slot count is the number of cells.

Free space is every byte no header, slot or live record uses: 4096 − 16 − 4 × slot_count − the lengths of the live records. Here that is 4096 − 16 − 12 − 23 = 4045.

Deleting leaves a hole

Delete slot 1 and the page looks like this:

Nothing moved. That matters: anything that remembered "page 1, slot 2" can still find delta. Free space grew by 13 at once, to 4058, because free space counts holes. But the gap, the contiguous room between the directory and the record start, did not grow: a new 13-byte record would still go below delta, not into the hole.

A deleted slot is not wasted. The next record takes the lowest deleted slot before the directory grows, so a page that sees many deletes and inserts does not grow a directory of dead slots.

Compaction closes the holes

Compaction moves every live record to the end of the page, in slot order, and rewrites their offsets:

Slot numbers are what compaction protects. The record moved, the slot that names it did not.

An insert does not always wait for you to compact. When a record fits in the free space but not in the gap, because the room it needs is in holes, the page compacts itself first and then places the record. Only a record that does not fit in the free space at all is refused, with 00605.

Real engines do this too. PostgreSQL calls a slot a line pointer and names a row by its page and line pointer, which is why its rows can move within a page without their indexes changing. SQLite's pages have the same two ends, and defragment themselves when an insert needs the room.

Output contract for this stage

These are the exact lines the tests check. The full definition is on the output contract page, sections 3 and 16.

The record of page insert is the rest of the line after the page number and one space, spaces inside included, stored with no zero byte after it. page read prints it between single quotes. Slotted pages are pages of the pager, so they are saved when the session ends and read back from the file, as in the Core Engine.

What you should see when done

Welcome to droid!
>pager alloc
[PAGER] Alloc: page 0 (4096 bytes, zeroed)
>pager alloc
[PAGER] Alloc: page 1 (4096 bytes, zeroed)
>page init 1
[PAGE] Init page 1: free_space=4080
>page insert 1 alpha
[PAGE] Insert page 1: slot=0 offset=4091 length=5
>page insert 1 bravo charlie
[PAGE] Insert page 1: slot=1 offset=4078 length=13
>page insert 1 delta
[PAGE] Insert page 1: slot=2 offset=4073 length=5
>page delete 1 1
[PAGE] Delete page 1: slot=1
>page dump 1
[PAGE] Page 1: type=SLOTTED slots=3 free_space=4058
[PAGE]   Slot 0: offset=4091 length=5
[PAGE]   Slot 1: deleted
[PAGE]   Slot 2: offset=4073 length=5
>page compact 1
[PAGE] Compact page 1: free_space=4058
>page insert 1 echo
[PAGE] Insert page 1: slot=1 offset=4082 length=4
>page dump 1
[PAGE] Page 1: type=SLOTTED slots=3 free_space=4054
[PAGE]   Slot 0: offset=4091 length=5
[PAGE]   Slot 1: offset=4082 length=4
[PAGE]   Slot 2: offset=4086 length=5
>page read 1 1
[PAGE] Read page 1 slot 1: 'echo'
>page dump 0
[ERROR:00606] page 0 is not a slotted page
>.exit
exiting.. good bye!

Things to notice. The delete changed no offset. After compaction slot 2 is at 4086, and echo took the deleted slot 1 rather than a new slot 3. The last dump lists the slots in slot order, not in the order of their offsets: slot 1's record is now the lowest on the page. Page 0 was allocated but never initialised, so it is not a slotted page.

Common bugs in this stage

• Free space that forgets the slot. A new slot costs 4 bytes. A record of exactly free_space bytes that needs a new slot does not fit.
• Free space that ignores holes, or counts only holes. Free space is every unused byte: the gap and the holes together. The gap alone decides where a record goes, not whether it fits.
• Moving records on delete. A delete that compacts at once still keeps every slot's number, but it moves records the contract says stay put, and the file's bytes differ from what the tests expect.
• Shifting the directory on delete. Removing the slot and moving the later ones down renumbers every record after it. A deleted slot stays, as offset 0 and length 0.
• Taking a new slot while a deleted one is free. The lowest deleted slot comes first.
• Compacting in offset order. Compaction packs the records in slot order, lowest slot at the end of the page. In offset order, a record that was taken again into a low slot ends up somewhere else.
• An overlapping copy during compaction. Records move towards the end of the page and may overlap their old place. Copy each record out before writing it, or use a move that handles overlap.
• Forgetting the record start. After compaction it is the lowest record's offset. A stale record start puts the next record in the wrong place, or on top of another one.
• Trimming the record. page insert 1 bravo charlie stores 13 bytes, the space included.
• Storing 4096 in 2 bytes. The record start of an empty page is 4096, 00 10 little-endian. It fits, but only because 2 bytes go up to 65535; don't store it as an offset from somewhere else.

Language notes

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

• C and C++: the page is a uint8_t[4096]; read and write the 2-byte and 4-byte fields byte by byte, little-endian, as with the row. memmove, not memcpy, for compaction.
• Rust: u16::from_le_bytes(page[o..o + 2].try_into().unwrap()) reads a slot field; copy_within moves a record inside the page and handles overlap.
• Zig: std.mem.readInt(u16, page[o..][0..2], .little) reads a slot field, and std.mem.copyBackwards or std.mem.copyForwards moves a record depending on the direction.