Keys

Dialog keeps its facts in a sorted tree, and a sorted tree can only find things by the order of their keys. A fact gets looked up in three different ways, though. An app shows one grocery item, and needs every fact about item:1. It shows the whole list, and needs every demo.grocery/name. It asks which items are tagged "breakfast", and needs to start from a value.

No single sort order serves all three. So Dialog writes every fact three times, each time with its parts in a different order:

Each copy is called an index. The first byte of the key, the tag, says which index it belongs to. All the indexes live side by side in one tree, and the tag keeps them apart:

The first three hold the facts themselves. The last three are Dialog’s own bookkeeping, and later chapters come back to them. Nothing is added under tag 04 any more. A stored asset is recorded by an ordinary fact instead (see Blocks and Storage), and the entries older trees hold there are still read.

A key, byte by byte

Here is the EAV key for the grocery name of item 1 is “Oat milk”:

The key starts with the tag, 00. Then each part follows, written so that comparing the raw bytes gives the same answer as comparing the parts themselves:

• Strings (the entity URI, the attribute, and text values) are written as their UTF-8 bytes followed by a 00 terminator. Any 00 inside the string is written as 00 FF, so the terminator is never ambiguous.
• The type byte of the value comes right before the value. It is the value’s type number from the Facts chapter; 03 is text.
• Numbers all carry the type byte 09, and are written as decimals, in the key encoding SQLite4 designed. The first byte says the number’s sign and how big it is. The digits follow, two decimal digits to a byte, and the last byte is marked, so a number ends itself and needs no terminator. A negative number has every byte after the first inverted. Bigger numbers sort later, whether they are whole or not, and a number has exactly one encoding: the quantity 2 is the two bytes 18 04, and so are 2.0 and +2.
• Booleans are one byte, 00 for false and 01 for true.

The terminator is what makes prefixes sort first. item:1 ends with 00, and item:10 continues with 30 (the character 0) at the same position. Since 00 is smaller, every key for item:1 comes before every key for item:10, just as the strings would. Nothing about item 1 ever lands in the middle of item 10.

The VAE key holds the same bytes in a different order. The tag is 02, and the value comes first, led by its type:

Sorted, the list tells its own story

Put Alice’s keys in byte order and each index turns into a set of neat runs. Part of the AEV index is elided:

Every fact about item:2 is one contiguous run in EAV. Every demo.grocery/done is one run in AEV. In VAE the type byte comes right after the tag, so every Boolean sorts before every string: Boolean is type 02 and text is type 03. Among the strings, "Eggs" and "Oat milk" come before "breakfast", because uppercase letters have smaller byte values than lowercase ones.

A query is mostly a matter of picking the index whose runs match the question, then reading one run.

The value lives in the key

The value is part of every key, not stored beside it. That means a lookup by value in VAE finds the entity without reading anything else.

It also means a fact has exactly one place in each index. If Alice and Bob both assert that the eggs are done, both assertions build the same key, so each index holds one entry for that fact, not two.

That entry has a small payload next to its key. The payload holds no part of the fact, only its temporal information: the versions that asserted it, here both Alice’s and Bob’s, and the fact’s optional cause (see Commits and History).

Big values spill

A key holding a whole photo would make a terrible key. So every tree sets a limit on how long a value in a key may be, and a value whose encoded form is longer than that limit spills. The value’s place in the key keeps only the encoding of a short prefix of it, and the key ends with a 01 byte and the 32-byte BLAKE3 hash of the whole value. In EAV and AEV that tail comes right after the value; in VAE it comes after the entity, the key’s last part. The value itself is stored on its own, in the asset store, named by that hash:

The prefix keeps a spilled value sorting by how it starts, so a range scan over strings still finds it in about the right neighborhood. The hash keeps two different long values from sharing a key. A reader tells the two shapes apart by what is left after the key’s last part: nothing for an inline value, exactly 33 bytes for a spilled one.

The limit and the length of the prefix are not constants of Dialog. They are settings of the tree, and every node carries them in its header, as the Nodes chapter shows. Unless a tree says otherwise, the limit is 4,096 bytes and the prefix is the value’s first 64 bytes. A reader that guessed them wrong would build different keys and miss facts, so they are among the few settings a reader must understand.