Stamatis Zampetakis created IMPALA-15334:
--------------------------------------------
Summary: Decompose unrewritable CTE suggestions to explore more
rewrites
Key: IMPALA-15334
URL: https://issues.apache.org/jira/browse/IMPALA-15334
Project: IMPALA
Issue Type: Sub-task
Components: Frontend
Reporter: Stamatis Zampetakis
Assignee: Stamatis Zampetakis
The [CTE
suggester|https://github.com/apache/impala/blob/7a3cb82b49d845bc5ef597e598f589593dd13549/java/calcite-planner/src/main/java/org/apache/impala/calcite/service/CalciteOptimizer.java#L384]
traverses a plan and identifies commonalities and sub-trees appearing multiple
times in the query. There are no structural restrictions on the output
suggestions thus they may contain any kind of relational expression (RelNode).
However the [rewrite
algorithm|https://github.com/apache/impala/blob/7a3cb82b49d845bc5ef597e598f589593dd13549/java/calcite-planner/src/main/java/org/apache/impala/calcite/service/CalciteOptimizer.java#L406]
imposes limitations on the structure of views/CTEs to be rewritable:
# Only Scan, Filter, Join (inner), and Project nodes, in any order
# Aggregate node followed by Scan, Filter, Join (inner), and Project nodes, in
any order
In various cases, notably TPC-DS queries the default suggester implementation
returns unrewritable CTEs. For example, for Q64 the suggester returns:
++
+cte_suggestion_2+
{noformat}
LogicalJoin(condition=[=($0, $14)], joinType=[inner])
LogicalJoin(condition=[=($0, $12)], joinType=[inner])
LogicalFilter(condition=[AND(IS NOT NULL($0), IS NOT NULL($7), IS NOT
NULL($11), IS NOT NULL($5), IS NOT NULL($1), IS NOT NULL($2), IS NOT NULL($6),
IS NOT NULL($3), IS NOT NULL($4))])
LogicalProject(ss_item_sk=[$1], ss_customer_sk=[$2], ss_cdemo_sk=[$3],
ss_hdemo_sk=[$4], ss_addr_sk=[$5], ss_store_sk=[$6], ss_promo_sk=[$7],
ss_ticket_number=[$8], ss_wholesale_cost=[$10], ss_list_price=[$11],
ss_coupon_amt=[$18], ss_sold_date_sk=[$22])
LogicalTableScan(table=[[tpcds_partitioned_parquet_snap, store_sales]])
LogicalProject(i_item_sk=[$0], i_product_name=[$3])
LogicalFilter(condition=[AND(SEARCH($2,
Sarg[_UTF-8'burlywood':VARCHAR(2147483647) CHARACTER SET "UTF-8",
_UTF-8'floral':VARCHAR(2147483647) CHARACTER SET "UTF-8",
_UTF-8'indian':VARCHAR(2147483647) CHARACTER SET "UTF-8",
_UTF-8'medium':VARCHAR(2147483647) CHARACTER SET "UTF-8",
_UTF-8'purple':VARCHAR(2147483647) CHARACTER SET "UTF-8",
_UTF-8'spring':VARCHAR(2147483647) CHARACTER SET "UTF-8"]:VARCHAR(2147483647)
CHARACTER SET "UTF-8"), SEARCH($1, Sarg[[65.00:DECIMAL(7, 2)..74.00:DECIMAL(7,
2)]]:DECIMAL(7, 2)), IS NOT NULL($0))])
LogicalProject(i_item_sk=[$0], i_current_price=[$5], i_color=[$17],
i_product_name=[$21])
LogicalTableScan(table=[[tpcds_partitioned_parquet_snap, item]])
LogicalFilter(condition=[>($1, *(2:DECIMAL(3, 0), $2))])
LogicalAggregate(group=[{0}], SALE=[SUM($1)], REFUND=[SUM($2)])
LogicalProject(CS_ITEM_SK=[$0], cs_ext_list_price=[$2], $f2=[+(+($5, $6),
$7)])
LogicalJoin(condition=[AND(=($0, $3), =($1, $4))], joinType=[inner])
LogicalFilter(condition=[AND(IS NOT NULL($0), IS NOT NULL($1))])
LogicalProject(cs_item_sk=[$14], cs_order_number=[$16],
cs_ext_list_price=[$24])
LogicalTableScan(table=[[tpcds_partitioned_parquet_snap,
catalog_sales]])
LogicalFilter(condition=[AND(IS NOT NULL($0), IS NOT NULL($1))])
LogicalProject(cr_item_sk=[$1], cr_order_number=[$15],
cr_refunded_cash=[$22], cr_reversed_charge=[$23], cr_store_credit=[$24])
LogicalTableScan(table=[[tpcds_partitioned_parquet_snap,
catalog_returns]]){noformat}
The suggestion is not rewritable cause it contains a {*}nested aggregate{*}. As
per limitation 2, only *one* top-level aggregate is allowed.
We cannot use the cte_suggestion_2 as it is but if we decompose it into
rewritable components we can still exploit some sharing possibilities. The
suggestion for Q64 can be split into two rewritable parts.
+PartA+
{noformat}
LogicalJoin(condition=[=($0, $12)], joinType=[inner])
LogicalFilter(condition=[AND(IS NOT NULL($0), IS NOT NULL($7), IS NOT
NULL($11), IS NOT NULL($5), IS NOT NULL($1), IS NOT NULL($2), IS NOT NULL($6),
IS NOT NULL($3), IS NOT NULL($4))])
LogicalProject(ss_item_sk=[$1], ss_customer_sk=[$2], ss_cdemo_sk=[$3],
ss_hdemo_sk=[$4], ss_addr_sk=[$5], ss_store_sk=[$6], ss_promo_sk=[$7],
ss_ticket_number=[$8], ss_wholesale_cost=[$10], ss_list_price=[$11],
ss_coupon_amt=[$18], ss_sold_date_sk=[$22])
LogicalTableScan(table=[[tpcds_partitioned_parquet_snap, store_sales]])
LogicalProject(i_item_sk=[$0], i_product_name=[$3])
LogicalFilter(condition=[AND(SEARCH($2,
Sarg[_UTF-8'burlywood':VARCHAR(2147483647) CHARACTER SET "UTF-8",
_UTF-8'floral':VARCHAR(2147483647) CHARACTER SET "UTF-8",
_UTF-8'indian':VARCHAR(2147483647) CHARACTER SET "UTF-8",
_UTF-8'medium':VARCHAR(2147483647) CHARACTER SET "UTF-8",
_UTF-8'purple':VARCHAR(2147483647) CHARACTER SET "UTF-8",
_UTF-8'spring':VARCHAR(2147483647) CHARACTER SET "UTF-8"]:VARCHAR(2147483647)
CHARACTER SET "UTF-8"), SEARCH($1, Sarg[[65.00:DECIMAL(7, 2)..74.00:DECIMAL(7,
2)]]:DECIMAL(7, 2)), IS NOT NULL($0))])
LogicalProject(i_item_sk=[$0], i_current_price=[$5], i_color=[$17],
i_product_name=[$21])
LogicalTableScan(table=[[tpcds_partitioned_parquet_snap, item]])
{noformat}
+PartB+
{noformat}
LogicalAggregate(group=[{0}], SALE=[SUM($1)], REFUND=[SUM($2)])
LogicalProject(CS_ITEM_SK=[$0], cs_ext_list_price=[$2], $f2=[+(+($5, $6),
$7)])
LogicalJoin(condition=[AND(=($0, $3), =($1, $4))], joinType=[inner])
LogicalFilter(condition=[AND(IS NOT NULL($0), IS NOT NULL($1))])
LogicalProject(cs_item_sk=[$14], cs_order_number=[$16],
cs_ext_list_price=[$24])
LogicalTableScan(table=[[tpcds_partitioned_parquet_snap,
catalog_sales]])
LogicalFilter(condition=[AND(IS NOT NULL($0), IS NOT NULL($1))])
LogicalProject(cr_item_sk=[$1], cr_order_number=[$15],
cr_refunded_cash=[$22], cr_reversed_charge=[$23], cr_store_credit=[$24])
LogicalTableScan(table=[[tpcds_partitioned_parquet_snap,
catalog_returns]]) {noformat}
Unrewritable suggestions occur for various other TPC-DS queries such as Q14,
Q23, Q44, Q58, Q65, and Q83.
I propose to add an additional step after the suggester to decompose
unrewritable CTE suggestions to valid rewritable candidates to explore more
rewrites.
--
This message was sent by Atlassian Jira
(v8.20.10#820010)
