Compute on compressed.
Compression usually means storing less. In l it also means computing differently: running primitives on the encoding itself.
Compression usually means storing less. In l, it also means computing differently.
l keeps vectors compressed in memory to move fewer bytes. This post is about running primitives on the encoding itself, so the dense vector never exists. We call it computation on compressed layouts, or CoC.
The runtime sees physical representation, not just logical type, and decides if the primitive can run on it directly. The programmer writes standard k/q; the runtime selects the physical algebra.
The old model
Historically, compression lived at the edges:
disk -> compressed
memory -> decompressed
execution -> denseThis made sense when disk was the bottleneck. It is not enough now. If data is in memory, full decompression is waste: cache pollution and bandwidth are wasted before execution begins.
CoC asks: can the primitive be evaluated on the encoding itself? If so, the dense vector never exists.
The physical algebra
A dense runtime has one rule:
value -> dense vector -> primitiveA CoC runtime has a richer one:
logical value + physical layout + primitive -> physical planThe plan can be metadata answers, single-lane lookups, compressed predicates, or histograms. CoC is a family of choices based on layout.
Metadata is computation
The simplest CoC operations use metadata. If the header knows count, count x is O(1). If it knows min/max, scans are skipped. Bounds can stamp predicate results without unpacking lanes.
l’s compression model is designed to emit useful metadata.
Predicates inside the vector
Consider x<100 on a Frame of Reference vector, base plus delta. The runtime translates the comparison into the encoded domain, scans compact lanes, and emits the mask directly. A predicate only needs truth values, computed at the cheapest representation. Packed values can use the optimal SIMD width, for example sorting 64-bit integers using 32-bit registers.
Histograms instead of hashes
Dense distinct/group/in/bin require hashing or sorting. But a compressed column with a small value domain can replace hash tables with a compact histogram or bitmap over the encoded domain.
This algorithm is selected because of layout. A shared histogram over small-range FoR columns powers compressed operations:
| primitive | speedup (x86) |
|---|---|
| bin | 37x |
| group | 9.1x |
| in | 3.25x, up to 70x |
| distinct | 3.0x |
No magic. A hash table is not always the right abstraction. Sometimes the encoding is already the index.
Arithmetic in the encoded domain
Some operations are closed over an encoding. A Frame of Reference vector absorbs x+5 by shifting its base. A constant column multiplies into its metadata. A float layout with integer payloads can sum/avg in the integer domain and scale once.
Against an ALP float layout, the measured audit:
| primitive | speedup |
|---|---|
| sum price | 7.7x |
| avg price | 33x |
| min / max | metadata |
| sum x*y (dot) | 6.1x |
Composability is key: if x*y remains compressed and sum consumes it, expressions benefit without new verbs. The 6.1x dot product fell out of composing compressed multiply and sum.
The embarrassing case
For x[i], inflating a compressed vector to read one value is wasteful. The runtime decodes only the target lane. For x[ids], the runtime gates: it reads encoded lanes at low selectivity, and materializes at high selectivity.
CoC must be asymmetric
Some operations do not benefit from compression: random probes spend time in hashes, math libraries dominate transcendentals, and random writes are expensive. CoC is asymmetric on purpose: it detects and hides these choices. Reductions win, while distinct falls back to dense. Dispatch handles the bottleneck.
The result can stay compressed
The highest form of CoC is compressed input to compressed output, preserving structure across operations. This is where CoC compounds: if layouts survive across a chain of operations, isolated wins become expression-wide advantages.
CoC preserves facts: count, bounds, range, scale, sortedness. A dense runtime discards these facts and rescans; l keeps them alive.
k: vectors are the unit of expression. l: compressed layouts are the unit of execution. CoC: primitives become encoding-aware plans. The runtime decides how, in what representation, and at what cost.
References
- Abadi et al., Integrating Compression and Execution in Databases
- Boncz et al., MonetDB/X100: Hyper-Pipelining Query Execution
- Zukowski et al., Super-Scalar Cache Compression
- Li et al., BitWeaving: Fast Scans for Main Memory
- Elgohary et al., Compressed Linear Algebra for ML
- Afroozeh et al., The FastLanes Layout
- Kuschewski et al., BtrBlocks: Columnar Compression