This is an automated email from the ASF dual-hosted git repository.
jakevin pushed a commit to branch master
in repository https://gitbox.apache.org/repos/asf/doris.git
The following commit(s) were added to refs/heads/master by this push:
new 58e7ad82b50 [feature](Nereids): support infer join when comapring mv
(#28988)
58e7ad82b50 is described below
commit 58e7ad82b504897882b90d21cbe0aeef94186c7f
Author: 谢健 <jianx...@gmail.com>
AuthorDate: Wed Dec 27 10:40:44 2023 +0800
[feature](Nereids): support infer join when comapring mv (#28988)
---
.../jobs/joinorder/hypergraph/HyperGraph.java | 171 +-----------
.../jobs/joinorder/hypergraph/edge/Edge.java | 40 ++-
.../jobs/joinorder/hypergraph/edge/JoinEdge.java | 12 +
.../rules/exploration/mv/ComparisonResult.java | 41 ++-
.../rules/exploration/mv/HyperGraphComparator.java | 299 +++++++++++++++++++++
.../nereids/rules/exploration/mv/StructInfo.java | 3 +-
.../nereids/trees/plans/logical/LogicalJoin.java | 5 +
.../joinorder/hypergraph/CompareOuterJoinTest.java | 25 +-
...ompareOuterJoinTest.java => InferJoinTest.java} | 105 +++-----
.../joinorder/hypergraph/PullupExpressionTest.java | 9 +-
.../rules/exploration/mv/BuildStructInfoTest.java | 4 +-
11 files changed, 444 insertions(+), 270 deletions(-)
diff --git
a/fe/fe-core/src/main/java/org/apache/doris/nereids/jobs/joinorder/hypergraph/HyperGraph.java
b/fe/fe-core/src/main/java/org/apache/doris/nereids/jobs/joinorder/hypergraph/HyperGraph.java
index 7bd33c64b3c..f094efe7180 100644
---
a/fe/fe-core/src/main/java/org/apache/doris/nereids/jobs/joinorder/hypergraph/HyperGraph.java
+++
b/fe/fe-core/src/main/java/org/apache/doris/nereids/jobs/joinorder/hypergraph/HyperGraph.java
@@ -27,8 +27,6 @@ import
org.apache.doris.nereids.jobs.joinorder.hypergraph.node.DPhyperNode;
import org.apache.doris.nereids.jobs.joinorder.hypergraph.node.StructInfoNode;
import org.apache.doris.nereids.memo.Group;
import org.apache.doris.nereids.memo.GroupExpression;
-import org.apache.doris.nereids.rules.exploration.mv.ComparisonResult;
-import
org.apache.doris.nereids.rules.exploration.mv.LogicalCompatibilityContext;
import org.apache.doris.nereids.rules.rewrite.PushDownFilterThroughJoin;
import org.apache.doris.nereids.trees.expressions.Alias;
import org.apache.doris.nereids.trees.expressions.Expression;
@@ -44,20 +42,14 @@ import
org.apache.doris.nereids.trees.plans.logical.LogicalProject;
import org.apache.doris.nereids.util.PlanUtils;
import com.google.common.base.Preconditions;
-import com.google.common.collect.ImmutableList;
-import com.google.common.collect.ImmutableMap;
import com.google.common.collect.ImmutableSet;
import com.google.common.collect.Lists;
-import com.google.common.collect.Sets;
import java.util.ArrayList;
import java.util.BitSet;
import java.util.HashMap;
-import java.util.HashSet;
import java.util.List;
import java.util.Map;
-import java.util.Map.Entry;
-import java.util.Optional;
import java.util.Set;
import java.util.stream.Collectors;
@@ -272,11 +264,11 @@ public class HyperGraph {
filterEdges.forEach(e -> {
if (LongBitmap.isSubset(e.getReferenceNodes(), leftSubNodes)
&&
!PushDownFilterThroughJoin.COULD_PUSH_THROUGH_LEFT.contains(joinEdge.getJoinType()))
{
- e.addRejectEdge(joinEdge);
+ e.addLeftRejectEdge(joinEdge);
}
if (LongBitmap.isSubset(e.getReferenceNodes(), rightSubNodes)
&&
!PushDownFilterThroughJoin.COULD_PUSH_THROUGH_RIGHT.contains(joinEdge.getJoinType()))
{
- e.addRejectEdge(joinEdge);
+ e.addRightRejectEdge(joinEdge);
}
});
}
@@ -293,11 +285,11 @@ public class HyperGraph {
JoinEdge childA = joinEdges.get(i);
if (!JoinType.isAssoc(childA.getJoinType(), edgeB.getJoinType())) {
leftRequired = LongBitmap.newBitmapUnion(leftRequired,
childA.getLeftSubNodes(joinEdges));
- childA.addRejectEdge(edgeB);
+ childA.addLeftRejectEdge(edgeB);
}
if (!JoinType.isLAssoc(childA.getJoinType(), edgeB.getJoinType()))
{
leftRequired = LongBitmap.newBitmapUnion(leftRequired,
childA.getRightSubNodes(joinEdges));
- childA.addRejectEdge(edgeB);
+ childA.addLeftRejectEdge(edgeB);
}
}
@@ -305,11 +297,11 @@ public class HyperGraph {
JoinEdge childA = joinEdges.get(i);
if (!JoinType.isAssoc(edgeB.getJoinType(), childA.getJoinType())) {
rightRequired = LongBitmap.newBitmapUnion(rightRequired,
childA.getRightSubNodes(joinEdges));
- childA.addRejectEdge(edgeB);
+ childA.addRightRejectEdge(edgeB);
}
if (!JoinType.isRAssoc(edgeB.getJoinType(), childA.getJoinType()))
{
rightRequired = LongBitmap.newBitmapUnion(rightRequired,
childA.getLeftSubNodes(joinEdges));
- childA.addRejectEdge(edgeB);
+ childA.addRightRejectEdge(edgeB);
}
}
edgeB.setLeftExtendedNodes(leftRequired);
@@ -597,157 +589,6 @@ public class HyperGraph {
return joinEdges.size() + filterEdges.size();
}
- /**
- * compare hypergraph
- *
- * @param viewHG the compared hyper graph
- * @return Comparison result
- */
- public ComparisonResult isLogicCompatible(HyperGraph viewHG,
LogicalCompatibilityContext ctx) {
- // 1 try to construct a map which can be mapped from edge to edge
- Map<Edge, Edge> queryToView = constructMapWithNode(viewHG,
ctx.getQueryToViewNodeIDMapping());
-
- // 2. compare them by expression and extract residual expr
- ComparisonResult.Builder builder = new ComparisonResult.Builder();
- ComparisonResult edgeCompareRes = compareEdgesWithExpr(queryToView,
ctx.getQueryToViewEdgeExpressionMapping());
- if (edgeCompareRes.isInvalid()) {
- return ComparisonResult.INVALID;
- }
- builder.addComparisonResult(edgeCompareRes);
-
- // 3. pull join edge of view is no sense, so reject them
- if (!queryToView.values().containsAll(viewHG.joinEdges)) {
- return ComparisonResult.INVALID;
- }
-
- // 4. process residual edges
- List<Expression> residualQueryJoin =
- processOrphanEdges(Sets.difference(Sets.newHashSet(joinEdges),
queryToView.keySet()));
- if (residualQueryJoin == null) {
- return ComparisonResult.INVALID;
- }
- builder.addQueryExpressions(residualQueryJoin);
-
- List<Expression> residualQueryFilter =
-
processOrphanEdges(Sets.difference(Sets.newHashSet(filterEdges),
queryToView.keySet()));
- if (residualQueryFilter == null) {
- return ComparisonResult.INVALID;
- }
- builder.addQueryExpressions(residualQueryFilter);
-
- List<Expression> residualViewFilter =
- processOrphanEdges(
- Sets.difference(Sets.newHashSet(viewHG.filterEdges),
Sets.newHashSet(queryToView.values())));
- if (residualViewFilter == null) {
- return ComparisonResult.INVALID;
- }
- builder.addViewExpressions(residualViewFilter);
-
- return builder.build();
- }
-
- private List<Expression> processOrphanEdges(Set<Edge> edges) {
- List<Expression> expressions = new ArrayList<>();
- for (Edge edge : edges) {
- if (!edge.canPullUp()) {
- return null;
- }
- expressions.addAll(edge.getExpressions());
- }
- return expressions;
- }
-
- private Map<Edge, Edge> constructMapWithNode(HyperGraph viewHG,
Map<Integer, Integer> nodeMap) {
- // TODO use hash map to reduce loop
- Map<Edge, Edge> joinEdgeMap = joinEdges.stream().map(qe -> {
- Optional<JoinEdge> viewEdge = viewHG.joinEdges.stream()
- .filter(ve -> compareEdgeWithNode(qe, ve,
nodeMap)).findFirst();
- return Pair.of(qe, viewEdge);
- }).filter(e ->
e.second.isPresent()).collect(ImmutableMap.toImmutableMap(p -> p.first, p ->
p.second.get()));
- Map<Edge, Edge> filterEdgeMap = filterEdges.stream().map(qe -> {
- Optional<FilterEdge> viewEdge = viewHG.filterEdges.stream()
- .filter(ve -> compareEdgeWithNode(qe, ve,
nodeMap)).findFirst();
- return Pair.of(qe, viewEdge);
- }).filter(e ->
e.second.isPresent()).collect(ImmutableMap.toImmutableMap(p -> p.first, p ->
p.second.get()));
- return ImmutableMap.<Edge,
Edge>builder().putAll(joinEdgeMap).putAll(filterEdgeMap).build();
- }
-
- private boolean compareEdgeWithNode(Edge t, Edge o, Map<Integer, Integer>
nodeMap) {
- if (t instanceof FilterEdge && o instanceof FilterEdge) {
- return compareEdgeWithFilter((FilterEdge) t, (FilterEdge) o,
nodeMap);
- } else if (t instanceof JoinEdge && o instanceof JoinEdge) {
- return compareJoinEdge((JoinEdge) t, (JoinEdge) o, nodeMap);
- }
- return false;
- }
-
- private boolean compareEdgeWithFilter(FilterEdge t, FilterEdge o,
Map<Integer, Integer> nodeMap) {
- long tChild = t.getReferenceNodes();
- long oChild = o.getReferenceNodes();
- return compareNodeMap(tChild, oChild, nodeMap);
- }
-
- private boolean compareJoinEdge(JoinEdge t, JoinEdge o, Map<Integer,
Integer> nodeMap) {
- long tLeft = t.getLeftExtendedNodes();
- long tRight = t.getRightExtendedNodes();
- long oLeft = o.getLeftExtendedNodes();
- long oRight = o.getRightExtendedNodes();
- if (!t.getJoinType().equals(o.getJoinType()) &&
!t.getJoinType().swap().equals(o.getJoinType())) {
- return false;
- }
- boolean matched = false;
- if (t.getJoinType().swap().equals(o.getJoinType())) {
- matched |= compareNodeMap(tRight, oLeft, nodeMap) &&
compareNodeMap(tLeft, oRight, nodeMap);
- }
- matched |= compareNodeMap(tLeft, oLeft, nodeMap) &&
compareNodeMap(tRight, oRight, nodeMap);
- return matched;
- }
-
- private boolean compareNodeMap(long bitmap1, long bitmap2, Map<Integer,
Integer> nodeIDMap) {
- long newBitmap1 = LongBitmap.newBitmap();
- for (int i : LongBitmap.getIterator(bitmap1)) {
- int mappedI = nodeIDMap.getOrDefault(i, 0);
- newBitmap1 = LongBitmap.set(newBitmap1, mappedI);
- }
- return bitmap2 == newBitmap1;
- }
-
- private ComparisonResult compareEdgesWithExpr(Map<Edge, Edge>
queryToViewedgeMap,
- Map<Expression, Expression> queryToView) {
- ComparisonResult.Builder builder = new ComparisonResult.Builder();
- for (Entry<Edge, Edge> e : queryToViewedgeMap.entrySet()) {
- ComparisonResult res = compareEdgeWithExpr(e.getKey(),
e.getValue(), queryToView);
- if (res.isInvalid()) {
- return ComparisonResult.INVALID;
- }
- builder.addComparisonResult(res);
- }
- return builder.build();
- }
-
- private ComparisonResult compareEdgeWithExpr(Edge query, Edge view,
Map<Expression, Expression> queryToView) {
- Set<? extends Expression> queryExprSet = query.getExpressionSet();
- Set<? extends Expression> viewExprSet = view.getExpressionSet();
-
- Set<Expression> equalViewExpr = new HashSet<>();
- List<Expression> residualQueryExpr = new ArrayList<>();
- for (Expression queryExpr : queryExprSet) {
- if (queryToView.containsKey(queryExpr) &&
viewExprSet.contains(queryToView.get(queryExpr))) {
- equalViewExpr.add(queryToView.get(queryExpr));
- } else {
- residualQueryExpr.add(queryExpr);
- }
- }
- List<Expression> residualViewExpr =
ImmutableList.copyOf(Sets.difference(viewExprSet, equalViewExpr));
- if (!residualViewExpr.isEmpty() && !view.canPullUp()) {
- return ComparisonResult.INVALID;
- }
- if (!residualQueryExpr.isEmpty() && !query.canPullUp()) {
- return ComparisonResult.INVALID;
- }
- return new ComparisonResult(residualQueryExpr, residualViewExpr);
- }
-
/**
* For the given hyperGraph, make a textual representation in the form
* of a dotty graph. You can save this to a file and then use Graphviz
diff --git
a/fe/fe-core/src/main/java/org/apache/doris/nereids/jobs/joinorder/hypergraph/edge/Edge.java
b/fe/fe-core/src/main/java/org/apache/doris/nereids/jobs/joinorder/hypergraph/edge/Edge.java
index c47300922b5..9bdb9ac272f 100644
---
a/fe/fe-core/src/main/java/org/apache/doris/nereids/jobs/joinorder/hypergraph/edge/Edge.java
+++
b/fe/fe-core/src/main/java/org/apache/doris/nereids/jobs/joinorder/hypergraph/edge/Edge.java
@@ -25,6 +25,7 @@ import org.apache.doris.nereids.trees.expressions.Slot;
import com.google.common.collect.ImmutableSet;
import java.util.BitSet;
+import java.util.HashSet;
import java.util.List;
import java.util.Set;
@@ -53,7 +54,8 @@ public abstract class Edge {
// record all sub nodes behind in this operator. It's T function in paper
private final long subTreeNodes;
- private long rejectNodes = 0;
+ private final Set<JoinEdge> leftRejectEdges;
+ private final Set<JoinEdge> rightRejectEdges;
/**
* Create simple edge.
@@ -69,14 +71,36 @@ public abstract class Edge {
this.leftExtendedNodes = leftRequiredNodes;
this.rightExtendedNodes = rightRequiredNodes;
this.subTreeNodes = subTreeNodes;
+ this.leftRejectEdges = new HashSet<>();
+ this.rightRejectEdges = new HashSet<>();
}
public boolean isSimple() {
return LongBitmap.getCardinality(leftExtendedNodes) == 1 &&
LongBitmap.getCardinality(rightExtendedNodes) == 1;
}
- public void addRejectEdge(Edge edge) {
- rejectNodes = LongBitmap.newBitmapUnion(edge.getReferenceNodes(),
rejectNodes);
+ public void addLeftRejectEdge(JoinEdge edge) {
+ leftRejectEdges.add(edge);
+ }
+
+ public void addRightRejectEdge(JoinEdge edge) {
+ rightRejectEdges.add(edge);
+ }
+
+ public void addLeftRejectEdges(Set<JoinEdge> edge) {
+ leftRejectEdges.addAll(edge);
+ }
+
+ public void addRightRejectEdges(Set<JoinEdge> edge) {
+ rightRejectEdges.addAll(edge);
+ }
+
+ public Set<JoinEdge> getLeftRejectEdge() {
+ return ImmutableSet.copyOf(leftRejectEdges);
+ }
+
+ public Set<JoinEdge> getRightRejectEdge() {
+ return ImmutableSet.copyOf(rightRejectEdges);
}
public void addLeftExtendNode(long left) {
@@ -183,16 +207,6 @@ public abstract class Edge {
return ImmutableSet.copyOf(getExpressions());
}
- public boolean canPullUp() {
- // Only inner join and filter with none rejectNodes can be pull up
- return rejectNodes == 0
- && !(this instanceof JoinEdge && !((JoinEdge)
this).getJoinType().isInnerJoin());
- }
-
- public long getRejectNodes() {
- return rejectNodes;
- }
-
public Expression getExpression(int i) {
return getExpressions().get(i);
}
diff --git
a/fe/fe-core/src/main/java/org/apache/doris/nereids/jobs/joinorder/hypergraph/edge/JoinEdge.java
b/fe/fe-core/src/main/java/org/apache/doris/nereids/jobs/joinorder/hypergraph/edge/JoinEdge.java
index 81e80bee85f..635bf91f364 100644
---
a/fe/fe-core/src/main/java/org/apache/doris/nereids/jobs/joinorder/hypergraph/edge/JoinEdge.java
+++
b/fe/fe-core/src/main/java/org/apache/doris/nereids/jobs/joinorder/hypergraph/edge/JoinEdge.java
@@ -45,6 +45,18 @@ public class JoinEdge extends Edge {
this.join = join;
}
+ /**
+ * swap the edge
+ */
+ public JoinEdge swap() {
+ JoinEdge swapEdge = new
+ JoinEdge(join.swap(), getIndex(), getRightChildEdges(),
+ getLeftChildEdges(), getSubTreeNodes(),
getRightRequiredNodes(), getLeftRequiredNodes());
+ swapEdge.addLeftRejectEdges(getLeftRejectEdge());
+ swapEdge.addRightRejectEdges(getRightRejectEdge());
+ return swapEdge;
+ }
+
public JoinType getJoinType() {
return join.getJoinType();
}
diff --git
a/fe/fe-core/src/main/java/org/apache/doris/nereids/rules/exploration/mv/ComparisonResult.java
b/fe/fe-core/src/main/java/org/apache/doris/nereids/rules/exploration/mv/ComparisonResult.java
index cc8284f33e6..8836745465e 100644
---
a/fe/fe-core/src/main/java/org/apache/doris/nereids/rules/exploration/mv/ComparisonResult.java
+++
b/fe/fe-core/src/main/java/org/apache/doris/nereids/rules/exploration/mv/ComparisonResult.java
@@ -18,29 +18,36 @@
package org.apache.doris.nereids.rules.exploration.mv;
import org.apache.doris.nereids.trees.expressions.Expression;
+import org.apache.doris.nereids.trees.expressions.Slot;
import com.google.common.collect.ImmutableList;
+import com.google.common.collect.ImmutableSet;
import java.util.Collection;
import java.util.List;
+import java.util.Set;
/**
* comparison result of view and query
*/
public class ComparisonResult {
- public static final ComparisonResult INVALID = new
ComparisonResult(ImmutableList.of(), ImmutableList.of(), false);
- public static final ComparisonResult EMPTY = new
ComparisonResult(ImmutableList.of(), ImmutableList.of(), true);
+ public static final ComparisonResult INVALID =
+ new ComparisonResult(ImmutableList.of(), ImmutableList.of(),
ImmutableSet.of(), false);
private final boolean valid;
private final List<Expression> viewExpressions;
private final List<Expression> queryExpressions;
+ private final Set<Set<Slot>> viewNoNullableSlot;
- public ComparisonResult(List<Expression> queryExpressions,
List<Expression> viewExpressions) {
- this(queryExpressions, viewExpressions, true);
+ public ComparisonResult(List<Expression> queryExpressions,
List<Expression> viewExpressions,
+ Set<Set<Slot>> viewNoNullableSlot) {
+ this(queryExpressions, viewExpressions, viewNoNullableSlot, true);
}
- ComparisonResult(List<Expression> queryExpressions, List<Expression>
viewExpressions, boolean valid) {
+ ComparisonResult(List<Expression> queryExpressions, List<Expression>
viewExpressions,
+ Set<Set<Slot>> viewNoNullableSlot, boolean valid) {
this.viewExpressions = ImmutableList.copyOf(viewExpressions);
this.queryExpressions = ImmutableList.copyOf(queryExpressions);
+ this.viewNoNullableSlot = ImmutableSet.copyOf(viewNoNullableSlot);
this.valid = valid;
}
@@ -52,6 +59,10 @@ public class ComparisonResult {
return queryExpressions;
}
+ public Set<Set<Slot>> getViewNoNullableSlot() {
+ return viewNoNullableSlot;
+ }
+
public boolean isInvalid() {
return !valid;
}
@@ -62,6 +73,7 @@ public class ComparisonResult {
public static class Builder {
ImmutableList.Builder<Expression> queryBuilder = new
ImmutableList.Builder<>();
ImmutableList.Builder<Expression> viewBuilder = new
ImmutableList.Builder<>();
+ ImmutableSet.Builder<Set<Slot>> viewNoNullableSlotBuilder = new
ImmutableSet.Builder<>();
boolean valid = true;
/**
@@ -77,18 +89,31 @@ public class ComparisonResult {
return this;
}
- public Builder addQueryExpressions(Collection<Expression> expressions)
{
+ public Builder addQueryExpressions(Collection<? extends Expression>
expressions) {
queryBuilder.addAll(expressions);
return this;
}
- public Builder addViewExpressions(Collection<Expression> expressions) {
+ public Builder addViewExpressions(Collection<? extends Expression>
expressions) {
viewBuilder.addAll(expressions);
return this;
}
+ public Builder addViewNoNullableSlot(Set<Slot> viewNoNullableSlot) {
+
viewNoNullableSlotBuilder.add(ImmutableSet.copyOf(viewNoNullableSlot));
+ return this;
+ }
+
+ public boolean isInvalid() {
+ return !valid;
+ }
+
public ComparisonResult build() {
- return new ComparisonResult(queryBuilder.build(),
viewBuilder.build(), valid);
+ if (isInvalid()) {
+ return ComparisonResult.INVALID;
+ }
+ return new ComparisonResult(queryBuilder.build(),
viewBuilder.build(),
+ viewNoNullableSlotBuilder.build(), valid);
}
}
}
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
new file mode 100644
index 00000000000..a869fe729a9
--- /dev/null
+++
b/fe/fe-core/src/main/java/org/apache/doris/nereids/rules/exploration/mv/HyperGraphComparator.java
@@ -0,0 +1,299 @@
+// Licensed to the Apache Software Foundation (ASF) under one
+// or more contributor license agreements. See the NOTICE file
+// distributed with this work for additional information
+// regarding copyright ownership. The ASF licenses this file
+// to you under the Apache License, Version 2.0 (the
+// "License"); you may not use this file except in compliance
+// with the License. You may obtain a copy of the License at
+//
+// http://www.apache.org/licenses/LICENSE-2.0
+//
+// Unless required by applicable law or agreed to in writing,
+// software distributed under the License is distributed on an
+// "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY
+// KIND, either express or implied. See the License for the
+// specific language governing permissions and limitations
+// under the License.
+
+package org.apache.doris.nereids.rules.exploration.mv;
+
+import org.apache.doris.common.Pair;
+import org.apache.doris.nereids.jobs.joinorder.hypergraph.HyperGraph;
+import org.apache.doris.nereids.jobs.joinorder.hypergraph.bitmap.LongBitmap;
+import org.apache.doris.nereids.jobs.joinorder.hypergraph.edge.Edge;
+import org.apache.doris.nereids.jobs.joinorder.hypergraph.edge.FilterEdge;
+import org.apache.doris.nereids.jobs.joinorder.hypergraph.edge.JoinEdge;
+import org.apache.doris.nereids.rules.rewrite.PushDownFilterThroughJoin;
+import org.apache.doris.nereids.trees.expressions.Expression;
+import org.apache.doris.nereids.trees.expressions.Slot;
+import org.apache.doris.nereids.trees.plans.JoinType;
+
+import com.google.common.collect.ImmutableList;
+import com.google.common.collect.ImmutableMap;
+import com.google.common.collect.ImmutableSet;
+import com.google.common.collect.Sets;
+
+import java.util.ArrayList;
+import java.util.HashMap;
+import java.util.HashSet;
+import java.util.List;
+import java.util.Map;
+import java.util.Map.Entry;
+import java.util.Optional;
+import java.util.Set;
+
+/**
+ * HyperGraphComparator
+ */
+public class HyperGraphComparator {
+ // This second join can be inferred to the first join by map value,
+ // The map value means the child's should be no-nullable
+ static Map<Pair<JoinType, JoinType>, Pair<Boolean, Boolean>>
canInferredJoinTypeMap = ImmutableMap
+ .<Pair<JoinType, JoinType>, Pair<Boolean, Boolean>>builder()
+ .put(Pair.of(JoinType.LEFT_SEMI_JOIN, JoinType.INNER_JOIN),
Pair.of(false, false))
+ .put(Pair.of(JoinType.RIGHT_SEMI_JOIN, JoinType.INNER_JOIN),
Pair.of(false, false))
+ .put(Pair.of(JoinType.INNER_JOIN, JoinType.LEFT_OUTER_JOIN),
Pair.of(false, true))
+ .put(Pair.of(JoinType.INNER_JOIN, JoinType.RIGHT_OUTER_JOIN),
Pair.of(true, false))
+ .put(Pair.of(JoinType.INNER_JOIN, JoinType.FULL_OUTER_JOIN),
Pair.of(true, true))
+ .put(Pair.of(JoinType.LEFT_OUTER_JOIN, JoinType.FULL_OUTER_JOIN),
Pair.of(true, false))
+ .put(Pair.of(JoinType.RIGHT_OUTER_JOIN, JoinType.FULL_OUTER_JOIN),
Pair.of(false, true))
+ .build();
+
+ // record inferred edges when comparing mv
+ private final HyperGraph queryHyperGraph;
+ private final HyperGraph viewHyperGraph;
+ private final Map<JoinEdge, Pair<JoinType, Set<Slot>>> inferredViewEdgeMap
= new HashMap<>();
+ private final Map<Edge, List<? extends Expression>>
pullUpQueryExprWithEdge = new HashMap<>();
+ private final Map<Edge, List<? extends Expression>> pullUpViewExprWithEdge
= new HashMap<>();
+ private final LogicalCompatibilityContext logicalCompatibilityContext;
+
+ HyperGraphComparator(HyperGraph queryHyperGraph, HyperGraph viewHyperGraph,
+ LogicalCompatibilityContext logicalCompatibilityContext) {
+ this.queryHyperGraph = queryHyperGraph;
+ this.viewHyperGraph = viewHyperGraph;
+ this.logicalCompatibilityContext = logicalCompatibilityContext;
+ }
+
+ /**
+ * compare hypergraph
+ *
+ * @param viewHG the compared hyper graph
+ * @return Comparison result
+ */
+ public static ComparisonResult isLogicCompatible(HyperGraph queryHG,
HyperGraph viewHG,
+ LogicalCompatibilityContext ctx) {
+ return new HyperGraphComparator(queryHG, viewHG,
ctx).isLogicCompatible();
+ }
+
+ private ComparisonResult isLogicCompatible() {
+ // 1 try to construct a map which can be mapped from edge to edge
+ Map<Edge, Edge> queryToView = constructMapWithNode();
+
+ // 2. compare them by expression and extract residual expr
+ queryToView.forEach(this::compareEdgeWithExpr);
+
+ // 3. process residual edges
+ Sets.difference(getQueryJoinEdgeSet(), queryToView.keySet())
+ .forEach(e -> pullUpQueryExprWithEdge.put(e,
e.getExpressions()));
+ Sets.difference(getQueryFilterEdgeSet(), queryToView.keySet())
+ .forEach(e -> pullUpQueryExprWithEdge.put(e,
e.getExpressions()));
+ Sets.difference(getViewJoinEdgeSet(),
Sets.newHashSet(queryToView.values()))
+ .forEach(e -> pullUpViewExprWithEdge.put(e,
e.getExpressions()));
+ Sets.difference(getViewFilterEdgeSet(),
Sets.newHashSet(queryToView.values()))
+ .forEach(e -> pullUpViewExprWithEdge.put(e,
e.getExpressions()));
+
+ return buildComparisonRes();
+ }
+
+ private ComparisonResult buildComparisonRes() {
+ ComparisonResult.Builder builder = new ComparisonResult.Builder();
+ for (Entry<Edge, List<? extends Expression>> e :
pullUpQueryExprWithEdge.entrySet()) {
+ if (!e.getValue().isEmpty() && !canPullUp(e.getKey())) {
+ return ComparisonResult.INVALID;
+ }
+ builder.addQueryExpressions(e.getValue());
+ }
+ for (Entry<Edge, List<? extends Expression>> e :
pullUpViewExprWithEdge.entrySet()) {
+ if (!e.getValue().isEmpty() && !canPullUp(e.getKey())) {
+ return ComparisonResult.INVALID;
+ }
+ builder.addViewExpressions(e.getValue());
+ }
+ for (Pair<JoinType, Set<Slot>> inferredCond :
inferredViewEdgeMap.values()) {
+ builder.addViewNoNullableSlot(inferredCond.second);
+ }
+ return builder.build();
+ }
+
+ private boolean canPullUp(Edge edge) {
+ // Only inner join and filter with none rejectNodes can be pull up
+ if (edge instanceof JoinEdge && !((JoinEdge)
edge).getJoinType().isInnerJoin()) {
+ return false;
+ }
+ boolean pullFromLeft = edge.getLeftRejectEdge().stream()
+ .map(e -> inferredViewEdgeMap.getOrDefault(e,
Pair.of(e.getJoinType(), null)))
+ .allMatch(e -> canPullFromLeft(edge, e.first));
+ boolean pullFromRight = edge.getRightRejectEdge().stream()
+ .map(e -> inferredViewEdgeMap.getOrDefault(e,
Pair.of(e.getJoinType(), null)))
+ .allMatch(e -> canPullFromRight(edge, e.first));
+ return pullFromLeft && pullFromRight;
+ }
+
+ private boolean canPullFromLeft(Edge bottomEdge, JoinType topJoinType) {
+ if (bottomEdge instanceof FilterEdge) {
+ return
PushDownFilterThroughJoin.COULD_PUSH_THROUGH_LEFT.contains(topJoinType);
+ } else if (bottomEdge instanceof JoinEdge) {
+ return JoinType.isAssoc(((JoinEdge) bottomEdge).getJoinType(),
topJoinType)
+ || JoinType.isLAssoc(((JoinEdge)
bottomEdge).getJoinType(), topJoinType);
+ }
+ return false;
+ }
+
+ private boolean canPullFromRight(Edge bottomEdge, JoinType topJoinType) {
+ if (bottomEdge instanceof FilterEdge) {
+ return
PushDownFilterThroughJoin.COULD_PUSH_THROUGH_RIGHT.contains(topJoinType);
+ } else if (bottomEdge instanceof JoinEdge) {
+ return JoinType.isAssoc(topJoinType, ((JoinEdge)
bottomEdge).getJoinType())
+ || JoinType.isRAssoc(topJoinType, ((JoinEdge)
bottomEdge).getJoinType());
+ }
+ return false;
+ }
+
+ private List<JoinEdge> getQueryJoinEdges() {
+ return queryHyperGraph.getJoinEdges();
+ }
+
+ private Set<JoinEdge> getQueryJoinEdgeSet() {
+ return ImmutableSet.copyOf(queryHyperGraph.getJoinEdges());
+ }
+
+ private List<FilterEdge> getQueryFilterEdges() {
+ return queryHyperGraph.getFilterEdges();
+ }
+
+ private Set<FilterEdge> getQueryFilterEdgeSet() {
+ return ImmutableSet.copyOf(queryHyperGraph.getFilterEdges());
+ }
+
+ private Set<FilterEdge> getViewFilterEdgeSet() {
+ return ImmutableSet.copyOf(viewHyperGraph.getFilterEdges());
+ }
+
+ private Set<JoinEdge> getViewJoinEdgeSet() {
+ return ImmutableSet.copyOf(viewHyperGraph.getJoinEdges());
+ }
+
+ private List<JoinEdge> getViewJoinEdges() {
+ return viewHyperGraph.getJoinEdges();
+ }
+
+ private List<FilterEdge> getViewFilterEdges() {
+ return viewHyperGraph.getFilterEdges();
+ }
+
+ private Map<Expression, Expression> getQueryToViewExprMap() {
+ return
logicalCompatibilityContext.getQueryToViewEdgeExpressionMapping();
+ }
+
+ private Map<Integer, Integer> getQueryToViewNodeIdMap() {
+ return logicalCompatibilityContext.getQueryToViewNodeIDMapping();
+ }
+
+ private Map<Edge, Edge> constructMapWithNode() {
+ // TODO use hash map to reduce loop
+ Map<Edge, Edge> joinEdgeMap = getQueryJoinEdges().stream().map(qe -> {
+ Optional<JoinEdge> viewEdge = getViewJoinEdges().stream()
+ .filter(ve -> compareEdgeWithNode(qe, ve)).findFirst();
+ return Pair.of(qe, viewEdge);
+ }).filter(e ->
e.second.isPresent()).collect(ImmutableMap.toImmutableMap(p -> p.first, p ->
p.second.get()));
+ Map<Edge, Edge> filterEdgeMap = getQueryFilterEdges().stream().map(qe
-> {
+ Optional<FilterEdge> viewEdge = getViewFilterEdges().stream()
+ .filter(ve -> compareEdgeWithNode(qe, ve)).findFirst();
+ return Pair.of(qe, viewEdge);
+ }).filter(e ->
e.second.isPresent()).collect(ImmutableMap.toImmutableMap(p -> p.first, p ->
p.second.get()));
+ return ImmutableMap.<Edge,
Edge>builder().putAll(joinEdgeMap).putAll(filterEdgeMap).build();
+ }
+
+ private boolean compareEdgeWithNode(Edge query, Edge view) {
+ if (query instanceof FilterEdge && view instanceof FilterEdge) {
+ return compareEdgeWithFilter((FilterEdge) query, (FilterEdge)
view);
+ } else if (query instanceof JoinEdge && view instanceof JoinEdge) {
+ return compareJoinEdge((JoinEdge) query, (JoinEdge) view);
+ }
+ return false;
+ }
+
+ private boolean compareEdgeWithFilter(FilterEdge query, FilterEdge view) {
+ long qChild = query.getReferenceNodes();
+ long vChild = view.getReferenceNodes();
+ return rewriteQueryNodeMap(qChild) == vChild;
+ }
+
+ private boolean compareJoinEdge(JoinEdge query, JoinEdge view) {
+ if (query.getJoinType().equals(view.getJoinType())
+ ||
canInferredJoinTypeMap.containsKey(Pair.of(query.getJoinType(),
view.getJoinType()))) {
+ if (tryInferEdge(query, view)) {
+ return true;
+ }
+
+ }
+
+ if (query.getJoinType().swap().equals(view.getJoinType())
+ ||
canInferredJoinTypeMap.containsKey(Pair.of(query.getJoinType().swap(),
view.getJoinType()))) {
+ if (tryInferEdge(query.swap(), view)) {
+ return true;
+ }
+ }
+
+ return false;
+ }
+
+ private boolean tryInferEdge(JoinEdge query, JoinEdge view) {
+ if (rewriteQueryNodeMap(query.getLeftExtendedNodes()) !=
view.getLeftExtendedNodes()
+ || rewriteQueryNodeMap(query.getRightExtendedNodes()) !=
view.getRightExtendedNodes()) {
+ return false;
+ }
+ if (!query.getJoinType().equals(view.getJoinType())) {
+ Pair<Boolean, Boolean> noNullableChild =
canInferredJoinTypeMap.getOrDefault(
+ Pair.of(query.getJoinType(), view.getJoinType()), null);
+ if (noNullableChild == null) {
+ return false;
+ }
+ Set<Slot> noNullableSlot = Sets.union(
+ noNullableChild.first ?
view.getJoin().left().getOutputSet() : ImmutableSet.of(),
+ noNullableChild.second ?
view.getJoin().right().getOutputSet() : ImmutableSet.of()
+ );
+ inferredViewEdgeMap.put(view, Pair.of(query.getJoinType(),
noNullableSlot));
+ }
+ return true;
+ }
+
+ private long rewriteQueryNodeMap(long bitmap) {
+ long newBitmap = LongBitmap.newBitmap();
+ for (int i : LongBitmap.getIterator(bitmap)) {
+ int newIdx = getQueryToViewNodeIdMap().getOrDefault(i, 0);
+ newBitmap = LongBitmap.set(newBitmap, newIdx);
+ }
+ return newBitmap;
+ }
+
+ private void compareEdgeWithExpr(Edge query, Edge view) {
+ Set<? extends Expression> queryExprSet = query.getExpressionSet();
+ Set<? extends Expression> viewExprSet = view.getExpressionSet();
+
+ Set<Expression> exprMappedOfView = new HashSet<>();
+ List<Expression> residualQueryExpr = new ArrayList<>();
+ for (Expression queryExpr : queryExprSet) {
+ if (getQueryToViewExprMap().containsKey(queryExpr) &&
viewExprSet.contains(
+ getQueryToViewExprMap().get(queryExpr))) {
+ exprMappedOfView.add(getQueryToViewExprMap().get(queryExpr));
+ } else {
+ residualQueryExpr.add(queryExpr);
+ }
+ }
+ List<Expression> residualViewExpr =
ImmutableList.copyOf(Sets.difference(viewExprSet, exprMappedOfView));
+ pullUpQueryExprWithEdge.put(query, residualQueryExpr);
+ pullUpViewExprWithEdge.put(query, residualViewExpr);
+ }
+
+}
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 20da9ee12fd..2688882be97 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
@@ -265,7 +265,8 @@ public class StructInfo {
*/
public static ComparisonResult isGraphLogicalEquals(StructInfo
queryStructInfo, StructInfo viewStructInfo,
LogicalCompatibilityContext compatibilityContext) {
- return
queryStructInfo.hyperGraph.isLogicCompatible(viewStructInfo.hyperGraph,
compatibilityContext);
+ return HyperGraphComparator
+ .isLogicCompatible(queryStructInfo.hyperGraph,
viewStructInfo.hyperGraph, compatibilityContext);
}
private static class RelationCollector extends DefaultPlanVisitor<Void,
List<CatalogRelation>> {
diff --git
a/fe/fe-core/src/main/java/org/apache/doris/nereids/trees/plans/logical/LogicalJoin.java
b/fe/fe-core/src/main/java/org/apache/doris/nereids/trees/plans/logical/LogicalJoin.java
index 773dbce5fc2..c729aec752f 100644
---
a/fe/fe-core/src/main/java/org/apache/doris/nereids/trees/plans/logical/LogicalJoin.java
+++
b/fe/fe-core/src/main/java/org/apache/doris/nereids/trees/plans/logical/LogicalJoin.java
@@ -181,6 +181,11 @@ public class LogicalJoin<LEFT_CHILD_TYPE extends Plan,
RIGHT_CHILD_TYPE extends
this.markJoinSlotReference = markJoinSlotReference;
}
+ public LogicalJoin<? extends Plan, ? extends Plan> swap() {
+ return withTypeChildren(getJoinType().swap(),
+ right(), left());
+ }
+
public List<Expression> getOtherJoinConjuncts() {
return otherJoinConjuncts;
}
diff --git
a/fe/fe-core/src/test/java/org/apache/doris/nereids/jobs/joinorder/hypergraph/CompareOuterJoinTest.java
b/fe/fe-core/src/test/java/org/apache/doris/nereids/jobs/joinorder/hypergraph/CompareOuterJoinTest.java
index cfc88b2aa3c..105a5d450c3 100644
---
a/fe/fe-core/src/test/java/org/apache/doris/nereids/jobs/joinorder/hypergraph/CompareOuterJoinTest.java
+++
b/fe/fe-core/src/test/java/org/apache/doris/nereids/jobs/joinorder/hypergraph/CompareOuterJoinTest.java
@@ -20,6 +20,8 @@ package org.apache.doris.nereids.jobs.joinorder.hypergraph;
import org.apache.doris.nereids.CascadesContext;
import org.apache.doris.nereids.rules.RuleSet;
import
org.apache.doris.nereids.rules.exploration.mv.AbstractMaterializedViewRule;
+import org.apache.doris.nereids.rules.exploration.mv.ComparisonResult;
+import org.apache.doris.nereids.rules.exploration.mv.HyperGraphComparator;
import
org.apache.doris.nereids.rules.exploration.mv.LogicalCompatibilityContext;
import org.apache.doris.nereids.rules.exploration.mv.StructInfo;
import org.apache.doris.nereids.rules.exploration.mv.mapping.RelationMapping;
@@ -62,7 +64,8 @@ class CompareOuterJoinTest extends SqlTestBase {
.getAllPlan().get(0).child(0);
HyperGraph h1 = HyperGraph.toStructInfo(p1).get(0);
HyperGraph h2 = HyperGraph.toStructInfo(p2).get(0);
- Assertions.assertFalse(h1.isLogicCompatible(h2, constructContext(p1,
p2)).isInvalid());
+ Assertions.assertFalse(
+ HyperGraphComparator.isLogicCompatible(h1, h2,
constructContext(p1, p2)).isInvalid());
}
@Test
@@ -79,7 +82,8 @@ class CompareOuterJoinTest extends SqlTestBase {
.getAllPlan().get(0);
HyperGraph h1 = HyperGraph.toStructInfo(p1).get(0);
HyperGraph h2 = HyperGraph.toStructInfo(p2).get(0);
- Assertions.assertFalse(h1.isLogicCompatible(h2, constructContext(p1,
p2)).isInvalid());
+ Assertions.assertFalse(
+ HyperGraphComparator.isLogicCompatible(h1, h2,
constructContext(p1, p2)).isInvalid());
}
@Test
@@ -104,9 +108,9 @@ class CompareOuterJoinTest extends SqlTestBase {
.getAllPlan().get(0).child(0);
HyperGraph h1 = HyperGraph.toStructInfo(p1).get(0);
HyperGraph h2 = HyperGraph.toStructInfo(p2).get(0);
- List<Expression> exprList = h1.isLogicCompatible(h2,
constructContext(p1, p2)).getQueryExpressions();
- Assertions.assertEquals(1, exprList.size());
- Assertions.assertEquals("(id = 0)", exprList.get(0).toSql());
+ ComparisonResult res = HyperGraphComparator.isLogicCompatible(h1, h2,
constructContext(p1, p2));
+ Assertions.assertEquals(1, res.getQueryExpressions().size());
+ Assertions.assertEquals("(id = 0)",
res.getQueryExpressions().get(0).toSql());
}
@Disabled
@@ -132,7 +136,7 @@ class CompareOuterJoinTest extends SqlTestBase {
.getAllPlan().get(0).child(0);
HyperGraph h1 = HyperGraph.toStructInfo(p1).get(0);
HyperGraph h2 = HyperGraph.toStructInfo(p2).get(0);
- List<Expression> exprList = h1.isLogicCompatible(h2,
constructContext(p1, p2)).getQueryExpressions();
+ List<Expression> exprList = HyperGraphComparator.isLogicCompatible(h1,
h2, constructContext(p1, p2)).getQueryExpressions();
Assertions.assertEquals(0, exprList.size());
}
@@ -159,9 +163,9 @@ class CompareOuterJoinTest extends SqlTestBase {
.getAllPlan().get(0).child(0);
HyperGraph h1 = HyperGraph.toStructInfo(p1).get(0);
HyperGraph h2 = HyperGraph.toStructInfo(p2).get(0);
- List<Expression> exprList = h1.isLogicCompatible(h2,
constructContext(p1, p2)).getQueryExpressions();
- Assertions.assertEquals(1, exprList.size());
- Assertions.assertEquals("(id = 0)", exprList.get(0).toSql());
+ ComparisonResult res = HyperGraphComparator.isLogicCompatible(h1, h2,
constructContext(p1, p2));
+ Assertions.assertEquals(1, res.getQueryExpressions().size());
+ Assertions.assertEquals("(id = 0)",
res.getQueryExpressions().get(0).toSql());
}
@Test
@@ -187,7 +191,8 @@ class CompareOuterJoinTest extends SqlTestBase {
.getAllPlan().get(0).child(0);
HyperGraph h1 = HyperGraph.toStructInfo(p1).get(0);
HyperGraph h2 = HyperGraph.toStructInfo(p2).get(0);
- Assertions.assertTrue(h1.isLogicCompatible(h2, constructContext(p1,
p2)).isInvalid());
+ ComparisonResult res = HyperGraphComparator.isLogicCompatible(h1, h2,
constructContext(p1, p2));
+ Assertions.assertTrue(res.isInvalid());
}
LogicalCompatibilityContext constructContext(Plan p1, Plan p2) {
diff --git
a/fe/fe-core/src/test/java/org/apache/doris/nereids/jobs/joinorder/hypergraph/CompareOuterJoinTest.java
b/fe/fe-core/src/test/java/org/apache/doris/nereids/jobs/joinorder/hypergraph/InferJoinTest.java
similarity index 64%
copy from
fe/fe-core/src/test/java/org/apache/doris/nereids/jobs/joinorder/hypergraph/CompareOuterJoinTest.java
copy to
fe/fe-core/src/test/java/org/apache/doris/nereids/jobs/joinorder/hypergraph/InferJoinTest.java
index cfc88b2aa3c..33100c1180b 100644
---
a/fe/fe-core/src/test/java/org/apache/doris/nereids/jobs/joinorder/hypergraph/CompareOuterJoinTest.java
+++
b/fe/fe-core/src/test/java/org/apache/doris/nereids/jobs/joinorder/hypergraph/InferJoinTest.java
@@ -20,70 +20,26 @@ package org.apache.doris.nereids.jobs.joinorder.hypergraph;
import org.apache.doris.nereids.CascadesContext;
import org.apache.doris.nereids.rules.RuleSet;
import
org.apache.doris.nereids.rules.exploration.mv.AbstractMaterializedViewRule;
+import org.apache.doris.nereids.rules.exploration.mv.ComparisonResult;
+import org.apache.doris.nereids.rules.exploration.mv.HyperGraphComparator;
import
org.apache.doris.nereids.rules.exploration.mv.LogicalCompatibilityContext;
import org.apache.doris.nereids.rules.exploration.mv.StructInfo;
import org.apache.doris.nereids.rules.exploration.mv.mapping.RelationMapping;
import org.apache.doris.nereids.rules.exploration.mv.mapping.SlotMapping;
import org.apache.doris.nereids.sqltest.SqlTestBase;
-import org.apache.doris.nereids.trees.expressions.Expression;
+import org.apache.doris.nereids.trees.expressions.functions.ExpressionTrait;
import org.apache.doris.nereids.trees.plans.Plan;
-import org.apache.doris.nereids.util.HyperGraphBuilder;
import org.apache.doris.nereids.util.PlanChecker;
import org.junit.jupiter.api.Assertions;
import org.junit.jupiter.api.Disabled;
import org.junit.jupiter.api.Test;
-import java.util.List;
+import java.util.stream.Collectors;
-class CompareOuterJoinTest extends SqlTestBase {
+class InferJoinTest extends SqlTestBase {
@Test
- void testStarGraphWithInnerJoin() {
- // t2
- // |
- //t3-- t1 -- t4
- // |
- // t5
- CascadesContext c1 = createCascadesContext(
- "select * from T1, T2, T3, T4 where "
- + "T1.id = T2.id "
- + "and T1.id = T3.id "
- + "and T1.id = T4.id ",
- connectContext
- );
- Plan p1 = PlanChecker.from(c1)
- .analyze()
- .rewrite()
- .getPlan().child(0);
- Plan p2 = PlanChecker.from(c1)
- .analyze()
- .rewrite()
- .applyExploration(RuleSet.BUSHY_TREE_JOIN_REORDER)
- .getAllPlan().get(0).child(0);
- HyperGraph h1 = HyperGraph.toStructInfo(p1).get(0);
- HyperGraph h2 = HyperGraph.toStructInfo(p2).get(0);
- Assertions.assertFalse(h1.isLogicCompatible(h2, constructContext(p1,
p2)).isInvalid());
- }
-
- @Test
- void testRandomQuery() {
- Plan p1 = new HyperGraphBuilder().randomBuildPlanWith(3, 3);
- p1 = PlanChecker.from(connectContext, p1)
- .analyze()
- .rewrite()
- .getPlan();
- Plan p2 = PlanChecker.from(connectContext, p1)
- .analyze()
- .rewrite()
- .applyExploration(RuleSet.BUSHY_TREE_JOIN_REORDER)
- .getAllPlan().get(0);
- HyperGraph h1 = HyperGraph.toStructInfo(p1).get(0);
- HyperGraph h2 = HyperGraph.toStructInfo(p2).get(0);
- Assertions.assertFalse(h1.isLogicCompatible(h2, constructContext(p1,
p2)).isInvalid());
- }
-
- @Test
- void testInnerJoinWithFilter() {
+ void testInnerInferLeft() {
connectContext.getSessionVariable().setDisableNereidsRules("INFER_PREDICATES");
CascadesContext c1 = createCascadesContext(
"select * from T1 inner join T2 on T1.id = T2.id where T1.id =
0",
@@ -94,7 +50,7 @@ class CompareOuterJoinTest extends SqlTestBase {
.rewrite()
.getPlan().child(0);
CascadesContext c2 = createCascadesContext(
- "select * from T1 inner join T2 on T1.id = T2.id",
+ "select * from T1 left join T2 on T1.id = T2.id where T1.id =
0",
connectContext
);
Plan p2 = PlanChecker.from(c2)
@@ -104,14 +60,15 @@ class CompareOuterJoinTest extends SqlTestBase {
.getAllPlan().get(0).child(0);
HyperGraph h1 = HyperGraph.toStructInfo(p1).get(0);
HyperGraph h2 = HyperGraph.toStructInfo(p2).get(0);
- List<Expression> exprList = h1.isLogicCompatible(h2,
constructContext(p1, p2)).getQueryExpressions();
- Assertions.assertEquals(1, exprList.size());
- Assertions.assertEquals("(id = 0)", exprList.get(0).toSql());
+ ComparisonResult res = HyperGraphComparator.isLogicCompatible(h1, h2,
constructContext(p1, p2));
+ Assertions.assertFalse(res.isInvalid());
+ Assertions.assertEquals(1, res.getViewNoNullableSlot().size());
+ Assertions.assertEquals("[id, score]",
+
res.getViewNoNullableSlot().iterator().next().stream().map(ExpressionTrait::toSql).collect(Collectors.toList()).toString());
}
- @Disabled
@Test
- void testInnerJoinWithFilter2() {
+ void testInnerInferLeftWithFilter() {
connectContext.getSessionVariable().setDisableNereidsRules("INFER_PREDICATES");
CascadesContext c1 = createCascadesContext(
"select * from T1 inner join T2 on T1.id = T2.id where T1.id =
0",
@@ -122,7 +79,7 @@ class CompareOuterJoinTest extends SqlTestBase {
.rewrite()
.getPlan().child(0);
CascadesContext c2 = createCascadesContext(
- "select * from T1 inner join T2 on T1.id = T2.id where T1.id =
0",
+ "select * from T1 left join (select * from T2 where id = 0) T2
on T1.id = T2.id",
connectContext
);
Plan p2 = PlanChecker.from(c2)
@@ -132,24 +89,34 @@ class CompareOuterJoinTest extends SqlTestBase {
.getAllPlan().get(0).child(0);
HyperGraph h1 = HyperGraph.toStructInfo(p1).get(0);
HyperGraph h2 = HyperGraph.toStructInfo(p2).get(0);
- List<Expression> exprList = h1.isLogicCompatible(h2,
constructContext(p1, p2)).getQueryExpressions();
- Assertions.assertEquals(0, exprList.size());
+ ComparisonResult res = HyperGraphComparator.isLogicCompatible(h1, h2,
constructContext(p1, p2));
+ Assertions.assertFalse(res.isInvalid());
+ Assertions.assertEquals(1, res.getViewNoNullableSlot().size());
+ Assertions.assertEquals("[id, score]",
+
res.getViewNoNullableSlot().iterator().next().stream().map(ExpressionTrait::toSql).collect(Collectors.toList()).toString());
+ Assertions.assertEquals("(id = 0)",
res.getViewExpressions().get(0).toSql());
+ Assertions.assertEquals("(id = 0)",
res.getQueryExpressions().get(0).toSql());
}
+ // should consider rebuilding the hypergraph
+ @Disabled
@Test
- void testLeftOuterJoinWithLeftFilter() {
+ void testInnerInferLeftWithJoinCond() {
connectContext.getSessionVariable().setDisableNereidsRules("INFER_PREDICATES");
CascadesContext c1 = createCascadesContext(
- "select * from ( select * from T1 where T1.id = 0) T1 left
outer join T2 on T1.id = T2.id",
+ "select * from T1 inner join "
+ + "(select T2.id from T2 inner join T3 on T2.id =
T3.id) T2 "
+ + "on T1.id = T2.id",
connectContext
);
-
connectContext.getSessionVariable().setDisableNereidsRules("INFER_PREDICATES");
Plan p1 = PlanChecker.from(c1)
.analyze()
.rewrite()
.getPlan().child(0);
CascadesContext c2 = createCascadesContext(
- "select * from T1 left outer join T2 on T1.id = T2.id",
+ "select * from T1 left join "
+ + "(select T2.id from T2 inner join T3 on T2.id =
T3.id and T2.score = T3.score) T2 "
+ + "on T1.id = T2.id",
connectContext
);
Plan p2 = PlanChecker.from(c2)
@@ -159,9 +126,12 @@ class CompareOuterJoinTest extends SqlTestBase {
.getAllPlan().get(0).child(0);
HyperGraph h1 = HyperGraph.toStructInfo(p1).get(0);
HyperGraph h2 = HyperGraph.toStructInfo(p2).get(0);
- List<Expression> exprList = h1.isLogicCompatible(h2,
constructContext(p1, p2)).getQueryExpressions();
- Assertions.assertEquals(1, exprList.size());
- Assertions.assertEquals("(id = 0)", exprList.get(0).toSql());
+ ComparisonResult res = HyperGraphComparator.isLogicCompatible(h1, h2,
constructContext(p1, p2));
+ Assertions.assertFalse(res.isInvalid());
+ Assertions.assertEquals(1, res.getViewNoNullableSlot().size());
+ Assertions.assertEquals("[id, score]",
+
res.getViewNoNullableSlot().iterator().next().stream().map(ExpressionTrait::toSql).collect(Collectors.toList()).toString());
+ Assertions.assertEquals("score = score",
res.getQueryExpressions().get(0).toSql());
}
@Test
@@ -187,7 +157,8 @@ class CompareOuterJoinTest extends SqlTestBase {
.getAllPlan().get(0).child(0);
HyperGraph h1 = HyperGraph.toStructInfo(p1).get(0);
HyperGraph h2 = HyperGraph.toStructInfo(p2).get(0);
- Assertions.assertTrue(h1.isLogicCompatible(h2, constructContext(p1,
p2)).isInvalid());
+ ComparisonResult res = HyperGraphComparator.isLogicCompatible(h1, h2,
constructContext(p1, p2));
+ Assertions.assertTrue(res.isInvalid());
}
LogicalCompatibilityContext constructContext(Plan p1, Plan p2) {
diff --git
a/fe/fe-core/src/test/java/org/apache/doris/nereids/jobs/joinorder/hypergraph/PullupExpressionTest.java
b/fe/fe-core/src/test/java/org/apache/doris/nereids/jobs/joinorder/hypergraph/PullupExpressionTest.java
index d4818a844e8..4da4905f8aa 100644
---
a/fe/fe-core/src/test/java/org/apache/doris/nereids/jobs/joinorder/hypergraph/PullupExpressionTest.java
+++
b/fe/fe-core/src/test/java/org/apache/doris/nereids/jobs/joinorder/hypergraph/PullupExpressionTest.java
@@ -21,6 +21,7 @@ import org.apache.doris.nereids.CascadesContext;
import org.apache.doris.nereids.rules.RuleSet;
import
org.apache.doris.nereids.rules.exploration.mv.AbstractMaterializedViewRule;
import org.apache.doris.nereids.rules.exploration.mv.ComparisonResult;
+import org.apache.doris.nereids.rules.exploration.mv.HyperGraphComparator;
import
org.apache.doris.nereids.rules.exploration.mv.LogicalCompatibilityContext;
import org.apache.doris.nereids.rules.exploration.mv.StructInfo;
import org.apache.doris.nereids.rules.exploration.mv.mapping.RelationMapping;
@@ -54,7 +55,7 @@ class PullupExpressionTest extends SqlTestBase {
.getAllPlan().get(0).child(0);
HyperGraph h1 = HyperGraph.toStructInfo(p1).get(0);
HyperGraph h2 = HyperGraph.toStructInfo(p2).get(0);
- ComparisonResult res = h1.isLogicCompatible(h2, constructContext(p1,
p2));
+ ComparisonResult res = HyperGraphComparator.isLogicCompatible(h1, h2,
constructContext(p1, p2));
Assertions.assertEquals(2, res.getQueryExpressions().size());
Assertions.assertEquals("(id = 1)",
res.getQueryExpressions().get(0).toSql());
Assertions.assertEquals("(id = 1)",
res.getQueryExpressions().get(1).toSql());
@@ -81,7 +82,7 @@ class PullupExpressionTest extends SqlTestBase {
.getAllPlan().get(0).child(0);
HyperGraph h1 = HyperGraph.toStructInfo(p1).get(0);
HyperGraph h2 = HyperGraph.toStructInfo(p2).get(0);
- ComparisonResult res = h1.isLogicCompatible(h2, constructContext(p1,
p2));
+ ComparisonResult res = HyperGraphComparator.isLogicCompatible(h1, h2,
constructContext(p1, p2));
Assertions.assertEquals(1, res.getQueryExpressions().size());
Assertions.assertEquals("(score = score)",
res.getQueryExpressions().get(0).toSql());
}
@@ -107,7 +108,7 @@ class PullupExpressionTest extends SqlTestBase {
.getAllPlan().get(0).child(0);
HyperGraph h1 = HyperGraph.toStructInfo(p1).get(0);
HyperGraph h2 = HyperGraph.toStructInfo(p2).get(0);
- ComparisonResult res = h1.isLogicCompatible(h2, constructContext(p1,
p2));
+ ComparisonResult res = HyperGraphComparator.isLogicCompatible(h1, h2,
constructContext(p1, p2));
Assertions.assertEquals(2, res.getViewExpressions().size());
Assertions.assertEquals("(id = 1)",
res.getViewExpressions().get(0).toSql());
Assertions.assertEquals("(id = 1)",
res.getViewExpressions().get(1).toSql());
@@ -134,7 +135,7 @@ class PullupExpressionTest extends SqlTestBase {
.getAllPlan().get(0).child(0);
HyperGraph h1 = HyperGraph.toStructInfo(p1).get(0);
HyperGraph h2 = HyperGraph.toStructInfo(p2).get(0);
- ComparisonResult res = h1.isLogicCompatible(h2, constructContext(p1,
p2));
+ ComparisonResult res = HyperGraphComparator.isLogicCompatible(h1, h2,
constructContext(p1, p2));
Assertions.assertEquals(1, res.getViewExpressions().size());
Assertions.assertEquals("(score = score)",
res.getViewExpressions().get(0).toSql());
}
diff --git
a/fe/fe-core/src/test/java/org/apache/doris/nereids/rules/exploration/mv/BuildStructInfoTest.java
b/fe/fe-core/src/test/java/org/apache/doris/nereids/rules/exploration/mv/BuildStructInfoTest.java
index f68365f6708..bf5edfa45ec 100644
---
a/fe/fe-core/src/test/java/org/apache/doris/nereids/rules/exploration/mv/BuildStructInfoTest.java
+++
b/fe/fe-core/src/test/java/org/apache/doris/nereids/rules/exploration/mv/BuildStructInfoTest.java
@@ -79,7 +79,8 @@ class BuildStructInfoTest extends SqlTestBase {
.when(j -> {
HyperGraph structInfo =
HyperGraph.toStructInfo(j).get(0);
Assertions.assertTrue(structInfo.getJoinEdge(0).getJoinType().isLeftOuterJoin());
- Assertions.assertEquals(3L,
structInfo.getFilterEdge(0).getRejectNodes());
+ Assertions.assertEquals(0,
structInfo.getFilterEdge(0).getLeftRejectEdge().size());
+ Assertions.assertEquals(1,
structInfo.getFilterEdge(0).getRightRejectEdge().size());
return true;
}));
@@ -92,7 +93,6 @@ class BuildStructInfoTest extends SqlTestBase {
.when(j -> {
HyperGraph structInfo =
HyperGraph.toStructInfo(j).get(0);
Assertions.assertTrue(structInfo.getJoinEdge(0).getJoinType().isLeftOuterJoin());
- Assertions.assertEquals(0,
structInfo.getFilterEdge(0).getRejectNodes());
return true;
}));
}
---------------------------------------------------------------------
To unsubscribe, e-mail: commits-unsubscr...@doris.apache.org
For additional commands, e-mail: commits-h...@doris.apache.org
