This is an automated email from the ASF dual-hosted git repository.
yiguolei pushed a commit to branch branch-2.1
in repository https://gitbox.apache.org/repos/asf/doris.git
commit 5046fa2bea46e08154b56f066642677ab2de96b4
Author: seawinde <149132972+seawi...@users.noreply.github.com>
AuthorDate: Sat May 11 11:04:38 2024 +0800
[improvement](mtmv) Split the expression mapping in
LogicalCompatibilityContext for performance (#34646)
Need query to view expression mapping when check the logic of hyper graph
is equals or not.
Getting all expression mapping one-time may affect performance. So split
the expresson to three type
JOIN_EDGE, NODE, FILTER_EDGE and get them step by step.
---
.../rules/exploration/mv/HyperGraphComparator.java | 6 +-
.../mv/LogicalCompatibilityContext.java | 97 ++++++++++++++++++----
.../nereids/rules/exploration/mv/StructInfo.java | 64 ++++++++++----
3 files changed, 132 insertions(+), 35 deletions(-)
diff --git
a/fe/fe-core/src/main/java/org/apache/doris/nereids/rules/exploration/mv/HyperGraphComparator.java
b/fe/fe-core/src/main/java/org/apache/doris/nereids/rules/exploration/mv/HyperGraphComparator.java
index 956a974982c..0c9dc9c33de 100644
---
a/fe/fe-core/src/main/java/org/apache/doris/nereids/rules/exploration/mv/HyperGraphComparator.java
+++
b/fe/fe-core/src/main/java/org/apache/doris/nereids/rules/exploration/mv/HyperGraphComparator.java
@@ -238,7 +238,7 @@ public class HyperGraphComparator {
int size = queryExprSetList.size();
for (int i = 0; i < size; i++) {
Set<Expression> mappingQueryExprSet =
queryExprSetList.get(i).stream()
- .map(e ->
logicalCompatibilityContext.getQueryToViewEdgeExpressionMapping().get(e))
+ .map(e ->
logicalCompatibilityContext.getQueryToViewAllExpressionMapping().get(e))
.collect(Collectors.toSet());
if (!mappingQueryExprSet.equals(viewExprSetList.get(i))) {
return false;
@@ -391,7 +391,7 @@ public class HyperGraphComparator {
}
private Map<Expression, Expression> getQueryToViewExprMap() {
- return
logicalCompatibilityContext.getQueryToViewEdgeExpressionMapping();
+ return
logicalCompatibilityContext.getQueryToViewAllExpressionMapping();
}
private Map<Integer, Integer> getQueryToViewNodeIdMap() {
@@ -414,7 +414,7 @@ public class HyperGraphComparator {
}
private Expression getViewExprFromQueryExpr(Expression query) {
- return
logicalCompatibilityContext.getQueryToViewEdgeExpressionMapping().get(query);
+ return
logicalCompatibilityContext.getQueryToViewAllExpressionMapping().get(query);
}
private void refreshViewEdges() {
diff --git
a/fe/fe-core/src/main/java/org/apache/doris/nereids/rules/exploration/mv/LogicalCompatibilityContext.java
b/fe/fe-core/src/main/java/org/apache/doris/nereids/rules/exploration/mv/LogicalCompatibilityContext.java
index 7f92735da64..b4ed509f300 100644
---
a/fe/fe-core/src/main/java/org/apache/doris/nereids/rules/exploration/mv/LogicalCompatibilityContext.java
+++
b/fe/fe-core/src/main/java/org/apache/doris/nereids/rules/exploration/mv/LogicalCompatibilityContext.java
@@ -19,6 +19,7 @@ package org.apache.doris.nereids.rules.exploration.mv;
import org.apache.doris.nereids.jobs.joinorder.hypergraph.node.StructInfoNode;
import org.apache.doris.nereids.memo.GroupExpression;
+import
org.apache.doris.nereids.rules.exploration.mv.StructInfo.ExpressionPosition;
import
org.apache.doris.nereids.rules.exploration.mv.mapping.Mapping.MappedRelation;
import org.apache.doris.nereids.rules.exploration.mv.mapping.RelationMapping;
import org.apache.doris.nereids.rules.exploration.mv.mapping.SlotMapping;
@@ -32,33 +33,55 @@ import org.apache.doris.nereids.trees.plans.RelationId;
import org.apache.doris.nereids.util.ExpressionUtils;
import org.apache.doris.nereids.util.Utils;
+import com.google.common.base.Suppliers;
import com.google.common.collect.BiMap;
import com.google.common.collect.HashBiMap;
import java.util.HashMap;
import java.util.Map;
+import java.util.function.Supplier;
/**
* For outer join we should check the outer join compatibility between query
and view
*/
public class LogicalCompatibilityContext {
private final BiMap<StructInfoNode, StructInfoNode> queryToViewNodeMapping;
- private final BiMap<Expression, Expression>
queryToViewEdgeExpressionMapping;
private final BiMap<Integer, Integer> queryToViewNodeIDMapping;
private final ObjectId planNodeId;
+ private final Supplier<BiMap<Expression, Expression>>
queryToViewJoinEdgeExpressionMappingSupplier;
+ private final Supplier<BiMap<Expression, Expression>>
queryToViewNodeExpressionMappingSupplier;
+ private final Supplier<BiMap<Expression, Expression>>
queryToViewFilterEdgeExpressionMappingSupplier;
+ @Deprecated
+ private BiMap<Expression, Expression> queryToViewAllExpressionMapping;
/**
* LogicalCompatibilityContext
*/
- public LogicalCompatibilityContext(BiMap<StructInfoNode, StructInfoNode>
queryToViewNodeMapping,
- BiMap<Expression, Expression> queryToViewEdgeExpressionMapping,
- StructInfo queryStructInfo) {
+ private LogicalCompatibilityContext(BiMap<StructInfoNode, StructInfoNode>
queryToViewNodeMapping,
+ Map<SlotReference, SlotReference> viewToQuerySlotMapping,
StructInfo queryStructInfo,
+ StructInfo viewStructInfo) {
+
+ this.queryToViewJoinEdgeExpressionMappingSupplier =
+ Suppliers.memoize(() ->
generateExpressionMapping(viewToQuerySlotMapping,
+
queryStructInfo.getShuttledExpressionsToExpressionsMap().get(ExpressionPosition.JOIN_EDGE),
+
viewStructInfo.getShuttledExpressionsToExpressionsMap().get(ExpressionPosition.JOIN_EDGE)));
+
+ this.queryToViewNodeExpressionMappingSupplier =
+ Suppliers.memoize(() ->
generateExpressionMapping(viewToQuerySlotMapping,
+
queryStructInfo.getShuttledExpressionsToExpressionsMap().get(ExpressionPosition.NODE),
+
viewStructInfo.getShuttledExpressionsToExpressionsMap().get(ExpressionPosition.NODE)));
+
+ this.queryToViewFilterEdgeExpressionMappingSupplier =
+ Suppliers.memoize(() ->
generateExpressionMapping(viewToQuerySlotMapping,
+
queryStructInfo.getShuttledExpressionsToExpressionsMap().get(ExpressionPosition.FILTER_EDGE),
+
viewStructInfo.getShuttledExpressionsToExpressionsMap().get(ExpressionPosition.FILTER_EDGE)));
+
this.queryToViewNodeMapping = queryToViewNodeMapping;
- this.queryToViewEdgeExpressionMapping =
queryToViewEdgeExpressionMapping;
this.queryToViewNodeIDMapping = HashBiMap.create();
+ queryToViewNodeMapping.forEach((k, v) ->
queryToViewNodeIDMapping.put(k.getIndex(), v.getIndex()));
+
this.planNodeId = queryStructInfo.getTopPlan().getGroupExpression()
.map(GroupExpression::getId).orElseGet(() -> new ObjectId(-1));
- queryToViewNodeMapping.forEach((k, v) ->
queryToViewNodeIDMapping.put(k.getIndex(), v.getIndex()));
}
public BiMap<StructInfoNode, StructInfoNode> getQueryToViewNodeMapping() {
@@ -69,8 +92,31 @@ public class LogicalCompatibilityContext {
return queryToViewNodeIDMapping;
}
- public BiMap<Expression, Expression> getQueryToViewEdgeExpressionMapping()
{
- return queryToViewEdgeExpressionMapping;
+ /**
+ * Get all expression mapping in query to view
+ */
+ @Deprecated
+ public BiMap<Expression, Expression> getQueryToViewAllExpressionMapping() {
+ if (queryToViewAllExpressionMapping != null) {
+ return queryToViewAllExpressionMapping;
+ }
+ queryToViewAllExpressionMapping = HashBiMap.create();
+
queryToViewAllExpressionMapping.putAll(getQueryToViewJoinEdgeExpressionMapping());
+
queryToViewAllExpressionMapping.putAll(getQueryToViewNodeExpressionMapping());
+
queryToViewAllExpressionMapping.putAll(getQueryToViewFilterEdgeExpressionMapping());
+ return queryToViewAllExpressionMapping;
+ }
+
+ public BiMap<Expression, Expression>
getQueryToViewJoinEdgeExpressionMapping() {
+ return queryToViewJoinEdgeExpressionMappingSupplier.get();
+ }
+
+ public BiMap<Expression, Expression> getQueryToViewNodeExpressionMapping()
{
+ return queryToViewNodeExpressionMappingSupplier.get();
+ }
+
+ public BiMap<Expression, Expression>
getQueryToViewFilterEdgeExpressionMapping() {
+ return queryToViewFilterEdgeExpressionMappingSupplier.get();
}
public ObjectId getPlanNodeId() {
@@ -104,24 +150,33 @@ public class LogicalCompatibilityContext {
// init expression mapping
Map<SlotReference, SlotReference> viewToQuerySlotMapping =
queryToViewSlotMapping.inverse()
.toSlotReferenceMap();
- Map<Expression, Expression> queryShuttledExprToExprMap =
- queryStructInfo.getShuttledHashConjunctsToConjunctsMap();
- Map<Expression, Expression> viewShuttledExprToExprMap =
- viewStructInfo.getShuttledHashConjunctsToConjunctsMap();
+ return new LogicalCompatibilityContext(queryToViewNodeMapping,
+ viewToQuerySlotMapping,
+ queryStructInfo,
+ viewStructInfo);
+ }
+
+ private static BiMap<Expression, Expression> generateExpressionMapping(
+ Map<SlotReference, SlotReference> viewToQuerySlotMapping,
+ Map<Expression, Expression> queryShuttledExprToExprMap,
+ Map<Expression, Expression> viewShuttledExprToExprMap) {
final Map<Expression, Expression> viewEdgeToConjunctsMapQueryBased =
new HashMap<>();
+ BiMap<Expression, Expression> queryToViewEdgeMapping =
HashBiMap.create();
+ if (queryShuttledExprToExprMap == null || viewShuttledExprToExprMap ==
null
+ || queryShuttledExprToExprMap.isEmpty() ||
viewShuttledExprToExprMap.isEmpty()) {
+ return queryToViewEdgeMapping;
+ }
viewShuttledExprToExprMap.forEach((shuttledExpr, expr) -> {
viewEdgeToConjunctsMapQueryBased.put(
- orderSlotAsc(ExpressionUtils.replace(shuttledExpr,
viewToQuerySlotMapping)),
- expr);
+ orderSlotAsc(ExpressionUtils.replace(shuttledExpr,
viewToQuerySlotMapping)), expr);
});
- BiMap<Expression, Expression> queryToViewEdgeMapping =
HashBiMap.create();
queryShuttledExprToExprMap.forEach((exprSet, edge) -> {
Expression viewExpr =
viewEdgeToConjunctsMapQueryBased.get(orderSlotAsc(exprSet));
if (viewExpr != null) {
queryToViewEdgeMapping.put(edge, viewExpr);
}
});
- return new LogicalCompatibilityContext(queryToViewNodeMapping,
queryToViewEdgeMapping, queryStructInfo);
+ return queryToViewEdgeMapping;
}
private static Expression orderSlotAsc(Expression expression) {
@@ -151,6 +206,14 @@ public class LogicalCompatibilityContext {
public String toString() {
return Utils.toSqlString("LogicalCompatibilityContext",
"queryToViewNodeMapping", queryToViewNodeMapping.toString(),
- "queryToViewEdgeExpressionMapping",
queryToViewEdgeExpressionMapping.toString());
+ "queryToViewJoinEdgeExpressionMapping",
+ queryToViewJoinEdgeExpressionMappingSupplier.get() == null
+ ? "" :
queryToViewJoinEdgeExpressionMappingSupplier.get().toString(),
+ "queryToViewNodeExpressionMapping",
+ queryToViewNodeExpressionMappingSupplier.get() == null
+ ? "" :
queryToViewNodeExpressionMappingSupplier.get().toString(),
+ "queryToViewFilterEdgeExpressionMapping",
+ queryToViewFilterEdgeExpressionMappingSupplier.get() == null
+ ? "" :
queryToViewFilterEdgeExpressionMappingSupplier.get().toString());
}
}
diff --git
a/fe/fe-core/src/main/java/org/apache/doris/nereids/rules/exploration/mv/StructInfo.java
b/fe/fe-core/src/main/java/org/apache/doris/nereids/rules/exploration/mv/StructInfo.java
index b617cdfe701..7f6b5f0d291 100644
---
a/fe/fe-core/src/main/java/org/apache/doris/nereids/rules/exploration/mv/StructInfo.java
+++
b/fe/fe-core/src/main/java/org/apache/doris/nereids/rules/exploration/mv/StructInfo.java
@@ -106,7 +106,7 @@ public class StructInfo {
private final EquivalenceClass equivalenceClass;
// Key is the expression shuttled and the value is the origin expression
// this is for building LogicalCompatibilityContext later.
- private final Map<Expression, Expression>
shuttledHashConjunctsToConjunctsMap;
+ private final Map<ExpressionPosition, Map<Expression, Expression>>
shuttledExpressionsToExpressionsMap;
// Record the exprId and the corresponding expr map, this is used by
expression shuttled
private final Map<ExprId, Expression> namedExprIdAndExprMapping;
@@ -117,7 +117,7 @@ public class StructInfo {
Plan bottomPlan, List<CatalogRelation> relations,
Map<RelationId, StructInfoNode> relationIdStructInfoNodeMap,
@Nullable Predicates predicates,
- Map<Expression, Expression> shuttledHashConjunctsToConjunctsMap,
+ Map<ExpressionPosition, Map<Expression, Expression>>
shuttledExpressionsToExpressionsMap,
Map<ExprId, Expression> namedExprIdAndExprMapping) {
this.originalPlan = originalPlan;
this.originalPlanId = originalPlanId;
@@ -140,7 +140,7 @@ public class StructInfo {
predicatesDerive(this.predicates, topPlan, tableBitSet);
this.splitPredicate = derivedPredicates.key();
this.equivalenceClass = derivedPredicates.value();
- this.shuttledHashConjunctsToConjunctsMap =
shuttledHashConjunctsToConjunctsMap;
+ this.shuttledExpressionsToExpressionsMap =
shuttledExpressionsToExpressionsMap;
this.namedExprIdAndExprMapping = namedExprIdAndExprMapping;
}
@@ -150,12 +150,12 @@ public class StructInfo {
public StructInfo withPredicates(Predicates predicates) {
return new StructInfo(this.originalPlan, this.originalPlanId,
this.hyperGraph, this.valid, this.topPlan,
this.bottomPlan, this.relations,
this.relationIdStructInfoNodeMap, predicates,
- this.shuttledHashConjunctsToConjunctsMap,
this.namedExprIdAndExprMapping);
+ this.shuttledExpressionsToExpressionsMap,
this.namedExprIdAndExprMapping);
}
private static boolean collectStructInfoFromGraph(HyperGraph hyperGraph,
Plan topPlan,
- Map<Expression, Expression> shuttledHashConjunctsToConjunctsMap,
+ Map<ExpressionPosition, Map<Expression, Expression>>
shuttledExpressionsToExpressionsMap,
Map<ExprId, Expression> namedExprIdAndExprMapping,
List<CatalogRelation> relations,
Map<RelationId, StructInfoNode> relationIdStructInfoNodeMap) {
@@ -189,7 +189,8 @@ public class StructInfo {
topPlan.accept(ExpressionLineageReplacer.INSTANCE,
replaceContext);
// Replace expressions by expression map
List<Expression> replacedExpressions =
replaceContext.getReplacedExpressions();
-
shuttledHashConjunctsToConjunctsMap.put(replacedExpressions.get(0),
conjunctExpr);
+
putShuttledExpressionsToExpressionsMap(shuttledExpressionsToExpressionsMap,
+ ExpressionPosition.JOIN_EDGE,
replacedExpressions.get(0), conjunctExpr);
// Record this, will be used in top level expression shuttle
later, see the method
// ExpressionLineageReplacer#visitGroupPlan
namedExprIdAndExprMapping.putAll(replaceContext.getExprIdExpressionMap());
@@ -213,7 +214,8 @@ public class StructInfo {
structInfoNode.getPlan().accept(ExpressionLineageReplacer.INSTANCE,
replaceContext);
// Replace expressions by expression map
List<Expression> replacedExpressions =
replaceContext.getReplacedExpressions();
-
shuttledHashConjunctsToConjunctsMap.put(replacedExpressions.get(0), expression);
+
putShuttledExpressionsToExpressionsMap(shuttledExpressionsToExpressionsMap,
+ ExpressionPosition.NODE,
replacedExpressions.get(0), expression);
// Record this, will be used in top level expression
shuttle later, see the method
// ExpressionLineageReplacer#visitGroupPlan
namedExprIdAndExprMapping.putAll(replaceContext.getExprIdExpressionMap());
@@ -226,8 +228,10 @@ public class StructInfo {
filterExpressions.forEach(predicate -> {
// this is used for LogicalCompatibilityContext
ExpressionUtils.extractConjunction(predicate).forEach(expr ->
-
shuttledHashConjunctsToConjunctsMap.put(ExpressionUtils.shuttleExpressionWithLineage(
- predicate, topPlan, hyperTableBitSet),
predicate));
+
putShuttledExpressionsToExpressionsMap(shuttledExpressionsToExpressionsMap,
+ ExpressionPosition.FILTER_EDGE,
+
ExpressionUtils.shuttleExpressionWithLineage(predicate, topPlan,
hyperTableBitSet),
+ predicate));
});
});
return true;
@@ -299,7 +303,8 @@ public class StructInfo {
// collect struct info fromGraph
List<CatalogRelation> relationList = new ArrayList<>();
Map<RelationId, StructInfoNode> relationIdStructInfoNodeMap = new
LinkedHashMap<>();
- Map<Expression, Expression> shuttledHashConjunctsToConjunctsMap = new
LinkedHashMap<>();
+ Map<ExpressionPosition, Map<Expression, Expression>>
shuttledHashConjunctsToConjunctsMap =
+ new LinkedHashMap<>();
Map<ExprId, Expression> namedExprIdAndExprMapping = new
LinkedHashMap<>();
boolean valid = collectStructInfoFromGraph(hyperGraph, topPlan,
shuttledHashConjunctsToConjunctsMap,
namedExprIdAndExprMapping,
@@ -359,8 +364,21 @@ public class StructInfo {
return relationIdStructInfoNodeMap;
}
- public Map<Expression, Expression>
getShuttledHashConjunctsToConjunctsMap() {
- return shuttledHashConjunctsToConjunctsMap;
+ public Map<ExpressionPosition, Map<Expression, Expression>>
getShuttledExpressionsToExpressionsMap() {
+ return shuttledExpressionsToExpressionsMap;
+ }
+
+ private static void putShuttledExpressionsToExpressionsMap(
+ Map<ExpressionPosition, Map<Expression, Expression>>
shuttledExpressionsToExpressionsMap,
+ ExpressionPosition expressionPosition,
+ Expression key, Expression value) {
+ Map<Expression, Expression> expressionExpressionMap =
shuttledExpressionsToExpressionsMap.get(
+ expressionPosition);
+ if (expressionExpressionMap == null) {
+ expressionExpressionMap = new LinkedHashMap<>();
+ shuttledExpressionsToExpressionsMap.put(expressionPosition,
expressionExpressionMap);
+ }
+ expressionExpressionMap.put(key, value);
}
public List<? extends Expression> getExpressions() {
@@ -444,7 +462,9 @@ public class StructInfo {
}
}
- /** Judge if source contains all target */
+ /**
+ * Judge if source contains all target
+ */
public static boolean containsAll(BitSet source, BitSet target) {
if (source.size() < target.size()) {
return false;
@@ -624,7 +644,9 @@ public class StructInfo {
}
}
- /**Collect partitions which scan used according to given table */
+ /**
+ * Collect partitions which scan used according to given table
+ */
public static class QueryScanPartitionsCollector extends
DefaultPlanVisitor<Plan, Map<Long, Set<PartitionItem>>> {
@Override
public Plan visitLogicalCatalogRelation(LogicalCatalogRelation
catalogRelation,
@@ -648,7 +670,9 @@ public class StructInfo {
}
}
- /**Add filter on table scan according to table filter map */
+ /**
+ * Add filter on table scan according to table filter map
+ */
public static Plan addFilterOnTableScan(Plan queryPlan, Map<TableIf,
Set<Expression>> filterOnOriginPlan,
CascadesContext parentCascadesContext) {
// Firstly, construct filter form invalid partition, this filter
should be added on origin plan
@@ -663,4 +687,14 @@ public class StructInfo {
return context.getRewritePlan();
}, queryPlanWithUnionFilter, queryPlan);
}
+
+ /**
+ * Expressions may appear in three place in hype graph, this identifies
the position where
+ * expression appear in hyper graph
+ */
+ public static enum ExpressionPosition {
+ JOIN_EDGE,
+ NODE,
+ FILTER_EDGE
+ }
}
---------------------------------------------------------------------
To unsubscribe, e-mail: commits-unsubscr...@doris.apache.org
For additional commands, e-mail: commits-h...@doris.apache.org
