I've sat through more arguments about Parquet vs Avro, columnar vs row, nested vs flat, zstd level 3 vs 9, dictionary size tuning — than I care to remember. Most of them go in circles. People defend their tool, their format, their codec. Nobody steps back.

At some point I realised every single one of those arguments is downstream of one question nobody asks:

What are the natural folds of this data?

That question — or something close to it — was once famously asked by Kolmogorov, in a different form: "What is the shortest program that outputs these exact bytes?" He called the answer Kolmogorov complexity. And once you internalise it, most format/codec/layout wars dissolve into implementation details.

What Kolmogorov Complexity Actually Is

The Kolmogorov complexity \( K(s) \) of a string \( s \) is the length — in bits — of the shortest possible computer program that outputs exactly \( s \) and nothing else. It's a measure of the minimal descriptive complexity of \( s \). The algorithmic information content.

Two things follow immediately:

  • Low \( K(s) \) = the data has a lot of structure, regularity, patterns. A short loop plus some parameters can generate it. Repeating strings, arithmetic sequences, smooth time-series, structured JSON with repeating keys. Highly compressible.
  • High \( K(s) \) = the data looks random. No describable structure. The shortest program is basically "print this literal data." \( K(s) \approx |s| \). Incompressible.

Most strings are incompressible — for length \( n \), almost all binary strings have \( K(s) \geq n - c \) for some small constant \( c \). The ones with exploitable structure are the interesting ones. And as data engineers, those are exactly what we work with.

No compression scheme, no matter how clever, can ever compress a string \( s \) to significantly shorter than \( K(s) \) bits. Any compressor + decompressor pair is itself just a fixed program that turns a short encoded version back into \( s \). Kolmogorov complexity is the floor.

The One Sentence

Here's the first-principles statement I keep burned into my brain:

Minimise the Kolmogorov complexity of the representation you actually store and query — because that is the theoretical lower bound on how compact, how fast-to-decompress, and how cheaply processable the data can ever become.

Everything else follows from that sentence.

Choose and design representations that expose the maximum amount of describable regularity the data intrinsically contains. That's it. That's the job.

What Destroys Structure

Destroying regularity raises \( K \). You pay forever in worse compression ratios, slower scans, higher storage costs, more CPU to decode.

  • Flattening structured timestamped JSON into one undifferentiated blob
  • Stringifying nested structures without preserving hierarchy
  • Mixing types chaotically in the same byte stream

Every one of these erases patterns a short program could exploit. You've taken a \( K(s) \) that was low and shoved it toward \( |s| \).

What Preserves Structure

Preserving and amplifying regularity lowers \( K \). Real compressors — zstd, brotli, Parquet page encodings, ClickHouse lz4/zstd + specialised codecs — suddenly achieve dramatically better ratios.

  • Typed timestamp columns
  • Delta-of-deltas on monotonic times
  • Dictionary encoding on low-cardinality tags
  • Run-length encoding on constant stretches
  • Frame-of-reference / Gorilla-style encoding on values

Each of these makes the "shortest program" shorter. A tight loop over deltas beats a verbatim dump every time.

The Checklist

Run this on any data representation decision:

  1. Where are the natural creases? What dimensions of this data — time, cardinality, type, granularity — have their own distinct regularity that a fold could exploit?
  2. Am I folding or flattening? Does this layout separate surfaces so each can be compressed and queried independently, or does it mash them into a single stream?
  3. Does every fold shorten a path? Can a query touch only the surfaces it needs — skip timestamps, skip tags, skip values it doesn't care about — or does it have to scan the whole sheet?
  4. Am I fighting the geometry? Monotonic data should be delta-folded. Low-cardinality data should be dictionary-folded. If the encoding doesn't match the shape, I'm paying for friction that shouldn't exist.

If you can say "yes, each surface is folded along its natural axis and queries only touch what they need" — you're aligned with minimizing \( K \). You win on compression, scan speed, cost, future-proofing.

If you're doing the opposite — flattening the manifold into a single undifferentiated stream — you're deliberately making the data as expensive and slow as random noise. Only justifiable for adversarial settings: encryption, watermarking, anti-forensics. Not normal engineering.

Caveat: Kolmogorov complexity is uncomputable in the general case. You can't actually calculate \( K(s) \) for an arbitrary string. But you don't need to. The framework still works as a mental model — it tells you which direction to fold. Every real compressor is an approximation of the ideal, and the closer your layout gets to minimal \( K \), the better every compressor will perform.

The Folds Equation

Here's where it gets interesting. Sometimes the right move is to add more folds — exploding nested or aggregated data into more rows, more surfaces, more creases. The raw row count balloons. But each new surface is individually simpler, more regular, more compressible. You're not adding information. You're redistributing it into a shape with more exploitable geometry.

This is the folds equation: the number of folds you introduce must be paid for by the compression and query leverage those folds create. More folds means narrower columns with lower entropy, more opportunities for delta, RLE, and dictionary encoding. The question is whether the geometry pays for itself.

Let's formalize it:

  • \( f > 1 \) — the explosion factor (new row count = \( f \times \) original)
  • \( U \) — uncompressed size of the original dataset
  • \( r_o \) — original compression ratio (compressed size \( C_o = U / r_o \))
  • \( r_n \) — new compression ratio after explosion (ideally \( r_n > r_o \))
  • \( g = r_n / r_o \) — the compression improvement factor

Uncompressed new size is roughly \( U_n \approx f \times U \). New compressed size:

$$C_n = \frac{f \times U}{r_n}$$

For a net storage win (\( C_n < C_o \)):

$$\frac{f \times U}{r_n} < \frac{U}{r_o} \implies f < \frac{r_n}{r_o} \implies f < g$$

The balanced condition: \( g \geq f \). The compression improvement factor must at least match the explosion factor.

Queries Benefit Too

Lower \( K \)-density means more predictable data layout. Scans and aggregations exploit the same patterns — sorted timestamps allow skipping, uniform columns enable vectorized ops.

  • \( q_o \) — original query overhead
  • \( q_n \) — new query overhead (hopefully lower)
  • \( h = q_o / q_n \) — the query improvement factor

For the explosion not to slow things down: \( h \geq f \).

The Full Condition

Combining storage and query, the first-principles condition for a net win — smaller and faster — is:

$$g \geq f \quad \land \quad h \geq f$$

Where \( g \) and \( h \) emerge from how well the schema exposes structure for the compressor's "short program" and the query engine's optimisations.

This is why formats like Parquet shine on exploded time-series: \( f \) might be 2–10× from denesting, but \( g \) and \( h \) often hit 5–50× on real data with monotonic or smooth columns. If \( g < f \) or \( h < f \), you're imbalanced — revert to denser schemas.

The Point

Kolmogorov asked about the shortest program. That's the theorist's version. The data engineer's version is: what are the fewest folds that make every path through this data as short as possible?

Stop thinking about data in terms of rows. Rows are a flat projection — a lossy view of something that has shape. Data is geometric. It's a manifold. It has dimensions, surfaces, gradients. And like origami, your job is to fold it along its natural creases so that every path through it — every query, every scan, every compression pass — becomes as short as it can be.

Delta encoding is a fold along time. Dictionary encoding is a fold along cardinality. Columnar storage is a fold along dimension. Each fold collapses distance. Monotonic timestamps fold down to near-zero under delta-of-deltas. Low-cardinality tags fold into tiny dictionaries. Smooth values fold with Gorilla or frame-of-reference. The geometry was always there — you just need to fold along the creases instead of flattening the whole thing into a sheet.

When you flatten everything into a single stream, you're unfolding the manifold — and the compressor has to rediscover structure you already knew about. When you fold along the natural axes, each surface becomes individually exploitable. Each fold gives you cardinality leverage that compounds.

That's what Kolmogorov complexity actually means for us. Not "write a shorter program" but "find the natural folds." Every schema decision, every format choice, every encoding selection — it's all the same question: am I folding this data along its natural geometry, or am I crushing it flat?

Everything after that — Parquet metadata, Delta ACID, zstd level tuning, dictionary size — is implementation detail. The folds are the thing.

Stay locked on the geometry and you'll keep making choices that age well.

← Back to home