You are viewing a plain text version of this content. The canonical link for it is here.
Posted to commits@arrow.apache.org by wj...@apache.org on 2023/09/03 21:53:51 UTC
[arrow-datafusion] 01/01: feat: add guarantees to simplifcation
This is an automated email from the ASF dual-hosted git repository.
wjones127 pushed a commit to branch 5923-simplify-with-guarantee
in repository https://gitbox.apache.org/repos/asf/arrow-datafusion.git
commit 44d1b48a3924480c8ce8af06f8ff66d7ef1fc26b
Author: Will Jones <wi...@gmail.com>
AuthorDate: Sun Sep 3 14:53:42 2023 -0700
feat: add guarantees to simplifcation
---
.../src/simplify_expressions/expr_simplifier.rs | 18 ++
.../src/simplify_expressions/guarantees.rs | 336 +++++++++++++++++++++
.../optimizer/src/simplify_expressions/mod.rs | 1 +
.../physical-expr/src/intervals/cp_solver.rs | 202 ++++++++-----
4 files changed, 480 insertions(+), 77 deletions(-)
diff --git a/datafusion/optimizer/src/simplify_expressions/expr_simplifier.rs b/datafusion/optimizer/src/simplify_expressions/expr_simplifier.rs
index 76073728b0..fc39aafe53 100644
--- a/datafusion/optimizer/src/simplify_expressions/expr_simplifier.rs
+++ b/datafusion/optimizer/src/simplify_expressions/expr_simplifier.rs
@@ -43,6 +43,8 @@ use datafusion_physical_expr::{create_physical_expr, execution_props::ExecutionP
use crate::simplify_expressions::SimplifyInfo;
+use crate::simplify_expressions::guarantees::{Guarantee, GuaranteeRewriter};
+
/// This structure handles API for expression simplification
pub struct ExprSimplifier<S> {
info: S,
@@ -149,6 +151,22 @@ impl<S: SimplifyInfo> ExprSimplifier<S> {
expr.rewrite(&mut expr_rewrite)
}
+
+ /// Add guarantees
+ pub fn simplify_with_gurantee<'a>(
+ &self,
+ expr: Expr,
+ guarantees: impl IntoIterator<Item = &'a (Expr, Guarantee)>,
+ ) -> Result<Expr> {
+ // Do a simplification pass in case it reveals places where a guarantee
+ // could be applied.
+ let expr = self.simplify(expr)?;
+ let mut rewriter = GuaranteeRewriter::new(guarantees);
+ let expr = expr.rewrite(&mut rewriter)?;
+ // Simplify after guarantees are applied, since constant folding should
+ // now be able to fold more expressions.
+ self.simplify(expr)
+ }
}
#[allow(rustdoc::private_intra_doc_links)]
diff --git a/datafusion/optimizer/src/simplify_expressions/guarantees.rs b/datafusion/optimizer/src/simplify_expressions/guarantees.rs
new file mode 100644
index 0000000000..a3a28b83ca
--- /dev/null
+++ b/datafusion/optimizer/src/simplify_expressions/guarantees.rs
@@ -0,0 +1,336 @@
+// Licensed to the Apache Software Foundation (ASF) under one
+// or more contributor license agreements. See the NOTICE file
+// distributed with this work for additional information
+// regarding copyright ownership. The ASF licenses this file
+// to you under the Apache License, Version 2.0 (the
+// "License"); you may not use this file except in compliance
+// with the License. You may obtain a copy of the License at
+//
+// http://www.apache.org/licenses/LICENSE-2.0
+//
+// Unless required by applicable law or agreed to in writing,
+// software distributed under the License is distributed on an
+// "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY
+// KIND, either express or implied. See the License for the
+// specific language governing permissions and limitations
+// under the License.
+
+//! Logic to inject guarantees with expressions.
+//!
+use datafusion_common::{tree_node::TreeNodeRewriter, Result, ScalarValue};
+use datafusion_expr::Expr;
+use std::collections::HashMap;
+
+/// A bound on the value of an expression.
+pub struct GuaranteeBound {
+ /// The value of the bound.
+ pub bound: ScalarValue,
+ /// If true, the bound is exclusive. If false, the bound is inclusive.
+ /// In terms of inequalities, this means the bound is `<` or `>` rather than
+ /// `<=` or `>=`.
+ pub open: bool,
+}
+
+impl GuaranteeBound {
+ /// Create a new bound.
+ pub fn new(bound: ScalarValue, open: bool) -> Self {
+ Self { bound, open }
+ }
+}
+
+impl Default for GuaranteeBound {
+ fn default() -> Self {
+ Self {
+ bound: ScalarValue::Null,
+ open: false,
+ }
+ }
+}
+
+/// The null status of an expression.
+///
+/// This might be populated by null count statistics, for example. A null count
+/// of zero would mean `NeverNull`, while a null count equal to row count would
+/// mean `AlwaysNull`.
+pub enum NullStatus {
+ /// The expression is guaranteed to be non-null.
+ NeverNull,
+ /// The expression is guaranteed to be null.
+ AlwaysNull,
+ /// The expression isn't guaranteed to never be null or always be null.
+ MaybeNull,
+}
+
+/// A set of constraints on the value of an expression.
+///
+/// This is similar to [datafusion_physical_expr::intervals::Interval], except
+/// that this is designed for working with logical expressions and also handles
+/// nulls.
+pub struct Guarantee {
+ /// The min values that the expression can take on. If `min.bound` is
+ pub min: GuaranteeBound,
+ /// The max values that the expression can take on.
+ pub max: GuaranteeBound,
+ /// Whether the expression is expected to be either always null or never null.
+ pub null_status: NullStatus,
+}
+
+impl Guarantee {
+ /// Create a new guarantee.
+ pub fn new(
+ min: Option<GuaranteeBound>,
+ max: Option<GuaranteeBound>,
+ null_status: NullStatus,
+ ) -> Self {
+ Self {
+ min: min.unwrap_or_default(),
+ max: max.unwrap_or_default(),
+ null_status,
+ }
+ }
+}
+
+impl From<&ScalarValue> for Guarantee {
+ fn from(value: &ScalarValue) -> Self {
+ Self {
+ min: GuaranteeBound {
+ bound: value.clone(),
+ open: false,
+ },
+ max: GuaranteeBound {
+ bound: value.clone(),
+ open: false,
+ },
+ null_status: match value {
+ ScalarValue::Null => NullStatus::AlwaysNull,
+ _ => NullStatus::NeverNull,
+ },
+ }
+ }
+}
+
+/// Rewrite expressions to incorporate guarantees.
+///
+///
+pub(crate) struct GuaranteeRewriter<'a> {
+ guarantees: HashMap<&'a Expr, &'a Guarantee>,
+}
+
+impl<'a> GuaranteeRewriter<'a> {
+ pub fn new(guarantees: impl IntoIterator<Item = &'a (Expr, Guarantee)>) -> Self {
+ Self {
+ guarantees: guarantees.into_iter().map(|(k, v)| (k, v)).collect(),
+ }
+ }
+}
+
+impl<'a> TreeNodeRewriter for GuaranteeRewriter<'a> {
+ type N = Expr;
+
+ fn mutate(&mut self, expr: Expr) -> Result<Expr> {
+ // IS NUll / NOT NUll
+
+ // Inequality expressions
+
+ // Columns (if bounds are equal and closed and column is not nullable)
+
+ // In list
+
+ Ok(expr)
+ }
+}
+
+#[cfg(test)]
+mod tests {
+ use super::*;
+
+ use datafusion_common::tree_node::TreeNode;
+ use datafusion_expr::{col, lit};
+
+ #[test]
+ fn test_null_handling() {
+ // IsNull / IsNotNull can be rewritten to true / false
+ let guarantees = vec![
+ (col("x"), Guarantee::new(None, None, NullStatus::AlwaysNull)),
+ (col("y"), Guarantee::new(None, None, NullStatus::NeverNull)),
+ ];
+ let mut rewriter = GuaranteeRewriter::new(guarantees.iter());
+
+ let cases = &[
+ (col("x").is_null(), true),
+ (col("x").is_not_null(), false),
+ (col("y").is_null(), false),
+ (col("y").is_not_null(), true),
+ ];
+
+ for (expr, expected_value) in cases {
+ let output = expr.clone().rewrite(&mut rewriter).unwrap();
+ assert_eq!(
+ output,
+ Expr::Literal(ScalarValue::Boolean(Some(*expected_value)))
+ );
+ }
+ }
+
+ #[test]
+ fn test_inequalities() {
+ let guarantees = vec![
+ // 1 < x <= 3
+ (
+ col("x"),
+ Guarantee::new(
+ Some(GuaranteeBound::new(ScalarValue::Int32(Some(1)), true)),
+ Some(GuaranteeBound::new(ScalarValue::Int32(Some(3)), false)),
+ NullStatus::NeverNull,
+ ),
+ ),
+ // 2021-01-01 <= y
+ (
+ col("y"),
+ Guarantee::new(
+ Some(GuaranteeBound::new(ScalarValue::Date32(Some(18628)), false)),
+ None,
+ NullStatus::NeverNull,
+ ),
+ ),
+ // "abc" < z <= "def"
+ (
+ col("z"),
+ Guarantee::new(
+ Some(GuaranteeBound::new(
+ ScalarValue::Utf8(Some("abc".to_string())),
+ true,
+ )),
+ Some(GuaranteeBound::new(
+ ScalarValue::Utf8(Some("def".to_string())),
+ false,
+ )),
+ NullStatus::MaybeNull,
+ ),
+ ),
+ ];
+ let mut rewriter = GuaranteeRewriter::new(guarantees.iter());
+
+ // These cases should be simplified
+ let cases = &[
+ (col("x").lt_eq(lit(1)), false),
+ (col("x").gt(lit(3)), false),
+ (col("y").gt_eq(lit(18628)), true),
+ (col("y").gt(lit(19000)), true),
+ (col("y").lt_eq(lit(17000)), false),
+ ];
+
+ for (expr, expected_value) in cases {
+ let output = expr.clone().rewrite(&mut rewriter).unwrap();
+ assert_eq!(
+ output,
+ Expr::Literal(ScalarValue::Boolean(Some(*expected_value)))
+ );
+ }
+
+ // These cases should be left as-is
+ let cases = &[
+ col("x").gt(lit(2)),
+ col("x").lt_eq(lit(3)),
+ col("y").gt_eq(lit(17000)),
+ ];
+
+ for expr in cases {
+ let output = expr.clone().rewrite(&mut rewriter).unwrap();
+ assert_eq!(&output, expr);
+ }
+ }
+
+ #[test]
+ fn test_column_single_value() {
+ let guarantees = vec![
+ // x = 2
+ (col("x"), Guarantee::from(&ScalarValue::Int32(Some(2)))),
+ // y is Null
+ (col("y"), Guarantee::from(&ScalarValue::Null)),
+ ];
+ let mut rewriter = GuaranteeRewriter::new(guarantees.iter());
+
+ // These cases should be simplified
+ let cases = &[
+ (col("x").lt_eq(lit(1)), false),
+ (col("x").gt(lit(3)), false),
+ (col("x").eq(lit(1)), false),
+ (col("x").eq(lit(2)), true),
+ (col("x").gt(lit(1)), true),
+ (col("x").lt_eq(lit(2)), true),
+ (col("x").is_not_null(), true),
+ (col("x").is_null(), false),
+ (col("y").is_null(), true),
+ (col("y").is_not_null(), false),
+ (col("y").lt_eq(lit(17000)), false),
+ ];
+
+ for (expr, expected_value) in cases {
+ let output = expr.clone().rewrite(&mut rewriter).unwrap();
+ assert_eq!(
+ output,
+ Expr::Literal(ScalarValue::Boolean(Some(*expected_value)))
+ );
+ }
+ }
+
+ #[test]
+ fn test_in_list() {
+ let guarantees = vec![
+ // x = 2
+ (col("x"), Guarantee::from(&ScalarValue::Int32(Some(2)))),
+ // 1 <= y < 10
+ (
+ col("y"),
+ Guarantee::new(
+ Some(GuaranteeBound::new(ScalarValue::Int32(Some(1)), false)),
+ Some(GuaranteeBound::new(ScalarValue::Int32(Some(10)), true)),
+ NullStatus::NeverNull,
+ ),
+ ),
+ // z is null
+ (col("z"), Guarantee::from(&ScalarValue::Null)),
+ ];
+ let mut rewriter = GuaranteeRewriter::new(guarantees.iter());
+
+ // These cases should be simplified
+ let cases = &[
+ // x IN ()
+ (col("x").in_list(vec![], false), false),
+ // x IN (10, 11)
+ (col("x").in_list(vec![lit(10), lit(11)], false), false),
+ // x IN (10, 2)
+ (col("x").in_list(vec![lit(10), lit(2)], false), true),
+ // x NOT IN (10, 2)
+ (col("x").in_list(vec![lit(10), lit(2)], true), false),
+ // y IN (10, 11)
+ (col("y").in_list(vec![lit(10), lit(11)], false), false),
+ // y NOT IN (0, 22)
+ (col("y").in_list(vec![lit(0), lit(22)], true), true),
+ // z IN (10, 11)
+ (col("z").in_list(vec![lit(10), lit(11)], false), false),
+ ];
+
+ for (expr, expected_value) in cases {
+ let output = expr.clone().rewrite(&mut rewriter).unwrap();
+ assert_eq!(
+ output,
+ Expr::Literal(ScalarValue::Boolean(Some(*expected_value)))
+ );
+ }
+
+ // These cases should be left as-is
+ let cases = &[
+ // y IN (10, 2)
+ col("y").in_list(vec![lit(10), lit(2)], false),
+ // y NOT IN (10, 2)
+ col("y").in_list(vec![lit(10), lit(2)], true),
+ ];
+
+ for expr in cases {
+ let output = expr.clone().rewrite(&mut rewriter).unwrap();
+ assert_eq!(&output, expr);
+ }
+ }
+}
diff --git a/datafusion/optimizer/src/simplify_expressions/mod.rs b/datafusion/optimizer/src/simplify_expressions/mod.rs
index dfa0fe7043..b030793e67 100644
--- a/datafusion/optimizer/src/simplify_expressions/mod.rs
+++ b/datafusion/optimizer/src/simplify_expressions/mod.rs
@@ -17,6 +17,7 @@
pub mod context;
pub mod expr_simplifier;
+pub mod guarantees;
mod or_in_list_simplifier;
mod regex;
pub mod simplify_exprs;
diff --git a/datafusion/physical-expr/src/intervals/cp_solver.rs b/datafusion/physical-expr/src/intervals/cp_solver.rs
index edf1507c70..7169101718 100644
--- a/datafusion/physical-expr/src/intervals/cp_solver.rs
+++ b/datafusion/physical-expr/src/intervals/cp_solver.rs
@@ -16,6 +16,99 @@
// under the License.
//! Constraint propagator/solver for custom PhysicalExpr graphs.
+//!
+//! Interval arithmetic provides a way to perform mathematical operations on
+//! intervals, which represent a range of possible values rather than a single
+//! point value. This allows for the propagation of ranges through mathematical
+//! operations, and can be used to compute bounds for a complicated expression.
+//! The key idea is that by breaking down a complicated expression into simpler
+//! terms, and then combining the bounds for those simpler terms, one can
+//! obtain bounds for the overall expression.
+//!
+//! For example, consider a mathematical expression such as x^2 + y = 4. Since
+//! it would be a binary tree in [PhysicalExpr] notation, this type of an
+//! hierarchical computation is well-suited for a graph based implementation.
+//! In such an implementation, an equation system f(x) = 0 is represented by a
+//! directed acyclic expression graph (DAEG).
+//!
+//! In order to use interval arithmetic to compute bounds for this expression,
+//! one would first determine intervals that represent the possible values of x
+//! and y. Let's say that the interval for x is [1, 2] and the interval for y
+//! is [-3, 1]. In the chart below, you can see how the computation takes place.
+//!
+//! This way of using interval arithmetic to compute bounds for a complex
+//! expression by combining the bounds for the constituent terms within the
+//! original expression allows us to reason about the range of possible values
+//! of the expression. This information later can be used in range pruning of
+//! the provably unnecessary parts of `RecordBatch`es.
+//!
+//! References
+//! 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, vol. 38, no. 04,
+//! pp. 277{293, 2004.
+//!
+//! ``` text
+//! Computing bounds for an expression using interval arithmetic. Constraint propagation through a top-down evaluation of the expression
+//! graph using inverse semantics.
+//!
+//! [-2, 5] ∩ [4, 4] = [4, 4] [4, 4]
+//! +-----+ +-----+ +-----+ +-----+
+//! +----| + |----+ +----| + |----+ +----| + |----+ +----| + |----+
+//! | | | | | | | | | | | | | | | |
+//! | +-----+ | | +-----+ | | +-----+ | | +-----+ |
+//! | | | | | | | |
+//! +-----+ +-----+ +-----+ +-----+ +-----+ +-----+ +-----+ +-----+
+//! | 2 | | y | | 2 | [1, 4] | y | | 2 | [1, 4] | y | | 2 | [1, 4] | y | [0, 1]*
+//! |[.] | | | |[.] | | | |[.] | | | |[.] | | |
+//! +-----+ +-----+ +-----+ +-----+ +-----+ +-----+ +-----+ +-----+
+//! | | | [-3, 1] |
+//! | | | |
+//! +---+ +---+ +---+ +---+
+//! | x | [1, 2] | x | [1, 2] | x | [1, 2] | x | [1, 2]
+//! +---+ +---+ +---+ +---+
+//!
+//! (a) Bottom-up evaluation: Step1 (b) Bottom up evaluation: Step2 (a) Top-down propagation: Step1 (b) Top-down propagation: Step2
+//!
+//! [1 - 3, 4 + 1] = [-2, 5] [1 - 3, 4 + 1] = [-2, 5]
+//! +-----+ +-----+ +-----+ +-----+
+//! +----| + |----+ +----| + |----+ +----| + |----+ +----| + |----+
+//! | | | | | | | | | | | | | | | |
+//! | +-----+ | | +-----+ | | +-----+ | | +-----+ |
+//! | | | | | | | |
+//! +-----+ +-----+ +-----+ +-----+ +-----+ +-----+ +-----+ +-----+
+//! | 2 |[1, 4] | y | | 2 |[1, 4] | y | | 2 |[3, 4]** | y | | 2 |[1, 4] | y |
+//! |[.] | | | |[.] | | | |[.] | | | |[.] | | |
+//! +-----+ +-----+ +-----+ +-----+ +-----+ +-----+ +-----+ +-----+
+//! | [-3, 1] | [-3, 1] | [0, 1] | [-3, 1]
+//! | | | |
+//! +---+ +---+ +---+ +---+
+//! | x | [1, 2] | x | [1, 2] | x | [1, 2] | x | [sqrt(3), 2]***
+//! +---+ +---+ +---+ +---+
+//!
+//! (c) Bottom-up evaluation: Step3 (d) Bottom-up evaluation: Step4 (c) Top-down propagation: Step3 (d) Top-down propagation: Step4
+//!
+//! * [-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]
+//! ```
+//!
+//! # Examples
+//!
+//! ```
+//! # Expression: (x + 4) - y
+//!
+//!
+//! # x: [0, 4), y: (1, 3]
+//!
+//! # Result:
+//! ```
+//!
+//! # Null handling
+//!
+//!
use std::collections::HashSet;
use std::fmt::{Display, Formatter};
@@ -39,83 +132,7 @@ use crate::PhysicalExpr;
use super::IntervalBound;
-// Interval arithmetic provides a way to perform mathematical operations on
-// intervals, which represent a range of possible values rather than a single
-// point value. This allows for the propagation of ranges through mathematical
-// operations, and can be used to compute bounds for a complicated expression.
-// The key idea is that by breaking down a complicated expression into simpler
-// terms, and then combining the bounds for those simpler terms, one can
-// obtain bounds for the overall expression.
-//
-// For example, consider a mathematical expression such as x^2 + y = 4. Since
-// it would be a binary tree in [PhysicalExpr] notation, this type of an
-// hierarchical computation is well-suited for a graph based implementation.
-// In such an implementation, an equation system f(x) = 0 is represented by a
-// directed acyclic expression graph (DAEG).
-//
-// In order to use interval arithmetic to compute bounds for this expression,
-// one would first determine intervals that represent the possible values of x
-// and y. Let's say that the interval for x is [1, 2] and the interval for y
-// is [-3, 1]. In the chart below, you can see how the computation takes place.
-//
-// This way of using interval arithmetic to compute bounds for a complex
-// expression by combining the bounds for the constituent terms within the
-// original expression allows us to reason about the range of possible values
-// of the expression. This information later can be used in range pruning of
-// the provably unnecessary parts of `RecordBatch`es.
-//
-// References
-// 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, vol. 38, no. 04,
-// pp. 277{293, 2004.
-//
-// ``` text
-// Computing bounds for an expression using interval arithmetic. Constraint propagation through a top-down evaluation of the expression
-// graph using inverse semantics.
-//
-// [-2, 5] ∩ [4, 4] = [4, 4] [4, 4]
-// +-----+ +-----+ +-----+ +-----+
-// +----| + |----+ +----| + |----+ +----| + |----+ +----| + |----+
-// | | | | | | | | | | | | | | | |
-// | +-----+ | | +-----+ | | +-----+ | | +-----+ |
-// | | | | | | | |
-// +-----+ +-----+ +-----+ +-----+ +-----+ +-----+ +-----+ +-----+
-// | 2 | | y | | 2 | [1, 4] | y | | 2 | [1, 4] | y | | 2 | [1, 4] | y | [0, 1]*
-// |[.] | | | |[.] | | | |[.] | | | |[.] | | |
-// +-----+ +-----+ +-----+ +-----+ +-----+ +-----+ +-----+ +-----+
-// | | | [-3, 1] |
-// | | | |
-// +---+ +---+ +---+ +---+
-// | x | [1, 2] | x | [1, 2] | x | [1, 2] | x | [1, 2]
-// +---+ +---+ +---+ +---+
-//
-// (a) Bottom-up evaluation: Step1 (b) Bottom up evaluation: Step2 (a) Top-down propagation: Step1 (b) Top-down propagation: Step2
-//
-// [1 - 3, 4 + 1] = [-2, 5] [1 - 3, 4 + 1] = [-2, 5]
-// +-----+ +-----+ +-----+ +-----+
-// +----| + |----+ +----| + |----+ +----| + |----+ +----| + |----+
-// | | | | | | | | | | | | | | | |
-// | +-----+ | | +-----+ | | +-----+ | | +-----+ |
-// | | | | | | | |
-// +-----+ +-----+ +-----+ +-----+ +-----+ +-----+ +-----+ +-----+
-// | 2 |[1, 4] | y | | 2 |[1, 4] | y | | 2 |[3, 4]** | y | | 2 |[1, 4] | y |
-// |[.] | | | |[.] | | | |[.] | | | |[.] | | |
-// +-----+ +-----+ +-----+ +-----+ +-----+ +-----+ +-----+ +-----+
-// | [-3, 1] | [-3, 1] | [0, 1] | [-3, 1]
-// | | | |
-// +---+ +---+ +---+ +---+
-// | x | [1, 2] | x | [1, 2] | x | [1, 2] | x | [sqrt(3), 2]***
-// +---+ +---+ +---+ +---+
-//
-// (c) Bottom-up evaluation: Step3 (d) Bottom-up evaluation: Step4 (c) Top-down propagation: Step3 (d) Top-down propagation: Step4
-//
-// * [-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]
-// ```
+
/// This object implements a directed acyclic expression graph (DAEG) that
/// is used to compute ranges for expressions through interval arithmetic.
@@ -561,6 +578,7 @@ pub fn check_support(expr: &Arc<dyn PhysicalExpr>) -> bool {
#[cfg(test)]
mod tests {
use super::*;
+ use datafusion_expr::expr;
use itertools::Itertools;
use crate::expressions::{BinaryExpr, Column};
@@ -1123,6 +1141,36 @@ mod tests {
let final_node_count = graph.node_count();
// Assert that the final node count is equal the previous node count (i.e., no node was pruned).
assert_eq!(prev_node_count, final_node_count);
+ Ok(())
+ }
+
+ #[test]
+ fn my_test() -> Result<()> {
+ let expr_x = Arc::new(Column::new("x", 0));
+ let expr_y = Arc::new(Column::new("y", 1));
+ let expression = Arc::new(BinaryExpr::new(
+ Arc::new(BinaryExpr::new(
+ expr_x.clone(),
+ Operator::Plus,
+ Arc::new(Literal::new(ScalarValue::Int32(Some(4)))),
+ )),
+ Operator::Minus,
+ expr_y.clone(),
+ ));
+
+ let mut graph = ExprIntervalGraph::try_new(expression.clone()).unwrap();
+ // Pass in expr_x and expr_y so we can input their intervals
+ let mapping = graph.gather_node_indices(&[expr_x, expr_y]);
+
+ let interval_x = Interval::make(Some(0), Some(4), (false, true));
+ let interval_y = Interval::make(Some(1), Some(3), (true, false));
+ graph.assign_intervals(&[
+ (mapping[0].1, interval_x.clone()),
+ (mapping[1].1, interval_y.clone()),
+ ]);
+
+
+
Ok(())
}
}