Dandandan opened a new pull request, #24456: URL: https://github.com/apache/datafusion/pull/24456
## Which issue does this PR close? - Related to #7000 (join reordering / cost based optimizer). Happy to file a dedicated issue if preferred. ## Rationale for this change `JoinSelection` only makes *local* decisions: for one join at a time it picks the build side and the partition mode. The shape of the join tree stays whatever the logical planner produced, which for a query written as a flat list of relations is a left-deep tree in `FROM`-clause order. That order ignores how much each join reduces or inflates its inputs, so DataFusion can materialise millions of rows only to throw them away one join later. TPC-H q18 is the clearest case. The semi join sits at the *top* of the tree, so all 6,001,215 `customer ⋈ orders ⋈ lineitem` rows are built before it filters `orders` down to 57 rows. ## What changes are included in this PR? A dynamic programming join order enumerator, run at the start of `JoinSelection`: 1. **Extract** a maximal subtree of reorderable joins into a graph of opaque relations plus the predicates between them. Column-pruning `ProjectionExec`s between joins are seen through, since `ProjectionPushdown` has not folded them into the joins yet at this point. 2. **Enumerate** all connected orders with a `O(3^n)` DP over relation subsets — bushy shapes as well as left-deep — scored by a `C_out` cost model (the sum of intermediate cardinalities) built from the same estimates `estimate_inner_join_cardinality` uses. Graphs larger than the limit fall back to a greedy search. 3. **Rebuild** the subtree, re-deriving each join key and filter against the new schemas and setting join projections so intermediate results stay as narrow as before. Three kinds of predicate take part, which is what makes reordering sound: a tree of inner joins is equivalent to the cross product of its relations filtered by the conjunction of all its predicates, so any tree applying every predicate exactly once, where the columns it needs are available, computes the same rows. - **Equi-join edges** are applied at the node whose inputs separate their endpoints. - **Non-equi join filters** are re-attached at their lowest common ancestor, so a join carrying one no longer blocks reordering. - **Semi and anti joins** participate as *reducers*: they are filters on their output side, so the quantified side becomes a relation applicable at any node covering the columns its keys reference. This is what fixes q18. The rewrite is only applied when the winning order is strictly cheaper than the planner's, so already-optimal plans stay byte-identical. Subtrees whose inputs lack row-count statistics are left alone entirely. New config: `datafusion.optimizer.join_enumeration` (default `true`) and `datafusion.optimizer.join_enumeration_limit` (default `12`). ### Performance TPC-H SF1, parquet, best of 5 interleaved runs. q1 and q6 have no joins and serve as controls for this machine's noise floor (±3%): | Query | enumeration off | on | ratio | | --- | --- | --- | --- | | q18 | 96.2 ms | 64.5 ms | **0.67x** | | q7 | 67.3 ms | 48.7 ms | **0.72x** | | q2 | 20.8 ms | 18.0 ms | **0.87x** | | q21 | 93.9 ms | 81.6 ms | **0.87x** | | q8 | 53.2 ms | 50.1 ms | 0.94x | | q9 | 70.3 ms | 65.8 ms | 0.94x | | q5 | 59.2 ms | 61.0 ms | 1.03x (median; within control noise) | | q11 | 15.8 ms | 15.8 ms | 1.00x | | q1 *(control)* | 64.0 ms | 66.1 ms | 1.03x | | q6 *(control)* | 25.4 ms | 24.6 ms | 0.97x | 8 of 22 queries change plan; nothing regressed beyond the noise floor. q18, before and after — the `RightSemi` moves from the top of the tree to the bottom: ``` # before HashJoinExec: join_type=RightSemi, on=[(l_orderkey@0, o_orderkey@2)] HashJoinExec: join_type=Inner, on=[(o_orderkey@2, l_orderkey@0)] HashJoinExec: join_type=Inner, on=[(c_custkey@0, o_custkey@1)] # after HashJoinExec: join_type=Inner, on=[(o_orderkey@0, l_orderkey@0)] HashJoinExec: join_type=Inner, on=[(c_custkey@0, o_custkey@0)] HashJoinExec: join_type=RightSemi, on=[(l_orderkey@0, o_orderkey@0)] ``` Planning cost is not measurable at these sizes: a 12-relation chain join (the DP limit, 531k splits) adds ~0.3 ms. ## Are these changes tested? Yes. - 10 new tests in `datafusion/core/tests/physical_optimizer/join_enumeration.rs`: plan snapshots for a late reducer, a semi join, an anti join and a non-equi filter; the config flag; missing statistics; an already-optimal order; and end-to-end row-equality checks with the flag on and off. - A new section in `statistics_registry.slt` covering the reordered plan. That file's existing cases keep testing build-side selection with enumeration disabled, since with it on both cases settle on the same order. - All 22 TPC-H SF1 queries return byte-identical results with the flag on and off (20,108 rows compared). - `sqllogictests` (including `INCLUDE_TPCH=true`) and the extended test suite pass. ## Are there any user-facing changes? Two new config options, and query plans change where a cheaper join order exists. `datafusion.optimizer.join_enumeration = false` restores the previous behaviour. `joins::utils::max_distinct_count` is now `pub` so the enumerator can share one NDV estimate with the join cardinality code. ### Known limitations (follow-ups) - No transitive closure of equalities, so `a = b ∧ b = c` never yields `a = c` and some orders are unreachable. - The cost model is `C_out` only: blind to build/probe asymmetry, exchange cost, and to `CollectLeft` serialising the build. Enumeration creates small build sides, so it trips the `CollectLeft` threshold more often than before — worth a look for q5, which changes plan substantially without converting that into a win. - Distinct counts still fall back to `max - min + 1` (no NDV), which caps the accuracy of every estimate above. -- This is an automated message from the Apache Git Service. To respond to the message, please log on to GitHub and use the URL above to go to the specific comment. To unsubscribe, e-mail: [email protected] For queries about this service, please contact Infrastructure at: [email protected] --------------------------------------------------------------------- To unsubscribe, e-mail: [email protected] For additional commands, e-mail: [email protected]
