Model

Nulls: bitmap or positions

N (bitmap) vs m lo g_{2} N (positions), equal at \frac{m}{N} = \frac{1}{lo g _{2} N}

$N$: Rows; rows in the chunk
$m$: Present values; present values

How it behaves

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

validity bitmapposition list

Data table

Bits per row by density of present values (N = 10⁶)
Density m/N	series	Bits per row
0	validity bitmap	1
0	validity bitmap	1
0	validity bitmap	1
0	validity bitmap	1
0	validity bitmap	1
0	validity bitmap	1
0	validity bitmap	1
0	validity bitmap	1
0	validity bitmap	1
0	validity bitmap	1
0	validity bitmap	1
0	validity bitmap	1
0	validity bitmap	1
0	validity bitmap	1
0.001	validity bitmap	1
0.001	validity bitmap	1
0.001	validity bitmap	1
0.001	validity bitmap	1
0.001	validity bitmap	1
0.001	validity bitmap	1
0.001	validity bitmap	1
0.001	validity bitmap	1
0.001	validity bitmap	1
0.001	validity bitmap	1
0.002	validity bitmap	1
0.002	validity bitmap	1
0.002	validity bitmap	1
0.002	validity bitmap	1
0.003	validity bitmap	1
0.003	validity bitmap	1
0.003	validity bitmap	1
0.004	validity bitmap	1
0.004	validity bitmap	1
0.004	validity bitmap	1
0.005	validity bitmap	1
0.006	validity bitmap	1
0.006	validity bitmap	1
0.007	validity bitmap	1
0.008	validity bitmap	1
0.009	validity bitmap	1
0.01	validity bitmap	1
0.011	validity bitmap	1
0.013	validity bitmap	1
0.014	validity bitmap	1
0.016	validity bitmap	1
0.018	validity bitmap	1
0.02	validity bitmap	1
0.022	validity bitmap	1
0.025	validity bitmap	1
0.028	validity bitmap	1
0.032	validity bitmap	1
0.036	validity bitmap	1
0.04	validity bitmap	1
0.045	validity bitmap	1
0.05	validity bitmap	1
0.056	validity bitmap	1
0.063	validity bitmap	1
0.071	validity bitmap	1
0.079	validity bitmap	1
0.089	validity bitmap	1
0.1	validity bitmap	1
0.112	validity bitmap	1
0.126	validity bitmap	1
0.141	validity bitmap	1
0.158	validity bitmap	1
0.178	validity bitmap	1
0.2	validity bitmap	1
0.224	validity bitmap	1
0.251	validity bitmap	1
0.282	validity bitmap	1
0.316	validity bitmap	1
0.355	validity bitmap	1
0.398	validity bitmap	1
0.447	validity bitmap	1
0.501	validity bitmap	1
0.562	validity bitmap	1
0.631	validity bitmap	1
0.708	validity bitmap	1
0.794	validity bitmap	1
0.891	validity bitmap	1
1	validity bitmap	1
0	position list	0.002
0	position list	0.002
0	position list	0.003
0	position list	0.003
0	position list	0.003
0	position list	0.004
0	position list	0.004
0	position list	0.004
0	position list	0.005
0	position list	0.006
0	position list	0.006
0	position list	0.007
0	position list	0.008
0	position list	0.009
0.001	position list	0.01
0.001	position list	0.011
0.001	position list	0.013
0.001	position list	0.014
0.001	position list	0.016
0.001	position list	0.018
0.001	position list	0.02
0.001	position list	0.022
0.001	position list	0.025
0.001	position list	0.028
0.002	position list	0.032
0.002	position list	0.035
0.002	position list	0.04
0.002	position list	0.045
0.003	position list	0.05
0.003	position list	0.056
0.003	position list	0.063
0.004	position list	0.071
0.004	position list	0.079
0.004	position list	0.089
0.005	position list	0.1
0.006	position list	0.112
0.006	position list	0.126
0.007	position list	0.141
0.008	position list	0.158
0.009	position list	0.178
0.01	position list	0.199
0.011	position list	0.224
0.013	position list	0.251
0.014	position list	0.282
0.016	position list	0.316
0.018	position list	0.354
0.02	position list	0.398
0.022	position list	0.446
0.025	position list	0.501
0.028	position list	0.562
0.032	position list	0.63
0.036	position list	0.707
0.04	position list	0.793
0.045	position list	0.89
0.05	position list	0.999
0.056	position list	1.12
0.063	position list	1.26
0.071	position list	1.41
0.079	position list	1.58
0.089	position list	1.78
0.1	position list	1.99
0.112	position list	2.24
0.126	position list	2.51
0.141	position list	2.82
0.158	position list	3.16
0.178	position list	3.54
0.2	position list	3.98
0.224	position list	4.46
0.251	position list	5.01
0.282	position list	5.62
0.316	position list	6.3
0.355	position list	7.07
0.398	position list	7.93
0.447	position list	8.9
0.501	position list	9.99
0.562	position list	11.2
0.631	position list	12.6
0.708	position list	14.1
0.794	position list	15.8
0.891	position list	17.8
1	position list	19.9

Worked examples, recomputed

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

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?
$m / N = 1/ lo g_{2} N$
Read it in place →