Skip to content
The Data EngineeringThe Data EngineeringBeta
About
Main content

Varints and order-preserving encoding

What do variable-length integers and order-preserving byte encodings cost that size tables never show?

Varint and zigzag: adaptivity bought with a serial dependency

A stores an integer in as few bytes as it needs. Each byte carries 7 payload bits; the top bit says "more bytes follow" (the continuation bit).

  • Values below 2^7 (128) cost 1 byte, below 2^14 cost 2 bytes, below 2^21 cost 3 bytes.
  • Compared with a fixed 32-bit integer (4 bytes), varint wins below 2^21 (about two million) and loses above 2^28.
  • Compared with a fixed 64-bit integer (8 bytes), the longest varint is , a 25% penalty (10 vs 8).

So varint is a bet that magnitudes are small. It loses the bet completely on hashes, UUIDs, random identifiers and nanosecond timestamps.

It also fails on negative numbers, badly. −1 in is sixty-four 1-bits, which needs the full 10 varint bytes. fixes this. It interleaves the signed range onto the unsigned range:

zigzag(n) = (n << 1) XOR (n >> 63)     // >> is an arithmetic shift (copies the sign bit)
 0 -> 0,  -1 -> 1,  1 -> 2,  -2 -> 3,  2 -> 4, ...

One shift and one XOR turn sign into magnitude as the thing that decides the size. Where do small signed numbers come from? From subtraction. So zigzag exists because encoding exists (storing differences between neighbouring values). You will meet it again in Lightweight compression.

The cost nobody quotes

The real cost of varint is not space. It is the dependency structure.

  • A varint stream has no computable offsets. To find element N, you must decode elements 0 to N − 1.
  • Decoding is a data-dependent branch per byte ("is the continuation bit set?"). Branch mispredictions at about 15–20 cycles dominate.
  • Scalar varint decoding runs at a few hundred MB/s, against about 10 GB/s for a plain memory copy.

You saved about 2× space and paid 10–20× decode cycles on those fields. You also lost random access.

This explains a design convergence: column formats abandoned varint for . Bit-packing uses a fixed number of bits per value within a block (for example 11 bits for every value of this block). Offsets stay computable, SIMD (one instruction on many values) applies, and most of the adaptivity to small magnitudes is kept. Per-block adaptivity keeps random access and gives up a little ratio.

So row formats and column formats resolve "simple versus adaptive" differently, for a structural reason and not a stylistic one. It is also a question: the unit of adaptation and the unit of access are the same decision.

Order-preserving byte encoding

Some storage engines keep keys in sorted order: LSM-trees (write-optimized stores that keep sorted files), B-trees (the classic sorted index), Bigtable-style stores, FoundationDB. They compare keys with memcmp: byte by byte, lexicographic (dictionary order), unsigned. They do this because the comparison code lives inside an engine that has no access to your types. The engine is late-bound to your schema and cannot interpret anything.

Therefore the ordering must be carried inside the encoding. Your job is to build an injective map (no two different values give the same bytes) from typed tuples to byte strings, so that memcmp order equals logical order. Let us see what breaks, one case at a time.

Unsigned integers need with fixed width. Little-endian puts the least significant byte first and breaks the order completely. For example, 256 = 01 00 (big-endian) and 1 = 00 01; compared byte by byte, 1 < 256 is correct. In little-endian, 256 = 00 01 and 1 = 01 00, so 256 would sort before 1. Network byte order is not old-fashioned here. It is load-bearing.

Signed integers. Two's complement big-endian puts negatives after positives, because the sign bit is 1. Fix: XOR the first byte with 0x80. Now −1 becomes 0x7FFF… and 0 becomes 0x8000…, and the order is correct again. (This is the same problem as the nanosecond-negative-timestamp ordering in Nikhil's key store.)

Floats are better designed than they look. puts the sign, then the biased exponent, then the , so positive floats already compare correctly as big-endian unsigned integers. This is deliberate. Negative floats compare backwards. The rule: if the sign bit is set, invert all the bits; otherwise invert only the sign bit. What is left is NaN (not a number) and negative zero. They have no correct position, so you choose a convention and document it, and every system chooses a different one.

Variable-length parts inside a composite key cannot simply be joined. The pairs ("ab","c") and ("a","bc") would both produce abc. A length prefix would remove the ambiguity but break the order, because length would be compared before content. So you need a terminator. But the terminator byte can appear in the data, so it must be escaped. The standard construction escapes 0x00 as 0x00 0xFF, and ends the component with 0x00 0x01. You pay extra space in proportion to the number of zero bytes in the data, and you give up decoding in place.

Descending order for a component is the bitwise complement of its encoding. Nulls get a reserved leading byte, which also serves as a type tag.

Strings hold the real trap. byte order equals Unicode order. This is a designed property. It is also the reason UTF-16 cannot be used for keys: in UTF-16, surrogate pairs (the two-unit codes for characters above U+FFFF) sort below U+E000, though they stand for codepoints far above it. But codepoint order is not human sorting order in any language, including English. If you need locale-correct sorting, you must encode an sort key (a byte string produced by a collation library). A sort key is larger than the string and cannot be turned back into the original. So you store the sort key for ordering and the original string for retrieval.