IvanVergiliev opened a new pull request #24068: [SPARK-27105][SQL] Optimize away exponential complexity in ORC predicate conversion URL: https://github.com/apache/spark/pull/24068 ## What changes were proposed in this pull request? `OrcFilters.createBuilder` has exponential complexity in the height of the filter tree due to the way the check-and-build pattern is implemented. We've hit this in production by passing a `Column` filter to Spark directly, with a job taking multiple hours for a simple set of ~30 filters. This PR changes the checking logic so that the conversion has linear complexity in the size of the tree instead of exponential in its height. Right now, due to the way ORC `SearchArgument` works, the code is forced to do two separate phases when converting a given Spark filter to an ORC filter: 1. Check if the filter is convertible. 2. Only if the check in 1. succeeds, perform the actual conversion into the resulting ORC filter. However, there's one detail which is the culprit in the exponential complexity: phases 1. and 2. are both done using the exact same method. The resulting exponential complexity is easiest to see in the `NOT` case - consider the following code: ``` val f1 = col("id") === lit(5) val f2 = !f1 val f3 = !f2 val f4 = !f3 val f5 = !f4 ``` Now, when we run `createBuilder` on `f5`, we get the following behaviour: 1. call `createBuilder(f4)` to check if the child `f4` is convertible 2. call `createBuilder(f4)` to actually convert it This seems fine when looking at a single level, but what actually ends up happening is: - `createBuilder(f3)` will then recursively be called 4 times - 2 times in step 1., and two times in step 2. - `createBuilder(f2)` will be called 8 times - 4 times in each top-level step, 2 times in each sub-step. - `createBuilder(f1)` will be called 16 times. As a result, having a tree of height > 30 leads to billions of calls to `createBuilder`, heap allocations, and so on and can take multiple hours. The way this PR solves this problem is by separating the `check` and `convert` functionalities into separate functions. This way, the call to `createBuilder` on `f5` above would look like this: 1. call `isConvertible(f4)` to check if the child `f4` is convertible - amortized constant complexity 2. call `createBuilder(f4)` to actually convert it - linear complexity in the size of the subtree. This way, we get an overall complexity that's linear in the size of the filter tree, allowing us to convert tree with 10s of thousands of nodes in milliseconds. The reason this split (`check` and `build`) is possible is that the checking never actually depends on the actual building of the filter. The `check` part of `createBuilder` depends mainly on: - `isSearchableType` for leaf nodes, and - `check`-ing the child filters for composite nodes like NOT, AND and OR. Situations like the `SearchArgumentBuilder` throwing an exception while building the resulting ORC filter are not handled right now - they just get thrown out of the class, and this change preserves this behaviour. This PR extracts this part of the code to a separate class which allows the conversion to make very efficient checks to confirm that a given child is convertible before actually converting it. Results: Before: - converting a skewed tree with a height of ~35 took about 6-7 hours. - converting a skewed tree with hundreds or thousands of nodes would be completely impossible. Now: - filtering against a skewed tree with a height of 1500 in the benchmark suite finishes in less than 10 seconds. ## How was this patch tested? There are no changes in behaviour, and the existing tests pass. Added new benchmarks that expose the problematic behaviour and they finish quickly with the changes applied.
---------------------------------------------------------------- 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. For queries about this service, please contact Infrastructure at: [email protected] With regards, Apache Git Services --------------------------------------------------------------------- To unsubscribe, e-mail: [email protected] For additional commands, e-mail: [email protected]
