Disk Serialization: The SQLite Record Format

Everything so far lived in memory as lists and objects. A database file is only bytes, so a row has to be turned into bytes, written into a page cell, and turned back into a row after a restart. This lesson implements the encoding SQLite really uses for table rows, byte for byte. The test fixtures were checked against rows written by a real SQLite database.

Varints: small numbers, few bytes

Lengths and types are mostly small, so SQLite stores them as varints: 7 bits of the number per byte, most significant group first, with the high bit of every byte except the last set to 1 ("more bytes follow").

127   = 0b1111111              -> 7f
128   = 0b0000001 0000000      -> 81 00      (groups 1 and 0; the first byte gets the 0x80 flag)
300   = 0b0000010 0101100      -> 82 2c
16384 = 0b0000001 0000000 0000000 -> 81 80 00

To decode, take 7 bits from each byte, shifting the running value left by 7 each time, and stop after the first byte with a clear high bit. (The real format has a 9th byte holding a full 8 bits for numbers of 2^56 and above; this lesson stops at 8 bytes.) A varint that runs off the end of the data is truncated.

A record: header, then body

A row (NULL, 300, 'Alice', 0, 1) becomes:

06 00 02 17 08 09   |  01 2c  41 6c 69 63 65
header               |  body: 300, then 'Alice'

The header starts with its own length as a varint (6: the length byte plus five type bytes). Then comes one varint per column, the serial type, which says both the type and the size of that column's bytes in the body. The body is the values back to back, with no padding or separators.

Types 7 (a float), 10 and 11 exist or are reserved; this lesson reports 7, 10 and 11 as ERR bad serial type. In the example: 300 does not fit one signed byte (range -128 to 127) but fits two, so type 2 and bytes 01 2c; 'Alice' is 5 bytes, so type 13 + 10 = 23 = 0x17; 0 and 1 are types 8 and 9 and take no body bytes at all.

Integers use the smallest size whose signed range holds them. 127 is type 1 but 128 needs type 2 (00 80); -129 needs two bytes (ff 7f); 32768 needs three (00 80 00); 2147483648 needs six. Text counts bytes, not characters: 'héllo' is 6 bytes (the é takes two), type 25.

If a header grows past 127 bytes, the length varint itself needs two bytes, and the length counts those two. Records with very many columns hit this.

A cell on a table page

A table leaf stores each row as a cell: the record length as a varint, the rowid as a varint, then the record. CELL 1 NULL 300 'Alice' 0 1 is 0d 01 followed by the 13 record bytes above.

Commands

Errors: ERR bad hex, ERR truncated record, ERR trailing bytes (bytes left after the last column), ERR bad serial type <n>, ERR bad number, ERR bad rowid, ERR integer out of range (beyond 2^53-1), ERR bad value: <text>, usage and unknown-command errors.

Common mistakes

• Little-endian integers. Everything in a record is big-endian.
• Not shrinking integers. A 4-byte int for the value 5 is a different record.
• Counting characters in text. The serial type uses the UTF-8 byte length.
• Forgetting to count the header's own length byte(s).
• Not sign-extending when decoding a negative integer from fewer than 8 bytes.

Your exercise

The starter parses values, prints, and handles hex. You write encode_varint, decode_varint, serial_type, encode_record, read_header and decode_record. The mistake to avoid: choosing the integer size from the number of digits instead of its signed range.