Repository navigation
perf(optimizer): EliminateCrossJoin walks the full plan tree even when there are no joins #22583
Description
Is your feature request related to a problem or challenge?
EliminateCrossJoin::rewrite in datafusion/optimizer/src/eliminate_cross_join.rs is called on every plan during logical optimization. The rule's body only does real work when the root (or its Filter child) is an inner Join; in every other case it falls through to rewrite_children, which recurses into the plan, processes uncorrelated subqueries, and rewrites every direct child via map_children (clone-on-write), then calls recompute_schema on the way back.
For plans with no joins anywhere in the tree, the rule still:
- Walks the entire plan via
map_uncorrelated_subqueries+map_children - Triggers schema recomputation if any node reported
transformed = true(which happens spuriously on plans likeOneOfextensions wheremap_childrenalways counts as transformed) - Allocates fresh
LogicalPlannodes on the recursion
This is paid by every query that goes through the logical optimizer pipeline, even simple ones like SELECT ... FROM single_table WHERE .... Production profiling on a reference-cluster query server shows EliminateCrossJoin taking a non-trivial share of plan time on point-query workloads that have no joins at all.
Related prior work that focused on the rule's EliminateCrossJoin hot-path itself (#10287, EPIC #9637) reduced allocation when the rule does fire, but did not add an early bail-out for the common "no joins in this plan" case.
Describe the solution you'd like
Add an apply (read-only) scan at the top of rewrite that bails out with Transformed::no(plan) when the tree contains no LogicalPlan::Join nodes. Equivalent shape to recent fast-paths added in the physical optimizer (e.g. #22521 for ensure_distribution):
use datafusion_common::tree_node::TreeNodeRecursion;
fn rewrite(&self, plan: LogicalPlan, config: &dyn OptimizerConfig) -> Result<Transformed<LogicalPlan>> {
let mut has_join = false;
plan.apply(|node| {
if matches!(node, LogicalPlan::Join(_)) {
has_join = true;
Ok(TreeNodeRecursion::Stop)
} else {
Ok(TreeNodeRecursion::Continue)
}
})?;
if !has_join {
return Ok(Transformed::no(plan));
}
// existing logic unchanged below ...
}apply is read-only; it does not clone-on-write the plan and short-circuits on the first match. For no-join plans the whole rule then costs one O(N) read-only walk. For plans that contain a join the behavior is unchanged.
Describe alternatives I've considered
- Leave it as-is. The rule is correct, just wasteful on no-join plans. Acceptable for clusters whose workload is join-heavy, costly for clusters whose workload is mostly point queries on single tables.
- Move the check into the
OptimizerRuledispatcher. Would need a generic "does this rule care about this plan" hook on the trait. Larger surface and not clearly worth it for one rule.
Additional context
Same pattern of "logical optimizer rule walks the full plan tree even when there is nothing to rewrite" likely exists for other rules. If this fast-path lands cleanly I am happy to audit the remaining logical-optimizer rules (e.g. DecorrelatePredicateSubquery, ExtractEquijoinPredicate) and submit follow-ups in the same shape.
Activity
neilconway commentedon May 28, 2026
Makes sense well enough, although it seems regrettable that we need to add additional work in the case when the rewrite fires, just to avoid some work when the rewrite doesn't fire. Queries that are expensive to optimize in the first place will almost always have joins, I would expect?
I don't have a concrete idea here, but I do wonder whether this (and other "fast-path" optimizer work) is a symptom of an underlying problem -- it should be possible to express tree rewrites in a way where we shouldn't do any copies or tree manipulation if the rewrite doesn't fire.
alamb commentedon May 28, 2026
Yes -- I think the core primitive that is needed to express this is mutable tree rewrites -- now we either need to walk/copy the entire tree or else do two passes
If we allowed mutations intead (aka
&mut) in some cases we could do the walk and then rewrite in place if needed without forcing a copy@adriangb did something like this for subqueries recently
Maybe we can do soemthing similar here
alamb commentedon May 28, 2026
Maybe we can use one of these functions to avoid recreating the entire plan:
datafusion/datafusion/physical-plan/src/execution_plan.rs
Lines 1189 to 1209 in 633595d
datafusion/datafusion/physical-expr-common/src/physical_expr.rs
Line 752 in 633595d
zhuqi-lucas commentedon May 29, 2026
Thanks @alamb and @neilconway for discussion, and the pointers on the issue thread. I went with the
plan_has_subqueriesshape since the precedent is already landed (#22298) and the cost profile matches — full PR description spells out why I think the deeper in-place rewrite is worth a separate PR rather than blocking this one.And #22612 is ready for review for the current solution.
alamb commentedon May 29, 2026
Thanks 0-- this makes sense to me
✅
perf(optimizer): EliminateCrossJoin fast-path for join-free plans (ap…