Model

What clustering can pay

The maximum value clustering can deliver is the unit size in rows. It is also capped by the query's own selectivity.

\frac{units read, random}{units read, clustered} \approx \frac{U min ( 1 , s G )}{max ( 1 , s U )} \approx min (G, \frac{1}{s})

$G$: Unit size; rows per unit (a file or a row group)
$U$: Units; number of units, N/G
$s$: Selectivity; the fraction of rows the query wants

How it behaves

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

G = 10⁶ rows per unitG = 10⁴

Data table

Clustering payoff by selectivity
Selectivity s	series	Units read: random ÷ clustered
0	G = 10⁶ rows per unit	1,000,000×
0	G = 10⁶ rows per unit	1,000,000×
0	G = 10⁶ rows per unit	1,000,000×
0	G = 10⁶ rows per unit	1,000,000×
0	G = 10⁶ rows per unit	1,000,000×
0	G = 10⁶ rows per unit	1,000,000×
0	G = 10⁶ rows per unit	1,000,000×
0	G = 10⁶ rows per unit	1,000,000×
0	G = 10⁶ rows per unit	1,000,000×
0	G = 10⁶ rows per unit	1,000,000×
0	G = 10⁶ rows per unit	1,000,000×
0	G = 10⁶ rows per unit	1,000,000×
0	G = 10⁶ rows per unit	1,000,000×
0	G = 10⁶ rows per unit	1,000,000×
0	G = 10⁶ rows per unit	1,000,000×
0	G = 10⁶ rows per unit	1,000,000×
0	G = 10⁶ rows per unit	1,000,000×
0	G = 10⁶ rows per unit	1,000,000×
0	G = 10⁶ rows per unit	1,000,000×
0	G = 10⁶ rows per unit	1,000,000×
0	G = 10⁶ rows per unit	1,000,000×
0	G = 10⁶ rows per unit	794,000×
0	G = 10⁶ rows per unit	631,000×
0	G = 10⁶ rows per unit	501,000×
0	G = 10⁶ rows per unit	398,000×
0	G = 10⁶ rows per unit	316,000×
0	G = 10⁶ rows per unit	251,000×
0	G = 10⁶ rows per unit	200,000×
0	G = 10⁶ rows per unit	158,000×
0	G = 10⁶ rows per unit	126,000×
0	G = 10⁶ rows per unit	100,000×
0	G = 10⁶ rows per unit	79,400×
0	G = 10⁶ rows per unit	63,100×
0	G = 10⁶ rows per unit	50,100×
0	G = 10⁶ rows per unit	39,800×
0	G = 10⁶ rows per unit	31,600×
0	G = 10⁶ rows per unit	25,100×
0	G = 10⁶ rows per unit	20,000×
0	G = 10⁶ rows per unit	15,800×
0	G = 10⁶ rows per unit	12,600×
0	G = 10⁶ rows per unit	10,000×
0	G = 10⁶ rows per unit	7,940×
0	G = 10⁶ rows per unit	6,310×
0	G = 10⁶ rows per unit	5,010×
0	G = 10⁶ rows per unit	3,980×
0	G = 10⁶ rows per unit	3,160×
0	G = 10⁶ rows per unit	2,510×
0.001	G = 10⁶ rows per unit	2,000×
0.001	G = 10⁶ rows per unit	1,580×
0.001	G = 10⁶ rows per unit	1,260×
0.001	G = 10⁶ rows per unit	1,000×
0.001	G = 10⁶ rows per unit	794×
0.002	G = 10⁶ rows per unit	631×
0.002	G = 10⁶ rows per unit	501×
0.003	G = 10⁶ rows per unit	398×
0.003	G = 10⁶ rows per unit	316×
0.004	G = 10⁶ rows per unit	251×
0.005	G = 10⁶ rows per unit	200×
0.006	G = 10⁶ rows per unit	158×
0.008	G = 10⁶ rows per unit	126×
0.01	G = 10⁶ rows per unit	100×
0.013	G = 10⁶ rows per unit	79.4×
0.016	G = 10⁶ rows per unit	63.1×
0.02	G = 10⁶ rows per unit	50.1×
0.025	G = 10⁶ rows per unit	39.8×
0.032	G = 10⁶ rows per unit	31.6×
0.04	G = 10⁶ rows per unit	25.1×
0.05	G = 10⁶ rows per unit	20×
0.063	G = 10⁶ rows per unit	15.8×
0.079	G = 10⁶ rows per unit	12.6×
0.1	G = 10⁶ rows per unit	10×
0.126	G = 10⁶ rows per unit	7.94×
0.158	G = 10⁶ rows per unit	6.31×
0.2	G = 10⁶ rows per unit	5.01×
0.251	G = 10⁶ rows per unit	3.98×
0.316	G = 10⁶ rows per unit	3.16×
0.398	G = 10⁶ rows per unit	2.51×
0.501	G = 10⁶ rows per unit	2×
0.631	G = 10⁶ rows per unit	1.58×
0.794	G = 10⁶ rows per unit	1.26×
1	G = 10⁶ rows per unit	1×
0	G = 10⁴	10,000×
0	G = 10⁴	10,000×
0	G = 10⁴	10,000×
0	G = 10⁴	10,000×
0	G = 10⁴	10,000×
0	G = 10⁴	10,000×
0	G = 10⁴	10,000×
0	G = 10⁴	10,000×
0	G = 10⁴	10,000×
0	G = 10⁴	10,000×
0	G = 10⁴	10,000×
0	G = 10⁴	10,000×
0	G = 10⁴	10,000×
0	G = 10⁴	10,000×
0	G = 10⁴	10,000×
0	G = 10⁴	10,000×
0	G = 10⁴	10,000×
0	G = 10⁴	10,000×
0	G = 10⁴	10,000×
0	G = 10⁴	10,000×
0	G = 10⁴	10,000×
0	G = 10⁴	10,000×
0	G = 10⁴	10,000×
0	G = 10⁴	10,000×
0	G = 10⁴	10,000×
0	G = 10⁴	10,000×
0	G = 10⁴	10,000×
0	G = 10⁴	10,000×
0	G = 10⁴	10,000×
0	G = 10⁴	10,000×
0	G = 10⁴	10,000×
0	G = 10⁴	10,000×
0	G = 10⁴	10,000×
0	G = 10⁴	10,000×
0	G = 10⁴	10,000×
0	G = 10⁴	10,000×
0	G = 10⁴	10,000×
0	G = 10⁴	10,000×
0	G = 10⁴	10,000×
0	G = 10⁴	10,000×
0	G = 10⁴	10,000×
0	G = 10⁴	7,940×
0	G = 10⁴	6,310×
0	G = 10⁴	5,010×
0	G = 10⁴	3,980×
0	G = 10⁴	3,160×
0	G = 10⁴	2,510×
0.001	G = 10⁴	2,000×
0.001	G = 10⁴	1,580×
0.001	G = 10⁴	1,260×
0.001	G = 10⁴	1,000×
0.001	G = 10⁴	794×
0.002	G = 10⁴	631×
0.002	G = 10⁴	501×
0.003	G = 10⁴	398×
0.003	G = 10⁴	316×
0.004	G = 10⁴	251×
0.005	G = 10⁴	200×
0.006	G = 10⁴	158×
0.008	G = 10⁴	126×
0.01	G = 10⁴	100×
0.013	G = 10⁴	79.4×
0.016	G = 10⁴	63.1×
0.02	G = 10⁴	50.1×
0.025	G = 10⁴	39.8×
0.032	G = 10⁴	31.6×
0.04	G = 10⁴	25.1×
0.05	G = 10⁴	20×
0.063	G = 10⁴	15.8×
0.079	G = 10⁴	12.6×
0.1	G = 10⁴	10×
0.126	G = 10⁴	7.94×
0.158	G = 10⁴	6.31×
0.2	G = 10⁴	5.01×
0.251	G = 10⁴	3.98×
0.316	G = 10⁴	3.16×
0.398	G = 10⁴	2.51×
0.501	G = 10⁴	2×
0.631	G = 10⁴	1.58×
0.794	G = 10⁴	1.26×
1	G = 10⁴	1×

Worked examples, recomputed

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

s·G = 10⁻⁶ × 10⁶ = 1: random placement touches every unit

Where it appears

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

Storage: Physical Organization
What should sit next to what, given that I must decide at write time and find out at read time?
$Clustering payoff \approx min (G, 1/ s)$
Read it in place →