Skip to content

Implement Common Subexpression Elimination optimizer rule #942

Closed

Description

@andygrove

What is the problem the feature request solves?

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;

Timings (Original)

13.752424478530884,
11.648030281066895,
11.35965895652771,
11.335061311721802,
11.383593797683716,
11.291191101074219,
11.31091046333313,
11.351991653442383,
11.32134222984314,
11.374904155731201

Timings (Optimized)

12.734412908554077,
10.684742212295532,
10.157625198364258,
10.06518030166626,
10.043614149093628,
9.986022233963013,
9.939271688461304,
9.925782918930054,
10.024176120758057,
10.018519401550293

Spark UI (Original)

Screenshot from 2024-09-13 12-16-22

Spark UI (Optimized)

Screenshot from 2024-09-13 12-15-51

Describe the potential solution

No response

Additional context

No response

Activity

  1. viirya commented on Sep 13, 2024

    @viirya
    Member

    Good finding. I think this kind of optimization should be in Spark optimizer instead.

  2. viirya commented on Sep 13, 2024

    @viirya
    Member

    I remember Spark SQL has corresponding optimization rule. But not sure why it doesn't affect the query.

  3. andygrove commented on Sep 15, 2024

    @andygrove
    MemberAuthor

    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.

  4. viirya commented on Sep 15, 2024

    @viirya
    Member

    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.

  5. changed the title [-]Implement Common Subquery Elimination optimizer rule[/-] [+]Implement Common Subexpression Elimination optimizer rule[/+] on Sep 23, 2024
  6. andygrove commented on Sep 24, 2024

    @andygrove
    MemberAuthor

    Good finding. I think this kind of optimization should be in Spark optimizer instead.

    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

  7. eejbyfeldt commented on Sep 25, 2024

    @eejbyfeldt
    Contributor
  8. andygrove commented on Oct 22, 2024

    @andygrove
    MemberAuthor

    There is now a DataFusion PR to add this feature: apache/datafusion#13046

  9. added this to the 0.4.0 milestone on Oct 22, 2024
  10. modified the milestones: 0.4.0, 0.5.0 on Nov 11, 2024
  11. modified the milestones: 0.5.0, 0.6.0 on Jan 7, 2025
  12. removed this from the 0.6.0 milestone on Jan 24, 2025
  13. andygrove commented on Jan 29, 2025

    @andygrove
    MemberAuthor

    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.

  14. modified the milestones: 0.6.0, 0.7.0, 0.8.0 on Jan 29, 2025
  15. removed this from the 0.8.0 milestone on Apr 7, 2025
  16. andygrove commented on Feb 11, 2026

    @andygrove
    MemberAuthor

    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

    Related upstream work

    Key challenges for future attempts

    1. 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.
    2. 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.).
    3. Spark already does codegen-level CSE: As @eejbyfeldt noted, 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
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment

Metadata

Metadata

Assignees

No one assigned

    Type

    No type

    Projects

    No projects

      Milestone

      No milestone

      Relationships

      None yet

      Development

      No branches or pull requests

      Issue actions