Baike.dev
Log in
Back to tool/Back to issues
#120581·ClickHouse

The tokenbf_v1 granule probe ANDs whole bloom filters per needle: 32-needle multiSearchAny 942 -> 782 ms, and 1477 -> 906 ms with 128 KiB filters

Author: snelheidaiCreated Sep 17, 2026Updated Sep 17, 2026
Labelsperformancecomp-text-index

Describe the situation

Granule skipping for a tokenbf_v1 / ngrambf_v1 index probes every needle against every granule with BloomFilter::contains(const BloomFilter &) (src/Interpreters/BloomFilter.cpp:203), which ANDs the two filters word by word — filter_size / 8 words, so 4096 words at the default tokenbf_v1(32768, 3, 0). The condition-side needle filter only ever sets hashes bits per token (3 by default), so the loop reads up to 4096 word pairs to answer a question about 3 bits.

contains returns as soon as it finds a needle word the granule lacks. That makes the cost depend on where the needle's first set bit is, and it makes an empty needle filter the worst case: nothing ever mismatches, so the loop always runs to the end. On the fixture below one probe costs ~1.5 µs for an absent 3-bit needle and ~5 µs for an empty needle at 32 KiB, and ~20 µs at 128 KiB.

Empty needle filters are not an edge case. For multiSearchAny and match, the condition calls substringToBloomFilter(..., is_prefix=false, is_suffix=false) (MergeTreeIndexBloomFilterText.cpp:874 and :903), and wordBoundarySubstringToBloomFilter (src/Interpreters/ITokenizer.cpp:213) deliberately drops the needle's first and last token unless the needle is anchored — correct, because a substring may cut a token. A needle that is a single token therefore contributes no bits at all. Every granule then pays a full filter scan per needle for a test that can never prune anything: multiSearchAny with 32 needles over 977 granules spends ~160 ms this way at 32 KiB filters and ~571 ms at 128 KiB.

The fix keeps the same test and removes the scan: when the condition is built, extract each needle filter's non-zero words once, then probe only those (word index, word) pairs. For filters of equal size and seed — already contains's contract — the result is identical by construction, and an empty needle filter costs nothing. Granule selection is unchanged: SelectedMarks and read_rows are identical arm-for-arm on all 20 measured shapes.

The largest wins are on multi-needle atoms (multiSearchAny, IN, hasAny/hasAll, match with alternatives) and grow with the filter size, which is exactly where users raise tokenbf_v1 sizing to cut false positives.

Which ClickHouse versions are affected?

All versions with the tokenbf_v1 / ngrambf_v1 index condition; BloomFilter::contains is unchanged on master as of f77edf0f92492281eef1f7d707278fa8948a5118.

Measured on 26.9.1.1 built from 1f13dbed6a604ba9b32ebad3eb4d2272fe9cdda0, clang++-21, Release, no ThinLTO, aarch64 (4 cores). That base is upstream 7dc4a129f21a36dd40fecf2198a51db0001b5ae8 plus five local experimental commits, byte-identical in both arms, which only touch the text() index classes and skip-index substream preparation; the measured queries use tokenbf_v1, and the one text() index control is flat.

How to reproduce

CREATE TABLE tb32 (ts DateTime, message String,
  INDEX bf message TYPE tokenbf_v1(32768, 3, 0) GRANULARITY 1)
ENGINE = MergeTree ORDER BY ts SETTINGS index_granularity = 8192, min_bytes_for_wide_part = 0;

-- tb128 is the same table with tokenbf_v1(131072, 3, 0); tx uses
-- INDEX idx message TYPE text(tokenizer = splitByNonAlpha) GRANULARITY 1; raw has no index.

INSERT INTO tb32
SELECT toDateTime(1700000000 + number) AS ts,
       concat(arrayStringConcat(arrayMap(k -> concat('w', toString(cityHash64(number, k) % 40000)),
                                         range(4)), ' '),
              if(number % 10 = 0, ' cmn10', ''),
              if(number % 1000 = 0, ' mid01', ''),
              if(number % 100000 = 0, ' rare01', '')) AS message
FROM numbers(0, 8000000)
SETTINGS max_insert_threads = 4, max_block_size = 65536;

OPTIMIZE TABLE tb32 FINAL;  -- 1 part, 977 granules

The needles zzabsent1 … zzabsent32 occur nowhere; rare01 is in 80 rows, cmn10 in 800,000. Measured queries, all with SETTINGS use_query_condition_cache = 0, max_threads = 1, use_skip_indexes = 1:

-- ms_absent1 / ms_absent8 / ms_absent32 (N = 1, 8, 32 absent needles)
SELECT count() FROM tb32 WHERE multiSearchAny(message, ['zzabsent1', ...]);
-- ms128_absent32: the same 32 needles against tb128
SELECT count() FROM tb128 WHERE multiSearchAny(message, ['zzabsent1', ...]);
-- ms_proj32: a real projection rather than count()
SELECT max(ts) FROM tb32 WHERE multiSearchAny(message, ['zzabsent1', ...]);
-- ms_rare_mix: one present needle plus 8 absent ones
SELECT count() FROM tb32 WHERE multiSearchAny(message, ['rare01', 'zzabsent1', ...]);
-- in_absent32, match_alt8, hastoken_rare, ctl_hastoken_cmn
SELECT count() FROM tb32 WHERE message IN ('zzabsent1', ...);
SELECT count() FROM tb32 WHERE match(message, 'zzabsent1|zzabsent2|...|zzabsent8');
SELECT count() FROM tb32 WHERE hasToken(message, 'rare01');
SELECT count() FROM tb32 WHERE hasToken(message, 'cmn10');
-- ms_dense2000: one needle containing 2000 distinct tokens ('w1 w2 … w2000'),
-- the stress case where the sparse word list is no longer small
SELECT count() FROM tb32 WHERE multiSearchAny(message, ['w1 w2 … w2000']);
-- controls on paths this patch must not touch
SELECT count() FROM tb32 WHERE ts > toDateTime(1704000000);          -- ctl_nonfts
SELECT count() FROM tx   WHERE hasAnyTokens(message, ['rare01']);    -- ctl_text_any
SELECT count() FROM raw  WHERE hasAnyTokens(message, ['rare01']);    -- ctl_noindex_any

A/B procedure: two servers from the same commit on one otherwise idle host, each on its own copy of the data, 9 paired interleaved repetitions per shape, the idle server SIGSTOPped around every timed visit. The metric is query_duration_ms from system.query_log; the statistic is the paired geometric mean ratio with a Student-t 95% interval.

Expected performance

Baseline is the unpatched binary, candidate has the patch below. Ratio < 1 is faster; the interval is on the paired log ratio.

query baseline ms candidate ms ratio 95% interval change
ms128_absent32 1477 906 0.6126 0.6101 – 0.6151 −38.74%
in_absent32 231 180 0.7806 0.7759 – 0.7852 −21.94%
ms_proj32 937 777 0.8285 0.8241 – 0.8330 −17.15%
ms_absent32 942 782 0.8312 0.8289 – 0.8335 −16.88%
ms_rare_mix 613 565 0.9224 0.9207 – 0.9240 −7.76%
ms_absent8 588 546 0.9275 0.9243 – 0.9307 −7.25%
hastoken_rare 85 80 0.9502 0.9352 – 0.9656 −4.98%
match_alt8 964 921 0.9571 0.9528 – 0.9615 −4.29%
ctl_hastoken_cmn 542 535 0.9875 0.9860 – 0.9890 −1.25%
ms_absent1 551 546 0.9905 0.9882 – 0.9928 −0.95%
ctl_noindex_any 823 821 0.9988 0.9960 – 1.0016 −0.12%
ms_dense2000 38 39 1.0001 0.9804 – 1.0201 +0.01%
ctl_nonfts 2 2 1.0000 — 0.00%
ctl_text_any 2 2 1.0000 — 0.00%

The removed cost is granules × needles × filter_size, so the percentage depends on how much other work the query does; the absolute saving here is 160 ms (ms_absent32), 571 ms (ms128_absent32) and 51 ms (in_absent32). That matches the mechanism: 977 granules × 32 needles × ~5 µs ≈ 160 ms at 32 KiB, and ~20 µs ≈ 571 ms at 128 KiB.

No shape regressed. ms_dense2000 is the deliberate stress case — a single needle with 2000 tokens leaves ~3150 of 4096 words non-zero, so the sparse list is nearly as long as the filter — and it comes out flat, which is why the patch needs no density fallback.

Correctness, all with zero disagreements:

  • answers identical between the two arms on all 20 shapes;
  • inside the candidate, use_skip_indexes = 1 vs 0 agree on all 20 shapes (the decisive check for a granule-skip change);
  • 51 randomized needle pairs over hasAnyTokens / hasAllTokens / multiSearchAny, drawn from the real vocabulary plus absent, mixed-case, separator-bearing and short needles, each compared against the unindexed copy of the same rows;
  • the 48 *.sql stateless tests matching bloom_filter|tokenbf|full_text|hasToken run through both binaries, with no candidate-only difference, plus 00908_bloom_filter_index, 00944_create_bloom_filter_index_with_merge_tree, 00990_hasToken and 03448_sparse_grams_bloom_filter byte-identical to their committed .reference in both arms.

Counter-effects: cold first touch after a server restart is 0.17/0.17 s, 0.90/0.88 s and 0.89/0.88 s (baseline/candidate) — the patch reads exactly the same index bytes and only changes which words of an already deserialized granule filter are compared. A 4-way concurrent arm is within single-sample noise (0.2408/0.2455 s, 1.0078/1.0073 s, 0.9962/0.9977 s). Peak query memory is identical arm-for-arm on every shape, including 4.2 MiB on the 32-needle tb128 shapes. Index size, index build time and the write path cannot change: the diff reaches no serialization, aggregator or codec code, and both arms read files written by the same unpatched binary.

Limitations: one host, one part, aarch64, warm page cache, single-threaded reads. The cold and concurrent arms are single samples per shape. Both arms were built without ThinLTO, and I have not measured a ThinLTO build. Unlike the duplicate-hashing case in #119562, the effect here is not a redundancy a compiler can remove: the number of loop iterations depends on the runtime contents of the needle filter, so cross-module inlining cannot turn the whole-filter scan into a three-word test.

Related issues and pull requests

https://github.com/ClickHouse/ClickHouse/issues/119562

Additional context

The patch adds buildSparseWords / containsSparse to BloomFilter and switches the five granule probe sites in MergeTreeConditionBloomFilterText, extracting the sparse form once after the RPN is built.

diff --git a/src/Interpreters/BloomFilter.cpp b/src/Interpreters/BloomFilter.cpp
index 95a6c163f27..7c08ee9d6ab 100644
--- a/src/Interpreters/BloomFilter.cpp
+++ b/src/Interpreters/BloomFilter.cpp
@@ -210,6 +210,23 @@ bool BloomFilter::contains(const BloomFilter & bf)
     return true;
 }
 
+BloomFilter::SparseWords BloomFilter::buildSparseWords() const
+{
+    SparseWords sparse_words;
+    for (size_t i = 0; i < words; ++i)
+        if (filter[i])
+            sparse_words.emplace_back(i, filter[i]);
+    return sparse_words;
+}
+
+bool BloomFilter::containsSparse(const SparseWords & sparse_words) const
+{
+    for (const auto & [index, mask] : sparse_words)
+        if ((filter[index] & mask) != mask)
+            return false;
+    return true;
+}
+
 UInt64 BloomFilter::isEmpty() const
 {
     for (size_t i = 0; i < words; ++i)
diff --git a/src/Interpreters/BloomFilter.h b/src/Interpreters/BloomFilter.h
index 5cf7d318ea5..1f848353673 100644
--- a/src/Interpreters/BloomFilter.h
+++ b/src/Interpreters/BloomFilter.h
@@ -66,6 +66,18 @@ public:
     /// Bloom filters must have equal size and seed.
     bool contains(const BloomFilter & bf);
 
+    /// The non-zero words of a filter, as (word index, word) pairs.
+    using SparseWord = std::pair<size_t, UnderType>;
+    using SparseWords = std::vector<SparseWord>;
+
+    /// A filter built from a searched value sets only `hashes` bits per token, but `contains` has to
+    /// AND the whole filter (size/8 words) against every filter it is probed against. Extract the
+    /// non-zero words of the searched value once with `buildSparseWords`, then use `containsSparse`
+    /// to read only those words of this filter. Equivalent to `contains(bf)` whenever `bf` has the
+    /// same size and seed as this filter, which is already `contains`'s contract.
+    SparseWords buildSparseWords() const;
+    bool containsSparse(const SparseWords & sparse_words) const;
+
     const Container & getFilter() const { return filter; }
     Container & getFilter() { return filter; }
     size_t getFilterSizeBytes() const { return size; }
diff --git a/src/Storages/MergeTree/MergeTreeIndexBloomFilterText.cpp b/src/Storages/MergeTree/MergeTreeIndexBloomFilterText.cpp
index c3e32bce8eb..d9c7f689bc5 100644
--- a/src/Storages/MergeTree/MergeTreeIndexBloomFilterText.cpp
+++ b/src/Storages/MergeTree/MergeTreeIndexBloomFilterText.cpp
@@ -177,6 +177,25 @@ MergeTreeConditionBloomFilterText::MergeTreeConditionBloomFilterText(
         context,
         [&](const RPNBuilderTreeNode & node, RPNElement & out) { return extractAtomFromTree(node, out); });
     rpn = std::move(builder).extractRPN();
+
+    /// The needle filters are fixed once the RPN is built, but each of them is probed against every
+    /// granule filter of every part. Extract their non-zero words here, so that `mayBeTrueOnGranule`
+    /// does not AND two whole filters per needle per granule.
+    for (auto & element : rpn)
+    {
+        if (element.bloom_filter)
+            element.sparse_bloom_filter = element.bloom_filter->buildSparseWords();
+
+        element.set_sparse_bloom_filters.resize(element.set_bloom_filters.size());
+        for (size_t column = 0; column < element.set_bloom_filters.size(); ++column)
+        {
+            const auto & column_filters = element.set_bloom_filters[column];
+            auto & column_sparse_filters = element.set_sparse_bloom_filters[column];
+            column_sparse_filters.reserve(column_filters.size());
+            for (const auto & filter : column_filters)
+                column_sparse_filters.push_back(filter.buildSparseWords());
+        }
+    }
 }
 
 bool MergeTreeConditionBloomFilterText::alwaysUnknownOrTrue() const
@@ -216,7 +235,8 @@ bool MergeTreeConditionBloomFilterText::mayBeTrueOnGranule(MergeTreeIndexGranule
             case RPNElement::FUNCTION_EQUALS:
             case RPNElement::FUNCTION_NOT_EQUALS:
             case RPNElement::FUNCTION_HAS:
-                rpn_stack.emplace_back(granule->bloom_filters[element.key_column].contains(*element.bloom_filter), true);
+                rpn_stack.emplace_back(
+                    granule->bloom_filters[element.key_column].containsSparse(element.sparse_bloom_filter), true);
 
                 if (element.function == RPNElement::FUNCTION_NOT_EQUALS)
                     rpn_stack.back() = !rpn_stack.back();
@@ -230,9 +250,10 @@ bool MergeTreeConditionBloomFilterText::mayBeTrueOnGranule(MergeTreeIndexGranule
                 {
                     const size_t key_idx = element.set_key_position[column];
 
-                    const auto & bloom_filters = element.set_bloom_filters[column];
-                    for (size_t row = 0; row < bloom_filters.size(); ++row)
-                        result[row] = result[row] && granule->bloom_filters[key_idx].contains(bloom_filters[row]);
+                    const auto & sparse_bloom_filters = element.set_sparse_bloom_filters[column];
+                    for (size_t row = 0; row < sparse_bloom_filters.size(); ++row)
+                        result[row]
+                            = result[row] && granule->bloom_filters[key_idx].containsSparse(sparse_bloom_filters[row]);
                 }
 
                 rpn_stack.emplace_back(
@@ -247,10 +268,11 @@ bool MergeTreeConditionBloomFilterText::mayBeTrueOnGranule(MergeTreeIndexGranule
             {
                 std::vector<bool> result(element.set_bloom_filters.back().size(), true);
 
-                const auto & bloom_filters = element.set_bloom_filters[0];
+                const auto & sparse_bloom_filters = element.set_sparse_bloom_filters[0];
 
-                for (size_t row = 0; row < bloom_filters.size(); ++row)
-                    result[row] = result[row] && granule->bloom_filters[element.key_column].contains(bloom_filters[row]);
+                for (size_t row = 0; row < sparse_bloom_filters.size(); ++row)
+                    result[row] = result[row]
+                        && granule->bloom_filters[element.key_column].containsSparse(sparse_bloom_filters[row]);
 
                 if (element.function == RPNElement::FUNCTION_HAS_ALL)
                     rpn_stack.emplace_back(std::find(std::cbegin(result), std::cend(result), false) == std::end(result), true);
@@ -264,17 +286,19 @@ bool MergeTreeConditionBloomFilterText::mayBeTrueOnGranule(MergeTreeIndexGranule
                     /// Alternative substrings
                     std::vector<bool> result(element.set_bloom_filters.back().size(), true);
 
-                    const auto & bloom_filters = element.set_bloom_filters[0];
+                    const auto & sparse_bloom_filters = element.set_sparse_bloom_filters[0];
 
-                    for (size_t row = 0; row < bloom_filters.size(); ++row)
-                        result[row] = result[row] && granule->bloom_filters[element.key_column].contains(bloom_filters[row]);
+                    for (size_t row = 0; row < sparse_bloom_filters.size(); ++row)
+                        result[row] = result[row]
+                            && granule->bloom_filters[element.key_column].containsSparse(sparse_bloom_filters[row]);
 
                     rpn_stack.emplace_back(std::find(std::cbegin(result), std::cend(result), true) != std::end(result), true);
                 }
                 else if (element.bloom_filter)
                 {
                     /// Required substrings
-                    rpn_stack.emplace_back(granule->bloom_filters[element.key_column].contains(*element.bloom_filter), true);
+                    rpn_stack.emplace_back(
+                        granule->bloom_filters[element.key_column].containsSparse(element.sparse_bloom_filter), true);
                 }
                 break;
             case RPNElement::FUNCTION_NOT:
diff --git a/src/Storages/MergeTree/MergeTreeIndexBloomFilterText.h b/src/Storages/MergeTree/MergeTreeIndexBloomFilterText.h
index 52694346ca8..3375d7a8d64 100644
--- a/src/Storages/MergeTree/MergeTreeIndexBloomFilterText.h
+++ b/src/Storages/MergeTree/MergeTreeIndexBloomFilterText.h
@@ -128,6 +128,11 @@ private:
 
         /// For FUNCTION_IN and FUNCTION_NOT_IN
         std::vector<size_t> set_key_position;
+
+        /// Non-zero words of `bloom_filter` and of each filter in `set_bloom_filters`, extracted
+        /// once so that probing a granule filter reads only the words the needle actually sets.
+        BloomFilter::SparseWords sparse_bloom_filter;
+        std::vector<std::vector<BloomFilter::SparseWords>> set_sparse_bloom_filters;
     };
 
     using RPN = std::vector<RPNElement>;

@groeneai could you take a look? If the analysis and patch hold up, feel free to open a PR if it fits.

Source: ClickHouse/ClickHouse

View original on GitHubView discussion on GitHub