Advanced Interval Analysis

[ozankabak]

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).

Additional context

Efficient Implementation of Interval Arithmetic Narrowing Using IEEE Arithmetic, Timothy J. Hickey and Qun Ju

[acking-you]

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]

Looking forward to collaborating! 🚀

[IshaGudewar]

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.

[NG2411]

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]

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]

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]

Great to connect—excited to see what we can build together!

[IshaGudewar]

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.