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.
46#[deprecated(
47    since = "53.0.0",
48    note = "This function will be made private in a future release, please file an issue if you have a reason for keeping it public."
49)]
50pub fn simplify_not_expr(
51    expr: Arc<dyn PhysicalExpr>,
52    schema: &Schema,
53) -> Result<Transformed<Arc<dyn PhysicalExpr>>> {
54    // Check if this is a NOT expression
55    let not_expr = match expr.as_any().downcast_ref::<NotExpr>() {
56        Some(not_expr) => not_expr,
57        None => return Ok(Transformed::no(expr)),
58    };
59
60    let inner_expr = not_expr.arg();
61
62    // Handle NOT(NOT(expr)) -> expr (double negation elimination)
63    if let Some(inner_not) = inner_expr.as_any().downcast_ref::<NotExpr>() {
64        return Ok(Transformed::yes(Arc::clone(inner_not.arg())));
65    }
66
67    // Handle NOT(literal) -> !literal
68    if let Some(literal) = inner_expr.as_any().downcast_ref::<Literal>() {
69        if let ScalarValue::Boolean(Some(val)) = literal.value() {
70            return Ok(Transformed::yes(lit(ScalarValue::Boolean(Some(!val)))));
71        }
72        if let ScalarValue::Boolean(None) = literal.value() {
73            return Ok(Transformed::yes(lit(ScalarValue::Boolean(None))));
74        }
75    }
76
77    // Handle NOT(IN list) -> NOT IN list
78    if let Some(in_list_expr) = inner_expr.as_any().downcast_ref::<InListExpr>() {
79        let negated = !in_list_expr.negated();
80        let new_in_list = in_list(
81            Arc::clone(in_list_expr.expr()),
82            in_list_expr.list().to_vec(),
83            &negated,
84            schema,
85        )?;
86        return Ok(Transformed::yes(new_in_list));
87    }
88
89    // Handle NOT(binary_expr)
90    if let Some(binary_expr) = inner_expr.as_any().downcast_ref::<BinaryExpr>() {
91        if let Some(negated_op) = binary_expr.op().negate() {
92            let new_binary = Arc::new(BinaryExpr::new(
93                Arc::clone(binary_expr.left()),
94                negated_op,
95                Arc::clone(binary_expr.right()),
96            ));
97            return Ok(Transformed::yes(new_binary));
98        }
99
100        // Handle De Morgan's laws for AND/OR
101        match binary_expr.op() {
102            Operator::And => {
103                // NOT(A AND B) -> NOT A OR NOT B
104                let not_left: Arc<dyn PhysicalExpr> =
105                    Arc::new(NotExpr::new(Arc::clone(binary_expr.left())));
106                let not_right: Arc<dyn PhysicalExpr> =
107                    Arc::new(NotExpr::new(Arc::clone(binary_expr.right())));
108                let new_binary =
109                    Arc::new(BinaryExpr::new(not_left, Operator::Or, not_right));
110                return Ok(Transformed::yes(new_binary));
111            }
112            Operator::Or => {
113                // NOT(A OR B) -> NOT A AND NOT B
114                let not_left: Arc<dyn PhysicalExpr> =
115                    Arc::new(NotExpr::new(Arc::clone(binary_expr.left())));
116                let not_right: Arc<dyn PhysicalExpr> =
117                    Arc::new(NotExpr::new(Arc::clone(binary_expr.right())));
118                let new_binary =
119                    Arc::new(BinaryExpr::new(not_left, Operator::And, not_right));
120                return Ok(Transformed::yes(new_binary));
121            }
122            _ => {}
123        }
124    }
125
126    // If no simplification possible, return the original expression
127    Ok(Transformed::no(expr))
128}
datafusion_physical_expr/simplifier/not.rs

datafusion_physical_expr/simplifier/
not.rs
