ClickHouse Plans Distributed Queries with Cascades: A Real Cost-Based Optimizer

TL;DR: ClickHouse’s new Cascades optimizer treats a distributed query as a search problem. It generates alternative plans in a memo, prices each one with a work/network/sequential cost model, and ships the cheapest — but it refuses to guess, and fails loudly when it can’t decide.

A single-node query plan has one obvious shape: read the table, filter, aggregate, sort. A distributed query does not.

The same SELECT can be executed as a gather-everything-to-the-coordinator, or as a shuffle of both sides of a join followed by a local aggregation, or as a broadcast of a tiny dimension table to every node followed by a local join. And these choices interact — the best join strategy depends on how the data will be aggregated afterwards, and the best aggregation strategy depends on how the join output is distributed.

So the planner has to explore combinations and compare them.

ClickHouse’s traditional answer was a set of fixed heuristics. Its new answer, arriving in 26.8 as an experimental setting, is a real cost-based optimizer built on the Cascades framework: a memo of alternative plans, a set of rules that generate alternatives, and a cost model that prices them.

cpp
// src/Core/Settings.cpp:11131
    DECLARE(Bool, enable_cascades_optimizer, false, R"(
Enable the Cascades cost-based optimizer for distributed query plans.
Takes effect only together with `make_distributed_plan = 1`: the setting alone does not change single-node query planning.
)", EXPERIMENTAL, \
        {"26.8", false, false, "New experimental setting."}) \

This article walks the implementation: the memo, the task-based search, the rules, the cost model, the enforcers, and the places where the implementation is deliberately conservative.

The problem the optimizer solves

The ARCHITECTURE.md that ships with the code states it plainly:

text
## What Problem Does This Solve?

ClickHouse can execute a query on a single node using its standard pipeline: plan the
query, read from MergeTree, apply filters/expressions/joins/aggregations, return results.
But when data is spread across multiple nodes (shared storage like S3, or a multi-node
cluster), the optimizer must decide how to distribute the work:

- Should a join shuffle both sides by the join key, or broadcast the smaller table to
  all nodes?
- Should an aggregation happen on each node first (partial agg) and then merge results,
  or gather all data to one node and aggregate there?
- Should a table scan be split across N nodes (parallel read), or should each node read
  the full table (replicated read for small dimension tables)?
- Where should exchanges (network data transfers between nodes) be placed?

Pay attention to the third bullet. With shared storage (S3), a 25-row dimension table doesn’t need to be broadcast at all — every node can just read it from S3 itself.

That alternative, ReplicatedRead, is exactly the kind of thing only a cost-based search would find, because it isn’t a “join strategy” in the classical sense. It’s a read strategy, chosen because the cost of re-reading a tiny table is lower than the cost of shipping it.

The memo

The memo is the central data structure. It contains groups, each representing a set of logically equivalent subexpressions. Each group holds both the logical expressions (ways of computing the same thing) and the physical expressions (ways of computing it with a concrete algorithm and concrete properties).

cpp
// src/Processors/QueryPlan/Optimizations/Cascades/Memo.h:10
class Memo
{
public:
    explicit Memo(LoggerPtr log_)
        : log(log_)
    {}

    GroupId addGroup(GroupExpressionPtr group_expression);

    GroupPtr getGroup(GroupId group_id);
    GroupConstPtr getGroup(GroupId group_id) const;

    size_t getGroupCount() const { return groups_by_id.size(); }

The plan is ingested into the memo one group per step. A step with children becomes a group whose expression has one input link per child, and the input link carries the required properties of that child:

cpp
// src/Processors/QueryPlan/Optimizations/Cascades/Optimizer.cpp:179
    auto group_expression = std::make_shared<GroupExpression>(std::move(node.step));
    auto group_id = memo.addGroup(group_expression);
    for (auto * child_node : node.children)
    {
        auto [input_group_id, pending_props] = addGroup(*child_node);
        group_expression->inputs.push_back({input_group_id, pending_props});
    }

So each input link carries the child’s group id and the properties the parent requires of it. That’s where the “required properties” of the whole framework enter the picture.

Properties: distribution and sorting

A physical expression has two kinds of properties.

Distribution — how the data is spread over the nodes:

cpp
// src/Processors/QueryPlan/Optimizations/Cascades/Properties.h:17
struct DistributionDescription
{
    DistributionColumns columns;    /// Columns by which data is distributed. E.g. for shuffle exchange or partitioned table scan.
    /// Type each key is cast to before hashing (parallel to `columns`; empty when the raw
    /// types agree). Aligns buckets across both sides of a shuffle join.
    Names hash_type_names;
    bool is_replicated = false;     /// All data is replicated to all nodes, so any distribution is satisfied. E.g. for small tables that are broadcasted to all nodes.
    size_t node_count = 1;          /// Number of nodes among which data is distributed. E.g. for a shuffle exchange or a partitioned read.

    bool operator==(const DistributionDescription & other) const = default;

    void dump(WriteBuffer & out) const;
    String dump() const;
};

Sorting — whether the output is ordered, and by what.

A parent requires properties of its child, and a child satisfies a requirement if it provides at least as much. The matching isn’t trivial: a sorted-by-(a) stream satisfies a requirement of “sorted by (a)”, and the required sort must be a prefix of the existing one:

cpp
// src/Processors/QueryPlan/Optimizations/Cascades/Properties.cpp:9
bool ExpressionProperties::isSortingSatisfiedBy(const SortDescription & required, const SortDescription & existing)
{
    /// Required sorting is satisfied by existing sorting if required is the prefix of existing
    if (required.size() > existing.size())
        return false;
    for (size_t i = 0; i < required.size(); ++i)
    {
        if (required[i] != existing[i])
            return false;
    }
    return true;
}

and the distribution match is positional — data shuffled by (b, a) does not colocate with data shuffled by (a, b):

cpp
// src/Processors/QueryPlan/Optimizations/Cascades/Properties.cpp:39
    /// The partition hash chains the key columns in order and may cast them first, so the
    /// match must be positional and the hash types must agree: data shuffled by `(b, a)`
    /// or hashed at a different type does not colocate with data shuffled by `(a, b)`.
    if (required.hash_type_names != existing.hash_type_names)
        return false;

Sorting is a property, not an operator

One design decision deserves a callout, because it differs from classical Cascades.

A plain ORDER BY (no LIMIT) is not an operator in the memo — it’s a property that the parent requires of its input. The optimizer then produces the sort itself, if some child can provide it more cheaply:

cpp
// src/Processors/QueryPlan/Optimizations/Cascades/Optimizer.cpp:162
    /// Strip a limit-less SortingStep::Full - pure sorting is a physical property, not a logical
    /// one.  Return the child's GroupId along with the sorting as required properties, so the
    /// caller can attach them to the input link of the parent group expression.
    /// A SortingStep with a limit is a top-N (row-reducing) operator, so it is kept as an
    /// operator instead; the limit is owned by that operator, never by the sorting property.
    const auto * sorting_step = typeid_cast<const SortingStep *>(node.step.get());
    if (sorting_step && sorting_step->getType() == SortingStep::Type::Full && sorting_step->getLimit() == 0)
    {
        chassert(node.children.size() == 1);
        auto [child_group_id, _] = addGroup(*node.children.front());
        ExpressionProperties stripped_props;
        stripped_props.sorting = sorting_step->getSortDescription();
        return {child_group_id, stripped_props};
    }

And a LIMIT after the sort makes it a top-N, which reduces the row count and therefore is an operator, with its own rules and its own cost.

The search: tasks on a stack

The optimizer is a LIFO stack of tasks. There are six task types, and a group moves through four stages.

Stage 1 — Explore. Transformation rules generate logically equivalent alternatives (join commutativity, two-stage aggregation).

Stage 2 — Implement. Implementation rules turn logical expressions into physical ones with concrete properties (local join, broadcast join, shuffle join; local read, parallel read, replicated read).

Stage 3 — Enforce. Enforcer rules bridge property gaps by inserting exchange steps.

Stage 4 — Done.

OptimizeGroupTask drives the stages:

cpp
// src/Processors/QueryPlan/Optimizations/Cascades/Task.cpp:38
    if (!group->isExplored())
    {
        /// Explore the group, then re-run `OptimizeGroupTask`
        optimizer.pushTask(std::make_unique<OptimizeGroupTask>(group_id, required_properties));
        optimizer.pushTask(std::make_unique<ExploreGroupTask>(group_id));
    }
    else if (!group->isOptimizedFor(required_properties))
    {
        optimizer.pushTask(std::make_unique<OptimizeGroupTask>(group_id, required_properties));

        for (auto & expression : group->logical_expressions)
            optimizer.pushTask(std::make_unique<OptimizeExpressionTask>(expression, required_properties));

        group->setOptimizedFor(required_properties);
    }

The interesting part is the pruning decision at the top of the task, which is explicitly not a cost-based prune:

cpp
// src/Processors/QueryPlan/Optimizations/Cascades/Task.cpp:20
    /// Skip this group only if it is already fully processed (explored + implemented +
    /// enforced) for these properties and has a satisfying plan - re-running would be a no-op.
    /// We deliberately do not prune just because a current best is within a finite cost budget:
    /// the budget is an upper bound, not a lower bound, so such pruning is unsound for
    /// optimality, and it can return before stage-3 enforcers add the distributed alternatives.
    {
        const auto & cost_config = optimizer.getMemo().getContext().cost_config;
        bool group_fully_processed = group->isExplored()
            && group->isOptimizedFor(required_properties)
            && group->isEnforcedFor(required_properties);
        if (group_fully_processed && group->getBestImplementation(required_properties, cost_config).expression)
        {
            group->setFullyDoneFor(required_properties);
            LOG_TEST(optimizer.log, "OptimizeGroupTask group #{}: already fully processed", group_id);
            return;
        }
    }

This is the part people get wrong when they read this code.

Classical Cascades prunes with branch-and-bound: once a subtree’s cost exceeds the best complete plan, it gets dropped. ClickHouse’s implementation refuses to do that, because a subtree’s current best is an upper bound on its final cost — a cheaper enforcer-built alternative may still appear — and pruning on it would be unsound.

Instead, the search is bounded by a task count.

Rule ordering

Every rule has a static promise (a priority). The applicable rules are sorted by promise and pushed onto the LIFO stack, so the highest-promise rule runs first:

cpp
// src/Processors/QueryPlan/Optimizations/Cascades/Task.cpp:169
    std::vector<std::pair<Promise, OptimizationRulePtr>> moves;
    for (const auto & rule : rules)
    {
        if (!expression->isApplied(*rule, required_properties) && rule->checkPattern(expression, required_properties, optimizer.getMemo()))
            moves.push_back({rule->getPromise(), rule});
    }

    /// Sort ascending so the LIFO task stack pops the highest-promise rule first.
    std::sort(moves.begin(), moves.end(), [](const auto & lhs, const auto & rhs) { return lhs.first < rhs.first; });

The promise doesn’t change which plans are considered — every applicable rule is eventually applied. It only changes the order, which breaks ties among equal-cost alternatives (the first-found best wins).

The cost model

The cost has three dimensions, combined by configurable weights:

cpp
// src/Processors/QueryPlan/Optimizations/Cascades/Cost.h:39
struct CostConfig
{
    Float64 work_weight = 1.0;            /// Parallelizable work (scans, expression eval, I/O).
    Float64 network_weight = 1.0;         /// Per-byte network transfer.
    /// Single-threaded phases (gather/scatter funnels, merge cursors). The weight is the
    /// per-node thread count: work parallelizes across the threads of a node while a serial
    /// phase holds one thread, so one serial row costs about `threads` work rows (Brent's law:
    /// wall-clock ~ work / threads + serial path).
    Float64 sequential_weight = 32.0;
    /// Fixed per-exchange latency (connection setup, metadata), in sequential rows. The
    /// weighted value (~1e5 work units) keeps a plan over a small input local: distribution
    /// cannot pay for its setup there.
    Float64 exchange_fixed_overhead = 3000.0;

and the combination:

cpp
// src/Processors/QueryPlan/Optimizations/Cascades/Cost.h:74
    Float64 total(const CostConfig & config) const
    {
        /// If any component is infinite the plan is impossible; return infinity directly. Multiplying
        /// first would let a zero weight turn `inf * 0` into NaN, and a NaN cost compares as neither
        /// better nor worse, so an impossible plan could be picked as best.
        if (!std::isfinite(work) || !std::isfinite(network) || !std::isfinite(sequential))
            return std::numeric_limits<Float64>::infinity();

        return work * config.work_weight
             + network * config.network_weight
             + sequential * config.sequential_weight;
    }

The inf * 0 = NaN guard is the kind of detail that separates a cost model that works from one that occasionally picks an impossible plan.

The formulas

A hash join prices the probe, the output and the hash-table build:

cpp
// src/Processors/QueryPlan/Optimizations/Cascades/Cost.cpp:130
static Cost hashJoinCost(const CostInputs & inputs, bool is_broadcast)
{
    const auto & left_stats = inputStats(inputs, 0);
    const auto & right_stats = inputStats(inputs, 1);

    Cost cost;
    cost.work = (left_stats.estimated_row_count + inputs.output_stats.estimated_row_count) / inputs.parallelism;

    /// The build side is materialized fully on every node for a broadcast join (the nodes build
    /// concurrently) and 1/N per node otherwise. The build is work, not a sequential phase:
    /// `parallel_hash` shards the hash table across threads within a node.
    const Float64 build_rows_per_node = is_broadcast
        ? right_stats.estimated_row_count
        : right_stats.estimated_row_count / inputs.parallelism;
    /// Hash table materialization: memory allocation + cache pressure.
    cost.work += inputs.config.hash_table_build_factor * build_rows_per_node
        + build_rows_per_node * right_stats.estimated_bytes_per_row;
    return cost;
}

The exchange prices the network, and the distinction between a shuffle and a gather is where most of the distributed reasoning lives:

cpp
// src/Processors/QueryPlan/Optimizations/Cascades/Cost.cpp:240
static Cost exchangeCost(const CostInputs & inputs, const IQueryPlanStep & step)
{
    /// A sorted gather over a partial top-N transfers min(input_rows, L * node_count) rows,
    /// not the group's trimmed L; the caller resolves that override from the memo.
    const Float64 rows = inputs.exchange_rows_override.value_or(inputs.output_stats.estimated_row_count);
    Cost cost;
    /// The network term is wall-clock per node, like the work term. A shuffle (N->N) moves
    /// 1/N of the data per node, all nodes concurrently; without the division one node
    /// scanning the whole table is priced the same as the cluster shuffling it, and the
    /// optimizer keeps big scans on a single node.
    Float64 network_bytes = rows * inputs.output_stats.estimated_bytes_per_row;
    if (dynamic_cast<const ShuffleExchangeStep *>(&step))
        network_bytes /= std::max(1.0, inputs.node_count);
    cost.network += network_bytes;
    cost.sequential += inputs.config.exchange_fixed_overhead;
    /// Gather (N->1) and Scatter (1->N) funnel every row through a single node that
    /// sends or receives them sequentially, so their transfer stays undivided and each row
    /// pays the funnel cost. Without it a gather of a large input looks as cheap as a
    /// shuffle, so the optimizer distributes work (e.g. a sort) that should stay local.
    if (dynamic_cast<const GatherExchangeStep *>(&step) || dynamic_cast<const ScatterExchangeStep *>(&step))
        cost.sequential += inputs.config.funnel_sequential_cost_per_row * rows;
    return cost;
}

Three subtleties are worth spelling out:

A shuffle divides the network cost by the node count, because each node ships 1/N of the data and all nodes do it concurrently.

A broadcast does not divide, because every node ingests the whole payload:

cpp
// src/Processors/QueryPlan/Optimizations/Cascades/Cost.cpp:227
static Cost broadcastExchangeCost(const CostInputs & inputs)
{
    Cost cost;
    /// The network term is wall-clock per node, like the work term (which is divided by
    /// parallelism): every receiving node ingests the full payload, all of them concurrently,
    /// and the senders each ship their share of the copies in parallel. So one full payload
    /// is the per-node bound. A shuffle moves 1/N per node, so a broadcast still costs N times
    /// a shuffle of the same data.
    cost.network += inputs.output_stats.estimated_row_count * inputs.output_stats.estimated_bytes_per_row;
    cost.sequential += inputs.config.exchange_fixed_overhead;
    return cost;
}

Every exchange pays a fixed overhead in sequential units, which is what keeps a plan over a small input local: distributing 25 rows is not worth a network round trip.

A read is priced on its scan volume, not its output

This one is subtle and important. A filter that the primary key can’t prune leaves the whole granule selection to scan, so the output estimate badly understates the cost:

cpp
// src/Processors/QueryPlan/Optimizations/Cascades/Cost.cpp:150
/// One node reads the whole table.
static Cost fullReadCost(const CostInputs & inputs)
{
    /// Price the scan volume, not the output volume: a filter the primary key cannot prune
    /// leaves the whole granule selection to scan, and without this a replicated read of such
    /// a table would look orders of magnitude cheaper than the scan it does.
    if (inputs.output_stats.physical_read_bytes > 0)
        return Cost{.work = inputs.output_stats.physical_read_bytes};
    return Cost{.work = inputs.output_stats.estimated_row_count * inputs.output_stats.estimated_bytes_per_row};
}

Without this, ReplicatedRead — every node reading the whole table from S3 — would look free for a table whose filter prunes 99 % of the rows.

The cost model is query-tunable

Everything above is overridable with one JSON parameter:

sql
SET param__internal_cascades_cost_config = '{"work_weight":1,"network_weight":1,"sequential_weight":32}';

and an invalid configuration rejects the query rather than silently falling back to the defaults.

The rules

Join implementations

One rule produces all the join alternatives:

cpp
// src/Processors/QueryPlan/Optimizations/Cascades/Rules/HashJoinImplementation.cpp:19
/// Produces all applicable hash join implementations in a single rule:
///   - Local join: both inputs gathered to one node (always applicable)
///   - Broadcast join: left partitioned any way, right replicated (only when node_count > 1)
///   - Partitioned (shuffle) join: both inputs shuffled by join keys (only when node_count > 1
///     and the join has equi-join predicates)
///
/// When node_count == 1 all three strategies produce the same plan, so only the local join
/// is emitted to avoid redundant identical alternatives in the memo.
class HashJoinImplementation : public IOptimizationRule

A shuffle join partitions both sides by the join key. The key columns are recorded positionally on both sides, together with the type they’re hashed at:

cpp
// src/Processors/QueryPlan/Optimizations/Cascades/Rules/HashJoinImplementation.cpp:316
    auto add_key = [&](const JoinKeyPair & key)
    {
        left_dist.columns.push_back({key.left});
        right_dist.columns.push_back({key.right});
        if (needs_hash_cast)
        {
            const String & type_name = hash_type_for(key);
            left_dist.hash_type_names.push_back(type_name);
            right_dist.hash_type_names.push_back(type_name);
        }
        /// Advertise the output partitioning only on the preserved side(s).
        NameSet output_key;
        if (left_preserved)
            output_key.insert(key.left);
        if (right_preserved)
            output_key.insert(key.right);

The hash_type_names exist because if the two sides have different key types, they must be cast to a common type before hashing. Otherwise the two sides land in different buckets and the join produces nothing.

Two-stage aggregation

The transformation rule splits a single-phase aggregation into a partial and a merge:

cpp
// src/Processors/QueryPlan/Optimizations/Cascades/Rules/AggregationImplementations.cpp:92
/// Logical transformation that splits a single-phase Agg into a two-phase plan:
///   PartialAgg(input) -> ShuffleExchange -> FinalMergeAgg
///
/// PartialAgg computes partial aggregate states locally on each node without finalization.
/// FinalMergeAgg receives pre-aggregated states and merges them into final results.
/// The exchange between the two is inserted by the `DistributionEnforcer` based on the
/// distribution requirements set by the implementation rules on FinalMergeAgg.
///
/// A non-final aggregation is split too when it promises bucket order to a consumer outside the
/// plan: the merge then stays non-final and restores the bucket order over the gathered partials,
/// which is the distributed alternative to the single-node partial `AggregationImplementation`
/// leaves for such a step.
class TwoStageAggregationTransformation : public IOptimizationRule

and the split clones the aggregation step, marks the clone as non-final, and creates a MergingAggregatedStep for the merge half:

cpp
// src/Processors/QueryPlan/Optimizations/Cascades/Rules/AggregationImplementations.cpp:345
    /// Phase 1: partial aggregation - takes raw rows, outputs intermediate aggregate states.
    auto partial_step_ptr = cloneStepAs(*agg_step);
    auto * partial_step = partial_step_ptr.get();
    partial_step->setFinal(false);

The shuffle aggregation is only applicable in some cases, and every one of those reasons is a correctness reason:

cpp
// src/Processors/QueryPlan/Optimizations/Cascades/Rules/AggregationImplementations.cpp:64
    /// See `addShuffleAggregation` for why each condition disables the shuffle strategy.
    bool isShuffleApplicable() const
    {
        return !agg_step.getParams().keys.empty()
            && !agg_step.isGroupingSets()
            && !agg_step.getParams().overflow_row
            && agg_step.getParams().max_rows_to_group_by == 0;
    }

no group keys → a global aggregation has nothing to shuffle by;
grouping sets → the keys are the union of the sets’ keys, so shuffling by the union splits the rows of one grouping-set group across nodes;
an overflow row → every node would emit its own;
max_rows_to_group_by → the limit is a global contract, but each node would enforce it independently.

Single-key shuffle alternatives

A nice touch: for a multi-key GROUP BY, the optimizer also considers shuffling by one of the keys, which is cheaper (fewer bytes in the exchange) and still correct:

cpp
// src/Processors/QueryPlan/Optimizations/Cascades/Rules/AggregationImplementations.cpp:198
/// Single-key shuffle alternatives.
/// For aggregations with 2+ group-by keys, generate a shuffle alternative for each
/// individual key. Correctness: `GROUP BY (A, B)` with data shuffled by `A` is correct
/// because all rows with the same `(A, B)` have the same `A`, hence the same node.
void AggregationImplementation::StrategyEnumerator::addSingleKeyShuffleAggregations(const std::vector<size_t> & candidate_node_counts)

Enforcers: self-referential expressions

When a parent requires {1 node} and the cheapest child produces {4 nodes}, something has to bridge the gap. That something is an enforcer — an exchange step inserted by the optimizer.

Enforcers are the hairiest part of the implementation, because an enforcer’s input is the same group with relaxed requirements. That looks like a cycle:

cpp
// src/Processors/QueryPlan/Optimizations/Cascades/Rules/DistributionEnforcer.cpp:24
/// Produces self-referential enforcer expressions that bridge distribution gaps.
/// Each enforcer expression lives in the same group as the source expression; its
/// single input points back to the same group with normalized properties (node_count,
/// is_replicated, and sorting where needed) as the requirement - this lets the optimizer
/// pick the cheapest source with that distribution shape.  The optimizer recursively
/// satisfies this self-referential input through the normal task mechanism, enabling
/// natural enforcer composition (e.g. a sort and a gather compose into gather-then-sort,
/// see `SortingEnforcer`, without
/// bundling steps).
class DistributionEnforcer : public IOptimizationRule

The construction is centralised:

cpp
// src/Processors/QueryPlan/Optimizations/Cascades/Rules/DistributionEnforcer.cpp:104
void DistributionEnforcer::EnforcerEnumerator::addEnforcer(QueryPlanStepPtr step, ExpressionProperties input_required, SortDescription output_sorting)
{
    ExpressionProperties output_properties;
    output_properties.distribution = required_properties.distribution;
    output_properties.sorting = std::move(output_sorting);
    auto enforcer_expr = makeEnforcerExpression(
        expression, std::move(step), std::move(input_required), std::move(output_properties), EnforcedProperty::Distribution);

    rule.addPhysicalToMemo(enforcer_expr, required_properties, memo, result);
}

Two invariants keep the self-reference acyclic.

The first is that an enforcer carries an axis (Sorting or Distribution), and an enforcer that satisfies a wildcard axis only by over-providing on it isn’t eligible. A sorted enforcer can’t fill an empty-sort slot; a keyed exchange can’t fill an empty-columns slot:

cpp
// src/Processors/QueryPlan/Optimizations/Cascades/Group.cpp:159
        if (input_is_self_referential && candidate->enforced_property != EnforcedProperty::None)
        {
            /// Empty sort requirement: reject a sorted enforcer (it over-provides on the sort axis).
            if (required_properties.sorting.empty() && !candidate->properties.sorting.empty())
                return;
            /// Empty distribution-columns requirement: reject a keyed exchange. A sorting enforcer
            /// carrying keyed columns is still needed to feed a sorted gather, so keep it eligible.
            if (candidate->enforced_property == EnforcedProperty::Distribution
                && required_properties.distribution.columns.empty()
                && (!candidate->properties.distribution.columns.empty()
                    || !candidate->properties.distribution.hash_type_names.empty()))
                return;
        }

The second is that an enforcer must never evict a non-enforcer alternative from the best-implementation cache, because that alternative is the acyclic way out:

cpp
// src/Processors/QueryPlan/Optimizations/Cascades/Group.cpp:78
    /// An enforcer "satisfies" a weaker non-enforcer only by over-providing (e.g. a sorted gather
    /// covers an empty-sort requirement). Dropping the base would leave a self-referential enforcer
    /// chain with no acyclic alternative, so an enforcer never suppresses or evicts a distinct base.
    auto enforcer_over_provides_for = [](const GroupExpressionPtr & enforcer_candidate, const GroupExpressionPtr & base_candidate)
    {
        return enforcer_candidate->enforced_property != EnforcedProperty::None
            && base_candidate->enforced_property == EnforcedProperty::None
            && !(enforcer_candidate->properties == base_candidate->properties);
    };

The fixed point

Enforcers compose: a sort enables a sorted gather, which enables a gather. The Stage 3 loop iterates until no new enforcer is produced:

cpp
// src/Processors/QueryPlan/Optimizations/Cascades/Task.cpp:96
    /// Fixed-point loop: iterate over newly-added physical expressions until no
    /// new enforcers are produced.  Each iteration may create expressions that
    /// enable further enforcers (e.g. a sort enables a sorted `GatherExchange`).
    size_t enforced_up_to = 0;
    bool new_enforcers_created = true;
    while (new_enforcers_created)
    {
        new_enforcers_created = false;

Keeping the best implementation

Each group keeps a Pareto frontier of implementations, bucketed by distribution shape so that a lookup is O(1) plus a short scan:

cpp
// src/Processors/QueryPlan/Optimizations/Cascades/Group.cpp:73
void Group::updateBestImplementation(GroupExpressionPtr expression, const CostConfig & cost_config)
{
    UInt64 key = distributionKey(expression->properties.distribution);
    auto & bucket = best_implementations[key];

and the eviction rule is a domination test: an implementation is dropped when another one satisfies at least the same properties at a lower cost.

cpp
// src/Processors/QueryPlan/Optimizations/Cascades/Group.cpp:88
    /// Remove all known best expressions with higher cost and properties satisfied by the new expression.
    /// Only the matching distribution-shape bucket needs checking - `isSatisfiedBy` requires
    /// exact match on (node_count, is_replicated).
    for (auto best_it = bucket.begin(); best_it != bucket.end();)
    {
        if (expression->properties.isSatisfiedBy((*best_it)->properties) &&
            (*best_it)->cost->subtree_cost.total(cost_config) <= expression->cost->subtree_cost.total(cost_config) &&
            !enforcer_over_provides_for(*best_it, expression))
        {
            /// There is already a cheaper implementation that satisfies the same properties
            return;
        }

Failing closed

The search is bounded by a task count, not by branch-and-bound. And when the budget runs out, the query is rejected rather than planned from a partial memo:

cpp
// src/Processors/QueryPlan/Optimizations/Cascades/Optimizer.cpp:308
    /// Limit the time in terms of optimization tasks instead of wall clock time. This is done for stability of generated plans regardless of system load.
    /// Microsoft SQL Server's optimizer team describes this in Andy Pavlo's seminar: https://www.youtube.com/watch?v=pQe1LQJiXN0
    const size_t executed_tasks_limit = getCascadesTaskLimitParam(query_context, CascadesDefaults::DEFAULT_TASK_LIMIT);
    size_t executed_tasks_count = 0;
    for (; !tasks.empty() && executed_tasks_count < executed_tasks_limit; ++executed_tasks_count)
    {
        auto task = std::move(tasks.top());
        tasks.pop();
        task->execute(*this);
    }

cpp
// src/Processors/QueryPlan/Optimizations/Cascades/Optimizer.cpp:321
    /// Fail closed if the search did not finish within the task budget: building a plan from a
    /// partial memo can yield a non-minimal plan or a confusing failure deep inside buildBestPlan.
    /// Surface a clear error instead and point at the knob to raise the limit.
    if (!tasks.empty())
        throw Exception(ErrorCodes::SUPPORT_IS_DISABLED,
            "Cascades optimizer did not finish within the task budget of {} tasks "
            "(root group #{}, required properties {}, {} groups in memo, {} tasks left, next: {}). "
            "The distributed Cascades optimizer is experimental; set enable_cascades_optimizer = 0 "
            "or simplify the query.",
            executed_tasks_limit, root_group_id, root_required_properties.dump(),
            memo.getGroupCount(), tasks.size(), tasks.top()->describe());

The default budget is 100 000 tasks:

cpp
// src/Processors/QueryPlan/Optimizations/Cascades/OptimizerDefaults.h:17
constexpr size_t DEFAULT_TASK_LIMIT = 100000;

Trying it

sql
SET enable_cascades_optimizer = 1;
SET make_distributed_plan = 1;

SELECT n_name, SUM(o_totalprice) AS revenue
FROM orders
JOIN customer ON o_custkey = c_custkey
JOIN nation ON c_nationkey = n_nationkey
WHERE o_orderdate >= '1995-01-01' AND o_orderdate < '1995-04-01'
GROUP BY n_name
ORDER BY revenue DESC
SETTINGS send_logs_level = 'test';

The test log level prints the memo, every costed expression with its work/network/sequential breakdown, and the final plan — which is the intended way to understand why the optimizer chose what it chose.

Trade-offs

What it buys: plans that no fixed heuristic would produce. A broadcast of a tiny table instead of a shuffle of a huge one. A ReplicatedRead from shared storage instead of a network transfer. A two-phase aggregation instead of a gather. A sort per node instead of a sort of everything.

What it costs:

It is experimental. The setting is EXPERIMENTAL and off by default, and it only applies with make_distributed_plan = 1.
Join ordering is not part of it. This is the biggest difference from classical Cascades. ClickHouse fixes the join order first (with the existing dpsize/dphyp/greedy algorithms) and Cascades only optimises the distribution strategy. The published literature calls this the “split” design, and it loses the global optimum when the join order interacts with physical properties — which, in a distributed setting, it does.
The statistics are weak. Today they come from index analysis and from query-parameter hints. There’s no cardinality estimator as sophisticated as the one the pre-Cascades join orderer uses. A cost model on bad statistics picks the wrong plan confidently.
Only two parallelism levels are explored: {1 node} and {N nodes}. Intermediate counts were never chosen on TPC-H, and exploring them would multiply the search space.
The search can be exponential, which is why there’s a hard task budget and a fail-closed error. Classical Cascades would prune instead.
Some plan shapes are rejected outright — WITH TOTALS, ROLLUP, CUBE, extremes, PASTE JOIN, and reads that cannot be cloned across workers.

Wrapping up

Here’s the thing: the most interesting part of this code isn’t the optimizer. It’s the discipline around it.

Every place where the implementation deliberately deviates from the textbook — no branch-and-bound, a fail-closed budget, the enforcer-axis rules, the “never evict the acyclic fallback” rule — carries a comment explaining exactly why the textbook version would be wrong here. That’s rare, and it’s the part of the code most worth reading.

What to do about it: if you’re running a distributed ClickHouse cluster, turn enable_cascades_optimizer = 1 on a staging cluster, set send_logs_level = 'test', and read the memo for one of your real queries. You’ll see immediately whether your statistics are good enough for it to trust itself.

And if you hit the task budget, that’s not a bug — that’s the optimizer telling you it couldn’t afford to think. Fix the query shape, or raise the limit.