ClickHouse Skips Data: Granules, Marks, and Bit-Packed Indexes

TL;DR: A MergeTree scan isn’t a full scan. Parts are cut into granules, each granule gets a bit-packed mark, and the primary key index stores one key value per granule — so ClickHouse can prove a granule can’t match and skip it entirely.

A SELECT on a MergeTree table is, mechanically, a scan of a set of files. The only reason it isn’t a full scan is that the files are chopped into pieces, and each piece carries enough metadata for the engine to prove that the piece cannot contain a matching row.

ClickHouse calls those pieces granules, the metadata is called a mark, and the mechanism that ties them together is the primary key index — one key value per granule, held in memory.

This is the single most important performance idea in MergeTree, and it’s built out of three small, very specific tricks:

Granules are sized in bytes, not rows, so a granule of fat rows isn’t a granule of a million rows.
Marks are bit-packed in memory — three bytes per mark for an integer column, instead of the sixteen bytes a naive {offset, offset_in_block} pair would take.
The primary key index is trimmed: if a key column is nearly constant within a part, the key columns after it aren’t kept in memory at all, because they can’t narrow anything down.

Granules: sized in bytes, not rows

The classic description of MergeTree granularity is “8192 rows”, and that’s the default value of the index_granularity setting. But that’s only the cap. The actual mechanism computes the number of rows per granule from the size of the data being written:

cpp
// src/Storages/MergeTree/MergeTreeIndexGranularity.cpp:115
size_t computeIndexGranularity(
    size_t rows,
    size_t bytes_uncompressed,
    size_t index_granularity_bytes,
    size_t fixed_index_granularity_rows,
    bool blocks_are_granules,
    bool can_use_adaptive_index_granularity)
{
    size_t index_granularity_for_block = 0;

    if (!can_use_adaptive_index_granularity)
    {
        index_granularity_for_block = fixed_index_granularity_rows;
    }
    else
    {
        if (blocks_are_granules)
        {
            index_granularity_for_block = rows;
        }
        else if (index_granularity_bytes != 0 && bytes_uncompressed >= index_granularity_bytes)
        {
            /// index_granularity_bytes == 0 disables adaptive sizing upstream, so this branch is
            /// unreachable with a zero divisor; the explicit check makes that visible to static analysis.
            size_t granules_in_block = bytes_uncompressed / index_granularity_bytes;
            index_granularity_for_block = rows / granules_in_block;
        }
        else
        {
            size_t size_of_row_in_bytes = std::max(bytes_uncompressed / rows, 1UL);
            index_granularity_for_block = index_granularity_bytes / size_of_row_in_bytes;
        }
    }

    /// We should be less or equal than fixed index granularity.
    /// But if block size is a granule size then do not adjust it.
    /// Granularity greater than fixed granularity might come from compact part.
    if (!blocks_are_granules)
        index_granularity_for_block = std::min(fixed_index_granularity_rows, index_granularity_for_block);

    /// Very rare case when index granularity bytes less than single row.
    if (index_granularity_for_block == 0)
        index_granularity_for_block = 1;

    return index_granularity_for_block;
}

Read the interesting branch — the else at the bottom. If the block is smaller than index_granularity_bytes, then

text

    rows_per_granule = index_granularity_bytes / average_row_size

The granule stays a constant number of bytes. The default index_granularity_bytes is 10 MB, so a granule is 10 MB of data whether its rows are 10 bytes wide or 10 KB wide.

Why does that matter? Because a granule is the unit of skipping. If granules were a fixed 8192 rows, then a table of 1 KB rows would have 8 MB granules (fine), but a table of 100 KB rows would have 800 MB granules (useless — you can’t skip anything smaller than 800 MB). Sizing in bytes makes the granule a predictable, bounded amount of IO, and therefore a predictable, bounded amount of waste when you have to read a granule that does contain matches.

The price is that the row count of a granule is no longer constant, so it has to be remembered. The adaptive granularity object stores partial sums:

cpp
// src/Storages/MergeTree/MergeTreeIndexGranularityAdaptive.h:9
/// Class that stores adaptive index granularity.
/// Inside it contains vector of partial sums of rows after mark:
/// |-----|---|----|----|
/// |  5  | 8 | 12 | 16 |
class MergeTreeIndexGranularityAdaptive final : public MergeTreeIndexGranularity

One size_t per mark, and the row count of any mark is a subtraction. The alternative — a constant number of rows per granule — is available as use_const_adaptive_granularity, and its setting description explains the trade-off exactly:

cpp
// src/Storages/MergeTree/MergeTreeSettings.cpp:2174
    DECLARE(Bool, use_const_adaptive_granularity, false, R"(
Non-const adaptive granularity (the default, `index_granularity_bytes` is not `0`) keeps
granules at a constant size in bytes, so their row count varies: for every
written block, rows per granule is `index_granularity_bytes` divided by the
average size of a row in that block, capped at `index_granularity`. Because it differs
from granule to granule, the row count of every granule in the part has to be kept in
memory, 8 bytes each, which on large tables adds up to tens of gigabytes.

“Tens of gigabytes” — that’s the cost of the byte-granularity guarantee, and it’s the reason the constant-row variant exists at all. On a table with 100 million parts × 100 marks each, 8 bytes per mark is 80 GB of pure bookkeeping.

The marks themselves are appended as the block is written:

cpp
// src/Storages/MergeTree/MergeTreeIndexGranularity.cpp:162
void fillIndexGranularityForWidePart(
    MergeTreeIndexGranularity & index_granularity, size_t index_offset, size_t index_granularity_for_block, size_t rows_in_block)
{
    for (size_t current_row = index_offset; current_row < rows_in_block; current_row += index_granularity_for_block)
        index_granularity.appendMark(index_granularity_for_block);
}

A Wide part gets exactly index_granularity_for_block rows per mark. A Compact part, where all columns share one file, has to be more careful:

cpp
// src/Storages/MergeTree/MergeTreeIndexGranularity.cpp:169
void fillIndexGranularityForCompactPart(
    MergeTreeIndexGranularity & index_granularity, size_t index_offset, size_t index_granularity_for_block, size_t rows_in_block)
{
    for (size_t current_row = index_offset; current_row < rows_in_block; current_row += index_granularity_for_block)
    {
        size_t rows_left_in_block = rows_in_block - current_row;

        /// Try to extend last granule if block is large enough
        ///  or it isn't first in granule (index_offset != 0).
        if (rows_left_in_block < index_granularity_for_block &&
            (rows_in_block >= index_granularity_for_block || index_offset != 0))
        {
            // If enough rows are left, create a new granule. Otherwise, extend previous granule.
            // So, real size of granule differs from index_granularity_for_block not more than 50%.
            if (rows_left_in_block * 2 >= index_granularity_for_block)
                index_granularity.appendMark(rows_left_in_block);
            else
                index_granularity.addRowsToLastMark(rows_left_in_block);
        }
        else
        {
            index_granularity.appendMark(index_granularity_for_block);
        }
    }
}

The comment “real size of granule differs from index_granularity_for_block not more than 50%” is the invariant: a short tail is either given its own granule (if it’s at least half a granule) or merged into the previous one.

Marks: where in the file does each granule start?

A granule is a range of rows. To read it, you need to know where in the compressed .bin file its rows live. That’s the mark:

cpp
// src/Formats/MarkInCompressedFile.h:14
/** Mark is the position in the compressed file. The compressed file consists of adjacent compressed blocks.
  * Mark is a tuple - the offset in the file to the start of the compressed block, the offset in the decompressed block to the start of the data.
  */
struct MarkInCompressedFile
{
    size_t offset_in_compressed_file;
    size_t offset_in_decompressed_block;

Two numbers, both size_t, so sixteen bytes per mark in the naive layout. For a part with 100 marks that’s nothing. For a table with 100 000 parts of 1 GB each (100 TB), 100 marks per part × 16 bytes × 100 000 parts = 160 MB of index — and that’s only if every mark of every column is resident.

Which is why the in-memory representation isn’t a struct array:

cpp
// src/Formats/MarkInCompressedFile.h:30
/**
 * In-memory representation of an array of marks.
 *
 * Uses an ad-hoc compression scheme that decreases memory usage while allowing
 * random access in O(1) time.
 * This is independent from the marks *file* format, which may be uncompressed
 * or use a different compression method.
 *
 * Typical memory usage:
 *  * ~3 bytes/mark for integer columns
 *  * ~5 bytes/mark for string columns
 *  * ~0.3 bytes/mark for trivial marks in auxiliary dict files of LowCardinality columns
 */
class MarksInCompressedFile

Three bytes per mark. How?

The trick is that marks are not random. The comment in the header spells out the regularities the compression exploits:

cpp
// src/Formats/MarkInCompressedFile.h:51
    /** We need to store a sequence of marks, each consisting of two 64-bit integers:
     * offset_in_compressed_file and offset_in_decompressed_block. We'll call them x and y for
     * convenience, since compression doesn't care what they mean. The compression exploits the
     * following regularities:
     *  * y is usually zero.
     *  * x usually increases steadily.
     *  * Differences between x values in nearby marks usually fit in much fewer than 64 bits.
     *
     * We split the sequence of marks into blocks, each containing MARKS_PER_BLOCK marks.
     * (Not to be confused with data blocks.)
     * For each mark, we store the difference [value] - [min value in the block], for each of the
     * two values in the mark. Each block specifies the number of bits to use for these differences
     * for all marks in this block.
     * The smaller the blocks the fewer bits are required, but the bigger the relative overhead of
     * block headers.
     *
     * Packed marks and block headers all live in one contiguous array.
     */

So: 256 marks per block. Per block, store the minimum x and y and the number of bits needed to represent the spread within the block. Then store every mark as a delta from the block minimum, in that many bits.

The block header computation:

cpp
// src/Formats/MarkInCompressedFile.cpp:122
void MarksInCompressedFile::Builder::flushBlock(const MarkInCompressedFile * data, size_t count)
{
    chassert(count > 0 && count <= MARKS_PER_BLOCK);

    size_t block_idx = marks_flushed / MARKS_PER_BLOCK;
    BlockInfo & block = blocks[block_idx];
    block.bit_offset_in_packed_array = packed_bits;

    /// Compute block metadata: min values, bit widths.
    size_t max_x = 0;
    size_t max_y = 0;
    for (size_t i = 0; i < count; ++i)
    {
        block.min_x = std::min(block.min_x, data[i].offset_in_compressed_file);
        max_x = std::max(max_x, data[i].offset_in_compressed_file);
        block.min_y = std::min(block.min_y, data[i].offset_in_decompressed_block);
        max_y = std::max(max_y, data[i].offset_in_decompressed_block);
        block.trailing_zero_bits_in_y
            = std::min(block.trailing_zero_bits_in_y, static_cast<UInt8>(getTrailingZeroBits(data[i].offset_in_decompressed_block)));
    }

    block.bits_for_x = static_cast<UInt8>(sizeof(size_t) * 8 - getLeadingZeroBits(max_x - block.min_x));
    block.bits_for_y
        = static_cast<UInt8>(sizeof(size_t) * 8 - getLeadingZeroBits((max_y - block.min_y) >> block.trailing_zero_bits_in_y));

Two ideas in six lines.

Delta encoding per block. bits_for_x is the number of bits needed to represent the range of x values inside the block, not the magnitude of x itself. If a block of 256 marks spans 64 KB of compressed file, that’s 19 bits per mark, not 64.

Trailing-zero stripping for y. y is the offset inside the decompressed block, and it’s usually zero — a granule normally starts at the beginning of a compressed block. The code computes the number of trailing zero bits common to all the y values in the block and shifts them all right by that amount before packing. For a block where every y is zero, the shift is 63 and bits_for_y becomes zero: the y coordinate costs no bits at all.

The write path, showing both encodings:

cpp
// src/Formats/MarkInCompressedFile.cpp:153
    /// Write bit-packed deltas.
    size_t bit_offset = packed_bits;
    for (size_t i = 0; i < count; ++i)
    {
        writeBitsPacked64(packed.data(), bit_offset, data[i].offset_in_compressed_file - block.min_x);
        writeBitsPacked64(
            packed.data(),
            bit_offset + block.bits_for_x,
            (data[i].offset_in_decompressed_block - block.min_y) >> block.trailing_zero_bits_in_y);
        bit_offset += block.bits_for_x + block.bits_for_y;
    }

And the read path, which has to be O(1) — a mark lookup happens for every granule the reader touches:

cpp
// src/Formats/MarkInCompressedFile.cpp:47
std::tuple<const MarksInCompressedFile::BlockInfo *, size_t> MarksInCompressedFile::lookUpMark(size_t idx) const
{
    size_t block_idx = idx / MARKS_PER_BLOCK;
    const BlockInfo & block = blocks[block_idx];
    size_t offset = block.bit_offset_in_packed_array + (idx - block_idx * MARKS_PER_BLOCK) * (block.bits_for_x + block.bits_for_y);
    return {&block, offset};
}

Divide by 256 to find the block header, then a shift-and-mask to find the mark inside it. That’s the whole random-access structure: one array division and one multiply. Compare that to a compressed list of marks, which would need a binary search.

Where do the marks come from at write time?

The mark is written when the compressed block is flushed, so it’s simply the state of the hashing/compression stream at that moment:

cpp
// src/Storages/MergeTree/MergeTreeDataPartWriterOnDisk.cpp:351
                    MarkInCompressedFile mark{stream->plain_hashing.count(), stream->compressed_hashing.offset()};

plain_hashing.count() is the number of uncompressed bytes written so far — that’s y, the offset inside the decompressed block. And compressed_hashing.offset() is the number of compressed bytes written so far — that’s x, the offset of the compressed block in the file.

The mark cache

Marks are read from .mrk files and cached in a global LRU keyed by the file path:

cpp
// src/Storages/MergeTree/MergeTreeMarksLoader.cpp:313
    if (mark_cache)
    {
        auto key = MarkCache::hash(data_part_storage->getDiskName() + ":" + (fs::path(data_part_storage->getFullPath()) / mrk_path).string());

        if (save_marks_in_cache)
        {
            auto callback = [this] { return loadMarksImpl(); };
            loaded_marks = mark_cache->getOrSet(key, callback);
        }
        else
        {
            loaded_marks = mark_cache->getWithoutMetrics(key);
            if (!loaded_marks)
                loaded_marks = loadMarksImpl();
        }
    }

Note the two paths. getOrSet records hits and misses and inserts the loaded marks into the cache. getWithoutMetrics only looks: it’s used when the marks are wanted for a merge or a mutation, which shouldn’t evict the query’s working set or pollute the cache statistics.

That’s a small but real piece of cache hygiene — background work must not steal the cache from foreground queries.

The cache itself weights each entry by its compressed size plus a fixed overhead:

cpp
// src/Storages/MergeTree/MarkCache.h:23
/// Estimate of number of bytes in cache for marks.
struct MarksWeightFunction
{
    /// We spent additional bytes on key in hashmap, linked lists, shared pointers, etc ...
    static constexpr size_t MARK_CACHE_OVERHEAD = 128;

    size_t operator()(const MarksInCompressedFile & marks) const
    {
        return marks.approximateMemoryUsage() + MARK_CACHE_OVERHEAD;
    }
};

The 128-byte constant is the per-entry overhead of the hash map node, the list node, the shared pointer, and the MarksInCompressedFile object itself. For a part with 100 marks, the compressed marks are ~300 bytes and the overhead is 128 — so the accounting is honest about the fact that the bookkeeping dominates for small parts.

The primary key index: one key value per granule

The marks tell you where the bytes are. The primary key index tells you what’s in them. It’s a separate file, primary.idx, containing the sorting key values of the first row of every granule:

cpp
// src/Storages/MergeTree/IMergeTreeDataPart.cpp:1935
std::shared_ptr<IMergeTreeDataPart::Index> IMergeTreeDataPart::loadIndex() const
{
    auto component_guard = Coordination::setCurrentComponent("IMergeTreeDataPart::loadIndex");
    /// Memory for index must not be accounted as memory usage for query, because it belongs to a table.
    MemoryTrackerBlockerInThread temporarily_disable_memory_tracker;

and the loop that reads it is the whole format — marks_count rows of key_size values, serialized one after another:

cpp
// src/Storages/MergeTree/IMergeTreeDataPart.cpp:1972
    FormatSettings format_settings;
    for (size_t i = 0; i < marks_count; ++i)
    {
        for (size_t j = 0; j < key_size; ++j)
            key_serializations[j]->deserializeBinary(*loaded_index[j], *index_file, format_settings);
    }

marks_count rows of key_size values, serialized one after another. The in-memory form is a set of ColumnPtrs — one column per key column, each holding marks_count values — which is exactly the layout a KeyCondition wants to evaluate a predicate against.

The trimming trick

Now the interesting part. The primary key may be (a, b, c). If a is almost constant within a part — say, a low-cardinality column — then keeping b and c in memory is a waste. A query filtering on b can’t be answered from the index anyway, because a doesn’t narrow anything down. So the index is trimmed:

cpp
// src/Storages/MergeTree/IMergeTreeDataPart.cpp:1895
void IMergeTreeDataPart::optimizeIndexColumns(size_t marks_count, Columns & index_columns) const
{
    if (marks_count == 0)
    {
        chassert(isEmpty());
        return;
    }

    /// Do not optimize index for patch parts because patch parts
    /// use manual index analysis which requires all index columns.
    if (info.isPatch())
        return;

    size_t key_size = index_columns.size();
    Float64 ratio_to_drop_suffix_columns = static_cast<double>((*storage.getSettings())[MergeTreeSetting::primary_key_ratio_of_unique_prefix_values_to_skip_suffix_columns]);

    /// Cut useless suffix columns, if necessary.
    if (key_size > 1 && ratio_to_drop_suffix_columns > 0 && ratio_to_drop_suffix_columns < 1)
    {
        for (size_t j = 0; j < key_size - 1; ++j)
        {
            size_t num_changes = 0;
            for (size_t i = 1; i < marks_count; ++i)
            {
                if (0 != index_columns[j]->compareAt(i, i - 1, *index_columns[j], 0))
                    ++num_changes;
            }

            if (static_cast<Float64>(num_changes) / static_cast<Float64>(marks_count) >= ratio_to_drop_suffix_columns)
            {
                key_size = j + 1;
                index_columns.resize(key_size);
                break;
            }
        }

The rule: while the fraction of granules in which key column j changes is at least primary_key_ratio_of_unique_prefix_values_to_skip_suffix_columns (default 0.9), column j is informative, so keep it and move on. The first column that changes in fewer than 90% of granules is “nearly constant” within this part — the part is probably all one value of it — and then everything after it is dropped.

This is a per-part decision. A part that covers one day of data might have a constant country column and a varying user_id; the index keeps country and drops user_id. Another part, spanning many countries, keeps both.

The consequence is that index analysis must know which columns are actually available — and the code accounts for it, treating the missing suffix columns as “constant over the whole universe”, which relaxes the analysis to a safe over-approximation.

The primary index cache

For very large tables, keeping every part’s primary index in memory isn’t possible, so it can be cached in an LRU instead:

cpp
// src/Storages/MergeTree/PrimaryIndexCache.h:29
/** Cache of primary index for MergeTree tables.
  * Primary index is a list of columns from primary key
  * that store first row for each granule of data part.
  */
class PrimaryIndexCache : public CacheBase<UInt128, PrimaryIndex, UInt128TrivialHash, PrimaryIndexWeightFunction>

and the part consults it lazily:

cpp
// src/Storages/MergeTree/IMergeTreeDataPart.cpp:706
IMergeTreeDataPart::IndexPtr IMergeTreeDataPart::getIndex() const
{
    std::scoped_lock lock(index_mutex);

    if (index)
        return index;

    if (auto index_cache = storage.getPrimaryIndexCache())
        return loadIndexToCache(*index_cache);

    index = loadIndex();
    return index;
}

with the key being the disk name plus the part’s path, so that two parts with the same name on different disks don’t collide:

cpp
// src/Storages/MergeTree/IMergeTreeDataPart.cpp:726
IMergeTreeDataPart::IndexPtr IMergeTreeDataPart::loadIndexToCache(PrimaryIndexCache & index_cache) const
{
    auto key = PrimaryIndexCache::hash(getDataPartStorage().getDiskName() + ":" + getRelativePathOfActivePart());
    auto callback = [this] { return loadIndex(); };
    return index_cache.getOrSet(key, callback);
}

Now the payoff: two different search algorithms

With marks and the primary index in hand, a query has to answer “which granules can contain a matching row?”. ClickHouse has two algorithms for this, and it picks between them based on the shape of the predicate.

The decision point is whether the predicate describes a continuous range of the sorting key:

cpp
// src/Storages/MergeTree/MergeTreeDataSelectExecutor.cpp:2705
    bool key_condition_exact_range = !key_condition_useful || key_condition.matchesExactContinuousRange();
    bool part_offset_condition_exact_range = !part_offset_condition_useful || part_offset_condition->matchesExactContinuousRange();
    bool total_offset_condition_exact_range = !total_offset_condition_useful || total_offset_condition->matchesExactContinuousRange();
    const String & part_name = part->isProjectionPart() ? fmt::format("{}.{}", part->name, part->getParentPart()->name) : part->name;

    if (!key_condition_exact_range || !part_offset_condition_exact_range || !total_offset_condition_exact_range)
    {
        // Do exclusion search, where we drop ranges that do not match

Algorithm 1: binary search (continuous range)

If the predicate describes a single continuous interval of the sorting key — WHERE key >= 100 AND key < 200 — then the matching granules form a contiguous range in the index, and two binary searches find its boundaries:

cpp
// src/Storages/MergeTree/MergeTreeDataSelectExecutor.cpp:2801
            /// Invariant: !check_in_range(part_range.begin..searched_left).can_be_true
            ///             check_in_range(part_range.begin..searched_right).can_be_true
            /// (part_range.end + 1 is a sentinel out-of-bounds index, such that by definition
            ///  check_in_range(x..part_range.end+1).can_be_true is true. The binary search will never
            ///  actually call check_in_range with this out-of-bounds index.)
            /// If the condition is not true anywhere, we'll end up with searched_left == part_range.end.
            size_t searched_left = part_range.begin;
            size_t searched_right = part_range.end + 1;

            while (searched_left + 1 < searched_right)
            {
                const size_t middle = (searched_left + searched_right) / 2;
                MarkRange range(0, middle);
                if (check_in_range(range, BoolMask::consider_only_can_be_true).can_be_true)
                    searched_right = middle;
                else
                    searched_left = middle;
                ++steps;
            }
            result_range.begin = searched_left;
            LOG_TEST(log, "Found (LEFT) boundary mark: {}", searched_left);

check_in_range(0, middle) asks: “could any row in granules [0, middle) match?” The KeyCondition evaluates the predicate against the index values at the two ends of the range and the monotonicity of the key columns. Because the key is sorted, the answer is monotone in middle, so binary search is valid. O(log n) index checks for the whole part.

Algorithm 2: generic exclusion search (everything else)

Now consider WHERE key2 = 5 where key2 is the second column of the sorting key, or WHERE key = 5 OR key = 900000. The matching granules are not contiguous, so a binary search can’t be used.

ClickHouse falls back to an exclusion search: split the mark range recursively, drop the parts that cannot match.

cpp
// src/Storages/MergeTree/GenericExclusionSearch.cpp:61
void searchUnlimited(
    const MarkRanges & initial_ranges,
    const MarkRangeCheck & check_in_range,
    const GenericExclusionSearchSettings & search_settings,
    bool collect_exact_ranges,
    GenericExclusionSearchResult & result)
{
    for (const auto & initial_range : initial_ranges)
    {
        std::vector<MarkRange> ranges_stack = {initial_range};
        while (!ranges_stack.empty())
        {
            MarkRange range = ranges_stack.back();
            ranges_stack.pop_back();

            ++result.num_steps;

            BoolMask mask = check_in_range(range);

            if (!mask.can_be_true)
                continue;

            bool exact = !mask.can_be_false;
            if (exact || range.end == range.begin + 1)
            {
                appendWithMaxGap(result.ranges, range, search_settings.min_marks_for_seek);

                /// Unlike `ranges`, exact ranges must never absorb the gap between two accepted
                /// ranges: every mark of an exact range has to fully match the condition, while the
                /// skipped marks in between do not.
                if (collect_exact_ranges && exact)
                    appendWithMaxGap(result.exact_ranges, range, 0);
            }
            else
            {
                splitRange(range, search_settings.coarse_index_granularity, [&](MarkRange subrange) { ranges_stack.push_back(subrange); });
            }
        }
    }
}

This is a depth-first search over mark ranges. The check returns a BoolMask with two bits: can_be_true and can_be_false.

!can_be_true → the whole range cannot match → drop it.
!can_be_false → every row in the range matches → keep it whole.
otherwise → the range is a mixture → split it into merge_tree_coarse_index_granularity (default 8) subranges and recurse.

Splitting into 8 rather than 2 is deliberate. It’s a breadth-ish compromise: splitting in half is the classic binary split, but each split costs one check_in_range call, and each check isn’t free — it evaluates a KeyCondition against the index columns at the range boundaries. Eight subranges per step means the search converges in about log_8(n) steps while doing 8× the work per step.

The step budget

The unlimited search has no bound. A pathological predicate could make it check thousands of ranges, so there’s a budget:

cpp
// src/Storages/MergeTree/GenericExclusionSearch.cpp:119
void searchLimited(
    const MarkRanges & initial_ranges,
    const MarkRangeCheck & check_in_range,
    const GenericExclusionSearchSettings & search_settings,
    bool collect_exact_ranges,
    GenericExclusionSearchResult & result)
{
    std::vector<MarkRange> heap_storage(initial_ranges.begin(), initial_ranges.end());
    std::priority_queue<MarkRange, std::vector<MarkRange>, LessBySize> queue(LessBySize{}, std::move(heap_storage));

    /// Ranges are accepted out of spatial order, so they are collected raw and merged after sorting.
    std::vector<MarkRange> accepted;
    std::vector<MarkRange> accepted_exact;

    while (!queue.empty())
    {
        MarkRange range = queue.top();
        queue.pop();

        ++result.num_steps;

        BoolMask mask = check_in_range(range);

        if (!mask.can_be_true)
            continue;

        bool exact = !mask.can_be_false;
        if (exact || range.end == range.begin + 1)
        {
            accepted.push_back(range);
            if (collect_exact_ranges && exact)
                accepted_exact.push_back(range);
            continue;
        }

        if (result.num_steps + queue.size() > search_settings.max_steps)
        {
            result.reached_step_limit = true;
            accepted.push_back(range);
            continue;
        }

        splitRange(range, search_settings.coarse_index_granularity, [&](MarkRange subrange) { queue.push(subrange); });
    }

Two things change relative to the unlimited version.

A priority queue, largest range first. The budget is spent where it buys the most: splitting a huge range is what removes the most granules, so the biggest range is examined first. The comparator is explicit:

cpp
// src/Storages/MergeTree/GenericExclusionSearch.cpp:102
/// Orders the queue of the step-limited search: the largest range comes first.
struct LessBySize
{
    bool operator()(const MarkRange & lhs, const MarkRange & rhs) const
    {
        size_t lhs_size = lhs.end - lhs.begin;
        size_t rhs_size = rhs.end - rhs.begin;
        return std::tie(lhs_size, rhs.begin) < std::tie(rhs_size, lhs.begin);
    }
};

When the budget runs out, the range is accepted whole. This is the important bit: the search never returns an incorrect answer. When result.num_steps + queue.size() > max_steps, the range is pushed into accepted as-is — meaning “we don’t know, so read it”. The result is a superset of the true matching granules, so the query is correct; it just reads more data than an unlimited search would have.

That’s what the setting says:

cpp
// src/Core/Settings.cpp:1936
    DECLARE(UInt64, merge_tree_generic_exclusion_search_max_steps, 0, R"(
When a filter cannot be evaluated as a single continuous range of the primary key, for example when it uses key columns other than the first one, ClickHouse runs an iterative generic exclusion search algorithm over the index marks. The same algorithm is used for the analysis of the text index. This setting limits the number of steps (index checks) the algorithm spends on each data part.

The budget is spent on the largest remaining mark ranges first. When it is exhausted, the ranges that were not fully analyzed are accepted as a whole, so the query stays correct but may read more granules than an unlimited search would select. A lower budget speeds up index analysis at the cost of reading more data. The limit is approximate rather than a strict cap on the analysis cost: the search can exceed it by roughly one round of splitting, and when the part is already divided into many ranges (for example, by the query condition cache), each of them is checked at least once regardless of the limit.

The default of 0 means unlimited steps. So the default behaviour is exact and unbounded; the budget is an escape hatch for pathological cases.

The seek heuristic

One more knob, and it’s about IO, not about correctness. When two accepted ranges are separated by a small gap of marks, it’s cheaper to read the gap sequentially than to seek past it. appendWithMaxGap merges the two ranges when the gap is at most max_gap marks wide.

The gap threshold comes from merge_tree_min_rows_for_seek and merge_tree_min_bytes_for_seek, converted into marks by the granularity of the part. Both default to 0, i.e. “never bridge a gap” — but on a spinning disk or an object store with a high per-request cost, setting them turns “read 8 KB from here, seek, read 8 KB from there” into “read 40 KB contiguously”.

Note the asymmetry that the comment points out: exact_ranges are merged with max_gap = 0, always. An exact range is a range where every row matches, and bridging a gap into it would claim that the skipped marks match too — which is false. So the gap-bridging optimization applies only to the “may match” ranges, never to the “definitely matches” ones.

Putting it together

text
  part on disk
  ┌───────────────────────────────────────────────────────────────┐
  │ granule 0        granule 1        granule 2        granule 3 │
  │ rows 0..8191     rows 8192..16383 rows ...         rows ...   │
  └───────────────────────────────────────────────────────────────┘
      │                 │                 │                 │
      ▼                 ▼                 ▼                 ▼
    marks:  (x0,y0)     (x1,y1)          (x2,y2)          (x3,y3)
           bit-packed, ~3 bytes each, one per column file
      │
      ▼
  primary.idx:  key values of the FIRST ROW of each granule
      │
      ▼
  KeyCondition.checkInRange(...)
      │
      ├── predicate is a continuous key range  →  binary search  (2·log₂ n checks)
      │
      └── predicate is anything else            →  exclusion search (recursive, budgeted)
      │
      ▼
  MarkRanges: the granules that must be read

What this buys you, and what it costs

It buys you a scan that’s proportional to the data you asked for, not to the data you stored. A SELECT with a range predicate on a sorted key reads roughly the granules that overlap the range, plus one granule of granularity on each side.

It buys you an index that fits in memory. Three bytes per mark, and the primary key index trimmed to the columns that can actually narrow things down. Without those two tricks, a 10 TB table would need tens of gigabytes of index.

It costs you a fixed granularity of waste. A predicate that matches a single row still reads a whole granule — 10 MB by default. This is the central trade of the whole design, and it’s why index_granularity_bytes is a setting you may want to lower for a table with a very selective predicate and small rows.

It costs you an in-memory structure that has to be built and kept. The primary index is loaded per part (or cached), and the marks are loaded per column file that the query touches. Both are cached, and both have their own LRU, but the first query against a cold part pays for them.

It costs you complexity in the analysis. Two algorithms, a budget, a trimming heuristic that makes the analysis conservative in some cases, and the requirement that the analysis be sound (never skip a granule that could match) even when it isn’t complete.

Seeing it in action

The profile events tell you which algorithm ran:

sql
SELECT event, value
FROM system.events
WHERE event IN (
    'IndexBinarySearchAlgorithm',
    'IndexGenericExclusionSearchAlgorithm',
    'IndexGenericExclusionSearchStepLimitReached',
    'FilteringMarksWithPrimaryKeyProcessedMarks',
    'FilteringMarksWithPrimaryKey'
);

FilteringMarksWithPrimaryKeyProcessedMarks is the number of marks examined. FilteringMarksWithPrimaryKey is the number of parts where the primary key was used at all. The ratio between the two, and the ratio of marks read to marks examined, is your “how selective is my index” metric.

And the parts themselves report the granularity they were written with:

sql
SELECT
    name,
    rows,
    marks,
    round(rows / marks) AS rows_per_mark,
    formatReadableSize(bytes_on_disk) AS size
FROM system.parts
WHERE active AND rows > 0
ORDER BY marks DESC
LIMIT 10;

A rows_per_mark far below 8192 means the table has fat rows and the byte-based granularity kicked in. A rows_per_mark of exactly 8192 means use_const_adaptive_granularity is on, or index_granularity_bytes was 0 when the part was written.

Wrapping up

The one thing to remember: a MergeTree granule is the unit of skipping, and everything else — marks, the primary index, the two search algorithms — exists to answer one question about it: can this granule possibly match?

What to go do about it: if a query on your table isn’t skipping granules, look at the shape of the predicate before you touch anything else. A predicate on the first sorting-key column with a continuous range gets the fast binary search. A predicate on a later column, or an OR across values, gets the recursive exclusion search — and there you should be watching IndexGenericExclusionSearchStepLimitReached.

If you see that event firing, the search ran out of budget and fell back to reading more granules than it needed to. Either raise merge_tree_generic_exclusion_search_max_steps, or — better — add a projected column and query that instead.