adriangb commented on issue #25459: URL: https://github.com/apache/datafusion/issues/25459#issuecomment-5805723665
## Optimizer convergence Two rule fights stop plans from reaching a fixed point before `max_passes`. `PushDownFilter` is one side of each fight. I checked both on `main` at 95bb0a0dfa. ### 1. `PushDownFilter` and `PushDownLeafProjections` (#14540, #25455) On `main`, `push_down_filter`, `push_down_leaf_projections` and `optimize_projections` change the #14540 plan in every pass. The loop stops after 3 passes only because it sees a plan that it saw before. With `max_passes = 10` it also stops after 3 passes. Thus the cost is one extra pass. With #25455, the last pass changes nothing. ### 2. `PushDownFilter` and `CommonSubexprEliminate` never converge This is the fight in the original title of #14540. #25455 does not fix it. I propose a new issue for it and a row in the "Open bugs" table. Reproduction (the query is already in `floor_preimage.slt`): ```sql CREATE TABLE test_data (id INT, int_val INT) AS VALUES (1, 100); SET datafusion.optimizer.max_passes = 10; EXPLAIN VERBOSE SELECT * FROM test_data WHERE floor(int_val) = 100; ``` In each pass: 1. `common_sub_expression_eliminate` moves `CAST(int_val AS Float64)` into a projection below the `Filter`, as `__common_expr_N`. 2. `push_down_filter` pushes the `Filter` through that projection and puts the cast back into the predicate. 3. `common_sub_expression_eliminate` moves it out again, as `__common_expr_N+1`. The alias changes in every pass, so the loop never sees a repeated plan. It runs all 10 passes, and the final plan contains `__common_expr_10`. The expected plans in `floor_preimage.slt` and `eliminate_outer_join.slt` contain `__common_expr_3` for the same reason. `rewrite_projection` already refuses to push through a `MoveTowardsLeafNodes` expression, because `ExtractLeafExpressions` undoes that push. It has no equivalent guard for a CSE projection. I tried the simple fix: `rewrite_projection` does not push through a `__common_expr` projection. The plans then converge, but 3 expected plans get worse. A CSE projection stays in the final plan when the simplified predicate uses the expression only once. Thus this needs a design decision. Some options: - `PushDownFilter` does not push through a CSE projection, and a later rule removes a CSE projection whose expression is used only once. - CSE does not extract an expression from a `Filter` predicate if it extracted that expression before in the same optimizer run. - CSE runs only after the other rules reach a fixed point. - In all cases, a typed marker for a CSE projection (#25449) replaces the alias-prefix check. ### Related - #25672: `PushDownLimit` removes a redundant `Limit` one pass late, so every `ORDER BY ... LIMIT n` query runs one extra pass. - #22411 / #22412: skip a rule that returned `Transformed::no` when no rule changed the plan since then. A pass in which a fight changes the plan cannot skip rules. Thus fixing the two fights above also makes this change more effective. - #24281: reuse the projection schema in `OptimizeProjections`. `optimize_projections` runs again in every pass of both fights, so this makes each extra pass cheaper. -- 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]
