ClickHouse Searches Join Orders with Dynamic Programming

TL;DR: Every DP algorithm here is the same three lines: enumerate splits of a relation set, cost each split with the NDV model, and keep the cheapest plan per relation set in a memo keyed by a bitmask. They differ in which splits they enumerate: DPsize enumerates all of them, DPhyp enumerates only connected ones, DPsub enumerates connected components and understands outer joins.

The previous article in this series explained the graph and the greedy search. The greedy search is O(N²) per step and gets stuck in local minima: it picks the cheapest pair now, and it may turn out that a different first pair would have been much better overall.

The principled fix is Bellman’s optimality principle applied to join trees:

If you know the best plan for every subset of relations, you can compute the best plan for any larger subset by trying every way of splitting it in two.

The catch is the state space. A plan is identified by the set of relations it covers, so the memo is a map from subsets to plans. For N relations there are 2^N subsets, and each one may be split in 2^(N-1) ways — for N=10 that is 2^10 · 2^9 ≈ 500 000 candidate evaluations, and for N=15 it is 2^28 ≈ 268 million. A naive implementation is not a query planner, it is a denial of service.

ClickHouse implements three variants that all share the same memo and cost model, and differ only in what they enumerate.

The memo

The memo is a BitSet → entry map:

cpp
// src/Processors/QueryPlan/Optimizations/joinOrderCommon.h:11
using PlanMemo = std::unordered_map<BitSet, DPJoinEntryPtr>;

The key is a BitSet — a wrapper over boost::dynamic_bitset — so a relation set is a machine word (or a few), and the map lookup is a hash of the bits.

The value is a DPJoinEntry: a node of the join tree being built, carrying its relation set, its two children, its cost, its selectivity, and its estimated output size.

cpp
// src/Processors/QueryPlan/Optimizations/joinOrder.h:32
struct DPJoinEntry
{
    BitSet relations;

    DPJoinEntryPtr left;
    DPJoinEntryPtr right;

    double cost = 0.0;
    /// NDV-based selectivity of the join predicates, see `SelectivityEstimate::reported_value`; reported by `EXPLAIN` as `estimated (NDV)`.
    double selectivity = 0.0;
    std::optional<UInt64> estimated_rows = {};
    std::unordered_map<String, ColumnStats> column_stats = {};

Every candidate evaluation goes through evaluateJoin, and it is where the “keep the cheapest” rule lives:

cpp
// src/Processors/QueryPlan/Optimizations/joinOrderDP.cpp:42
    auto selectivity = computeSelectivity(query_graph, dp_table, expression_selectivity, predicates, left->relations, right->relations);
    auto new_cost = computeJoinCost(left, right, selectivity);

    const BitSet combined_rels = left->relations | right->relations;
    auto current_best = dp_table.find(combined_rels);
    if (current_best != dp_table.end() && new_cost >= current_best->second->cost)
        return nullptr;

Note the early exit: if the memo already holds a plan for left ∪ right that is at least as cheap, the candidate is discarded. This is what makes the whole thing a dynamic program rather than an exhaustive search — and it is also the reason the memo must be keyed by the relation set alone, with no other state.

There is one subtlety in the kind of the join. If the two sides are connected only transitively (through an equivalence class), the join is an inner join even though no predicate directly connects them; the predicate is synthesised later:

cpp
// src/Processors/QueryPlan/Optimizations/joinOrderDP.cpp:50
    /// Transitively connected pairs are inner joins; their predicate is synthesized later.
    bool connected = !predicates.empty()
        || query_graph.areTransitivelyConnected(left->relations, right->relations);
    auto effective_kind = (connected && join_kind == JoinKind::Cross) ? JoinKind::Inner : join_kind;
    auto cardinality = estimateJoinCardinality(left, right, selectivity, effective_kind);

DPsize: enumerate everything

DPsize is the textbook bottom-up DP. It builds components in increasing size and, for each size, tries every way of splitting a component into two smaller ones:

cpp
// src/Processors/QueryPlan/Optimizations/joinOrderDPSize.cpp:59
    /// Components by size (index 0 is not used that why the size is N+1)
    std::vector<std::unordered_map<BitSet, DPJoinEntryPtr>> components(total_relations_count + 1);

and the enumeration:

cpp
// src/Processors/QueryPlan/Optimizations/joinOrderDPSize.cpp:76
    /// Iteratively build components of size from 2 to N
    for (size_t component_size = 2; component_size <= total_relations_count; ++component_size)
    {
        for (size_t smaller_component_size = 1; smaller_component_size <= component_size / 2; ++smaller_component_size)
        {
            const size_t bigger_component_size = component_size - smaller_component_size;

            for (const auto & [_, right] : components[smaller_component_size])
            {
                for (const auto & [_, left] : components[bigger_component_size])
                {
                    /// Do components overlap?
                    if (left->relations & right->relations)
                        continue;

                    /// If both components are of the same size then check each pair just once, not twice
                    if (smaller_component_size == bigger_component_size && *left->relations.begin() > *right->relations.begin())
                        continue;

The two continues are the standard symmetry eliminations: a split is unordered, so smaller/bigger is enough, and equal-size splits are checked once.

The plan is then gated on connectivity, because a plan that joins two unrelated components is a cross product and the optimizer does not want to invent one:

cpp
// src/Processors/QueryPlan/Optimizations/joinOrderDPSize.cpp:158
                    bool connected = !edge.empty()
                        || query_graph.areTransitivelyConnected(left->relations, right->relations);

                    LOG_TEST(log, "Considering join between {} and {}, predicates count: {}, connected: {}",
                        left->dump(), right->dump(), edge.size(), connected);

                    if (!connected)
                        continue;

And DPsize is inner-join only:

cpp
// src/Processors/QueryPlan/Optimizations/joinOrderDPSize.cpp:110
                    /// FIXME: Restrict to Inner joins for now because isValidJoinOrder seems to not handle non-Inner joins with swapped inputs correctly
                    if (*join_kind != JoinKind::Inner)
                        continue;

which is why the setting’s documentation says “currently only for Inner joins”.

DPhyp: enumerate only connected subsets

DPsize’s problem is that it enumerates disconnected intermediate results. On a sparse join graph — say 10 tables where each table joins to two others — most subsets of size 5 are disconnected, and DPsize pays for every one of them before throwing them away.

DPhyp (“Dynamic Programming Strikes Back”, Moerkotte & Neumann, SIGMOD 2008) fixes this by working on a hypergraph and enumerating only connected subgraphs (CSG) and their complements (CMP).

The hyperedge representation is a natural fit for SQL, because a join predicate may reference more than two relations:

cpp
// src/Processors/QueryPlan/Optimizations/joinOrderDPHyp.cpp:63
    /** A hyperedge in the join graph connecting a set of left relations to a set of right relations.
    * For simple binary predicates (A.x = B.y), |left| = |right| = 1.
    * For complex predicates (A.x = B.y + C.z), left and/or right may span multiple relations.
    */
    struct Hyperedge
    {
        BitSet left;
        BitSet right;
    };

A non-binary predicate is represented with the same set on both sides, which is a neat trick:

cpp
// src/Processors/QueryPlan/Optimizations/joinOrderDPHyp.cpp:294
/// Non-binary predicates like `f(A,B,C) = const` are represented as L={A,B,C}, R={A,B,C}

The neighbourhood function is what makes the enumeration connected-only: a relation is a neighbour of a set if some hyperedge has one side fully inside the set and the other side outside it.

cpp
// src/Processors/QueryPlan/Optimizations/joinOrderDPHyp.cpp:317
                if (isSubsetOf(edge.left, node_set))
                    neighbors |= edge.right;
                if (isSubsetOf(edge.right, node_set))
                    neighbors |= edge.left;

The enumeration is four functions, transcribed from the paper:

cpp
// src/Processors/QueryPlan/Optimizations/joinOrderDPHyp.cpp:357
/// The four functions below implement the core DPhyp enumeration from
/// "Dynamic Programming Strikes Back" (Moerkotte & Neumann, SIGMOD 2008), Section 3.
///
/// `emitCsg` (paper: EmitCsg, Sec 3.3) -- given a connected subgraph S1, generates all
///     complement seeds S2 = {v} from the neighborhood and extends them via `enumerateCmpRec`.
/// `enumerateCmpRec` (paper: EnumerateCmpRec, Sec 3.4) -- recursively extends complement S2
///     by adding neighboring nodes, emitting each valid csg-cmp pair.
/// `enumerateCsgRec` (paper: EnumerateCsgRec, Sec 3.2) -- recursively extends the primary
///     connected subgraph S1 by adding neighboring nodes.
/// `emitCsgCmp` (paper: EmitCsgCmp, Sec 3.5) -- evaluates a (S1, S2) pair for plan construction.

The cleverest part is the exclusion set, which is what stops the enumeration from producing every pair twice:

cpp
// src/Processors/QueryPlan/Optimizations/joinOrderDPHyp.cpp:421
/// Generate all complement seeds for a given connected subgraph S1.
/// Seeds are single neighbor nodes, processed in descending index order. Each processed seed is
/// added to the exclusion passed to later seeds, so a complement spanning several neighbors is grown
/// from only one of them and each (S1, S2) pair is enumerated exactly once.
///
/// `exclusion` (paper: X) = S1 | B_min(S1), where B_min(S1) = {v : v < min(S1)}.
/// B_min excludes all relations ordered before the smallest relation in S1.
/// This is the key mechanism that prevents generating symmetric pairs:
/// the complement can only contain relations ordered after the CSG's minimum.

The main loop seeds each single relation and grows:

cpp
// src/Processors/QueryPlan/Optimizations/joinOrderDPHyp.cpp:540
    /// Main DPhyp loop (paper: Solve, Sec 3.1).
    /// Seed with each single-relation CSG in descending index order.
    /// For each seed {v}, `emitCsg` finds complements (the other side of the join),
    /// and `enumerateCsgRec` grows {v} into larger connected subgraphs.
    /// The exclusion set B_v = {w : w < v} | {v} ensures each unordered (S1, S2) pair
    /// is considered exactly once (the side with the smaller min-index is always S1).

DPhyp has two hard limits. The subset enumeration uses a 64-bit bitmask, so it gives up at 64 relations:

cpp
// src/Processors/QueryPlan/Optimizations/joinOrderDPHyp.cpp:509
    /// DPhyp's subset enumeration uses a 64-bit bitmask, so it cannot handle neighborhoods
    /// larger than 63 relations. Bail out gracefully so the fallback algorithm chain can continue.
    if (num_relations >= 64)

and it cannot handle disconnected graphs at all, because it never considers cross products:

cpp
// src/Processors/QueryPlan/Optimizations/joinOrderDPHyp.cpp:573
    /// DPhyp cannot produce a plan for disconnected graphs (no cross products).
    /// The caller's fallback chain (e.g. dphyp,greedy) handles this.
    LOG_TRACE(log, "Failed to find best plan using DPhyp algorithm");
    return nullptr;

DPsub: connected components, and outer joins

DPsub is the algorithm from the “Building Query Compilers” paper, and it is the one that understands outer joins. Its state is a connected component of the join graph rather than an arbitrary subset:

cpp
// src/Processors/QueryPlan/Optimizations/joinOrderDPSub.cpp:553
/** Implements the `Dpsub` bottom-up dynamic programming algorithm for optimal bushy join tree generation.
* This algorithm constructs optimal join trees by iterating over subsets of the relations in an ascending order
* based on an integer bitmask (from 1 to 2^n - 2). This ordering ensures that for any relation subset S,
* the best plans for all its proper sub-plans (subsets S1 ⊂ S) have already been computed, thereby adhering to
* Bellman's optimality principle.
* This methodical evaluation of all connected subsets results in the creation of the best plan for each.
* The final answer is the optimal plan for the complete set of relations.

Its state fits in a UInt32:

cpp
// src/Processors/QueryPlan/Optimizations/joinOrderDPSub.cpp:571
    const size_t n = query_graph.relation_stats.size();
    using Bitvector = UInt32; // choose UInt64 or even UInt128 for larger sets
    // A budget cap on nr. of connected components considered by DPsub to avoid excessive optimization time on large join graphs.
    // This budget cap is obtained from empirical testing using different queries and join graphs.
    static constexpr UInt32 max_nr_ccps = 50'000;

— and if there are more relations than bits, it declines:

cpp
// src/Processors/QueryPlan/Optimizations/joinOrderDPSub.cpp:577
    if (n >= std::numeric_limits<Bitvector>::digits)
    {
        LOG_TRACE(log,
            "Number of relations {} exceeds the DP threshold {}, skipping DP optimization invoking greedy algorithm",
            n, std::numeric_limits<Bitvector>::digits);
        return nullptr;
    }

Outer joins in DPsub

The reason DPsub exists separately is that outer joins are not freely reorderable, and the rule is fiddly. DPsub encodes it as a required set per relation: the null-supplying relation of an outer join may only be joined against a side that contains every relation its ON clause mentions.

cpp
// src/Processors/QueryPlan/Optimizations/joinOrderDPSub.cpp:280
    auto check = [&](UInt32 lhs, UInt32 rhs) -> std::optional<JoinKind>
    {
        if (std::popcount(lhs) == 1)
        {
            const auto & restriction = dpsub_data.restriction_by_rel[std::countr_zero(lhs)];
            if (restriction.present)
            {
                /// If there are any bits set in `restriction.required`
                /// that are not set in `rhs`, the bitwise AND (&) results in a non-zero value
                if (restriction.required & ~rhs)
                    return {};
                return restriction.kind;
            }
        }
        return JoinKind::Inner;
    };

and then combines the two sides’ requirements, with a conflict rule at the end:

cpp
// src/Processors/QueryPlan/Optimizations/joinOrderDPSub.cpp:310
    if (left_join_type == JoinKind::Inner)
        return right_join_type;
    if (right_join_type == JoinKind::Inner)
        return left_join_type;
    if (left_join_type == JoinKind::Full && right_join_type == JoinKind::Full)
        return JoinKind::Full;

    /// Conflicting outer-join constraints, the order is not possible
    return {};

Conflict detectors

The per-relation restriction above is sound but incomplete: it rejects some reorderings that are actually legal. The “conflict detector” machinery is the attempt to be complete. The setting chooses one:

cpp
// src/Core/Settings.cpp:11272
    DECLARE(JoinOrderConflictDetector, query_plan_optimize_join_order_conflict_detector, JoinOrderConflictDetector::NONE, R"(
Only affects the `dpsub` join order algorithm. Selects the conflict detector that DPsub uses to
decide which join reorderings are valid. The following values are available:
 - `''` (default) - no conflict detector, DPsub uses the per-relation `ON` clause restriction
 - `'a'` - the CD-A conflict detector, which is correct but incomplete
 - `'c'` - the CD-C conflict detector, which is correct and complete
)", EXPERIMENTAL, \

The detector’s job is to decide, for a given split of the relation set, whether the outer-join operators that straddle it are still valid there. The check is a set-containment test per operator:

cpp
// src/Processors/QueryPlan/Optimizations/joinOrderDPSub.cpp:361
        /// Required-set containment. `forward` keeps the operator's (left, right) inputs aligned
        /// with (left_mask, right_mask); `mirrored` swaps them -- a valid equivalence for any of our
        /// operators via `reverseJoinKind` (Left<->Right, Full/Inner unchanged; for semi/anti it
        /// flips the preserved side). The two required sides are disjoint and, for a non-degenerate
        /// predicate, both non-empty, so at most one orientation can hold.
        bool forward = subset_of(op.required_left, left_mask) && subset_of(op.required_right, right_mask);
        bool mirrored = subset_of(op.required_left, right_mask) && subset_of(op.required_right, left_mask);

and the “fail closed” rule is important — when the orientation is ambiguous, the split is rejected rather than guessed:

cpp
// src/Processors/QueryPlan/Optimizations/joinOrderDPSub.cpp:392
        /// A non-inner operator whose orientation is still ambiguous (both sides admissible) would
        /// have its preserved side guessed; fail closed instead (see `reverseJoinKind`, which flips
        /// Left<->Right / the semi/anti preserved side while `buildPhysicalPlan` keeps the child order).
        if (forward && mirrored)
            return std::nullopt;

DPsub also refuses to run on a graph that only cross products hold together:

cpp
// src/Processors/QueryPlan/Optimizations/joinOrderDPSub.cpp:608
    /// Turn down a graph that only cross products hold together, before enumerating anything: DPsub
    /// cannot stitch its components, so the next algorithm in the chain plans the query instead.
    if (dpsub_data.disconnected_graph)

The budget and the fallback chain

Both the DPsize and DPhyp searches are bounded by a deterministic budget — a count of enumerated partial plans, not a wall-clock timer:

cpp
// src/Core/Settings.cpp:3121
DECLARE(UInt64, query_plan_optimize_join_order_max_searched_plans, 100000, R"(
Maximum number of partial plans the join order optimizer may enumerate before giving up and falling back to the next algorithm in `query_plan_optimize_join_order_algorithm`.
This bounds optimization time deterministically (independent of wall-clock) on dense join graphs such as cliques or stars, where the search space grows exponentially.
Set to 0 to disable the limit. Has no effect on the default `query_plan_optimize_join_order_limit`, where the search always stays well below this bound.
)", EXPERIMENTAL, \

The check is inside the enumeration loop:

cpp
// src/Processors/QueryPlan/Optimizations/joinOrderDPSize.cpp:95
                    ++searched_plans;
                    if (max_searched_plans && searched_plans > max_searched_plans)
                    {
                        LOG_TRACE(log, "Exceeded the limit of {} searched plans, falling back", max_searched_plans);
                        return nullptr;
                    }

and the cancellation check is polled only every 4096 plans, because it can send progress over the network:

cpp
// src/Processors/QueryPlan/Optimizations/joinOrderDPSize.cpp:101
                    /// `checkLimits` invokes the interactive cancel callback, which can send progress over
                    /// the network. Poll it once every few thousand pairs instead of on every one.
                    if ((searched_plans & 0xFFF) == 0)
                        checkLimits();

When the budget is blown, the algorithm returns nullptr — and the chain moves on:

cpp
// src/Processors/QueryPlan/Optimizations/joinOrder.cpp:371
    for (const auto & algorithm : enabled_algorithms)
    {
        LOG_TRACE(log, "Solving join order using {} algorithm", toString(algorithm));
        switch (algorithm)
        {
            case JoinOrderAlgorithm::DPSUB:
                best_plan = solveDPSubJoinOrder(query_graph);
                break;
            case JoinOrderAlgorithm::DPSIZE:
                best_plan = solveDPSizeJoinOrder(query_graph, max_searched_plans, query_status, interactive_cancel_callback);
                break;
            case JoinOrderAlgorithm::DPHYP:
                best_plan = solveDPHypJoinOrder(query_graph, max_searched_plans, query_status, interactive_cancel_callback);
                break;
            case JoinOrderAlgorithm::GREEDY:
                best_plan = solveGreedyJoinOrder(query_graph);
                if (!best_plan)
                    throw Exception(ErrorCodes::LOGICAL_ERROR, "Failed to find a valid join order with greedy algorithm");
                break;
        }

        if (best_plan)
            break;
    }

The greedy algorithm is the last resort and the only one that cannot fail — it can always produce a valid order, because the original order is always valid. That is why it is the default and the fallback.

Each algorithm also clears the memo when it starts, so a failed attempt does not poison the next one:

cpp
// src/Processors/QueryPlan/Optimizations/joinOrderGreedy.cpp:45
    /// Discard any partial state left by an earlier algorithm in the fallback chain
    /// (e.g. `dphyp,greedy`) so cost-model lookups via `getColumnStats` only see
    /// entries built by this run. `expression_selectivity` is cleared along with
    /// `dp_table` because multi-relation predicates resolve NDV through it.
    dp_table.clear();
    expression_selectivity.clear();

Choosing an algorithm

sql
-- Inner joins only, small graph, want the best plan:
SETTINGS query_plan_optimize_join_order_algorithm = 'dpsize';

-- Inner joins, sparse graph, want it fast:
SETTINGS query_plan_optimize_join_order_algorithm = 'dphyp';

-- Outer joins, want completeness:
SETTINGS query_plan_optimize_join_order_algorithm = 'dpsub';

-- Best of both: try the DP, fall back to greedy if it declines.
SETTINGS query_plan_optimize_join_order_algorithm = 'dphyp,greedy';

Trade-offs

The memo is the whole trick. Everything else in these files exists to make the memo’s key small and its value cheap. The key is a bitmask; the value is four numbers and two pointers.

The DP algorithms are not free, and the budget is what makes them safe. The 100 000-plan budget is a deterministic bound — two runs of the same query enumerate the same number of plans, so the optimizer’s runtime is predictable. A wall-clock timeout would have been simpler and worse: it would make the chosen plan depend on machine load, which is a nightmare to debug.

Outer joins are where completeness gets expensive. The per-relation restriction is cheap and rejects legal reorderings; the conflict detectors are complete but cost more per candidate, and they only apply to DPsub. This is why the setting’s scope is narrow: “Only affects the dpsub join order algorithm”.

The algorithms decline rather than guess. Every one of them has an explicit “give up” path — DPhyp on disconnected graphs, DPsub on graphs it cannot stitch, both on budget exhaustion — and every give-up hands the query to the next algorithm in the chain. A join-order optimizer that always returns a plan is safe; one that returns a wrong plan is not.

What the DP buys you in practice. For the star query, the greedy algorithm usually gets it right, because the cost model naturally prefers joining the small dimension tables first. The DP algorithms matter when the graph is a chain, or when a medium table must be joined to a large one before a cross-product-forming pair, and the greedy choice has to be revised two steps later. On those shapes, the DP plan can be an order of magnitude better — and on the shapes where they are not, the budget means you do not pay much.