You signed in with another tab or window. Reload to refresh your session.You signed out in another tab or window. Reload to refresh your session.You switched accounts on another tab or window. Reload to refresh your session.Dismiss alert
{{ message }}
Repository navigation
BinaryExpr evaluate lacks optimization for Or and And scenarios #11212
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
WHERE1=0-- This condition is always falseAND (
(total_purchases >1000AND EXTRACT(YEAR FROM registration_date) >2018)
OR (LOWER(email) LIKE'%@gmail.com'AND loyalty_points >500)
OR (
LENGTH(first_name) + LENGTH(last_name) >15AND SUBSTR(last_name, 1, 1) IN ('M', 'N', 'O', 'P')
AND DATE_PART('month', last_purchase_date) BETWEEN 6AND8
)
)
AND (
customer_id % 3=0OR EXISTS (
SELECT1FROM orders
WHEREorders.customer_id=customers.customer_idANDorders.order_status='Completed'ANDorders.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.
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.
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
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
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).
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
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
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 >1000AND EXTRACT(YEAR FROM registration_date) >2018)
OR (LOWER(email) LIKE'%@gmail.com'AND loyalty_points >500)
OR (
LENGTH(first_name) + LENGTH(last_name) >15AND SUBSTR(last_name, 1, 1) IN ('M', 'N', 'O', 'P')
AND DATE_PART('month', last_purchase_date) BETWEEN 6AND8
)
)
AND (
customer_id % 3=0OR EXISTS (
SELECT1FROM orders
WHEREorders.customer_id=customers.customer_idANDorders.order_status='Completed'ANDorders.order_total>250
)
);
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
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):
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.
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.
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
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'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
I did some more looking into the idea of using true_count in boolean kernels in arrow to speed things up (e..g special casing when BooleanArray::true_count and BooleanArray::row_count were the same to avoid actually computing the binary result
However, I concluded that since BooleanArray::true_count has to check all the values of the array anyways it might be nearly as fast to just do the binary operation (which is already quite fast) than to count the true/faslse values
@alamb I sincerely apologize for not revisiting this issue or pushing forward with that PR for such a long time. However, this optimization has led to significant performance improvements in one of our internal use cases—nearly 100 times faster. Recently, while seeing the community working on runtime filters, this issue came to mind again. I’m truly grateful for the community’s friendliness and active engagement.
Application Scenarios
Scenario 1
I attempted to reproduce our usage scenario using the hits dataset from clickbench hits:
SELECTcount(*)
FROM hits
WHERE-- Core filtering criteria: In most cases, the data can be filtered down to 0 records."UserID">7350907328996404000AND"URL"='http://smeshariki.ru/recipes/search/cuZ29vZ2xlLzcwODthZHdvcmRz&page/make=43;1334313116'-- Other filtersAND"EventTime" BETWEEN
EXTRACT(epoch FROM'2014-03-23 00:00:00'::timestamp)::BIGINTAND
EXTRACT(epoch FROM'2014-04-22 23:59:59'::timestamp)::BIGINTAND (("Age" BETWEEN 18AND35AND"Sex"='female')
OR ("Income">50000AND ("Interests" & 128) =128))
AND (
("IsMobile"=1AND"MobilePhoneModel"LIKE'iPhone%')
OR ("IsMobile"=0AND"ResolutionWidth">=1920)
)
AND"IsDownload"=0AND"IsNotBounce"=1AND"DontCountHits"=0AND split_part(split_part("URL", 'make=', 2), ';', 1) ='43'AND"UTMSource"='google_ads'AND"UTMCampaign"='spring_promo'AND"HTTPError"= CAST(200ASSMALLINT)
AND"JavascriptEnable"=1AND"CookieEnable"=1AND EXTRACT(hour FROM to_timestamp("EventTime")) BETWEEN 14AND18AND (
regexp_match("UserAgent", 'Chrome/(9[0-9]|10[0-2])') IS NOT NULLOR regexp_match("UserAgent", 'Safari/[6-8]\.') IS NOT NULL
)
AND"SocialSourceNetworkID"IN (CAST(5ASSMALLINT),CAST(12ASSMALLINT))
AND"SocialAction"='share'AND (
("ClientTimeZone" BETWEEN -5AND5AND"BrowserCountry"<>'RU')
OR ("ClientTimeZone" NOT BETWEEN -5AND5AND"BrowserCountry"='RU')
)
AND (
strpos("OriginalURL", 'utm_id=') >0OR"OpenstatCampaignID"IS NOT NULL
)
AND"Robotness"< CAST(0.3AS FLOAT)
AND"IsArtifical"=0AND"IsEvent"=1AND"IsParameter"=0;
The performance difference of this SQL compared to the main branch without short-circuit optimization is as follows, achieving a nearly 500X improvement:
Benchmark clickbench_partitioned.json
--------------------
┏━━━━━━━━━━━━━━┳━━━━━━━━━━━┳━━━━━━━━━━━━━━━━━━━┳━━━━━━━━━━━━━━━━━┓
┃ Query ┃ main ┃ add_short_circuit ┃ Change ┃
┡━━━━━━━━━━━━━━╇━━━━━━━━━━━╇━━━━━━━━━━━━━━━━━━━╇━━━━━━━━━━━━━━━━━┩
│ QQuery 0 │ 5024.39ms │ 10.16ms │ +494.40x faster │
└──────────────┴───────────┴───────────────────┴─────────────────┘
┏━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━┳━━━━━━━━━━━┓
┃ Benchmark Summary ┃ ┃
┡━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━╇━━━━━━━━━━━┩
│ Total Time (main) │ 5024.39ms │
│ Total Time (add_short_circuit) │ 10.16ms │
│ Average Time (main) │ 5024.39ms │
│ Average Time (add_short_circuit) │ 10.16ms │
│ Queries Faster │ 1 │
│ Queries Slower │ 0 │
│ Queries with No Change │ 0 │
└──────────────────────────────────┴───────────┘
Scenario 2
I also thought of a scenario where where in (subquery) could be used:
SELECTcount(*) FROM hits WHERE"UserID">7350909328996404000and"URL"in (select"URL"from hits where"URL"like'%tt%');
However, this scenario will not optimize performance, because the statement is actually a join:
This SQL query will perform extremely slowly with or without this optimization. I believe this scenario should benefit from the optimization of Dynamic Join Predicates, as mentioned by @alamb in this #7955 , referencing the duckdb blog.
Why TPCH or ClickBench Did Not Improve
TPCH
I went through each of the test SQL statements in TPCH and found that most of them focus on joins rather than point queries. Additionally, the computational load of the predicate conditions does not yield significant benefits, as illustrated by the following SQL:
selectsum(l_extendedprice * l_discount) as revenue
from
lineitem
where
l_shipdate >=date'1994-01-01'and l_shipdate <date'1995-01-01'and l_discount between 0.06-0.01and0.06+0.01and l_quantity <24;
Each predicate is based on simple comparisons and additions of numbers, which does not yield any profit.
ClickBench
There are not many SQL with more than one predicate in ClickBench, including Q21, Q22, Q36, Q37, Q38, Q39, Q40, Q41, and Q42:
SELECT"SearchPhrase", MIN("URL"), COUNT(*) AS c FROM hits WHERE"URL"LIKE'%google%'AND"SearchPhrase"<>''GROUP BY"SearchPhrase"ORDER BY c DESCLIMIT10;
SELECT"SearchPhrase", MIN("URL"), MIN("Title"), COUNT(*) AS c, COUNT(DISTINCT "UserID") FROM hits WHERE"Title"LIKE'%Google%'AND"URL" NOT LIKE'%.google.%'AND"SearchPhrase"<>''GROUP BY"SearchPhrase"ORDER BY c DESCLIMIT10;
SELECT"URL", COUNT(*) AS PageViews FROM hits WHERE"CounterID"=62AND"EventDate"::INT::DATE>='2013-07-01'AND"EventDate"::INT::DATE<='2013-07-31'AND"DontCountHits"=0AND"IsRefresh"=0AND"URL"<>''GROUP BY"URL"ORDER BY PageViews DESCLIMIT10;
SELECT"Title", COUNT(*) AS PageViews FROM hits WHERE"CounterID"=62AND"EventDate"::INT::DATE>='2013-07-01'AND"EventDate"::INT::DATE<='2013-07-31'AND"DontCountHits"=0AND"IsRefresh"=0AND"Title"<>''GROUP BY"Title"ORDER BY PageViews DESCLIMIT10;
SELECT"URL", COUNT(*) AS PageViews FROM hits WHERE"CounterID"=62AND"EventDate"::INT::DATE>='2013-07-01'AND"EventDate"::INT::DATE<='2013-07-31'AND"IsRefresh"=0AND"IsLink"<>0AND"IsDownload"=0GROUP BY"URL"ORDER BY PageViews DESCLIMIT10 OFFSET 1000;
SELECT"TraficSourceID", "SearchEngineID", "AdvEngineID", CASE WHEN ("SearchEngineID"=0AND"AdvEngineID"=0) THEN "Referer" ELSE '' END AS Src, "URL"AS Dst, COUNT(*) AS PageViews FROM hits WHERE"CounterID"=62AND"EventDate"::INT::DATE>='2013-07-01'AND"EventDate"::INT::DATE<='2013-07-31'AND"IsRefresh"=0GROUP BY"TraficSourceID", "SearchEngineID", "AdvEngineID", Src, Dst ORDER BY PageViews DESCLIMIT10 OFFSET 1000;
SELECT"URLHash", "EventDate"::INT::DATE, COUNT(*) AS PageViews FROM hits WHERE"CounterID"=62AND"EventDate"::INT::DATE>='2013-07-01'AND"EventDate"::INT::DATE<='2013-07-31'AND"IsRefresh"=0AND"TraficSourceID"IN (-1, 6) AND"RefererHash"=3594120000172545465GROUP BY"URLHash", "EventDate"::INT::DATEORDER BY PageViews DESCLIMIT10 OFFSET 100;
SELECT"WindowClientWidth", "WindowClientHeight", COUNT(*) AS PageViews FROM hits WHERE"CounterID"=62AND"EventDate"::INT::DATE>='2013-07-01'AND"EventDate"::INT::DATE<='2013-07-31'AND"IsRefresh"=0AND"DontCountHits"=0AND"URLHash"=2868770270353813622GROUP BY"WindowClientWidth", "WindowClientHeight"ORDER BY PageViews DESCLIMIT10 OFFSET 10000;
SELECT DATE_TRUNC('minute', to_timestamp_seconds("EventTime")) AS M, COUNT(*) AS PageViews FROM hits WHERE"CounterID"=62AND"EventDate"::INT::DATE>='2013-07-14'AND"EventDate"::INT::DATE<='2013-07-15'AND"IsRefresh"=0AND"DontCountHits"=0GROUP BY DATE_TRUNC('minute', to_timestamp_seconds("EventTime")) ORDER BY DATE_TRUNC('minute', M) LIMIT10 OFFSET 1000;
From the above SQLs, we can observe that:
Most of them are simple predicate conditions.
Some of the slightly more complex predicate conditions are followed by limit 10, and the computational cost of these predicate conditions is still relatively low (especially when compared to many string-matching scenarios).
Summary
Scenarios that benefit from short-circuit optimization:
The initial filter can filter out most of the data.
Subsequent filters involve time-consuming computations (e.g., operations that mostly involve matching strings longer than 1k characters, or predicates with a large number of string manipulations).
The next step would be to make a PR with the optimization -- we can then use the query in the first step to verify performance is improved and also verify other queries are not slowed down.
Activity
Dandandan commentedon Jul 2, 2024
Could you give an example where this would make a difference? We have an optimization pass
SimplifyExpressionswhich already takes care oftrueandfalseconstants inANDandORduring planning.alamb commentedon Jul 2, 2024
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 evalutingb = 10.However, for an example like
(a = 5) AND (very_expensive_udf(b) = 10)it may well be faster to do short circuting executionNote DataFusion already does short circuting for evaluating
CASEdatafusion/datafusion/physical-expr/src/expressions/case.rs
Lines 125 to 187 in 4f4cd81
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 commentedon Jul 3, 2024
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 theleftside would be sufficient to determine the result).jayzhan211 commentedon Jul 3, 2024
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
acking-you commentedon Jul 3, 2024
What I'm trying to describe is probably something like this.
acking-you commentedon Jul 3, 2024
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):
Dandandan commentedon Jul 3, 2024
Thanks for providing some benchmarks / example @acking-you !
I think the missing optimizations seem to be:
acking-you commentedon Jul 3, 2024
I think the root cause is that
leftandrightare calculated first, and then further calculations are performed based onop. 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
DataFusioncode.Possible Solutions: commit link
jayzhan211 commentedon Jul 3, 2024
I'm not sure if modifying
and / or kleenelogic 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 inNot a good idea to compute ColumnValue::Array in const_evalutorSimplifier🤔Dandandan commentedon Jul 3, 2024
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_kleenerather than inBinaryExpralone.jayzhan211 commentedon Jul 3, 2024
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
But ideally we could avoid computation of
right#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
falsestatement in the left hand side,given the queries like
a AND b AND falsewhere most of thefalsestatement 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 caseDandandan commentedon Jul 3, 2024
Hm I get where you're going at, there is some more optimization possible if we add it to
BinaryExpras wellalamb commentedon Jul 5, 2024
I believe @Dandandan filed #11262 to discuss this idea further
alamb commentedon Jul 5, 2024
I did some more looking into the idea of using
true_countin boolean kernels in arrow to speed things up (e..g special casing whenBooleanArray::true_countandBooleanArray::row_countwere the same to avoid actually computing the binary resultHowever, I concluded that since
BooleanArray::true_counthas to check all the values of the array anyways it might be nearly as fast to just do the binary operation (which is already quite fast) than to count the true/faslse valueshttps://docs.rs/arrow-array/52.0.0/src/arrow_array/array/boolean_array.rs.html#142
acking-you commentedon Mar 26, 2025
@alamb I sincerely apologize for not revisiting this issue or pushing forward with that PR for such a long time. However, this optimization has led to significant performance improvements in one of our internal use cases—nearly 100 times faster. Recently, while seeing the community working on runtime filters, this issue came to mind again. I’m truly grateful for the community’s friendliness and active engagement.
Application Scenarios
Scenario 1
I attempted to reproduce our usage scenario using the hits dataset from clickbench hits:
The performance difference of this SQL compared to the main branch without short-circuit optimization is as follows, achieving a nearly 500X improvement:
Scenario 2
I also thought of a scenario where
where in (subquery)could be used:However, this scenario will not optimize performance, because the statement is actually a join:
This SQL query will perform extremely slowly with or without this optimization. I believe this scenario should benefit from the optimization of Dynamic Join Predicates, as mentioned by @alamb in this #7955 , referencing the duckdb blog.
Why TPCH or ClickBench Did Not Improve
TPCH
I went through each of the test SQL statements in TPCH and found that most of them focus on joins rather than point queries. Additionally, the computational load of the predicate conditions does not yield significant benefits, as illustrated by the following SQL:
Each predicate is based on simple comparisons and additions of numbers, which does not yield any profit.
ClickBench
There are not many SQL with more than one predicate in ClickBench, including Q21, Q22, Q36, Q37, Q38, Q39, Q40, Q41, and Q42:
From the above SQLs, we can observe that:
limit 10, and the computational cost of these predicate conditions is still relatively low (especially when compared to many string-matching scenarios).Summary
Scenarios that benefit from short-circuit optimization:
jayzhan211 commentedon Mar 26, 2025
If we can optimize the specialized query you mentioned and not slowing down other queries, it would be nice to have it.
alamb commentedon Mar 26, 2025
Thank you for bringing this up again @acking-you
I agree with @jayzhan211 -- if we can improve performance in your scenario without slowing down other queries this is a great thing to do
Nice! Thank you for this analysis
Perhaps as a first step you could add this query (or perhaps a derivative one) to the "extended" clickbench suite (that is DataFusion specific but covers some important cases): https://github.com/apache/datafusion/tree/main/benchmarks/queries/clickbench#extended-queries
The next step would be to make a PR with the optimization -- we can then use the query in the first step to verify performance is improved and also verify other queries are not slowed down.
acking-you commentedon Mar 27, 2025
Thank you for your guidance and advice @alamb .
I will try to work on these later today (I might be a bit busy right now).
alamb commentedon Mar 27, 2025
Thanks @acking-you -- I think the benchmark is the most important thing at first
acking-you commentedon Mar 28, 2025
Thank you very much for your reply. These are some updates on this issue. @alamb:
ANDandOR#15462, you can check the details there:SQL linkMy question: Is there a pipeline in DataFusion that can automatically perform benchmark comparisons?
ANDandOR#15462 (comment) and can't pass the tests yet. I'm trying to fix them.