2010YOUY01 opened a new issue, #25894:
URL: https://github.com/apache/datafusion/issues/25894
This is a high-level heuristic for simplifying optimizer rewrites in
general, rather than something specific to this example. These are still
partial thoughts—I don't have extensive optimizer experience yet or a concrete
problem that requires this design.
# Motivating Example
Consider a projected join. Suppose the join's canonical output schema is:
```text
[c1, c2, c3, c4]
```
There are two ways to represent a plan that only needs `c1` and `c2`.
## Representation 1: explicit projection
```text
Projection(c1, c2)
Join(output=[c1,c2,c3,c4], projection=None)
```
## Representation 2: projection fused into the join
```text
Join(output=[c1,c2,c3,c4], projection=[c1,c2])
```
Projection fusion is only possible in some cases. For example, if the
projection computes `c1 + c2`, we still need an explicit `Projection` node.
The problem is that we now have multiple representations for semantically
equivalent plans. Other optimizer rules may therefore need to understand both
forms, which causes special cases to accumulate and increases rewrite
complexity.
For example, projection pushdown currently has logic to handle both
representations:
-
[https://github.com/apache/datafusion/blob/main/datafusion/physical-optimizer/src/projection_pushdown.rs#L92](https://github.com/apache/datafusion/blob/main/datafusion/physical-optimizer/src/projection_pushdown.rs#L92)
# Proposed Idea
Introduce explicit phase boundaries between optimizer rewrites.
For projection pushdown, the optimizer could maintain three stages with
invariants:
- **Canonicalization:** normalize equivalent representations into a single
optimizer-friendly shape. For example, represent projected joins using an
explicit `Projection` node rather than a projection fused into `Join`.
- **Optimization:** run optimizer rules while preserving this canonical
representation, so most rules only need to understand one shape.
- **Lowering:** near the end, convert the canonical representation into more
execution-friendly forms, such as fusing the `Projection` into `Join` where
possible.
The guiding heuristic is to **push lowering as late as possible**, so most
optimizer rules operate on a smaller and more predictable set of
representations and therefore have fewer special cases to handle. 
(AI reminds me this is a very common compiler technique, so the terms
lowering/... came from there)
Applying this idea on the projection pushdown example:
```text
// Optimizer Stage Split Example (for projection pushdown only)
// Phase 1: Canonicalization
//
// Normalize equivalent representations into one optimizer-friendly shape.
//
// Invariant after this phase:
// projected joins always use an explicit Projection node.
// e.g.
// Join(projection=[c1,c2])
//
// becomes:
//
// Projection(c1,c2)
// Join(projection=None)
initial_physical_planning
// ----- Phase boundary ----
// Phase 2: Optimization
//
// Run rewrites while preserving the canonical representation.
// Rules in this region can assume projections are explicit.
rule1
rule2
rule3
// ----- Phase boundary ----
// Phase 3: Lowering
//
// Convert the canonical representation into execution-friendly forms.
// After this point, multiple physical representations may exist.
rule4 // Fuse Projection into Join where possible
```
# Implementation
1. Figure out more specific cases where multiple equivalent representations
cause maintenance overhead today.
2. Enforce the invariant explicitly (e.g. sanity-check it after each rule
within a stage).
The main challenge is that projection fusion is only one example. Many
optimizer passes can introduce alternative representations for semantically
equivalent plans. If every transformation introduces its own phase boundary or
invariant, the phase structure itself could become difficult to maintain.
So the open question is whether there is a small set of meaningful global
phases and invariants that captures most of these cases, rather than
introducing many fine-grained stages.
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
To unsubscribe, e-mail: [email protected]
For queries about this service, please contact Infrastructure at:
[email protected]
---------------------------------------------------------------------
To unsubscribe, e-mail: [email protected]
For additional commands, e-mail: [email protected]
