Opensource internals

ClickHouse Prunes Granules with a Bloom Filter Skip Index

22 min read Jay Hubbert

How ClickHouse's bloom_filter skip index stores one bitset per granule, derives k bit positions from a single 64-bit hash, and trades a false-positive rate for skipped I/O.

TL;DR: ClickHouse’s bloom_filter skip index keeps one bitset per granule. Each indexed value is hashed once into a 64-bit integer; that one integer is then mixed with k fixed seeds to produce k bit positions. A query that hashes to positions that are all set cannot be pruned; if any position is clear the whole granule is skipped without touching the data.

Every columnar database eventually asks the same question: the predicate says user_id = 42; which chunks can be thrown away without reading them?

For a sorted key the answer is cheap — the primary index holds min/max per granule and a binary search answers it. But ClickHouse’s primary key is mandatory and it is a prefix of the sorting key; any other column is unindexed by default. A SELECT ... WHERE user_id = 42 on a table ordered by (created_at, event_id) has to read every row.

Skip indexes are the answer. ClickHouse ships minmax, set, bloom_filter, ngrambf_v1, tokenbf_v1, text, hypothesis and a vector-similarity index. This article is about the most interesting of them: the bloom filter, and the two quite different bloom filters that live behind it — one for numeric keys, one for text.

The bitset

A skip index is a secondary structure attached to a part, laid out in granules — the same 8192-row blocks (by default) that the primary index uses. Each granule gets its own index granule, so pruning is granular: you can skip 8192 rows at a time, not the whole part.

The filter itself is a std::vector<UInt64> — one 8-byte word per 64 bits — and the size is measured in bytes while the modulus is measured in bits:

cpp 
// src/Interpreters/BloomFilter.h:83
    static constexpr size_t word_bits = 8 * sizeof(UnderType);

    size_t size;
    size_t hashes;
    size_t seed;
    size_t words;
    size_t modulus; /// 8 * size, cached for fast modulo.
    libdivide::divider<size_t, libdivide::BRANCHFREE> divider; /// Divider for fast modulo by modulus.
    Container filter;

    inline size_t fastMod(size_t value) const { return value - (value / divider) * modulus; }

That divider line is the reason a separate member exists. A bloom filter needs hash % modulus and % by a runtime value is a 20–40 cycle division on x86. libdivide precomputes a magic-number reciprocal once, and the hot loop becomes a multiply and a shift. libdivide::BRANCHFREE is the variant that avoids a branch on the “does the divisor have a special case” question, which matters because the loop below executes k times per value.

One hash, k positions

Here is the trick that makes the whole thing affordable. A textbook bloom filter computes k independent hashes of the value. That means k hash computations per value — for a granule of 8192 rows and k = 4, that is 32768 hashes.

ClickHouse computes one hash and derives the k positions from it. The derivation is not h1 + i (the naive scheme, which produces correlated positions and terrible false-positive rates for structured data); it is a quadratic probe sequence seeded by a second hash:

cpp 
// src/Interpreters/BloomFilter.cpp:45
template <size_t compile_time_hashes>
ALWAYS_INLINE void addHashPairToFilter(
    BloomFilter::Container & filter,
    const BloomFilterHashPair & pair,
    size_t hashes,
    size_t modulus,
    const BloomDivider & divider)
{
    const size_t count = compile_time_hashes != 0 ? compile_time_hashes : hashes;
    size_t acc = pair.hash1;
    for (size_t i = 0; i < count; ++i)
    {
        size_t pos = fastMod(acc + i * i, modulus, divider);
        filter[pos / BLOOM_WORD_BITS] |= (1ULL << (pos % BLOOM_WORD_BITS));
        acc += pair.hash2;
    }
}

Read it carefully. acc starts at hash1 and is incremented by hash2 on every iteration, so the probed positions are

text 
p_i = (hash1 + i*hash2 + i^2) mod modulus

The i^2 term is what breaks the correlation: consecutive positions are never adjacent, and the sequence is not a linear walk. The i*hash2 term makes it look random per value. This is the classic Kirsch–Mitzenmacher construction — one pair of hashes, k derived positions — and it has essentially the same false-positive behaviour as k independent hashes.

The pair itself comes from CityHash, run twice with different seeds:

cpp 
// src/Interpreters/BloomFilter.cpp:119
BloomFilterHashPair BloomFilter::computeHashPair(const char * data, size_t len, UInt64 seed_)
{
    return
    {
        CityHash_v1_0_2::CityHash64WithSeed(data, len, seed_),
        CityHash_v1_0_2::CityHash64WithSeed(data, len, SEED_GEN_A * seed_ + SEED_GEN_B)
    };
}

SEED_GEN_A and SEED_GEN_B are 845897321 and 217728422 — constants chosen so that SEED_GEN_A * seed + SEED_GEN_B decorrelates the second hash from the first. Two CityHash passes over the value’s bytes, then k multiply-adds.

There is one more subtlety: the default k is 3, and the compiler is told about it:

cpp 
// src/Interpreters/BloomFilter.cpp:138
void BloomFilter::addHashPair(const BloomFilterHashPair & pair)
{
    if (hashes == 3)
        addHashPairToFilter<3>(filter, pair, hashes, modulus, divider);
    else
        addHashPairToFilter<0>(filter, pair, hashes, modulus, divider);
}

addHashPairToFilter<3> makes count a compile-time constant, so the loop unrolls and i * i becomes a strength-reduced increment. The <0> fallback keeps the runtime-hashes path working for other k values. The dispatch happens outside the per-value loop in the bulk entry points (addHashPairs, findHashPairs), so the branch is taken once per batch, not once per row.

The other scheme: one hash, many seeds

The numeric bloom_filter index does not use computeHashPair at all. It takes the opposite approach: one 64-bit hash per value, then k seeds mixed into it.

cpp 
// src/Storages/MergeTree/MergeTreeIndexBloomFilter.cpp:138
void MergeTreeIndexGranuleBloomFilter::fillingBloomFilter(BloomFilterPtr & bf, const HashSet<UInt64> &hashes) const
{
    for (const auto & bf_base_hash : hashes)
        for (size_t i = 0; i < hash_functions; ++i)
            bf->addHashWithSeed(bf_base_hash.getKey(), BloomFilterHash::bf_hash_seed[i]);
}

BloomFilterHash::bf_hash_seed is a fixed table of 15 magic constants:

cpp 
// src/Interpreters/BloomFilterHash.h:31
    static constexpr UInt64 bf_hash_seed[15] = {
        13635471485423070496ULL, 10336109063487487899ULL, 17779957404565211594ULL, 8988612159822229247ULL, 4954614162757618085ULL,
        12980113590177089081ULL, 9263883436177860930ULL, 3656772712723269762ULL, 10362091744962961274ULL, 7582936617938287249ULL,
        15033938188484401405ULL, 18286745649494826751ULL, 6852245486148412312ULL, 8886056245089344681ULL, 10151472371158292780ULL
    };

Each seed is mixed into the base hash by a 128-bit CityHash and the result modulo the filter size:

cpp 
// src/Interpreters/BloomFilter.cpp:234
void BloomFilter::addHashWithSeed(const UInt64 & hash, const UInt64 & hash_seed)
{
    size_t pos = fastMod(hashWithSeedCityHash(hash, hash_seed));
    filter[pos / word_bits] |= (1ULL << (pos % word_bits));
}

So the numeric index does k 128-bit CityHash calls per distinct value, while the text index does 2 64-bit CityHash calls per value and derives the rest arithmetically. The two schemes are mutually incompatible within one filter — different position functions — which is why there are two sets of methods on the same class rather than one unified one.

Sizing: the false-positive-rate table

How big should the bitset be, and how many positions per value? The answer depends on the false-positive rate the user asked for. ClickHouse ships a lookup table of measured false-positive rates and searches it:

cpp 
// src/Interpreters/BloomFilterHash.h:369
    static std::pair<size_t, size_t> calculationBestPractices(double false_positive_rate)
    {
        static const size_t MAX_BITS_PER_ROW = 20;
        static const size_t MAX_HASH_FUNCTION_COUNT = 15;

        static const size_t MIN_BITS_PER_ROW = 2;
        static const size_t MIN_HASH_FUNCTION_COUNT = 2;

The table below is a 21×15 matrix of measured false-positive rates: the entry at [bits_per_row][hash_functions] is the probability that a random query value is wrongly reported as present.

cpp 
// src/Interpreters/BloomFilterHash.h:387
        static const long double probability_lookup_table[MAX_BITS_PER_ROW + 1][MAX_HASH_FUNCTION_COUNT] =
            {
                {1.0L},  /// dummy, 0 bits per row
                {1.0L, 1.0L},
                {1.0L, 0.393L,  0.400L},
                {1.0L, 0.283L,  0.237L,   0.253L},

Read the rows. The second row ({1.0L, 0.393L, 0.400L}) is 2 bits per row: one hash function gives a 39.3% false-positive rate, two give 40.0% — with so few bits, a second probe hurts. The third row (3 bits per row) is better but still a coin flip: 28.3% with one function, 23.7% with two, 25.3% with three. You need more bits before the rate becomes useful at all.

The search walks bits_per_row upward and, for each candidate, finds the largest hash_functions whose best entry in that row still fits the requested rate:

cpp 
// src/Interpreters/BloomFilterHash.h:412
        for (size_t bits_per_row = 1; bits_per_row < MAX_BITS_PER_ROW; ++bits_per_row)
        {
            if (probability_lookup_table[bits_per_row][min_probability_index_each_bits[bits_per_row]] <= static_cast<long double>(false_positive_rate))
            {
                size_t max_size_of_hash_functions = min_probability_index_each_bits[bits_per_row];
                for (size_t size_of_hash_functions = max_size_of_hash_functions; size_of_hash_functions > 0; --size_of_hash_functions)
                    if (probability_lookup_table[bits_per_row][size_of_hash_functions] > static_cast<long double>(false_positive_rate))
                        return std::pair<size_t, size_t>(bits_per_row, size_of_hash_functions + 1);
            }
        }

The min_probability_index_each_bits array is a hand-maintained shortcut: for each row, the index of the entry with the lowest false-positive rate in that row. It lets the outer loop skip rows that cannot possibly satisfy the rate.

The default rate is 0.025, set when the index is created:

cpp 
// src/Storages/MergeTree/MergeTreeIndexBloomFilter.cpp:1500
MergeTreeIndexPtr bloomFilterIndexCreator(
    StorageMetadataPtr metadata_snapshot, const IndexDescription & index, const MergeTreeSettings & /*settings*/)
{
    double false_positive_rate = 0.025;

    if (index.arguments && !index.arguments->children.empty())
    {
        auto argument = getFieldFromIndexArgumentAST(index.arguments->children[0]);
        false_positive_rate = std::min<Float64>(1.0, std::max<Float64>(argument.safeGet<Float64>(), 0.0));
    }

For 0.025 the table picks 8 bits per row and 4 hash functions. That is the default shape of a bloom_filter index in ClickHouse: 1 byte of index per row of data, and 4 probes per lookup.

The granule: one bitset per 8192 rows

The index is not one filter per part. It is one filter per granule, and each granule’s filter is sized by the number of distinct values it covers:

cpp 
// src/Storages/MergeTree/MergeTreeIndexBloomFilter.cpp:60
MergeTreeIndexGranuleBloomFilter::MergeTreeIndexGranuleBloomFilter(
    size_t bits_per_row_, size_t hash_functions_, const std::vector<HashSet<UInt64>>& column_hashes_)
        : bits_per_row(bits_per_row_), hash_functions(hash_functions_), bloom_filters(column_hashes_.size())
{
    if (column_hashes_.empty())
        throw Exception(ErrorCodes::LOGICAL_ERROR, "Granule_index_blocks empty or total_rows is zero.");

    size_t bloom_filter_max_size = 0;
    for (const auto & column_hash : column_hashes_)
        bloom_filter_max_size = std::max(bloom_filter_max_size, column_hash.size());

    static size_t atom_size = 8;

    // If multiple columns are given, we will initialize all the bloom filters
    // with the size of the highest-cardinality one. This is done for compatibility with
    // existing binary serialization format
    total_rows = bloom_filter_max_size;
    size_t bytes_size = (bits_per_row * total_rows + atom_size - 1) / atom_size;

Two things to notice. First, total_rows is not the row count — it is the maximum number of distinct hashes across the indexed columns. The filter is sized by cardinality, not by row count. A LowCardinality(String) column with 12 distinct values in a granule gets a filter sized for 12 values, not 8192. The header comment says the same thing from the other side:

cpp 
// src/Storages/MergeTree/MergeTreeIndexBloomFilter.h:164
    /// The filter is sized by the number of distinct values, so about half of its bits are set.
    /// It still compresses when adjacent granules have the same values, or, with several columns,
    /// when the filters of columns with fewer distinct values are mostly zeros, so the codec is chosen per block.
    bool isCompressible() const override { return false; }

Second, all columns share the size of the highest-cardinality one. The comment says why: binary format compatibility. An existing part on disk has filters of one size; writing a differently-sized filter for a new column would break the format.

The cardinality trick is exploited even harder at build time. A bloom filter only cares about the set of values in a granule, so hashing 8192 identical strings 8192 times is wasted work:

cpp 
// src/Storages/MergeTree/MergeTreeIndexBloomFilter.cpp:1424
void MergeTreeIndexAggregatorBloomFilter::update(const Block & block, size_t * pos, size_t limit)
{
    if (*pos >= block.rows())
        throw Exception(ErrorCodes::LOGICAL_ERROR, "The provided position is not less than the number of block rows. "
                        "Position: {}, Block rows: {}.", *pos, block.rows());

    Block granule_index_block;
    size_t max_read_rows = std::min(block.rows() - *pos, limit);

    for (size_t column = 0; column < index_columns_name.size(); ++column)
    {
        const auto & column_and_type = block.getByName(index_columns_name[column]);
        /// A bloom filter only needs the set of distinct hashes, so for LowCardinality
        /// columns this returns one hash per distinct dictionary value present in the
        /// granule instead of one per row -- turning O(rows) hash-set inserts into
        /// O(distinct). For other columns it is one hash per row, as before.
        auto index_column = BloomFilterHash::hashWithColumnDistinct(column_and_type.type, column_and_type.column, *pos, max_read_rows);

and hashWithColumnDistinct reaches into the LowCardinality dictionary to pull out just the distinct values the slice uses (low_cardinality_col.getDistinctIndexes(pos, limit)). This is the single most valuable optimization in the whole index: a LowCardinality(String) column with 12 distinct values costs 12 hashes per granule, not 8192.

Querying: RPN and the granule test

The predicate is compiled into an RPN expression, the same reverse-polish notation the primary key uses, so that AND/OR/NOT over index atoms can be evaluated with a stack.

The atomic test is “the constant’s hash might be in this granule’s filter”. For the numeric index:

cpp 
// src/Storages/MergeTree/MergeTreeIndexBloomFilter.cpp:179
bool hashMatchesFilter(const BloomFilterPtr& bloom_filter, UInt64 hash, size_t hash_functions)
{
    return std::all_of(BloomFilterHash::bf_hash_seed,
                       BloomFilterHash::bf_hash_seed + hash_functions,
                       [&](const auto &hash_seed)
                       {
                           return bloom_filter->findHashWithSeed(hash,
                                                                 hash_seed);
                       });
}

all_of over the k seeds: the value is possibly present only if every one of the k positions is set. A single clear bit prunes the granule. This is the exact dual of fillingBloomFilter — same seeds, same order, so a value that was added is always found.

For an IN set the test becomes “any of these values might be present”, and the code has to be careful about the direction:

cpp 
// src/Storages/MergeTree/MergeTreeIndexBloomFilter.cpp:190
bool maybeTrueOnBloomFilter(const IColumn * hash_column, const BloomFilterPtr & bloom_filter, size_t hash_functions, bool match_all)
{
    const auto * const_column = typeid_cast<const ColumnConst *>(hash_column);
    const auto * non_const_column = typeid_cast<const ColumnUInt64 *>(hash_column);

    if (!const_column && !non_const_column)
        throw Exception(ErrorCodes::LOGICAL_ERROR, "Hash column must be Const or UInt64.");

    if (const_column)
    {
        return hashMatchesFilter(bloom_filter,
                                 const_column->getValue<UInt64>(),
                                 hash_functions);
    }

    const ColumnUInt64::Container & hashes = non_const_column->getData();

    if (match_all)
    {
        return std::all_of(hashes.begin(),
                           hashes.end(),
                           [&](const auto& hash_row)
                           {
                               return hashMatchesFilter(bloom_filter,
                                                        hash_row,
                                                        hash_functions);
                           });
    }

    return std::any_of(
        hashes.begin(), hashes.end(), [&](const auto & hash_row) { return hashMatchesFilter(bloom_filter, hash_row, hash_functions); });
}

match_all is true for hasAll and false for hasAny / IN. Note the asymmetry: hasAll requires every element to be possibly-present, which means it prunes only if at least one element is definitely-absent. hasAny prunes if every element is definitely-absent.

The RPN evaluation itself is a stack machine over BoolMask values, where each mask carries two bits: “can be true” and “can be false”. That two-bit representation is what lets ClickHouse prune partially under disjunctions: a OR b where a is definitely absent and b is unknown yields “can be true”, and the granule survives; but the optimizer can also record that only b’s branch contributed, which the partial-disjunction machinery uses to narrow ranges further.

Text bloom filters: ngrambf_v1 and tokenbf_v1

The numeric index is useless for strings, because the hash of a string has no relationship to the string’s prefix — WHERE url LIKE '%checkout%' cannot be pruned by a filter that only answers “is this exact value present”.

The text variants solve this by tokenizing the string and indexing the tokens. Two tokenizers ship:

  • ngrambf_v1(n, size, hashes, seed) — n-grams of n code points.
  • tokenbf_v1(size, hashes, seed) — words split on non-alphanumeric bytes.

The n-gram tokenizer works on code points, not bytes, which matters for UTF-8:

cpp 
// src/Interpreters/ITokenizer.cpp:48
bool NgramsTokenizer::nextInString(const char * data, size_t length, size_t & __restrict pos, size_t & __restrict token_start, size_t & __restrict token_length) const
{
    token_start = pos;
    token_length = 0;
    size_t code_points = 0;
    for (; code_points < n && token_start + token_length < length; ++code_points)
    {
        size_t sz = UTF8::seqLength(static_cast<UInt8>(data[token_start + token_length]));
        token_length += sz;
    }
    /// The sequence length is determined by the first character, but we should always check it does not go beyond the buffer length.
    token_length = std::min(token_length, length - token_start);
    pos += UTF8::seqLength(static_cast<UInt8>(data[pos]));
    return code_points == n;
}

Each n-gram is a substring of the original, and the index stores the hash of that substring. So the string "checkout" with n = 3 contributes "che", "heck", "eck", "cko", "kou", "out", "ut". A query for "eckout" tokenizes to "eck", "cko", "kou", "out" — all of which are present in the granule’s filter, so the granule survives. A query for "zebra" produces "zeb", "ebr", "bra" — none present, so the granule is pruned.

The word tokenizer uses a byte-set lookup to find separators, and it does it 16 bytes at a time with SIMD:

cpp 
// src/Interpreters/ITokenizer.h:295
    static constexpr ByteSetLookup separator_chars = ByteSetLookup::fromPredicate([](char c)
    {
        return isASCII(c) && !isAlphaNumericASCII(c);
    });

ByteSetLookup uses pshufb on x86 and tbl on ARM to test 16 bytes per instruction, via two 16-entry nibble tables.

The substring hazard: the first and last token

The interesting bit is how a substring predicate is turned into filter probes. For startsWith('Serv'), the granule must contain the token "Service" — but the probe only knows "Serv", which is not a token, so probing for it would produce false negatives. The solution is to probe for the tokens the needle would have been part of, with the edges treated carefully:

cpp 
// src/Interpreters/ITokenizer.cpp:212
template <typename Tokenizer>
void wordBoundarySubstringToBloomFilter(
    const Tokenizer & tokenizer, const char * data, size_t length, BloomFilter & bloom_filter, bool is_prefix, bool is_suffix)
{
    size_t cur = 0;
    size_t token_start = 0;
    size_t token_len = 0;

    while (cur < length && tokenizer.nextInString(data, length, cur, token_start, token_len))
        if ((token_start > 0 || is_prefix) && (token_start + token_len < length || is_suffix))
            bloom_filter.add(data + token_start, token_len);
}

Read the condition. A token of the needle is probed only if it is not the first token of the needle (unless the needle is a prefix) and not the last token of the needle (unless the needle is a suffix). The needle’s first and last tokens are dropped, because a fragment at the edge of the needle is not necessarily a whole token of the row.

The source comment gives the canonical example:

cpp 
// src/Interpreters/ITokenizer.cpp:202
/// In order to avoid filter updates with incomplete tokens, the first token is
/// ignored unless the substring is a prefix, and the last token is ignored unless
/// the substring is a suffix.
/// Ex: If we want to match row "Service is not ready", and substring is "Serv"
/// or "eady", we don't want to add either of these substrings as tokens since
/// they will not match any of the real tokens. However if our token string is
/// "Service " or " not ", we want to add these full tokens to our bloom filter.

This is the single most subtle correctness detail in the whole index. Take the row "Service is not ready", whose tokens are ["Service", "is", "not", "ready"].

For a needle "Serv" (as startsWith('Serv') produces), the tokenizer yields exactly one token, "Serv", occupying the whole needle. It is both the first and the last token, so both conditions apply and it is dropped:

text 
token_start = 0, token_len = 4, length = 4
keep = (0 > 0 || is_prefix) && (0 + 4 < 4 || is_suffix)
     = (false || true)  && (false || false)
     = false

The probe is therefore nothing at all, and startsWith('Serv') degrades to “read the granule”. That is the correct, conservative outcome: "Serv" is a fragment of the row’s token "Service", so probing for "Serv" would set bits the row never set, and the granule would be pruned — losing the row.

Now take the needle "Service is" with is_prefix = true (a startsWith('Service is') probe). The tokenizer yields "Service" at offset 0 and "is" at offset 7:

text 
token "Service": keep = (0 > 0 || true) && (0 + 7 < 9 || false)
                       = true            &&  true                = true   -> probed
token "is":      keep = (7 > 0 || true) && (7 + 2 < 9 || false)
                       = true            &&  false               = false  -> dropped

"Service" is the row’s first token — because the needle is a prefix of the row, the row’s first token is exactly the needle’s first token. So probing for it is sound, and it is probed. "is" is the needle’s last token and would be a fragment of the row’s second token, so it is dropped.

The middle tokens are always safe, and the reason is structural rather than heuristic: a middle token of the needle is surrounded by the same separator characters inside the needle as in the row (the needle is a contiguous substring of the row), so the row’s tokenizer breaks in the same place and produces that token too.

This is exactly why the n-gram tokenizer behaves differently — and better. An n-gram is never a “whole token”; it is always a fragment, by construction, and fragments are what the n-gram index stores:

cpp 
// src/Interpreters/ITokenizer.cpp:128
void NgramsTokenizer::substringToBloomFilter(const char * data, size_t length, BloomFilter & bloom_filter, bool, bool) const
{
    stringToBloomFilter(data, length, bloom_filter);
}

The is_prefix/is_suffix flags are named but ignored — the signature is bool, bool with unnamed parameters. The needle is simply re-tokenized into n-grams and hashed, which is sound because an n-gram of the needle is an n-gram of the row whenever the needle appears in the row.

What the text index stores

The text index is a completely separate set of classes with a different granule layout. Its granule holds one filter per indexed column, sized by the filter_size parameter in bytes, not by row count:

cpp 
// src/Storages/MergeTree/MergeTreeIndexBloomFilterText.cpp:42
MergeTreeIndexGranuleBloomFilterText::MergeTreeIndexGranuleBloomFilterText(
    const String & index_name_,
    size_t columns_number,
    const BloomFilterParameters & params_)
    : index_name(index_name_)
    , params(params_)
    , bloom_filters(
        columns_number, BloomFilter(params))
    , has_elems(false)
{
}

The build path tokenizes every row and adds each token to the granule’s filter:

cpp 
// src/Storages/MergeTree/MergeTreeIndexBloomFilterText.cpp:145
        else
        {
            for (size_t i = 0; i < rows_read; ++i)
            {
                auto ref = column->getDataAt(current_position + i);
                forEachTokenToBloomFilter(*tokenizer, ref.data(), ref.size(), granule->bloom_filters[col]);
            }
        }

And the text filter uses the contains relation rather than per-value probing. contains is a bitwise subset test: every bit set in bf must also be set in filter:

cpp 
// src/Interpreters/BloomFilter.cpp:203
bool BloomFilter::contains(const BloomFilter & bf)
{
    for (size_t i = 0; i < words; ++i)
    {
        if ((filter[i] & bf.filter[i]) != bf.filter[i])
            return false;
    }
    return true;
}

For a token-based index this is the natural “does the granule have all the tokens the query needs” test. It also explains why the text index cannot use the numeric index’s hashMatchesFilter approach: the text granule was built with add() on the pair scheme, whose positions are p_i = (h1 + i*h2 + i^2) mod m, a different position function than addHashWithSeed. The subset test does not need to know the position function at all — it only needs to know that the set of bits the query’s tokens would occupy is contained in the granule’s set. The query side builds a bloom filter of its own tokens using the same add() path and then asks the subset question. One implementation, two users.

The hasAny/hasAll distinction reappears on top of it:

cpp 
// src/Storages/MergeTree/MergeTreeIndexBloomFilterText.cpp:248
            case RPNElement::FUNCTION_MULTI_SEARCH:
            case RPNElement::FUNCTION_HAS_ANY:
            case RPNElement::FUNCTION_HAS_ALL:
            {
                std::vector<bool> result(element.set_bloom_filters.back().size(), true);

                const auto & bloom_filters = element.set_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]);

                if (element.function == RPNElement::FUNCTION_HAS_ALL)
                    rpn_stack.emplace_back(std::find(std::cbegin(result), std::cend(result), false) == std::end(result), true);
                else
                    rpn_stack.emplace_back(std::find(std::cbegin(result), std::cend(result), true) != std::end(result), true);
                break;
            }

hasAll survives only if every candidate passes contains; hasAny survives if any does. Same logic as the numeric index, but expressed through subset tests instead of per-value probes.

Storage on disk, and the endianness trap

The numeric granule serializes the row count and then the raw bitset. There is an endianness wart here: on big-endian the filter is a whole number of 64-bit words, but the size computed from bits_per_row * total_rows is a byte count that may not be word-aligned.

cpp 
// src/Storages/MergeTree/MergeTreeIndexBloomFilter.cpp:125
    writeVarUInt(total_rows, ostr);

    static size_t atom_size = 8;
    size_t write_size = (bits_per_row * total_rows + atom_size - 1) / atom_size;
    for (const auto & bloom_filter : bloom_filters)
    {
        /// Mirrors `deserializeBinary`: the size is byte-order dependent, the write is not.
        if constexpr (std::endian::native == std::endian::big)
            write_size = bloom_filter->getFilter().size() * sizeof(BloomFilter::UnderType);
        ostr.write(reinterpret_cast<const char *>(bloom_filter->getFilter().data()), write_size);
    }

The write patches its size on big-endian, but the read is unconditional:

cpp 
// src/Storages/MergeTree/MergeTreeIndexBloomFilter.cpp:104
    size_t bytes_size = (bits_per_row * total_rows + atom_size - 1) / atom_size;
    size_t read_size = bytes_size;
    for (auto & filter : bloom_filters)
    {
        filter->resize(bytes_size);
        /// Big-endian granules hold whole `BloomFilter::UnderType` words, so only the payload size
        /// differs there. The read itself is unconditional: guarding it too leaves the filter zeroed.
        if constexpr (std::endian::native == std::endian::big)
            read_size = filter->getFilter().size() * sizeof(BloomFilter::UnderType);
        istr.readStrict(reinterpret_cast<char *>(filter->getFilter().data()), read_size);
    }

Note the comment: “guarding it too leaves the filter zeroed” — a read that is skipped leaves the filter all-zero, which means every value looks absent, which means every granule is pruned, which means data loss. That is the shape of the bug this comment guards against: a bloom filter must never under-approximate.

Costs and trade-offs

Space. At the default 8 bits per row, a bloom_filter index over one column costs 1 byte per distinct value in the granule — for a high-cardinality column that is about 1 byte per row, so a 100-million-row table pays 100 MB per indexed column. With LowCardinality columns the cost collapses, because the filter is sized by distinct values, not rows.

Build time. Per distinct value: one 64-bit hash plus k 128-bit CityHash mixes (numeric path) or two 64-bit CityHash calls (text path). The index is built during merges, so it is paid once per part, and merged parts re-derive it.

Query time. Per granule tested: k modulo operations (each a multiply plus a shift thanks to libdivide) and k bit tests. Cheap.

The false-positive rate is the knob. TYPE bloom_filter(0.001) buys a 100× lower false-positive rate at roughly 4× the index size. The user picks.

Granularity is the other knob. GRANULARITY 1 means one filter per 8192 rows; GRANULARITY 100 means one per 819200 rows, which is 100× cheaper in space but prunes 100× more coarsely.

Correctness. The bloom filter can only ever over-approximate. A value that was added is always found, because the same seeds and the same position function are used on both sides. A value that was not added might be reported present, and then the granule is read and the real filter applied. The one place where this could go wrong is the text index’s contains test — but that is a strict subset test on a filter built by the same add() path, so it also only over-approximates.

The bottom line

The bloom filter skip index is a small, sharp idea: hash each value once, derive k positions from a seed table or a quadratic probe, and keep one bitset per granule. The parts that make it work in practice are the engineering details — libdivide for the modulo, the compile-time dispatch on k = 3, the distinct-value hashing for LowCardinality, the cardinality-based sizing, the contains subset relation for text, and above all the very careful handling of the word-boundary tokenizer’s first and last tokens, where one extra probe would silently drop rows.

The cost is a false-positive rate you choose, and a fixed space overhead per row. For a column with high cardinality and a selective predicate, it is one of the highest-leverage things you can add to a MergeTree table:

sql 
CREATE TABLE events
(
    event_time DateTime,
    event_id   UInt64,
    user_id    UInt64,
    payload    String
)
ENGINE = MergeTree
ORDER BY (event_time, event_id)
INDEX idx_user user_id TYPE bloom_filter(0.001) GRANULARITY 4;

The bloom filter does not make the query fast by itself — it makes the query not read data it does not need to. On a table with a billion rows and a predicate that matches a thousand, that is the difference between reading a terabyte and reading a megabyte.

ClickhousePerformanceInternalsIndexesBloom filter