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:50 UTC
[arrow-datafusion] branch 5923-simplify-with-guarantee created (now 44d1b48a39)
This is an automated email from the ASF dual-hosted git repository.
wjones127 pushed a change to branch 5923-simplify-with-guarantee
in repository https://gitbox.apache.org/repos/asf/arrow-datafusion.git
at 44d1b48a39 feat: add guarantees to simplifcation
This branch includes the following new commits:
new 44d1b48a39 feat: add guarantees to simplifcation
The 1 revisions listed above as "new" are entirely new to this
repository and will be described in separate emails. The revisions
listed as "add" were already present in the repository and have only
been added to this reference.
[arrow-datafusion] 01/01: feat: add guarantees to simplifcation
Posted by wj...@apache.org.
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(())
}
}