MQDB Storage Format

Overview

mq-db persists documents in a fixed-size page file. Every file is split into 8192-byte pages. Page 0 is the file header, page 1 is the catalog root, and all remaining pages hold document blocks, secondary indexes, custom-table rows, or overflow chunks.

+-----------+-----------+-----------+-----------+-----------+
| Page 0    | Page 1    | Page N    | Page N+1  | Page ...  |
| FileHeader| Catalog   | BlockData | Overflow  | Free/Future|
+-----------+-----------+-----------+-----------+-----------+

Multi-page values are stored as singly linked page chains using the next_page field in the page header.

Page Layout

Each page is exactly 8192 bytes.

Page header (16 bytes)

Page body (8176 bytes)

File Header Page (page 0)

Page 0 always has page_type = 1 and page_id = 0.

File header body

Catalog Pages

The catalog always starts at page 1. If the serialized catalog exceeds one page body, additional catalog pages are linked by next_page.

Page 1 (Catalog) --> Page 12 (Catalog) --> Page 18 (Catalog) --> 0

Catalog body format

The catalog holds document entries, custom tables, content hashes, view definitions, and the store’s tokenizer, in this order:

index_start_page is 0 when no secondary index is persisted for that document. Every trailing section (custom tables onward) is optional: a catalog blob written by an older mq-db version simply ends early, and readers default the missing sections to empty (tokenizer defaults to Word).

Block Data Pages

A document is serialized as concatenated encoded blocks. The byte stream is cut into 8176-byte chunks.

• The first chunk is stored in a page with page_type = 3 (BlockData).
• Continuation chunks are stored in pages with page_type = 4 (Overflow).
• The last page in the chain has next_page = 0.

first_block_page
      |
      v
+-------------------+    +-------------------+    +-------------------+
| type=BlockData    | -> | type=Overflow     | -> | type=Overflow     |
| body bytes 0..8175|    | next chunk        |    | final chunk       |
+-------------------+    +-------------------+    +-------------------+

Unused bytes at the end of the final page body are zero-filled.

Block Wire Format

Each block is encoded independently and concatenated without separators.

Block type mapping

PropertyValue Encoding

Each property value starts with a one-byte type tag.

Arrays are recursive: each element is another complete PropertyValue.

Index Pages

A document’s secondary index (zone maps aside) is serialized separately from its blocks and stored in its own page chain, pointed to by the catalog entry’s index_start_page.

• The first chunk is stored in a page with page_type = 5 (Index).
• Continuation chunks use page_type = 4 (Overflow), same as block chains.
• The encoded bytes are opaque to the page layer; only DocumentIndex interprets them.

Table Data Pages

Custom-table rows (from CREATE TABLE / INSERT INTO) live in their own page chain, referenced by the catalog’s first_row_page and last_row_page.

• The first page is page_type = 6 (TableData); continuation pages are page_type = 4 (Overflow).
• Unlike block and index chains, table chains grow incrementally, one INSERT at a time, so a chunk does not always fill a full page body. Each table-data/overflow page therefore reserves its first 2 bytes for a u16 LE chunk length, followed by that many bytes of row data.
• Row data is a flat stream of u32 LE-length-prefixed UTF-8 cells. Decoding needs the table’s row and column counts (from the catalog) since rows are not self-delimiting.

ZoneMap Encoding

Zone maps are encoded independently and embedded as opaque bytes inside catalog entries.

Sets are serialized as sorted UTF-8 strings for deterministic output.

Checksum Algorithm

The checksum is a wrapping sum over every byte in the 8192-byte page, except the checksum field itself (page[4..8]).

Pseudo-code:

checksum = 0u32
for i in 0..8192:
    if i in [4, 5, 6, 7]:
        continue
    checksum = checksum.wrapping_add(page[i] as u32)

Verification recomputes the checksum and compares it to the stored checksum field.

Multi-Page Chains

Large catalog payloads, document block streams, index blobs, and table-row batches are all stored as chains.

+---------+      +---------+      +---------+
| page_id |----->| page_id |----->| page_id |
| next=42 |      | next=77 |      | next=0  |
+---------+      +---------+      +---------+

The body bytes of each page are concatenated in chain order to reconstruct the original serialized byte stream.

Atomic Write Procedure

DocumentStore::save() writes atomically using a sibling temporary file:

1. Create path.tmp (a fresh page file with only the file header and an empty catalog page).
2. Write every document’s blocks as a block-data chain.
3. Write every document’s secondary index as an index chain.
4. Write every custom table’s rows as a table-data chain.
5. Serialize and write the final catalog chain, referencing all pages written above.
6. Rename path.tmp to path.

Because the final rename is atomic on the same filesystem, readers either observe the old file or the new complete file, never a partially written database image.