Row order dominates the codec

Why does the order of the rows change the compression ratio more than the choice of codec?

The encoder looks at the values

Serialization settled where the description of the data lives (in a schema, in a registry, in a footer). From here on we assume that question is answered. We now have a homogeneous run of values: one column, one type, many values.

What is new in this stage is that the encoder gets to look at the data before it decides how to represent it.

This is the first time here that the representation depends on the values and not only on the type. Until now the schema fixed the layout: an int64 took eight bytes because it was declared int64. Here the encoder inspects a block of values and may find that all 128 values lie between 1,000,000 and 1,000,255. Then it spends eight bits on each value. Nothing in the schema said that. The schema said 64 bits. The schema was not wrong, but it was loose: it gave an upper bound, and people mistook the upper bound for a description.

The new constraint is that the choice must be made from a bounded window of data (one block), must be recorded somewhere so the reader can undo it, and can turn out to be wrong if the distribution changes later. The constraint that stops mattering is field extent (where a field starts and ends) and field identity. The governing question becomes:

Given the real distribution of a column, what is the fewest bits per value that still lets you decode at memory-bandwidth speed, and, better, that lets you answer the query without decoding at all?

The last part of that sentence is the reason this stage exists separately from general-purpose compression (General-purpose compression). Many introductions miss it.

Operability means: you can still do useful work (compare, search, add up) on the encoded form.

---

The floor that everything is measured against

Before looking at any technique, let us set a numeric target. We use entropy: the minimum average number of bits per symbol. For values drawn from a distribution p, the order-0 entropy is

"Order-0" means we only use how often each value occurs, and we ignore which values come before or after it. The minimum size for a column of N values is then N × H bits.

This is the economic case for the whole stage: lightweight encodings capture nearly all of the order-0 gain at almost no CPU cost. They leave the general-purpose codec only the last few percent, plus whatever structure of higher order remains. It is also why the pipeline order in Bytes become an output is forced and not just a habit.

But these encodings go beyond order-0, and this is where their real power is. Take one million distinct 64-bit timestamps. Every value is unique, so the order-0 entropy is log₂(10⁶) ≈ 20 bits per value. That is a hard floor for any order-0 method, including a dictionary. Now sort the timestamps. The differences between neighbours are small and regular. The conditional entropy (the entropy of a value given the value before it) falls to two or three bits. The data and the information are the same, but the achievable size is about 7× smaller (20 ÷ 3). This gain came from a decision that has nothing to do with the codec.

This leads to the first topic. It is the answer to Nikhil's problem.

---

Row order: the decision that dominates the codec

Most lists of encodings do not mention sort order. In practice, the order of the rows changes the compression ratio more than the choice among all the encodings below, often by a factor of ten, and it costs nothing at read time.

Let us derive this for run-length encoding (RLE, explained fully in a moment: store a value and how many times it repeats). It is the clearest case.

• A column has k distinct values and N rows. If the rows are in random order, the number of runs is about N × (1 − 1/k). For any k above a few, this is essentially N: every row starts a new run. The ratio is 1 (no gain), and there is even a small expansion.
• If the rows are sorted, there are exactly k runs. The ratio is N / k.

With N = 1,000,000 and k = 100 this is a swing from 1× to 10,000×. Same column, same codec, four orders of magnitude, decided only by row order.

For delta encoding (store the difference from the previous value, explained below) the situation is worse than "no gain". On data with no sequential relation, delta is harmful. The difference of two independent random values has about twice the range of the original values, so you pay about one extra bit per value. Delta is a bet on correlation between neighbours, and losing the bet has a real cost.

Sorting also buys a second benefit through the same act. A file format stores min/max statistics for each chunk of rows (a "zone map"). A query like WHERE event_time > X can skip every chunk whose maximum is below X. But skipping works only when different chunks cover non-overlapping ranges. On a sorted column, every chunk has its own range and skipping is nearly perfect. On an unsorted column, every chunk spans almost the whole domain and skipping is worth exactly nothing. Compression and skipping are two returns on one decision.

The catch: sort order is a scarce resource

You get one physical order per file. Sort by (A, B), and column A gets long runs while column B gets runs only inside each run of equal A values, so the leading column takes almost all of the compression benefit. Which key to choose, how a composite key fails, and when space-filling curves such as Z-order are worth their partial locality are storage layout's questions; what matters here is that the answer decides the ratio.

Streaming ingestion cannot sort globally. Rows arrive in time order, so each file is ordered only locally. Sortedness is something writes consume and only rewriting restores, and the rewrite is compaction: a background job that merges small files into larger, re-sorted files. So compaction improves the compression ratio and the skipping, not only the file count. This benefit is almost never counted when people size the compaction budget.