feat(Optimizer): eliminate common sub-expressions

[lokax]

Signed-off-by: lokax [email protected]

Implement this feature #658 for projection and aggregate.

I removed projection merge rule in LogicalProjection::new(), because we will need a projection below the current projection in some case.

like this:

> explain select l_extendedprice * (1 - l_discount), l_extendedprice * (1 - l_discount) * (1 + l_tax) from lineitem;
PhysicalProjection:
    InputRef #0
    (InputRef #0 * (1 + InputRef #1))
  PhysicalProjection:
      (InputRef #0 * (1 - InputRef #1))
      InputRef #2
    PhysicalTableScan:
        table #64,
        columns [5, 6, 7],
        with_row_handler: false,
        is_sorted: false,
        expr: None

In the above example, it will evaluate (1 - l_discount) 2 times and l_extendedprice * A 2 times before optimization. This would not be a problem as long as the expression itself is not expensive. However, evaluating a expensive scalar function multiple times could incur a performance overhead. After optimization, common sub-expressions are evaluated only once.

[TennyZhuang]

@st1page PTAL

[skyzh]

We need #593! 🥵

Next time for sure!

[skyzh]

I'm working on a new project https://github.com/risinglightdb/sqlplannertest-rs. With planner test, we can merge such optimizer PRs with more confidence!

[skyzh]

Hopefully I can finish it this weekend :)

[skyzh]

It's here! https://github.com/risinglightdb/risinglight/pull/661/

[skyzh]

Please add planner test cases for affected queries after #661 gets merged :)

[lokax]

It's here! #661

Thanks. 😇😇

[lokax]

Some things have been modified.

[lokax]

Thanks for the review. I have no passion to finish it. And the optimizer has been refactored. So I closed this pr.

[wangrunji0408]

Feel free to retry it on the new optimizer if you are interested. It would be easier than this one in my view. Thank you anyway! 🥰