Repository navigation
Commit 5c92390
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
| Original file line number | Diff line number | Diff line change | |
|---|---|---|---|
| |||
20 | 20 | | |
21 | 21 | | |
22 | 22 | | |
23 | | - | |
| 23 | + | |
24 | 24 | | |
25 | 25 | | |
26 | 26 | | |
| |||
85 | 85 | | |
86 | 86 | | |
87 | 87 | | |
| 88 | + | |
| 89 | + | |
| 90 | + | |
| 91 | + | |
| 92 | + | |
| 93 | + | |
| 94 | + | |
| 95 | + | |
| 96 | + | |
| 97 | + | |
| 98 | + | |
88 | 99 | | |
89 | 100 | | |
90 | 101 | | |
| |||
207 | 218 | | |
208 | 219 | | |
209 | 220 | | |
| 221 | + | |
| 222 | + | |
| 223 | + | |
| 224 | + | |
| 225 | + | |
| 226 | + | |
| 227 | + | |
| 228 | + | |
| 229 | + | |
| 230 | + | |
| 231 | + | |
| 232 | + | |
| 233 | + | |
| 234 | + | |
| 235 | + | |
| 236 | + | |
| 237 | + | |
| 238 | + | |
| 239 | + | |
| 240 | + | |
| 241 | + | |
| 242 | + | |
| 243 | + | |
| 244 | + | |
| 245 | + | |
| 246 | + | |
| 247 | + | |
| 248 | + | |
210 | 249 | | |
211 | 250 | | |
212 | 251 | | |
| |||
1418 | 1457 | | |
1419 | 1458 | | |
1420 | 1459 | | |
| 1460 | + | |
| 1461 | + | |
| 1462 | + | |
| 1463 | + | |
| 1464 | + | |
| 1465 | + | |
| 1466 | + | |
| 1467 | + | |
| 1468 | + | |
| 1469 | + | |
| 1470 | + | |
| 1471 | + | |
| 1472 | + | |
| 1473 | + | |
| 1474 | + | |
| 1475 | + | |
| 1476 | + | |
| 1477 | + | |
| 1478 | + | |
| 1479 | + | |
| 1480 | + | |
| 1481 | + | |
| 1482 | + | |
| 1483 | + | |
| 1484 | + | |
| 1485 | + | |
| 1486 | + | |
| 1487 | + | |
| 1488 | + | |
| 1489 | + | |
| 1490 | + | |
| 1491 | + | |
| 1492 | + | |
| 1493 | + | |
| 1494 | + | |
| 1495 | + | |
| 1496 | + | |
| 1497 | + | |
| 1498 | + | |
| 1499 | + | |
| 1500 | + | |
| 1501 | + | |
| 1502 | + | |
| 1503 | + | |
| 1504 | + | |
| 1505 | + | |
| 1506 | + | |
| 1507 | + | |
| 1508 | + | |
| 1509 | + | |
| 1510 | + | |
| 1511 | + | |
| 1512 | + | |
| 1513 | + | |
| 1514 | + | |
| 1515 | + | |
| 1516 | + | |
| 1517 | + | |
| 1518 | + | |
| 1519 | + | |
| 1520 | + | |
| 1521 | + | |
| 1522 | + | |
| 1523 | + | |
| 1524 | + | |
| 1525 | + | |
| 1526 | + | |
| 1527 | + | |
| 1528 | + | |
| 1529 | + | |
| 1530 | + | |
| 1531 | + | |
| 1532 | + | |
| 1533 | + | |
| 1534 | + | |
| 1535 | + | |
| 1536 | + | |
| 1537 | + | |
| 1538 | + | |
| 1539 | + | |
| 1540 | + | |
| 1541 | + | |
| 1542 | + | |
| 1543 | + | |
| 1544 | + | |
| 1545 | + | |
| 1546 | + | |
| 1547 | + | |
| 1548 | + | |
| 1549 | + | |
| 1550 | + | |
| 1551 | + | |
| 1552 | + | |
| 1553 | + | |
| 1554 | + | |
| 1555 | + | |
| 1556 | + | |
| 1557 | + | |
1421 | 1558 | | |
0 commit comments