Bitfilters

What this extension is for

Bitfilters materializes four families of approximate-membership-query (AMQ) data structures as DuckDB aggregate functions. Build the filter once, store the BLOB as an ordinary column, probe it later — locally, in another DuckDB instance, or shipped over the network.

• • Skip a join when the answer is definitely no: Build a filter from the small "interesting" side of a join, then test the large side against it. False positives let an unwanted row through; false negatives never happen — so the cheap probe + expensive verify pattern is exact for correctness.
• • Per-partition data skipping: Materialize one filter per logical partition, store alongside metadata, and probe at query time to skip whole partitions that can't possibly contain the key. For high-cardinality lookups against fact tables this routinely skips 99%+ of partitions.
• • Compact set artifacts: A Binary Fuse 8 filter is under 9 bits per key — three orders of magnitude smaller than the source set for typical UUID workloads. Persist it in a Parquet column, ship it to another process, embed it in a manifest.
• • DuckDB-native join filters: One family emits filters in the same internal format DuckDB uses for its own runtime join filters — persist a filter, then re-use it in custom data-skipping logic the optimizer recognizes.

Filter families

Four families, three design points. Pick on mutation, memory, and false-positive rate in that order — not the other way around.

• • Quotient — dynamic sets: The only family here that supports deletion and resize. Pick it when the underlying set evolves at runtime. Tunable slot count and FPR. See Quotient filter.
• • XOR — static, cross-system compatible: ~9 bits per key at ~0.39% FPR (8-bit) or ~18 bits per key at ~0.0015% FPR (16-bit) — about 20% smaller than a Bloom at the same FPR. Built once, queried many times. See the Xor filters paper (Graf & Lemire, 2019).
• • Binary Fuse — modern best-in-class: Typically lands under 9 bits per key with very fast construction and lookups — currently the most space-efficient static filter family. Default choice for read-heavy, append-only sets.
• • DuckDB Bloom — native compatibility: Speaks DuckDB's internal Bloom filter format and hash layout, so a persisted filter slots into the engine's own data-skipping path.

How it works

Every filter constructor is a DuckDB aggregate function that takes UBIGINT hashes as input and returns a single BLOB. The result is dense, self-contained, and storable like any other column.

• • Hashes go in, BLOBs come out: Hash your input first — DuckDB's built-in hash() is fine for most cases. For specific algorithms (xxh3_64, MurmurHash3, rapidhash), pair with the hashfuncs extension. Filters distribute keys based on hash bits — quality of the hash matters.
• • Filters as columns: Every filter is just a BLOB. Store it in a regular column, persist to Parquet, send over the wire, hold in a CTE, partition by anything — there is no special filter type, only the matching *_contains probe function.
• • No false negatives, ever: The filter never lies about absence: a false from a probe means the key is definitively not in the source set. False positives are bounded — measure them by probing known non-members and confirm the rate matches the family.
• • Set-membership only — not cardinality: Bitfilters answers "is X in the set?". For cardinality estimation ("how many distinct items?") and set intersection sizes, use the sibling datasketches extension — it has Theta sketches and HyperLogLog for that workload. The two extensions cover complementary problems.

Honest limitations

What probabilistic filters cannot do — read this before designing a system around one.

• • False positives are inherent: Every family here trades exactness for memory. A true from *_contains means probably present, not definitely present. If your downstream cannot tolerate even one wrong yes, pair the probe with an exact verify — the filter just narrows the candidate set.
• • Filters cannot enumerate: There's no way to list the members from a filter — it's set-membership only. If you need the elements themselves, store them; if you need cardinality, use datasketches.
• • Static families don't support updates: XOR, Binary Fuse, and DuckDB-Bloom filters are built once and immutable. Adding a single key requires a full rebuild. Use quotient_filter when the set genuinely churns, or rebuild on a cadence that matches your write throughput.
• • Tiny sets don't earn the filter: For a few thousand elements an in-memory hash set or a sorted array is faster and exact. Bitfilters earns its keep when the source set is large enough that storing the full set is what hurts — millions of keys, per-partition replication, network ship costs.

Common Use Cases

Build an xor8 filter from hashed keys

-- 1% false-positive rate, ~9 bits per key
WITH f AS (
  SELECT xor8_filter(hash(email)) AS filter FROM users
)
SELECT email,
       xor8_filter_contains(f.filter, hash(email)) AS might_be_known
FROM new_signups, f
LIMIT 10;

Per-partition Quotient filter — supports deletion and resize

SELECT bucket,
       quotient_filter(16, 4, hash(id)) AS filter
FROM ids
GROUP BY bucket;