Column Statistics and the Page-Skipping Decision

A scan over a petabyte-scale table rarely reads a petabyte. It reads the row groups whose statistics admit the possibility of a match, and the fraction discarded depends entirely on how the data was ordered when it was written. The skipping machinery is simple; the effectiveness is a property of the data layout, which the writer chose for reasons that had nothing to do with this query.

Three structures do the work: per-chunk and per-page min/max bounds, null counts, and optional bloom filters. Each has a different failure mode, and each is used at a different granularity.

Bounds and the pruning inequality

For a predicate x < 40, a page whose minimum is at least 40 cannot contain a match and is discarded outright. A page whose maximum is below 40 is entirely matching, so it needs no further predicate evaluation, only decoding. The general rule is that a range $[lo, hi]$ is disjoint from the predicate’s satisfying set when the predicate cannot hold for any value in the range. For equality, disjoint means the target lies outside $[lo, hi]$. For a range predicate, disjoint means the ranges do not intersect. For a negation, the bounds say almost nothing, because “not equal to 40” is satisfied by every value in a page that contains 40 and by all but one otherwise, so a page containing the value must be read.

Bounds are only sound if they are computed over the values that are actually present, and only if the comparison matches the column’s semantics. This is where most skipping bugs live. A min recorded as the minimum of the ordinals in a dictionary-encoded chunk, rather than of the values, is a bound in the wrong order and will cause a page containing matches to be skipped. A string column compared with a signed byte order when the type declares unsigned order inverts the range for any byte above 0x7f. A timestamp column whose statistics were written in milliseconds and read under a schema that declares microseconds places every bound in the wrong era. None of these produce an error; they produce a fast, wrong answer.

Null counts matter for a different reason. If a page’s null count equals its value count, the page contains no values at all, so every predicate except IS NULL and count(*) can discard it. A null count is also required to interpret a bounds range that excludes nulls: a page with 1000 rows, 900 nulls, and a min/max over the remaining 100 has bounds that describe only a tenth of the page.

Granularity: chunk, page, and the index

The coarsest level is the row-group-level statistic in the file footer, one min/max per column chunk. A reader filtering on order_date prunes whole row groups before fetching any data page, which is why the footer is read first. The limit is that a row group holds many pages, so a predicate that matches one page still forces the reader to fetch and decode that page’s neighbours if it only consults the chunk statistic.

The page index adds a level. It records, per page, the min/max, the null count, and the byte offset, in two structures: a column index holding the statistics in page order, and an offset index holding the page locations so a reader can seek directly to the surviving pages. With the index, a reader that needs page 47 of a chunk jumps there without reading pages 0 through 46. The index is optional and is written after the pages, which means it can be omitted by writers that stream, and it costs additional bytes in the footer region.

The finest level is the value itself, reached only by decoding. No statistics structure can skip within a page, which sets the floor on read amplification: a query matching one row still decodes the page containing it.

Bloom filters and the equality case

Bounds handle ranges and equality on ordered types well when the data is clustered, and poorly when it is not. A column of user identifiers scattered at random across a chunk has a min/max range spanning the whole identifier space, so an equality predicate on one identifier matches the bounds of every page in the chunk. The bounds say nothing, and every page is read.

A bloom filter addresses exactly this case. It is a bit array with $k$ hash functions; insertion sets $k$ bits per value, and a query reports “possibly present” or “definitely absent”. The false-positive rate for $m$ bits, $n$ inserted values, and $k$ hashes is approximately $(1 - e^{-kn/m})^k$, minimized at $k \approx (m/n)\ln 2$, where the rate is about $0.6185^{m/n}$. Ten bits per value gives roughly a 1 percent false-positive rate at seven hashes. The filter has no false negatives by construction, so a “definitely absent” answer is a sound reason to skip the page.

The Parquet bloom filter is stored per column chunk in a dedicated structure whose header names the filter algorithm, the hash function, and the size of the bit array, all chosen by the writer. It is optional, and it is only useful for equality and IN predicates on high-cardinality columns; for ranges it is useless, and for low-cardinality columns the bounds usually prune better anyway. The failure mode is a filter sized for the wrong number of distinct values: a filter built with a small bit budget for a column that turns out to have millions of distinct values saturates, and a saturated filter answers “possibly present” for everything, which is correct and worthless.

import math

def bloom_sizing(n, fp):
    """Bits of filter and hash count for n items at false-positive rate fp."""
    bits = -n * math.log(fp) / (math.log(2) ** 2)
    return math.ceil(bits), max(1, round(bits / n * math.log(2)))

print(bloom_sizing(10**6, 0.01))   # 9585059 bits (~1.2 MB), 7 hashes

The sizing depends on the expected number of distinct values, which is exactly the quantity that is not known until the chunk has been written. A writer that guesses low produces a saturated filter; one that guesses high spends bits on a column that bounds would have pruned anyway. That uncertainty is why the format makes the filter optional rather than part of the base metadata.

Clustering is the real variable

Given sound statistics, the pruning ratio is determined by the correlation between the predicate’s column and the physical order of rows. If the table is sorted by order_date, a range predicate on order_date touches only the row groups whose date range intersects, and the fraction read is proportional to the fraction of the time range requested. If the table is sorted by customer_id instead, the same predicate touches every row group, because each one spans the full date range. The statistics are equally accurate in both files and the reader is equally correct; one file reads a thousandth of the data and the other reads all of it.

This is why physical clustering, not statistics, is the lever. Sorting a table by its most selective filter column, or partitioning it so that each partition holds a narrow range of that column, makes bounds effective. A partition scheme keyed on a low-cardinality column such as region gives coarser pruning than sorting on a high-cardinality column such as timestamp, but partition pruning happens in the catalog before any file is opened, which is cheaper than reading footers.

Multi-dimensional filtering breaks the property. A table clustered by date answers date predicates well and customer_id predicates badly; a table clustered by customer answers the reverse. A second copy sorted the other way, or a second clustering key inside a finer partition, restores pruning for both at the cost of storing and maintaining the data twice. Formats cannot solve this: the layout is one-dimensional and the predicates are not.

Cost accounting

The decision to skip is not free. Reading a page index costs bytes and a parse; reading a bloom filter costs a fetch and $k$ hash computations per probe; evaluating a bounds predicate costs a comparison. For a chunk with a thousand pages, the index read is worthwhile. For a chunk with two pages, the index costs more than the pages it might skip.

The break-even point depends on the ratio of metadata bytes to page bytes. A column index with two 8-byte bounds per page plus a null count is roughly 20 bytes per page against a page of a megabyte, so the index is negligible at that page size and significant at a page size of a few kilobytes. Small pages improve skipping granularity and worsen metadata overhead, which is the same trade that governs row group size in Inside a Parquet File.

There is also a correctness obligation that the reader cannot delegate. Statistics must be treated as optional and possibly absent, because the format permits writers to omit them; a reader that assumes their presence fails on files from such a writer. And statistics must be treated as advisory in the sense that a predicate evaluation still happens on the values that survive, because a page whose bounds admit a match may still contain no matching row. Skipping reduces work; it never replaces the filter. The interaction between the surviving pages and the encodings inside them is where the pruning win is finally realized, since a surviving page still has to be decoded under whatever scheme Dictionary Encoding and the Cardinality Cliff selected for it.