Row Serialization

Why this stage exists

So far a row has only existed as the values of a parsed INSERT, held however your language likes to hold things. The btree-leaf stage stores rows in pages, and pages are just bytes: 4096 of them, written to a file and read back, maybe by a later run of the program. A page cannot hold "a struct" or "an object"; it can only hold bytes. Something has to decide which bytes a row becomes, and that decision has to be the same every time, on every machine, in every run.

That decision is the row format, and this stage builds it on its own, before any page exists, so that it can be checked byte by byte. The debug command serialize shows the bytes of a row; deserialize reads bytes and shows the row. Nothing is stored yet.

The format is deliberately simple: every row is exactly 60 bytes. Because the size never varies, finding a field never requires reading the fields before it, and later stages can find the tenth row of a page by multiplication instead of by walking.

What changes: the 60 bytes

This is insert into users (id, name, email) values (1, 'dan', '[email protected]'); as a row:

Three rules make these bytes the only right answer:

• Every field has a fixed place. id is bytes 0–3, name bytes 4–31, email bytes 32–59. A field never moves because another one is short.
• Strings are padded with zeros, and their last byte is always zero. A field is 28 bytes, so a string may use at most 27 of them. The zero after the string tells a reader where it ends.
• id is written least significant byte first. This is called little-endian. The number 1 is 01 00 00 00, not 00 00 00 01.

Byte order is a rule, not an accident

A 4-byte number has a most significant byte and a least significant one, and a format has to say which comes first. Ours says: the least significant. 305419896 is 0x12345678 in hex, four different bytes, so its encoding shows the order plainly:

Many computers happen to keep numbers in memory in this order, so copying an integer's memory straight into the buffer produces the right bytes on them. That is a property of the machine, not of the format, and the file you write in the next stages must read back the same on a machine that orders bytes the other way. Write the bytes on purpose: the lowest 8 bits into byte 0, the next 8 into byte 1, and so on.

id is unsigned: it goes from 0 to 4294967295, and 4294967295 is ff ff ff ff. A signed 32-bit integer stops at 2147483647, so it cannot hold every valid id.

Refuse what does not fit

A name of 40 bytes cannot be stored in 27. Keeping only the first 27 would make the row look fine and silently lose data, which is the one thing a database must never do. So a value the layout cannot hold is an error, and nothing is encoded. The limit is in bytes: a character outside ASCII takes two to four bytes in UTF-8, so a 27-character name can be too long.

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

The columns of the INSERT may come in any order; the bytes are the same. deserialize accepts hex digits in either case and pads fewer than 60 bytes with zeros. An empty string prints nothing after = . 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', '[email protected]');
[SERIALIZE] 01 00 00 00 64 61 6e 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 64 61 6e 40 74 65 73 74 2e 63 6f 6d 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00
>serialize insert into users (email, name, id) values ('[email protected]', 'dan', 1);
[SERIALIZE] 01 00 00 00 64 61 6e 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 64 61 6e 40 74 65 73 74 2e 63 6f 6d 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00
>deserialize 01 00 00 00 64 61 6e
[DESERIALIZE] Field id = 1
[DESERIALIZE] Field name = dan
[DESERIALIZE] Field email = 
>serialize insert into users (id, name, email) values (1, 'a name that is much too long', 'x');
[ERROR:00405] name is longer than 27 bytes
>serialize insert into users (id, name, email) values (4294967296, 'a', 'b');
[ERROR:00404] id 4294967296 is out of range
>deserialize 01 00 0g
[ERROR:00502] not a hex byte: 0g
>.exit
exiting.. good bye!

Three things to notice. The two INSERTs list their columns in different orders and give identical bytes. deserialize was given seven bytes and still printed a whole row, with an empty email. And the 28-byte name was refused, not cut to 27. The error messages are yours to word; the tests check only the codes.

Common bugs in this stage

• Big-endian id. 01 00 00 00 for 1 but 00 00 30 39 for 12345: the bytes are in the wrong order. id 1 and id 0 cannot catch this, because they read the same both ways; 305419896 can.
• A signed id. 4294967295 comes out as an error, or 2147483648 as a negative number when decoded. The id is unsigned.
• Truncating long strings. A 40-byte name printed as 27 bytes and no error. Check the length first and refuse.
• Counting characters instead of bytes. A name of 27 characters with an accent in it is more than 27 bytes and must be refused.
• A 28-byte string accepted. It fills the field completely and leaves no zero at the end, so the next reader runs straight into email. The limit is 27, not 28.
• Garbage in the padding. Bytes after the string that are not zero, left over from an earlier row or from uninitialised memory. Start every row from 60 zero bytes.
• Fields written in the order the INSERT lists them. (email, id, name) must not put the email at byte 0. Place each value by its column name.
• Uppercase hex, or a 61st byte. 5A instead of 5a, a trailing space, or a stray byte at the end of the line all fail the format check.
• deserialize reading past a short input. With fewer than 60 bytes given, the rest must be zeros, not whatever was in the buffer before.
• Decoding a string without stopping at the zero. The name comes back as dan followed by invisible characters. Stop at the first zero byte.

Language notes

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

• C and C++: memcpy of a uint32_t gives little-endian bytes only on a little-endian machine; shifting and masking gives them everywhere. char name[28] with strlen works because the last byte is always zero, and snprintf or strncpy will happily truncate, which is exactly what this stage forbids: check the length first.
• Rust: u32::to_le_bytes and u32::from_le_bytes say the byte order in their names. str::len counts bytes, which is the length the limit is about.
• Zig: std.mem.writeInt(u32, buf, value, .little) and std.mem.readInt take the byte order as an argument, so the format is visible in the code.