Opensource internals

ClickHouse's Query Condition Cache: Skip Granules You Don't Need to Read

13 min read Jay Hubbert

ClickHouse's QueryConditionCache remembers which granules a predicate emptied, so repeated queries skip them without re-running index analysis. Here's how it works, why it's one-directional, and how `now()` predicates get cached anyway.

TL;DR: ClickHouse caches, per (table, part, predicate), a bitmap of granules that a filter proved empty. Repeated queries skip those granules entirely — no index analysis, no reading, no decompression. The cache only records negative results (“this granule matched nothing”), never positive ones, and it salts the key with settings, time zones, and skip-index profiles so a wrong verdict can never leak between queries.

Index analysis is not free. Every time a query runs, ClickHouse has to figure out which granules of which parts could possibly contain a matching row. That means evaluating the predicate against the primary key index, the minmax indexes, the skip indexes, and — in the hard cases — a recursive exclusion search over the marks.

Now think about a real workload: a monitoring dashboard that runs the same query every 30 seconds, a service filtering on tenant_id = 42 over and over, a batch job re-reading yesterday’s data hourly. The predicate is the same every time. The data isn’t — but the data is also mostly not matching.

That’s a textbook case for memoization, and ClickHouse implements it as the QueryConditionCache: a global LRU that remembers, for each (table UUID, part name, predicate hash) triple, a bitmap of the granules the predicate emptied during the last scan.

What the cache actually stores

The class doc is unusually explicit:

cpp 
// src/Interpreters/Cache/QueryConditionCache.h:26
/// An implementation of predicate caching a la https://doi.org/10.1145/3626246.3653395
///
/// Given the table, part name and a hash of a predicate as key, caches which marks definitely don't match the predicate and which marks may
/// match the predicate. This allows to skip the scan if the same predicate is evaluated on the same data again. Note that this doesn't work
/// the other way round: we can't tell if _all_ rows in the mark match the predicate.
class QueryConditionCache
{
public:
    /// False means none of the rows in the mark match the predicate. We can skip such marks.
    /// True means at least one row in the mark matches the predicate. We need to read such marks.
    using MatchingMarks = std::vector<bool>;

Two things to internalize:

It’s one-directional. The cache records “this granule matched nothing.” It never records “this granule matched everything” — because a scan can’t establish that. If a granule produced rows, the cache can’t tell whether all of them matched.

It’s allowed to be imprecise — in one direction only. The bitmap’s true means “may match.” A granule that matched one row in a million is marked true — the whole granule has to be read. The cache never produces a false negative, which is the only thing that matters for correctness.

MatchingMarks is a std::vector<bool> — a bit-packed boolean array, one bit per granule. A part with 100,000 granules costs 12.5 KB per predicate.

The whole mechanism is controlled by use_query_condition_cache, which defaults to true.

The key: three components, hashed

cpp 
// src/Interpreters/Cache/QueryConditionCache.h:45
private:
    /// A hash of the table id, part name and condition id.
    using Key = UInt128;
cpp 
// src/Interpreters/Cache/QueryConditionCache.cpp:237
QueryConditionCache::Key QueryConditionCache::makeKey(const UUID & table_id, const String & part_name, UInt64 condition_hash)
{
    SipHash hash;
    hash.update(table_id);
    hash.update(part_name);
    hash.update(condition_hash);
    return hash.get128();
}

The key is the part, so a cached verdict about one part never leaks into another. The part name is qualified by the table UUID, so two tables with the same part name (very common in MergeTree — part names come from block ranges and partition values) don’t collide.

There’s a wrinkle for file-backed engines, where “part” is a file:

cpp 
// src/Interpreters/Cache/QueryConditionCache.h:93
    static String makeFilePartName(const String & path, std::string_view version_token);

This folds in a content-version token (ETag for remote objects, mtime+inode+size for local files) so an in-place rewrite of the file yields a different key rather than a stale hit. For a file-backed table, the “part” can change under you, and a stale “this file matches nothing” verdict would be a correctness bug.

The safety property: everything starts as “may match”

This is the detail that makes the whole thing safe. When an entry is created, every granule is marked true — “may match” — so a fresh entry skips nothing:

cpp 
// src/Interpreters/Cache/QueryConditionCache.cpp:396
QueryConditionCache::Entry::Entry(size_t mark_count)
    : matching_marks(mark_count, true)
{
}

The header explains why that default is a correctness requirement, not a performance one: if a query is cancelled mid-scan and the cache had been updated optimistically (“these granules match nothing”), future scans would skip granules the predicate would in fact have matched — wrong results, silently, forever.

By initializing everything to “may match” and only ever clearing bits after the scan has proven the granule empty, a crash can only lose information (the cache knows less than it could), never gain it.

Writing: only clear bits, never set them

cpp 
// src/Interpreters/Cache/QueryConditionCache.cpp:272
void QueryConditionCache::write(
    const UUID & table_id, const String & part_name, UInt64 condition_hash, const String & condition,
    const MarkRanges & mark_ranges, size_t marks_count, bool has_final_mark)
{
    if (table_id == UUIDHelpers::Nil)
        return;

    Key key = makeKey(table_id, part_name, condition_hash);

    auto load_func = [&](){ return std::make_shared<Entry>(marks_count); };

    auto [entry, inserted] = cache.getOrSet(key, load_func);

getOrSet is atomic: two concurrent scans of the same part with the same predicate can’t create two entries; they share one.

Then the update — note the direction:

cpp 
// src/Interpreters/Cache/QueryConditionCache.cpp:311
    {
        std::lock_guard lock(entry->mutex);

        for (const auto & mark_range : mark_ranges)
            std::fill(entry->matching_marks.begin() + mark_range.begin, entry->matching_marks.begin() + mark_range.end, false);

        if (has_final_mark)
            entry->matching_marks[marks_count - 1] = false;
    }

std::fill(..., false) — the entry is only ever narrowed. The mark ranges passed in are the ones the scan proved empty. Nothing is ever set back to true, because “this granule matched something” isn’t a fact the cache can rely on: a later scan of the same part with the same predicate might read a different set of marks (another query’s cached verdict pruned some!), and those un-read marks must stay “may match.”

That last point is subtle and important: the cache is a cache of negative results only, and the negative results are monotone. Once a granule is known empty for a predicate, it stays known empty for as long as the entry lives.

There’s also a fast path that avoids taking the exclusive lock when there’s nothing to do — most writes are no-ops because the same query run repeatedly finds the same granules empty and the bits are already clear.

Why the entry has its own mutex

The CacheBase lock protects the map — the mapping from key to entry. It does not protect the contents of the entry. And the contents are mutated concurrently: a query with 16 streams reads 16 disjoint mark ranges of the same part simultaneously, and each writes back the ranges it proved empty.

Without a per-entry lock, two threads could be doing std::fill(begin, mid, false) and std::fill(mid, end, false) simultaneously on the same std::vector<bool>. std::vector<bool> packs eight booleans into a byte, so the two fills could land in the same byte and lose one another’s writes — a lost update, which means a granule proven empty stays “may match.” Not a correctness bug (only a lost optimization), but a real one.

The SharedMutex lets the many readers of a cached verdict proceed in parallel while the rare writer excludes them.

Reading: turning a bitmap back into mark ranges

The consult side is in MergeTreeDataSelectExecutor::filterPartsByQueryConditionCache. After the cache lookup, the bitmap is converted back into MarkRanges — the surviving granules:

cpp 
// src/Storages/MergeTree/MergeTreeDataSelectExecutor.cpp:1944
            for (const auto & mark_range : part_with_ranges.ranges)
            {
                size_t begin = mark_range.begin;
                for (size_t mark_it = begin; mark_it < mark_range.end;)
                {
                    if (!matching_marks[mark_it])
                    {
                        // ... collapse consecutive zeros into skip ranges ...
                    }
                    else
                        ++mark_it;
                }
            }

0 means “skip this granule,” 1 means “must read it.” Leading zeros are skipped. A gap of zeros between two ones is dropped — unless the gap is smaller than min_marks_for_seek, in which case reading through it is cheaper than seeking past it.

And if every granule of the part was eliminated, the part is dropped from the query entirely:

cpp 
// src/Storages/MergeTree/MergeTreeDataSelectExecutor.cpp:1994
            if (ranges.empty())
                it = parts_with_ranges.erase(it);

A part the cached verdict proves empty is not opened at all. No marks read, no decompression, no filters evaluated.

The predicate hash is not just the predicate

The most delicate part of the design is the key. If two different predicates hashed to the same value, one query’s verdict would be applied to another query’s data — silently returning wrong results.

The base hash is the ActionsDAG hash of the filter expression, covering function names, result types, children, and constant values. But that’s not enough:

sql 
SELECT * FROM t WHERE ts >= now() - INTERVAL 10 DAY;

The DAG hash changes every time the query runs (the constant changes), so this predicate never gets a cache hit. Fine — but there’s a subtler problem in the other direction: a setting can change a function’s result without changing the DAG. formatDateTime with different flags produces different strings from the same DAG. least/greatest propagate NULLs differently. h3ToGeo swaps its arguments.

So the cache key includes a salt computed from every setting a function might capture at build time — settings like session_timezone, formatdatetime_f_prints_single_zero, least_greatest_legacy_null_behavior, h3togeo_lon_lat_result_order, and dozens more.

Two sessions in different time zones produce the same DAG for toDateTime(s), but parse s differently. Without the salt, one session’s verdict would be served to the other. This is the kind of bug that’s nearly impossible to find by testing and completely obvious once you’ve read the rule.

The time-condition trick

now() in a predicate is a special case, handled with a derived condition rather than a salt.

The problem: WHERE ts >= now() - INTERVAL 10 DAY has a different DAG hash every second, so it never caches. But it’s a very common predicate.

The solution: round the time constant onto a grid. On the write side, the condition is strengthened; on the read side, it’s weakened:

cpp 
// src/Processors/QueryPlan/Optimizations/updateQueryConditionCache.cpp:107
    /// Non-deterministic conditions must not be cached under their own hash.
    /// For conditions non-deterministic only because of folded current-time constants,
    /// a deterministic condition can be derived by rounding the constants onto a time grid.

Read the logic carefully, because the asymmetry is the whole trick:

  • Write side (strengthen): the actual filter used now() - 10 days. The derived condition is a rounded version, e.g. rounded up to the next grid point — a narrower condition. If the narrow condition matched no rows in this granule, the wider (actual) condition certainly matched no rows either. So the entry (written under the derived hash) is sound.
  • Read side (weaken): the query probes with the rounded-down version, which is wider. “The wider condition matched no rows” implies “the narrower condition matched no rows” — so skipping is sound.

The two coincide for grid-aligned constants and are one grid cell apart otherwise. The grid factor is a setting (query_condition_cache_time_condition_grid_factor).

This is genuinely elegant reasoning: it takes a predicate that’s not cacheable (its value changes every second) and makes it cacheable by proving that a slightly different, grid-aligned predicate implies the right thing in both directions.

The skip-index profile: another salt

Some cached verdicts come from skip index analysis — “the minmax index on this column says no row in this granule can match.” But skip index analysis depends on which indexes exist and are enabled. If a query runs with use_skip_indexes = 0 and another runs with them on, the verdicts differ.

So skip-index verdicts are stored under a profiled key — the condition hash salted with the profile of the index set that produced the verdict:

cpp 
// src/Storages/MergeTree/MergeTreeDataSelectExecutor.cpp:1771
    /// Each condition is looked up under two keys:
    ///   * the bare condition hash, holding row-level exclusions (always sound);
    ///   * a hash salted with the effective skip-index profile (skip-index exclusions).

A mark may be skipped iff either verdict says it doesn’t match — the merge is an AND of the two “may match” bitmaps:

cpp 
// src/Storages/MergeTree/MergeTreeDataSelectExecutor.cpp:1881
        matching_marks[i] = matching_marks[i] && (*marks_opt)[i];

AND of the “may match” bits: a granule is skipped only if both verdicts agree it cannot match. Conservative in the right direction.

Where the “empty granule” fact comes from

The write side is the read pipeline itself. When the PREWHERE filter processes a granule and the filter removes every row of it, the read task records the granule as “unmatched”:

cpp 
// src/Storages/MergeTree/MergeTreeReadTask.cpp:590
void MergeTreeReadTask::addPrewhereUnmatchedMarks(const MarkRanges & mark_ranges_)
{
    prewhere_unmatched_marks.insert(prewhere_unmatched_marks.end(), mark_ranges_.begin(), mark_ranges_.end());
}

And the write happens when the task is finished:

cpp 
// src/Storages/MergeTree/MergeTreeSelectProcessor.cpp:617
                if (reader_settings.use_query_condition_cache && task && prewhere_info
                    && !task->readersChainCanSkipMarksBeforePrewhere(prewhere_filters_by_top_k_threshold)
                    && !task->appliesMutationsBeforePrewhere()
                    && !row_level_filter
                    && task->getInfo().data_part_info->getDataPart())

Every one of those four extra conditions is a soundness condition:

  • !task->readersChainCanSkipMarksBeforePrewhere(...) — if a skip index upstream of PREWHERE could have filtered marks before PREWHERE saw them, attributing them to the PREWHERE predicate would be a lie.
  • !task->appliesMutationsBeforePrewhere() — on-the-fly mutations filter rows ahead of PREWHERE, for the same reason.
  • !row_level_filter — a row-level security filter is prepended before PREWHERE, but the cache key covers only the query’s PREWHERE hash. A mark hidden by a row policy must not be attributed to the PREWHERE predicate.

That last one is a beautiful example of a cache whose key doesn’t cover everything that influenced the result — the fix is to not write in that case, rather than to make the key bigger.

The whole flow

text 
   query with predicate Q
            │
            ▼
   hash(Q) + settings salt + [skip-index profile]
            │
            ├──► QueryConditionCache::read(table_uuid, part, hash)
            │        │
            │        └──► bitmap of "may match" granules
            │                   │
            │                   ▼
            │             surviving MarkRanges per part
            │             (parts with no surviving ranges are dropped entirely)
            │
            ▼
   index analysis (primary key, minmax, skip indexes)
            │
            ▼
   scan the surviving granules
            │
            ├── granules where the filter removed everything ──► cache.write(cleared bits)
            │
            └── rows ──► result

What this buys you, and what it costs

It buys you the elimination of repeated index analysis. The expensive part of “which granules can match” isn’t the bitmap lookup — it’s the KeyCondition evaluation and the exclusion search. On a warm cache, that work is replaced by a hash lookup and a bit scan.

It buys you the elimination of reading granules that match nothing. The index analysis can only prove a granule is empty using the index; a predicate on a non-key column can’t be resolved from the index at all. But once a scan has observed that a granule contains no matching rows, that fact is cached, and the next run doesn’t read it.

It costs you memory. One bit per granule per (table, part, predicate). The cache is a CacheBase LRU with a max_size_bytes.

It costs you correctness vigilance. Everything in this design is about not serving a verdict computed under different circumstances: a different predicate, a different set of skip indexes, a different time zone, a different row-level policy. The salt functions, the profiles, the derived time conditions, and the !row_level_filter guard are all the same idea applied four times.

It gives up on one direction. The cache can’t record “this granule matches everything,” so a highly selective predicate matching a few rows in every granule buys nothing. The cache is for predicates that are granule-level selective — which is most of them, since a granule is 10 MB of data.

Seeing it in action

sql 
SELECT
    event,
    value
FROM system.events
WHERE event IN ('QueryConditionCacheHits', 'QueryConditionCacheMisses');

A high, stable hit/miss ratio is the signature of a workload with repeated predicates over stable data. A ratio near zero means the predicates are always new — dashboards with per-request filters, for instance — and the cache is pure overhead.

The cache is also inspectable:

sql 
SELECT *
FROM system.query_condition_cache
LIMIT 10;

And to see it working, run the same query twice and compare the SelectedMarks and SelectedRanges counters in system.query_log:

sql 
SELECT
    query_id,
    ProfileEvents['SelectedMarks'] AS marks,
    ProfileEvents['SelectedRanges'] AS ranges,
    ProfileEvents['QueryConditionCacheHits'] AS qcc_hits
FROM system.query_log
WHERE query LIKE '%tenant_id = 42%'
ORDER BY event_time;

The second run should show dramatically fewer selected marks — and, if the predicate empties whole granules, the same query won’t even open the part.

ClickhousePerformanceInternalsMerge treeStorage engineCaching