Physical clustering: which units can we skip?

How do we arrange rows so that whole units can be skipped without reading them?

CaseConstructed case · Kavya at Parcelo

The lookup that opens all 3,125 files

Parcelo's scan_events table now sits in about 3,125 Parquet files of 128 MB each (2 billion rows, 640,000 rows per file). Two things go wrong.

The tracking page asks for one parcel_id. That parcel has only about 12 scan rows. Yet the query engine opens all 3,125 files to find them. Nothing is broken: the answer is correct, only slow and expensive.
The query "all scans of depot 17 on last Tuesday" was fast for months. After a large backfill (old data loaded late from a partner system), the same query suddenly scans everything. There is no error, no warning and no change in the query. The query is simply slow.

Layout models made each unit that she reads less wasteful. Now she needs to read fewer units. To understand why the second symptom happened, and why it is so quiet, we need to look at how skipping really works.

How it ends →

Fewer units, not less waste per unit

Layout (Layout models) reduced the waste inside a unit you read. Clustering (also called physical placement) reduces the number of units you read at all. This sounds like the same thing said twice. It is not. The two have very different risk profiles, and that difference is what this article is about.

Layout cannot fail. A columnar file is better than a row file for a query that reads 3 of 100 columns, always. You can compute the gain in advance and bound it: n/k times the compression ratio, maybe 100×, and never zero.
Clustering can fail completely. A table that is perfectly clustered on one column, queried with a filter on a different column, reads every byte, exactly as if you had done nothing. And you still pay the maintenance cost.

A hard constraint appears, and it is geometric, close to a theorem:

Sort keys, Z-order, Hilbert curves, micro-partitions and bucketing (all explained below) are different negotiations with this one fact.

What stops mattering in this article is byte adjacency. Clustering does not care what is inside a unit. It cares only about the distribution of values across units. The working resolution jumps from bytes to units. And the unit size G (rows per unit) was fixed earlier, in Data at rest and the one ratio (about 128 MB), so here it arrives as a parameter you inherited, not one you choose. (Access and media shows where it really comes from.)

One more point reframes everything below. Data skipping is not a storage technique. It is an inference technique. You skip a unit because you can prove that it holds no qualifying row. The proof rests on a small summary of the unit (for example its smallest and largest value). How strong the summary is depends on clustering. The chain is:

clustering → tight summaries → provable exclusion → skipped I/O

Clustering has no direct benefit. It buys nothing you can read. It buys the tightness of a summary, and the summary buys the skip.

The governing question of this article:

The core arithmetic: clustering payoff

Let:

N = number of rows,
G = rows per unit (here a unit is a file or a row group),
U = N/G = number of units,
s = selectivity of the query (the fraction of rows it wants).

Perfectly clustered on the filter column, the query reads max(1, s·U) units. It needs at least one unit, and otherwise only the fraction s of all units.

Randomly placed, each unit contains at least one matching row with probability 1 − (1−s)^G ≈ s·G (when s·G is small). So the query must read about U · min(1, s·G) units, if it has a summary that can tell which units have matches.

Divide the two:

RelationshipWhat clustering can pay →

Clustering payoff \approx min (G, 1/ s)

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

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×

(This holds when the query wants at least one unit's worth of rows, that is s ≥ 1/U. Below that, the clustered query still reads one whole unit, and the gain is capped by that floor of one unit.)

Two readings, both worth remembering:

The maximum value clustering can deliver is the unit size in rows. With G = 10⁶ rows, clustering is worth up to a million-fold and not one unit more, however good your sort key is.
It is also capped by the query's own selectivity. A query that returns half of the table cannot be helped by more than 2×, because you cannot skip what you need.

Both caps bind in practice from opposite ends. Queries with s near 1 do not need clustering. Queries with s below 1/N do not exist (they would return less than one row). Clustering is transformative for selective queries against large units.

Notice the perverse direction: the larger your unit, the more clustering is worth, and the more it costs to maintain. G went up when data moved to object storage. That is exactly why clustering became a first-class concern in the "lakehouse" era (data lakes with table formats on top) and not just a tuning detail.

Same data, same query, same hardware, three orders of magnitude of difference. And the bad case shows up only as "the query is slow". There is no error, no warning and no metric that tells it apart from a query that really needed all the data. This is the variance rule in action: failures of this mechanism are silent.