Exact, compact and still queryable

Why do space and speed move together at the bit level, and how do encodings differ from compression?

CaseConstructed case · Arjun at Parcelo

A 1.25 TB bitmap, and zone maps that skip nothing

Parcelo wants fast filters like WHERE status = 'delayed' AND depot = 'PNQ-3' over 5 billion events. Arjun's first design is one bitmap (a string of bits, one per row) for each distinct value. Status has 6 values, so that is 6 × 5 × 10⁹ bits = 3.75 GB: fine. But depot has 2,000 values, and 2,000 × 5 × 10⁹ bits = 10¹³ bits = 1.25 TB. A textbook says: "bitmap indexes are only for low-cardinality columns" (few distinct values). So he drops the idea, and the indexes he builds instead do not fit in RAM either.

Meanwhile, the nightly report "events for tracking IDs starting with 7F" opens every one of 40,000 files, although each file has a min/max statistic for tracking_id. The statistics were built, stored and checked, and they never skip anything. Both problems have clear causes.

How it ends →

Exact, compact, and still queryable

Probabilistic structures bought space by giving up correctness. This article buys space and gives up nothing. It pushes the representation toward the information-theoretic floor and stays exact. That is possible because of a fact the previous articles never used: real data is not random. Its entropy (the true amount of information in it) is far below the maximum its naive layout allows, and the gap between actual entropy and naive layout is free space that no other article can reach.

But compactness alone is not the discovery. Gzip has been compact since 1992, and no query engine queries gzip. The discovery is queryability in the compressed domain: structures that reach near-optimal space while keeping random access and boolean operations, so you never decompress. The formal ladder tells you how much overhead you accept (Z is the information-theoretic minimum, the least number of bits that can represent the data):

Class	Space
Implicit	Z + O(1)
Succinct	Z + o(Z)
Compact	O(Z)
Entropy-compressed	H_k(data) + o(Z), still queryable
Classically compressed	often below Z + o(Z) in practice, but not queryable

(o(Z) means "an amount that becomes negligible compared to Z as the data grows".) The last row is the one the industry escaped, and escaping it is what this article is about.

Here the usual trade-off inverts. In every other article, space and time are opposites: you spend one to buy the other. Here they move together, for two compounding reasons. First, analytics is bandwidth-bound (limited by bytes moved, not by arithmetic), so bytes not stored are bytes not moved. That alone makes smaller faster. Second, once data is packed into bits, a 64-bit word operation processes 64 elements at once and a 512-bit AVX register processes 512. Compactness converts directly into parallelism. A bitmap AND does 512 row-level predicate tests in one instruction, not because it is clever, but because the representation happens to fit the arithmetic unit.

Everywhere else space buys speed. Here space is speed, because the machine is starved for bandwidth, and every byte you do not store is a byte you do not move or decode.

One more thing this article settles. Lookup structures, Ordering structures and Probabilistic structures each had a mutation story: in-place update, merge later, or rebuild. This article has essentially one: nothing here updates. Bit-packed, rank-indexed, entropy-coded structures are built once and read many times. So they are, for the fourth time, in the "free-rider" position: they are deployable exactly where a system already rebuilds. This is the strongest recurring structural fact here.

Encoding versus compression: the split that organizes this article

Encodings (dictionary, run-length, bit-packing, delta, frame-of-reference) are structure-aware and queryable: you can evaluate a predicate on dictionary codes, skip a run without expanding it, compare bit-packed integers directly. Compression codecs (LZ4, Zstd, Snappy) are byte-oriented and opaque: you must decompress a block before you can do anything with it, and whether one pays depends on the bandwidth of the tier the bytes come from. The structures below consume the encodings: dictionary encoding is what makes a bitmap index practical on a string column, bit-packing is what rank/select addresses into, and a run-length run is one of Roaring's container types.