You are viewing a plain text version of this content. The canonical link for it is here.
Posted to github@arrow.apache.org by "alamb (via GitHub)" <gi...@apache.org> on 2023/03/04 17:00:06 UTC
[GitHub] [arrow-datafusion] alamb commented on a diff in pull request #5423: feat: add optimization rules for bitwise operations
alamb commented on code in PR #5423:
URL: https://github.com/apache/arrow-datafusion/pull/5423#discussion_r1125500622
##########
datafusion/optimizer/src/simplify_expressions/expr_simplifier.rs:
##########
@@ -700,6 +705,298 @@ impl<'a, S: SimplifyInfo> ExprRewriter for Simplifier<'a, S> {
return Err(DataFusionError::ArrowError(ArrowError::DivideByZero));
}
+ //
+ // Rules for BitwiseAnd
+ //
+
+ // A & null -> null
+ Expr::BinaryExpr(BinaryExpr {
+ left: _,
+ op: BitwiseAnd,
+ right,
+ }) if is_null(&right) => *right,
+
+ // null & A -> null
+ Expr::BinaryExpr(BinaryExpr {
+ left,
+ op: BitwiseAnd,
+ right: _,
+ }) if is_null(&left) => *left,
+
+ // A & 0 -> 0 (if A not nullable)
+ Expr::BinaryExpr(BinaryExpr {
+ left,
+ op: BitwiseAnd,
+ right,
+ }) if !info.nullable(&left)? && is_zero(&right) => *right,
+
+ // 0 & A -> 0 (if A not nullable)
+ Expr::BinaryExpr(BinaryExpr {
+ left,
+ op: BitwiseAnd,
+ right,
+ }) if !info.nullable(&right)? && is_zero(&left) => *left,
+
+ // !A & A -> 0 (if A not nullable)
+ Expr::BinaryExpr(BinaryExpr {
+ left,
+ op: BitwiseAnd,
+ right,
+ }) if is_negative_of(&left, &right) && !info.nullable(&right)? => {
+ new_int_by_expr_data_type(0, &info.get_data_type(&left))
Review Comment:
I think `ScalarValue::new_zero` might be better here
https://github.com/apache/arrow-datafusion/blob/e9852074bacd8c891d84eba38b3417aa16a2d18c/datafusion/common/src/scalar.rs#L1023-L1043
##########
datafusion/optimizer/src/simplify_expressions/utils.rs:
##########
@@ -77,6 +78,61 @@ pub fn expr_contains(expr: &Expr, needle: &Expr, search_op: Operator) -> bool {
}
}
+/// Deletes all 'needles' or remains one 'needle' that are found in a chain of xor
+/// expressions. Such as: A ^ (A ^ (B ^ A))
+pub fn delete_xor_in_complex_expr(expr: &Expr, needle: &Expr, is_left: bool) -> Expr {
Review Comment:
I wonder if you could implement this using `ExprRewriter`: https://github.com/apache/arrow-datafusion/blob/e9852074bacd8c891d84eba38b3417aa16a2d18c/datafusion/expr/src/utils.rs#L519
🤔
##########
datafusion/optimizer/src/simplify_expressions/expr_simplifier.rs:
##########
@@ -1346,6 +1643,522 @@ mod tests {
assert_eq!(simplify(expr), expected);
}
+ #[test]
+ fn test_simplify_bitwise_xor_by_null() {
+ let null = Expr::Literal(ScalarValue::Null);
+ // A ^ null --> null
+ {
+ let expr = binary_expr(col("c2"), Operator::BitwiseXor, null.clone());
Review Comment:
Is there a reason you didn't use the new expr_fn's like `bitwise_xor` that were added in datafusion/expr/src/expr.rs ? I think these tessts would be significantly more concise if you did
##########
datafusion/optimizer/src/simplify_expressions/expr_simplifier.rs:
##########
@@ -700,6 +705,298 @@ impl<'a, S: SimplifyInfo> ExprRewriter for Simplifier<'a, S> {
return Err(DataFusionError::ArrowError(ArrowError::DivideByZero));
}
+ //
+ // Rules for BitwiseAnd
+ //
+
+ // A & null -> null
+ Expr::BinaryExpr(BinaryExpr {
+ left: _,
+ op: BitwiseAnd,
+ right,
+ }) if is_null(&right) => *right,
+
+ // null & A -> null
+ Expr::BinaryExpr(BinaryExpr {
+ left,
+ op: BitwiseAnd,
+ right: _,
+ }) if is_null(&left) => *left,
+
+ // A & 0 -> 0 (if A not nullable)
+ Expr::BinaryExpr(BinaryExpr {
+ left,
+ op: BitwiseAnd,
+ right,
+ }) if !info.nullable(&left)? && is_zero(&right) => *right,
+
+ // 0 & A -> 0 (if A not nullable)
+ Expr::BinaryExpr(BinaryExpr {
+ left,
+ op: BitwiseAnd,
+ right,
+ }) if !info.nullable(&right)? && is_zero(&left) => *left,
+
+ // !A & A -> 0 (if A not nullable)
+ Expr::BinaryExpr(BinaryExpr {
+ left,
+ op: BitwiseAnd,
+ right,
+ }) if is_negative_of(&left, &right) && !info.nullable(&right)? => {
+ new_int_by_expr_data_type(0, &info.get_data_type(&left))
Review Comment:
I think you could perhaps add a either `new_negative_one` or `new_int(val: i64, data_type: &DataType) -> Result<ScalarValue>` to handle the -1 case
##########
datafusion/optimizer/src/simplify_expressions/expr_simplifier.rs:
##########
@@ -700,6 +705,298 @@ impl<'a, S: SimplifyInfo> ExprRewriter for Simplifier<'a, S> {
return Err(DataFusionError::ArrowError(ArrowError::DivideByZero));
}
+ //
+ // Rules for BitwiseAnd
+ //
+
+ // A & null -> null
+ Expr::BinaryExpr(BinaryExpr {
+ left: _,
+ op: BitwiseAnd,
+ right,
+ }) if is_null(&right) => *right,
+
+ // null & A -> null
+ Expr::BinaryExpr(BinaryExpr {
+ left,
+ op: BitwiseAnd,
+ right: _,
+ }) if is_null(&left) => *left,
+
+ // A & 0 -> 0 (if A not nullable)
+ Expr::BinaryExpr(BinaryExpr {
+ left,
+ op: BitwiseAnd,
+ right,
+ }) if !info.nullable(&left)? && is_zero(&right) => *right,
+
+ // 0 & A -> 0 (if A not nullable)
+ Expr::BinaryExpr(BinaryExpr {
+ left,
+ op: BitwiseAnd,
+ right,
+ }) if !info.nullable(&right)? && is_zero(&left) => *left,
+
+ // !A & A -> 0 (if A not nullable)
+ Expr::BinaryExpr(BinaryExpr {
+ left,
+ op: BitwiseAnd,
+ right,
+ }) if is_negative_of(&left, &right) && !info.nullable(&right)? => {
+ new_int_by_expr_data_type(0, &info.get_data_type(&left))
+ }
+
+ // A & !A -> 0 (if A not nullable)
+ Expr::BinaryExpr(BinaryExpr {
+ left,
+ op: BitwiseAnd,
+ right,
+ }) if is_negative_of(&right, &left) && !info.nullable(&left)? => {
+ new_int_by_expr_data_type(0, &info.get_data_type(&left))
+ }
+
+ // (..A..) & A --> (..A..)
+ Expr::BinaryExpr(BinaryExpr {
+ left,
+ op: BitwiseAnd,
+ right,
+ }) if expr_contains(&left, &right, BitwiseAnd) => *left,
+
+ // A & (..A..) --> (..A..)
+ Expr::BinaryExpr(BinaryExpr {
+ left,
+ op: BitwiseAnd,
+ right,
+ }) if expr_contains(&right, &left, BitwiseAnd) => *right,
+
+ // A & (A | B) --> A (if B not null)
+ Expr::BinaryExpr(BinaryExpr {
+ left,
+ op: BitwiseAnd,
+ right,
+ }) if !info.nullable(&right)? && is_op_with(BitwiseOr, &right, &left) => {
+ *left
+ }
+
+ // (A | B) & A --> A (if B not null)
+ Expr::BinaryExpr(BinaryExpr {
+ left,
+ op: BitwiseAnd,
+ right,
+ }) if !info.nullable(&left)? && is_op_with(BitwiseOr, &left, &right) => {
+ *right
+ }
+
+ //
+ // Rules for BitwiseOr
+ //
+
+ // A | null -> null
+ Expr::BinaryExpr(BinaryExpr {
+ left: _,
+ op: BitwiseOr,
+ right,
+ }) if is_null(&right) => *right,
+
+ // null | A -> null
+ Expr::BinaryExpr(BinaryExpr {
+ left,
+ op: BitwiseOr,
+ right: _,
+ }) if is_null(&left) => *left,
+
+ // A | 0 -> A (if A not nullable)
Review Comment:
I think `A | 0 -> A` works even if A is nullable
##########
datafusion/optimizer/src/simplify_expressions/expr_simplifier.rs:
##########
@@ -700,6 +705,298 @@ impl<'a, S: SimplifyInfo> ExprRewriter for Simplifier<'a, S> {
return Err(DataFusionError::ArrowError(ArrowError::DivideByZero));
}
+ //
+ // Rules for BitwiseAnd
+ //
+
+ // A & null -> null
+ Expr::BinaryExpr(BinaryExpr {
+ left: _,
+ op: BitwiseAnd,
+ right,
+ }) if is_null(&right) => *right,
+
+ // null & A -> null
+ Expr::BinaryExpr(BinaryExpr {
+ left,
+ op: BitwiseAnd,
+ right: _,
+ }) if is_null(&left) => *left,
+
+ // A & 0 -> 0 (if A not nullable)
+ Expr::BinaryExpr(BinaryExpr {
+ left,
+ op: BitwiseAnd,
+ right,
+ }) if !info.nullable(&left)? && is_zero(&right) => *right,
+
+ // 0 & A -> 0 (if A not nullable)
+ Expr::BinaryExpr(BinaryExpr {
+ left,
+ op: BitwiseAnd,
+ right,
+ }) if !info.nullable(&right)? && is_zero(&left) => *left,
+
+ // !A & A -> 0 (if A not nullable)
+ Expr::BinaryExpr(BinaryExpr {
+ left,
+ op: BitwiseAnd,
+ right,
+ }) if is_negative_of(&left, &right) && !info.nullable(&right)? => {
+ new_int_by_expr_data_type(0, &info.get_data_type(&left))
+ }
+
+ // A & !A -> 0 (if A not nullable)
+ Expr::BinaryExpr(BinaryExpr {
+ left,
+ op: BitwiseAnd,
+ right,
+ }) if is_negative_of(&right, &left) && !info.nullable(&left)? => {
+ new_int_by_expr_data_type(0, &info.get_data_type(&left))
+ }
+
+ // (..A..) & A --> (..A..)
+ Expr::BinaryExpr(BinaryExpr {
+ left,
+ op: BitwiseAnd,
+ right,
+ }) if expr_contains(&left, &right, BitwiseAnd) => *left,
+
+ // A & (..A..) --> (..A..)
+ Expr::BinaryExpr(BinaryExpr {
+ left,
+ op: BitwiseAnd,
+ right,
+ }) if expr_contains(&right, &left, BitwiseAnd) => *right,
+
+ // A & (A | B) --> A (if B not null)
+ Expr::BinaryExpr(BinaryExpr {
+ left,
+ op: BitwiseAnd,
+ right,
+ }) if !info.nullable(&right)? && is_op_with(BitwiseOr, &right, &left) => {
+ *left
+ }
+
+ // (A | B) & A --> A (if B not null)
+ Expr::BinaryExpr(BinaryExpr {
+ left,
+ op: BitwiseAnd,
+ right,
+ }) if !info.nullable(&left)? && is_op_with(BitwiseOr, &left, &right) => {
+ *right
+ }
+
+ //
+ // Rules for BitwiseOr
+ //
+
+ // A | null -> null
+ Expr::BinaryExpr(BinaryExpr {
+ left: _,
+ op: BitwiseOr,
+ right,
+ }) if is_null(&right) => *right,
+
+ // null | A -> null
+ Expr::BinaryExpr(BinaryExpr {
+ left,
+ op: BitwiseOr,
+ right: _,
+ }) if is_null(&left) => *left,
+
+ // A | 0 -> A (if A not nullable)
+ Expr::BinaryExpr(BinaryExpr {
+ left,
+ op: BitwiseOr,
+ right,
+ }) if !info.nullable(&left)? && is_zero(&right) => *left,
+
+ // 0 | A -> A (if A not nullable)
+ Expr::BinaryExpr(BinaryExpr {
+ left,
+ op: BitwiseOr,
+ right,
+ }) if !info.nullable(&right)? && is_zero(&left) => *right,
+
+ // !A | A -> -1 (if A not nullable)
+ Expr::BinaryExpr(BinaryExpr {
+ left,
+ op: BitwiseOr,
+ right,
+ }) if is_negative_of(&left, &right) && !info.nullable(&right)? => {
+ new_int_by_expr_data_type(-1, &info.get_data_type(&left))
+ }
+
+ // A | !A -> -1 (if A not nullable)
+ Expr::BinaryExpr(BinaryExpr {
+ left,
+ op: BitwiseOr,
+ right,
+ }) if is_negative_of(&right, &left) && !info.nullable(&left)? => {
+ new_int_by_expr_data_type(-1, &info.get_data_type(&left))
+ }
+
+ // (..A..) | A --> (..A..)
+ Expr::BinaryExpr(BinaryExpr {
+ left,
+ op: BitwiseOr,
+ right,
+ }) if expr_contains(&left, &right, BitwiseOr) => *left,
+
+ // A | (..A..) --> (..A..)
+ Expr::BinaryExpr(BinaryExpr {
+ left,
+ op: BitwiseOr,
+ right,
+ }) if expr_contains(&right, &left, BitwiseOr) => *right,
+
+ // A | (A & B) --> A (if B not null)
+ Expr::BinaryExpr(BinaryExpr {
+ left,
+ op: BitwiseOr,
+ right,
+ }) if !info.nullable(&right)? && is_op_with(BitwiseAnd, &right, &left) => {
+ *left
+ }
+
+ // (A & B) | A --> A (if B not null)
+ Expr::BinaryExpr(BinaryExpr {
+ left,
+ op: BitwiseOr,
+ right,
+ }) if !info.nullable(&left)? && is_op_with(BitwiseAnd, &left, &right) => {
+ *right
+ }
+
+ //
+ // Rules for BitwiseXor
+ //
+
+ // A ^ null -> null
+ Expr::BinaryExpr(BinaryExpr {
+ left: _,
+ op: BitwiseXor,
+ right,
+ }) if is_null(&right) => *right,
+
+ // null ^ A -> null
+ Expr::BinaryExpr(BinaryExpr {
+ left,
+ op: BitwiseXor,
+ right: _,
+ }) if is_null(&left) => *left,
+
+ // A ^ 0 -> A (if A not nullable)
+ Expr::BinaryExpr(BinaryExpr {
+ left,
+ op: BitwiseXor,
+ right,
+ }) if !info.nullable(&left)? && is_zero(&right) => *left,
+
+ // 0 ^ A -> A (if A not nullable)
+ Expr::BinaryExpr(BinaryExpr {
+ left,
+ op: BitwiseXor,
+ right,
+ }) if !info.nullable(&right)? && is_zero(&left) => *right,
+
+ // !A ^ A -> -1 (if A not nullable)
+ Expr::BinaryExpr(BinaryExpr {
+ left,
+ op: BitwiseXor,
+ right,
+ }) if is_negative_of(&left, &right) && !info.nullable(&right)? => {
+ new_int_by_expr_data_type(-1, &info.get_data_type(&left))
+ }
+
+ // A ^ !A -> -1 (if A not nullable)
+ Expr::BinaryExpr(BinaryExpr {
+ left,
+ op: BitwiseXor,
+ right,
+ }) if is_negative_of(&right, &left) && !info.nullable(&left)? => {
+ new_int_by_expr_data_type(-1, &info.get_data_type(&left))
+ }
+
+ // (..A..) ^ A --> (the expression without A, if number of A is odd, otherwise one A)
+ Expr::BinaryExpr(BinaryExpr {
+ left,
+ op: BitwiseXor,
+ right,
+ }) if expr_contains(&left, &right, BitwiseXor) => {
+ let expr = delete_xor_in_complex_expr(&left, &right, false);
+ if expr == *right {
+ new_int_by_expr_data_type(0, &info.get_data_type(&right))
+ } else {
+ expr
+ }
+ }
+
+ // A ^ (..A..) --> (the expression without A, if number of A is odd, otherwise one A)
+ Expr::BinaryExpr(BinaryExpr {
+ left,
+ op: BitwiseXor,
+ right,
+ }) if expr_contains(&right, &left, BitwiseXor) => {
+ let expr = delete_xor_in_complex_expr(&right, &left, true);
+ if expr == *left {
+ new_int_by_expr_data_type(0, &info.get_data_type(&left))
+ } else {
+ expr
+ }
+ }
+
+ //
+ // Rules for BitwiseShiftRight
+ //
+
+ // A >> null -> null
+ Expr::BinaryExpr(BinaryExpr {
+ left: _,
+ op: BitwiseShiftRight,
+ right,
+ }) if is_null(&right) => *right,
+
+ // null >> A -> null
+ Expr::BinaryExpr(BinaryExpr {
+ left,
+ op: BitwiseShiftRight,
+ right: _,
+ }) if is_null(&left) => *left,
+
+ // A >> 0 -> A (if A not nullable)
Review Comment:
I think this still works even if A is nullable too
##########
datafusion/optimizer/src/simplify_expressions/utils.rs:
##########
@@ -154,11 +210,31 @@ pub fn is_op_with(target_op: Operator, haystack: &Expr, needle: &Expr) -> bool {
matches!(haystack, Expr::BinaryExpr(BinaryExpr { left, op, right }) if op == &target_op && (needle == left.as_ref() || needle == right.as_ref()))
}
-/// returns true if `not_expr` is !`expr`
+/// returns true if `not_expr` is !`expr` (not)
pub fn is_not_of(not_expr: &Expr, expr: &Expr) -> bool {
matches!(not_expr, Expr::Not(inner) if expr == inner.as_ref())
}
+/// returns true if `not_expr` is !`expr` (bitwise not)
+pub fn is_negative_of(not_expr: &Expr, expr: &Expr) -> bool {
+ matches!(not_expr, Expr::Negative(inner) if expr == inner.as_ref())
+}
+
+/// Returns a new int type based on data type of an expression
+pub fn new_int_by_expr_data_type(val: i64, expr_data_type: &DataType) -> Expr {
Review Comment:
does it need to be pub?
##########
datafusion/optimizer/src/simplify_expressions/utils.rs:
##########
@@ -154,11 +229,16 @@ pub fn is_op_with(target_op: Operator, haystack: &Expr, needle: &Expr) -> bool {
matches!(haystack, Expr::BinaryExpr(BinaryExpr { left, op, right }) if op == &target_op && (needle == left.as_ref() || needle == right.as_ref()))
}
-/// returns true if `not_expr` is !`expr`
+/// returns true if `not_expr` is !`expr` (not)
pub fn is_not_of(not_expr: &Expr, expr: &Expr) -> bool {
matches!(not_expr, Expr::Not(inner) if expr == inner.as_ref())
}
+/// returns true if `not_expr` is !`expr` (bitwise not)
+pub fn is_negative_of(not_expr: &Expr, expr: &Expr) -> bool {
+ matches!(not_expr, Expr::Negative(inner) if expr == inner.as_ref())
Review Comment:
Any thoughts here @izveigor ?
##########
datafusion/optimizer/src/simplify_expressions/context.rs:
##########
@@ -123,6 +126,18 @@ impl<'a> SimplifyInfo for SimplifyContext<'a> {
})
}
+ /// Returns data type of this expr needed for determining optimized int type of a value
+ fn get_data_type(&self, expr: &Expr) -> DataType {
Review Comment:
I think this should simply return the error if the data type can not be determined -- it seems wrong to treat it as a 32 bit number 🤔 .
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
To unsubscribe, e-mail: github-unsubscribe@arrow.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org