Law

Error falls as one over the square root

Approximation buys space at a square-root rate: the error of an estimate from m independent observations is proportional to 1/√m. To halve the error you need four times the memory.

error \approx \frac{c}{m}

$m$: Observations; independent observations: registers, retained hashes, ring positions
$c$: Constant; set by the estimator (1.04 for HyperLogLog, about 1 for k minimum values and for virtual nodes)

Trade-off: Exactness vs. approximation

How it behaves

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

HyperLogLog (c = 1.04)k minimum values, virtual nodes (c ≈ 1)

Data table

Standard error by observations kept
Observations m	series	Standard error
10	HyperLogLog (c = 1.04)	32.9%
11.5	HyperLogLog (c = 1.04)	30.6%
13.3	HyperLogLog (c = 1.04)	28.5%
15.4	HyperLogLog (c = 1.04)	26.5%
17.8	HyperLogLog (c = 1.04)	24.7%
20.5	HyperLogLog (c = 1.04)	23%
23.7	HyperLogLog (c = 1.04)	21.4%
27.4	HyperLogLog (c = 1.04)	19.9%
31.6	HyperLogLog (c = 1.04)	18.5%
36.5	HyperLogLog (c = 1.04)	17.2%
42.2	HyperLogLog (c = 1.04)	16%
48.7	HyperLogLog (c = 1.04)	14.9%
56.2	HyperLogLog (c = 1.04)	13.9%
64.9	HyperLogLog (c = 1.04)	12.9%
75	HyperLogLog (c = 1.04)	12%
86.6	HyperLogLog (c = 1.04)	11.2%
100	HyperLogLog (c = 1.04)	10.4%
115	HyperLogLog (c = 1.04)	9.68%
133	HyperLogLog (c = 1.04)	9.01%
154	HyperLogLog (c = 1.04)	8.38%
178	HyperLogLog (c = 1.04)	7.8%
205	HyperLogLog (c = 1.04)	7.26%
237	HyperLogLog (c = 1.04)	6.75%
274	HyperLogLog (c = 1.04)	6.28%
316	HyperLogLog (c = 1.04)	5.85%
365	HyperLogLog (c = 1.04)	5.44%
422	HyperLogLog (c = 1.04)	5.06%
487	HyperLogLog (c = 1.04)	4.71%
562	HyperLogLog (c = 1.04)	4.39%
649	HyperLogLog (c = 1.04)	4.08%
750	HyperLogLog (c = 1.04)	3.8%
866	HyperLogLog (c = 1.04)	3.53%
1K	HyperLogLog (c = 1.04)	3.29%
1.15K	HyperLogLog (c = 1.04)	3.06%
1.33K	HyperLogLog (c = 1.04)	2.85%
1.54K	HyperLogLog (c = 1.04)	2.65%
1.78K	HyperLogLog (c = 1.04)	2.47%
2.05K	HyperLogLog (c = 1.04)	2.3%
2.37K	HyperLogLog (c = 1.04)	2.14%
2.74K	HyperLogLog (c = 1.04)	1.99%
3.16K	HyperLogLog (c = 1.04)	1.85%
3.65K	HyperLogLog (c = 1.04)	1.72%
4.22K	HyperLogLog (c = 1.04)	1.6%
4.87K	HyperLogLog (c = 1.04)	1.49%
5.62K	HyperLogLog (c = 1.04)	1.39%
6.49K	HyperLogLog (c = 1.04)	1.29%
7.5K	HyperLogLog (c = 1.04)	1.2%
8.66K	HyperLogLog (c = 1.04)	1.12%
10K	HyperLogLog (c = 1.04)	1.04%
11.5K	HyperLogLog (c = 1.04)	0.968%
13.3K	HyperLogLog (c = 1.04)	0.901%
15.4K	HyperLogLog (c = 1.04)	0.838%
17.8K	HyperLogLog (c = 1.04)	0.78%
20.5K	HyperLogLog (c = 1.04)	0.726%
23.7K	HyperLogLog (c = 1.04)	0.675%
27.4K	HyperLogLog (c = 1.04)	0.628%
31.6K	HyperLogLog (c = 1.04)	0.585%
36.5K	HyperLogLog (c = 1.04)	0.544%
42.2K	HyperLogLog (c = 1.04)	0.506%
48.7K	HyperLogLog (c = 1.04)	0.471%
56.2K	HyperLogLog (c = 1.04)	0.439%
64.9K	HyperLogLog (c = 1.04)	0.408%
75K	HyperLogLog (c = 1.04)	0.38%
86.6K	HyperLogLog (c = 1.04)	0.353%
100K	HyperLogLog (c = 1.04)	0.329%
115K	HyperLogLog (c = 1.04)	0.306%
133K	HyperLogLog (c = 1.04)	0.285%
154K	HyperLogLog (c = 1.04)	0.265%
178K	HyperLogLog (c = 1.04)	0.247%
205K	HyperLogLog (c = 1.04)	0.23%
237K	HyperLogLog (c = 1.04)	0.214%
274K	HyperLogLog (c = 1.04)	0.199%
316K	HyperLogLog (c = 1.04)	0.185%
365K	HyperLogLog (c = 1.04)	0.172%
422K	HyperLogLog (c = 1.04)	0.16%
487K	HyperLogLog (c = 1.04)	0.149%
562K	HyperLogLog (c = 1.04)	0.139%
649K	HyperLogLog (c = 1.04)	0.129%
750K	HyperLogLog (c = 1.04)	0.12%
866K	HyperLogLog (c = 1.04)	0.112%
1M	HyperLogLog (c = 1.04)	0.104%
10	k minimum values, virtual nodes (c ≈ 1)	31.6%
11.5	k minimum values, virtual nodes (c ≈ 1)	29.4%
13.3	k minimum values, virtual nodes (c ≈ 1)	27.4%
15.4	k minimum values, virtual nodes (c ≈ 1)	25.5%
17.8	k minimum values, virtual nodes (c ≈ 1)	23.7%
20.5	k minimum values, virtual nodes (c ≈ 1)	22.1%
23.7	k minimum values, virtual nodes (c ≈ 1)	20.5%
27.4	k minimum values, virtual nodes (c ≈ 1)	19.1%
31.6	k minimum values, virtual nodes (c ≈ 1)	17.8%
36.5	k minimum values, virtual nodes (c ≈ 1)	16.5%
42.2	k minimum values, virtual nodes (c ≈ 1)	15.4%
48.7	k minimum values, virtual nodes (c ≈ 1)	14.3%
56.2	k minimum values, virtual nodes (c ≈ 1)	13.3%
64.9	k minimum values, virtual nodes (c ≈ 1)	12.4%
75	k minimum values, virtual nodes (c ≈ 1)	11.5%
86.6	k minimum values, virtual nodes (c ≈ 1)	10.7%
100	k minimum values, virtual nodes (c ≈ 1)	10%
115	k minimum values, virtual nodes (c ≈ 1)	9.31%
133	k minimum values, virtual nodes (c ≈ 1)	8.66%
154	k minimum values, virtual nodes (c ≈ 1)	8.06%
178	k minimum values, virtual nodes (c ≈ 1)	7.5%
205	k minimum values, virtual nodes (c ≈ 1)	6.98%
237	k minimum values, virtual nodes (c ≈ 1)	6.49%
274	k minimum values, virtual nodes (c ≈ 1)	6.04%
316	k minimum values, virtual nodes (c ≈ 1)	5.62%
365	k minimum values, virtual nodes (c ≈ 1)	5.23%
422	k minimum values, virtual nodes (c ≈ 1)	4.87%
487	k minimum values, virtual nodes (c ≈ 1)	4.53%
562	k minimum values, virtual nodes (c ≈ 1)	4.22%
649	k minimum values, virtual nodes (c ≈ 1)	3.92%
750	k minimum values, virtual nodes (c ≈ 1)	3.65%
866	k minimum values, virtual nodes (c ≈ 1)	3.4%
1K	k minimum values, virtual nodes (c ≈ 1)	3.16%
1.15K	k minimum values, virtual nodes (c ≈ 1)	2.94%
1.33K	k minimum values, virtual nodes (c ≈ 1)	2.74%
1.54K	k minimum values, virtual nodes (c ≈ 1)	2.55%
1.78K	k minimum values, virtual nodes (c ≈ 1)	2.37%
2.05K	k minimum values, virtual nodes (c ≈ 1)	2.21%
2.37K	k minimum values, virtual nodes (c ≈ 1)	2.05%
2.74K	k minimum values, virtual nodes (c ≈ 1)	1.91%
3.16K	k minimum values, virtual nodes (c ≈ 1)	1.78%
3.65K	k minimum values, virtual nodes (c ≈ 1)	1.65%
4.22K	k minimum values, virtual nodes (c ≈ 1)	1.54%
4.87K	k minimum values, virtual nodes (c ≈ 1)	1.43%
5.62K	k minimum values, virtual nodes (c ≈ 1)	1.33%
6.49K	k minimum values, virtual nodes (c ≈ 1)	1.24%
7.5K	k minimum values, virtual nodes (c ≈ 1)	1.15%
8.66K	k minimum values, virtual nodes (c ≈ 1)	1.07%
10K	k minimum values, virtual nodes (c ≈ 1)	1%
11.5K	k minimum values, virtual nodes (c ≈ 1)	0.931%
13.3K	k minimum values, virtual nodes (c ≈ 1)	0.866%
15.4K	k minimum values, virtual nodes (c ≈ 1)	0.806%
17.8K	k minimum values, virtual nodes (c ≈ 1)	0.75%
20.5K	k minimum values, virtual nodes (c ≈ 1)	0.698%
23.7K	k minimum values, virtual nodes (c ≈ 1)	0.649%
27.4K	k minimum values, virtual nodes (c ≈ 1)	0.604%
31.6K	k minimum values, virtual nodes (c ≈ 1)	0.562%
36.5K	k minimum values, virtual nodes (c ≈ 1)	0.523%
42.2K	k minimum values, virtual nodes (c ≈ 1)	0.487%
48.7K	k minimum values, virtual nodes (c ≈ 1)	0.453%
56.2K	k minimum values, virtual nodes (c ≈ 1)	0.422%
64.9K	k minimum values, virtual nodes (c ≈ 1)	0.392%
75K	k minimum values, virtual nodes (c ≈ 1)	0.365%
86.6K	k minimum values, virtual nodes (c ≈ 1)	0.34%
100K	k minimum values, virtual nodes (c ≈ 1)	0.316%
115K	k minimum values, virtual nodes (c ≈ 1)	0.294%
133K	k minimum values, virtual nodes (c ≈ 1)	0.274%
154K	k minimum values, virtual nodes (c ≈ 1)	0.255%
178K	k minimum values, virtual nodes (c ≈ 1)	0.237%
205K	k minimum values, virtual nodes (c ≈ 1)	0.221%
237K	k minimum values, virtual nodes (c ≈ 1)	0.205%
274K	k minimum values, virtual nodes (c ≈ 1)	0.191%
316K	k minimum values, virtual nodes (c ≈ 1)	0.178%
365K	k minimum values, virtual nodes (c ≈ 1)	0.165%
422K	k minimum values, virtual nodes (c ≈ 1)	0.154%
487K	k minimum values, virtual nodes (c ≈ 1)	0.143%
562K	k minimum values, virtual nodes (c ≈ 1)	0.133%
649K	k minimum values, virtual nodes (c ≈ 1)	0.124%
750K	k minimum values, virtual nodes (c ≈ 1)	0.115%
866K	k minimum values, virtual nodes (c ≈ 1)	0.107%
1M	k minimum values, virtual nodes (c ≈ 1)	0.1%

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.

Data Movement
How do records cross between two systems that have independent rates, independent availability and independent lifetimes, and what are you willing to lose when the assumption underneath the crossing breaks?
$variance falls roughly as 1/ V$
V (ring positions per node) = $m$
Read it in place →
Core Data Structures
How do we choose a data structure when the real cost is set by the hardware, not by Big-O?
$error \propto \frac{1}{m}$
Read it in place →
Core Data Structures
How do we choose a data structure when the real cost is set by the hardware, not by Big-O?
$1.04/ m$
m (registers) = $m$ · 1.04 = $c$
Read it in place →
Query Processing
Why can one question be answered by plans whose costs differ by a factor of ten thousand, and what does each operator force the engine to do?
$m \approx (\frac{1.04}{error})^{2}$
m (registers) = $m$
Read it in place →
Observability & Operations
What is the smallest description of a running system from which we can find a fault, fast enough to matter, at a cost we can still pay while the system is failing?
$error \propto 1/ n samples$
Read it in place →
Measurement & Experimental Method
What would have to be true for this number to mean what I think it means?
$error of a count n \approx n$
Read it in place →