Zoltán Borók-Nagy created IMPALA-15523:
------------------------------------------
Summary: Calcite planner: HepPlanner runs with noDag=true, so
repeated subtrees are optimized again and again (q14 plans for 13 s)
Key: IMPALA-15523
URL: https://issues.apache.org/jira/browse/IMPALA-15523
Project: IMPALA
Issue Type: Improvement
Components: Frontend
Reporter: Zoltán Borók-Nagy
CalciteOptimizer.runProgram() creates its HepPlanner with noDag=true
(CalciteOptimizer.java:358-360 on master 1f34ea915e). When a WITH clause is
inlined many times, the plan contains many identical subtrees, and every copy
is optimized separately. HepPlanner also restarts the graph traversal after
each rule firing in TOP_DOWN/BOTTOM_UP order, so the cost grows roughly with
the square of the plan size.
*Data* (TPC-DS SF100, PLANNER=CALCITE vs the original planner):
* q14_1 inlines cross_items 15 times. Planning takes 13.0-14.6 s against 2.07 s
with the original planner: "optimized plan pre join" takes 2.55 s and "post
join" 9.33 s. CTE_THRESHOLD=1 does not help, because CTE detection runs after
these passes.
* Smaller cases: q64 1.04 s vs 0.22 s, q94/q16 0.36/0.40 s vs 0.06/0.09 s.
* Over the 104 queries, planning time goes from 11.5 s to 29.2 s.
*Proposal:*
* Run the expensive programs in DAG mode (noDag=false, Calcite's default): node
optimization before and after join ordering, and the join-ordering program.
Impala already uses DAG mode for subquery removal in CalciteRelNodeConverter.
* Identical subtrees then become one HepRelVertex and are optimized once.
* Before the CTE rewrite and the conversion to Impala plan nodes, turn the
result back into a tree: copy every RelNode reached a second time, with its
subtree, including LogicalTableScan/LogicalValues leaves. Tuple descriptors and
plan nodes are then never aliased.
*Prototype result:*
* Impala plans were byte-identical for all 104 TPC-DS workload queries.
* The existing Calcite planner tests pass, except for 5 conjunct-order
differences inside the Calcite-level EXPLAIN section.
* Together with IMPALA-XXXXX (keep a selective DISTINCT under semi-joins),
q14_1 went from 22.3 s to 7.0 s (MT_DOP=8, CTE_THRESHOLD=1).
--
This message was sent by Atlassian Jira
(v8.20.10#820010)
