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
Implement Common Subexpression Elimination optimizer rule #942
When running TPC-H q1 in Spark/Comet, the expression l_extendedprice#21 * (1 - l_discount#22) appears twice in the query and currently gets evaluated twice. This could be optimized out so that it is only evaluated once. I was able to test this by manually rewriting the query.
Original Query
select
l_returnflag,
l_linestatus,
sum(l_quantity) as sum_qty,
sum(l_extendedprice) as sum_base_price,
sum(l_extendedprice * (1- l_discount)) as sum_disc_price,
sum(l_extendedprice * (1- l_discount) * (1+ l_tax)) as sum_charge,
avg(l_quantity) as avg_qty,
avg(l_extendedprice) as avg_price,
avg(l_discount) as avg_disc,
count(*) as count_order
from
lineitem
where
l_shipdate <=date'1998-12-01'- interval '68 days'group by
l_returnflag,
l_linestatus
order by
l_returnflag,
l_linestatus;
Optimized Query
select
l_returnflag,
l_linestatus,
sum(l_quantity) as sum_qty,
sum(l_extendedprice) as sum_base_price,
sum(foo) as sum_disc_price,
sum(foo * (1+ l_tax)) as sum_charge,
avg(l_quantity) as avg_qty,
avg(l_extendedprice) as avg_price,
avg(l_discount) as avg_disc,
count(*) as count_order
from (select
l_returnflag,
l_linestatus,
l_quantity,
l_extendedprice,
l_extendedprice * (1- l_discount) as foo,
l_tax,
l_discount
from lineitem
where
l_shipdate <=date'1998-12-01'- interval '68 days')
group by
l_returnflag,
l_linestatus
order by
l_returnflag,
l_linestatus;
Related to this, it would be nice if we could improve the metrics for CometHashAggregate to show the time for evaluating the aggregate input expressions. I am not sure how much work that would be though.
Related to this, it would be nice if we could improve the metrics for CometHashAggregate to show the time for evaluating the aggregate input expressions. I am not sure how much work that would be though.
Sounds good. It should be added into DataFusion hash aggregate operator.
changed the title [-]Implement Common Subquery Elimination optimizer rule[/-][+]Implement Common Subexpression Elimination optimizer rule[/+]on Sep 23, 2024
Notes from CSE optimizer implementation attempt (PR #3444)
Note: This summary was generated by AI (Claude) based on the issue history, PR #3444, and related upstream discussions. It may contain inaccuracies.
Closing PR #3444 since the benchmarks did not show meaningful improvement, but documenting learnings here for anyone who wants to revisit this in the future.
What was implemented
A Rust-based physical CSE optimizer rule (physical_cse.rs, ~611 lines) that:
Runs as a DataFusion PhysicalOptimizerRule on the native plan before execution
Walks the plan bottom-up, looking for repeated subexpressions within ProjectionExec and AggregateExec nodes
When duplicates are found, inserts an intermediate ProjectionExec that computes the common subexpression once, then rewrites the parent node to reference the pre-computed column
Skips trivial expressions (columns, literals) and volatile expressions
When nested common subexpressions exist, only extracts the outermost one to avoid unused intermediate columns
The PR also added:
A config spark.comet.exec.nativePhysicalOptimizer.enabled to toggle the optimizer
A mechanism to pass DataFusion configs from Spark via spark.comet.datafusion.* prefix
What the benchmarks showed
The rule correctly identified the common subexpression in TPC-H Q1 (l_extendedprice * (1 - l_discount)), but the automated TPC-H SF100 benchmark showed 0.0% total improvement across all 22 queries. Q1 specifically showed +0.8% (within noise). This is surprising given that the original manual SQL rewrite in this issue showed ~10-12% improvement on Q1.
Possible explanations for the gap:
The manual rewrite may have benefited from other Spark optimizer effects (e.g., different plan shape)
The overhead of the extra ProjectionExec node (memory allocation, column copying) may offset the savings from avoiding redundant computation
The benchmark environment (SF100 on a single machine with local[*]) may behave differently than the original test setup
CPU instruction caches and vectorization effects may make redundant evaluation cheaper than the extra projection indirection
DataFusion PR: Add Common Subexpression Elimination for PhysicalExpr trees datafusion#13046 (closed/stale) — this was a more general approach by @peter-toth for CSE on PhysicalExpr trees. It was closed because: "the main usecase for physical plan CSE is Comet, I will reopen this PR once we figured out the metrics related issues due to extra projections added by CSE."
Key challenges for future attempts
Metrics tracking: Extra ProjectionExec nodes inserted by CSE break the 1:1 mapping between Spark plan nodes and native plan nodes, which complicates metrics reporting back to Spark. This was also the blocker for the upstream DataFusion PR.
Cost-benefit tradeoff: For simple arithmetic (multiply, subtract), the cost of adding a projection (allocating arrays, copying data) can exceed the cost of just recomputing the expression. CSE may only pay off for expensive subexpressions (UDFs, complex string operations, regex, etc.).
Spark already does codegen-level CSE: As @eejbyfeldtnoted, Spark handles this at the codegen level (CodeGenerator.scala), not at the plan level. A plan-level approach has inherently more overhead.
Recommendations
If revisiting, consider targeting only expensive subexpressions rather than all duplicates
Consider implementing CSE at the expression evaluation level (like Spark does) rather than at the plan level, to avoid the overhead of extra projection nodes
The spark.comet.datafusion.* config passthrough mechanism from this PR may be worth landing independently, as it's useful beyond CSE
Activity
viirya commentedon Sep 13, 2024
Good finding. I think this kind of optimization should be in Spark optimizer instead.
viirya commentedon Sep 13, 2024
I remember Spark SQL has corresponding optimization rule. But not sure why it doesn't affect the query.
andygrove commentedon Sep 15, 2024
Related to this, it would be nice if we could improve the metrics for CometHashAggregate to show the time for evaluating the aggregate input expressions. I am not sure how much work that would be though.
viirya commentedon Sep 15, 2024
Sounds good. It should be added into DataFusion hash aggregate operator.
[-]Implement Common Subquery Elimination optimizer rule[/-][+]Implement Common Subexpression Elimination optimizer rule[/+]andygrove commentedon Sep 24, 2024
It would make sense for Spark to add this, but I think that it could also be beneficial for DataFusion to support this as a physical optimizer rule.
I filed apache/datafusion#12599
eejbyfeldt commentedon Sep 25, 2024
Spark has it, but not at the plan level. Instead they do it as part of their code generation: https://github.com/apache/spark/blob/v3.5.3/sql/catalyst/src/main/scala/org/apache/spark/sql/catalyst/expressions/codegen/CodeGenerator.scala#L1064-L1098C1
andygrove commentedon Oct 22, 2024
There is now a DataFusion PR to add this feature: apache/datafusion#13046
andygrove commentedon Jan 29, 2025
The DataFusion PR apache/datafusion#13046 is still waiting for a review. I am adding this issue back onto the 0.6 milestone as a reminder.
andygrove commentedon Feb 11, 2026
Notes from CSE optimizer implementation attempt (PR #3444)
Closing PR #3444 since the benchmarks did not show meaningful improvement, but documenting learnings here for anyone who wants to revisit this in the future.
What was implemented
A Rust-based physical CSE optimizer rule (
physical_cse.rs, ~611 lines) that:PhysicalOptimizerRuleon the native plan before executionProjectionExecandAggregateExecnodesProjectionExecthat computes the common subexpression once, then rewrites the parent node to reference the pre-computed columnThe PR also added:
spark.comet.exec.nativePhysicalOptimizer.enabledto toggle the optimizerspark.comet.datafusion.*prefixWhat the benchmarks showed
The rule correctly identified the common subexpression in TPC-H Q1 (
l_extendedprice * (1 - l_discount)), but the automated TPC-H SF100 benchmark showed 0.0% total improvement across all 22 queries. Q1 specifically showed +0.8% (within noise). This is surprising given that the original manual SQL rewrite in this issue showed ~10-12% improvement on Q1.Possible explanations for the gap:
ProjectionExecnode (memory allocation, column copying) may offset the savings from avoiding redundant computationlocal[*]) may behave differently than the original test setupRelated upstream work
PhysicalExprtrees datafusion#13046 (closed/stale) — this was a more general approach by @peter-toth for CSE onPhysicalExprtrees. It was closed because: "the main usecase for physical plan CSE is Comet, I will reopen this PR once we figured out the metrics related issues due to extra projections added by CSE."Key challenges for future attempts
ProjectionExecnodes inserted by CSE break the 1:1 mapping between Spark plan nodes and native plan nodes, which complicates metrics reporting back to Spark. This was also the blocker for the upstream DataFusion PR.Recommendations
spark.comet.datafusion.*config passthrough mechanism from this PR may be worth landing independently, as it's useful beyond CSE