Consolidate interval analysies from `Interval` and `PruningPredicate`
- Dominant language
- Rust
- Stars
- 9.3k
- Forks
- 2.4k
- Avg merge
- 3d 7h
- Merged PRs (30d)
- 344
Description
### Is your feature request related to a problem or challenge?
We now have two ways to do range / interval analysis in DataFusion.
Having two representations is challenging because we have to implement the same logic in two places. For example,
* [supporting columns known to be `NULL`](https://github.com/apache/arrow-datafusion/issues/9171) that @appletreeisyellow is working on will only affect `PruningPredicates`
* Supporting `LIKE` or `substr` would require different code in different places
* Support for `IN` lists added to `PruningPredicate` was not added to Interval arithmetic
The rewrite used by the `PruningPrediate` logic is tricky to understand and only handles very specific predicate forms (see https://github.com/apache/arrow-datafusion/pull/9184 for an essay on the topic and https://github.com/apache/arrow-datafusion/issues/9230 for an example of getting it wrong). Thus it is hard to extend the number of functions / types of predicates that are supported.
The existing range analysis are:
#### `Interval` based analysis
The [`ExprIntervalGraph`](https://docs.rs/datafusion/latest/datafusion/physical_expr/intervals/cp_solver/struct.ExprIntervalGraph.html) library is used for cardinality estimation and range analysis for the symmetric hash join, and it:
1. Can handle arbitrary expressions (such as `a < b`, not just constants `a < 5`)
2. Has a story for how it would support user defined functions (each function would implement a range analysis)
#### Pruning Predicate [`Pruning Predicate`](https://docs.rs/datafusion/latest/datafusion/physical_optimizer/pruning/struct.PruningPredicate.html) is used to prune row groups based on min/max values which:
1. Is vectorized (is efficient to evaluate over 1000s of containers)
3. Handles the common cases of `col constant` (such as `a = 5`, or `a < 100`), and conjunctions of them
4. It is not clear (to me at least) how the rewrite that is used can handle arbitrary expressions (e.g. `a < b`)
### Describe the solution you'd like
I would like to rewrite `PruningPredicate` to use `ExprIntervalGraph`, measuring and possibly improving the performance of `ExprIntervalGraph`
The benefits would be:
1. We would have a single code path to extend and maintain
2. We would have a clear path for handling arbitrary predicates to prune row groups
### Describe alternatives you've considered
Doing so would likely require extending the interval analysis to support more operators (like `IN` lists) to reach feature parity with the current `PruningPredicate` rewrite
### Additional context
There was a lot of discussion of this topic on the PR that originally introduced `Interval`s: https://github.com/apache/arrow-datafusion/pull/5322#discussion_r1114324054 between @ozankabak @metegenez and myself
Contributor guide
Research direction
Start by reading the ExprIntervalGraph interval-analysis documentation and the PruningPredicate implementation described in the issue, then compare their supported predicate forms and performance characteristics. Trace the existing pruning path and interval-analysis users, including symmetric hash join estimation. Done means PruningPredicate uses the shared analysis while retaining current pruning behavior and addressing feature-parity or performance gaps such as IN lists.
Written by the indexing model from the issue text.
Assessment
- Tech stack
- rust
- Domain
- databases, performance
- Issue type
- Feature
- Difficulty
- 5/5
- Estimated time
- Over a week
- Activity status
- Stale
- Clarity
- Mostly clear
- Newbie friendliness
- 20/100