`BinaryExpr` evaluate lacks optimization for `Or` and `And` scenarios

[acking-you]

Describe the bug

As shown in the code link, BinaryExpr directly calculates the left and right operands without considering the possibility that left might already be false and op is And, or that left might be true and op is Or.

For example, in this complex filtering statement, unnecessary calculations will be performed:

SELECT 
    customer_id,
    first_name,
    last_name,
    email,
    total_purchases
FROM 
    customers
WHERE 
    1 = 0  -- This condition is always false
    AND (
        (total_purchases > 1000 AND EXTRACT(YEAR FROM registration_date) > 2018)
        OR (LOWER(email) LIKE '%@gmail.com' AND loyalty_points > 500)
        OR (
            LENGTH(first_name) + LENGTH(last_name) > 15
            AND SUBSTR(last_name, 1, 1) IN ('M', 'N', 'O', 'P')
            AND DATE_PART('month', last_purchase_date) BETWEEN 6 AND 8
        )
    )
    AND (
        customer_id % 3 = 0
        OR EXISTS (
            SELECT 1 
            FROM orders 
            WHERE orders.customer_id = customers.customer_id
            AND orders.order_status = 'Completed'
            AND orders.order_total > 250
        )
    );

To Reproduce

When evaluating AND or OR expressions

Expected behavior

When an And expression is executed, a false occurs to stop the computation of the result.
When an Or expression is executed, a true occurs and the result is stopped.

Additional context

No

[Dandandan]

Could you give an example where this would make a difference? We have an optimization pass SimplifyExpressions which already takes care of true and false constants in AND and OR during planning.

[alamb]

possibility that left might already be false and op is And, or that left might be true and op is Or.

In general I think there is a tradeoff between doing short circuiting (what I think this ticket is describing) and having to check if each row should be evaluted

So for a predicate like (a = 5) AND (b = 10) it is very likely faster to evaluate (a = b) and (b = 10) with very tight loops / SIMD instructions and then && the resutlting boolean together that it would be to evalute (a = b) and then have a loop that checked the result for each row when evaluting b = 10.

However, for an example like (a = 5) AND (very_expensive_udf(b) = 10) it may well be faster to do short circuting execution

Note DataFusion already does short circuting for evaluating CASE

datafusion/datafusion/physical-expr/src/expressions/case.rs

Lines 125 to 187 in 4f4cd81

	let return_type = self.data_type(&batch.schema())?;
	let expr = self.expr.as_ref().unwrap();
	let base_value = expr.evaluate(batch)?;
	let base_value = base_value.into_array(batch.num_rows())?;
	let base_nulls = is_null(base_value.as_ref())?;
	// start with nulls as default output
	let mut current_value = new_null_array(&return_type, batch.num_rows());
	// We only consider non-null values while comparing with whens
	let mut remainder = not(&base_nulls)?;
	for i in 0..self.when_then_expr.len() {
	let when_value = self.when_then_expr[i]
	.0
	.evaluate_selection(batch, &remainder)?;
	let when_value = when_value.into_array(batch.num_rows())?;
	// build boolean array representing which rows match the "when" value
	let when_match = eq(&when_value, &base_value)?;
	// Treat nulls as false
	let when_match = match when_match.null_count() {
	0 => Cow::Borrowed(&when_match),
	_ => Cow::Owned(prep_null_mask_filter(&when_match)),
	};
	// Make sure we only consider rows that have not been matched yet
	let when_match = and(&when_match, &remainder)?;
	// When no rows available for when clause, skip then clause
	if when_match.true_count() == 0 {
	continue;
	}
	let then_value = self.when_then_expr[i]
	.1
	.evaluate_selection(batch, &when_match)?;
	current_value = match then_value {
	ColumnarValue::Scalar(ScalarValue::Null) => {
	nullif(current_value.as_ref(), &when_match)?
	}
	ColumnarValue::Scalar(then_value) => {
	zip(&when_match, &then_value.to_scalar()?, &current_value)?
	}
	ColumnarValue::Array(then_value) => {
	zip(&when_match, &then_value, &current_value)?
	}
	};
	remainder = and_not(&remainder, &when_match)?;
	}
	if let Some(e) = &self.else_expr {
	// keep `else_expr`'s data type and return type consistent
	let expr = try_cast(e.clone(), &batch.schema(), return_type.clone())
	.unwrap_or_else(|_| e.clone());
	// null and unmatched tuples should be assigned else value
	remainder = or(&base_nulls, &remainder)?;
	let else_ = expr
	.evaluate_selection(batch, &remainder)?
	.into_array(batch.num_rows())?;
	current_value = zip(&remainder, &else_, &current_value)?;
	}
	Ok(ColumnarValue::Array(current_value))
	}

SO TLDR I think this would be an interesting optimization to explore and as @Dandandan notes finding some benchmarks where it matters is likely a good first step

[acking-you]

Could you give an example where this would make a difference? We have an optimization pass SimplifyExpressions which already takes care of true and false constants in AND and OR during planning.

My apologies, my example might not have been the best illustration because cases with constants are indeed optimized by the rule. What I'm trying to get at is that there's currently unnecessary computation happening within BinaryExpr (perhaps in many cases, just calculating the left side would be sufficient to determine the result).

[jayzhan211]

What I'm trying to get at is that there's currently unnecessary computation happening within BinaryExpr (perhaps in many cases, just calculating the left side would be sufficient to determine the result).

I would be surprise if there is any, could you provide the example that shows optimizer failed to do what you expect?

Here is the optimize rule that skip the right hand side if left is false

datafusion/datafusion/optimizer/src/simplify_expressions/expr_simplifier.rs

Lines 848 to 853 in 3421b52

	// false AND A --> false (even if A is null)
	Expr::BinaryExpr(BinaryExpr {
	left,
	op: And,
	right: _,
	}) if is_false(&left) => Transformed::yes(*left),

[acking-you]

What I'm trying to get at is that there's currently unnecessary computation happening within BinaryExpr (perhaps in many cases, just calculating the left side would be sufficient to determine the result).

I would be surprise if there is any, could you provide the example that shows optimizer failed to do what you expect?

Here is the optimize rule that skip the right hand side if left is false

datafusion/datafusion/optimizer/src/simplify_expressions/expr_simplifier.rs

Lines 848 to 853 in 3421b52

	// false AND A --> false (even if A is null)
	Expr::BinaryExpr(BinaryExpr {
	left,
	op: And,
	right: _,
	}) if is_false(&left) => Transformed::yes(*left),

What I'm trying to describe is probably something like this.

SELECT 
    customer_id,
    first_name,
    last_name,
    email,
    total_purchases
FROM 
    customers
WHERE 
    some_udf(first_name)  -- if this condition is mostly false at runtime.
    AND (
        (total_purchases > 1000 AND EXTRACT(YEAR FROM registration_date) > 2018)
        OR (LOWER(email) LIKE '%@gmail.com' AND loyalty_points > 500)
        OR (
            LENGTH(first_name) + LENGTH(last_name) > 15
            AND SUBSTR(last_name, 1, 1) IN ('M', 'N', 'O', 'P')
            AND DATE_PART('month', last_purchase_date) BETWEEN 6 AND 8
        )
    )
    AND (
        customer_id % 3 = 0
        OR EXISTS (
            SELECT 1 
            FROM orders 
            WHERE orders.customer_id = customers.customer_id
            AND orders.order_status = 'Completed'
            AND orders.order_total > 250
        )
    );

[acking-you]

possibility that left might already be false and op is And, or that left might be true and op is Or.

In general I think there is a tradeoff between doing short circuiting (what I think this ticket is describing) and having to check if each row should be evaluted

So for a predicate like (a = 5) AND (b = 10) it is very likely faster to evaluate (a = b) and (b = 10) with very tight loops / SIMD instructions and then && the resutlting boolean together that it would be to evalute (a = b) and then have a loop that checked the result for each row when evaluting b = 10.

However, for an example like (a = 5) AND (very_expensive_udf(b) = 10) it may well be faster to do short circuting execution

Note DataFusion already does short circuting for evaluating CASE

datafusion/datafusion/physical-expr/src/expressions/case.rs

Lines 125 to 187 in 4f4cd81

	let return_type = self.data_type(&batch.schema())?;
	let expr = self.expr.as_ref().unwrap();
	let base_value = expr.evaluate(batch)?;
	let base_value = base_value.into_array(batch.num_rows())?;
	let base_nulls = is_null(base_value.as_ref())?;
	// start with nulls as default output
	let mut current_value = new_null_array(&return_type, batch.num_rows());
	// We only consider non-null values while comparing with whens
	let mut remainder = not(&base_nulls)?;
	for i in 0..self.when_then_expr.len() {
	let when_value = self.when_then_expr[i]
	.0
	.evaluate_selection(batch, &remainder)?;
	let when_value = when_value.into_array(batch.num_rows())?;
	// build boolean array representing which rows match the "when" value
	let when_match = eq(&when_value, &base_value)?;
	// Treat nulls as false
	let when_match = match when_match.null_count() {
	0 => Cow::Borrowed(&when_match),
	_ => Cow::Owned(prep_null_mask_filter(&when_match)),
	};
	// Make sure we only consider rows that have not been matched yet
	let when_match = and(&when_match, &remainder)?;
	// When no rows available for when clause, skip then clause
	if when_match.true_count() == 0 {
	continue;
	}
	let then_value = self.when_then_expr[i]
	.1
	.evaluate_selection(batch, &when_match)?;
	current_value = match then_value {
	ColumnarValue::Scalar(ScalarValue::Null) => {
	nullif(current_value.as_ref(), &when_match)?
	}
	ColumnarValue::Scalar(then_value) => {
	zip(&when_match, &then_value.to_scalar()?, &current_value)?
	}
	ColumnarValue::Array(then_value) => {
	zip(&when_match, &then_value, &current_value)?
	}
	};
	remainder = and_not(&remainder, &when_match)?;
	}
	if let Some(e) = &self.else_expr {
	// keep `else_expr`'s data type and return type consistent
	let expr = try_cast(e.clone(), &batch.schema(), return_type.clone())
	.unwrap_or_else(|_| e.clone());
	// null and unmatched tuples should be assigned else value
	remainder = or(&base_nulls, &remainder)?;
	let else_ = expr
	.evaluate_selection(batch, &remainder)?
	.into_array(batch.num_rows())?;
	current_value = zip(&remainder, &else_, &current_value)?;
	}
	Ok(ColumnarValue::Array(current_value))
	}

SO TLDR I think this would be an interesting optimization to explore and as @Dandandan notes finding some benchmarks where it matters is likely a good first step

Adding short-circuiting after the left calculation alone resulted in performance improvements in my local TPCH tests.
commit link

Here are the test results for my local TPCH run (on my M3Pro chip with 36GB of RAM):

Comparing main and add_short_circuit
--------------------
Benchmark tpch_sf1.json
--------------------
┏━━━━━━━━━━━━━━┳━━━━━━━━━━┳━━━━━━━━━━━━━━━━━━━┳━━━━━━━━━━━━━━━┓
┃ Query        ┃     main ┃ add_short_circuit ┃        Change ┃
┡━━━━━━━━━━━━━━╇━━━━━━━━━━╇━━━━━━━━━━━━━━━━━━━╇━━━━━━━━━━━━━━━┩
│ QQuery 1     │  89.54ms │           90.81ms │     no change │
│ QQuery 2     │  24.09ms │           20.56ms │ +1.17x faster │
│ QQuery 3     │  37.53ms │           38.00ms │     no change │
│ QQuery 4     │  23.99ms │           23.73ms │     no change │
│ QQuery 5     │  61.97ms │           54.52ms │ +1.14x faster │
│ QQuery 6     │  21.62ms │           20.98ms │     no change │
│ QQuery 7     │  75.46ms │           75.51ms │     no change │
│ QQuery 8     │  49.76ms │           50.09ms │     no change │
│ QQuery 9     │  68.53ms │           68.13ms │     no change │
│ QQuery 10    │  61.78ms │           60.36ms │     no change │
│ QQuery 11    │  13.16ms │           13.55ms │     no change │
│ QQuery 12    │  34.62ms │           34.35ms │     no change │
│ QQuery 13    │  41.50ms │           42.54ms │     no change │
│ QQuery 14    │  32.07ms │           30.29ms │ +1.06x faster │
│ QQuery 15    │  43.47ms │           43.82ms │     no change │
│ QQuery 16    │  18.59ms │           16.59ms │ +1.12x faster │
│ QQuery 17    │  97.63ms │           95.67ms │     no change │
│ QQuery 18    │ 115.07ms │          111.64ms │     no change │
│ QQuery 19    │  53.83ms │           57.37ms │  1.07x slower │
│ QQuery 20    │  45.42ms │           44.09ms │     no change │
│ QQuery 21    │  82.97ms │           82.69ms │     no change │
│ QQuery 22    │  16.46ms │           13.59ms │ +1.21x faster │
└──────────────┴──────────┴───────────────────┴───────────────┘
┏━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━┳━━━━━━━━━━━┓
┃ Benchmark Summary                ┃           ┃
┡━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━╇━━━━━━━━━━━┩
│ Total Time (main)                │ 1109.06ms │
│ Total Time (add_short_circuit)   │ 1088.88ms │
│ Average Time (main)              │   50.41ms │
│ Average Time (add_short_circuit) │   49.49ms │
│ Queries Faster                   │         5 │
│ Queries Slower                   │         1 │
│ Queries with No Change           │        16 │
└──────────────────────────────────┴───────────┘

[Dandandan]

Thanks for providing some benchmarks / example @acking-you !

I think the missing optimizations seem to be:

• Checking for array.true_count() to be all zero / all true. I think this is an optimization that might be better to implement in the arrow-rs and/or (and_kleene, or_kleene) kernels as a special case instead of in DataFusion.
• UDF -> Immutable/non-volatile are executed during optimization in the constant evaluator, so the extra optimization will only apply for non-volatile UDFs.

[acking-you]

Checking for array.true_count() to be all zero / all true. I think this is an optimization that might be better to implement in the arrow-rs and/or (and_kleene, or_kleene) kernels as a special case instead of in DataFusion.

I think the root cause is that left and right are calculated first, and then further calculations are performed based on op. The specific code is in the link below:
https://github.com/apache/datafusion/blob/main/datafusion/physical-expr/src/expressions/binary.rs#L260-L261

To make changes here, you'll need to modify the DataFusion code.
Possible Solutions: commit link

[jayzhan211]

Thanks for providing some benchmarks / example @acking-you !

I think the missing optimizations seem to be:

• Checking for array.true_count() to be all zero / all true. I think this is an optimization that might be better to implement in the arrow-rs and/or (and_kleene, or_kleene) kernels as a special case instead of in DataFusion.
• UDF -> Immutable/non-volatile are executed during optimization in the constant evaluator, so the extra optimization will only apply for non-volatile UDFs.

I'm not sure if modifying and / or kleene logic help, since it needs two boolean array, but in this case we expect to short circuit if the left hand side has boolean array with all false for AND clause.

I think we might need to extend expression simplify logic for array case in Simplifier 🤔 Not a good idea to compute ColumnValue::Array in const_evalutor

[Dandandan]

I'm not sure if modifying and / or kleene logic help, since it needs two boolean array, but in this case we expect to short circuit if the left hand side has boolean array with all false for AND clause.

In the kernel we can add a fast case as well, just as @acking-you has done in his code . The benefit of this is that it will apply for any place that uses and/ and_kleene/or/or_kleene rather than in BinaryExpr alone.

[jayzhan211]

I'm not sure if modifying and / or kleene logic help, since it needs two boolean array, but in this case we expect to short circuit if the left hand side has boolean array with all false for AND clause.

In the kernel we can add a fast case as well, just as @acking-you has done in his code . The benefit of this is that it will apply for any place that uses and/ and_kleene/or/or_kleene rather than in BinaryExpr alone.

I agree that we can also optimize the kleene kernel, so we can early return the result.
But besides that we also need to find a way to avoid computation in datafusion.

Current code is like

let left: BooleanArray = expr.evalute()
let right: BooleanArray = expr.evalute()
let result = and_kleene(left, right) // we can optimize this too!

But ideally we could avoid computation of right

let left: BooleanArray = expr.evalute()
// left is always false
skip right evaluation // right evaluation is possible to be expensive
skip and_kleene

#11247 indeed did a good job, but it seems like a specialize hacking code, not sure if it is the best solution 🤔
I feel like the solution is optimizing query that has most of the false statement in the left hand side,
given the queries like a AND b AND false where most of the false statement is in the right hand side, the optimization here does not help, it is highly correlated to the benchmark we run i.e. tpch in your case

[Dandandan]

Hm I get where you're going at, there is some more optimization possible if we add it to BinaryExpr as well

[alamb]

Hm I get where you're going at, there is some more optimization possible if we add it to BinaryExpr as well

I believe @Dandandan filed #11262 to discuss this idea further