Research··3 min read

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

#encoding#columnar#databases

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.

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.

Input
{ "a": 1, "b": 2,
  "c": [3, 4] }

One depth-first scan:
{} → a → 1 → b → 2 → c → [] → 3 → 4

Slots klink = parent + 1
slotnodeklinkktype
0{}—object · 01
1"a"1b64 key · 10
2"b"1b64 key · 10
3"c"1b64 key · 10
4[]4array · 00
Leaves vlink = owner + 1
valuevlinkΔ code
122
231
352
450

Links [2,3,5,5] become delta codes [2,1,2,0], 3 bits each.

Emitted bitstream: 12 columns in fixed order, then zero padding
  1. 1dc · mode + count
  2. 2vflags
  3. 3vlinks
  4. 4kflags
  5. 5klinks
  6. 6keys
  7. 7kvals
  8. 8types
  9. 9bools
  10. 10nums
  11. 11vals
  12. 12strdiffs
  13. ·pad
Fig. 1Scanning {a:1, b:2, c:[3,4]}. Slots hold the tree's shape, and leaves point at their owners. Both become lists of small, slowly changing integers.

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 linksas codesflag 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
Fig. 2Value links of {x:{y:{z:1}}, w:2}. The literal 7 (link 6 + 1) needs 3 bits, so it is preceded by two widen markers. The next link is a 3-bit delta. Total: 9 bits.

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

  1. 1
    Header

    Mode bit and leaf count.

  2. 2–5
    Links

    Value and key flags and links.

  3. 6–8
    Keys and types

    Kinds, key characters and 3-bit value types.

  4. 9–12
    Payload

    Bools, numbers, strings and string diffs.

  5. ·
    Pad

    Zero-fill to the next byte.

Fig. 3The twelve columns are always emitted in the same order. Each one tells the decoder how to read what follows.

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.