Repository navigation
Consolidate interval analysies from Interval and PruningPredicate #7887
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
NULLthat @appletreeisyellow is working on will only affectPruningPredicates - Supporting
LIKEorsubstrwould require different code in different places - Support for
INlists added toPruningPredicatewas not added to Interval arithmetic
The rewrite used by the PruningPrediate logic is tricky to understand and only handles very specific predicate forms (see #9184 for an essay on the topic and #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 library is used for cardinality estimation and range analysis for the symmetric hash join, and it:
- Can handle arbitrary expressions (such as
a < b, not just constantsa < 5) - Has a story for how it would support user defined functions (each function would implement a range analysis)
Pruning Predicate Pruning Predicate is used to prune row groups based on min/max values which:
- Is vectorized (is efficient to evaluate over 1000s of containers)
- Handles the common cases of
col <op> constant(such asa = 5, ora < 100), and conjunctions of them - 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:
- We would have a single code path to extend and maintain
- 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 Intervals: #5322 (comment) between @ozankabak @metegenez and myself
Activity
alamb commentedon Oct 20, 2023
@ozankabak and @tustvold I swear we have talked about this topic before but I could not find an existing ticket or discussion. Do you have any other pointers to past discussions?
berkaysynnada commentedon Oct 21, 2023
I am not sure this is what you searched for but there was an issue #5535.
Actually, I have tried to apply cp_solver strategy to prune row groups. But we observed a performance degradation since this method sacrifices vectorized computing power, meaning that the process needs to be run for each set of statistics. As the number of sets increases, the efficiency decreases.
I will again think about how to insert Interval library there without sacrificing performance.
alamb commentedon Oct 21, 2023
Thank you -- this is exactly what I was looking for.
I may be able to help with this too. One way is use
Datum(from arrow) (rather than ScalarValue)in theInterval` representation -- that way each can store a single value or multiple.alamb commentedon Feb 14, 2024
I just updated this ticket's description with a more coherent story and examples that @appletreeisyellow and I have hit recently while working on in #9171
We were talking today and I think @appletreeisyellow may try to prototype what this solution could look like, if she has time, to move the conversation forward.
appletreeisyellow commentedon Feb 14, 2024
Thank you @alamb for the updating the description
adriangb commentedon Mar 26, 2025
Hi @appletreeisyellow or @#15425 I was wondering if you were able to make any progress with this? I was thinking about #15425 today but since it requires considerable changes to
PruningPredicateand conflict with this work I wanted to check first.appletreeisyellow commentedon Mar 26, 2025
Hi @adriangb! I've done this part of the work:
I don't have any plans to work on
PruningPredicatein the near future, so you are good! Unless @alamb has anything to add?adriangb commentedon Mar 26, 2025
I was more so asking about work to use
ExprIntervalGraphinside ofPruningPredicate