Opensource internals

ClickHouse Reorders Joins by Turning the Join Tree into a Graph

15 min read Jay Hubbert

ClickHouse flattens a SQL join tree into a relation graph, picks a cheaper order with a greedy or DP search, and rebuilds the join steps from the winning tree.

TL;DR: The join tree you typed is flattened into a QueryGraph of relations and edges; a search algorithm (greedy by default, DP variants optionally) picks a cheaper binary tree over that graph; the plan is then rebuilt from scratch in the winning order, with a fresh JoinStepLogical per step.

A join order is the classic example of a decision that is trivial to state and catastrophic to get wrong.

sql 
SELECT * FROM a JOIN b ON a.id = b.id JOIN c ON b.id = c.id;

Written left-to-right, this is (a ⋈ b) ⋈ c. Written the other way it is a ⋈ (b ⋈ c). Both are legal SQL, they return the same rows, and one of them can be a hundred times faster than the other — because the intermediate result of the inner join is either 10 rows or 10 billion rows, and everything downstream pays for that.

The number of legal binary trees over N relations is the Catalan number C(N): 2 for N=2, 5 for N=3, 14 for N=4, 42 for N=5, 132 for N=6, 429 for N=7. For N=10 it is 16 796. A cost-based optimizer wants to look at all of them; a real query planner cannot afford to.

ClickHouse’s answer is a three-stage pipeline:

text 
   SQL join tree                QueryGraph                  DPJoinEntry tree
   (JoinStepLogical)     ┌──────────────────────┐        ┌────────────────────┐
   a ⋈ (b ⋈ c)   ──────►│ relations[]  edges[]  │  ────► │  Join(Join(Leaf))  │
                        │ join_kinds[]          │        │  cost, cardinality, │
                        │ column_equivalences   │        │  join_operator      │
                        └──────────────────────┘        └────────────────────┘
                                 │                              │
                          greedy / dpsize /                  rebuild:
                          dphyp / dpsub                     new JoinStepLogical
                                                                per step

This article walks the whole path: how the tree becomes a graph, how the graph becomes a search problem, and how the winning tree becomes a new plan.

The switch

Two settings control the whole thing. The first says how much to optimize:

cpp 
// src/Core/Settings.cpp:3115
DECLARE(UInt64, query_plan_optimize_join_order_limit, 10, R"(
Optimize the order of joins within the same subquery. Currently only supported for very limited cases.
Value is the maximum number of tables to optimize.
)", 0, \
        {"25.12", 1, 10, "Allow JOIN reordering with more tables by default"}, \
        {"25.9", 1, 1, "New setting"}) \

Ten relations is the default cap on how many relations the flattened graph may contain before the optimizer refuses to flatten further. The second says which algorithm to use:

cpp 
// src/Core/Settings.cpp:11263
DECLARE(JoinOrderAlgorithm, query_plan_optimize_join_order_algorithm, "greedy", R"(
Specifies which JOIN order algorithms to attempt during query plan optimization. The following algorithms are available:
 - 'greedy' - basic greedy algorithm - works fast but might not produce the best join order
 - 'dpsize' - implements DPsize algorithm currently only for Inner joins - considers all possible join orders and finds the most optimal one but might be slow for queries with many tables and join predicates.
 - 'dpsub' - implements DPsub algorithm which supports both inner and non-inner joins - considers all possible join orders and finds the most optimal one but might be slow for queries with many tables and join predicates.
 - 'dphyp' - implements DPhyp (Dynamic Programming via Hypergraph Partitioning) algorithm currently only for inner joins - explores the same search space as `dpsize` but enumerates only connected subgraph pairs, which generates fewer intermediate joins on sparse join graphs, at the cost of not considering cross products
Multiple algorithms can be specified as a comma-separated list, e.g. `dphyp,greedy`. They are tried in order; if an algorithm cannot handle the query (e.g. due to outer joins or disconnected components), the next one is used as a fallback.
)", EXPERIMENTAL, \
        {"25.12", "greedy", "greedy", "New experimental setting."}) \

Note the fallback semantics: the setting is a list, and each algorithm may decline the query, handing over to the next.

Before any of that, the optimizer checks whether the query is even eligible:

cpp 
// src/Processors/QueryPlan/Optimizations/optimizeJoin.cpp:1492
    const auto & join_operator = join_step->getJoinOperator();
    auto strictness = join_operator.strictness;
    auto kind = join_operator.kind;
    auto locality = join_operator.locality;
    if (!optimization_settings.query_plan_optimize_join_order_limit
        || (strictness != JoinStrictness::All && !isSwapOnlyJoinStrictness(strictness))
        || locality != JoinLocality::Unspecified
        || kind == JoinKind::Paste
        || !join_operator.residual_filter.empty()
    )
    {
        join_step->setOptimized();
        return;
    }

JoinStrictness::All is the plain INNER JOIN case. ANY/SEMI/ANTI joins are swap-only — they may exchange their two inputs but not be reordered around each other — and FULL JOIN is swap-only too:

cpp 
// src/Processors/QueryPlan/Optimizations/optimizeJoin.cpp:1513
    int query_graph_size_limit = safe_cast<int>(optimization_settings.query_plan_optimize_join_order_limit);
    if ((isSwapOnlyJoinStrictness(strictness) || isSwapOnlyJoinKind(kind)) && query_graph_size_limit > 2 && !cda_reorder_semi_anti)
        /// Do not reorder joins, only allow swap
        query_graph_size_limit = 2;

Building the graph

The graph builder walks the QueryPlan tree top-down. At each JoinStepLogical it asks two questions: can the left subtree be flattened into the same graph (the join becomes an edge rather than a subtree), and can the right subtree?

cpp 
// src/Processors/QueryPlan/Optimizations/optimizeJoin.cpp:691
    auto type_changing_sides = join_step->typeChangingSides();
    bool allow_left_subgraph = !type_changing_sides.contains(JoinTableSide::Left) && (isInnerOrCross(join_kind) || isLeft(join_kind));
    bool allow_right_subgraph = !type_changing_sides.contains(JoinTableSide::Right) && (isInnerOrCross(join_kind) || isRight(join_kind));

Three gates, each of which exists because of a real bug class:

  • Type-changing sides. A LEFT JOIN with join_use_nulls = 1 makes the right side’s columns Nullable. If the optimizer is allowed to move that relation elsewhere in the tree, the type change would be applied at the wrong step. The comment says it outright:

    cpp 
    // src/Processors/QueryPlan/Optimizations/optimizeJoin.cpp:504
            /// Do not flatten joins that have type-changing sides (e.g., LEFT JOIN
            /// with `join_use_nulls` making right-side columns Nullable). Flattening
            /// such joins allows the optimizer to reorder them, which can separate
            /// a relation from the join that causes its type change, leading to
            /// type changes being applied at the wrong step and the exception
            /// "Cannot fold actions for projection".

  • Join kind. The left subtree of a RIGHT JOIN may not be flattened (allow_left_subgraph requires isInnerOrCross(join_kind) || isLeft(join_kind)), because a RIGHT JOIN is not commutative with respect to null-extension.

  • Column-name clashes. Two relations that expose the same column name cannot be merged into one flat namespace:

    cpp 
    // src/Processors/QueryPlan/Optimizations/optimizeJoin.cpp:729
        if (std::ranges::any_of(lhs_cols, [&](const auto & name) { return rhs_cols.contains(name); }))
        {
            LOG_DEBUG(getLogger("optimizeJoin"), "Column name clash detected between join sides, disabling subgraph flattening");
            allow_left_subgraph = false;
            allow_right_subgraph = false;
        }

When a subtree is flattened, its relations become sibling leaves of the graph and the join between them becomes an edge. The builder merges the two child graphs, shifting the child’s relation ids so that the restrictions recorded for the outer joins keep pointing at the right relations:

cpp 
// src/Processors/QueryPlan/Optimizations/optimizeJoin.cpp:368
    for (auto & [id, restriction] : rhs.join_kinds)
    {
        restriction.first.shift(shift);
        lhs.join_kinds[id + shift] = std::move(restriction);
    }

The shape of a graph

The result is a small, explicit structure:

cpp 
// src/Processors/QueryPlan/Optimizations/joinOrder.h:89
struct QueryGraph
{
    std::vector<RelationStats> relation_stats;

    std::vector<JoinActionRef> edges;

    /// Operators of the original join tree, in tree (not enumeration) order. Populated during
    /// `buildQueryGraph` and consumed by the conflict detector (CD-A/CD-C) when it is enabled; empty
    /// otherwise. See `ConflictJoinOp`.
    std::vector<ConflictJoinOp> conflict_ops;

with a BitSet per relation set. The BitSet is a thin wrapper over boost::dynamic_bitset that tolerates operands of different widths:

cpp 
// src/Interpreters/JoinExpressionActions.h:34
class BitSet
{
private:
    using Base = boost::dynamic_bitset<>;

A relation set of {0, 3, 7} is one bitwise-OR away from another, which is exactly the operation the DP memo needs.

Reordering an inner join is free. Reordering an outer join is not: a LEFT JOIN b must be evaluated before b is joined to c, or the null-extension happens at the wrong moment. The graph records this as a restriction on the null-supplying relation:

cpp 
// src/Processors/QueryPlan/Optimizations/joinOrder.h:105
    /// Restriction for a null-supplying relation of an outer join.
    /// Maps (relation id) -> (set of relations referenced by the outer join's ON clause, join kind).
    /// The relation may be joined (as a singleton side) only against a set that contains all
    /// relations its ON clause depends on; the remaining relations may be joined outside.
    std::unordered_map<size_t, std::pair<BitSet, JoinKind>> join_kinds;

and the builder fills it in when it sees a LEFT/RIGHT/FULL join:

cpp 
// src/Processors/QueryPlan/Optimizations/optimizeJoin.cpp:849
    if (isRightOrFull(join_kind))
    {
        if (lhs_count != 1)
            throw Exception(ErrorCodes::LOGICAL_ERROR, "JoinStepLogical with RIGHT or FULL join must have exactly one left input, but has {}", lhs_count);
        join_expression_sources.set(0, false);
        query_graph.join_kinds[0] = std::make_pair(join_expression_sources, join_kind);
    }
    if (isLeftOrFull(join_kind))
    {
        if (rhs_count != 1)
            throw Exception(ErrorCodes::LOGICAL_ERROR, "JoinStepLogical with LEFT or FULL join must have exactly one right input, but has {}", rhs_count);
        join_expression_sources.set(total_inputs - 1, false);
        query_graph.join_kinds[total_inputs - 1] = std::make_pair(join_expression_sources, join_kind);
    }

The ON-clause predicates of an outer join are pinned to the step that joins the null-supplying relation, because there they mean “matching” and not “filtering”:

cpp 
// src/Processors/QueryPlan/Optimizations/joinOrder.h:111
    /// Predicates from the ON clause of an outer join, mapped to the id of the null-supplying
    /// relation. Such a predicate must be applied in the ON clause of the join step that joins
    /// this relation: it affects matching, not filtering (rows of the preserved side are kept
    /// even when the predicate doesn't hold).
    /// All other predicates are filters: they may be applied at any step where all their source
    /// relations are available, but they must not be merged into an outer join's ON clause -
    /// they go to the post-join `residual_filter` instead.
    std::unordered_map<JoinActionRef, size_t> outer_join_conditions;

Every candidate join order is then checked against these restrictions by isValidJoinOrder, which is a small, sharp function:

cpp 
// src/Processors/QueryPlan/Optimizations/joinOrderBitSet.cpp:14
    auto check = [&](const auto & lhs, const auto & rhs) -> std::optional<JoinKind>
    {
        auto rel_id = lhs.getSingleBit();
        if (rel_id.has_value())
        {
            auto it = query_graph.join_kinds.find(rel_id.value());
            if (it != query_graph.join_kinds.end())
            {
                if (isSubsetOf(it->second.first, rhs))
                    return it->second.second;
                return {};
            }
        }
        return JoinKind::Inner;
    };

If the restricted relation’s dependency set is not a subset of the other side, the pair is simply not joinable — the function returns an empty optional and the candidate is discarded. The comment at the bottom of the function explains the classic case:

cpp 
// src/Processors/QueryPlan/Optimizations/joinOrderBitSet.cpp:55
    /// Conflict, join is not possible:
    /// FROM t1 LEFT JOIN t2 LEFT JOIN t3
    /// t1 -> Inner, t2 -> Left, t3 -> Left
    /// Cannot do (t2 x t3)
    return {};

Transitive predicates

A.x = B.x AND B.x = C.x implies A.x = C.x, and an optimizer that can see that can consider joining A to C directly. ClickHouse builds equivalence classes over the join keys:

cpp 
// src/Processors/QueryPlan/Optimizations/joinOrder.h:120
    /// Column equivalence classes derived from equi-join edges (e.g., A.x = B.x AND B.x = C.x
    /// implies A.x, B.x, C.x are all equivalent). Used by the join order optimizer to detect
    /// transitive connectivity between relations without synthesizing extra edges.
    /// Stored as alias-resolved JoinActionRef-s pointing to INPUT nodes.
    EquivalenceClasses<JoinActionRef> column_equivalences;

and it refuses to build a class across an outer join, because an outer join’s equality does not hold for the null-padded rows:

cpp 
// src/Processors/QueryPlan/Optimizations/joinOrder.cpp:140
        /// Skip predicates involving outer-joined relations: when a LEFT/RIGHT/FULL JOIN
        /// doesn't match, the outer side produces NULLs, so the equality doesn't hold
        /// for all rows and the transitive equivalence would be invalid.

The synthesis happens after the search, as a post-pass over the winning tree, so that the search itself can use the connectivity without materialising redundant predicates:

cpp 
// src/Processors/QueryPlan/Optimizations/joinOrder.cpp:262
        /// Phase 2: Synthesize predicates for equivalence classes spanning both subtrees.

and the synthesized predicate is a real one, added to the join operator:

cpp 
// src/Processors/QueryPlan/Optimizations/joinOrder.cpp:311
                    expressions.push_back(JoinActionRef::transform(
                        {member, other},
                        JoinActionRef::AddFunction(JoinConditionOperator::Equals)));

The default algorithm is the simplest possible one: repeatedly pick the pair of components whose join is cheapest, merge them, repeat.

cpp 
// src/Processors/QueryPlan/Optimizations/joinOrderGreedy.cpp:52
    std::deque<std::shared_ptr<DPJoinEntry>> components;
    for (size_t i = 0; i < query_graph.relation_stats.size(); ++i)
    {
        const auto & rel = query_graph.relation_stats[i];
        components.push_back(std::make_shared<DPJoinEntry>(i, rel.estimated_rows, rel.column_stats));
    }

Every iteration scans all pairs:

cpp 
// src/Processors/QueryPlan/Optimizations/joinOrderGreedy.cpp:69
        for (size_t i = 0; i < components.size(); i++)
        {
            for (size_t j = i + 1; j < components.size(); j++)
            {
                auto left = components[i];
                auto right = components[j];

                auto join_kind = isValidJoinOrder(query_graph, left->relations, right->relations);
                if (!join_kind)
                    continue;

The cost of a candidate is the cost of the two inputs plus the estimated number of matched pairs the join produces:

cpp 
// src/Processors/QueryPlan/Optimizations/joinOrderCommon.h:223
inline double computeJoinCost(const DPJoinEntryPtr & left, const DPJoinEntryPtr & right, const SelectivityEstimate & selectivity)
{
    return left->cost + right->cost + estimateJoinedRows(selectivity, left->estimated_rows, right->estimated_rows);
}

The subtlety is the tie-break. A pair with no equality predicate is a cross product, and a cross product’s cost estimate is rows_left * rows_right — which is enormous — unless one side has no row estimate at all, in which case the missing side is charged as a single row and the cross product looks free. The greedy algorithm guards against that by preferring any equi-connected pair over any non-equi pair regardless of cost:

cpp 
// src/Processors/QueryPlan/Optimizations/joinOrderGreedy.cpp:90
                /// An equi-connected pair always supersedes one without an equi key, regardless of
                /// cost: without an equi predicate the cost estimate is essentially a cross product
                /// (a relation without a row estimate makes it look arbitrarily small), so such a
                /// pair that happened to be evaluated first must not shadow valid equi-joined plans.
                if (!best_plan || (equi_connected && !best_plan_equi_connected)
                    || (equi_connected == best_plan_equi_connected && current_cost < best_plan->cost))

There is a second subtlety: a filter predicate that mentions one relation only must not be smuggled into an outer join’s ON clause, where it would change matching semantics:

cpp 
// src/Processors/QueryPlan/Optimizations/joinOrderGreedy.cpp:102
                    for (const auto * e : edges)
                    {
                        /// A filter predicate applied at an outer join step must not go to the
                        /// ON clause, where it would affect matching instead of filtering and
                        /// let non-matching rows of the preserved side survive NULL-extended.
                        /// Apply it after the join instead.
                        if (is_inner_step || query_graph.outer_join_conditions.contains(*e))
                            join_operator.expression.push_back(*e);
                        else
                            join_operator.residual_filter.push_back(*e);
                    }

The merge itself is a two-line splice, and the search ends with exactly one component:

cpp 
// src/Processors/QueryPlan/Optimizations/joinOrderGreedy.cpp:140
        components.erase(components.begin() + std::max(best_i, best_j));
        components.erase(components.begin() + std::min(best_i, best_j));
        components.push_front(best_plan);
        dp_table[best_plan->relations] = best_plan;

Rebuilding the plan

The search produces a DPJoinEntry tree. Turning it back into a QueryPlan is the second half of the work, and it is a rebuild, not an edit: the original JoinStepLogical nodes are discarded and new ones are constructed.

The tree is flattened into a post-order sequence, so that each step’s children are already built when the step itself is built:

cpp 
// src/Processors/QueryPlan/Optimizations/optimizeJoin.cpp:868
static std::vector<DPJoinEntry *> getJoinTreePostOrderSequence(DPJoinEntryPtr root)
{
    std::vector<DPJoinEntry *> result;
    result.reserve(root->relations.count() * 2);

Then a stack machine walks it. Leaves push the original read node; join nodes pop two children and push the new join step:

cpp 
// src/Processors/QueryPlan/Optimizations/optimizeJoin.cpp:1081
    for (size_t entry_idx = 0; entry_idx < sequence.size(); ++entry_idx)
    {
        auto * entry = sequence[entry_idx];
        if (entry->isLeaf())
        {
            /// Base relation, use this step as input node
            size_t relation_id = safe_cast<size_t>(entry->relation_id);
            if (relation_id >= input_nodes.size())
                throw Exception(ErrorCodes::LOGICAL_ERROR, "Invalid relation id: {}, input nodes size: {}", relation_id, input_nodes.size());
            node_stack.push(input_nodes[relation_id]);
        }
        else
        {
            /// Combine two nodes from the stack into a single join operation
            auto * left_child_node = node_stack.top();
            node_stack.pop();
            auto * right_child_node = node_stack.top();
            node_stack.pop();

At this point one more decision is made: which side builds the hash table. The estimator knows the row count of each side, and for a hash join you want the smaller side in the hash table:

cpp 
// src/Processors/QueryPlan/Optimizations/optimizeJoin.cpp:1119
            auto lhs_estimation = entry->left->estimated_rows;
            auto rhs_estimation = entry->right->estimated_rows;

            bool swap_on_sizes = optimization_settings.join_swap_table.has_value()
                ? optimization_settings.join_swap_table.value()
                : entry->join_method == JoinMethod::Hash && lhs_estimation && rhs_estimation
                    && lhs_estimation.value() < rhs_estimation.value();

            bool flip_join = has_prepared_storage_at_left || (!has_prepared_storage_at_right && swap_on_sizes);

and the flip reverses the join kind, because a LEFT join flipped becomes a RIGHT join:

cpp 
// src/Processors/QueryPlan/Optimizations/optimizeJoin.cpp:1146
            if (flip_join)
            {
                /// For hash joins, we want to keep the smaller side on the right
                std::swap(left_rels, right_rels);
                std::swap(left_child_node, right_child_node);
                join_operator.kind = reverseJoinKind(join_operator.kind);
            }

Finally the new step is created and the estimates are attached to it, so that EXPLAIN can show them:

cpp 
// src/Processors/QueryPlan/Optimizations/optimizeJoin.cpp:1299
            auto join_step = std::make_unique<JoinStepLogical>(
                left_header_ptr,
                right_header_ptr,
                std::move(join_operator),
                std::move(current_expression_actions),
                actions_after_join,
                join_settings,
                sorting_settings);
cpp 
// src/Processors/QueryPlan/Optimizations/optimizeJoin.cpp:1323
            join_step->setOptimized(entry->estimated_rows, entry->column_stats, imprecise_estimate, entry->cost, entry->selectivity, cluster_id);

The imprecise_estimate flag is the honest part: it is true if any leaf of the subtree had an imprecise estimate, and it makes EXPLAIN render the row count with a ~~ prefix:

cpp 
// src/Processors/QueryPlan/JoinStepLogical.cpp:335
    if (imprecise_estimate)
        description.emplace_back("ResultRows", result_rows_estimation ? fmt::format("~~{}", result_rows_estimation.value()) : "unknown");
    else
        description.emplace_back("ResultRows", result_rows_estimation ? toString(result_rows_estimation.value()) : "unknown");

What it buys you, and what it costs

The win. For a star query — one big fact table, several small dimension tables — the difference between joining the dimensions first and joining them last is the difference between a 10-row intermediate and a 10-billion-row one. The greedy algorithm gets this right for the common shapes, and the DP algorithms get it right more often.

The cost. The optimizer has to be right, and “right” here means “produces the same rows”. The restrictions above are all consequences of cases where a reordering changed the result. The join_kinds restriction, the outer_join_conditions pinning, the type-change gate, the column-name-clash check, the join_use_nulls gate on null-rejection reasoning — each one exists because a simpler rule produced a wrong answer.

The cost of being wrong. A join-order optimizer that picks a bad order does not produce wrong rows, it produces slow queries. That is why the default algorithm is the cheap one and the expensive ones are opt-in and experimental.

The escape hatch.

sql 
SELECT * FROM a JOIN b ON a.id = b.id JOIN c ON b.id = c.id
SETTINGS query_plan_optimize_join_order_algorithm = 'greedy';

and, to see what the optimizer thinks:

sql 
EXPLAIN actions = 1, compact = 1, pretty = 1
SELECT * FROM t1 INNER JOIN t2 ON t1.id = t2.id;
text 
Join (JOIN FillRightFirst)
│  t1[100] ⋈ t2[100]
│  Type: inner | Strictness: all | Algorithm: SpillingHashJoin(HashJoin)
│  Cost: estimated 100.00
│  Selectivity: estimated (NDV) 0.01
│  Output rows: estimated 100.00
│  Left: rows estimated 100.00
│  Right: rows estimated 100.00
│  Join conditions: id = id

The number in brackets is the estimated row count of the relation, and the Cost line is the number the optimizer minimised. The next article in this series digs into where those numbers come from.

ClickhouseQuery planningJoinsOptimizerInternals