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 fde474609e [feature](Nereids) Add dphyp job (#14485)
fde474609e is described below
commit fde474609efc4108af2af45f316cb5de5aefe4c9
Author: 谢健 <[email protected]>
AuthorDate: Thu Nov 24 15:50:05 2022 +0800
[feature](Nereids) Add dphyp job (#14485)
---
.../org/apache/doris/nereids/NereidsPlanner.java | 7 -
.../org/apache/doris/nereids/jobs/JobType.java | 4 +-
.../doris/nereids/jobs/joinorder/JoinOrderJob.java | 98 ++++++++++++
.../joinorder}/hypergraph/CircleDetector.java | 9 +-
.../joinorder}/hypergraph/Edge.java | 4 +-
.../joinorder}/hypergraph/GraphSimplifier.java | 164 +++++++++++++++++----
.../joinorder}/hypergraph/HyperGraph.java | 115 ++++-----------
.../joinorder}/hypergraph/Node.java | 42 +++---
.../joinorder}/hypergraph/SubgraphEnumerator.java | 56 ++++---
.../hypergraph/bitmap/BitSetIterator.java | 2 +-
.../joinorder}/hypergraph/bitmap/Bitmap.java | 2 +-
.../hypergraph/bitmap/ReverseBitSetIterator.java | 2 +-
.../hypergraph/bitmap/SubsetIterator.java | 2 +-
.../hypergraph/receiver/AbstractReceiver.java | 12 +-
.../joinorder}/hypergraph/receiver/Counter.java | 33 ++++-
.../hypergraph/receiver/PlanReceiver.java | 140 ++++++++++++++++++
.../java/org/apache/doris/nereids/memo/Group.java | 5 +
.../apache/doris/nereids/memo/GroupExpression.java | 5 +
.../rules/joinreorder/HyperGraphJoinReorder.java | 48 ------
.../HyperGraphJoinReorderGroupLeft.java | 48 ------
.../HyperGraphJoinReorderGroupRight.java | 47 ------
.../joinreorder/hypergraph/receiver/PlanTable.java | 57 -------
.../joinorder/JoinOrderJobTest.java} | 22 +--
.../joinorder}/hypergraph/BitSetTest.java | 6 +-
.../joinorder}/hypergraph/CircleDetectorTest.java | 2 +-
.../joinorder}/hypergraph/GraphSimplifierTest.java | 41 ++++--
.../joinorder}/hypergraph/HyperGraphTest.java | 2 +-
.../hypergraph/SubgraphEnumeratorTest.java | 8 +-
.../HyperGraphJoinReorderGroupRightTest.java | 52 -------
.../joinreorder/HyperGraphJoinReorderTest.java | 56 -------
.../doris/nereids/util/HyperGraphBuilder.java | 75 ++++------
.../org/apache/doris/nereids/util/PlanChecker.java | 37 +++--
32 files changed, 628 insertions(+), 575 deletions(-)
diff --git
a/fe/fe-core/src/main/java/org/apache/doris/nereids/NereidsPlanner.java
b/fe/fe-core/src/main/java/org/apache/doris/nereids/NereidsPlanner.java
index 34a088d799..acaf27ddb1 100644
--- a/fe/fe-core/src/main/java/org/apache/doris/nereids/NereidsPlanner.java
+++ b/fe/fe-core/src/main/java/org/apache/doris/nereids/NereidsPlanner.java
@@ -28,13 +28,11 @@ import
org.apache.doris.nereids.glue.translator.PlanTranslatorContext;
import org.apache.doris.nereids.jobs.batch.NereidsRewriteJobExecutor;
import org.apache.doris.nereids.jobs.batch.OptimizeRulesJob;
import org.apache.doris.nereids.jobs.cascades.DeriveStatsJob;
-import org.apache.doris.nereids.jobs.rewrite.RewriteTopDownJob;
import org.apache.doris.nereids.memo.Group;
import org.apache.doris.nereids.memo.GroupExpression;
import org.apache.doris.nereids.processor.post.PlanPostProcessors;
import org.apache.doris.nereids.processor.pre.PlanPreprocessors;
import org.apache.doris.nereids.properties.PhysicalProperties;
-import org.apache.doris.nereids.rules.joinreorder.HyperGraphJoinReorder;
import org.apache.doris.nereids.trees.expressions.NamedExpression;
import org.apache.doris.nereids.trees.plans.Plan;
import
org.apache.doris.nereids.trees.plans.commands.ExplainCommand.ExplainLevel;
@@ -213,11 +211,6 @@ public class NereidsPlanner extends Planner {
}
private void joinReorder() {
- new RewriteTopDownJob(
- getRoot(),
- (new HyperGraphJoinReorder()).buildRules(),
- cascadesContext.getCurrentJobContext()
- ).execute();
}
/**
diff --git
a/fe/fe-core/src/main/java/org/apache/doris/nereids/jobs/JobType.java
b/fe/fe-core/src/main/java/org/apache/doris/nereids/jobs/JobType.java
index 528109babb..03681c58ee 100644
--- a/fe/fe-core/src/main/java/org/apache/doris/nereids/jobs/JobType.java
+++ b/fe/fe-core/src/main/java/org/apache/doris/nereids/jobs/JobType.java
@@ -30,6 +30,6 @@ public enum JobType {
DERIVE_STATS,
TOP_DOWN_REWRITE,
VISITOR_REWRITE,
- BOTTOM_UP_REWRITE
- ;
+ BOTTOM_UP_REWRITE,
+ JOIN_ORDER;
}
diff --git
a/fe/fe-core/src/main/java/org/apache/doris/nereids/jobs/joinorder/JoinOrderJob.java
b/fe/fe-core/src/main/java/org/apache/doris/nereids/jobs/joinorder/JoinOrderJob.java
new file mode 100644
index 0000000000..4b5e20ad0d
--- /dev/null
+++
b/fe/fe-core/src/main/java/org/apache/doris/nereids/jobs/joinorder/JoinOrderJob.java
@@ -0,0 +1,98 @@
+// 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.jobs.joinorder;
+
+import org.apache.doris.nereids.exceptions.AnalysisException;
+import org.apache.doris.nereids.jobs.Job;
+import org.apache.doris.nereids.jobs.JobContext;
+import org.apache.doris.nereids.jobs.JobType;
+import org.apache.doris.nereids.jobs.joinorder.hypergraph.GraphSimplifier;
+import org.apache.doris.nereids.jobs.joinorder.hypergraph.HyperGraph;
+import org.apache.doris.nereids.jobs.joinorder.hypergraph.SubgraphEnumerator;
+import
org.apache.doris.nereids.jobs.joinorder.hypergraph.receiver.PlanReceiver;
+import org.apache.doris.nereids.memo.Group;
+import org.apache.doris.nereids.memo.GroupExpression;
+
+import com.google.common.base.Preconditions;
+
+/**
+ * Join Order job with DPHyp
+ */
+public class JoinOrderJob extends Job {
+ private final Group group;
+
+ public JoinOrderJob(Group group, JobContext context) {
+ super(JobType.JOIN_ORDER, context);
+ this.group = group;
+ }
+
+ @Override
+ public void execute() throws AnalysisException {
+ Preconditions.checkArgument(!group.isJoinGroup());
+ GroupExpression rootExpr = group.getLogicalExpression();
+ int arity = rootExpr.arity();
+ for (int i = 0; i < arity; i++) {
+ rootExpr.setChild(i, optimizePlan(rootExpr.child(i)));
+ }
+ }
+
+ private Group optimizePlan(Group group) {
+ if (group.isJoinGroup()) {
+ return optimizeJoin(group);
+ }
+ GroupExpression rootExpr = group.getLogicalExpression();
+ int arity = rootExpr.arity();
+ for (int i = 0; i < arity; i++) {
+ rootExpr.setChild(i, optimizePlan(rootExpr.child(i)));
+ }
+ return group;
+ }
+
+ private Group optimizeJoin(Group group) {
+ HyperGraph hyperGraph = new HyperGraph();
+ buildGraph(group, hyperGraph);
+ // Right now, we just hardcode the limit with 10000, maybe we need a
better way to set it
+ int limit = 10000;
+ PlanReceiver planReceiver = new PlanReceiver(limit);
+ SubgraphEnumerator subgraphEnumerator = new
SubgraphEnumerator(planReceiver, hyperGraph);
+ if (!subgraphEnumerator.enumerate()) {
+ GraphSimplifier graphSimplifier = new GraphSimplifier(hyperGraph);
+ graphSimplifier.simplifyGraph(limit);
+ if (!subgraphEnumerator.enumerate()) {
+ throw new RuntimeException("DPHyp can not enumerate all sub
graphs with limit=" + limit);
+ }
+ }
+ return planReceiver.getBestPlan(hyperGraph.getNodesMap());
+ }
+
+ /**
+ * build a hyperGraph for the root group
+ *
+ * @param group root group, should be join type
+ * @param hyperGraph build hyperGraph
+ */
+ public void buildGraph(Group group, HyperGraph hyperGraph) {
+ if (!group.isJoinGroup()) {
+ hyperGraph.addNode(optimizePlan(group));
+ return;
+ }
+ buildGraph(group.getLogicalExpression().child(0), hyperGraph);
+ buildGraph(group.getLogicalExpression().child(1), hyperGraph);
+ hyperGraph.addEdge(group);
+ }
+}
diff --git
a/fe/fe-core/src/main/java/org/apache/doris/nereids/rules/joinreorder/hypergraph/CircleDetector.java
b/fe/fe-core/src/main/java/org/apache/doris/nereids/jobs/joinorder/hypergraph/CircleDetector.java
similarity index 94%
rename from
fe/fe-core/src/main/java/org/apache/doris/nereids/rules/joinreorder/hypergraph/CircleDetector.java
rename to
fe/fe-core/src/main/java/org/apache/doris/nereids/jobs/joinorder/hypergraph/CircleDetector.java
index 7cdcb16073..7f97904cf6 100644
---
a/fe/fe-core/src/main/java/org/apache/doris/nereids/rules/joinreorder/hypergraph/CircleDetector.java
+++
b/fe/fe-core/src/main/java/org/apache/doris/nereids/jobs/joinorder/hypergraph/CircleDetector.java
@@ -15,9 +15,9 @@
// specific language governing permissions and limitations
// under the License.
-package org.apache.doris.nereids.rules.joinreorder.hypergraph;
+package org.apache.doris.nereids.jobs.joinorder.hypergraph;
-import org.apache.doris.nereids.rules.joinreorder.hypergraph.bitmap.Bitmap;
+import org.apache.doris.nereids.jobs.joinorder.hypergraph.bitmap.Bitmap;
import com.google.common.base.Preconditions;
@@ -39,8 +39,8 @@ public class CircleDetector {
List<Integer> nodes = new ArrayList<>();
// stored the dependency of each node
List<BitSet> directedEdges = new ArrayList<>();
+ // the nodes are after than this node
List<BitSet> subNodes = new ArrayList<>();
- // whether the node has been visited in dfs
CircleDetector(int size) {
for (int i = 0; i < size; i++) {
@@ -67,9 +67,10 @@ public class CircleDetector {
int order1 = orders.get(node1);
int order2 = orders.get(node2);
if (order1 >= order2) {
- shift(order2, order1 + 1, subNodes.get(order2));
+ shift(order2, order1 + 1, subNodes.get(node2));
}
for (BitSet nodes : subNodes) {
+ // add all subNodes which contains node1 into subNodes of node2.
if (Bitmap.get(nodes, node1)) {
Bitmap.or(nodes, subNodes.get(node2));
}
diff --git
a/fe/fe-core/src/main/java/org/apache/doris/nereids/rules/joinreorder/hypergraph/Edge.java
b/fe/fe-core/src/main/java/org/apache/doris/nereids/jobs/joinorder/hypergraph/Edge.java
similarity index 96%
rename from
fe/fe-core/src/main/java/org/apache/doris/nereids/rules/joinreorder/hypergraph/Edge.java
rename to
fe/fe-core/src/main/java/org/apache/doris/nereids/jobs/joinorder/hypergraph/Edge.java
index 835f599751..576e7910c6 100644
---
a/fe/fe-core/src/main/java/org/apache/doris/nereids/rules/joinreorder/hypergraph/Edge.java
+++
b/fe/fe-core/src/main/java/org/apache/doris/nereids/jobs/joinorder/hypergraph/Edge.java
@@ -15,9 +15,9 @@
// specific language governing permissions and limitations
// under the License.
-package org.apache.doris.nereids.rules.joinreorder.hypergraph;
+package org.apache.doris.nereids.jobs.joinorder.hypergraph;
-import org.apache.doris.nereids.rules.joinreorder.hypergraph.bitmap.Bitmap;
+import org.apache.doris.nereids.jobs.joinorder.hypergraph.bitmap.Bitmap;
import org.apache.doris.nereids.trees.plans.GroupPlan;
import org.apache.doris.nereids.trees.plans.Plan;
import org.apache.doris.nereids.trees.plans.logical.LogicalJoin;
diff --git
a/fe/fe-core/src/main/java/org/apache/doris/nereids/rules/joinreorder/hypergraph/GraphSimplifier.java
b/fe/fe-core/src/main/java/org/apache/doris/nereids/jobs/joinorder/hypergraph/GraphSimplifier.java
similarity index 76%
rename from
fe/fe-core/src/main/java/org/apache/doris/nereids/rules/joinreorder/hypergraph/GraphSimplifier.java
rename to
fe/fe-core/src/main/java/org/apache/doris/nereids/jobs/joinorder/hypergraph/GraphSimplifier.java
index b341289ae0..88c35d479c 100644
---
a/fe/fe-core/src/main/java/org/apache/doris/nereids/rules/joinreorder/hypergraph/GraphSimplifier.java
+++
b/fe/fe-core/src/main/java/org/apache/doris/nereids/jobs/joinorder/hypergraph/GraphSimplifier.java
@@ -15,12 +15,13 @@
// specific language governing permissions and limitations
// under the License.
-package org.apache.doris.nereids.rules.joinreorder.hypergraph;
+package org.apache.doris.nereids.jobs.joinorder.hypergraph;
+import org.apache.doris.nereids.jobs.joinorder.hypergraph.bitmap.Bitmap;
+import org.apache.doris.nereids.jobs.joinorder.hypergraph.receiver.Counter;
import org.apache.doris.nereids.memo.Group;
import org.apache.doris.nereids.memo.GroupExpression;
import org.apache.doris.nereids.properties.PhysicalProperties;
-import org.apache.doris.nereids.rules.joinreorder.hypergraph.bitmap.Bitmap;
import org.apache.doris.nereids.stats.StatsCalculator;
import org.apache.doris.nereids.trees.plans.GroupPlan;
import org.apache.doris.nereids.trees.plans.Plan;
@@ -34,6 +35,8 @@ import java.util.HashMap;
import java.util.List;
import java.util.Optional;
import java.util.PriorityQueue;
+import java.util.Stack;
+import javax.annotation.Nullable;
/**
* GraphSimplifier is used to simplify HyperGraph {@link HyperGraph}
@@ -41,6 +44,8 @@ import java.util.PriorityQueue;
public class GraphSimplifier {
// Note that each index in the graph simplifier is the half of the actual
index
private final int edgeSize;
+ // Detect the circle when order join
+ private CircleDetector circleDetector;
// This is used for cache the intermediate results when calculate the
benefit
// Note that we store it for the after. Because if we put B after A (t1
Join_A t2 Join_B t3),
// B is changed. Therefore, Any step that involves B need to be
recalculated.
@@ -48,14 +53,20 @@ public class GraphSimplifier {
private PriorityQueue<BestSimplification> priorityQueue = new
PriorityQueue<>();
// The graph we are simplifying
private HyperGraph graph;
- // Detect the circle when order join
- private CircleDetector circleDetector;
// It cached the plan in simplification. we don't store it in hyper graph,
// because it's just used for simulating join. In fact, the graph
simplifier
// just generate the partial order of join operator.
private HashMap<BitSet, Plan> cachePlan = new HashMap<>();
- GraphSimplifier(HyperGraph graph) {
+ private Stack<SimplificationStep> appliedSteps = new
Stack<SimplificationStep>();
+ private Stack<SimplificationStep> unAppliedSteps = new
Stack<SimplificationStep>();
+
+ /**
+ * Create a graph simplifier
+ *
+ * @param graph create a graph simplifier to simplify the graph
+ */
+ public GraphSimplifier(HyperGraph graph) {
this.graph = graph;
edgeSize = graph.getEdges().size();
for (int i = 0; i < edgeSize; i++) {
@@ -78,6 +89,30 @@ public class GraphSimplifier {
}
}
+ /**
+ * Check whether all edge has been ordered
+ *
+ * @return if true, all edges has a total order
+ */
+ public boolean isTotalOrder() {
+ for (int i = 0; i < edgeSize; i++) {
+ for (int j = i + 1; j < edgeSize; j++) {
+ Edge edge1 = graph.getEdge(i);
+ Edge edge2 = graph.getEdge(j);
+ List<BitSet> superset = new ArrayList<>();
+ tryGetSuperset(edge1.getLeft(), edge2.getLeft(), superset);
+ tryGetSuperset(edge1.getLeft(), edge2.getRight(), superset);
+ tryGetSuperset(edge1.getRight(), edge2.getLeft(), superset);
+ tryGetSuperset(edge1.getRight(), edge2.getRight(), superset);
+ if (!circleDetector.checkCircleWithEdge(i, j) &&
!circleDetector.checkCircleWithEdge(j, i)
+ && !edge2.isSub(edge1) && !edge1.isSub(edge2) &&
!superset.isEmpty()) {
+ return false;
+ }
+ }
+ }
+ return true;
+ }
+
/**
* This function will repeatedly apply simplification steps util the
number of csg-cmp pair
* is under the limit.
@@ -87,10 +122,45 @@ public class GraphSimplifier {
* @param limit the limit number of the csg-cmp pair
*/
public boolean simplifyGraph(int limit) {
- // Now we only support simplify graph until the hyperGraph only
contains one plan
- Preconditions.checkArgument(limit == 1);
- while (applySimplificationStep()) {
+ Preconditions.checkArgument(limit >= 1);
+ initFirstStep();
+ int lowerBound = 0;
+ int upperBound = 1;
+
+ // Try to probe the largest number of steps to satisfy the limit
+ int numApplySteps = 0;
+ Counter counter = new Counter(limit);
+ SubgraphEnumerator enumerator = new SubgraphEnumerator(counter, graph);
+ while (true) {
+ while (numApplySteps < upperBound) {
+ if (!applySimplificationStep()) {
+ // If we have done all steps but still has more sub graphs
+ // Just return
+ if (!enumerator.enumerate()) {
+ return false;
+ }
+ break;
+ }
+ numApplySteps += 1;
+ }
+ if (numApplySteps < upperBound || enumerator.enumerate()) {
+ break;
+ }
+ upperBound *= 2;
}
+
+ // Try to search the lowest number of steps to satisfy the limit
+ upperBound = numApplySteps + 1;
+ while (lowerBound < upperBound) {
+ int mid = lowerBound + (upperBound - lowerBound) / 2;
+ applyStepsWithNum(mid);
+ if (enumerator.enumerate()) {
+ upperBound = mid;
+ } else {
+ lowerBound = mid + 1;
+ }
+ }
+ applyStepsWithNum(upperBound);
return true;
}
@@ -100,26 +170,62 @@ public class GraphSimplifier {
* @return If there is no other steps, return false.
*/
public boolean applySimplificationStep() {
- if (priorityQueue.isEmpty()) {
+ boolean needProcessNeighbor = unAppliedSteps.isEmpty();
+ SimplificationStep bestStep = fetchSimplificationStep();
+ if (bestStep == null) {
return false;
}
+ appliedSteps.push(bestStep);
+ Preconditions.checkArgument(
+ cachePlan.containsKey(bestStep.newLeft) &&
cachePlan.containsKey(bestStep.newRight),
+ String.format("%s - %s", bestStep.newLeft, bestStep.newRight));
+ graph.modifyEdge(bestStep.afterIndex, bestStep.newLeft,
bestStep.newRight);
+ if (needProcessNeighbor) {
+ processNeighbors(bestStep.afterIndex, 0, edgeSize);
+ }
+ return true;
+ }
+
+ private boolean unApplySimplificationStep() {
+ Preconditions.checkArgument(appliedSteps.size() > 0);
+ SimplificationStep bestStep = appliedSteps.pop();
+ unAppliedSteps.push(bestStep);
+ graph.modifyEdge(bestStep.afterIndex, bestStep.oldLeft,
bestStep.oldRight);
+ // Note we don't need to delete this edge in circleDetector, because
we don't need to
+ // recalculate neighbors until all steps applied
+ return true;
+ }
+
+ private @Nullable SimplificationStep fetchSimplificationStep() {
+ if (!unAppliedSteps.isEmpty()) {
+ return unAppliedSteps.pop();
+ }
+ if (priorityQueue.isEmpty()) {
+ return null;
+ }
BestSimplification bestSimplification = priorityQueue.poll();
bestSimplification.isInQueue = false;
SimplificationStep bestStep = bestSimplification.getStep();
- while (!circleDetector.tryAddDirectedEdge(bestStep.beforeIndex,
bestStep.afterIndex)) {
+ while (bestSimplification.bestNeighbor == -1 ||
!circleDetector.tryAddDirectedEdge(bestStep.beforeIndex,
+ bestStep.afterIndex)) {
if (priorityQueue.isEmpty()) {
- return false;
+ return null;
}
bestSimplification = priorityQueue.poll();
bestSimplification.isInQueue = false;
+ processNeighbors(bestStep.afterIndex, 0, edgeSize);
bestStep = bestSimplification.getStep();
}
- Preconditions.checkArgument(
- cachePlan.containsKey(bestStep.newLeft) &&
cachePlan.containsKey(bestStep.newRight),
- String.format("%s - %s", bestStep.newLeft, bestStep.newRight));
- graph.modifyEdge(bestStep.afterIndex, bestStep.newLeft,
bestStep.newRight);
- processNeighbors(bestStep.afterIndex, 0, edgeSize);
- return true;
+ return bestStep;
+ }
+
+ private void applyStepsWithNum(int num) {
+ while (appliedSteps.size() < num) {
+ applySimplificationStep();
+ }
+ while (appliedSteps.size() > num) {
+ unApplySimplificationStep();
+ }
}
/**
@@ -148,11 +254,11 @@ public class GraphSimplifier {
}
// Go through the neighbors with higher index, we only need to
recalculate all related steps
+ BestSimplification bestSimplification =
simplifications.get(edgeIndex1);
+ bestSimplification.bestNeighbor = -1;
for (int edgeIndex2 = Integer.max(beginIndex, edgeIndex1 + 1);
edgeIndex2 < endIndex; edgeIndex2 += 1) {
- BestSimplification bestSimplification =
simplifications.get(edgeIndex1);
Optional<SimplificationStep> optionalStep =
makeSimplificationStep(edgeIndex1, edgeIndex2);
if (optionalStep.isPresent()) {
- bestSimplification.bestNeighbor = -1;
trySetSimplificationStep(optionalStep.get(),
bestSimplification, edgeIndex1, edgeIndex2);
}
}
@@ -160,7 +266,8 @@ public class GraphSimplifier {
private boolean trySetSimplificationStep(SimplificationStep step,
BestSimplification bestSimplification,
int index, int neighborIndex) {
- if (bestSimplification.bestNeighbor == -1 ||
bestSimplification.getBenefit() <= step.getBenefit()) {
+ if (bestSimplification.bestNeighbor == -1 ||
bestSimplification.isInQueue == false
+ || bestSimplification.getBenefit() <= step.getBenefit()) {
bestSimplification.bestNeighbor = neighborIndex;
bestSimplification.setStep(step);
updatePriorityQueue(index);
@@ -284,14 +391,14 @@ public class GraphSimplifier {
}
// choose edge1Before2
step = new SimplificationStep(benefit, edgeIndex1, edgeIndex2,
edge1Before2.getLeft(),
- edge1Before2.getRight());
+ edge1Before2.getRight(),
graph.getEdge(edgeIndex2).getLeft(), graph.getEdge(edgeIndex2).getRight());
} else {
if (cost2Before1 != 0) {
benefit = cost1Before2 / cost2Before1;
}
// choose edge2Before1
step = new SimplificationStep(benefit, edgeIndex2, edgeIndex1,
edge2Before1.getLeft(),
- edge2Before1.getRight());
+ edge2Before1.getRight(),
graph.getEdge(edgeIndex1).getLeft(), graph.getEdge(edgeIndex1).getRight());
}
return step;
}
@@ -308,8 +415,8 @@ public class GraphSimplifier {
}
private double getSimpleCost(Plan plan) {
- if (plan instanceof GroupPlan) {
- return ((GroupPlan) plan).getGroup().getStatistics().getRowCount();
+ if (!(plan instanceof LogicalJoin)) {
+ return
plan.getGroupExpression().get().getOwnerGroup().getStatistics().getRowCount();
}
return
plan.getGroupExpression().get().getCostByProperties(PhysicalProperties.ANY);
}
@@ -360,11 +467,16 @@ public class GraphSimplifier {
int afterIndex;
BitSet newLeft;
BitSet newRight;
+ BitSet oldLeft;
+ BitSet oldRight;
- SimplificationStep(double benefit, int beforeIndex, int afterIndex,
BitSet newLeft, BitSet newRight) {
+ SimplificationStep(double benefit, int beforeIndex, int afterIndex,
BitSet newLeft, BitSet newRight,
+ BitSet oldLeft, BitSet oldRight) {
this.afterIndex = afterIndex;
this.beforeIndex = beforeIndex;
this.benefit = benefit;
+ this.oldLeft = oldLeft;
+ this.oldRight = oldRight;
this.newLeft = newLeft;
this.newRight = newRight;
}
@@ -381,7 +493,7 @@ public class GraphSimplifier {
@Override
public String toString() {
- return String.format("%d -> %d %.2f : %s-%s", beforeIndex,
afterIndex, benefit, newLeft, newRight);
+ return String.format("%d -> %d", beforeIndex, afterIndex);
}
}
diff --git
a/fe/fe-core/src/main/java/org/apache/doris/nereids/rules/joinreorder/hypergraph/HyperGraph.java
b/fe/fe-core/src/main/java/org/apache/doris/nereids/jobs/joinorder/hypergraph/HyperGraph.java
similarity index 76%
rename from
fe/fe-core/src/main/java/org/apache/doris/nereids/rules/joinreorder/hypergraph/HyperGraph.java
rename to
fe/fe-core/src/main/java/org/apache/doris/nereids/jobs/joinorder/hypergraph/HyperGraph.java
index 15f00a3bf6..3155bfec9a 100644
---
a/fe/fe-core/src/main/java/org/apache/doris/nereids/rules/joinreorder/hypergraph/HyperGraph.java
+++
b/fe/fe-core/src/main/java/org/apache/doris/nereids/jobs/joinorder/hypergraph/HyperGraph.java
@@ -15,16 +15,15 @@
// specific language governing permissions and limitations
// under the License.
-package org.apache.doris.nereids.rules.joinreorder.hypergraph;
+package org.apache.doris.nereids.jobs.joinorder.hypergraph;
-import org.apache.doris.nereids.rules.joinreorder.hypergraph.bitmap.Bitmap;
+import org.apache.doris.nereids.jobs.joinorder.hypergraph.bitmap.Bitmap;
+import org.apache.doris.nereids.memo.Group;
import org.apache.doris.nereids.trees.expressions.Expression;
import org.apache.doris.nereids.trees.expressions.Slot;
-import org.apache.doris.nereids.trees.plans.GroupPlan;
import org.apache.doris.nereids.trees.plans.JoinType;
import org.apache.doris.nereids.trees.plans.Plan;
import org.apache.doris.nereids.trees.plans.logical.LogicalJoin;
-import org.apache.doris.nereids.trees.plans.logical.LogicalProject;
import com.google.common.base.Preconditions;
import com.google.common.collect.ImmutableList;
@@ -41,13 +40,6 @@ import java.util.Set;
public class HyperGraph {
private List<Edge> edges = new ArrayList<>();
private List<Node> nodes = new ArrayList<>();
- private Plan bestPlan;
-
- public static HyperGraph fromPlan(Plan plan) {
- HyperGraph graph = new HyperGraph();
- graph.buildGraph(plan);
- return graph;
- }
public List<Edge> getEdges() {
return edges;
@@ -57,6 +49,10 @@ public class HyperGraph {
return nodes;
}
+ public BitSet getNodesMap() {
+ return Bitmap.newBitmapBetween(0, nodes.size());
+ }
+
public Edge getEdge(int index) {
return edges.get(index);
}
@@ -65,86 +61,26 @@ public class HyperGraph {
return nodes.get(index);
}
- /**
- * Extract the best plan of HyperGraph
- *
- * @return return the best plan
- */
- public Plan toPlan() {
- return bestPlan;
- }
-
- public boolean simplify() {
- GraphSimplifier graphSimplifier = new GraphSimplifier(this);
- graphSimplifier.initFirstStep();
- return graphSimplifier.simplifyGraph(1);
- }
-
- /**
- * Try to enumerate all csg-cmp pairs and get the best plan
- *
- * @return whether enumerate successfully
- */
- public boolean emitPlan() {
- return false;
- }
-
- public boolean optimize() {
- return simplify() && emitPlan();
- }
-
public void splitEdgesForNodes() {
for (Node node : nodes) {
node.splitEdges();
}
}
- private void buildGraph(Plan plan) {
- if ((plan instanceof LogicalProject && plan.child(0) instanceof
GroupPlan)
- || plan instanceof GroupPlan) {
- nodes.add(new Node(nodes.size(), plan));
- return;
- }
-
- LogicalJoin<? extends Plan, ? extends Plan> join;
- if (plan instanceof LogicalProject) {
- LogicalProject<? extends Plan> project = (LogicalProject<? extends
Plan>) plan;
- join = (LogicalJoin<? extends Plan, ? extends Plan>)
project.child();
-
- // Handle project
- // Ignore the projection expression just using for selection
column.
- // TODO: how to handle Alias and complex project expression
- } else {
- join = (LogicalJoin<? extends Plan, ? extends Plan>) plan;
- }
-
- // Now we only support inner join with Inside-Project
- // TODO: Other joins can be added according CD-C algorithm
- if (join.getJoinType() != JoinType.INNER_JOIN) {
- Node node = new Node(nodes.size(), plan);
- nodes.add(node);
- return;
- }
-
- buildGraph(join.left());
- buildGraph(join.right());
- addEdge(join);
- }
-
- private BitSet findNodes(Set<Slot> slots) {
- BitSet bitSet = Bitmap.newBitmap();
- for (Node node : nodes) {
- for (Slot slot : node.getPlan().getOutput()) {
- if (slots.contains(slot)) {
- Bitmap.set(bitSet, node.getIndex());
- break;
- }
- }
- }
- return bitSet;
+ public void addNode(Group group) {
+ Preconditions.checkArgument(!group.isJoinGroup());
+ // TODO: replace plan with group expression or others
+ nodes.add(new Node(nodes.size(), group));
}
- private void addEdge(LogicalJoin<? extends Plan, ? extends Plan> join) {
+ /**
+ * try to add edge for join group
+ *
+ * @param group The join group
+ */
+ public void addEdge(Group group) {
+ Preconditions.checkArgument(group.isJoinGroup());
+ LogicalJoin<? extends Plan, ? extends Plan> join = (LogicalJoin)
group.getLogicalExpression().getPlan();
for (Expression expression : join.getExpressions()) {
LogicalJoin singleJoin = new LogicalJoin(join.getJoinType(),
ImmutableList.of(expression), join.left(),
join.right());
@@ -165,6 +101,19 @@ public class HyperGraph {
// We don't implement this trick now.
}
+ private BitSet findNodes(Set<Slot> slots) {
+ BitSet bitSet = Bitmap.newBitmap();
+ for (Node node : nodes) {
+ for (Slot slot : node.getPlan().getOutput()) {
+ if (slots.contains(slot)) {
+ Bitmap.set(bitSet, node.getIndex());
+ break;
+ }
+ }
+ }
+ return bitSet;
+ }
+
/**
* Graph simplifier need to update the edge for join ordering
*
diff --git
a/fe/fe-core/src/main/java/org/apache/doris/nereids/rules/joinreorder/hypergraph/Node.java
b/fe/fe-core/src/main/java/org/apache/doris/nereids/jobs/joinorder/hypergraph/Node.java
similarity index 79%
rename from
fe/fe-core/src/main/java/org/apache/doris/nereids/rules/joinreorder/hypergraph/Node.java
rename to
fe/fe-core/src/main/java/org/apache/doris/nereids/jobs/joinorder/hypergraph/Node.java
index 51712e24f2..8eb4bb843e 100644
---
a/fe/fe-core/src/main/java/org/apache/doris/nereids/rules/joinreorder/hypergraph/Node.java
+++
b/fe/fe-core/src/main/java/org/apache/doris/nereids/jobs/joinorder/hypergraph/Node.java
@@ -15,14 +15,12 @@
// specific language governing permissions and limitations
// under the License.
-package org.apache.doris.nereids.rules.joinreorder.hypergraph;
+package org.apache.doris.nereids.jobs.joinorder.hypergraph;
-import org.apache.doris.nereids.rules.joinreorder.hypergraph.bitmap.Bitmap;
-import org.apache.doris.nereids.trees.plans.GroupPlan;
+import org.apache.doris.nereids.jobs.joinorder.hypergraph.bitmap.Bitmap;
+import org.apache.doris.nereids.memo.Group;
import org.apache.doris.nereids.trees.plans.Plan;
-import com.google.common.base.Preconditions;
-
import java.util.ArrayList;
import java.util.BitSet;
import java.util.List;
@@ -33,7 +31,7 @@ import javax.annotation.Nullable;
*/
public class Node {
private final int index;
- private Plan plan;
+ private Group group;
private List<Edge> edges = new ArrayList<>();
// We split these into simple edges (only one node on each side) and
complex edges (others)
// because we can often quickly discard all simple edges by testing the
set of interesting nodes
@@ -43,8 +41,8 @@ public class Node {
private List<Edge> simpleEdges = new ArrayList<>();
private BitSet complexNeighborhood = new BitSet();
- public Node(int index, Plan plan) {
- this.plan = plan;
+ public Node(int index, Group group) {
+ this.group = group;
this.index = index;
}
@@ -65,7 +63,11 @@ public class Node {
throw new RuntimeException(String.format("There is no simple Edge
<%d - %s>", index, nodes));
} else if (Bitmap.isOverlap(complexNeighborhood, nodes)) {
for (Edge edge : complexEdges) {
- if (Bitmap.isSubset(edge.getLeft(), nodes) ||
Bitmap.isSubset(edge.getRight(), nodes)) {
+ // TODO: Right now we check all edges. But due to the simple
cmp, we can only check that the edge with
+ // one side that equal to this node
+ if ((Bitmap.isSubset(edge.getLeft(), nodes) &&
Bitmap.isSubset(edge.getRight(),
+ Bitmap.newBitmap(index))) ||
(Bitmap.isSubset(edge.getRight(), nodes) && Bitmap.isSubset(
+ edge.getLeft(), Bitmap.newBitmap(index)))) {
return edge;
}
}
@@ -82,12 +84,12 @@ public class Node {
}
public Plan getPlan() {
- return plan;
+ return group.getLogicalExpression().getPlan();
}
- public void setPlan(Plan plan) {
- this.plan = plan;
- }
+ // public void setPlan(Plan plan) {
+ // this.plan = plan;
+ // }
public List<Edge> getComplexEdges() {
return complexEdges;
@@ -137,6 +139,10 @@ public class Node {
* by graph simplifier.
*/
public void splitEdges() {
+ simpleEdges.clear();
+ Bitmap.clear(simpleNeighborhood);
+ complexEdges.clear();
+ Bitmap.clear(complexNeighborhood);
for (Edge edge : edges) {
if (edge.isSimple()) {
simpleEdges.add(edge);
@@ -153,12 +159,14 @@ public class Node {
}
public String getName() {
- Preconditions.checkArgument(plan instanceof GroupPlan, "Each node is a
group plan in child");
- return ((GroupPlan)
plan).getGroup().getLogicalExpression().getPlan().getType().name() + index;
+ return getPlan().getType().name() + index;
}
public double getRowCount() {
- Preconditions.checkArgument(plan instanceof GroupPlan, "Each node is a
group plan in child");
- return ((GroupPlan) plan).getGroup().getStatistics().getRowCount();
+ return group.getStatistics().getRowCount();
+ }
+
+ public Group getGroup() {
+ return group;
}
}
diff --git
a/fe/fe-core/src/main/java/org/apache/doris/nereids/rules/joinreorder/hypergraph/SubgraphEnumerator.java
b/fe/fe-core/src/main/java/org/apache/doris/nereids/jobs/joinorder/hypergraph/SubgraphEnumerator.java
similarity index 80%
rename from
fe/fe-core/src/main/java/org/apache/doris/nereids/rules/joinreorder/hypergraph/SubgraphEnumerator.java
rename to
fe/fe-core/src/main/java/org/apache/doris/nereids/jobs/joinorder/hypergraph/SubgraphEnumerator.java
index d17cd06f1c..03be7bf34c 100644
---
a/fe/fe-core/src/main/java/org/apache/doris/nereids/rules/joinreorder/hypergraph/SubgraphEnumerator.java
+++
b/fe/fe-core/src/main/java/org/apache/doris/nereids/jobs/joinorder/hypergraph/SubgraphEnumerator.java
@@ -15,11 +15,11 @@
// specific language governing permissions and limitations
// under the License.
-package org.apache.doris.nereids.rules.joinreorder.hypergraph;
+package org.apache.doris.nereids.jobs.joinorder.hypergraph;
-import org.apache.doris.nereids.rules.joinreorder.hypergraph.bitmap.Bitmap;
-import
org.apache.doris.nereids.rules.joinreorder.hypergraph.bitmap.SubsetIterator;
-import
org.apache.doris.nereids.rules.joinreorder.hypergraph.receiver.AbstractReceiver;
+import org.apache.doris.nereids.jobs.joinorder.hypergraph.bitmap.Bitmap;
+import
org.apache.doris.nereids.jobs.joinorder.hypergraph.bitmap.SubsetIterator;
+import
org.apache.doris.nereids.jobs.joinorder.hypergraph.receiver.AbstractReceiver;
import java.util.BitSet;
import java.util.List;
@@ -35,7 +35,7 @@ public class SubgraphEnumerator {
//The enumerated hyperGraph
HyperGraph hyperGraph;
- SubgraphEnumerator(AbstractReceiver receiver, HyperGraph hyperGraph) {
+ public SubgraphEnumerator(AbstractReceiver receiver, HyperGraph
hyperGraph) {
this.receiver = receiver;
this.hyperGraph = hyperGraph;
}
@@ -46,10 +46,11 @@ public class SubgraphEnumerator {
* @return whether the hyperGraph is enumerated successfully
*/
public boolean enumerate() {
+ receiver.reset();
List<Node> nodes = hyperGraph.getNodes();
// Init all nodes in Receiver
for (Node node : nodes) {
- receiver.addPlan(node.getBitSet(), node.getPlan());
+ receiver.addGroup(node.getBitSet(), node.getGroup());
}
hyperGraph.splitEdgesForNodes();
int size = nodes.size();
@@ -59,32 +60,38 @@ public class SubgraphEnumerator {
for (int i = size - 2; i >= 0; i--) {
BitSet csg = Bitmap.newBitmap(i);
Bitmap.unset(forbiddenNodes, i);
- emitCsg(csg);
- enumerateCsgRec(csg, Bitmap.newBitmap(forbiddenNodes));
+ if (!emitCsg(csg) || !enumerateCsgRec(csg,
Bitmap.newBitmap(forbiddenNodes))) {
+ return false;
+ }
}
return true;
}
// The general purpose of EnumerateCsgRec is to extend a given set csg,
which
// induces a connected subgraph of G to a larger set with the same
property.
- private void enumerateCsgRec(BitSet csg, BitSet forbiddenNodes) {
+ private boolean enumerateCsgRec(BitSet csg, BitSet forbiddenNodes) {
BitSet neighborhood = calcNeighborhood(csg, forbiddenNodes);
SubsetIterator subsetIterator = Bitmap.getSubsetIterator(neighborhood);
for (BitSet subset : subsetIterator) {
BitSet newCsg = Bitmap.newBitmapUnion(csg, subset);
if (receiver.contain(newCsg)) {
- emitCsg(newCsg);
+ if (!emitCsg(newCsg)) {
+ return false;
+ }
}
}
Bitmap.or(forbiddenNodes, neighborhood);
subsetIterator.reset();
for (BitSet subset : subsetIterator) {
BitSet newCsg = Bitmap.newBitmapUnion(csg, subset);
- enumerateCsgRec(newCsg, Bitmap.newBitmap(forbiddenNodes));
+ if (!enumerateCsgRec(newCsg, Bitmap.newBitmap(forbiddenNodes))) {
+ return false;
+ }
}
+ return true;
}
- private void enumerateCmpRec(BitSet csg, BitSet cmp, BitSet
forbiddenNodes) {
+ private boolean enumerateCmpRec(BitSet csg, BitSet cmp, BitSet
forbiddenNodes) {
BitSet neighborhood = calcNeighborhood(cmp, forbiddenNodes);
SubsetIterator subsetIterator = new SubsetIterator(neighborhood);
for (BitSet subset : subsetIterator) {
@@ -96,7 +103,9 @@ public class SubgraphEnumerator {
for (Edge edge : hyperGraph.getEdges()) {
if (Bitmap.isSubset(edge.getLeft(), csg) &&
Bitmap.isSubset(edge.getRight(), newCmp) || (
Bitmap.isSubset(edge.getLeft(), newCmp) &&
Bitmap.isSubset(edge.getRight(), csg))) {
- receiver.emitCsgCmp(csg, newCmp, edge);
+ if (!receiver.emitCsgCmp(csg, newCmp, edge)) {
+ return false;
+ }
break;
}
}
@@ -106,24 +115,30 @@ public class SubgraphEnumerator {
subsetIterator.reset();
for (BitSet subset : subsetIterator) {
BitSet newCmp = Bitmap.newBitmapUnion(cmp, subset);
- enumerateCmpRec(csg, newCmp, Bitmap.newBitmap(forbiddenNodes));
+ if (!enumerateCmpRec(csg, newCmp,
Bitmap.newBitmap(forbiddenNodes))) {
+ return false;
+ }
}
+ return true;
}
// EmitCsg takes as an argument a non-empty, proper subset csg of
HyperGraph , which
// induces a connected subgraph. It is then responsible to generate the
seeds for
// all cmp such that (csg, cmp) becomes a csg-cmp-pair.
- private void emitCsg(BitSet csg) {
+ private boolean emitCsg(BitSet csg) {
BitSet forbiddenNodes = Bitmap.newBitmapBetween(0,
Bitmap.nextSetBit(csg, 0));
Bitmap.or(forbiddenNodes, csg);
BitSet neighborhoods = calcNeighborhood(csg,
Bitmap.newBitmap(forbiddenNodes));
+
for (int nodeIndex : Bitmap.getReverseIterator(neighborhoods)) {
BitSet cmp = Bitmap.newBitmap(nodeIndex);
// whether there is an edge between csg and cmp
Node cmpNode = hyperGraph.getNode(nodeIndex);
Edge edge = cmpNode.tryGetEdgeWith(csg);
if (edge != null) {
- receiver.emitCsgCmp(csg, cmp, edge);
+ if (!receiver.emitCsgCmp(csg, cmp, edge)) {
+ return false;
+ }
}
// In order to avoid enumerate repeated cmp, e.g.,
@@ -138,8 +153,11 @@ public class SubgraphEnumerator {
BitSet newForbiddenNodes = Bitmap.newBitmapBetween(0, nodeIndex +
1);
Bitmap.and(newForbiddenNodes, neighborhoods);
Bitmap.or(newForbiddenNodes, forbiddenNodes);
- enumerateCmpRec(csg, cmp, newForbiddenNodes);
+ if (!enumerateCmpRec(csg, cmp, newForbiddenNodes)) {
+ return false;
+ }
}
+ return true;
}
// This function is used to calculate neighborhoods of given subgraph.
@@ -163,9 +181,9 @@ public class SubgraphEnumerator {
for (Edge edge : hyperGraph.getEdges()) {
BitSet left = edge.getLeft();
BitSet right = edge.getRight();
- if (Bitmap.isSubset(left, subGraph) && !Bitmap.isOverlap(left,
forbiddenNodes)) {
+ if (Bitmap.isSubset(left, subGraph) && !Bitmap.isOverlap(right,
forbiddenNodes)) {
Bitmap.set(neighborhoods, right.nextSetBit(0));
- } else if (Bitmap.isSubset(right, subGraph) &&
!Bitmap.isOverlap(right, forbiddenNodes)) {
+ } else if (Bitmap.isSubset(right, subGraph) &&
!Bitmap.isOverlap(left, forbiddenNodes)) {
Bitmap.set(neighborhoods, left.nextSetBit(0));
}
}
diff --git
a/fe/fe-core/src/main/java/org/apache/doris/nereids/rules/joinreorder/hypergraph/bitmap/BitSetIterator.java
b/fe/fe-core/src/main/java/org/apache/doris/nereids/jobs/joinorder/hypergraph/bitmap/BitSetIterator.java
similarity index 96%
rename from
fe/fe-core/src/main/java/org/apache/doris/nereids/rules/joinreorder/hypergraph/bitmap/BitSetIterator.java
rename to
fe/fe-core/src/main/java/org/apache/doris/nereids/jobs/joinorder/hypergraph/bitmap/BitSetIterator.java
index 1c1af0b1f1..77d55da361 100644
---
a/fe/fe-core/src/main/java/org/apache/doris/nereids/rules/joinreorder/hypergraph/bitmap/BitSetIterator.java
+++
b/fe/fe-core/src/main/java/org/apache/doris/nereids/jobs/joinorder/hypergraph/bitmap/BitSetIterator.java
@@ -15,7 +15,7 @@
// specific language governing permissions and limitations
// under the License.
-package org.apache.doris.nereids.rules.joinreorder.hypergraph.bitmap;
+package org.apache.doris.nereids.jobs.joinorder.hypergraph.bitmap;
import org.jetbrains.annotations.NotNull;
diff --git
a/fe/fe-core/src/main/java/org/apache/doris/nereids/rules/joinreorder/hypergraph/bitmap/Bitmap.java
b/fe/fe-core/src/main/java/org/apache/doris/nereids/jobs/joinorder/hypergraph/bitmap/Bitmap.java
similarity index 98%
rename from
fe/fe-core/src/main/java/org/apache/doris/nereids/rules/joinreorder/hypergraph/bitmap/Bitmap.java
rename to
fe/fe-core/src/main/java/org/apache/doris/nereids/jobs/joinorder/hypergraph/bitmap/Bitmap.java
index 27ba8d5994..619a9edf62 100644
---
a/fe/fe-core/src/main/java/org/apache/doris/nereids/rules/joinreorder/hypergraph/bitmap/Bitmap.java
+++
b/fe/fe-core/src/main/java/org/apache/doris/nereids/jobs/joinorder/hypergraph/bitmap/Bitmap.java
@@ -15,7 +15,7 @@
// specific language governing permissions and limitations
// under the License.
-package org.apache.doris.nereids.rules.joinreorder.hypergraph.bitmap;
+package org.apache.doris.nereids.jobs.joinorder.hypergraph.bitmap;
import java.util.BitSet;
diff --git
a/fe/fe-core/src/main/java/org/apache/doris/nereids/rules/joinreorder/hypergraph/bitmap/ReverseBitSetIterator.java
b/fe/fe-core/src/main/java/org/apache/doris/nereids/jobs/joinorder/hypergraph/bitmap/ReverseBitSetIterator.java
similarity index 96%
rename from
fe/fe-core/src/main/java/org/apache/doris/nereids/rules/joinreorder/hypergraph/bitmap/ReverseBitSetIterator.java
rename to
fe/fe-core/src/main/java/org/apache/doris/nereids/jobs/joinorder/hypergraph/bitmap/ReverseBitSetIterator.java
index b039fbed9d..125f05dc1c 100644
---
a/fe/fe-core/src/main/java/org/apache/doris/nereids/rules/joinreorder/hypergraph/bitmap/ReverseBitSetIterator.java
+++
b/fe/fe-core/src/main/java/org/apache/doris/nereids/jobs/joinorder/hypergraph/bitmap/ReverseBitSetIterator.java
@@ -15,7 +15,7 @@
// specific language governing permissions and limitations
// under the License.
-package org.apache.doris.nereids.rules.joinreorder.hypergraph.bitmap;
+package org.apache.doris.nereids.jobs.joinorder.hypergraph.bitmap;
import org.jetbrains.annotations.NotNull;
diff --git
a/fe/fe-core/src/main/java/org/apache/doris/nereids/rules/joinreorder/hypergraph/bitmap/SubsetIterator.java
b/fe/fe-core/src/main/java/org/apache/doris/nereids/jobs/joinorder/hypergraph/bitmap/SubsetIterator.java
similarity index 97%
rename from
fe/fe-core/src/main/java/org/apache/doris/nereids/rules/joinreorder/hypergraph/bitmap/SubsetIterator.java
rename to
fe/fe-core/src/main/java/org/apache/doris/nereids/jobs/joinorder/hypergraph/bitmap/SubsetIterator.java
index 0f48b3ad2f..8b7c2921df 100644
---
a/fe/fe-core/src/main/java/org/apache/doris/nereids/rules/joinreorder/hypergraph/bitmap/SubsetIterator.java
+++
b/fe/fe-core/src/main/java/org/apache/doris/nereids/jobs/joinorder/hypergraph/bitmap/SubsetIterator.java
@@ -15,7 +15,7 @@
// specific language governing permissions and limitations
// under the License.
-package org.apache.doris.nereids.rules.joinreorder.hypergraph.bitmap;
+package org.apache.doris.nereids.jobs.joinorder.hypergraph.bitmap;
import org.jetbrains.annotations.NotNull;
diff --git
a/fe/fe-core/src/main/java/org/apache/doris/nereids/rules/joinreorder/hypergraph/receiver/AbstractReceiver.java
b/fe/fe-core/src/main/java/org/apache/doris/nereids/jobs/joinorder/hypergraph/receiver/AbstractReceiver.java
similarity index 77%
rename from
fe/fe-core/src/main/java/org/apache/doris/nereids/rules/joinreorder/hypergraph/receiver/AbstractReceiver.java
rename to
fe/fe-core/src/main/java/org/apache/doris/nereids/jobs/joinorder/hypergraph/receiver/AbstractReceiver.java
index 1d6da72803..13c85595d1 100644
---
a/fe/fe-core/src/main/java/org/apache/doris/nereids/rules/joinreorder/hypergraph/receiver/AbstractReceiver.java
+++
b/fe/fe-core/src/main/java/org/apache/doris/nereids/jobs/joinorder/hypergraph/receiver/AbstractReceiver.java
@@ -15,10 +15,10 @@
// specific language governing permissions and limitations
// under the License.
-package org.apache.doris.nereids.rules.joinreorder.hypergraph.receiver;
+package org.apache.doris.nereids.jobs.joinorder.hypergraph.receiver;
-import org.apache.doris.nereids.rules.joinreorder.hypergraph.Edge;
-import org.apache.doris.nereids.trees.plans.Plan;
+import org.apache.doris.nereids.jobs.joinorder.hypergraph.Edge;
+import org.apache.doris.nereids.memo.Group;
import java.util.BitSet;
@@ -28,9 +28,11 @@ import java.util.BitSet;
public interface AbstractReceiver {
public boolean emitCsgCmp(BitSet csg, BitSet cmp, Edge edge);
- public void addPlan(BitSet bitSet, Plan plan);
+ public void addGroup(BitSet bitSet, Group group);
public boolean contain(BitSet bitSet);
- public Plan getBestPlan(BitSet bitSet);
+ public void reset();
+
+ public Group getBestPlan(BitSet bitSet);
}
diff --git
a/fe/fe-core/src/main/java/org/apache/doris/nereids/rules/joinreorder/hypergraph/receiver/Counter.java
b/fe/fe-core/src/main/java/org/apache/doris/nereids/jobs/joinorder/hypergraph/receiver/Counter.java
similarity index 77%
rename from
fe/fe-core/src/main/java/org/apache/doris/nereids/rules/joinreorder/hypergraph/receiver/Counter.java
rename to
fe/fe-core/src/main/java/org/apache/doris/nereids/jobs/joinorder/hypergraph/receiver/Counter.java
index 5633d1b9c9..b3bba9a2e8 100644
---
a/fe/fe-core/src/main/java/org/apache/doris/nereids/rules/joinreorder/hypergraph/receiver/Counter.java
+++
b/fe/fe-core/src/main/java/org/apache/doris/nereids/jobs/joinorder/hypergraph/receiver/Counter.java
@@ -15,10 +15,10 @@
// specific language governing permissions and limitations
// under the License.
-package org.apache.doris.nereids.rules.joinreorder.hypergraph.receiver;
+package org.apache.doris.nereids.jobs.joinorder.hypergraph.receiver;
-import org.apache.doris.nereids.rules.joinreorder.hypergraph.Edge;
-import org.apache.doris.nereids.trees.plans.Plan;
+import org.apache.doris.nereids.jobs.joinorder.hypergraph.Edge;
+import org.apache.doris.nereids.memo.Group;
import com.google.common.base.Preconditions;
@@ -30,8 +30,18 @@ import java.util.HashMap;
*/
public class Counter implements AbstractReceiver {
// limit define the max number of csg-cmp pair in this Receiver
+ private int limit;
+ private int emitCount = 0;
private HashMap<BitSet, Integer> counter = new HashMap<>();
+ public Counter() {
+ this.limit = Integer.MAX_VALUE;
+ }
+
+ public Counter(int limit) {
+ this.limit = limit;
+ }
+
/**
* Emit a new plan from bottom to top
*
@@ -43,6 +53,10 @@ public class Counter implements AbstractReceiver {
public boolean emitCsgCmp(BitSet left, BitSet right, Edge edge) {
Preconditions.checkArgument(counter.containsKey(left));
Preconditions.checkArgument(counter.containsKey(right));
+ emitCount += 1;
+ if (emitCount > limit) {
+ return false;
+ }
BitSet bitSet = new BitSet();
bitSet.or(left);
bitSet.or(right);
@@ -54,7 +68,7 @@ public class Counter implements AbstractReceiver {
return true;
}
- public void addPlan(BitSet bitSet, Plan plan) {
+ public void addGroup(BitSet bitSet, Group group) {
counter.put(bitSet, 1);
}
@@ -62,7 +76,12 @@ public class Counter implements AbstractReceiver {
return counter.containsKey(bitSet);
}
- public Plan getBestPlan(BitSet bitSet) {
+ public void reset() {
+ this.counter.clear();
+ emitCount = 0;
+ }
+
+ public Group getBestPlan(BitSet bitSet) {
throw new RuntimeException("Counter does not support getBestPlan()");
}
@@ -73,4 +92,8 @@ public class Counter implements AbstractReceiver {
public HashMap<BitSet, Integer> getAllCount() {
return counter;
}
+
+ public int getLimit() {
+ return limit;
+ }
}
diff --git
a/fe/fe-core/src/main/java/org/apache/doris/nereids/jobs/joinorder/hypergraph/receiver/PlanReceiver.java
b/fe/fe-core/src/main/java/org/apache/doris/nereids/jobs/joinorder/hypergraph/receiver/PlanReceiver.java
new file mode 100644
index 0000000000..be708902a9
--- /dev/null
+++
b/fe/fe-core/src/main/java/org/apache/doris/nereids/jobs/joinorder/hypergraph/receiver/PlanReceiver.java
@@ -0,0 +1,140 @@
+// 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.jobs.joinorder.hypergraph.receiver;
+
+import org.apache.doris.nereids.jobs.joinorder.hypergraph.Edge;
+import org.apache.doris.nereids.jobs.joinorder.hypergraph.bitmap.Bitmap;
+import org.apache.doris.nereids.memo.Group;
+import org.apache.doris.nereids.memo.GroupExpression;
+import org.apache.doris.nereids.properties.PhysicalProperties;
+import org.apache.doris.nereids.stats.StatsCalculator;
+import org.apache.doris.nereids.trees.plans.Plan;
+import org.apache.doris.nereids.trees.plans.logical.LogicalJoin;
+
+import com.google.common.base.Preconditions;
+import com.google.common.collect.Lists;
+
+import java.util.BitSet;
+import java.util.HashMap;
+
+/**
+ * The Receiver is used for cached the plan that has been emitted and build
the new plan
+ */
+public class PlanReceiver implements AbstractReceiver {
+ // limit define the max number of csg-cmp pair in this Receiver
+ HashMap<BitSet, Group> planTable = new HashMap<>();
+ int limit;
+ int emitCount = 0;
+
+ public PlanReceiver() {
+ limit = Integer.MAX_VALUE;
+ }
+
+ public PlanReceiver(int limit) {
+ this.limit = limit;
+ }
+
+ /**
+ * Emit a new plan from bottom to top
+ *
+ * @param left the bitmap of left child tree
+ * @param right the bitmap of the right child tree
+ * @param edge the join operator
+ * @return the left and the right can be connected by the edge
+ */
+ @Override
+ public boolean emitCsgCmp(BitSet left, BitSet right, Edge edge) {
+ Preconditions.checkArgument(planTable.containsKey(left));
+ Preconditions.checkArgument(planTable.containsKey(right));
+ emitCount += 1;
+ if (emitCount > limit) {
+ return false;
+ }
+ BitSet fullKey = Bitmap.newBitmapUnion(left, right);
+ Group group1 = constructGroup(left, right, edge);
+ Group group2 = constructGroup(right, left, edge);
+ Group winnerGroup;
+ if
(group1.getLogicalExpression().getCostByProperties(PhysicalProperties.ANY) <
group2.getLogicalExpression()
+ .getCostByProperties(PhysicalProperties.ANY)) {
+ winnerGroup = group1;
+ } else {
+ winnerGroup = group2;
+ }
+
+ if (!planTable.containsKey(fullKey)
+ ||
planTable.get(fullKey).getLogicalExpression().getCostByProperties(PhysicalProperties.ANY)
+ >
winnerGroup.getLogicalExpression().getCostByProperties(PhysicalProperties.ANY))
{
+ planTable.put(fullKey, winnerGroup);
+ }
+ return true;
+ }
+
+ @Override
+ public void addGroup(BitSet bitSet, Group group) {
+ planTable.put(bitSet, group);
+ }
+
+ @Override
+ public boolean contain(BitSet bitSet) {
+ return planTable.containsKey(bitSet);
+ }
+
+ @Override
+ public void reset() {
+ planTable.clear();
+ emitCount = 0;
+ }
+
+ @Override
+ public Group getBestPlan(BitSet bitSet) {
+ Preconditions.checkArgument(planTable.containsKey(bitSet));
+ return planTable.get(bitSet);
+ }
+
+ private double getSimpleCost(Plan plan) {
+ if (!(plan instanceof LogicalJoin)) {
+ return
plan.getGroupExpression().get().getOwnerGroup().getStatistics().getRowCount();
+ }
+ return
plan.getGroupExpression().get().getCostByProperties(PhysicalProperties.ANY);
+ }
+
+ private Group constructGroup(BitSet left, BitSet right, Edge edge) {
+ Preconditions.checkArgument(planTable.containsKey(left));
+ Preconditions.checkArgument(planTable.containsKey(right));
+ Group leftGroup = planTable.get(left);
+ Group rightGroup = planTable.get(right);
+ Plan leftPlan = leftGroup.getLogicalExpression().getPlan();
+ Plan rightPlan = rightGroup.getLogicalExpression().getPlan();
+
+ double cost = getSimpleCost(leftPlan) + getSimpleCost(rightPlan);
+ LogicalJoin newJoin = new LogicalJoin(edge.getJoin().getJoinType(),
edge.getJoin().getExpressions(),
+ leftGroup.getLogicalExpression().getPlan(),
+ rightGroup.getLogicalExpression().getPlan());
+
+ GroupExpression groupExpression = new GroupExpression(newJoin,
Lists.newArrayList(leftGroup, rightGroup));
+ Group group = new Group();
+ group.addGroupExpression(groupExpression);
+ StatsCalculator.estimate(groupExpression);
+ cost += group.getStatistics().getRowCount();
+
+ groupExpression.updateLowestCostTable(PhysicalProperties.ANY,
+ Lists.newArrayList(PhysicalProperties.ANY,
PhysicalProperties.ANY), cost);
+ return group;
+ }
+}
+
diff --git a/fe/fe-core/src/main/java/org/apache/doris/nereids/memo/Group.java
b/fe/fe-core/src/main/java/org/apache/doris/nereids/memo/Group.java
index e699e74eb3..ca7e47a0f9 100644
--- a/fe/fe-core/src/main/java/org/apache/doris/nereids/memo/Group.java
+++ b/fe/fe-core/src/main/java/org/apache/doris/nereids/memo/Group.java
@@ -20,6 +20,7 @@ package org.apache.doris.nereids.memo;
import org.apache.doris.common.Pair;
import org.apache.doris.nereids.properties.LogicalProperties;
import org.apache.doris.nereids.properties.PhysicalProperties;
+import org.apache.doris.nereids.trees.plans.logical.LogicalJoin;
import org.apache.doris.nereids.trees.plans.logical.LogicalPlan;
import org.apache.doris.nereids.util.TreeStringUtils;
import org.apache.doris.statistics.StatsDeriveResult;
@@ -316,6 +317,10 @@ public class Group {
lowestCostPlans.clear();
}
+ public boolean isJoinGroup() {
+ return getLogicalExpression().getPlan() instanceof LogicalJoin;
+ }
+
@Override
public boolean equals(Object o) {
if (this == o) {
diff --git
a/fe/fe-core/src/main/java/org/apache/doris/nereids/memo/GroupExpression.java
b/fe/fe-core/src/main/java/org/apache/doris/nereids/memo/GroupExpression.java
index d7cf89ed3b..da5b65f1c0 100644
---
a/fe/fe-core/src/main/java/org/apache/doris/nereids/memo/GroupExpression.java
+++
b/fe/fe-core/src/main/java/org/apache/doris/nereids/memo/GroupExpression.java
@@ -105,6 +105,11 @@ public class GroupExpression {
return children.get(i);
}
+ public void setChild(int i, Group group) {
+ children.set(i, group);
+ group.addParentExpression(this);
+ }
+
public List<Group> children() {
return children;
}
diff --git
a/fe/fe-core/src/main/java/org/apache/doris/nereids/rules/joinreorder/HyperGraphJoinReorder.java
b/fe/fe-core/src/main/java/org/apache/doris/nereids/rules/joinreorder/HyperGraphJoinReorder.java
deleted file mode 100644
index 52d1609b9c..0000000000
---
a/fe/fe-core/src/main/java/org/apache/doris/nereids/rules/joinreorder/HyperGraphJoinReorder.java
+++ /dev/null
@@ -1,48 +0,0 @@
-// 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.joinreorder;
-
-import org.apache.doris.nereids.rules.Rule;
-import org.apache.doris.nereids.rules.RuleType;
-import org.apache.doris.nereids.rules.joinreorder.hypergraph.HyperGraph;
-import org.apache.doris.nereids.rules.rewrite.OneRewriteRuleFactory;
-import org.apache.doris.nereids.trees.plans.Plan;
-import org.apache.doris.nereids.trees.plans.logical.LogicalJoin;
-import org.apache.doris.nereids.trees.plans.logical.LogicalProject;
-
-/**
- * This rule is for Join Reorder (non Cascades Transfrom Join Reorder).
- */
-public class HyperGraphJoinReorder extends OneRewriteRuleFactory {
- @Override
- public Rule build() {
- // TODO: we need a pattern to match a subtree of join and mark the
node in this tree ordered
- return logicalJoin(
- subTree(LogicalJoin.class, LogicalProject.class),
- subTree(LogicalJoin.class, LogicalProject.class))
- .thenApply(ctx -> {
- LogicalJoin<? extends Plan, ? extends Plan> rootJoin =
ctx.root;
- // TODO: check mark.
- HyperGraph graph = HyperGraph.fromPlan(rootJoin);
- if (graph.optimize()) {
- return graph.toPlan();
- }
- return null;
- }).toRule(RuleType.JOIN_REORDER);
- }
-}
diff --git
a/fe/fe-core/src/main/java/org/apache/doris/nereids/rules/joinreorder/HyperGraphJoinReorderGroupLeft.java
b/fe/fe-core/src/main/java/org/apache/doris/nereids/rules/joinreorder/HyperGraphJoinReorderGroupLeft.java
deleted file mode 100644
index 56aa07a0fc..0000000000
---
a/fe/fe-core/src/main/java/org/apache/doris/nereids/rules/joinreorder/HyperGraphJoinReorderGroupLeft.java
+++ /dev/null
@@ -1,48 +0,0 @@
-// 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.joinreorder;
-
-import org.apache.doris.nereids.rules.Rule;
-import org.apache.doris.nereids.rules.RuleType;
-import org.apache.doris.nereids.rules.joinreorder.hypergraph.HyperGraph;
-import org.apache.doris.nereids.rules.rewrite.OneRewriteRuleFactory;
-import org.apache.doris.nereids.trees.plans.Plan;
-import org.apache.doris.nereids.trees.plans.logical.LogicalJoin;
-import org.apache.doris.nereids.trees.plans.logical.LogicalProject;
-
-/**
- * This rule is for Join Reorder (non Cascades Transfrom Join Reorder).
- */
-public class HyperGraphJoinReorderGroupLeft extends OneRewriteRuleFactory {
- @Override
- public Rule build() {
- // TODO: we need a pattern to match a subtree of join and mark the
node in this tree ordered
- return logicalJoin(
- group(),
- subTree(LogicalJoin.class, LogicalProject.class))
- .thenApply(ctx -> {
- LogicalJoin<? extends Plan, ? extends Plan> rootJoin =
ctx.root;
- HyperGraph graph = HyperGraph.fromPlan(rootJoin);
- System.out.println(graph.toDottyHyperGraph());
- if (graph.optimize()) {
- return graph.toPlan();
- }
- return null;
- }).toRule(RuleType.JOIN_REORDER);
- }
-}
diff --git
a/fe/fe-core/src/main/java/org/apache/doris/nereids/rules/joinreorder/HyperGraphJoinReorderGroupRight.java
b/fe/fe-core/src/main/java/org/apache/doris/nereids/rules/joinreorder/HyperGraphJoinReorderGroupRight.java
deleted file mode 100644
index c1f3d1e16c..0000000000
---
a/fe/fe-core/src/main/java/org/apache/doris/nereids/rules/joinreorder/HyperGraphJoinReorderGroupRight.java
+++ /dev/null
@@ -1,47 +0,0 @@
-// 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.joinreorder;
-
-import org.apache.doris.nereids.rules.Rule;
-import org.apache.doris.nereids.rules.RuleType;
-import org.apache.doris.nereids.rules.joinreorder.hypergraph.HyperGraph;
-import org.apache.doris.nereids.rules.rewrite.OneRewriteRuleFactory;
-import org.apache.doris.nereids.trees.plans.Plan;
-import org.apache.doris.nereids.trees.plans.logical.LogicalJoin;
-import org.apache.doris.nereids.trees.plans.logical.LogicalProject;
-
-/**
- * This rule is for Join Reorder (non Cascades Transfrom Join Reorder).
- */
-public class HyperGraphJoinReorderGroupRight extends OneRewriteRuleFactory {
- @Override
- public Rule build() {
- // TODO: we need a pattern to match a subtree of join and mark the
node in this tree ordered
- return logicalJoin(
- subTree(LogicalJoin.class, LogicalProject.class),
- group())
- .thenApply(ctx -> {
- LogicalJoin<? extends Plan, ? extends Plan> rootJoin =
ctx.root;
- HyperGraph graph = HyperGraph.fromPlan(rootJoin);
- if (graph.optimize()) {
- return graph.toPlan();
- }
- return null;
- }).toRule(RuleType.JOIN_REORDER);
- }
-}
diff --git
a/fe/fe-core/src/main/java/org/apache/doris/nereids/rules/joinreorder/hypergraph/receiver/PlanTable.java
b/fe/fe-core/src/main/java/org/apache/doris/nereids/rules/joinreorder/hypergraph/receiver/PlanTable.java
deleted file mode 100644
index 2cb9b62d23..0000000000
---
a/fe/fe-core/src/main/java/org/apache/doris/nereids/rules/joinreorder/hypergraph/receiver/PlanTable.java
+++ /dev/null
@@ -1,57 +0,0 @@
-// 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.joinreorder.hypergraph.receiver;
-
-import org.apache.doris.nereids.rules.joinreorder.hypergraph.Edge;
-import org.apache.doris.nereids.trees.plans.Plan;
-
-import java.util.BitSet;
-import java.util.HashMap;
-
-/**
- * The Receiver is used for cached the plan that has been emitted and build
the new plan
- */
-public class PlanTable implements AbstractReceiver {
- // limit define the max number of csg-cmp pair in this Receiver
- HashMap<BitSet, Integer> counter;
-
- /**
- * Emit a new plan from bottom to top
- *
- * @param left the bitmap of left child tree
- * @param right the bitmap of the right child tree
- * @param edge the join operator
- * @return the left and the right can be connected by the edge
- */
- public boolean emitCsgCmp(BitSet left, BitSet right, Edge edge) {
- throw new RuntimeException("PlanTable does not support emitCsgCmp()");
- }
-
- public void addPlan(BitSet bitSet, Plan plan) {
- throw new RuntimeException("PlanTable does not support addPlan()");
- }
-
- public boolean contain(BitSet bitSet) {
- throw new RuntimeException("PlanTable does not support contain()");
- }
-
- public Plan getBestPlan(BitSet bitSet) {
- throw new RuntimeException("PlanTable does not support getBestPlan()");
- }
-}
-
diff --git
a/fe/fe-core/src/test/java/org/apache/doris/nereids/rules/joinreorder/HyperGraphJoinReorderGroupLeftTest.java
b/fe/fe-core/src/test/java/org/apache/doris/nereids/jobs/joinorder/JoinOrderJobTest.java
similarity index 85%
rename from
fe/fe-core/src/test/java/org/apache/doris/nereids/rules/joinreorder/HyperGraphJoinReorderGroupLeftTest.java
rename to
fe/fe-core/src/test/java/org/apache/doris/nereids/jobs/joinorder/JoinOrderJobTest.java
index b8d74d555b..93edf18663 100644
---
a/fe/fe-core/src/test/java/org/apache/doris/nereids/rules/joinreorder/HyperGraphJoinReorderGroupLeftTest.java
+++
b/fe/fe-core/src/test/java/org/apache/doris/nereids/jobs/joinorder/JoinOrderJobTest.java
@@ -15,7 +15,7 @@
// specific language governing permissions and limitations
// under the License.
-package org.apache.doris.nereids.rules.joinreorder;
+package org.apache.doris.nereids.jobs.joinorder;
import org.apache.doris.common.Pair;
import org.apache.doris.nereids.trees.plans.JoinType;
@@ -26,17 +26,18 @@ import org.apache.doris.nereids.util.MemoTestUtils;
import org.apache.doris.nereids.util.PlanChecker;
import org.apache.doris.nereids.util.PlanConstructor;
+import com.google.common.collect.Lists;
import org.junit.jupiter.api.Test;
-class HyperGraphJoinReorderGroupLeftTest {
- private final LogicalOlapScan scan1 =
PlanConstructor.newLogicalOlapScan(0, "t1", 0);
- private final LogicalOlapScan scan2 =
PlanConstructor.newLogicalOlapScan(1, "t2", 0);
- private final LogicalOlapScan scan3 =
PlanConstructor.newLogicalOlapScan(2, "t3", 0);
- private final LogicalOlapScan scan4 =
PlanConstructor.newLogicalOlapScan(3, "t4", 0);
- private final LogicalOlapScan scan5 =
PlanConstructor.newLogicalOlapScan(4, "t5", 0);
+public class JoinOrderJobTest {
+ private final LogicalOlapScan scan1 =
PlanConstructor.newLogicalOlapScan(1, "t1", 0);
+ private final LogicalOlapScan scan2 =
PlanConstructor.newLogicalOlapScan(2, "t2", 0);
+ private final LogicalOlapScan scan3 =
PlanConstructor.newLogicalOlapScan(3, "t3", 0);
+ private final LogicalOlapScan scan4 =
PlanConstructor.newLogicalOlapScan(4, "t4", 0);
+ private final LogicalOlapScan scan5 =
PlanConstructor.newLogicalOlapScan(5, "t5", 0);
@Test
- void test() {
+ void testJoinOrderJob() {
LogicalPlan plan = new LogicalPlanBuilder(scan1)
.hashJoinUsing(
new LogicalPlanBuilder(scan2)
@@ -46,11 +47,12 @@ class HyperGraphJoinReorderGroupLeftTest {
.build(),
JoinType.INNER_JOIN, Pair.of(0, 1)
)
+ .project(Lists.newArrayList(1))
.build();
-
+ System.out.println(plan.treeString());
PlanChecker.from(MemoTestUtils.createConnectContext(), plan)
.deriveStats()
- .applyTopDown(new HyperGraphJoinReorderGroupLeft())
+ .orderJoin()
.printlnTree();
}
}
diff --git
a/fe/fe-core/src/test/java/org/apache/doris/nereids/rules/joinreorder/hypergraph/BitSetTest.java
b/fe/fe-core/src/test/java/org/apache/doris/nereids/jobs/joinorder/hypergraph/BitSetTest.java
similarity index 86%
rename from
fe/fe-core/src/test/java/org/apache/doris/nereids/rules/joinreorder/hypergraph/BitSetTest.java
rename to
fe/fe-core/src/test/java/org/apache/doris/nereids/jobs/joinorder/hypergraph/BitSetTest.java
index 8a40a0a534..20b69583ac 100644
---
a/fe/fe-core/src/test/java/org/apache/doris/nereids/rules/joinreorder/hypergraph/BitSetTest.java
+++
b/fe/fe-core/src/test/java/org/apache/doris/nereids/jobs/joinorder/hypergraph/BitSetTest.java
@@ -15,10 +15,10 @@
// specific language governing permissions and limitations
// under the License.
-package org.apache.doris.nereids.rules.joinreorder.hypergraph;
+package org.apache.doris.nereids.jobs.joinorder.hypergraph;
-import org.apache.doris.nereids.rules.joinreorder.hypergraph.bitmap.Bitmap;
-import
org.apache.doris.nereids.rules.joinreorder.hypergraph.bitmap.SubsetIterator;
+import org.apache.doris.nereids.jobs.joinorder.hypergraph.bitmap.Bitmap;
+import
org.apache.doris.nereids.jobs.joinorder.hypergraph.bitmap.SubsetIterator;
import org.junit.jupiter.api.Assertions;
import org.junit.jupiter.api.Test;
diff --git
a/fe/fe-core/src/test/java/org/apache/doris/nereids/rules/joinreorder/hypergraph/CircleDetectorTest.java
b/fe/fe-core/src/test/java/org/apache/doris/nereids/jobs/joinorder/hypergraph/CircleDetectorTest.java
similarity index 96%
rename from
fe/fe-core/src/test/java/org/apache/doris/nereids/rules/joinreorder/hypergraph/CircleDetectorTest.java
rename to
fe/fe-core/src/test/java/org/apache/doris/nereids/jobs/joinorder/hypergraph/CircleDetectorTest.java
index de654924ea..bee8b56059 100644
---
a/fe/fe-core/src/test/java/org/apache/doris/nereids/rules/joinreorder/hypergraph/CircleDetectorTest.java
+++
b/fe/fe-core/src/test/java/org/apache/doris/nereids/jobs/joinorder/hypergraph/CircleDetectorTest.java
@@ -15,7 +15,7 @@
// specific language governing permissions and limitations
// under the License.
-package org.apache.doris.nereids.rules.joinreorder.hypergraph;
+package org.apache.doris.nereids.jobs.joinorder.hypergraph;
import com.google.common.collect.ImmutableList;
import org.junit.jupiter.api.Assertions;
diff --git
a/fe/fe-core/src/test/java/org/apache/doris/nereids/rules/joinreorder/hypergraph/GraphSimplifierTest.java
b/fe/fe-core/src/test/java/org/apache/doris/nereids/jobs/joinorder/hypergraph/GraphSimplifierTest.java
similarity index 81%
rename from
fe/fe-core/src/test/java/org/apache/doris/nereids/rules/joinreorder/hypergraph/GraphSimplifierTest.java
rename to
fe/fe-core/src/test/java/org/apache/doris/nereids/jobs/joinorder/hypergraph/GraphSimplifierTest.java
index d0365615ca..ec6790f41d 100644
---
a/fe/fe-core/src/test/java/org/apache/doris/nereids/rules/joinreorder/hypergraph/GraphSimplifierTest.java
+++
b/fe/fe-core/src/test/java/org/apache/doris/nereids/jobs/joinorder/hypergraph/GraphSimplifierTest.java
@@ -15,9 +15,9 @@
// specific language governing permissions and limitations
// under the License.
-package org.apache.doris.nereids.rules.joinreorder.hypergraph;
+package org.apache.doris.nereids.jobs.joinorder.hypergraph;
-import org.apache.doris.nereids.rules.joinreorder.hypergraph.receiver.Counter;
+import org.apache.doris.nereids.jobs.joinorder.hypergraph.receiver.Counter;
import org.apache.doris.nereids.trees.plans.JoinType;
import org.apache.doris.nereids.util.HyperGraphBuilder;
@@ -33,7 +33,7 @@ public class GraphSimplifierTest {
// |
// t2
HyperGraph hyperGraph = new HyperGraphBuilder()
- .init(10, 20, 30, 40, 50)
+ .init(10, 30, 20, 40, 50)
.addEdge(JoinType.INNER_JOIN, 0, 1)
.addEdge(JoinType.INNER_JOIN, 0, 2)
.addEdge(JoinType.INNER_JOIN, 0, 3)
@@ -47,8 +47,9 @@ public class GraphSimplifierTest {
SubgraphEnumerator subgraphEnumerator = new
SubgraphEnumerator(counter, hyperGraph);
subgraphEnumerator.enumerate();
for (int count : counter.getAllCount().values()) {
- Assertions.assertEquals(count, 1);
+ Assertions.assertTrue(count < 10);
}
+ Assertions.assertTrue(graphSimplifier.isTotalOrder());
}
@Test
@@ -74,8 +75,9 @@ public class GraphSimplifierTest {
SubgraphEnumerator subgraphEnumerator = new
SubgraphEnumerator(counter, hyperGraph);
subgraphEnumerator.enumerate();
for (int count : counter.getAllCount().values()) {
- Assertions.assertEquals(count, 1);
+ Assertions.assertTrue(count < 10);
}
+ Assertions.assertTrue(graphSimplifier.isTotalOrder());
}
@Test
@@ -102,8 +104,9 @@ public class GraphSimplifierTest {
SubgraphEnumerator subgraphEnumerator = new
SubgraphEnumerator(counter, hyperGraph);
subgraphEnumerator.enumerate();
for (int count : counter.getAllCount().values()) {
- Assertions.assertEquals(count, 1);
+ Assertions.assertTrue(count < 10);
}
+ Assertions.assertTrue(graphSimplifier.isTotalOrder());
}
@Test
@@ -135,8 +138,9 @@ public class GraphSimplifierTest {
SubgraphEnumerator subgraphEnumerator = new
SubgraphEnumerator(counter, hyperGraph);
subgraphEnumerator.enumerate();
for (int count : counter.getAllCount().values()) {
- Assertions.assertEquals(count, 1);
+ Assertions.assertTrue(count < 10);
}
+ Assertions.assertTrue(graphSimplifier.isTotalOrder());
}
@Test
@@ -160,8 +164,8 @@ public class GraphSimplifierTest {
@Test
void testRandomQuery() {
- for (int i = 0; i < 10; i++) {
- HyperGraph hyperGraph = new
HyperGraphBuilder().randomBuildWith(10, 40);
+ for (int i = 0; i < 100; i++) {
+ HyperGraph hyperGraph = new
HyperGraphBuilder().randomBuildWith(20, 40);
GraphSimplifier graphSimplifier = new GraphSimplifier(hyperGraph);
graphSimplifier.initFirstStep();
while (graphSimplifier.applySimplificationStep()) {
@@ -170,8 +174,25 @@ public class GraphSimplifierTest {
SubgraphEnumerator subgraphEnumerator = new
SubgraphEnumerator(counter, hyperGraph);
subgraphEnumerator.enumerate();
for (int count : counter.getAllCount().values()) {
- Assertions.assertEquals(count, 1);
+ Assertions.assertTrue(count < 1000);
}
+ Assertions.assertTrue(graphSimplifier.isTotalOrder());
}
}
+
+ @Test
+ void testLimit() {
+ int tableNum = 10;
+ int edgeNum = 20;
+ for (int limit = 1000; limit < 10000; limit += 100) {
+ HyperGraph hyperGraph = new
HyperGraphBuilder().randomBuildWith(tableNum, edgeNum);
+ GraphSimplifier graphSimplifier = new GraphSimplifier(hyperGraph);
+ graphSimplifier.simplifyGraph(limit);
+ Counter counter = new Counter();
+ SubgraphEnumerator subgraphEnumerator = new
SubgraphEnumerator(counter, hyperGraph);
+ subgraphEnumerator.enumerate();
+ Assertions.assertTrue(counter.getLimit() >= 0);
+ }
+
+ }
}
diff --git
a/fe/fe-core/src/test/java/org/apache/doris/nereids/rules/joinreorder/hypergraph/HyperGraphTest.java
b/fe/fe-core/src/test/java/org/apache/doris/nereids/jobs/joinorder/hypergraph/HyperGraphTest.java
similarity index 98%
rename from
fe/fe-core/src/test/java/org/apache/doris/nereids/rules/joinreorder/hypergraph/HyperGraphTest.java
rename to
fe/fe-core/src/test/java/org/apache/doris/nereids/jobs/joinorder/hypergraph/HyperGraphTest.java
index df7cf69852..113a8db93d 100644
---
a/fe/fe-core/src/test/java/org/apache/doris/nereids/rules/joinreorder/hypergraph/HyperGraphTest.java
+++
b/fe/fe-core/src/test/java/org/apache/doris/nereids/jobs/joinorder/hypergraph/HyperGraphTest.java
@@ -15,7 +15,7 @@
// specific language governing permissions and limitations
// under the License.
-package org.apache.doris.nereids.rules.joinreorder.hypergraph;
+package org.apache.doris.nereids.jobs.joinorder.hypergraph;
import org.apache.doris.nereids.trees.plans.JoinType;
import org.apache.doris.nereids.util.HyperGraphBuilder;
diff --git
a/fe/fe-core/src/test/java/org/apache/doris/nereids/rules/joinreorder/hypergraph/SubgraphEnumeratorTest.java
b/fe/fe-core/src/test/java/org/apache/doris/nereids/jobs/joinorder/hypergraph/SubgraphEnumeratorTest.java
similarity index 95%
rename from
fe/fe-core/src/test/java/org/apache/doris/nereids/rules/joinreorder/hypergraph/SubgraphEnumeratorTest.java
rename to
fe/fe-core/src/test/java/org/apache/doris/nereids/jobs/joinorder/hypergraph/SubgraphEnumeratorTest.java
index 7f1bd8ec11..1b4e1fb306 100644
---
a/fe/fe-core/src/test/java/org/apache/doris/nereids/rules/joinreorder/hypergraph/SubgraphEnumeratorTest.java
+++
b/fe/fe-core/src/test/java/org/apache/doris/nereids/jobs/joinorder/hypergraph/SubgraphEnumeratorTest.java
@@ -15,11 +15,11 @@
// specific language governing permissions and limitations
// under the License.
-package org.apache.doris.nereids.rules.joinreorder.hypergraph;
+package org.apache.doris.nereids.jobs.joinorder.hypergraph;
-import org.apache.doris.nereids.rules.joinreorder.hypergraph.bitmap.Bitmap;
-import
org.apache.doris.nereids.rules.joinreorder.hypergraph.bitmap.SubsetIterator;
-import org.apache.doris.nereids.rules.joinreorder.hypergraph.receiver.Counter;
+import org.apache.doris.nereids.jobs.joinorder.hypergraph.bitmap.Bitmap;
+import
org.apache.doris.nereids.jobs.joinorder.hypergraph.bitmap.SubsetIterator;
+import org.apache.doris.nereids.jobs.joinorder.hypergraph.receiver.Counter;
import org.apache.doris.nereids.trees.plans.JoinType;
import org.apache.doris.nereids.util.HyperGraphBuilder;
diff --git
a/fe/fe-core/src/test/java/org/apache/doris/nereids/rules/joinreorder/HyperGraphJoinReorderGroupRightTest.java
b/fe/fe-core/src/test/java/org/apache/doris/nereids/rules/joinreorder/HyperGraphJoinReorderGroupRightTest.java
deleted file mode 100644
index e9ee1d1542..0000000000
---
a/fe/fe-core/src/test/java/org/apache/doris/nereids/rules/joinreorder/HyperGraphJoinReorderGroupRightTest.java
+++ /dev/null
@@ -1,52 +0,0 @@
-// 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.joinreorder;
-
-import org.apache.doris.common.Pair;
-import org.apache.doris.nereids.trees.plans.JoinType;
-import org.apache.doris.nereids.trees.plans.logical.LogicalOlapScan;
-import org.apache.doris.nereids.trees.plans.logical.LogicalPlan;
-import org.apache.doris.nereids.util.LogicalPlanBuilder;
-import org.apache.doris.nereids.util.MemoTestUtils;
-import org.apache.doris.nereids.util.PlanChecker;
-import org.apache.doris.nereids.util.PlanConstructor;
-
-import org.junit.jupiter.api.Test;
-
-class HyperGraphJoinReorderGroupRightTest {
- private final LogicalOlapScan scan1 =
PlanConstructor.newLogicalOlapScan(0, "t1", 0);
- private final LogicalOlapScan scan2 =
PlanConstructor.newLogicalOlapScan(1, "t2", 0);
- private final LogicalOlapScan scan3 =
PlanConstructor.newLogicalOlapScan(2, "t3", 0);
- private final LogicalOlapScan scan4 =
PlanConstructor.newLogicalOlapScan(3, "t4", 0);
- private final LogicalOlapScan scan5 =
PlanConstructor.newLogicalOlapScan(4, "t5", 0);
-
- @Test
- void test() {
- LogicalPlan plan = new LogicalPlanBuilder(scan1)
- .hashJoinUsing(scan2, JoinType.INNER_JOIN, Pair.of(0, 1))
- .hashJoinUsing(scan3, JoinType.INNER_JOIN, Pair.of(0, 1))
- .hashJoinUsing(scan4, JoinType.INNER_JOIN, Pair.of(0, 1))
- .hashJoinUsing(scan5, JoinType.INNER_JOIN, Pair.of(0, 1))
- .build();
-
- PlanChecker.from(MemoTestUtils.createConnectContext(), plan)
- .deriveStats()
- .applyTopDown(new HyperGraphJoinReorderGroupRight())
- .printlnTree();
- }
-}
diff --git
a/fe/fe-core/src/test/java/org/apache/doris/nereids/rules/joinreorder/HyperGraphJoinReorderTest.java
b/fe/fe-core/src/test/java/org/apache/doris/nereids/rules/joinreorder/HyperGraphJoinReorderTest.java
deleted file mode 100644
index d707722014..0000000000
---
a/fe/fe-core/src/test/java/org/apache/doris/nereids/rules/joinreorder/HyperGraphJoinReorderTest.java
+++ /dev/null
@@ -1,56 +0,0 @@
-// 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.joinreorder;
-
-import org.apache.doris.common.Pair;
-import org.apache.doris.nereids.trees.plans.JoinType;
-import org.apache.doris.nereids.trees.plans.logical.LogicalOlapScan;
-import org.apache.doris.nereids.trees.plans.logical.LogicalPlan;
-import org.apache.doris.nereids.util.LogicalPlanBuilder;
-import org.apache.doris.nereids.util.MemoTestUtils;
-import org.apache.doris.nereids.util.PlanChecker;
-import org.apache.doris.nereids.util.PlanConstructor;
-
-import org.junit.jupiter.api.Test;
-
-class HyperGraphJoinReorderTest {
- private final LogicalOlapScan scan1 =
PlanConstructor.newLogicalOlapScan(0, "t1", 0);
- private final LogicalOlapScan scan2 =
PlanConstructor.newLogicalOlapScan(1, "t2", 0);
- private final LogicalOlapScan scan3 =
PlanConstructor.newLogicalOlapScan(2, "t3", 0);
- private final LogicalOlapScan scan4 =
PlanConstructor.newLogicalOlapScan(3, "t4", 0);
- private final LogicalOlapScan scan5 =
PlanConstructor.newLogicalOlapScan(4, "t5", 0);
-
- @Test
- void test() {
- LogicalPlan plan = new LogicalPlanBuilder(scan1)
- .hashJoinUsing(scan2, JoinType.INNER_JOIN, Pair.of(0, 1))
- .hashJoinUsing(scan3, JoinType.INNER_JOIN, Pair.of(0, 1))
- .hashJoinUsing(
- new LogicalPlanBuilder(scan4)
- .hashJoinUsing(scan5, JoinType.INNER_JOIN,
Pair.of(0, 1))
- .build(),
- JoinType.INNER_JOIN, Pair.of(0, 1)
- )
- .build();
-
- PlanChecker.from(MemoTestUtils.createConnectContext(), plan)
- .deriveStats()
- .applyTopDown(new HyperGraphJoinReorder())
- .printlnTree();
- }
-}
diff --git
a/fe/fe-core/src/test/java/org/apache/doris/nereids/util/HyperGraphBuilder.java
b/fe/fe-core/src/test/java/org/apache/doris/nereids/util/HyperGraphBuilder.java
index 65750c9140..66db0bd490 100644
---
a/fe/fe-core/src/test/java/org/apache/doris/nereids/util/HyperGraphBuilder.java
+++
b/fe/fe-core/src/test/java/org/apache/doris/nereids/util/HyperGraphBuilder.java
@@ -19,17 +19,13 @@ package org.apache.doris.nereids.util;
import org.apache.doris.common.Pair;
import org.apache.doris.nereids.CascadesContext;
-import org.apache.doris.nereids.pattern.GroupExpressionMatching;
-import org.apache.doris.nereids.rules.Rule;
-import org.apache.doris.nereids.rules.joinreorder.HyperGraphJoinReorder;
-import
org.apache.doris.nereids.rules.joinreorder.HyperGraphJoinReorderGroupLeft;
-import
org.apache.doris.nereids.rules.joinreorder.HyperGraphJoinReorderGroupRight;
-import org.apache.doris.nereids.rules.joinreorder.hypergraph.HyperGraph;
-import org.apache.doris.nereids.rules.joinreorder.hypergraph.bitmap.Bitmap;
-import org.apache.doris.nereids.stats.StatsCalculator;
+import org.apache.doris.nereids.jobs.cascades.DeriveStatsJob;
+import org.apache.doris.nereids.jobs.joinorder.JoinOrderJob;
+import org.apache.doris.nereids.jobs.joinorder.hypergraph.HyperGraph;
+import org.apache.doris.nereids.jobs.joinorder.hypergraph.bitmap.Bitmap;
+import org.apache.doris.nereids.memo.Group;
import org.apache.doris.nereids.trees.expressions.EqualTo;
import org.apache.doris.nereids.trees.expressions.Expression;
-import org.apache.doris.nereids.trees.plans.GroupPlan;
import org.apache.doris.nereids.trees.plans.JoinType;
import org.apache.doris.nereids.trees.plans.Plan;
import org.apache.doris.nereids.trees.plans.logical.LogicalJoin;
@@ -38,7 +34,6 @@ import
org.apache.doris.nereids.trees.plans.logical.LogicalPlan;
import org.apache.doris.statistics.StatsDeriveResult;
import com.google.common.base.Preconditions;
-import org.junit.jupiter.api.Assertions;
import java.util.ArrayList;
import java.util.BitSet;
@@ -54,9 +49,7 @@ public class HyperGraphBuilder {
public HyperGraph build() {
assert plans.size() == 1 : "there are cross join";
Plan plan = plans.values().iterator().next();
- Plan planWithStats = extractJoinCluster(plan);
- HyperGraph graph = HyperGraph.fromPlan(planWithStats);
- return graph;
+ return buildHyperGraph(plan);
}
public HyperGraph randomBuildWith(int tableNum, int edgeNum) {
@@ -168,49 +161,31 @@ public class HyperGraphBuilder {
return bitSet.equals(bitSet2);
}
- private Rule selectRuleForPlan(Plan plan) {
- Assertions.assertTrue(plan instanceof LogicalJoin);
- LogicalJoin join = (LogicalJoin) plan;
- if (!(join.left() instanceof LogicalJoin)) {
- return new HyperGraphJoinReorderGroupLeft().build();
- } else if (!(join.right() instanceof LogicalJoin)) {
- return new HyperGraphJoinReorderGroupRight().build();
- }
- return new HyperGraphJoinReorder().build();
- }
-
- private Plan extractJoinCluster(Plan plan) {
- Rule rule = selectRuleForPlan(plan);
+ private HyperGraph buildHyperGraph(Plan plan) {
CascadesContext cascadesContext =
MemoTestUtils.createCascadesContext(MemoTestUtils.createConnectContext(),
plan);
- GroupExpressionMatching groupExpressionMatching
- = new GroupExpressionMatching(rule.getPattern(),
- cascadesContext.getMemo().getRoot().getLogicalExpression());
- List<Plan> planList = new ArrayList<>();
- for (Plan matchingPlan : groupExpressionMatching) {
- planList.add(matchingPlan);
- }
- assert planList.size() == 1 : "Now we only support one join cluster";
- injectRowcount(planList.get(0));
- return planList.get(0);
+ JoinOrderJob joinOrderJob = new
JoinOrderJob(cascadesContext.getMemo().getRoot(),
+ cascadesContext.getCurrentJobContext());
+ cascadesContext.pushJob(
+ new
DeriveStatsJob(cascadesContext.getMemo().getRoot().getLogicalExpression(),
+ cascadesContext.getCurrentJobContext()));
+ cascadesContext.getJobScheduler().executeJobPool(cascadesContext);
+ injectRowcount(cascadesContext.getMemo().getRoot());
+ HyperGraph hyperGraph = new HyperGraph();
+ joinOrderJob.buildGraph(cascadesContext.getMemo().getRoot(),
hyperGraph);
+ return hyperGraph;
}
- private void injectRowcount(Plan plan) {
- if (plan instanceof GroupPlan) {
- GroupPlan olapGroupPlan = (GroupPlan) plan;
-
StatsCalculator.estimate(olapGroupPlan.getGroup().getLogicalExpression());
- LogicalOlapScan scanPlan = (LogicalOlapScan)
olapGroupPlan.getGroup().getLogicalExpression().getPlan();
- StatsDeriveResult stats = olapGroupPlan.getGroup().getStatistics();
- olapGroupPlan.getGroup()
- .setStatistics(stats
-
.updateRowCount(rowCounts.get(Integer.parseInt(scanPlan.getTable().getName()))));
+ private void injectRowcount(Group group) {
+ if (!group.isJoinGroup()) {
+ StatsDeriveResult stats = group.getStatistics();
+ LogicalOlapScan scanPlan = (LogicalOlapScan)
group.getLogicalExpression().getPlan();
+ int rowCount =
rowCounts.get(Integer.parseInt(scanPlan.getTable().getName()));
+ group.setStatistics(stats.updateRowCount(rowCount));
return;
}
- LogicalJoin join = (LogicalJoin) plan;
- injectRowcount(join.left());
- injectRowcount(join.right());
- // Because the children stats has been changed, so we need to
recalculate it
- StatsCalculator.estimate(join.getGroupExpression().get());
+ injectRowcount(group.getLogicalExpression().child(0));
+ injectRowcount(group.getLogicalExpression().child(1));
}
private void addCondition(int node1, int node2, BitSet key) {
diff --git
a/fe/fe-core/src/test/java/org/apache/doris/nereids/util/PlanChecker.java
b/fe/fe-core/src/test/java/org/apache/doris/nereids/util/PlanChecker.java
index d6b92578f6..a86ce9ed6c 100644
--- a/fe/fe-core/src/test/java/org/apache/doris/nereids/util/PlanChecker.java
+++ b/fe/fe-core/src/test/java/org/apache/doris/nereids/util/PlanChecker.java
@@ -24,6 +24,7 @@ import org.apache.doris.nereids.glue.LogicalPlanAdapter;
import org.apache.doris.nereids.jobs.JobContext;
import org.apache.doris.nereids.jobs.batch.NereidsRewriteJobExecutor;
import org.apache.doris.nereids.jobs.cascades.DeriveStatsJob;
+import org.apache.doris.nereids.jobs.joinorder.JoinOrderJob;
import org.apache.doris.nereids.memo.Group;
import org.apache.doris.nereids.memo.GroupExpression;
import org.apache.doris.nereids.memo.Memo;
@@ -71,6 +72,19 @@ public class PlanChecker {
this.cascadesContext = cascadesContext;
}
+ public static PlanChecker from(ConnectContext connectContext) {
+ return new PlanChecker(connectContext);
+ }
+
+ public static PlanChecker from(ConnectContext connectContext, Plan
initPlan) {
+ CascadesContext cascadesContext =
MemoTestUtils.createCascadesContext(connectContext, initPlan);
+ return new PlanChecker(cascadesContext);
+ }
+
+ public static PlanChecker from(CascadesContext cascadesContext) {
+ return new PlanChecker(cascadesContext);
+ }
+
public PlanChecker checkParse(String sql, Consumer<PlanParseChecker>
consumer) {
PlanParseChecker checker = new PlanParseChecker(sql);
consumer.accept(checker);
@@ -248,7 +262,15 @@ public class PlanChecker {
public PlanChecker deriveStats() {
cascadesContext.pushJob(
- new
DeriveStatsJob(cascadesContext.getMemo().getRoot().getLogicalExpression(),
cascadesContext.getCurrentJobContext()));
+ new
DeriveStatsJob(cascadesContext.getMemo().getRoot().getLogicalExpression(),
+ cascadesContext.getCurrentJobContext()));
+ cascadesContext.getJobScheduler().executeJobPool(cascadesContext);
+ return this;
+ }
+
+ public PlanChecker orderJoin() {
+ cascadesContext.pushJob(
+ new JoinOrderJob(cascadesContext.getMemo().getRoot(),
cascadesContext.getCurrentJobContext()));
cascadesContext.getJobScheduler().executeJobPool(cascadesContext);
return this;
}
@@ -348,19 +370,6 @@ public class PlanChecker {
});
}
- public static PlanChecker from(ConnectContext connectContext) {
- return new PlanChecker(connectContext);
- }
-
- public static PlanChecker from(ConnectContext connectContext, Plan
initPlan) {
- CascadesContext cascadesContext =
MemoTestUtils.createCascadesContext(connectContext, initPlan);
- return new PlanChecker(cascadesContext);
- }
-
- public static PlanChecker from(CascadesContext cascadesContext) {
- return new PlanChecker(cascadesContext);
- }
-
public CascadesContext getCascadesContext() {
return cascadesContext;
}
---------------------------------------------------------------------
To unsubscribe, e-mail: [email protected]
For additional commands, e-mail: [email protected]
