Row Serialization

Encode a users row (id, name, email) as exactly 60 bytes in a fixed layout, decode those bytes back to the same row, and refuse any value the layout cannot hold.

Not run yet · 23 tests

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:

idbytes 0–3 (4 bytes) · the number 1, least significant byte first
namebytes 4–31 (28 bytes) · 'dan' is 64 61 6e, then 25 zero bytes
emailbytes 32–59 (28 bytes) · '[email protected]' is 12 bytes, then 16 zero bytes

Each field starts at a fixed byte: id at 0, name at 4, email at 32. Zero bytes are shown dimmed. The name ends long before its field does, and email still starts at byte 32.

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:

idbytes 0–3 (4 bytes) · 0x12345678 written from its low byte (78) to its high byte (12)

The number 305419896 as the first four bytes of a row.

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.

The algorithm in words

Encode a row

The INSERT has already been parsed. Encoding turns its three values into the 60 bytes of the layout.

1.Match each value to its column by name, not by position: the INSERT may list the columns in any order.
2.Check every value before writing a byte. id must be a number between 0 and 4294967295; name and email must be strings of at most 27 bytes, counted in bytes, not characters. The first value that fails decides the error.
3.Start from 60 zero bytes.
4.Write id into bytes 0 to 3, least significant byte first: the lowest 8 bits of the number go in byte 0, the highest 8 bits in byte 3.
5.Copy the bytes of name from byte 4 on, and the bytes of email from byte 32 on. Everything you did not write stays zero.
6.Invariants: the result is always 60 bytes; email always begins at byte 32 however long name is; bytes 31 and 59 are always zero.

Decode a row

The reverse: read each field at its fixed position.

1.Read the four bytes 0 to 3 as an unsigned number, byte 0 being the least significant.
2.Read name from byte 4, stopping at the first zero byte or at the end of its 28 bytes. Read email the same way from byte 32.
3.Invariant: decoding the encoding of a row gives back the same id, name and email.

Read the hex that `deserialize` is given

The debug command takes bytes as text. Turning that text into bytes is its own small job, and its own error.

1.Split the input on spaces. Each piece must be exactly two hex digits, in either case; anything else is error 00502.
2.More than 60 pieces is error 00502. Fewer than 60 is allowed: the missing bytes at the end are zeros.
3.Decode the resulting 60 bytes as above.

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.

Input	Output
`serialize <insert>`	`[SERIALIZE]` then the 60 bytes, each two lowercase hex digits, separated by single spaces, on one line
`deserialize <hex bytes>`	`[DESERIALIZE] Field id = <id>`, `[DESERIALIZE] Field name = <name>`, `[DESERIALIZE] Field email = <email>`, in that order
a string longer than 27 bytes	`[ERROR:00405] <message>`
an `id` outside 0..4294967295	`[ERROR:00404] <message>`
a string for `id`, or a number for `name` or `email`	`[ERROR:00403] <message>`
`serialize` with nothing, or with a statement that is not an INSERT	`[ERROR:00501] <message>`
a syntax error after `serialize`	the parser's code and column, counted from the start of the line, `serialize` included
a `deserialize` token that is not two hex digits, or more than 60 bytes	`[ERROR:00502] <message>`

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

droid session

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.

Loading starter code…

No run yet

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