Changelog category (leave one):

• Experimental Feature

Related Issue:

#101795 (Cuckoo Filter)
#104466 (Binary Fuse Filter)

Changelog entry:

Added experimental cuckoo_filter and binary_fuse_filter skip index types for MergeTree tables. Both are gated by experimental settings and documented as workload-dependent alternatives to bloom_filter, with stateless size-benchmark coverage; the binary-fuse CI benchmark also includes a tiny pruning sanity check.

Documentation entry for user-facing changes

• Documentation is written (mandatory for new features)

Summary

This PR implements and benchmarks two experimental probabilistic filter structures for MergeTree skip indexes: cuckoo_filter and binary_fuse_filter.

Both structures are based on published research on compact approximate membership filters for large static sets. Benchmark results in the stateless tests show that they are not general replacements for bloom_filter in ClickHouse's current skip-index model. In particular, at skip-index GRANULARITY = 1 and a common target FPR such as 0.025, both filters are often larger than bloom_filter because of fixed structural overhead on small per-index-granule key sets.

The feature remains experimental and gated. bloom_filter remains the recommended default skip index unless workload-specific benchmarks show an advantage for one of these filters.

Implemented Index Types

1. cuckoo_filter

Based on Fan et al., "Cuckoo Filter: Practically Better Than Bloom" (ACM CoNEXT 2014), with secondary-index motivation from Kipf et al., "Cuckoo Index" (PVLDB 2020).

Parameters: Single argument — target false positive rate, for example 0.01.

Experimental setting: Requires allow_experimental_cuckoo_filter_index = 1.

2. binary_fuse_filter

Based on Graf & Lemire, "Binary Fuse Filters: Fast and Smaller Than Xor Filters" (arXiv:2201.01174, 2022).

Parameters: Single argument — target false positive rate, for example 0.025.

Experimental setting: Requires allow_experimental_binary_fuse_filter_index = 1.

Benchmark Results

Both filters were evaluated against bloom_filter in 04104_cuckoo_filter_benchmark.sql and 04204_binary_fuse_filter_benchmark.sql.

Methodology: 10,000 rows per table, table index_granularity = 8192, skip-index GRANULARITY = 1, OPTIMIZE FINAL, then sum(secondary_indices_uncompressed_bytes) from system.parts. Each file covers 18 core scenarios: 6 cardinality regimes × 3 FPR values. 04204 adds representative CI-friendly extensions (lower FPR snapshot, skip-index GRANULARITY sensitivity, distribution-sensitive cases, and a tiny pruning sanity check).

Cuckoo Filter vs Bloom

At skip-index GRANULARITY = 1 and fpr = 0.025, cuckoo_filter was larger than bloom_filter in all six tested cardinality regimes (04104 reference).

Observed range at fpr = 0.025: 1.4x–7.5x larger than Bloom.

At the lower fpr = 0.001 (where the requested FPR is rounded up to the nearest supported fingerprint width), cuckoo_filter remains larger than bloom_filter in every tested cardinality regime as well (04104 reference):

Binary Fuse Filter vs Bloom

At skip-index GRANULARITY = 1 and fpr = 0.025, binary_fuse_filter was also larger than bloom_filter in all six core cardinality regimes (04204 reference).

Observed range at fpr = 0.025: 1.2x–6.0x larger than Bloom.

However, binary_fuse_filter can be smaller in specific FPR regimes where its fingerprint width is favorable. For example, at fpr = 0.001:

Additional representative CI-friendly coverage in 04204_binary_fuse_filter_benchmark.sql: lower-FPR snapshot (fpr = 0.005), skip-index GRANULARITY = 1 / 8 / 64, distribution-sensitive scenarios, and a tiny hit/miss pruning sanity check. 04104 covers the full 18-scenario size matrix for cuckoo but does not include those extensions.

Root Cause Analysis

The common issue is structural overhead in small-set regimes:

• cuckoo_filter: per-index-granule bucket count rounds up to a power of two; fixed overhead from slot structure, load-factor requirements, and fingerprint-width choices cannot amortize well for small distinct-key counts.
• binary_fuse_filter: whole-byte fingerprints and power-of-two segment alignment introduce step changes in size. This can be favorable in some FPR regimes, but unfavorable at common settings such as fpr = 0.025.

Both structures are designed for larger static sets where structural overhead is easier to amortize. ClickHouse skip indexes often operate on much smaller per-index-granule key sets, so the benefit is workload- and parameter-dependent.

Why keep this experimental implementation?

Although the MergeTree skip-index results are workload-dependent, these implementations provide reusable probabilistic filter structures that may be useful beyond the current skip-index model, for example for runtime filters or future index layouts with larger key sets.

The user-facing skip-index integrations remain experimental and gated, and the documentation describes the measured limitations instead of presenting these filters as general bloom_filter replacements.

Test Files

• 04077_cuckoo_filter_skip_index.sql — focused cuckoo predicate coverage vs bloom_filter: scalar equality/!=/NOT IN, scalar IN (including a forced miss set), hasAny/hasAll, tuple expression indexes, and map key paths; EXPLAIN sanity for scalar equality
• 04299_binary_fuse_filter_skip_index.sql — same focused predicate coverage for binary_fuse_filter
• 04319_experimental_skip_index_json_isnotnull_nested.sql — JSON path-presence correctness: bare isNotNull(json.path) uses the index; nested forms such as isNotNull(json.path) = 0 do not
• 04078_cuckoo_filter_skip_index_bad_args.sql — cuckoo bad-argument validation, experimental-setting gates, and unchanged-index ALTER behavior
• 04205_binary_fuse_filter_bad_args.sql — same for binary_fuse_filter
• 04104_cuckoo_filter_benchmark.sql — full 18-scenario Cuckoo vs Bloom size benchmark (04104 reference)
• 04204_binary_fuse_filter_benchmark.sql — 18 core scenarios plus representative CI-friendly extensions for Binary Fuse vs Bloom
• 04103_cuckoo_filter_vs_bloom_filter_equivalence.sql — PREWHERE scalar-equality count equivalence vs bloom_filter
• 04203_binary_fuse_filter_vs_bloom_filter_equivalence.sql — same for binary_fuse_filter

Both benchmark files use the same core methodology: same schema/data pattern, OPTIMIZE FINAL, then reading secondary_indices_uncompressed_bytes from system.parts.

Predicates Covered

The implemented index-condition paths follow existing bloom_filter skip-index semantics where applicable, while unsafe or unsupported forms fall back conservatively to avoid false negatives.

Covered paths exercised by the stateless tests include:

• scalar equality (=)
• scalar IN (including a forced miss set in 04077 / 04299)
• array predicates hasAny and hasAll
• tuple expression indexes (x = … AND y = … on a tuple index)
• map key access paths (m['key'] = … with a mapKeys(m) index)
• bare JSON path-presence checks such as isNotNull(json.path) (04319)

Not claimed as index-backed in tests:

• nested boolean forms such as isNotNull(json.path) = 0
• negation / inversion paths such as !=, NOT IN — compared against bloom_filter for result parity, but not forced through the skip index

More complex boolean forms should fall back to normal scanning rather than being forced through the skip index.

Example Usage

SET allow_experimental_cuckoo_filter_index = 1;
SET allow_experimental_binary_fuse_filter_index = 1;

CREATE TABLE t
(
    k UInt64,
    INDEX idx_cuckoo k TYPE cuckoo_filter(0.01) GRANULARITY 1,
    INDEX idx_bfuse k TYPE binary_fuse_filter(0.025) GRANULARITY 1
)
ENGINE = MergeTree
ORDER BY k;