ClickHouse Short-Circuits AND and OR with a Mask and a Deferred Column

TL;DR: SELECT ... WHERE expensive(a) AND cheap(b) should not parse a on the rows where b is already false. ClickHouse does this by deferring the expensive argument: at plan time the argument becomes a ColumnFunction — a thunk holding a function and its captured columns — and at run time the short-circuit function keeps a UInt8 mask of the rows it has not yet decided, filters the thunk’s captures down to those rows, and only then calls it.

SQL’s AND and OR are short-circuit operators: the classic reading is “evaluate the left operand; if it decides the answer, do not look at the right”. Row-at-a-time engines get this for free, because the interpreter evaluates one row and can simply stop.

ClickHouse is not a row-at-a-time engine. It evaluates a whole 65 409-row column at a time. There is no “row 4711 of column a” to skip to — the function expensive(a) takes a column and returns a column. So the naive implementation of expensive(a) AND cheap(b) is:

text
compute expensive(a)   -> 65 409 evaluations
compute cheap(b)       -> 65 409 evaluations
combine                -> 65 409 evaluations

and none of the first 65 409 expensive evaluations were necessary if cheap(b) is false for most rows.

ClickHouse’s answer is a two-part trick: defer the expensive argument into a deferred value, and filter it by a mask before finally executing it.

The setting

cpp
// src/Core/Settings.cpp:8437
    DECLARE(ShortCircuitFunctionEvaluation, short_circuit_function_evaluation, ShortCircuitFunctionEvaluation::ENABLE, R"(
Allows calculating the [if](/reference/functions/regular-functions/conditional-functions#if), [multiIf](/reference/functions/regular-functions/conditional-functions#multiIf), [and](/reference/functions/regular-functions/logical-functions#and), and [or](/reference/functions/regular-functions/logical-functions#or) functions according to a [short scheme](https://en.wikipedia.org/wiki/Short-circuit_evaluation). This helps optimize the execution of complex expressions in these functions and prevent possible exceptions (such as division by zero when it is not expected).

The three-valued enum is deliberately tiny:

cpp
// src/Core/ShortCircuitFunctionEvaluation.h:8
enum class ShortCircuitFunctionEvaluation : uint8_t
{
    ENABLE, // Use short-circuit function evaluation for functions that are suitable for it.
    FORCE_ENABLE, // Use short-circuit function evaluation for all functions.
    DISABLE, // Disable short-circuit function evaluation.
};

ENABLE only defers arguments that are worth deferring — those that can throw or are computationally heavy. FORCE_ENABLE defers everything. DISABLE turns the whole thing off.

Who declares itself short-circuit-able

The mechanism is opt-in per function. A function implements isShortCircuit and fills in a ShortCircuitSettings:

cpp
// src/Functions/IFunction.h:356
    struct ShortCircuitSettings
    {
        /// Should we enable lazy execution for the nth argument of short-circuit function?
        /// Example 1st argument: if(cond, then, else), we don't need to execute cond lazily.
        /// Example other arguments: 1st, 2nd, 3rd argument of dictGetOrDefault should always be calculated.
        UnorderedSetWithMemoryTracking<size_t> arguments_with_disabled_lazy_execution;

        /// Should we enable lazy execution for functions, that are common descendants of
        /// different short-circuit function arguments?
        /// Example 1: if (cond, expr1(..., expr, ...), expr2(..., expr, ...)), we don't need
        /// to execute expr lazily, because it's used in both branches.
        /// Example 2: and(expr1, expr2(..., expr, ...), expr3(..., expr, ...)), here we
        /// should enable lazy execution for expr, because it must be filtered by expr1.
        bool enable_lazy_execution_for_common_descendants_of_arguments{};
        /// Should we enable lazy execution without checking isSuitableForShortCircuitArgumentsExecution?
        /// Example: toTypeName(expr), even if expr contains functions that are not suitable for
        /// lazy execution (because of their simplicity), we shouldn't execute them at all.
        bool force_enable_lazy_execution{};
        /// Does the result of the function not depend on the order in which its arguments are executed,
        /// and can the function receive any of its arguments lazily? Example: and, or.
        /// Then `arguments_with_disabled_lazy_execution` is only a preference: if the argument listed there
        /// is heavy while another one is cheap, the cheap one is executed on all rows instead,
        /// and the function is free to execute its lazy arguments in any order,
        /// see `ExpressionActions` and `ShortCircuitArgumentStatistics`.
        bool arguments_are_commutative{};
    };

and and or are the interesting case, because they are commutative:

cpp
// src/Functions/FunctionsLogical.h:204
    bool isShortCircuit(ShortCircuitSettings & settings, size_t /*number_of_arguments*/) const override
    {
        settings.arguments_with_disabled_lazy_execution.insert(0);
        settings.enable_lazy_execution_for_common_descendants_of_arguments = true;
        settings.force_enable_lazy_execution = false;
        settings.arguments_are_commutative = true;
        return name == NameAnd::name || name == NameOr::name;
    }

and/or always evaluate argument 0 eagerly (it is the first one you see), but because the result does not depend on the order, the rest of the arguments may be evaluated in any order — and, crucially, each of them only on the rows that are still undecided.

if is different: the branches are not commutative, so the condition must be evaluated first and the branches are tied to it.

Plan time: deciding which nodes to defer

The analysis happens once, when the ExpressionActions is constructed — that is, at plan time, not per block:

cpp
// src/Interpreters/ExpressionActions.cpp:61
ExpressionActions::ExpressionActions(ActionsDAG actions_dag_, const ExpressionActionsSettings & settings_, bool project_inputs_)
    : actions_dag(std::move(actions_dag_))
    , project_inputs(project_inputs_)
    , settings(settings_)
{
    /// It's important to determine lazy executed nodes before compiling expressions.
    std::unordered_map<const ActionsDAG::Node *, size_t> short_circuit_eager_arguments;
    std::unordered_set<const ActionsDAG::Node *> lazy_executed_nodes = processShortCircuitFunctions(
        actions_dag,
        settings.short_circuit_function_evaluation,
        settings.short_circuit_function_evaluation_reorder_arguments,
        short_circuit_eager_arguments);

The analysis has three stages.

Stage 1 — classify every node. setLazyExecutionInfo walks the DAG bottom-up from the outputs, propagating a single bit per node: can this node be evaluated lazily (i.e. on a subset of rows) at all? A node cannot be lazy if it is itself an output of the plan (somebody will read the full column), or if it is not a function:

cpp
// src/Interpreters/ExpressionActions.cpp:198
    /// If node is used in result or it doesn't have parents, we can't enable lazy execution.
    if (node_info.used_in_result || node_info.parents.empty() || (node->type != ActionsDAG::ActionType::FUNCTION && node->type != ActionsDAG::ActionType::ALIAS))
    {
        lazy_execution_info.can_be_lazy_executed = false;
        return;
    }

The interesting case is a node that is a common descendant of two arguments of the same short-circuit function:

cpp
// src/Interpreters/ExpressionActions.cpp:248
    /// Check if current node is common descendant of different function arguments of
    /// short-circuit function that disables lazy execution on this case.
    for (const auto & [short_circuit_node, indexes] : lazy_execution_info.short_circuit_ancestors_info)
    {
        /// If lazy execution is enabled for this short-circuit node,
        /// we shouldn't disable it for current node.
        if (lazy_execution_infos[short_circuit_node].can_be_lazy_executed)
            continue;

        if (!short_circuit_nodes.at(short_circuit_node).enable_lazy_execution_for_common_descendants_of_arguments && indexes.size() > 1)
        {
            lazy_execution_info.can_be_lazy_executed = false;
            return;
        }
    }

For if(cond, f(x), g(x)), x is used by both branches, so computing it lazily would compute it twice or not at all — if sets enable_lazy_execution_for_common_descendants_of_arguments = false, so x is excluded. For and(a, f(x), g(x)), x can be lazy, because the and mask filters it once and both consumers see the same filtered result — and sets the flag to true.

Stage 2 — propagate. findLazyExecutedNodes then walks down from each short-circuit function and marks the nodes that will be deferred:

cpp
// src/Interpreters/ExpressionActions.cpp:296
            case ActionsDAG::ActionType::FUNCTION:
            {
                /// Propagate lazy execution through function arguments.
                bool has_lazy_child = findLazyExecutedNodes(child->children, lazy_execution_infos, force_enable_lazy_execution, lazy_executed_nodes_out);

                /// Use lazy execution when:
                ///  - It's force enabled.
                ///  - Function is suitable for lazy execution.
                ///  - Function has lazy executed arguments.
                if (force_enable_lazy_execution || has_lazy_child || child->function_base->isSuitableForShortCircuitArgumentsExecution(getDataTypesWithConstInfoFromNodes(child->children)))
                {
                    has_lazy_node = true;
                    lazy_executed_nodes_out.insert(child);
                }
                break;
            }

Note the third condition: a node is deferred if it contains a deferred child, even if the node itself is not “suitable”. That is how expensive(a) — a chain of ordinary functions — gets deferred as a whole: the leaf is deferred, and the chain above it is deferred with it.

Stage 3 — reorder. Because and/or are commutative, the order in which the arguments are evaluated is a free choice. ClickHouse exploits that twice.

First, a static reorder: if argument 0 is heavy but argument 3 is cheap, the cheap one is executed eagerly on all rows instead, so the heavy one only runs on the rows the cheap one let through:

cpp
// src/Interpreters/ExpressionActions.cpp:393
            /// The argument with disabled lazy execution is executed on all rows. If it is heavy, while another argument
            /// is cheap, and the function allows it, execute the cheap argument on all rows instead, so that the heavy one
            /// is executed lazily, only on the rows that passed the cheap one. Example: `heavy(x) AND y > 0`.
            /// It is safe: the cheap argument is executed on all rows anyway (it is not lazy), and the heavy one is
            /// executed on a subset of the rows it was executed on before.
            /// In the `force_enable` mode all arguments are lazy, so there is no cheap argument that is executed anyway.
            /// The heavy argument must not contain stateful functions, functions with observable side effects (like `sleep`)
            /// or functions that are not deterministic in the scope of the query (like `rand`),
            /// because executing them on fewer rows changes what an observer sees.
            /// For the same reason, the cheap argument is not moved in front of the arguments between the first one
            /// and itself that contain such functions: they would be executed on fewer rows as well.
            /// The arguments after the cheap one are executed on the same rows as before.
            if (reorder_arguments
                && short_circuit_function_evaluation == ShortCircuitFunctionEvaluation::ENABLE
                && short_circuit_settings.arguments_are_commutative
                && short_circuit_settings.arguments_with_disabled_lazy_execution.size() == 1
                && short_circuit_settings.arguments_with_disabled_lazy_execution.contains(0)
                && !isCheapForShortCircuitEvaluation(node.children[0], is_cheap_cache)
                && !hasOrderSensitiveFunctions(node.children[0], has_order_sensitive_functions_cache))
            {
                for (size_t i = 1; i < node.children.size(); ++i)
                {
                    if (isCheapForShortCircuitEvaluation(node.children[i], is_cheap_cache))
                    {
                        short_circuit_settings.arguments_with_disabled_lazy_execution = {i};
                        /// If the function itself is executed lazily, it executes this argument first as well.
                        short_circuit_eager_arguments[&node] = i;
                        break;
                    }

                    if (hasOrderSensitiveFunctions(node.children[i], has_order_sensitive_functions_cache))
                        break;
                }
            }

The hasOrderSensitiveFunctions guard is the correctness escape hatch: rand(), sleep() and stateful functions must not be executed on fewer rows than before, because an observer would see a different number of calls.

Second, a dynamic reorder: at run time, the arguments are ordered by measured cost (see “Learning the order” below).

Run time: the thunk

A deferred node is not executed at all during the action loop. Instead it is stored as a ColumnFunction — a column whose “values” are a function and its captured arguments:

cpp
// src/Interpreters/ExpressionActions.cpp:877
            if (action.is_lazy_executed)
                res_column.column = ColumnFunction::create(
                    num_rows,
                    action.node->function_base,
                    std::move(arguments),
                    /*is_short_circuit_argument_=*/ true,
                    action.node->is_function_compiled,
                    /*recursively_convert_result_to_full_column_if_low_cardinality_=*/ false,
                    /*allow_lazy_replicated_captures_=*/ false,
                    action.short_circuit_argument_statistics,
                    action.short_circuit_eager_argument);

ColumnFunction is a real column type: it has a size (the row count) and it can be filtered, cut and replicated. Its filter applies the filter to the captured columns and produces a smaller thunk:

cpp
// src/Columns/ColumnFunction.cpp:214
ColumnPtr ColumnFunction::filter(const Filter & filt, ssize_t result_size_hint) const
{
    if (elements_size != filt.size())
        throw Exception(ErrorCodes::SIZES_OF_COLUMNS_DOESNT_MATCH, "Size of filter ({}) doesn't match size of column ({})",
                        filt.size(), elements_size);

    ColumnsWithTypeAndName capture = captured_columns;
    for (auto & column : capture)
        column.column = column.column->filter(filt, result_size_hint);

    size_t filtered_size = 0;
    if (capture.empty())
    {
        filtered_size = countBytesInFilter(filt);
    }
    else
        filtered_size = capture.front().column->size();

    return ColumnFunction::create(
        filtered_size,
        function,
        capture,
        is_short_circuit_argument,
        is_function_compiled,
        recursively_convert_result_to_full_column_if_low_cardinality,
        allow_lazy_replicated_captures,
        short_circuit_argument_statistics,
        short_circuit_eager_argument);
}

This is the key step: filtering a thunk shrinks the data the deferred function will see. It is not “compute then discard” — it is “compute on fewer rows”.

reduce() is where the deferred function finally runs:

cpp
// src/Columns/ColumnFunction.cpp:466
ColumnWithTypeAndName ColumnFunction::reduce(bool dry_run) const
{
    auto args = function->getArgumentTypes().size();
    auto captured = captured_columns.size();

    if (args != captured)
        throw Exception(ErrorCodes::LOGICAL_ERROR, "Cannot call function {} because is has {} "
                        "arguments but {} columns were captured.",
                        function->getName(), toString(args), toString(captured));

    ColumnsWithTypeAndName columns = captured_columns;
    /// Arguments of lazy executed function can also be lazy executed.
    if (is_short_circuit_argument)
    {
        IFunction::ShortCircuitSettings settings;
        /// We shouldn't execute all arguments if this function is short circuit,
        /// because it will handle lazy executed arguments by itself.
        /// Execute only arguments with disabled lazy execution.
        /// A function with commutative arguments can have another argument chosen to be executed first.
        if (function->isShortCircuit(settings, args))
        {
            if (short_circuit_eager_argument)
                settings.arguments_with_disabled_lazy_execution = {*short_circuit_eager_argument};

            for (size_t i : settings.arguments_with_disabled_lazy_execution)
            {
                if (const ColumnFunction * arg = checkAndGetShortCircuitArgument(columns[i].column))
                    columns[i] = arg->reduce(dry_run);
            }
        }

Note the recursion: a deferred argument of a deferred function is a deferred argument of a deferred function. reduce() only forces the arguments that must be evaluated eagerly.

The mask

Now the runtime. and/or keep a UInt8 mask: one byte per row, 1 means “this row is still undecided”. maskedExecuteAndUpdateMask is the workhorse:

cpp
// src/Columns/MaskOperations.cpp:312
template <bool inverted>
static MaskInfo maskedExecuteAndUpdateMaskImpl(
    const ColumnWithTypeAndName & column,
    PaddedPODArray<UInt8> & mask,
    const MaskInfo & mask_info,
    PaddedPODArray<UInt8> * nulls,
    UInt8 null_value)
{
    if (!mask_info.has_ones)
        return mask_info;

    const auto * column_function = checkAndGetShortCircuitArgument(column.column);
    if (!column_function)
        return extractMaskImpl<inverted>(mask, column.column, null_value, nullptr, nulls);

    if (!mask_info.has_zeros)
    {
        auto result = column_function->reduce();
        return extractMaskImpl<inverted>(mask, result.column, null_value, nullptr, nulls);
    }

    /// Unlike `if`/`multiIf`, `and`/`or` only need to update the mask. Consume the selected
    /// result directly instead of expanding it to the full block and reading it again.
    /// Only this path accepts compact columns; the public `extractMask` functions keep
    /// requiring full-sized columns.
    auto filtered = column_function->filter(mask, -1);
    auto result = assert_cast<const ColumnFunction &>(*filtered).reduce();
    return extractMaskImpl<inverted, true>(mask, result.column, null_value, nullptr, nulls);
}

Read it as three cases:

The mask is all zeros. Nothing is undecided, so nothing needs to be computed at all. The function is never called. (has_ones == false.)
The mask is all ones. Every row is undecided, so there is nothing to gain from filtering: the thunk is reduced directly, on the full block.
The mask is mixed. This is the interesting case: the thunk is filtered by the mask first, so the captured columns shrink to only the undecided rows; then it is reduced, computing the function on just those rows; then the result is folded back into the mask — but compactly, so the result is never expanded back to the full block.

That third point is the compact template parameter on extractMaskImpl: the result column has fewer rows than the mask, and the mask update walks the result in order, keeping the row positions of the mask intact.

MaskInfo is the two-bit summary of the mask state that makes the fast paths cheap:

cpp
// src/Columns/MaskOperations.h:18
struct MaskInfo
{
    bool has_ones;
    bool has_zeros;
};

The full and/or implementation ties it together:

cpp
// src/Functions/FunctionsLogical.cpp:763
    /// A set mask bit means that the row still needs evaluation: it has not encountered
    /// false for `and`, or true for `or`. `NULL` does not decide either operation, so it leaves
    /// the row active and is remembered separately. A later decisive value clears the
    /// `NULL` state in `applyTernaryLogic`; otherwise the final result remains `NULL`.
    /// The `or` mask contains inverted values and is inverted once at the end.

    bool inverted = Name::name != NameAnd::name;
    UInt8 null_value = static_cast<UInt8>(Name::name == NameAnd::name);
    IColumn::Filter mask(arguments[0].column->size(), 1);

and the loop over the arguments:

cpp
// src/Functions/FunctionsLogical.cpp:800
    MaskInfo mask_info{.has_ones = true, .has_zeros = false};
    /// The number of rows that are still undecided, if it is known.
    std::optional<size_t> undecided_rows = mask.size();
    for (size_t i : order)
    {
        if (statistics[i])
        {
            size_t executed_rows = undecided_rows ? *undecided_rows : countBytesInFilter(mask);
            Stopwatch watch;
            mask_info = maskedExecuteAndUpdateMask(arguments[i], mask, mask_info, inverted, nulls.get(), null_value);
            UInt64 elapsed = watch.elapsedNanoseconds();

            if (!mask_info.has_ones)
                undecided_rows = 0;
            else if (!mask_info.has_zeros)
                undecided_rows = mask.size();
            else
                undecided_rows = countBytesInFilter(mask);

            statistics[i]->add(executed_rows, *undecided_rows, elapsed);
        }
        else
        {
            mask_info = maskedExecuteAndUpdateMask(arguments[i], mask, mask_info, inverted, nulls.get(), null_value);
            undecided_rows.reset();
        }

        /// Stop when every row has a decisive result.
        if (!mask_info.has_ones)
            break;
    }
    /// For OR function we need to inverse mask to get the resulting column.
    if (inverted)
        inverseMask(mask, mask_info);

The break is the payoff: once every row has been decided, the remaining arguments are not evaluated at all.

or is implemented with an inverted mask, so the same code serves both — the mask always means “undecided”, and the inversion happens once at the end.

`if` is different: the mask selects a branch

if(cond, then, else) cannot reorder or merge its arguments; it must compute then on the rows where cond is true and else on the rest. The mask is used the same way, but each branch gets its own mask (one is the inverse of the other):

cpp
// src/Functions/if.cpp:1318
    static void executeShortCircuitArguments(ColumnsWithTypeAndName & arguments)
    {
        int last_short_circuit_argument_index = checkShortCircuitArguments(arguments);
        if (last_short_circuit_argument_index == -1)
            return;

        executeColumnIfNeeded(arguments[0]);

        /// Check if condition is const or null to not create full mask from it.
        if ((isColumnConst(*arguments[0].column) || arguments[0].column->onlyNull()) && !arguments[0].column->empty())
        {
            /// `onlyNull` columns (e.g. `Const(Nullable(Nothing))`) are treated as the false branch:
            /// `getBool` would throw on the dummy nested column, but `if(NULL, then, else)` returns `else`.
            const bool value = !arguments[0].column->onlyNull() && arguments[0].column->getBool(0);
            executeColumnIfNeeded(arguments[1], !value);
            executeColumnIfNeeded(arguments[2], value);
            return;
        }

        IColumn::Filter mask(arguments[0].column->size(), 1);
        auto mask_info = extractMask(mask, arguments[0].column);
        maskedExecute(arguments[1], mask, mask_info);
        inverseMask(mask, mask_info);
        maskedExecute(arguments[2], mask, mask_info);
    }

maskedExecute is the version that expands the result back to the full block, because if has to produce a full-length column:

cpp
// src/Columns/MaskOperations.cpp:278
void maskedExecute(ColumnWithTypeAndName & column, const PaddedPODArray<UInt8> & mask, const MaskInfo & mask_info)
{
    const auto * column_function = checkAndGetShortCircuitArgument(column.column);
    if (!column_function)
        return;

    size_t original_size = column.column->size();

    ColumnWithTypeAndName result;
    if (!mask_info.has_ones)
    {
        /// If mask contains only zeros, we can just create a column with default values as it will be ignored
        auto result_type = column_function->getResultType();
        auto default_column = result_type->createColumnConstWithDefaultValue(original_size)->convertToFullColumnIfConst();
        column = {default_column, result_type, ""};
    }
    else if (mask_info.has_zeros)
    {
        /// If it contains both zeros and ones, we need to execute the function only on the mask values
        /// First we filter the column, which creates a new column, then we apply the column, and finally we expand it
        /// Expanding is done to keep consistency in function calls (all columns the same size) and it's ok
        /// since the values won't be used by `if`
        auto filtered = column_function->filter(mask, -1);
        auto filter_after_execution = typeid_cast<const ColumnFunction *>(filtered.get())->reduce();
        auto mut_column = IColumn::mutate(std::move(filter_after_execution.column));
        mut_column->expand(mask, false);
        column.column = std::move(mut_column);
    }
    else
        column = column_function->reduce();

    chassert(column.column->size() == original_size);
}

The expand at the end is the “scatter back” step: the compact result is expanded to the full row count, with default values in the holes. For if, those holes are exactly the rows where the branch was not taken, so the values are discarded anyway — but the column must have the right size.

Learning the order

The dynamic reordering deserves its own section, because it is the most novel part. and/or arguments are commutative, so their evaluation order is free — but only for arguments that cannot change their observable behaviour. ClickHouse measures the cost of each argument and orders them by “nanoseconds per decided row”.

The measurement lives in a small, mutex-protected accumulator:

cpp
// src/Columns/ShortCircuitArgumentStatistics.cpp:7
void ShortCircuitArgumentStatistics::add(size_t executed_rows_, size_t undecided_rows_, UInt64 elapsed_nanoseconds_)
{
    if (executed_rows_ == 0)
        return;

    std::lock_guard lock(mutex);

    executed_rows += static_cast<double>(executed_rows_);
    decided_rows += static_cast<double>(executed_rows_ - undecided_rows_);
    elapsed_nanoseconds += static_cast<double>(elapsed_nanoseconds_);

    if (executed_rows > decay_threshold_rows)
    {
        executed_rows /= 2;
        decided_rows /= 2;
        elapsed_nanoseconds /= 2;
    }
}

and the rank is:

cpp
// src/Columns/ShortCircuitArgumentStatistics.cpp:26
double ShortCircuitArgumentStatistics::getRank() const
{
    std::lock_guard lock(mutex);

    if (executed_rows == 0)
        return -1;

    /// One row is added to the denominator to keep the rank finite for an argument that has not decided any row.
    /// The rank of such an argument is its total time, which is large compared to the time per decided row.
    return elapsed_nanoseconds / (decided_rows + 1);
}

The statistics object is shared by all threads executing the same expression (“The object is shared between the threads that execute the same expression, so it is protected by a mutex. It is locked once per argument per block, which is negligible compared to the execution of the argument.” — the header says). The counters are halved once they exceed 2^20 rows, so the estimate follows the data as it changes.

The class header states the theory:

cpp
// src/Columns/ShortCircuitArgumentStatistics.h:13
/** Statistics of a lazily executed argument of a short-circuit function with commutative arguments (`and`, `or`),
  * accumulated over the blocks the argument was executed on.
  *
  * The function executes its lazy arguments one after another, each one only on the rows that are still undecided
  * (have not encountered `false` for `and`, or `true` for `or`). For every argument it records how many rows it
  * was executed on, how many of them stayed undecided after it, and how long it took.
  *
  * From these, `getRank` computes the time spent per decided row. For independent arguments, executing them in
  * ascending order of this rank minimizes the expected total time: an argument with cost `c` per row that leaves
  * a fraction `p` of rows undecided should go before an argument with `c'` and `p'` if
  * `c + p * c' < c' + p' * c`, which is `c / (1 - p) < c' / (1 - p')`.
  *
  * The object is shared between the threads that execute the same expression, so it is protected by a mutex.
  * It is locked once per argument per block, which is negligible compared to the execution of the argument.
  */

The sort itself is a stable_sort over the groups of arguments that may be reordered:

cpp
// src/Functions/FunctionsLogical.cpp:735
static bool orderArgumentsByStatistics(VectorWithMemoryTracking<size_t> & order, const VectorWithMemoryTracking<ShortCircuitArgumentStatistics *> & statistics)
{
    VectorWithMemoryTracking<double> ranks(order.size());
    for (size_t i = 1; i < order.size(); ++i)
        if (statistics[i])
            ranks[i] = statistics[i]->getRank();

    auto group_begin = order.begin() + 1;
    while (group_begin != order.end())
    {
        auto group_end = std::find_if(group_begin, order.end(), [&](size_t i) { return statistics[i] == nullptr; });
        /// The rank is negative for the arguments that have not been executed yet.
        std::stable_sort(group_begin, group_end, [&](size_t lhs, size_t rhs) { return ranks[lhs] < ranks[rhs]; });
        group_begin = group_end == order.end() ? group_end : group_end + 1;
    }

    return !std::is_sorted(order.begin(), order.end());
}

The grouping is what keeps the correctness guarantee: arguments without statistics — the ones that can throw, or that are not safe to move — act as barriers, and each group between two barriers is sorted independently. So x != 0 AND intDiv(1, x) > 0 never divides by zero: intDiv throws, so it has no statistics, so the group boundary keeps x != 0 in front of it.

The setting that controls this is brand new — its changelog entry in the source says 26.10:

cpp
// src/Core/Settings.cpp:9564
    DECLARE(Bool, short_circuit_function_evaluation_reorder_arguments, true, R"(
Allows changing the order in which the arguments of the [and](/reference/functions/regular-functions/logical-functions#and) and [or](/reference/functions/regular-functions/logical-functions#or) functions are evaluated with [short-circuit evaluation](#short_circuit_function_evaluation), when it does not change the result and does not introduce exceptions.

- If the first argument is computationally heavy and another argument is cheap, the cheap argument is evaluated first, and the heavy one is evaluated only on the rows where the result is not yet decided. For example, in `WHERE JSONExtractString(json, 'a') = 'x' AND id < 100` the JSON is parsed only for the rows with `id < 100`.
- The arguments that are evaluated lazily and cannot throw an exception are evaluated in the order of increasing time per row they decide, as measured on the previous blocks. The arguments that can throw an exception keep all the arguments that precede them in front of them, so that, for example, `x != 0 AND intDiv(1, x) > 0` never divides by zero.
)", 0, \
        {"26.10", false, true, "New setting."}) \

The picture

text
   plan time                          run time (per block)
   --------                          -------------------
   and(a, b, c)                       mask = [1,1,1,...]   (all undecided)
        |                                    |
        |  a is eager                      +-- evaluate a on 65409 rows
        |  b, c are lazy thunks            |     mask &= a     (some rows decided false)
        |                                  |
   Action list:                     +-- filter thunk b by mask  -> 12000 rows
     and    <- a (eager)                |   reduce b              -> 12000 evaluations
     b      <- ColumnFunction thunk     |   mask &= b
     c      <- ColumnFunction thunk  +-- filter thunk c by mask  -> 300 rows
                                        |   reduce c              -> 300 evaluations
                                        |   mask &= c
                                        v
                                    mask = 0 everywhere -> break
                                    remaining arguments never evaluated

Trade-offs

What the mask trick buys:

Work proportional to the surviving rows, not the block size. A JSONExtractString in a WHERE clause runs on the rows that survive the cheaper conjuncts, not on all of them.
Exceptions become unreachable. intDiv(1, x) in a WHERE clause only throws on the rows that actually reach it. This is the “prevent possible exceptions” half of the setting’s description, and for many workloads it is worth more than the CPU saving.
The order of evaluation becomes a runtime decision. The static reordering handles the obvious cases; the statistics-driven reordering handles the ones that depend on the data.

What it costs:

The thunk is a real column. ColumnFunction holds captures, has a size, and participates in filter/cut/replicate. Every operation on it has to be implemented for the thunk type, not just for the underlying column type. This is why ColumnFunction has its own filter, cut, replicate, cloneResized implementations.
A std::vector<bool>-style mask per short-circuit function. One byte per row, allocated and filled per block. For a 65 409-row block that is 64 KiB of traffic per short-circuit function — noticeable, but small next to the columns themselves.

The compact-result dance. and/or consume a compact result and fold it back into the mask without expanding; if has to expand. The two paths are different code with different invariants, and the compact one is explicitly restricted:

cpp
// src/Columns/MaskOperations.cpp:335
    /// Unlike `if`/`multiIf`, `and`/`or` only need to update the mask. Consume the selected
    /// result directly instead of expanding it to the full block and reading it again.
    /// Only this path accepts compact columns; the public `extractMask` functions keep
    /// requiring full-sized columns.

A mutex on the hot path. The statistics are shared between threads, so every argument of every block takes a lock. The header’s claim is that this is “negligible compared to the execution of the argument”, which is true only if the argument is actually doing work.
Correctness is subtle. The rules about stateful functions, observable side effects, in-scope determinism, common descendants of arguments, and throwing arguments are all there because the naive version of this optimisation changes observable behaviour. Every one of those guards is a rule you have to remember when you add a new function that claims to be short-circuit-able.

The one thing to remember: the short-circuit optimisation is not “skip the rest of the expression” — it is “run the rest of the expression on fewer rows”. The mask is the only state that crosses the boundary, and everything else is a normal column operation.

The part people get wrong: and/or argument reordering is only legal because those two operators are commutative and because ClickHouse checks that the reordered arguments cannot throw and are not observable. If you write your own function and claim arguments_are_commutative = true, you are taking on that contract: the argument order will change under you.

What to go do about it: write a query where a genuinely expensive expression is guarded by a cheap one and check the number of evaluations with system.query_log (ProfileEvents counts function executions). If the expensive function’s count equals the number of rows, short-circuiting did not fire — most often because the expensive argument is not “suitable” for lazy execution, and the fix is short_circuit_function_evaluation = 'force_enable'.