Model

Run-length encoding and row order

The order of the rows changes the compression ratio more than the choice among all the encodings.

runs_{random} \approx N (1 - \frac{1}{k}), runs_{sorted} = k, ratio_{sorted} = \frac{N}{k}

$N$: Rows; rows
$k$: Distinct values; distinct values

Trade-off: Precompute vs. compute-on-read

How it behaves

One input on the horizontal axis, the others held fixed.

sortedrandom order

Data table

RLE ratio by distinct values (N = 10⁶ rows)
Distinct values k	series	Compression ratio
2	sorted	500,000×
2.29	sorted	437,000×
2.62	sorted	382,000×
3	sorted	333,000×
3.44	sorted	291,000×
3.93	sorted	254,000×
4.5	sorted	222,000×
5.15	sorted	194,000×
5.9	sorted	169,000×
6.76	sorted	148,000×
7.73	sorted	129,000×
8.85	sorted	113,000×
10.1	sorted	98,700×
11.6	sorted	86,200×
13.3	sorted	75,300×
15.2	sorted	65,800×
17.4	sorted	57,400×
19.9	sorted	50,200×
22.8	sorted	43,800×
26.1	sorted	38,300×
29.9	sorted	33,400×
34.2	sorted	29,200×
39.2	sorted	25,500×
44.9	sorted	22,300×
51.4	sorted	19,500×
58.8	sorted	17,000×
67.3	sorted	14,900×
77.1	sorted	13,000×
88.2	sorted	11,300×
101	sorted	9,900×
116	sorted	8,650×
132	sorted	7,550×
152	sorted	6,600×
174	sorted	5,760×
199	sorted	5,030×
227	sorted	4,400×
260	sorted	3,840×
298	sorted	3,360×
341	sorted	2,930×
391	sorted	2,560×
447	sorted	2,240×
512	sorted	1,950×
586	sorted	1,710×
671	sorted	1,490×
768	sorted	1,300×
879	sorted	1,140×
1.01K	sorted	993×
1.15K	sorted	868×
1.32K	sorted	758×
1.51K	sorted	662×
1.73K	sorted	578×
1.98K	sorted	505×
2.27K	sorted	441×
2.59K	sorted	385×
2.97K	sorted	337×
3.4K	sorted	294×
3.89K	sorted	257×
4.46K	sorted	224×
5.1K	sorted	196×
5.84K	sorted	171×
6.69K	sorted	150×
7.66K	sorted	131×
8.76K	sorted	114×
10K	sorted	99.7×
11.5K	sorted	87.1×
13.2K	sorted	76×
15.1K	sorted	66.4×
17.2K	sorted	58×
19.7K	sorted	50.7×
22.6K	sorted	44.3×
25.9K	sorted	38.7×
29.6K	sorted	33.8×
33.9K	sorted	29.5×
38.8K	sorted	25.8×
44.4K	sorted	22.5×
50.9K	sorted	19.7×
58.2K	sorted	17.2×
66.6K	sorted	15×
76.3K	sorted	13.1×
87.3K	sorted	11.4×
100K	sorted	10×
2	random order	2×
2.29	random order	1.78×
2.62	random order	1.62×
3	random order	1.5×
3.44	random order	1.41×
3.93	random order	1.34×
4.5	random order	1.29×
5.15	random order	1.24×
5.9	random order	1.2×
6.76	random order	1.17×
7.73	random order	1.15×
8.85	random order	1.13×
10.1	random order	1.11×
11.6	random order	1.09×
13.3	random order	1.08×
15.2	random order	1.07×
17.4	random order	1.06×
19.9	random order	1.05×
22.8	random order	1.05×
26.1	random order	1.04×
29.9	random order	1.03×
34.2	random order	1.03×
39.2	random order	1.03×
44.9	random order	1.02×
51.4	random order	1.02×
58.8	random order	1.02×
67.3	random order	1.02×
77.1	random order	1.01×
88.2	random order	1.01×
101	random order	1.01×
116	random order	1.01×
132	random order	1.01×
152	random order	1.01×
174	random order	1.01×
199	random order	1.01×
227	random order	1×
260	random order	1×
298	random order	1×
341	random order	1×
391	random order	1×
447	random order	1×
512	random order	1×
586	random order	1×
671	random order	1×
768	random order	1×
879	random order	1×
1.01K	random order	1×
1.15K	random order	1×
1.32K	random order	1×
1.51K	random order	1×
1.73K	random order	1×
1.98K	random order	1×
2.27K	random order	1×
2.59K	random order	1×
2.97K	random order	1×
3.4K	random order	1×
3.89K	random order	1×
4.46K	random order	1×
5.1K	random order	1×
5.84K	random order	1×
6.69K	random order	1×
7.66K	random order	1×
8.76K	random order	1×
10K	random order	1×
11.5K	random order	1×
13.2K	random order	1×
15.1K	random order	1×
17.2K	random order	1×
19.7K	random order	1×
22.6K	random order	1×
25.9K	random order	1×
29.6K	random order	1×
33.9K	random order	1×
38.8K	random order	1×
44.4K	random order	1×
50.9K	random order	1×
58.2K	random order	1×
66.6K	random order	1×
76.3K	random order	1×
87.3K	random order	1×
100K	random order	1×

Worked examples, recomputed

Every number the mechanisms quote for this relationship is recomputed from it, so none of them disagrees with it.

N = 10⁶, k = 100, sorted → 10,000×

Where it appears

Each mechanism states it in its own names. The general symbol each name stands for is shown with it.

Encoding, Serialization & Compression
What do we turn our values into when we turn them into bytes, and what does that choice cost?
$N \times (1 - 1/ k) runs at random, k sorted$
Read it in place →