[jira] [Created] (IMPALA-15523) Calcite planner: HepPlanner runs with noDag=true, so repeated subtrees are optimized again and again (q14 plans for 13 s)

["Zoltán Borók-Nagy (Jira)" <ji...@apache.org>]

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)

---------------------------------------------------------------------
To unsubscribe, e-mail: issues-all-unsubscribe@impala.apache.org
For additional commands, e-mail: issues-all-help@impala.apache.org