Variable-Length Row Format

Why this stage exists

The row format of the Core Engine gives every row 60 bytes. That made everything after it easy: a field is always at the same byte, and a cell is always 64 bytes, so a leaf finds its tenth cell by multiplication. It also has two costs, and they grow together.

The first is waste. The row (1, 'dan', 'd@e') uses 10 bytes of real data and takes 60: the rest is zero padding, written to the page, then to the file, then read back on every scan. The second is the limit. A name can never be longer than 27 bytes, because the field is 28 bytes wide. Raising the limit to 1000 bytes would make every row more than 2000 bytes long, including the ones whose name is dan.

A variable-length row stops paying for room it does not use: each string is stored as its length and then its bytes, and nothing else. Short rows get short, and a long limit stops costing short rows anything. That is what lets the next stages raise the limit.

This stage builds the new format on its own, with the debug commands serialize and deserialize, the way row-serialization built the first one. The B+Tree still stores the 60-byte rows of the Core Engine until varlen-btree-leaf, so the limit on name and email stays at 27 bytes for now, and every SQL statement behaves exactly as before.

What changes: the row describes itself

Here is (1, 'dan', 'd@e') in the Core Engine's format:

And here it is in the new one:

What the new format says:

• A string is its length, then its bytes. Two bytes of length, so a string could in principle be up to 65535 bytes long. There is no zero byte at the end: the length already says where the string stops, so a zero is just another byte a string may hold.
• The row starts with its own size. A reader that is handed a row can check it has all of it before reading a single field, and a page that stores rows back to back can find where one ends and the next begins.
• The row says how many columns it has. A table that later gains a column can still read its old rows: they say they have one column fewer.
• The null bitmap holds one bit per column, rounded up to whole bytes, so one byte for users. Nothing in this part sets a bit. It is there now because a NULL needs it, and adding it later would mean changing the format a second time.

What you give up

In the fixed format email was always at byte 32. Now it is wherever name ends: at byte 18 after dan, at byte 22 after danimar. To reach a field you walk the fields before it. That is the price of the space saved, and it is why serialize now prints the layout: the offsets are no longer something you can know in advance.

A row is not always smaller, either. With both strings at their 27-byte limit the row is 15 + 27 + 27 = 69 bytes, 9 more than the fixed format: the header and the length prefixes cost 11 bytes that padding never did. Rows are rarely full, and the saving on every other row pays for it many times over.

Distrust what you read

A fixed row cannot lie: any 60 bytes are a row, perhaps a strange one. A variable row can. Its header can claim 21 bytes when 18 were given, a length can claim 48 bytes where 3 are left, a column count can name a table that does not exist. A decoder that believes those claims reads past the end of its buffer, which is at best a crash and at worst someone else's data printed as a name. So deserialize checks each claim against the bytes it actually has, and refuses the row with 00503 when one does not hold.

The Core Engine's 60-byte rows are refused too. They start 01 00 00 00, which the new format reads as a row of 1 byte. A format change means old bytes are no longer readable as new ones. So this stage retires the Core Engine's row-serialization cases that check the 60-byte bytes, by name, and they stop being run; that stage's error cases (00403, 00404, 00405, 00501, the parser's codes and 00502 for bad hex) still hold and still run.

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 15.

In the layout a string column c is two fields, c_len:2@<o> and c:<length>@<o + 2>, and an empty string is still listed, as c:0@<o>. The bytes that are not a row, each 00503: no bytes at all; fewer than the header and the fields need; a row_size that is not the number of bytes given; a column_count that is not 3; a string whose length runs past the end of the row or is longer than 27; bytes left after the last field. Every error is one line and prints no [SERIALIZE] or [DESERIALIZE] line.

What you should see when done

Welcome to droid!
>serialize insert into users (id, name, email) values (1, 'dan', 'd@e');
[SERIALIZE] Row size: 21 bytes
[SERIALIZE] Layout: row_size:4@0 column_count:2@4 null_bitmap:1@6 id:4@7 name_len:2@11 name:3@13 email_len:2@16 email:3@18
[SERIALIZE] Bytes: 15 00 00 00 03 00 00 01 00 00 00 03 00 64 61 6e 03 00 64 40 65
>serialize insert into users (id, name, email) values (2, 'danimar', '[email protected]');
[SERIALIZE] Row size: 39 bytes
[SERIALIZE] Layout: row_size:4@0 column_count:2@4 null_bitmap:1@6 id:4@7 name_len:2@11 name:7@13 email_len:2@20 email:17@22
[SERIALIZE] Bytes: 27 00 00 00 03 00 00 02 00 00 00 07 00 64 61 6e 69 6d 61 72 11 00 64 61 6e 69 6d 61 72 40 65 6d 61 69 6c 2e 63 6f 6d
>serialize insert into users (id, name, email) values (3, '', '');
[SERIALIZE] Row size: 15 bytes
[SERIALIZE] Layout: row_size:4@0 column_count:2@4 null_bitmap:1@6 id:4@7 name_len:2@11 name:0@13 email_len:2@13 email:0@15
[SERIALIZE] Bytes: 0f 00 00 00 03 00 00 03 00 00 00 00 00 00 00
>deserialize 15 00 00 00 03 00 00 01 00 00 00 03 00 64 61 6e 03 00 64 40 65
[DESERIALIZE] Field id = 1
[DESERIALIZE] Field name = dan
[DESERIALIZE] Field email = d@e
>deserialize 15 00 00 00 03 00 00 01 00 00 00 30 00 64 61 6e 03 00 64 40 65
[ERROR:00503] name claims 48 bytes and only 8 are left
>deserialize 01 00 00 00 64 61 6e
[ERROR:00503] row_size is 1 but 7 bytes were given
>.exit
exiting.. good bye!

Things to notice. email_len is at byte 16 after dan and at byte 20 after danimar. The empty row is 15 bytes, and its two empty strings are still in the layout, name:0@13 and email:0@15. In the fifth command one byte changed, 03 to 30 in name_len, and the row stopped being a row. The last one is the start of an old 60-byte row, which is no longer one. The error messages are yours to word; the tests check only the codes.

Common bugs in this stage

• A zero byte after each string. Habit from the fixed format. The length says where a string ends; an extra zero makes the row one byte longer per string and shifts every offset after it.
• row_size without its own 4 bytes. 17 instead of 21. The size is the size of the whole row.
• The length in characters. São is 3 characters and 4 bytes, and the length prefix is 4.
• Big-endian lengths. 00 03 instead of 03 00. Every integer in the row is little-endian, the 2-byte ones too.
• Forgetting the bitmap. The header is 7 bytes, not 6, so id starts at byte 7. A missing bitmap moves every field one byte to the left.
• Fields in the INSERT's order. (email, id, name) is still stored id, name, email.
• Trusting row_size or a length. Reading name_len bytes without checking they are there reads past the input. Check each claim against the bytes you have, and refuse with 00503.
• Stopping early and calling it a row. Bytes left after email mean the row is not what its header says. That is 00503, not a success.
• Padding short input with zeros. The Core Engine did that; this format does not. Seven bytes are seven bytes.
• Raising the 27-byte limit now. The B+Tree still stores 60-byte rows until varlen-btree-leaf, so a longer string could not be stored. The limit moves in that stage.

Language notes

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

• C and C++: a variable-length row cannot be a struct you memcpy. Build it in a byte buffer with a write position that moves forward, and read it with a read position you compare against the buffer's length before every read.
• Rust: a Vec<u8> with extend_from_slice builds the row; slicing with get(start..end) returns None instead of panicking when a length runs past the end, which is exactly the check 00503 needs.
• Zig: std.ArrayList(u8) and its writer() build the row, and std.mem.readInt over a slice you have already checked the length of reads it back.