Skip to content

Commit 5c92390

Browse files
authored
perf(optimizer): EliminateCrossJoin fast-path for join-free plans (apache#22612)
## Which issue does this PR close? Closes apache#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 apache#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 apache#22298) is worth considering — see issue apache#22583 comments for discussion. Out of scope here.
1 parent 48adae4 commit 5c92390

1 file changed

Lines changed: 138 additions & 1 deletion

File tree

‎datafusion/optimizer/src/eliminate_cross_join.rs‎

Lines changed: 138 additions & 1 deletion
Original file line numberDiff line numberDiff line change
@@ -20,7 +20,7 @@ use crate::{OptimizerConfig, OptimizerRule};
2020
use std::sync::Arc;
2121

2222
use crate::join_key_set::JoinKeySet;
23-
use datafusion_common::tree_node::{Transformed, TreeNode};
23+
use datafusion_common::tree_node::{Transformed, TreeNode, TreeNodeRecursion};
2424
use datafusion_common::{NullEquality, Result};
2525
use datafusion_expr::expr::{BinaryExpr, Expr};
2626
use datafusion_expr::logical_plan::{
@@ -85,6 +85,17 @@ impl OptimizerRule for EliminateCrossJoin {
8585
plan: LogicalPlan,
8686
config: &dyn OptimizerConfig,
8787
) -> Result<Transformed<LogicalPlan>> {
88+
// Fast path: nothing to do if the plan contains no `Join` nodes.
89+
// Without this guard the rule still falls through to
90+
// `rewrite_children`, which walks the entire plan, processes
91+
// uncorrelated subqueries, and rewrites every direct child via
92+
// `map_children` (clone-on-write) — paid by every query in the
93+
// logical optimizer pipeline. Same shape as the
94+
// `plan_has_subqueries` fast-path landed in #22298.
95+
if !plan_has_joins(&plan) {
96+
return Ok(Transformed::no(plan));
97+
}
98+
8899
let plan_schema = Arc::clone(plan.schema());
89100
let mut possible_join_keys = JoinKeySet::new();
90101
let mut all_inputs: Vec<LogicalPlan> = vec![];
@@ -207,6 +218,34 @@ impl OptimizerRule for EliminateCrossJoin {
207218
}
208219
}
209220

221+
/// Returns `true` if `plan` contains at least one [`LogicalPlan::Join`]
222+
/// node, either directly in its tree *or* inside an embedded subquery
223+
/// plan reachable through `Expr::ScalarSubquery` / `Expr::InSubquery`
224+
/// / `Expr::Exists` / `Expr::SetComparison`.
225+
///
226+
/// Used as a fast-path gate at the top of [`EliminateCrossJoin::rewrite`]
227+
/// so that join-free plans skip the full recursive rewrite. Subquery
228+
/// traversal matters because `rewrite_children` also dives into
229+
/// uncorrelated subqueries via `map_uncorrelated_subqueries`; ignoring
230+
/// them here would skip optimizing a `CROSS JOIN` that sits only inside
231+
/// an `IN (SELECT ... FROM a, b)`-style predicate.
232+
///
233+
/// `LogicalPlan::apply_with_subqueries` already implements the
234+
/// "walk this node + every child + every subquery plan" traversal we
235+
/// need, so the helper is a thin wrapper around it.
236+
fn plan_has_joins(plan: &LogicalPlan) -> bool {
237+
let mut found = false;
238+
let _ = plan.apply_with_subqueries(|node| {
239+
if matches!(node, LogicalPlan::Join(_)) {
240+
found = true;
241+
Ok(TreeNodeRecursion::Stop)
242+
} else {
243+
Ok(TreeNodeRecursion::Continue)
244+
}
245+
});
246+
found
247+
}
248+
210249
fn rewrite_children(
211250
optimizer: &impl OptimizerRule,
212251
plan: LogicalPlan,
@@ -1418,4 +1457,102 @@ mod tests {
14181457

14191458
Ok(())
14201459
}
1460+
1461+
// ---------------- fast-path tests ----------------
1462+
1463+
/// `plan_has_joins` detects a `Join` at the root of the plan.
1464+
#[test]
1465+
fn plan_has_joins_detects_root_join() -> Result<()> {
1466+
let plan = LogicalPlanBuilder::from(test_table_scan_with_name("t1")?)
1467+
.cross_join(test_table_scan_with_name("t2")?)?
1468+
.build()?;
1469+
assert!(plan_has_joins(&plan));
1470+
Ok(())
1471+
}
1472+
1473+
/// `plan_has_joins` detects a `Join` nested under other operators.
1474+
#[test]
1475+
fn plan_has_joins_detects_nested_join() -> Result<()> {
1476+
let plan = LogicalPlanBuilder::from(test_table_scan_with_name("t1")?)
1477+
.cross_join(test_table_scan_with_name("t2")?)?
1478+
.filter(col("t1.a").eq(col("t2.a")))?
1479+
.project(vec![col("t1.a")])?
1480+
.build()?;
1481+
assert!(plan_has_joins(&plan));
1482+
Ok(())
1483+
}
1484+
1485+
/// Join-free plans return `false` so the fast-path in `rewrite` can
1486+
/// bail out before doing any recursion.
1487+
#[test]
1488+
fn plan_has_joins_returns_false_for_join_free_plan() -> Result<()> {
1489+
let plan = LogicalPlanBuilder::from(test_table_scan_with_name("t1")?)
1490+
.filter(col("a").gt(lit(0_i32)))?
1491+
.project(vec![col("a"), col("b")])?
1492+
.build()?;
1493+
assert!(!plan_has_joins(&plan));
1494+
Ok(())
1495+
}
1496+
1497+
/// `plan_has_joins` walks into embedded subquery plans — e.g. an
1498+
/// outer `Filter` whose predicate is `IN (SELECT ... FROM a, b)`
1499+
/// where the inner plan contains a `CROSS JOIN`. Without this the
1500+
/// fast-path would silently skip optimizing joins-in-subqueries
1501+
/// because `LogicalPlan::apply` doesn't descend into subquery
1502+
/// plan trees.
1503+
#[test]
1504+
fn plan_has_joins_detects_join_inside_subquery() -> Result<()> {
1505+
use datafusion_expr::in_subquery;
1506+
1507+
// Subquery plan that itself contains a join.
1508+
let subquery_plan =
1509+
LogicalPlanBuilder::from(test_table_scan_with_name("sub_t1")?)
1510+
.cross_join(test_table_scan_with_name("sub_t2")?)?
1511+
.project(vec![col("sub_t1.a")])?
1512+
.build()?;
1513+
1514+
// Outer plan with NO direct Join — only the IN subquery reaches one.
1515+
let outer = LogicalPlanBuilder::from(test_table_scan_with_name("t1")?)
1516+
.filter(in_subquery(col("a"), Arc::new(subquery_plan)))?
1517+
.project(vec![col("a")])?
1518+
.build()?;
1519+
1520+
assert!(
1521+
plan_has_joins(&outer),
1522+
"plan_has_joins must descend into subquery plans"
1523+
);
1524+
Ok(())
1525+
}
1526+
1527+
/// `EliminateCrossJoin::rewrite` short-circuits on join-free plans:
1528+
/// no recursion into `rewrite_children`, no `Transformed::yes`,
1529+
/// the plan comes back identical.
1530+
#[test]
1531+
fn rewrite_short_circuits_when_plan_has_no_joins() -> Result<()> {
1532+
let plan = LogicalPlanBuilder::from(test_table_scan_with_name("t1")?)
1533+
.filter(col("a").gt(lit(0_i32)))?
1534+
.project(vec![col("a"), col("b")])?
1535+
.build()?;
1536+
1537+
let starting_display = plan.display_indent_schema().to_string();
1538+
let starting_schema = Arc::clone(plan.schema());
1539+
1540+
let rule = EliminateCrossJoin::new();
1541+
let Transformed {
1542+
transformed,
1543+
data: optimized_plan,
1544+
..
1545+
} = rule.rewrite(plan, &OptimizerContext::new())?;
1546+
1547+
assert!(
1548+
!transformed,
1549+
"join-free plan should not be marked as transformed"
1550+
);
1551+
assert_eq!(&starting_schema, optimized_plan.schema());
1552+
assert_eq!(
1553+
starting_display,
1554+
optimized_plan.display_indent_schema().to_string()
1555+
);
1556+
Ok(())
1557+
}
14211558
}

0 commit comments

Comments
 (0)