Twelve columns: turning a JSON tree into a bitstream
A bit-level columnar encoding scans a document once, gives every container and key a slot, and splits the result into twelve column streams. Earlier columns tell the decoder how to read later ones.
Related: Trees as columns
Columnar storage compresses well for a simple reason: putting values of the same kind together creates runs of similar data, and similar data is cheap to encode. The same idea can be applied to a single JSON document. Everything below describes a bit-level columnar encoding and was checked against the output of its reference implementation. Trees as columns gives the formal treatment.
One scan, slots and links
The encoder walks the document depth first. Every container and every object key gets a slot, and slot 0 is the root. Each later slot records its parent as a key link (parent slot + 1). Each leaf (a primitive, or the marker of an empty container) records its owner, either a key slot or an array slot, as a value link (owner slot + 1). An empty container nested in the document gets a slot and one marker leaf owned by that slot. Arrays need no indices, because element order is simply the order of the value links.
{ "a": 1, "b": 2, "c": [3, 4] }
One depth-first scan:{} → a → 1 → b → 2 → c → [] → 3 → 4
| slot | node | klink | ktype |
|---|---|---|---|
| 0 | {} | — | object · 01 |
| 1 | "a" | 1 | b64 key · 10 |
| 2 | "b" | 1 | b64 key · 10 |
| 3 | "c" | 1 | b64 key · 10 |
| 4 | [] | 4 | array · 00 |
| value | vlink | Δ code |
|---|---|---|
| 1 | 2 | 2 |
| 2 | 3 | 1 |
| 3 | 5 | 2 |
| 4 | 5 | 0 |
Links [2,3,5,5] become delta codes [2,1,2,0], 3 bits each.
- 1dc · mode + count
- 2vflags
- 4kflags
- 7kvals
- 9bools
- 10nums
- 11vals
- 12strdiffs
- ·pad
The only count written explicitly is the number of leaves. The decoder infers the number of slots from the largest value link, and it infers how many booleans, numbers and strings to read from the type column.
Delta codes
Links are delta-coded against the previous link. A difference of 0 to 3 is stored as itself. A difference of −1 to −3 is stored as |d| + 3, so codes 4 to 6. Anything else becomes a literal. One flag bit per link says which form was used, and a delta link written on its own always costs exactly 3 bits.
| value links | as codes | flag column |
|---|---|---|
[2, 3, 5, 5] | [2, 1, 2, 0] | 01 (all delta, no body) |
[2, 3, 5, 3] | [2, 1, 2, 5] | 01 (−2 is code 5) |
[2, 3, 5, 11] | [2, 1, 2, 11] | 10 1110 (mixed, then raw bits) |
Flag columns start with a 2-bit mode: 00 means all zeros and 01 means all ones, both with no body, while 10 means mixed and is followed by the raw bits. When every link is a delta, as in the example above, the whole flag column costs 2 bits however large the document is.
Width grows inline
Literal links use a running width that starts at 1 bit. When a literal needs more bits, the encoder first writes a 0 at the current width for every extra bit. The decoder widens each time it reads a zero, so the width itself is never transmitted.
- widen (+1 bit)
- literal
- delta
Keys: base64url and a shared dictionary
Each slot has a 2-bit kind: 00 array, 01 object, 10 base64url key, 11 other string. String keys add their length + 1. Keys made only of [A-Za-z0-9-_] take 6 bits per character, and other keys take LEB128 per UTF-16 unit.
Keys and string values share one dictionary in first-seen order. In [{"name":"Bob"},{"name":"Alice"}] the second name is written as length 0 plus a short index, about 10 bits instead of about 30. A string that has appeared as a key can come back as a value reference, and the reverse also works.
The column order
- 1Header
Mode bit and leaf count.
- 9–12Payload
Bools, numbers, strings and string diffs.
- ·Pad
Zero-fill to the next byte.
For the document above, the result is 100 bits, which pads to 13 bytes: 3169951318a28869b70321d810. The four numbers 1, 2, 3, 4 collapse into one run of “delta +1” in the number column.
Primitive top-level values skip all of this. When the first bit is 1, the next seven bits form a compact code. null, true, false, "", [], {}, integers from 0 to 62 and single letters each fit in one byte.
Next: delta packing, or how runs of values collapse to almost nothing.