Repository navigation
Commit a329cf3
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
- core/tests/physical_optimizer
- physical-optimizer/src
- physical-plan/src/joins
- sqllogictest/test_files
- docs/source/user-guide
| Original file line number | Diff line number | Diff line change | |
|---|---|---|---|
| |||
1672 | 1672 | | |
1673 | 1673 | | |
1674 | 1674 | | |
| 1675 | + | |
| 1676 | + | |
| 1677 | + | |
| 1678 | + | |
| 1679 | + | |
| 1680 | + | |
| 1681 | + | |
| 1682 | + | |
| 1683 | + | |
| 1684 | + | |
| 1685 | + | |
| 1686 | + | |
| 1687 | + | |
| 1688 | + | |
| 1689 | + | |
1675 | 1690 | | |
1676 | 1691 | | |
1677 | 1692 | | |
| |||
0 commit comments