juliuszsompolski opened a new pull request, #59143: URL: https://github.com/apache/spark/pull/59143
### What changes were proposed in this pull request? Several optimizer rules combine a wide set of predicates into a single conjunction or disjunction with a linear `reduce(And)` / `reduceLeft(And)` / `reduceOption(And)` chain. That produces a left-deep `And`/`Or` tree of depth `O(n)` in the number of predicates, and a later recursive traversal of the tree (by another rule, or by a generic `transform`) then recurses `O(n)` deep. This PR replaces those linear combinations with the balanced-tree builder `PredicateHelper.buildBalancedPredicate`, which produces a tree of depth `O(log n)`. Concretely: - Adds `PredicateHelper.buildBalancedPredicateOption`, the `Option`-returning companion to the existing `buildBalancedPredicate` (returns `None` for an empty input, mirroring `reduceOption` / `reduceLeftOption`). - Switches the wide-input predicate-combination sites in the following rules from `reduce*`/`reduceOption*` to `buildBalancedPredicate` / `buildBalancedPtersFromConstraints`, `CombineFilters`, `PruneFilters`, `PushPredicateThroughNonJoin`, `PushPredicateThroughJoin`, `PushDownLeftSemiAntiJoin`,`PushExtraPredicateThroughJoin`, `ExtractPythonUDFFromJoinCondition`, `ReorderJoin`, and `ExtractEquiJoinKeys`. `buildBalancedPredicate` already exists and is used the same way in `BooleanSimplification` and `LikeSimplification`; this extends the same treatment to the remaining predicate-combination sites. Bounded-arity combinations (e.g. an expression's own children) and sites where the shape is irrelevant are left unchanged. ### Why are the changes needed? A deeply nested `And`/`Or` tree built from a wide predicate set can cause a `StackOverflowError` during optimization when a downstream rule traverses it recursively. Building the tree balanced at construction time bounds the recursion depth to `O(log n)` and removes that failure mode at the source. ### Does this PR introduce _any_ user-facing change? No. `And` and `Or` are associative and the left-to-right evaluation order of the leaf predicates is preserved, so the combined predicate is semantically identical (including short-circuiting). Only the internal shape of the `And`/`Or` tree changes: for two or three operands it is identical to the old linear tree, and for four or more it becomes balanced rather than left-deep. ### How was this patch tested? Added `PredicateHelperSuite` covering `buildBalancedPredicate` (balanced shape) and `buildBalancedPredicateOption` (empty input and balanced shape). The ercised by the existing catalyst optimizer suites (constraint inference, filter pushdown, join reordering, equi-join key extraction). ### Was this patch authored or co-authored using generative AI tooling? Yes - Claude Code Opus 5.5 -- 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]
