Interval Arithmetic in DataFusion: Proving That a Predicate Can Only Match Certain Values

TL;DR: A filter like x * x + y = 4 tells you something about x and y even if you only know their rough ranges. DataFusion builds a graph of the filter’s expression, computes each node’s value interval bottom-up, then propagates the filter’s equality constraint back down through inverse arithmetic (y = 4 - x*x means y ∈ [0, 1] once x is known), tightening the input intervals. Those tightened intervals are what let a file scan skip data it can prove cannot match.

The pruning articles in this series are about statistics: a Parquet row group knows the min and max of its columns, and a predicate is evaluated against those to decide whether the row group can be skipped.

Statistics give you the range of a column. Interval arithmetic gives you the range of an expression.

Consider a filter on a computed column:

SELECT * FROM t WHERE a * a + b > 100;

A Parquet file has statistics for a and b separately. It does not have statistics for a * a + b. But if the file says a ∈ [0, 10] and b ∈ [0, 10], then a*a + b ∈ [0, 110], and the filter > 100 might match. But if a ∈ [0, 3], then a*a + b ∈ [0, 19], and the filter cannot match — so the file can be skipped entirely.

DataFusion can do better than that, and the machinery is datafusion/physical-expr/src/intervals/cp_solver.rs (1,959 lines) plus datafusion/expr-common/src/interval_arithmetic.rs (5,362 lines).

Interval arithmetic

An Interval is a range of possible values:

pub struct Interval {
    lower: Option<ScalarValue>,
    upper: Option<ScalarValue>,
}

with None meaning unbounded on that side. The arithmetic is interval arithmetic in the classical sense: the sum of two intervals is the sum of their bounds, the product of two intervals is the min and max of the four products, and so on.

The crucial property is that interval arithmetic over-approximates: the computed interval always contains every value the expression can actually take. That is what makes it safe to use for pruning — you might fail to prune, but you will never prune a row that should have been kept.

The references in the module doc are the classics:

1. Kabak, Mehmet Ozan. Analog Circuit Start-Up Behavior Analysis: An Interval Arithmetic Based Approach, Chapter 4. Stanford University, 2015.
2. Moore, Ramon E. Interval analysis. Vol. 4. Englewood Cliffs: Prentice-Hall, 1966.
3. F. Messine, “Deterministic global optimization using interval constraint propagation techniques,” RAIRO-Operations Research, 2004.

The first reference is telling: analog circuit start-up analysis. The same mathematics that bounds a circuit’s operating range bounds a query’s filter selectivity. That is a genuinely delightful piece of computer science: interval arithmetic from circuit design, applied to query planning.

The expression graph

The solver does not work on a tree. It works on a directed acyclic expression graph (DAEG):

/// This object implements a directed acyclic expression graph (DAEG) that
/// is used to compute ranges for expressions through interval arithmetic.
#[derive(Clone, Debug)]
pub struct ExprIntervalGraph {
    graph: StableGraph<ExprIntervalGraphNode, usize>,
    root: NodeIndex,
}

A graph, not a tree, because a column can appear many times in an expression (a + a, or a * b - a * b) and you want to compute its interval once and share it.

Each node carries the expression and its current interval:

pub struct ExprIntervalGraphNode {
    expr: Arc<dyn PhysicalExpr>,
    interval: Interval,
}

and the graph is built with petgraph — a general-purpose graph library — using a StableGraph so that node indices stay valid as the graph is mutated.

Literals start as singleton intervals; everything else starts unbounded:

/// Constructs a new DAEG node from DataFusion's [`ExprTreeNode`]
/// object. Literals are created with definite, singleton intervals while
/// any other expression starts with an indefinite interval (`[-∞, ∞]`).

The [-∞, ∞] start is the honest one: before analysis, you know nothing about a.

Bottom-up: compute the ranges

The first pass computes each node’s interval from its children’s:

             +-----+
        +----|  +  |----+
        |    |     |    |
        |    +-----+    |
        |               |
    +-----+           +-----+
    |   2 |           |  y  |
    |[.]  |           |     |
    +-----+           +-----+
       |                               |
     +---+                           +---+
     | x | [1, 2]                    | x | [1, 2]
     +---+                           +---+

x ∈ [1, 2], so x * x ∈ [1, 4]. y ∈ [-3, 1]. Then x*x + y ∈ [1-3, 4+1] = [-2, 5].

This is a breadth-first traversal of the graph (the code imports petgraph::visit::Bfs), computing each node once its children are done.

Top-down: propagate the constraint

The interesting part is the second pass. The filter says the expression equals 4. That is a constraint on the root, and it can be pushed back down through inverse arithmetic:

   [-2, 5] ∩ [4, 4] = [4, 4]
           +-----+
      +----|  +  |----+
      |    |     |    |
      |    +-----+    |
      |               |
   +-----+           +-----+
   |   2 | [1, 4]    |  y  | [0, 1]*
   |[.]  |           |     |
   +-----+           +-----+
      |              [-3, 1]
      |
    +---+
    | x | [1, 2]
    +---+

with the arithmetic spelled out in the doc:

• [-3, 1] ∩ ([4, 4] - [1, 4]) = [0, 1]
• [1, 4] ∩ ([4, 4] - [0, 1]) = [3, 4]
• [1, 2] ∩ [sqrt(3), sqrt(4)] = [sqrt(3), 2]

Read that as a chain:

1. The root’s interval [-2, 5] is intersected with the constraint [4, 4] → the root is exactly 4.
2. Since root = x*x + y = 4, we get y = 4 - x*x. With x*x ∈ [1, 4], y ∈ [4-4, 4-1] = [0, 3], intersected with the original y ∈ [-3, 1] → y ∈ [0, 1].
3. Now x*x = 4 - y ∈ [4-1, 4-0] = [3, 4], intersected with [1, 4] → x*x ∈ [3, 4].
4. x ∈ [1, 2] and x*x ∈ [3, 4] → x ∈ [sqrt(3), 2].

So the solver has proved that any row satisfying x*x + y = 4 must have x ∈ [sqrt(3), 2] — a fact that is not visible anywhere in the original expression, and which a file-level statistics check on a and b alone could never derive.

That is the payoff. The tightened intervals are what the pruning machinery then uses to skip files and row groups.

The inverse operators

Step 2 needs the inverse of each operator: given x + y = 4 and x ∈ [1, 4], what is y? Answer: y ∈ [4-4, 4-1] = [0, 3].

The code has a helper for exactly this:

use super::utils::{convert_duration_type_to_interval, convert_interval_type_to_duration, get_inverse_op};

get_inverse_op maps an operator to its inverse — + becomes -, * becomes /, and so on. For the operators where no inverse exists (%, bitwise ops), the propagation simply stops, and the interval stays as computed bottom-up. A partial answer is still useful.

The result type makes the three outcomes explicit:

/// This object encapsulates all possible constraint propagation results.
#[derive(PartialEq, Debug)]
pub enum PropagationResult {
    CannotPropagate,
    Infeasible,
    Success,
}

Infeasible is the interesting one: it means the constraint contradicts itself — the filter is x > 5 AND x < 3, or x*x + y = 4 with y ∈ [100, 200]. When the solver reaches that state, the whole expression is provably empty, and the filter can be replaced with false and the entire subtree dropped from the plan.

The catch

• Interval arithmetic over-approximates, and it over-approximates badly. x * x with x ∈ [-10, 10] gives [-100, 100], not [0, 100] — because the interval arithmetic does not know that x appears twice. The top-down pass recovers some of that (it knows the two occurrences are the same variable), but the bottom-up pass does not. This is the classic weakness of interval arithmetic, and it is why the constraint propagation step exists.
• The propagation is not always possible. Some operators have no invertible counterpart, and some expressions have no useful structure. CannotPropagate is the honest answer.
• The result is only as good as the input statistics. If the file’s statistics for a are wrong, the derived intervals are wrong and the pruning is wrong. (Which is why the pruning machinery, not the interval solver, is where the correctness guarantees live.)
• The graph can be large. A wide expression tree becomes a graph with one node per distinct subexpression, and the propagation is a fixed-point iteration over it. For a very large expression this is not free — and it is not something you want to do for every predicate in every query.

Why it matters

Interval arithmetic is one of those techniques that sounds academic and turns out to be quietly load-bearing. It is the difference between “I know the range of column a” and “I know the range of a * a + b”, and the second is a much stronger statement — strong enough, in the right data layout, to skip a whole Parquet file.

And the top-down propagation is the part that makes it more than an arithmetic curiosity: it turns a filter into a constraint system, and solves it in both directions. The x ∈ [sqrt(3), 2] result is not a property of the data — it is a property of the query, deduced from the shape of the expression and the semantics of the operators.

Which is, in the end, the oldest trick in the book: read the question carefully and the answer often falls out.