Module datafusion_physical_expr::intervals::cp_solver

source ·
Expand description

Constraint propagator/solver for custom PhysicalExpr graphs.

Structs

  • ExprIntervalGraph
    This object implements a directed acyclic expression graph (DAEG) that is used to compute ranges for expressions through interval arithmetic.
  • ExprIntervalGraphNode
    This is a node in the DAEG; it encapsulates a reference to the actual PhysicalExpr as well as an interval containing expression bounds.

Enums

  • PropagationResult
    This object encapsulates all possible constraint propagation results.

Functions

  • check_support
    Indicates whether interval arithmetic is supported for the given expression. Currently, we do not support all PhysicalExprs for interval calculations. We do not support every type of Operators either. Over time, this check will relax as more types of PhysicalExprs and Operators are supported. Currently, CastExpr, BinaryExpr, Column and Literal are supported.
  • propagate_arithmetic
    This function refines intervals left_child and right_child by applying constraint propagation through parent via operation. The main idea is that we can shrink ranges of variables x and y using parent interval p.
  • propagate_comparison
    This function propagates constraints arising from comparison operators. The main idea is that we can analyze an inequality like x > y through the equivalent inequality x - y > 0. Assuming that x and y has ranges [xL, xU] and [yL, yU], we simply apply constraint propagation across [xL, xU], [yL, yH] and [0, ∞]. Specifically, we would first do - [xL, xU] <- ([yL, yU] + [0, ∞]) ∩ [xL, xU], and then - [yL, yU] <- ([xL, xU] - [0, ∞]) ∩ [yL, yU].