Optimize Presto self-join queries

[sopel39]

Case study tpcds/q95:

WITH
  ws_wh AS (
   SELECT
     "ws1"."ws_order_number"
   FROM
     ${database}.${schema}.web_sales ws1
   , ${database}.${schema}.web_sales ws2
   WHERE ("ws1"."ws_order_number" = "ws2"."ws_order_number")
      AND ("ws1"."ws_warehouse_sk" <> "ws2"."ws_warehouse_sk")
) 

Web sales tables are large and are currently read twice by Presto. However, since this is a self join Presto could wait until build side is read and feed it back as a probe side. This would save one read of web_sales table. Such optimization requires that join is executed as repartitioned join (which for large tables would be the case).

It seems that we could try to optimize self joins both before and after reorder joins rule:

• before reorder joins: we can optimize self join when cost of evaluating output of self join is smaller than cost of reading one extra copy of the table. This way even if source tables are filtered with reordered joins, the advantage of not reading one copy if the source table would still be beneficial
• after reorder joins: whenever there is a hash self join, we could optimize that join.

[sopel39]

In case of queries like:

                   InnerJoin[x1.a = x2.a]
                  /                    \
             TS[x1]                     InnerJoin[x2.a = z.a]
                                          /              \
                                      TS[x2]             TS[z]

it can still be simplified to:

                        SelfJoin[x.a = x.a]
                                 |
                        InnerJoin[x.a = z.a]
                          /              \
                     TS[x]              TS[z]

That can be simplified when either:

• z.a keys are unique
• output of InnerJoin[x1.a = x2.a] is cardinality insensitive (e.g there is group by on all columns on top of that join)