0-overview.md

How PlanMapper works

Purpose

PlanMapper helps Hive regenerate better query plans using runtime stats. It groups entities which are semantically the same. For example, A RelNode of Calcite to express WHERE id = 1 could be equivalent with a FilterOperator of Hive. A CommonMergeJoinOperator could be linked to a MapJoinOperator converted from the CommonMergeOperator.

Groups generated by PlanMapper express such relationship so that it can propagate the final runtime stats to RelNodes or Operators in each step. https://cwiki.apache.org/confluence/display/Hive/Query+ReExecution

Flow

The following invocations happen in SemanticAnalyzer#analyzeInternal.

1. ASTConverter links ASTNodes with RelNodes
   • For table scans, ASTNode <-> RelNode
   • For predicates, ASTNode <-> RelNode <-> RelTreeSignature
2. SemanticAnalyzer links ASTNodes with Operators
   • For predicates, ASTNode <-> Operator
3. AuxOpTreeSignature MERGEs all Operators with its signature(aux sig)
4. StatsRuleProcFactory links Operators with their signatures to share runtime stats between Operators
5. ConvertJoinMapJoin links original join Operators with optimized join Operators
6. AuxOpTreeSignature MERGEs all Operators with its signature(aux sig)
7. Vectorizer links non vectorized Operators with vectorized Operators

When are groups unified?

They are grouped when any of the following conditions are satisfied.

• Any instance is shared based on ==
• Any OpTreeSignature is shared based on equals

Final intra-links

Table scan

1. ASTConverter links an ASTNode with a RelNode => ASTNode <-> RelNode
   • I guess we should link the ASTNode with an Operator
2. StatsRuleProcFactory links an Operator with OpTreeSignature => Operator <-> OpTreeSignature
3. Finally, we expect two groups exist
   • ASTNode <-> RelNode
   • Operator <-> OpTreeSignature

Filter

1. ASTConverter links an ASTNode with a RelNode => ASTNode <-> RelNode
2. ASTCionverter links an ASTNode with a rel signature => ASTNode <-> RelNode <-> RelTreeSignature
3. SemanticAnalyzer links an AST with an Operator => ASTNode <-> RelNode <-> RelTreeSignature <-> Operator
4. TableScanPPD replaces the Operator with a new Operator
5. StatsRuleProcFactory links an Operator with its signature => replaced Operator <-> OpTreeSignature
6. AuxOpTreeSignature MERGEs operators => ASTNode <-> RelNode <-> RelTreeSignature <-> Operator <-> replaced Operator <-> OpTreeSignature
7. Vectorizer links an Operator with a vectorized Operator => ASTNode <-> RelNode <-> RelTreeSignature <-> Operator <-> replaced Operator <-> OpTreeSignature <-> vectorized Operator
8. Finally, we expect one group exists
   • ASTNode <-> RelNode <-> RelTreeSignature <-> Operator <-> replaced Operator <-> OpTreeSignature <-> vectorized Operator

Join

1. StatsRuleProcFactory links an Operator with its signature => Operator <-> OpTreeSignature
2. ConvertJoinMapJoin links an Operator with an optimized Operator => Operator <-> OpTreeSignature <-> optimized Operator
3. Vectorizer links an Operator with a vectorized Operator => Operator <-> OpTreeSignature <-> optimized Operator <-> vectorized Operator
4. Finally, we expect one group exists
   • Operator <-> OpTreeSignature <-> optimized Operator <-> vectorized Operator

The others

1. StatsRuleProcFactory links an Operator with its signature => Operator <-> OpTreeSignature
2. Vectorizer links an Operator with a vectorized Operator => Operator <-> OpTreeSignature <-> vectorized Operator
3. Finally, we expect one group exists
   • Operator <-> OpTreeSignature <-> vectorized Operator

Final inter-links

Operators with the same shape are unified by StatsRuleProcFactory or AuxOpTreeSignature. For example, in the following case, TableScanOperators, FilterOperators, and SelectOperators of are unified as those have the same signatures.

EXPLAIN CBO
SELECT a.key, a.value, b.key, b.value
FROM src a
JOIN src b ON a.key = b.key
WHERE a.key != '1' AND b.key != '1'
ORDER BY a.key;

1-when-fails.md

When PlanMapper doesn't work

How it validates wrong links

PlanMapper raises an exception when objects to be linked and signatures of operators belong to different groups.

The validation doesn't happen when AuxOpTreeSignature is involved because it merges all groups into one group.

When it happens

SemanticAnalyzer could fail to link an ASTNode with an FilterOperator when CTEs are materialized.

When a CTE is materialized, CalcitePlanner#analyzeInternal could be invoked multiple times. For example, when we submit the following query,

set hive.optimize.cte.materialize.threshold=1;
set hive.optimize.cte.materialize.full.aggregate.only=false;
WITH materialized_cte AS (
  SELECT key, value FROM src WHERE key != '1'
),
another_materialized_cte AS (
  SELECT key, value FROM src WHERE key != '1'
)
SELECT a.key, a.value, b.key, b.value
FROM materialized_cte a
JOIN another_materialized_cte b ON a.key = b.key
ORDER BY a.key;

analyzeInternal is applied to the following part first.

WITH materialized_cte AS (
  SELECT key, value FROM src WHERE key != '1'
)

Then, the second part is analyzed in another cycle.

another_materialized_cte AS (
  SELECT key, value FROM src WHERE key != '1'
)

When the second analyzeInternal is executed, a group to express FROM src WHERE key != '1' has been already created with a signature. So, the step SemanticAnalyzer links ASTNodes with Operators for the second CTE hits both the group and a group generated by ASTConverter.

When it doesn't happen

Table scan

• Groups of ASTNode <-> RelNode are fully disjoint
• Groups of Operator <-> OpTreeSignature are transitionally merged into a single group

Join

• Groups of Operator <-> OpTreeSignature <-> optimized Operator <-> vectorized Operator are transitionally merged into a single group

The others

• Groups of Operator <-> OpTreeSignature <-> vectorized Operator are transitionally merged into a single group

2-approaches.md

Approaches

Options

Don't pull groups of Operators by signatures

Currently, we pull linked groups of Operators based on not only the references but also signatures of them. I guess we don't need it from a point of view of the unification or validation. AuxOpTreeSignature unifies equivalent groups on every iteration, and any code path can explicitly link an Operator and its signature.

This is the current strategy of this PR. apache/hive#5037

Give separate namespaces to each CTE

In this case, the problem never happens when groups for materialized_cte and groups for another_materialized_cte are never unified.

set hive.optimize.cte.materialize.threshold=1;
set hive.optimize.cte.materialize.full.aggregate.only=false;
WITH materialized_cte AS (
  SELECT key, value FROM src WHERE key != '1'
),
another_materialized_cte AS (
  SELECT key, value FROM src WHERE key != '1'
)
SELECT a.key, a.value, b.key, b.value
FROM materialized_cte a
JOIN another_materialized_cte b ON a.key = b.key
ORDER BY a.key;

It would lose chances to optimize the same expressions with runtime stats. For example, it is apparent that both CTEs contain the same filters.

On creating a FilterOperator, we runs PlanMapper with the merge mode

It is likelyt to work. But I feel it is semantically hard to understand. https://github.com/apache/hive/pull/5037/commits/dbfe700e51ce04adea192495276ae3100d6e566f

Combine RelNodes with RelTreeSignature

I think it doesn't work.

• The current RelTreeSignature contains noises like an alias name of HiveTableScan. We need to redesign how we generate signatures
  • We can avoid this problem if we exclude those attributes from RelTreeSignatures
• RelNodes are less informative than Operators. It is unsure that we can unify RelNodes or equivalent operators with the same RelTreeSignature
  • It would be problematic when we merge two HiveTableScans. But, we don't merge two HiveTableScans with RelTreeSignatures for now. So, it might work

This is the PR with this approach. apache/hive#5077

Merge groups whenever signatures conflict

Does this work? I would say it is always mergeable when the same OpTreeSignature is shared.