ClickHouse Chooses What Goes into PREWHERE by Cost per Rejected Row

TL;DR: Every conjunct of your WHERE is scored by bytes read per rejected row — bytes_per_row × total_rows / rejected_rows — and the best-scoring ones are moved into PREWHERE, which is evaluated during the read. The PREWHERE is then split into several read steps, so a step that rejects 99 % of the rows lets the next step read its columns for 1 % of the rows.

Here is the shape of a MergeTree read.

sql
SELECT user_id, event_type, payload FROM events WHERE user_id = 42;

user_id is narrow, event_type is narrow, payload is a wide String. A naive execution reads all three columns for every row in the table, then throws away 99.99 % of them. A PREWHERE execution reads user_id for every row, keeps 1 % of them, and reads event_type and payload only for those.

That is the whole idea of PREWHERE, and it is a columnar idea: the filter is pushed down far enough that it can gate the reading of the other columns.

The hard part is deciding which conditions to move. A condition is only worth moving if:

it can be evaluated during the read at all (no arrayJoin, no GLOBAL IN),
the columns it needs are cheap to read,
and it actually rejects a lot of rows.

ClickHouse scores this with a single number — bytes per rejected row — and that number is one of the nicer pieces of cost modelling in the codebase.

Where the decision is made

The transformation happens in the query-plan optimizer, not in the storage engine:

cpp
// src/Processors/QueryPlan/Optimizations/optimizePrewhere.cpp:236
void optimizePrewhere(QueryPlan::Node & parent_node, const bool remove_unused_columns, const bool suppress_for_vector_search)
{
    /// Assume that there are at least 2 nodes:
    /// 1. FilterNode - parent_node
    /// 2. SourceStepWithFilterNode - child_node

The pattern is a FilterStep sitting directly on top of a read step. The optimizer peels the filter’s conjuncts, scores them, moves the good ones into the read step’s PrewhereInfo, and leaves the rest as a normal filter above.

The whole thing is controlled by four settings, all on by default:

cpp
// src/Core/Settings.cpp:1165
    DECLARE(Bool, move_all_conditions_to_prewhere, true, R"(
Move all viable conditions from WHERE to PREWHERE
)", 0) \
    DECLARE(Bool, enable_multiple_prewhere_read_steps, true, R"(
Move more conditions from WHERE to PREWHERE and do reads from disk and filtering in multiple steps if there are multiple conditions combined with AND
)", 0) \
    DECLARE(Bool, move_primary_key_columns_to_end_of_prewhere, true, R"(
Move PREWHERE conditions containing primary key columns to the end of AND chain. It is likely that these conditions are taken into account during primary key analysis and thus will not contribute a lot to PREWHERE filtering.
)", 0) \
    DECLARE(Bool, allow_reorder_prewhere_conditions, true, R"(
When moving conditions from WHERE to PREWHERE, allow reordering them to optimize filtering
)", 0, \

The third one is the most interesting and the least obvious: a condition on a primary key column has probably already been used by the primary index to skip granules, so evaluating it again during the read is nearly free and nearly useless — it should go last, after the conditions that actually filter rows.

Step 1: splitting the WHERE into conjuncts

The filter expression is flattened into its top-level AND chain, and each conjunct is analysed separately:

cpp
// src/Storages/MergeTree/MergeTreeWhereOptimizer.cpp:400
void MergeTreeWhereOptimizer::analyzeImpl(Conditions & res, const RPNBuilderTreeNode & node, const WhereOptimizerContext & where_optimizer_context, std::set<Int64> & pk_positions) const
{
    /// Flatten the top-level AND chain into individual conjuncts.
    std::vector<RPNBuilderTreeNode> conjuncts;
    collectConjuncts(node, conjuncts);

Each conjunct gets a set of referenced columns and a verdict on whether it is viable — that is, whether it can move to PREWHERE at all:

cpp
// src/Storages/MergeTree/MergeTreeWhereOptimizer.cpp:438
        /// Is it possible to use primary index for this condition? For conditions like `lower(country) = 'xx'`, may_use_primary_index will be false.
        info.viable =
            !info.has_invalid_column
            /// Condition depends on some column. Constant expressions are not moved.
            && !info.columns.empty()
            && !cannotBeMoved(conjunct, where_optimizer_context)
            /// When use final, do not take into consideration the conditions with non-sorting keys. Because final select
            /// need to use all sorting keys, it will cause correctness issues if we filter other columns before final merge.
            && (!where_optimizer_context.is_final || isDeterministicExpressionOverSortingKey(conjunct, where_optimizer_context.context))
            /// Some identifiers can unable to support PREWHERE (usually because of different types in Merge engine)
            && columnsSupportPrewhere(info.columns)
            /// Do not move conditions involving all queried columns,
            /// unless the condition can be used as a string filter during the scan:
            /// then it is beneficial on its own, because the reader skips copying the non-matching values.
            && (info.columns.size() < queried_columns.size()
                || (where_optimizer_context.apply_string_filters_during_scan && isConditionSuitableForStringValueFilter(conjunct, where_optimizer_context)));

Read the last clause carefully: a condition that mentions every queried column is normally pointless to move, because the reader has to read all the columns anyway. The exception is a substring search on a String column, where the reader can skip copying the non-matching values during deserialisation — so it is worth moving even though it touches everything.

Grouping by column set

Conditions that need the same columns are grouped and scored together, because their combined selectivity is what matters, and because the reader will have to read those columns once anyway:

cpp
// src/Storages/MergeTree/MergeTreeWhereOptimizer.cpp:458
    /// Group viable conjuncts by their required storage column set so same-column conditions
    /// are treated as a single unit and their combined selectivity can be estimated.

The grouping is by storage column, not by the exact column name, so that subcolumns of the same column (map.key_k0 and map.key_k1) stay together.

Step 2: the cost model

Here is the number. For a condition that rejects rejected_rows rows out of total_rows, the cost is the bytes that have to be read per rejected row:

cpp
// src/Storages/MergeTree/MergeTreeWhereOptimizer.cpp:563
            /// Combine I/O cost with selectivity using the classic conjunctive filter ordering rule:
            /// sort by cost / (1 - selectivity), i.e. cost per rejected row.
            const double rejected_rows = static_cast<double>(total_rows) - static_cast<double>(cond.estimated_row_count);
            if (total_rows == 0)
                /// No statistics: fall back to pure I/O cost.
                cond.bytes_per_rejected_row = static_cast<double>(cond.columns_size);
            else if (rejected_rows <= 0)
                /// Rejects no rows, so it is useless in PREWHERE regardless of its cost: schedule it last.
                cond.bytes_per_rejected_row = std::numeric_limits<double>::infinity();
            else if (total_size_of_queried_columns == 0)
                /// Nothing measured (compact parts): the type estimate is too coarse to outrank
                /// selectivity, e.g. `Nullable(Int64)` would beat `Int64` on the null byte.
                cond.bytes_per_rejected_row = static_cast<double>(cond.estimated_row_count);
            else
                cond.bytes_per_rejected_row = approximateBytesPerRow(cond.table_columns) * static_cast<double>(total_rows) / rejected_rows;

This is the classic “cost per rejected tuple” rule from the database literature (the Selinger-style ordering of conjunctive filters), and it is exactly the right metric for a columnar reader:

A cheap column that rejects many rows → few bytes per rejected row → evaluated first, because it lets the reader skip the expensive columns for most of the table.
An expensive column that rejects few rows → many bytes per rejected row → evaluated last, because the reader has to read a lot to save a little.

Note the three degenerate cases, which are all about not lying:

No statistics at all → fall back to the pure I/O cost of the condition’s columns.
A condition that rejects nothing → infinity, so it sorts last. There is no point paying to read a column early in order to reject zero rows.
Compact parts, where column sizes are not measurable → charge the estimated row count instead, so the metric stays comparable across conditions.

Where the byte estimate comes from

The per-column size is measured, not guessed, when the parts allow it:

cpp
// src/Storages/MergeTree/MergeTreeWhereOptimizer.cpp:747
double MergeTreeWhereOptimizer::approximateBytesPerRowAndColumn(const String & column) const
{
    chassert(total_rows > 0);

    if (auto it = column_sizes.find(column); it != column_sizes.end() && it->second != 0)
        return static_cast<double>(it->second) / static_cast<double>(total_rows);

and only guessed when it cannot be measured:

cpp
// src/Storages/MergeTree/MergeTreeWhereOptimizer.cpp:66
/// Uncompressed, unlike the stored column sizes, so it over-charges - the safe direction for a
/// column whose real cost is unknown.
double approximateBytesPerValueForType(const IDataType & type)
{
    if (type.haveMaximumSizeOfValue())
        return static_cast<double>(type.getMaximumSizeOfValueInMemory());
    if (WhichDataType(type).isString())
        return default_bytes_per_string_value;
    return default_bytes_per_complex_value;
}

with default_bytes_per_string_value = 64 and default_bytes_per_complex_value = 128. Over-charging an unknown column is the safe direction: it makes the condition sort later, not earlier.

The rejection count

estimated_row_count — the number of rows that survive the condition — comes from the statistics-based selectivity estimator, when statistics are available:

cpp
// src/Storages/MergeTree/MergeTreeWhereOptimizer.cpp:547
            if (where_optimizer_context.use_statistics)
            {
                cond.good = true;
                cond.estimated_row_count = estimator->estimateRelationProfile(storage_metadata, cond.nodes).rows;
                LOG_DEBUG(log, "Condition group ({}) has estimated row count {}", cond.toString(), cond.estimated_row_count);
            }

Without statistics, the older heuristic takes over: a condition of the form column = N with |N| > 2 is assumed to be selective.

cpp
// src/Storages/MergeTree/MergeTreeWhereOptimizer.cpp:46
/// Conditions like "x = N" are considered good if abs(N) > threshold.
/// This is used to assume that condition is likely to have good selectivity.
constexpr auto threshold = 2;

Step 3: the ordering

The conditions are compared with a lexicographic tuple, and the tuple is where several independent rules are packed into one comparator:

cpp
// src/Storages/MergeTree/MergeTreeWhereOptimizer.h:123
        auto tuple() const
        {
            return std::make_tuple(
                !viable, !good, -min_position_in_primary_key, is_runtime_filter, bytes_per_rejected_row, table_columns.size());
        }

Reading it in order:

!viable — non-viable conditions sort last (and the loop stops there).
!good — conditions without a selectivity hint sort after those with one.
-min_position_in_primary_key — conditions touching a later primary key column come first, so primary-key conditions end up at the tail.
is_runtime_filter — a join runtime filter is known to pass every row, so it sorts last.
bytes_per_rejected_row — the real cost metric.
table_columns.size() — fewer columns first, as a tie-break.

The primary-key rule is not just “sort PK conditions last” — it is subtler, and the code explains why:

cpp
// src/Storages/MergeTree/MergeTreeWhereOptimizer.cpp:622
    /// E.g., if the primary key is (a, b, c) but the condition is a = 1 and c = 1,
    /// we should only put (a = 1) to the tail of PREWHERE,
    /// and treat (c = 1) as a normal column.

The point is that the primary index can only use a prefix of the sorting key. A condition on a = 1 (the first key column) is very likely already handled by the index; a condition on c = 1 (the third) is not, because the index cannot use c without a and b. So a = 1 goes to the tail and c = 1 stays where it is. The code computes the longest valid prefix:

cpp
// src/Storages/MergeTree/MergeTreeWhereOptimizer.cpp:625
    if (where_optimizer_context.move_primary_key_columns_to_end_of_prewhere)
    {
        Int64 min_valid_pk_pos = -1;
        for (auto pk_pos : pk_positions)
        {
            if (pk_pos != min_valid_pk_pos + 1)
                break;
            min_valid_pk_pos = pk_pos;
        }

Step 4: how much to move

Scoring is not enough — moving everything is not free either, because the PREWHERE columns are read for every row of the table. The optimizer stops once the moved conditions account for a reasonable share of the read:

cpp
// src/Storages/MergeTree/MergeTreeWhereOptimizer.cpp:681
    /// Move conditions unless the ratio of total_size_of_moved_conditions to the total_size_of_queried_columns is less than some threshold.
    while (!where_conditions.empty())
    {
        /// Move the best condition to PREWHERE if it is viable.
        auto it = std::min_element(where_conditions.begin(), where_conditions.end());

        if (!it->viable)
            break;

        if (!where_optimizer_context.move_all_conditions_to_prewhere)
        {
            bool moved_enough = false;
            if (total_size_of_queried_columns > 0)
            {
                /// If we know size of queried columns use it as threshold. 10% ratio is just a guess.
                moved_enough = total_size_of_moved_conditions > 0
                    && (total_size_of_moved_conditions + it->columns_size) * 10 > total_size_of_queried_columns;
            }
            else
            {
                /// Otherwise, use number of moved columns as a fallback.
                /// It can happen, if table has only compact parts. 25% ratio is just a guess.
                moved_enough = total_number_of_moved_columns > 0
                    && (total_number_of_moved_columns + it->table_columns.size()) * 4 > queried_columns.size();
            }

            if (moved_enough)
                break;
        }

The thresholds are honestly labelled: “10 % ratio is just a guess”, and 25 % of the columns when the byte sizes are not measurable (compact parts).

With move_all_conditions_to_prewhere = true (the default) this whole early-exit is skipped and everything viable moves.

Step 5: splitting PREWHERE into read steps

This is the part that makes PREWHERE more than “filter earlier”. The PREWHERE condition is an AND of several conjuncts, and each conjunct may need different columns. The reader can therefore split the read into several steps, each reading its own columns and filtering the block:

text
   granule of 8192 rows, columns: user_id | event_type | payload

   step 1: read user_id only  ──► filter user_id = 42   ──►   82 rows survive
   step 2: read event_type    ──► filter event_type = 'x' ──►   30 rows survive
   step 3: read payload       ──► (no more filters)      ──►   30 rows out

   bytes read: 8192*sizeof(user_id) + 82*sizeof(event_type) + 30*sizeof(payload)

The splitting logic is in MergeTreeSplitPrewhereIntoReadSteps.cpp, and its docstring is the design:

cpp
// src/Storages/MergeTree/MergeTreeSplitPrewhereIntoReadSteps.cpp:262
/// We want to build a sequence of steps that will compute parts of the prewhere condition.
/// Each step reads some new columns and computes some new expressions and a filter condition.
/// The last step computes the final filter condition and the remaining expressions that are required for the main query.
/// The goal of this is to, when it is possible, filter out many rows in early steps so that the remaining steps will
/// read less data from the storage.
/// NOTE: The result of executing the steps is exactly the same as if we would execute the original DAG in single step.

The grouping rule is “adjacent conditions that read the same physical columns”, and the word adjacent is load-bearing:

cpp
// src/Storages/MergeTree/MergeTreeSplitPrewhereIntoReadSteps.cpp:341
    /// Only adjacent conditions are merged to preserve the user's explicit PREWHERE evaluation order.
    /// Non-adjacent conditions on the same storage column are kept in separate steps even though this
    /// may cause redundant reads, because the user may have intentionally interleaved a guard predicate
    /// (e.g. `PREWHERE tags['safe'] != '' AND value > 0 AND toUInt64(tags['unsafe']) > 0` — the
    /// `value > 0` step must filter rows before evaluating the potentially-throwing conversion).

The user’s explicit PREWHERE order is a contract, and the splitter will not reorder it.

The throwing-condition guard

That example — toUInt64(tags['unsafe']) — is the reason for the may_throw machinery. If a condition can throw (a cast that can fail, a function that can fail), it must not be evaluated on rows that a preceding filter would have rejected. The splitter tracks this per condition:

cpp
// src/Storages/MergeTree/MergeTreeSplitPrewhereIntoReadSteps.cpp:114
    /// Reuse the predicate that the short-circuit machinery uses to decide which nodes must be
    /// guarded (findLazyExecutedNodes in ExpressionActions.cpp). IExecutableFunction::canThrow
    /// delegates to it as well, through FunctionToExecutableFunctionAdaptor. It is imprecise in
    /// both directions: it reports true for merely expensive functions, and false for some
    /// functions that do throw while parsing row values (for example addDays(String, ...) via
    /// FunctionDateOrDateTimeAddInterval). There is no sound can-throw oracle in the tree yet,
    /// see the TODO on canThrow in IFunctionAdaptors.h.

and a group whose successor may throw is marked as “must materialise its filter”, so the filter is actually applied before the next step runs:

cpp
// src/Storages/MergeTree/MergeTreeSplitPrewhereIntoReadSteps.cpp:501
                /// A step that precedes a may_throw condition must materialize its filter, so that
                /// the throwing condition is not evaluated on the rows this step rejects.
                .need_filter = force_short_circuit_execution || groups_requiring_filtered_input.contains(step_index + 1),

Read-ahead of the same columns

There is one more optimisation: two steps that read the same storage column would normally deserialise it twice. The splitter can instead have the first step read it and pass it along:

cpp
// src/Storages/MergeTree/MergeTreeSplitPrewhereIntoReadSteps.cpp:358
    /// For every group, the index of the group whose step reads its columns. A group that was split
    /// from the previous one only because it may throw reads the same storage columns, so with
    /// `read_ahead_columns` its columns are read by the first step of that run and only the evaluation
    /// waits for the filter. Otherwise every such step would deserialize the same storage column again
    /// (for example a whole `Map` for each of its keys). Reading is safe only when the reader does not
    /// convert the column or fill it from a default expression, because that runs on the whole block
    /// before any filter, so the caller decides (see `MergeTreeReaderSettings::read_ahead_prewhere_columns`).

The read-column split itself

The final piece is in the block-reading utilities, where the read task’s column list is partitioned into “columns read by a PREWHERE step” and “columns read after PREWHERE”:

cpp
// src/Storages/MergeTree/MergeTreeBlockReadUtils.cpp:502
    auto add_step = [&](const PrewhereExprStep & step)
    {
        /// Computation results from previous steps might be used in the current step as well. In such a case these
        /// computed columns will be present in the current step inputs. They don't need to be read from the disk so
        /// exclude them from the list of columns to read. This filtering must be done before injecting required
        /// columns to avoid adding unnecessary columns or failing to find required columns that are computation
        /// results from previous steps.
        /// Example: step1: sin(a)>b, step2: sin(a)>c

and the accounting of “already known” columns:

cpp
// src/Storages/MergeTree/MergeTreeBlockReadUtils.cpp:536
        /// More columns could have been added, filter them as well by the list of columns from previous steps.
        Names columns_to_read_in_step;
        for (const auto & name : step_column_names)
        {
            if (columns_from_previous_steps.emplace(name).second)
                columns_to_read_in_step.push_back(name);
        }

        /// Add results of the step to the list of already "known" columns so that we don't read or compute them again.
        if (step.actions)
        {
            for (const auto & name : step.actions->getActionsDAG().getNames())
                columns_from_previous_steps.insert(name);
        }

        result.pre_columns.push_back(storage_snapshot->getColumnsByNames(options, columns_to_read_in_step));

and finally the columns that the main read needs, minus everything a PREWHERE step already read:

cpp
// src/Storages/MergeTree/MergeTreeBlockReadUtils.cpp:573
    /// Remove columns read in prewehere from the list of columns to read.
    Names post_column_names;
    for (const auto & name : column_to_read_after_prewhere)
    {
        if (!columns_from_previous_steps.contains(name))
            post_column_names.push_back(name);
    }

    result.columns = storage_snapshot->getColumnsByNames(options, post_column_names);

The read task then creates one reader per step, each with its own column list:

cpp
// src/Storages/MergeTree/MergeTreeReadTask.cpp:288
    for (const auto & pre_columns_per_step : read_info->task_columns.pre_columns)
    {

A worked example

sql
CREATE TABLE events
(
    user_id UInt32,
    event_type LowCardinality(String),
    ts DateTime,
    payload String
)
ENGINE = MergeTree
ORDER BY (ts, user_id);

sql
SELECT user_id, payload FROM events
WHERE user_id = 42
  AND event_type = 'purchase'
  AND ts > now() - INTERVAL 1 DAY;

What the optimizer does:

ts > now() - INTERVAL 1 DAY touches the first primary key column, so it goes to the tail of the PREWHERE chain — the primary index has probably already used it to skip granules.
user_id = 42 touches the second primary key column, so it is not a prefix-usable condition and stays a normal filter.
event_type = 'purchase' touches a LowCardinality(String) column, which is cheap to read.

The result is a two-step read: one step reads user_id (and event_type) for the whole granule, and the main read fetches payload only for the survivors.

Trade-offs

The metric is a heuristic with a clear shape. Bytes per rejected row is dimensionally correct — it is “how many bytes must I read to throw away one row” — and it is the standard rule for ordering conjunctive filters. It is not a model of the actual I/O: it ignores decompression cost, cache effects, and the fact that a LowCardinality(String) column is much cheaper to decompress than a String payload.

The thresholds are guesses, and the code says so. “10 % ratio is just a guess”, “25 % ratio is just a guess”, threshold = 2 for the “good condition” heuristic. They are heuristics with a decade of empirical tuning behind them, not derivable from first principles.

Statistics make the difference between a good plan and a bad one. Without statistics, the selectivity of a condition is unknown, the metric degenerates to “bytes per row”, and the ordering becomes “cheapest column first” — which is usually but not always right. With statistics, the metric is what it claims to be.

Splitting PREWHERE into steps is not free. Each step is a separate reader with its own decompression state, and each step boundary is a place where a condition’s semantics can be violated. The code is careful about the throwing-condition case and about the user’s explicit evaluation order, and those are the two places where a clever transformation would have produced wrong results.

The escape hatches.

sql
-- Turn the whole thing off.
SELECT * FROM events WHERE user_id = 42 SETTINGS optimize_move_to_prewhere = 0;

-- Keep the conditions in their original order.
SELECT * FROM events PREWHERE user_id = 42 AND event_type = 'purchase' SETTINGS allow_reorder_prewhere_conditions = 0;

-- Do it in one read step instead of several.
SELECT * FROM events WHERE user_id = 42 AND event_type = 'purchase'
SETTINGS enable_multiple_prewhere_read_steps = 0;

And to see where the conditions ended up:

sql
EXPLAIN actions = 1 SELECT * FROM events WHERE user_id = 42 AND event_type = 'purchase';

The plan shows a Prewhere filter line with the condition that was moved (and, in non-compact mode, the whole PREWHERE expression graph), plus the read step’s Output: list, which no longer contains the columns that only the PREWHERE needed.