alamb opened a new issue, #26481: URL: https://github.com/apache/datafusion/issues/26481
# EPIC: Separate optimizer rules from correctness transformation rules DataFusion's physical optimizer currently mixes 1. Transformations required to make a plan executable (e.g. [`EnsureRequirements`][EnsureRequirements]) 2. Optimizations intended to make it faster. There are also several implicit assumptions that built-in rules make, such as: - [`WindowTopN`][WindowTopN] assumes filters have no embedded projections (see #21596). - [`JoinSelection`][JoinSelection] assumes join inputs can still be swapped. Running it after post-optimization filter pushdown creates dynamic filters can violate that assumption and cause an internal planning error (see #26106). Correctness depends on carefully ordering rules around implicit distribution and ordering enforcements, and on assumptions about what earlier rules have produced. This makes rules difficult to understand, compose, and extend as rewrites can invalidate requirements, miss optimization opportunities, or undo one another's work. This can also lead to redundancy (e.g multiple repeated passes in the optimizer like in #25355) These concerns motivated the [discussion leading to this epic][epic-discussion]. The goal of this epic is: 1. to separate correctness transformations from performance optimizations (perhaps by mirroring the logical [analyzer][AnalyzerRule]/[optimizer][OptimizerRule]) 2. Remove as many implicit assumptions as possible ## Proposed work (outline) - Define the correctness/optimization boundary and classify the existing rules (see #26171) - Migrate rules to preserve validity, including rules currently placed before enforcement. - Check schema, distribution, and ordering contracts, building on existing invariant checks. - Simplify assumptions between rules and clarify the contract for downstream extensions. - Measure planning cost and plan quality; establish prerequisites for safely repeating optimizer rules. ### Subtasks - [ ] #26171 - [ ] #25572 - [ ] Validate plans after appended/custom optimizer rules and identify the rule that broke a requirement (#26460). - [ ] Run sqllogictests under an alternative physical optimizer pipeline (#26152). - [ ] Stop distribution and sorting enforcement from undoing one another's work (#25360). - [ ] Make requirement enforcement reach a fixpoint in one application (#25362). - [ ] Preserve constant/equivalence facts across projection rewrites after enforcement (#26391). - [ ] Consider extending [`WindowTopN`][WindowTopN] to filters with embedded projections (optimization coverage; #21596). ## Related work and discussion - #26171 / #26351 - Phase split and initial migration: #25688, #25572. - Invariant regions and the alternative of removing assumptions: PoC #26360 - Concrete rule interactions: partitioning panic #21826, aggregate regressions #25983, aggregate simplification #26069. - Planning cost and repeated enforcement: #25355, rule-skipping proposal #25356, enforcement phases undoing one another #25360. - Safe repetition and convergence: enforcement fixpoint #25362, experiments and reapplication failures #25585. - Existing validation and gaps: [`ExecutionPlan::check_invariants`][check-invariants], wrapper rules dropping schema checks #25316. [epic-discussion]: https://github.com/apache/datafusion/pull/25688#issuecomment-6246223865 [check-invariants]: https://docs.rs/datafusion/latest/datafusion/physical_plan/trait.ExecutionPlan.html#method.check_invariants [EnsureRequirements]: https://docs.rs/datafusion/latest/datafusion/physical_optimizer/ensure_requirements/struct.EnsureRequirements.html [WindowTopN]: https://docs.rs/datafusion/latest/datafusion/physical_optimizer/window_topn/struct.WindowTopN.html [JoinSelection]: https://docs.rs/datafusion/latest/datafusion/physical_optimizer/join_selection/struct.JoinSelection.html [AnalyzerRule]: https://docs.rs/datafusion/latest/datafusion/optimizer/trait.AnalyzerRule.html [OptimizerRule]: https://docs.rs/datafusion/latest/datafusion/optimizer/trait.OptimizerRule.html -- 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]
