apache / apache/datafusion

Advanced Interval Analysis

Open
#14,515 8 comments 6 reactions 0 assignees View on GitHub
enhancement
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?

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](https://citeseerx.ist.psu.edu/document?repid=rep1&type=pdf&doi=50c8714120fee5ae111655bc1d8c81c95e499a7f)

Contributor guide

Open the contributing guide

Research direction

Start by reading the interval arithmetic library's evaluate_bounds and propagate_constraints implementations and how they traverse expression DAGs. Read the linked interval-narrowing paper for the proposed approach. Done means a single update_bounds-based narrowing process produces more precise bounds for repeated symbols without unnecessarily revisiting unchanged nodes.

Written by the indexing model from the issue text.

Assessment

Tech stack
rust
Domain
data, performance
Issue type
Feature
Difficulty
5/5
Estimated time
Over a week
Activity status
Stale
Clarity
Mostly clear
Newbie friendliness
32/100

Get new issues in your inbox

A short digest of beginner-friendly GitHub issues.