Skip to content

Commit a329cf3

Browse files
Dandandanclaude
andcommitted
feat: cost-based join order enumeration in JoinSelection
`JoinSelection` only made local decisions -- the build side and partition mode of one join at a time -- so the shape of the join tree stayed whatever the logical planner produced. For a query written as a flat list of relations that is a left-deep tree in `FROM`-clause order, which ignores how much each join reduces or inflates its inputs. Add a dynamic programming enumerator that flattens a subtree of reorderable joins into a graph of opaque relations plus the predicates between them, searches every connected order (bushy as well as left-deep) under a `C_out` cost model built from the same cardinality estimates the rest of the rule uses, and rebuilds the subtree only when the winner is strictly cheaper than the planner's order. Semi and anti joins take part as reducers: they are filters on their output side, so their quantified side becomes a relation that may be applied at any node covering the columns its keys reference. Non-equi join filters are re-attached at their lowest common ancestor, so a join carrying one no longer blocks reordering. Controlled by `datafusion.optimizer.join_enumeration` (default on) and `datafusion.optimizer.join_enumeration_limit`. TPC-H SF1, best of 5 interleaved runs: q18 0.67x, q7 0.72x, q2 0.87x, q21 0.87x, q8 0.94x, q9 0.94x, and nothing regressed beyond the noise floor measured on join-free control queries. All 22 queries return byte-identical results with the flag on and off. Co-Authored-By: Claude Opus 5 <[email protected]>
1 parent bb038a6 commit a329cf3

11 files changed

Lines changed: 1829 additions & 7 deletions

File tree

‎datafusion/common/src/config.rs‎

Lines changed: 15 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -1672,6 +1672,21 @@ config_namespace! {
16721672
/// query is used.
16731673
pub join_reordering: bool, default = true
16741674

1675+
/// When set to true, the physical plan optimizer enumerates alternative
1676+
/// join orders for connected subtrees of inner hash joins and picks the
1677+
/// cheapest one from cardinality estimates, considering bushy shapes as
1678+
/// well as left-deep ones. Subtrees whose inputs lack row count
1679+
/// statistics, and subtrees whose original order is already the cheapest,
1680+
/// are left untouched.
1681+
pub join_enumeration: bool, default = true
1682+
1683+
/// Maximum number of inputs in a join subtree for which
1684+
/// `join_enumeration` runs its exhaustive dynamic programming search.
1685+
/// Larger subtrees fall back to a greedy search. The exhaustive search
1686+
/// costs `O(3^n)` in the number of inputs, so values above 16 are
1687+
/// clamped to 16.
1688+
pub join_enumeration_limit: usize, default = 12
1689+
16751690
/// When set to true, the physical plan optimizer uses the pluggable
16761691
/// `StatisticsRegistry` for statistics propagation across operators.
16771692
/// This enables more accurate cardinality estimates compared to each

0 commit comments

Comments
 (0)