Variable-Length Row Format

Encode a users row as a small header followed by its fields, each string with its length in front of it, decode those bytes back to the same row, and refuse bytes that do not add up to a row.

Not run yet · 21 tests

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:

idbytes 0–3 (4 bytes) · the number 1
namebytes 4–31 (28 bytes) · 'dan', then 25 zero bytes
emailbytes 32–59 (28 bytes) · 'd@e', then 25 zero bytes

The fixed format: 60 bytes, 50 of them padding.

And here it is in the new one:

row_sizebytes 0–3 (4 bytes) · 21: the whole row, these 4 bytes included
column_countbytes 4–5 (2 bytes) · 3: users has three columns
null_bitmapbytes 6–6 (1 bytes) · one bit per column, all zero in this part
idbytes 7–10 (4 bytes) · the number 1, little-endian as before
name_lenbytes 11–12 (2 bytes) · 3
namebytes 13–15 (3 bytes) · 'dan'
email_lenbytes 16–17 (2 bytes) · 3
emailbytes 18–20 (3 bytes) · 'd@e'

The variable format: 21 bytes, none of them padding. Every integer is little-endian, as in the Core Engine.

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.

The algorithm in words

Encode a row

The INSERT has been parsed and its values checked, exactly as before: the limits of the Core Engine still hold in this stage, so a string is still at most 27 bytes.

1.Work out the size first: 4 bytes for row_size, 2 for column_count, one byte of null bitmap for up to 8 columns, 4 for id, and for each string 2 bytes of length plus its bytes.
2.Write row_size, the whole size, these 4 bytes included, little-endian.
3.Write column_count, 3 for users, as 2 little-endian bytes, then the bitmap: one zero byte.
4.Write the columns in table order, whatever order the INSERT listed them in: id as 4 little-endian bytes; then for name and for email, the length in bytes as 2 little-endian bytes, then the bytes themselves. No zero byte ends a string.
5.Invariants: the row is 15 + len(name) + len(email) bytes; the first 4 bytes say that number; every byte of the row is written, none is padding.

Describe the layout

serialize also prints where each field landed, which is the part that has stopped being constant.

1.Keep a running offset from 0. For each field, in the order it is stored, note its name, its size and the current offset, then move the offset past it.
2.A string is two fields: <column>_len, 2 bytes, then <column>, as many bytes as the string has, possibly 0.
3.Invariant: the last field ends exactly at row_size.

Decode a row, trusting nothing

The bytes come from outside. Every length in them is a claim, and each claim is checked before it is followed.

1.There must be at least the header and the id: 11 bytes for users. Fewer is error 00503.
2.row_size must equal the number of bytes given, and column_count must be the table's 3. Either one wrong is 00503.
3.Read id from byte 7. Then, for each string: its 2 length bytes must be there, the length must be within the column's limit, and that many bytes must be left in the row. If not, 00503.
4.After the last string there must be no bytes left over. If there are, 00503.
5.Invariant: decoding the encoding of a row gives back the same values, and decoding never reads a byte past the end of what it was given.

Read the hex that `deserialize` is given

Unchanged from the Core Engine except for the limit and the padding.

1.Split on spaces; each piece is exactly two hex digits, in either case, or error 00502.
2.More than 1000 bytes is 00502: no row is ever longer. Fewer bytes are no longer padded with zeros; they are the row, and the decoder decides whether they are one.

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.

Input	Output
`serialize <insert>`	three lines: `[SERIALIZE] Row size: <n> bytes`, then `[SERIALIZE] Layout:` and every field as `<field>:<size>@<offset>` separated by single spaces, then `[SERIALIZE] Bytes:` and the row as two lowercase hex digits per byte, separated by single spaces
`deserialize <hex bytes>`	`[DESERIALIZE] Field id = <id>`, `[DESERIALIZE] Field name = <name>`, `[DESERIALIZE] Field email = <email>`, in that order
`deserialize` bytes that are not a row of `users`	`[ERROR:00503] <message>`
a `deserialize` token that is not two hex digits, or more than 1000 bytes	`[ERROR:00502] <message>`
a string longer than 27 bytes, an `id` out of range, a value of the wrong type, no INSERT, a syntax error	`00405`, `00404`, `00403`, `00501`, the parser's code: unchanged from `row-serialization`

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

droid session

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.

Loading starter code…

No run yet

21 tests wait for your first run

Run tests builds your code, drives the binary through every case for this stage, and shows expected and received output side by side here. Failing cases come first.