Implement physical optimizer rule for common subexpression elimination

[andygrove]

Is your feature request related to a problem or challenge?

When running TPC-H q1 in Spark + DataFusion 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

Describe the solution you'd like

I would like a physical optimizer rule in DataFusion for common subexpression elimination. IIRC, we already have a logical rule for doing this, but that does not help for projects that are using other query front ends and then mapping to DataFusion's physical plan.

An alternative option would be to implement this directly in Comet.

Describe alternatives you've considered

No response

Additional context

No response

[berkaysynnada]

We have also added this issue to our todo's (though we likely won't be able to address it in the short term). It would be better to have this rule implemented directly in DataFusion.

[alamb]

@peter-toth and several others have invested significant time making the CSE pass in the logical optimizer fast and efficient

The logical rewrite code is here https://github.com/apache/datafusion/blob/2e274bfbdfc19f11b2951456bb2a48e88733c9bf/datafusion/optimizer/src/common_subexpr_eliminate.rs#L1-L0

It would be sweet somehow to factor out the CSE logic itself so it worked on both LogicalPlan and ExecutionPlan

[peter-toth]

Thanks @alamb for pinging me! I was a bit busy lately, but I'm happy to look into this issue next week or so.

[peter-toth]

Just a quick update that I've started working on this. Will try to submit a PR this week.

[peter-toth]

@alamb, I'm still working on this, but opened 2 prerequisite PRs: #13002, #13005