datafusion_physical_expr/simplifier/
not.rs

1// Licensed to the Apache Software Foundation (ASF) under one
2// or more contributor license agreements.  See the NOTICE file
3// distributed with this work for additional information
4// regarding copyright ownership.  The ASF licenses this file
5// to you under the Apache License, Version 2.0 (the
6// "License"); you may not use this file except in compliance
7// with the License.  You may obtain a copy of the License at
8//
9//   http://www.apache.org/licenses/LICENSE-2.0
10//
11// Unless required by applicable law or agreed to in writing,
12// software distributed under the License is distributed on an
13// "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY
14// KIND, either express or implied.  See the License for the
15// specific language governing permissions and limitations
16// under the License.
17
18//! Simplify NOT expressions in physical expressions
19//!
20//! This module provides optimizations for NOT expressions such as:
21//! - Double negation elimination: NOT(NOT(expr)) -> expr
22//! - NOT with binary comparisons: NOT(a = b) -> a != b
23//! - NOT with IN expressions: NOT(a IN (list)) -> a NOT IN (list)
24//! - De Morgan's laws: NOT(A AND B) -> NOT A OR NOT B
25//! - Constant folding: NOT(TRUE) -> FALSE, NOT(FALSE) -> TRUE
26//!
27//! This function is designed to work with TreeNodeRewriter's f_up traversal,
28//! which means children are already simplified when this function is called.
29//! The TreeNodeRewriter will automatically call this function repeatedly until
30//! no more transformations are possible.
31
32use std::sync::Arc;
33
34use arrow::datatypes::Schema;
35use datafusion_common::{Result, ScalarValue, tree_node::Transformed};
36use datafusion_expr::Operator;
37
38use crate::PhysicalExpr;
39use crate::expressions::{BinaryExpr, InListExpr, Literal, NotExpr, in_list, lit};
40
41/// Attempts to simplify NOT expressions by applying one level of transformation
42///
43/// This function applies a single simplification rule and returns. When used with
44/// TreeNodeRewriter, multiple passes will automatically be applied until no more
45/// transformations are possible.
46pub fn simplify_not_expr(
47    expr: &Arc<dyn PhysicalExpr>,
48    schema: &Schema,
49) -> Result<Transformed<Arc<dyn PhysicalExpr>>> {
50    // Check if this is a NOT expression
51    let not_expr = match expr.as_any().downcast_ref::<NotExpr>() {
52        Some(not_expr) => not_expr,
53        None => return Ok(Transformed::no(Arc::clone(expr))),
54    };
55
56    let inner_expr = not_expr.arg();
57
58    // Handle NOT(NOT(expr)) -> expr (double negation elimination)
59    if let Some(inner_not) = inner_expr.as_any().downcast_ref::<NotExpr>() {
60        return Ok(Transformed::yes(Arc::clone(inner_not.arg())));
61    }
62
63    // Handle NOT(literal) -> !literal
64    if let Some(literal) = inner_expr.as_any().downcast_ref::<Literal>() {
65        if let ScalarValue::Boolean(Some(val)) = literal.value() {
66            return Ok(Transformed::yes(lit(ScalarValue::Boolean(Some(!val)))));
67        }
68        if let ScalarValue::Boolean(None) = literal.value() {
69            return Ok(Transformed::yes(lit(ScalarValue::Boolean(None))));
70        }
71    }
72
73    // Handle NOT(IN list) -> NOT IN list
74    if let Some(in_list_expr) = inner_expr.as_any().downcast_ref::<InListExpr>() {
75        let negated = !in_list_expr.negated();
76        let new_in_list = in_list(
77            Arc::clone(in_list_expr.expr()),
78            in_list_expr.list().to_vec(),
79            &negated,
80            schema,
81        )?;
82        return Ok(Transformed::yes(new_in_list));
83    }
84
85    // Handle NOT(binary_expr)
86    if let Some(binary_expr) = inner_expr.as_any().downcast_ref::<BinaryExpr>() {
87        if let Some(negated_op) = binary_expr.op().negate() {
88            let new_binary = Arc::new(BinaryExpr::new(
89                Arc::clone(binary_expr.left()),
90                negated_op,
91                Arc::clone(binary_expr.right()),
92            ));
93            return Ok(Transformed::yes(new_binary));
94        }
95
96        // Handle De Morgan's laws for AND/OR
97        match binary_expr.op() {
98            Operator::And => {
99                // NOT(A AND B) -> NOT A OR NOT B
100                let not_left: Arc<dyn PhysicalExpr> =
101                    Arc::new(NotExpr::new(Arc::clone(binary_expr.left())));
102                let not_right: Arc<dyn PhysicalExpr> =
103                    Arc::new(NotExpr::new(Arc::clone(binary_expr.right())));
104                let new_binary =
105                    Arc::new(BinaryExpr::new(not_left, Operator::Or, not_right));
106                return Ok(Transformed::yes(new_binary));
107            }
108            Operator::Or => {
109                // NOT(A OR B) -> NOT A AND NOT B
110                let not_left: Arc<dyn PhysicalExpr> =
111                    Arc::new(NotExpr::new(Arc::clone(binary_expr.left())));
112                let not_right: Arc<dyn PhysicalExpr> =
113                    Arc::new(NotExpr::new(Arc::clone(binary_expr.right())));
114                let new_binary =
115                    Arc::new(BinaryExpr::new(not_left, Operator::And, not_right));
116                return Ok(Transformed::yes(new_binary));
117            }
118            _ => {}
119        }
120    }
121
122    // If no simplification possible, return the original expression
123    Ok(Transformed::no(Arc::clone(expr)))
124}
datafusion_physical_expr/simplifier/not.rs

datafusion_physical_expr/simplifier/
not.rs
