Density: sparse indexes and zone maps

What does an entry per block buy, and why does a zone map prune nothing without clustering?

The constraint is that the index only has to narrow the search to a unit you are going to read in full anyway. If the read unit is a 4 MB SSTable block (a block of a sorted, immutable file in an LSM-tree database, a write-optimized design that keeps data in such files) or a 128 MB Parquet row group (a chunk of a Parquet file, a columnar file format), an entry per row wastes space in proportion to the number of rows per block.

If a block holds m entries and costs B to read, an entry per block costs 1/m the space of a dense index and adds an expected m/2 in-block comparisons. You choose m so the residual scan cost is comparable to the I/O it saved. This is the same rule that gives the natural transfer size of every storage medium: the fixed cost of an access determines the granularity of the summary above it. It is the same derivation as the disk block, the network packet size, the cache line and the micro-batch.

The precondition is the important part: a sparse index requires the data to be sorted in the same order. Without the sort order you cannot say what a block contains, so you cannot skip it. Sparse density is bought with clustering. That is why SSTables, Parquet row groups and LSM index blocks all pair a sort order with a sparse summary: not three design choices, but one design choice made three times.

Zone maps: keep the summary, drop the pointer

Zone maps are the degenerate limit of sparseness. They keep a per-block summary and drop the pointer. PostgreSQL's BRIN, Parquet footer statistics, Iceberg manifest column bounds (Iceberg is a table format over files) and ClickHouse skip indexes all store min and max per block (sometimes also a Bloom filter, a small structure that says "definitely not here" or "maybe here", a distinct count or a null count) and use them only to eliminate. With a zone map you cannot find a row. You can only prove a block cannot contain it.

The size difference is not small. A BRIN index on a correlated timestamp column stores a handful of bytes per 128-page range, while a B-tree on the same column stores an entry per row: orders of magnitude, routinely three.

Query ts BETWEEN 01:15 AND 01:30 can skip blocks 1 and 3 without reading them. If instead the events are in random order, every block has min 00:00 and max 02:59, and nothing can be skipped.

The sharpest claim of this article:

An unclustered B-tree degrades (more random fetches, worse crossover) but still finds the rows. An unclustered zone map prunes nothing: min/max over randomly distributed values covers the full domain for every block.

That single fact explains why lakehouse engines (table systems over files in object storage) spend so much effort on Z-ordering, sort keys and liquid clustering. It is not layout aesthetics. Zone maps are the only index those formats have, and clustering is the whole input to their effectiveness. If a Parquet or Iceberg query reads far more data than the predicate suggests, the question is never "is there an index?" It is "what is the correlation between the predicate column and the file layout?"

How much a zone map prunes, and what breaks it

The dependence on clustering can be made quantitative instead of folkloric. Take a block of b rows whose values are drawn uniformly at random from the normalized domain [0, 1]. The expected minimum is 1/(b + 1), the expected maximum is b/(b + 1), so the expected width of the block's [min, max] range is (b − 1)/(b + 1). For b = 10⁶ rows that is 0.999998: the block's range covers essentially the whole domain. Every block matches every predicate. Pruning is exactly zero, and the statistics were maintained perfectly the whole time.

Now sort the same column. Each block's range narrows to roughly 1/(number of blocks), and a point predicate hits one block. Nothing about the index changed. Only the order of the data changed. A zone map is a measurement of how well you sorted, reported at query time as an I/O bill. Snowflake's "clustering depth" is that measurement: the average number of overlapping micro-partitions at a point, which is the expected number of blocks a stabbing query touches.

Two practitioner facts cost real money:

• A single outlier destroys a block's pruning. One sentinel date, 9999-12-31 for "no end date" or 1900-01-01 for "unknown", in an otherwise well-clustered block widens its range to the full domain and makes it match every query for the rest of its life. This is the most common cause of "we sorted the table and pruning still does not work". The aggregate is a maximum, so variance in one direction is all it takes.
• Correlation is free when it is natural. An append-only table whose order_date grows with insertion gets pruning without anyone sorting anything, and often gets it on order_id too, because the two columns are correlated. This is why BRIN indexes are very good on naturally clustered data and useless otherwise, and why "sort by one column, get pruning on three" happens: the other two were already correlated.

Min and max are only the first rung.

Each rung costs more metadata and prunes more, with one hard constraint the data layer does not have: the metadata must be small enough to be read entirely before the query begins. Metadata grows with file count, so past some file count planning time dominates execution time, and the metadata needs its own hierarchy (Iceberg's manifest lists). That hierarchy works because min and max are homomorphisms: they can be computed per file, rolled up into a manifest, rolled up again into a manifest list, and merged at any level without recomputation.