Repository navigation
Advanced Interval Analysis #14515
Description
Is your feature request related to a problem or challenge?
The interval arithmetic library in DataFusion works via two fundamental methods: evaluate_bounds for bottom-up evaluation, and propagate_constraints for top-down propagation. We apply each traversal once to update bounds on columns. However, when there are complex expressions where symbols (e.g. columns) appear more than once, this will give overly pessimistic bounds, resulting in missed opportunities in data pruning and optimizations.
Describe the solution you'd like
If we use Timothy Hickey's interval narrowing approach and utilize a single update_bounds API (instead of the two APIs we have today), we can utilize a queue of nodes to only narrow intervals of nodes that keep shrinking. Simply stated, the update_bounds function is a simultaneous computation of both evaluation and propagation logics -- it updates intervals of the parent and the children nodes at the same time.
This will allow us to arrive at more precise bounds without unnecessarily traversing the expression DAG too many times.
Describe alternatives you've considered
We can apply evaluate_bounds and propagate_constraints in a loop until column bounds converge to a fixed point (to some tolerance), but that would be inefficient (albeit easy).
Activity
acking-you commentedon Feb 27, 2025
This looks like a super interesting optimization🌟! I'm really intrigued by it. Thanks for sharing the paper link - will definitely dive into it when I have some free time!
ozankabak commentedon Feb 28, 2025
Looking forward to collaborating! 🚀
IshaGudewar commentedon Mar 7, 2025
Hi @ozankabak
I’m interested in contributing to this project. I’ve read the issue description and understand the problem with the current interval arithmetic implementation. I’d like to work on implementing the
update_boundsAPI using Timothy Hickey’s interval narrowing approach.Could you provide some guidance on how to get started or any specific areas that need attention? I’ve already set up the project locally and am familiar with the current implementation.
NG2411 commentedon Mar 8, 2025
Hi @ozankabak I’m interested in contributing to this project. I’ve read the issue description and understand the problem with the current interval arithmetic implementation. I’d like to work on implementing the update_bounds API using Timothy Hickey’s interval narrowing approach.
Could you provide some guidance on how to get started or any specific areas that need attention? I’ve already set up the project locally and am familiar with the current implementation.
Malvern2109 commentedon Mar 26, 2025
Hello @ozankabak
As a mathematics enthusiast l am really excited to contribute to this project and would like to focus on enhancing the interval arithmetic implementation by adopting Timothy Hickey's interval narrowing methodology through the update_bounds API. Having reviewed the issue description and studied the current implementation, I understand the need to address the key challenges such as precision limitations in the existing bound calculations among others.
Any guidance on how to get started would be highly appreciated.
berkaysynnada commentedon Mar 27, 2025
Thanks @IshaGudewar, @NG2411, and @Malvern2109 for your interest! I recommend you to join the discord GSoC channel, and reach out to me there for the project related questions.
rutvik-max commentedon Jun 20, 2025
Great to connect—excited to see what we can build together!
IshaGudewar commentedon Jul 21, 2025
hey!!! @berkaysynnada Apologies for the delayed response I just saw your message. Thank you so much for considering me earlier!
I wanted to ask if there's still a chance for me to join the project or get involved in any way. I’m really interested and would love to contribute if it's still possible.