Why min/max skipping works or fails completely

How much of the domain does a block's min/max range cover, and why is the failure total on unsorted data?

The derivation that governs the whole article

Before the individual mechanisms, one piece of arithmetic explains most of what follows. It is often asserted but rarely derived.

Take min/max statistics over a block of B rows, and an equality predicate c = v. The block can be skipped if and only if v lies outside [min, max]. So the question is: how much of the value domain does a block's range cover?

If the column is unsorted, a block is effectively a random sample of B values from the column's distribution. For B samples drawn from a continuous domain, the expected fraction of the domain covered by [min, max] is (B − 1)/(B + 1). At a normal row-group size of B = 10,000:

(10,000 − 1) / (10,000 + 1) = 9,999 / 10,001 = 99.98%.

Every block's range covers almost the whole domain. No block is ever skippable.

If the column is perfectly sorted, each block covers B/N of the domain (N is the total number of rows). An equality predicate touches exactly one block out of N/B blocks.

The conclusion is stronger than "skipping works better on sorted data":

The optimizer contributes nothing to this outcome. The whole win was decided at write time, by the choice of how the data is clustered (sorted or grouped) when the files were written. Everything in this article is the consumption of a decision made earlier, during storage layout.

Two corollaries follow.

Corollary 1: min/max is the most outlier-sensitive summary. Min/max is the "extreme values" summary, so one strange row ruins it. A single row with dt = '1970-01-01' from a bad parse widens the range of its block to cover everything. Pruning for that whole block is lost, and the failure is silent. This is why engines keep more than one kind of metadata:

Bloom filters answer membership, not range. So they do not care about order or outliers. That is why Parquet added them, and it is also why they do not replace min/max. The important cell is the empty one: an unsorted column with a range predicate has no metadata solution at all. The only escapes are to change the layout (cluster the data when writing), or to build a real index. Both of these move the cost to write time.

Corollary 2: negative predicates can almost never prune. WHERE status <> 'X' cannot skip a block whose range contains X, because that block almost certainly also holds rows that are not X. Skipping can prove the absence of a value. No summary can prove the absence of everything except one value. A query whose selectivity comes from negation gets nothing from this whole article.

Three families of skipping metadata

Min/max is only one of at least three kinds of skipping metadata, and the equality-on-unsorted case cannot be reached without the second one:

1. Range summaries (min/max): good for range and equality on clustered data.
2. Membership summaries (Bloom filters): good for equality and IN-lists on any order.
3. Value lists for low-cardinality columns: the block stores the full list of distinct values it holds (for example the 3 values of a status column), which gives an exact answer for equality and IN.

In one sentence: skipping effectiveness is clustering quality and nothing else; min/max is an outlier-sensitive range summary that fails totally on unsorted data, Bloom filters cover the equality half of that gap, and negation cannot be pruned by construction.