Block-range indexes (BRIN and zone maps)

PostgreSQL’s BRIN (block range index) divides the table into ranges of pages_per_range pages, 128 by default, and stores one summary per range, for sortable types the minimum and maximum. A query reads the small index, marks every range whose summary could match, then reads every row in those ranges and rechecks it: the index is lossy by design. New ranges at the end of the table stay unsummarized until vacuum runs, brin_summarize_new_values() is called, or the index has autosummarize on. Since PostgreSQL 14, minmax-multi classes keep several intervals per range and bloom classes keep a Bloom filter, for data that isn’t neatly ordered; inclusion classes store a containing value such as a bounding box.

It works when a column follows the physical order of the rows: timestamps in an append-only table, IDs that grow with each insert. On 10 million time-ordered rows a BRIN index took 32 kB against 214 MB for a B-tree, and an hour’s query read one 128-page range. After the rows were shuffled (correlation near 0) the same query matched every range and read all 63,744 pages. BRIN is also the only core PostgreSQL index that doesn’t rule out heap-only (HOT) updates.

Analytic systems use the same idea under other names. ClickHouse has no row-level secondary indexes; its data skipping indexes keep, for example, a minmax per block of granules and help only when the indexed column correlates with the table’s sort key. Parquet files carry min/max statistics per column chunk and, with the page index, per page. Oracle Exadata storage servers keep in-memory storage indexes of each region’s column minimums and maximums and skip the I/O for regions a predicate rules out.