Bloom filter
A Bloom filter is a space-efficient probabilistic data structure used to test whether a value might be in a set, with no false negatives but a small, tunable rate of false positives.
Overview
A Bloom filter answers one narrow question very cheaply: "could this value be in the set?" It never produces a false negative — if it says a value is not present, that's guaranteed true — but it can produce false positives, occasionally saying a value might be present when it isn't. In exchange for that small imprecision, a Bloom filter uses far less memory than storing the actual set of values, and both inserting and checking membership are extremely fast.
How It Works
A Bloom filter is a bit array combined with several hash functions. Adding a value sets the bits at the positions its hash functions point to; checking a value tests whether all of those bit positions are set. If any of them are unset, the value is definitely absent. If all are set, the value is probably present — possibly because other values happened to set the same bits.
Use Cases in Databases
Databases use Bloom filters to skip work: rather than doing an expensive lookup or scan, a cheap Bloom filter check can rule out a match with certainty and avoid the expensive path entirely. This is common in join processing (skip probing a hash table when the filter says a key can't match) and in file/block pruning (skip reading a block whose Bloom filter proves it can't contain a filter value).
DuckDB and Bloom Filters
As of DuckDB 1.2, DuckDB reads and writes Parquet Bloom filters transparently. When writing Parquet, DuckDB automatically builds a Bloom filter per column chunk for dictionary-encoded columns; when reading, if a query filters on an equality predicate (WHERE customer_id = 42), DuckDB probes each row group's Bloom filter first and skips row groups the filter proves can't contain a match — before even looking at the row group's zone map or data.
Related terms
The FILTER clause restricts which rows an aggregate function processes, letting you compute multiple conditional aggregates in a single GROUP BY query without CASE expressions.
Predicate pushdown →Predicate pushdown is a query optimization that moves filter conditions as close as possible to the data source, so fewer rows (or bytes) are read before filtering happens.
filter →A filter operation selectively includes or excludes records from a dataset based on one or more conditions.
Zone map (min-max index) →A zone map, or min-max index, is a lightweight index that stores the minimum and maximum value of a column for each block of data, letting queries skip blocks that can't match a filter.
Parquet →Apache Parquet is a columnar storage file format designed for efficient data processing and analytics.
Partition pruning →Partition pruning is a query optimization that skips reading entire partitions of a dataset when a query's filters make it impossible for those partitions to contain matching rows.
FAQS
No. A Bloom filter never reports that a value is absent when it's actually present — it can only occasionally report a false positive, saying a value might be present when it isn't.
Yes. Since DuckDB 1.2, DuckDB both writes and reads Parquet Bloom filters, using them to skip row groups that can't match an equality filter before reading their data.
