You are viewing a plain text version of this content. The canonical link for it is here.
Posted to commits@datafusion.apache.org by gi...@apache.org on 2026/06/02 06:43:42 UTC
(datafusion) branch gh-readonly-queue/main/pr-22612-48adae4a3db1bdefcd87a12996abd5e25b506a6f created (now 5c92390921)
This is an automated email from the ASF dual-hosted git repository.
github-merge-queue[bot] pushed a change to branch gh-readonly-queue/main/pr-22612-48adae4a3db1bdefcd87a12996abd5e25b506a6f
in repository https://gitbox.apache.org/repos/asf/datafusion.git
at 5c92390921 perf(optimizer): EliminateCrossJoin fast-path for join-free plans (#22612)
This branch includes the following new commits:
new 5c92390921 perf(optimizer): EliminateCrossJoin fast-path for join-free plans (#22612)
The 1 revisions listed above as "new" are entirely new to this
repository and will be described in separate emails. The revisions
listed as "add" were already present in the repository and have only
been added to this reference.
---------------------------------------------------------------------
To unsubscribe, e-mail: commits-unsubscribe@datafusion.apache.org
For additional commands, e-mail: commits-help@datafusion.apache.org
(datafusion) 01/01: perf(optimizer): EliminateCrossJoin fast-path for join-free plans (#22612)
Posted by gi...@apache.org.
This is an automated email from the ASF dual-hosted git repository.
github-merge-queue[bot] pushed a commit to branch gh-readonly-queue/main/pr-22612-48adae4a3db1bdefcd87a12996abd5e25b506a6f
in repository https://gitbox.apache.org/repos/asf/datafusion.git
commit 5c92390921d8d667aa7cb7d56276a59ba36926f4
Author: Qi Zhu <zh...@gmail.com>
AuthorDate: Tue Jun 2 14:43:20 2026 +0800
perf(optimizer): EliminateCrossJoin fast-path for join-free plans (#22612)
## Which issue does this PR close?
Closes #22583.
## Rationale for this change
`EliminateCrossJoin::rewrite` 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.
This is paid by every query in the logical optimizer pipeline —
including simple point queries with no joins anywhere in the tree.
## Discussion on the issue
@neilconway raised the valid concern that a fast-path scan still does
*some* up-front work in the case where the rewrite does fire, and that
the deeper fix is mutable tree rewrites (avoiding the clone-on-write of
`TreeNode::rewrite` entirely). @alamb agreed and pointed at the in-place
`map_children_mut` / `plan_has_subqueries` infrastructure adriangb
landed in #22298 as the existing precedent.
This PR follows that precedent directly:
- **Same shape as `plan_has_subqueries`** — a read-only `apply` scan,
early-stops on the first matching node, allocates nothing.
- The scan cost on a query that *does* have joins is
O(depth-to-first-join) — typically a handful of nodes, well below the
cost of even one `map_children` clone-on-write the rewrite would
otherwise do.
- For the deeper "in-place mutable rewrite" direction,
`rewrite_children` here recurses via `optimizer.rewrite(input, config)`
per child — a different shape from `map_children_mut`'s `&mut`
traversal. Adapting that is a larger refactor and worth its own
follow-up; this PR doesn't block it.
## What changes are included in this PR?
- New `plan_has_joins(&LogicalPlan) -> bool` helper in
`eliminate_cross_join.rs` — `apply` walk that returns `true` on the
first `LogicalPlan::Join` it sees.
- Fast-path at the top of `EliminateCrossJoin::rewrite`: `if
!plan_has_joins(&plan) { return Ok(Transformed::no(plan)); }`.
Everything else is unchanged.
## Are these changes tested?
Four new unit tests in the existing `mod tests`:
- `plan_has_joins_detects_root_join`
- `plan_has_joins_detects_nested_join` (Join under Filter/Projection)
- `plan_has_joins_returns_false_for_join_free_plan`
- `rewrite_short_circuits_when_plan_has_no_joins` — end-to-end: rule's
`rewrite` returns `Transformed::no` and the plan comes back identical
(schema + display) on join-free input.
The existing 20 `EliminateCrossJoin` tests + the full 708-test
`datafusion-optimizer --lib` suite still pass. `cargo clippy -p
datafusion-optimizer --all-targets -- -D warnings` clean.
## Are there any user-facing changes?
No semantic change. Pure perf optimization, no new config knobs.
## Follow-ups
- A deeper architectural improvement (mutable tree rewrites following
the `map_children_mut` pattern from #22298) is worth considering — see
issue #22583 comments for discussion. Out of scope here.
---
datafusion/optimizer/src/eliminate_cross_join.rs | 139 ++++++++++++++++++++++-
1 file changed, 138 insertions(+), 1 deletion(-)
diff --git a/datafusion/optimizer/src/eliminate_cross_join.rs b/datafusion/optimizer/src/eliminate_cross_join.rs
index 8306d4b54c..95b70da443 100644
--- a/datafusion/optimizer/src/eliminate_cross_join.rs
+++ b/datafusion/optimizer/src/eliminate_cross_join.rs
@@ -20,7 +20,7 @@ use crate::{OptimizerConfig, OptimizerRule};
use std::sync::Arc;
use crate::join_key_set::JoinKeySet;
-use datafusion_common::tree_node::{Transformed, TreeNode};
+use datafusion_common::tree_node::{Transformed, TreeNode, TreeNodeRecursion};
use datafusion_common::{NullEquality, Result};
use datafusion_expr::expr::{BinaryExpr, Expr};
use datafusion_expr::logical_plan::{
@@ -85,6 +85,17 @@ impl OptimizerRule for EliminateCrossJoin {
plan: LogicalPlan,
config: &dyn OptimizerConfig,
) -> Result<Transformed<LogicalPlan>> {
+ // Fast path: nothing to do if the plan contains no `Join` nodes.
+ // Without this guard the rule still falls through to
+ // `rewrite_children`, which walks the entire plan, processes
+ // uncorrelated subqueries, and rewrites every direct child via
+ // `map_children` (clone-on-write) — paid by every query in the
+ // logical optimizer pipeline. Same shape as the
+ // `plan_has_subqueries` fast-path landed in #22298.
+ if !plan_has_joins(&plan) {
+ return Ok(Transformed::no(plan));
+ }
+
let plan_schema = Arc::clone(plan.schema());
let mut possible_join_keys = JoinKeySet::new();
let mut all_inputs: Vec<LogicalPlan> = vec![];
@@ -207,6 +218,34 @@ impl OptimizerRule for EliminateCrossJoin {
}
}
+/// Returns `true` if `plan` contains at least one [`LogicalPlan::Join`]
+/// node, either directly in its tree *or* inside an embedded subquery
+/// plan reachable through `Expr::ScalarSubquery` / `Expr::InSubquery`
+/// / `Expr::Exists` / `Expr::SetComparison`.
+///
+/// Used as a fast-path gate at the top of [`EliminateCrossJoin::rewrite`]
+/// so that join-free plans skip the full recursive rewrite. Subquery
+/// traversal matters because `rewrite_children` also dives into
+/// uncorrelated subqueries via `map_uncorrelated_subqueries`; ignoring
+/// them here would skip optimizing a `CROSS JOIN` that sits only inside
+/// an `IN (SELECT ... FROM a, b)`-style predicate.
+///
+/// `LogicalPlan::apply_with_subqueries` already implements the
+/// "walk this node + every child + every subquery plan" traversal we
+/// need, so the helper is a thin wrapper around it.
+fn plan_has_joins(plan: &LogicalPlan) -> bool {
+ let mut found = false;
+ let _ = plan.apply_with_subqueries(|node| {
+ if matches!(node, LogicalPlan::Join(_)) {
+ found = true;
+ Ok(TreeNodeRecursion::Stop)
+ } else {
+ Ok(TreeNodeRecursion::Continue)
+ }
+ });
+ found
+}
+
fn rewrite_children(
optimizer: &impl OptimizerRule,
plan: LogicalPlan,
@@ -1418,4 +1457,102 @@ mod tests {
Ok(())
}
+
+ // ---------------- fast-path tests ----------------
+
+ /// `plan_has_joins` detects a `Join` at the root of the plan.
+ #[test]
+ fn plan_has_joins_detects_root_join() -> Result<()> {
+ let plan = LogicalPlanBuilder::from(test_table_scan_with_name("t1")?)
+ .cross_join(test_table_scan_with_name("t2")?)?
+ .build()?;
+ assert!(plan_has_joins(&plan));
+ Ok(())
+ }
+
+ /// `plan_has_joins` detects a `Join` nested under other operators.
+ #[test]
+ fn plan_has_joins_detects_nested_join() -> Result<()> {
+ let plan = LogicalPlanBuilder::from(test_table_scan_with_name("t1")?)
+ .cross_join(test_table_scan_with_name("t2")?)?
+ .filter(col("t1.a").eq(col("t2.a")))?
+ .project(vec![col("t1.a")])?
+ .build()?;
+ assert!(plan_has_joins(&plan));
+ Ok(())
+ }
+
+ /// Join-free plans return `false` so the fast-path in `rewrite` can
+ /// bail out before doing any recursion.
+ #[test]
+ fn plan_has_joins_returns_false_for_join_free_plan() -> Result<()> {
+ let plan = LogicalPlanBuilder::from(test_table_scan_with_name("t1")?)
+ .filter(col("a").gt(lit(0_i32)))?
+ .project(vec![col("a"), col("b")])?
+ .build()?;
+ assert!(!plan_has_joins(&plan));
+ Ok(())
+ }
+
+ /// `plan_has_joins` walks into embedded subquery plans — e.g. an
+ /// outer `Filter` whose predicate is `IN (SELECT ... FROM a, b)`
+ /// where the inner plan contains a `CROSS JOIN`. Without this the
+ /// fast-path would silently skip optimizing joins-in-subqueries
+ /// because `LogicalPlan::apply` doesn't descend into subquery
+ /// plan trees.
+ #[test]
+ fn plan_has_joins_detects_join_inside_subquery() -> Result<()> {
+ use datafusion_expr::in_subquery;
+
+ // Subquery plan that itself contains a join.
+ let subquery_plan =
+ LogicalPlanBuilder::from(test_table_scan_with_name("sub_t1")?)
+ .cross_join(test_table_scan_with_name("sub_t2")?)?
+ .project(vec![col("sub_t1.a")])?
+ .build()?;
+
+ // Outer plan with NO direct Join — only the IN subquery reaches one.
+ let outer = LogicalPlanBuilder::from(test_table_scan_with_name("t1")?)
+ .filter(in_subquery(col("a"), Arc::new(subquery_plan)))?
+ .project(vec![col("a")])?
+ .build()?;
+
+ assert!(
+ plan_has_joins(&outer),
+ "plan_has_joins must descend into subquery plans"
+ );
+ Ok(())
+ }
+
+ /// `EliminateCrossJoin::rewrite` short-circuits on join-free plans:
+ /// no recursion into `rewrite_children`, no `Transformed::yes`,
+ /// the plan comes back identical.
+ #[test]
+ fn rewrite_short_circuits_when_plan_has_no_joins() -> Result<()> {
+ let plan = LogicalPlanBuilder::from(test_table_scan_with_name("t1")?)
+ .filter(col("a").gt(lit(0_i32)))?
+ .project(vec![col("a"), col("b")])?
+ .build()?;
+
+ let starting_display = plan.display_indent_schema().to_string();
+ let starting_schema = Arc::clone(plan.schema());
+
+ let rule = EliminateCrossJoin::new();
+ let Transformed {
+ transformed,
+ data: optimized_plan,
+ ..
+ } = rule.rewrite(plan, &OptimizerContext::new())?;
+
+ assert!(
+ !transformed,
+ "join-free plan should not be marked as transformed"
+ );
+ assert_eq!(&starting_schema, optimized_plan.schema());
+ assert_eq!(
+ starting_display,
+ optimized_plan.display_indent_schema().to_string()
+ );
+ Ok(())
+ }
}
---------------------------------------------------------------------
To unsubscribe, e-mail: commits-unsubscribe@datafusion.apache.org
For additional commands, e-mail: commits-help@datafusion.apache.org