Chapter 4: Indexes and Conditions #

Welcome back! In Chapter 3: Read Path and Query Execution, you followed a SELECT query as it created tasks and read mark ranges. But one mystery remained: how does ClickHouse decide which mark ranges to read in the first place?

The answer is Indexes and Conditions.

Imagine a reference book with two helpful features. First, a table of contents tells you which chapter to open. Second, pages have highlighted sentences, so you can quickly skip entire pages if they don’t contain what you need.

MergeTree has the same two features:

• The primary index is the table of contents. It is compiled into a KeyCondition, which prunes away whole data parts and mark ranges.
• Skip indexes are the highlighters. They look at each granule and say “yes” or “no” for your condition.

Both features depend on conditions — the compiled version of your WHERE clause. Let’s see how they work together.

The Use Case: Find a Few Needles in a Haystack #

Suppose you have a weather table:

CREATE TABLE weather
(
    event_date Date,
    city       String,
    temp_c     Int32
)
ENGINE = MergeTree
PARTITION BY toYYYYMM(event_date)
ORDER BY (event_date, city)

You add a skip index on temperature:

ALTER TABLE weather
    ADD INDEX temp_minmax (temp_c) TYPE minmax GRANULARITY 1;

Now run this query:

SELECT city, temp_c
FROM weather
WHERE event_date = '2026-01-01'
  AND city = 'Berlin'
  AND temp_c > 20;

Expected output:

Berlin  21

There may be millions of rows in the table. To find this one row, ClickHouse should not read every table. It can use:

• partition pruning to skip February and later parts,
• the primary key to skip granules whose dates are not January 1,
• the skip index to skip granules where the maximum temperature is 20 or colder.

Let’s understand each mechanism.

Key Concept 1: RPNBuilder Turns Your WHERE into a Stack #

Computers love simple, flat instructions. A WHERE clause is a tree of nested conditions. MergeTree uses RPNBuilder to turn that tree into a flat stack in Reverse Polish Notation (RPN).

For example, the condition:

city = 'Berlin' AND temp_c > 20

becomes this stack:

// WHERE city = 'Berlin' AND temp_c > 20
std::vector<RPNElement> rpn = {
    {FUNCTION_EQUALS,  "city",   "Berlin"},
    {FUNCTION_GREATER, "temp_c", 20},
    {FUNCTION_AND},
};

The AND tells the evaluator: combine the two previous results. RPNBuilder’s job is to build this stack from any expression tree.

The relevant class is in Storages/MergeTree/RPNBuilder.h:

class RPNBuilder
{
public:
    using RPNElements = std::vector<RPNElement>;
    RPNElements && extractRPN() &&;
};

RPNElement is different for each index type. For the primary key, it becomes part of a KeyCondition. For a bloom filter index, it becomes a bloom-filter condition. The important idea is the same: flatten the logic.

Key Concept 2: KeyCondition Answers “Can This Range Match?” #

Once the WHERE clause is in RPN form, KeyCondition uses that stack to answer a simple question:

Given a range for the key columns, can any row in this range match?

The primary key index stores the key values at granule boundaries. From those boundaries, ClickHouse can build ranges. If a range cannot contain a matching row, the granule is skipped.

Think of KeyCondition like a yes/no check on a chapter: “Does this chapter contain the word Berlin?” If no, close the book and move on.

A simplified KeyCondition interface looks like this:

class KeyCondition
{
public:
    bool mayBeTrueInRange(
        size_t key_size,
        const FieldRef * left,
        const FieldRef * right,
        const DataTypes & data_types) const;
};

For the query above, KeyCondition uses the primary key (event_date, city) to skip granules where event_date != '2026-01-01' or city cannot be 'Berlin'.

Key Concept 3: PartitionPruner Cuts Whole Sections #

Before looking at granule ranges, ClickHouse can skip entire data parts using partition pruning. If you partition by month, each part belongs to one month. A query for January should never open February parts.

The PartitionPruner in Storages/MergeTree/PartitionPruner.h uses a KeyCondition on the partition key:

bool PartitionPruner::canBePruned(const IMergeTreeDataPart & part) const
{
    // If the partition value cannot match the query,
    // the whole part can be skipped.
    return !partition_condition.mayBeTrueInRange(...);
}

In our example, the partition key is toYYYYMM(event_date). February parts have partition value 202602. The query’s January value 202601 cannot match, so PartitionPruner says “pruned”.

PartitionPruner also caches results by partition_id, so it doesn’t analyze the same partition twice.

Key Concept 4: Skip Indexes Are Highlighted Sections #

The primary key is great for the sort key. But what about other columns, like temp_c? That’s where skip indexes come in.

A skip index is extra metadata for each granule. When a query is running, the index condition checks each granule and says “maybe” or “no”. If “no”, that granule’s mark is removed.

MergeTree supports several index types:

• minmax: stores the minimum and maximum of the indexed expression.
• set: stores a limited set of distinct values.
• bloom_filter: stores a probabilistic set of values. It can have false positives, but never false negatives.
• text: stores dictionaries and postings for text search.
• vector_similarity: stores an HNSW graph for approximate nearest-neighbor search.

All of them follow the same idea. The condition interface is small:

class IMergeTreeIndexCondition
{
public:
    virtual bool mayBeTrueOnGranule(
        MergeTreeIndexGranulePtr granule) const = 0;
    virtual bool alwaysUnknownOrTrue() const { return false; }
};

If mayBeTrueOnGranule returns false, the granule is skipped. If it returns true, the granule might contain matching rows, so it is kept.

For minmax, the granule stores a hyperrectangle — just a fancy name for a box of min/max ranges:

struct MergeTreeIndexGranuleMinMax final : IMergeTreeIndexGranule
{
    Ranges hyperrectangle; // min/max values per indexed column
};

For a set index, the granule stores distinct values up to a limit:

struct MergeTreeIndexGranuleSet final : IMergeTreeIndexGranule
{
    Block block;             // distinct values
    Ranges set_hyperrectangle;
};

For a bloom_filter, the granule stores Bloom filters:

class MergeTreeIndexConditionBloomFilter
{
    bool mayBeTrueOnGranule(
        const MergeTreeIndexGranuleBloomFilter * granule) const;
};

Even vector similarity indexes fit this model:

class MergeTreeIndexVectorSimilarity : public IMergeTreeIndex
{
    bool isVectorSimilarityIndex() const override { return true; }
};

They provide approximate nearest neighbors; the condition can skip granules that don’t contain near neighbors.

Key Concept 5: MergeTreeIndexReader Opens the Highlighters #

Reading skip index data from disk is MergeTreeIndexReader’s job. It opens the index files, seeks to the mark of a granule, and deserializes the index granule.

This class lives in Storages/MergeTree/MergeTreeIndexReader.h and MergeTreeIndexReader.cpp. A simplified version of its read method:

void MergeTreeIndexReader::read(
    size_t mark,
    const IMergeTreeIndexCondition * condition,
    MergeTreeIndexGranulePtr & granule)
{
    seekToMark(mark);
    granule = index->createIndexGranule();
    granule->deserializeBinary(streams, ...);
}

After read, the condition can ask mayBeTrueOnGranule(...). If false, the mark is not used.

The reader is careful to only initialize the file streams once. It also uses MarkCache and UncompressedCache to avoid reading marks and compressed data repeatedly.

Key Concept 6: ConditionTemplate Caches Partition Constants #

Remember ConditionTemplate? It is a clever caching wrapper around any condition type, especially KeyCondition.

For each data part, the partition value is already known. If your WHERE contains expressions that depend only on partition key values, ClickHouse can fold them to constants once and reuse the resulting condition for every part in that partition.

For example, the expression toYYYYMM(event_date) = 202601 is always true for a part in partition 202601, and always false for a part in partition 202602. ConditionTemplate notices this and substitutes a constant.

Here is the code from ConditionTemplate.h:

template <class Cond>
class ConditionTemplate
{
public:
    const Cond & generateForPart(const MergeTreeDataPartPtr & part) const;
    const Cond & generateForPartition(
        const MergeTreePartition & partition,
        const String & partition_id) const;
};

The implementation does three things:

1. Try to find a cached condition for this partition_id.
2. If not found, substitute known partition constants into the predicate.
3. Generate a new condition, store it in the cache, and return it.

A simplified version of the cache lookup:

const Cond & ConditionTemplate<Cond>::generateForPartition(...) const
{
    if (auto * cached = lookupSubstituted(partition_id))
        return *cached;

    auto dag = substituteConstantInputs(...);
    return setSubstituted(partition_id, generate(&dag, root));
}

Why is this useful? If a table has thousands of parts in the same partition, ClickHouse does not need to recompile the same condition thousands of times. It compiles once per partition.

Solving the Use Case Step by Step #

Let’s combine everything and see how our SELECT query is processed.

Step-by-step:

1. ClickHouse parses the WHERE clause.
2. RPNBuilder flattens it into RPN elements.
3. PartitionPruner prunes all parts except those in partition 202601.
4. The primary key KeyCondition examines each remaining part’s primary index. It skips granules whose date range does not contain 2026-01-01.
5. For granules that survive, MergeTreeIndexReader reads the temp_minmax index granule.
6. The minmax condition checks if temp_c > 20 can be true. If the granule’s maximum temperature is 20 or less, the granule is skipped.
7. Only the remaining marks are read, and the result is returned.

Output:

Berlin  21

Under the Hood: A Small Code Tour #

Now let’s peek at the actual implementation pieces. You don’t need to memorize them; just notice how small each responsibility is.

RPNBuilder #

RPNBuilder walks the expression tree. It has two main inputs: a node from an AST or a DAG, and a function that knows how to extract atoms.

using ExtractAtomFromTreeFunction =
    std::function<bool(const RPNBuilderTreeNode & node, RPNElement & out)>;

class RPNBuilder
{
public:
    RPNElements && extractRPN() &&;
};

The extract_atom_from_tree_function is different for primary keys, minmax indexes, bloom filters, and so on. That is why the same builder can serve many index types.

ConditionTemplate in Action #

In ConditionTemplate.cpp, the ConditionTemplate stores two things:

• an unsubstituted condition for general use,
• a per-partition cache for specialized conditions.

When generating for a part, it first looks at the cache:

const Cond * ConditionTemplate<Cond>::lookupSubstituted(
    const std::string & cache_key) const
{
    std::unique_lock lock(mutex);
    if (auto it = cache.find(cache_key); it != cache.end())
        return &it->second;
    return nullptr;
}

If the condition is not cached, it builds a new one by substituting partition constants into the DAG:

void fillPartitionConstantsSubstitution(...)
{
    // Replace partition-key expressions with known constants.
}

This is the “constant folding” mentioned in the chapter title.

PartitionPruner’s Cache #

PartitionPruner does not care about granules. It only asks one question: can this partition value match the query? It also caches the answer per partition.

bool PartitionPruner::canBePruned(const IMergeTreeDataPart & part) const
{
    const auto & partition_id = part.info.getPartitionId();
    if (auto it = partition_filter_map.find(partition_id); it != end)
        return !it->second;

    // Compute and cache once per partition.
    is_valid = partition_condition.mayBeTrueInRange(...);
    partition_filter_map.emplace(partition_id, is_valid);
    return !is_valid;
}

MergeTreeIndexReader Initialization #

Inside MergeTreeIndexReader.cpp, streams are created lazily. This prevents opening index files if no skip indexing is needed.

void MergeTreeIndexReader::initStreamIfNeeded()
{
    if (!streams.empty())
        return;
    // Open one stream per substream of the index.
    for (const auto & substream : index_format.substreams)
        streams[substream.type] = makeIndexReaderStream(...).get();
}

Then read() seeks to the right mark and deserializes only that granule.

MergeTreeIndexReadResultPool #

When many threads read the same data part, they can share skip-index results. MergeTreeIndexReadResultPool makes sure only one thread builds the result and the others wait for it.

class MergeTreeIndexReadResultPool
{
public:
    MergeTreeIndexReadResultPtr getOrBuildIndexReadResult(...);
    void clear(size_t part_index);
};

The word “pool” is a hint: it pools resources for parallel readers.

Summary #

You now know the secret behind fast SELECT queries:

• RPNBuilder turns WHERE into a flat RPN stack.
• KeyCondition uses the primary key to prune parts and ranges.
• PartitionPruner skips whole partitions.
• Skip indexes answer “maybe” or “no” for each granule.
• MergeTreeIndexReader reads those index granules from disk.
• ConditionTemplate caches per-partition constant folding, and MergeTreeIndexReadResultPool shares results across threads.

The primary key is like a table of contents. Skip indexes are like highlighted sections. Conditions are the rules that tell both of them what to look for. Together, they let the reader skip huge portions of the table and read only the pages that matter.

Next, we will look at what happens when data changes shape over time: background merges, mutations, and compaction selection. That’s Chapter 5: Background Merges, Mutations, and Compaction Selection.

Happy querying!

Generated by AI Codebase Knowledge Builder