perf(optimizer): EliminateCrossJoin walks the full plan tree even when there are no joins

[zhuqi-lucas]

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 like OneOf extensions where map_children always counts as transformed)
• Allocates fresh LogicalPlan nodes 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 OptimizerRule dispatcher. 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.

[neilconway]

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]

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.

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

• Optimize logical optimizer: skip map_subqueries + in-place rewriting #22298

Maybe we can do soemthing similar here

[alamb]

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

  	pub fn with_new_children_if_necessary(
  	plan: Arc<dyn ExecutionPlan>,
  	children: Vec<Arc<dyn ExecutionPlan>>,
  	) -> Result<Arc<dyn ExecutionPlan>> {
  	let old_children = plan.children();
  	assert_eq_or_internal_err!(
  	children.len(),
  	old_children.len(),
  	"Wrong number of children"
  	);
  	if children.is_empty()
  	|| children
  	.iter()
  	.zip(old_children.iter())
  	.any(|(c1, c2)| !Arc::ptr_eq(c1, c2))
  	{
  	plan.with_new_children(children)
  	} else {
  	Ok(plan)
  	}
  	}

• datafusion/datafusion/physical-expr-common/src/physical_expr.rs

  Line 752 in 633595d

  pub fn with_new_children_if_necessary(

[zhuqi-lucas]

Thanks @alamb and @neilconway for discussion, and the pointers on the issue thread. I went with the plan_has_subqueries shape 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]

Thanks @alamb and @neilconway for discussion, and the pointers on the issue thread. I went with the plan_has_subqueries shape 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.

Thanks 0-- this makes sense to me

And #22612 is ready for review for the current solution.

✅