[I] Add explicit phase boundaries to optimizer rules for simplicity and safety [datafusion]

["2010YOUY01 (via GitHub)" <gi...@apache.org>]

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: github-unsubscribe@datafusion.apache.org.apache.org

For queries about this service, please contact Infrastructure at:
users@infra.apache.org


---------------------------------------------------------------------
To unsubscribe, e-mail: github-unsubscribe@datafusion.apache.org
For additional commands, e-mail: github-help@datafusion.apache.org