Phoenix500526 commented on issue #23264: URL: https://github.com/apache/datafusion/issues/23264#issuecomment-6517331645
> Thank you [@Phoenix500526](https://github.com/Phoenix500526) -- no one is working on this that I know of > > I think this will be a pretty significantly disruptive change, so if we were to make it I think we would need to show some compelling benefits. For example some combination of: > > 1. Faster performance > 2. Memory efficiency > 3. less stack overflows > > etc Hi @alamb, I explored a prototype that balances AND/OR trees during SQL-to-`Expr` conversion while keeping the existing `BinaryExpr` representation and operand order. The prototype exposed several compatibility issues. Although it avoids a public API change, rebalancing is not behavior-neutral with the current optimizer and executor: - **Existing simplifications depend on tree shape.** For example, with non-nullable `a`, `(p AND q) AND ((a AND NOT a) AND r)` simplifies to `FALSE`, while the balanced form `(p AND q) AND (a AND (NOT a AND r))` does not. We also reproduced missed OR-to-IN merging, range-to-equality simplification, IN-list intersection, duplicate elimination, and common-factor extraction. - **Common subexpression elimination loses opportunities** when rebalancing removes a previously shared subtree. - **Later rewrites undo the balancing.** In particular, `simplify_predicates`, called by `PushDownFilter`, flattens OR expressions and rebuilds them through `disjunction`, which currently uses a left fold. - **Actual execution behavior changes in an error-producing case.** With: ```text a = [true, false, true, false] b = [false, true, false, true] x = [0, 0, 0, 0] ``` `(a OR b) OR (1 / x > 0)` returns all TRUE, whereas `a OR (b OR (1 / x > 0))` raises a division-by-zero error. The current batch-level OR short-circuit strategy makes different decisions for these two groupings. These experiments show that keeping the existing BinaryExpr representation avoids a public API change, but does not make rebalancing non-disruptive. The compatibility impact extends to optimizer effectiveness, downstream tree reconstruction, and execution behavior. -- 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]
