apache / apache/datafusion

Implement physical optimizer rule for common subexpression elimination

Open
#12,599 5 comments 0 reactions 0 assignees View on GitHub
enhancement
Dominant language
Rust
Stars
9.3k
Forks
2.4k
Avg merge
3d 7h
Merged PRs (30d)
344

Description

### 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

```sql
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

```sql
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_

Contributor guide

Open the contributing guide

Research direction

Start by locating DataFusion's existing logical common-subexpression-elimination rule and the physical optimizer entry points; the issue does not name files or tests. Use the TPC-H q1 example as the validation case, and done means the repeated l_extendedprice * (1 - l_discount) expression is evaluated once in physical plans with equivalent results.

Written by the indexing model from the issue text.

Assessment

Tech stack
rust, sql
Domain
databases, performance
Issue type
Feature
Difficulty
5/5
Estimated time
Over a week
Activity status
Stale
Clarity
Mostly clear
Newbie friendliness
35/100

Get new issues in your inbox

A short digest of beginner-friendly GitHub issues.