You are viewing a plain text version of this content. The canonical link for it is here.
Posted to commits@doris.apache.org by ja...@apache.org on 2022/10/28 09:23:42 UTC
[doris] branch master updated: feat(nereids): draw hyper graph by graphviz (#13749)
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 2a5d3dbb6e feat(nereids): draw hyper graph by graphviz (#13749)
2a5d3dbb6e is described below
commit 2a5d3dbb6e4de88032cab961363e42928fb39a93
Author: 谢健 <ji...@gmail.com>
AuthorDate: Fri Oct 28 17:23:35 2022 +0800
feat(nereids): draw hyper graph by graphviz (#13749)
---
.../rules/exploration/join/hypergraph/Edge.java | 9 +++
.../exploration/join/hypergraph/HyperGraph.java | 71 ++++++++++++++++------
.../join/hypergraph/HyperGraphTest.java | 59 ++++++++++++++++++
3 files changed, 119 insertions(+), 20 deletions(-)
diff --git a/fe/fe-core/src/main/java/org/apache/doris/nereids/rules/exploration/join/hypergraph/Edge.java b/fe/fe-core/src/main/java/org/apache/doris/nereids/rules/exploration/join/hypergraph/Edge.java
index f222dd1917..79bb97d84c 100644
--- a/fe/fe-core/src/main/java/org/apache/doris/nereids/rules/exploration/join/hypergraph/Edge.java
+++ b/fe/fe-core/src/main/java/org/apache/doris/nereids/rules/exploration/join/hypergraph/Edge.java
@@ -30,6 +30,7 @@ class Edge {
BitSet left = new BitSet(32);
BitSet right = new BitSet(32);
BitSet constraints = new BitSet(32);
+ double selectivity = 1;
/**
* Create simple edge.
@@ -39,6 +40,14 @@ class Edge {
this.join = join;
}
+ public LogicalJoin getJoin() {
+ return join;
+ }
+
+ public double getSelectivity() {
+ return selectivity;
+ }
+
public boolean isSimple() {
return left.cardinality() == 1 && right.cardinality() == 1;
}
diff --git a/fe/fe-core/src/main/java/org/apache/doris/nereids/rules/exploration/join/hypergraph/HyperGraph.java b/fe/fe-core/src/main/java/org/apache/doris/nereids/rules/exploration/join/hypergraph/HyperGraph.java
index 0ae1f85fc4..1fe62df17c 100644
--- a/fe/fe-core/src/main/java/org/apache/doris/nereids/rules/exploration/join/hypergraph/HyperGraph.java
+++ b/fe/fe-core/src/main/java/org/apache/doris/nereids/rules/exploration/join/hypergraph/HyperGraph.java
@@ -34,8 +34,8 @@ import java.util.Set;
* It's used for join ordering
*/
public class HyperGraph {
- List<Edge> edges;
- List<Node> nodes;
+ List<Edge> edges = new ArrayList<>();
+ List<Node> nodes = new ArrayList<>();
// TODO: add system arg: limit
Receiver receiver = new Receiver(100);
@@ -111,34 +111,65 @@ public class HyperGraph {
}
/**
- 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
- to render this it a graphical representation of the hyperGraph for
- easier debugging, e.g. like this:
-
- dot -Tps graph.dot > graph.ps
- display graph.ps
+ * 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
+ * to render this it a graphical representation of the hyperGraph for
+ * easier debugging, e.g. like this:
+ * <p>
+ * dot -Tps graph.dot > graph.ps
+ * display graph.ps
*/
public String toDottyHyperGraph() {
- // TODO: finish it
StringBuilder builder = new StringBuilder();
builder.append(String.format("digraph G { # %d edges\n", edges.size() / 2));
- List<String> names = new ArrayList<>();
+ List<String> graphvisNodes = new ArrayList<>();
for (Node node : nodes) {
- String name = node.plan.getType().name();
- while (names.contains(name)) {
- name += "_";
- }
- if (!name.equals(node.plan.getType().name())) {
- builder.append(String.format(" %s [label=\"%s\"];\n", name, node.plan.getType().name()));
+ String nodeName = node.plan.getType().name() + node.index;
+ // nodeID is used to identify the node with the same name
+ String nodeID = nodeName;
+ while (graphvisNodes.contains(nodeID)) {
+ nodeID += "_";
}
- names.add(name);
+ builder.append(String.format(" %s [label=\"%s\"];\n", nodeID, nodeName));
+ graphvisNodes.add(nodeName);
}
for (int i = 0; i < edges.size(); i += 2) {
+ Edge edge = edges.get(i);
+ String label = String.valueOf(edge.getSelectivity());
if (edges.get(i).isSimple()) {
- // TODO
+ String arrowHead = "";
+ if (edge.getJoin().getJoinType() == JoinType.INNER_JOIN) {
+ arrowHead = ",arrowhead=none";
+ }
+
+ int leftIndex = edge.getLeft().nextSetBit(0);
+ int rightIndex = edge.getRight().nextSetBit(0);
+ builder.append(String.format("%s -> %s [label=\"%s\"%s]\n", graphvisNodes.get(leftIndex),
+ graphvisNodes.get(rightIndex), label, arrowHead));
} else {
- // TODO
+ // Hyper edge is considered as a tiny virtual node
+ builder.append(String.format("e%d [shape=circle, width=.001, label=\"\"\n", i));
+
+ String leftLabel = "";
+ String rightLabel = "";
+ if (edge.getLeft().cardinality() == 1) {
+ rightLabel = label;
+ } else {
+ leftLabel = label;
+ }
+
+ int finalI = i;
+ String finalLeftLabel = leftLabel;
+ edge.getLeft().stream().forEach(nodeIndex -> {
+ builder.append(String.format("%s -> e%d [arrowhead=none, label=\"%s\"]\n",
+ graphvisNodes.get(nodeIndex), finalI, finalLeftLabel));
+ });
+
+ String finalRightLabel = rightLabel;
+ edge.getRight().stream().forEach(nodeIndex -> {
+ builder.append(String.format("%s -> e%d [arrowhead=none, label=\"%s\"]\n",
+ graphvisNodes.get(nodeIndex), finalI, finalRightLabel));
+ });
}
}
builder.append("}\n");
diff --git a/fe/fe-core/src/test/java/org/apache/doris/nereids/rules/exploration/join/hypergraph/HyperGraphTest.java b/fe/fe-core/src/test/java/org/apache/doris/nereids/rules/exploration/join/hypergraph/HyperGraphTest.java
new file mode 100644
index 0000000000..da2a4efec5
--- /dev/null
+++ b/fe/fe-core/src/test/java/org/apache/doris/nereids/rules/exploration/join/hypergraph/HyperGraphTest.java
@@ -0,0 +1,59 @@
+// 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.join.hypergraph;
+
+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.PlanConstructor;
+
+import org.junit.jupiter.api.Test;
+
+public class HyperGraphTest {
+ 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 testDottyHyperGraph() {
+ LogicalPlan joinCluster = new LogicalPlanBuilder(scan1)
+ .hashJoinUsing(scan2, JoinType.INNER_JOIN, Pair.of(0, 0))
+ .hashJoinUsing(scan3, JoinType.INNER_JOIN, Pair.of(0, 0))
+ .hashJoinUsing(scan4, JoinType.INNER_JOIN, Pair.of(0, 0))
+ .hashJoinUsing(scan5, JoinType.INNER_JOIN, Pair.of(0, 0))
+ .build();
+ HyperGraph hyperGraph = HyperGraph.fromPlan(joinCluster);
+ String dottyGraph = hyperGraph.toDottyHyperGraph();
+ // This is a star join, which can be transformed to a image by graphviz.
+ assert dottyGraph.equals("digraph G { # 4 edges\n"
+ + " LOGICAL_OLAP_SCAN0 [label=\"LOGICAL_OLAP_SCAN0\"];\n"
+ + " LOGICAL_OLAP_SCAN1 [label=\"LOGICAL_OLAP_SCAN1\"];\n"
+ + " LOGICAL_OLAP_SCAN2 [label=\"LOGICAL_OLAP_SCAN2\"];\n"
+ + " LOGICAL_OLAP_SCAN3 [label=\"LOGICAL_OLAP_SCAN3\"];\n"
+ + " LOGICAL_OLAP_SCAN4 [label=\"LOGICAL_OLAP_SCAN4\"];\n"
+ + "LOGICAL_OLAP_SCAN0 -> LOGICAL_OLAP_SCAN1 [label=\"1.0\",arrowhead=none]\n"
+ + "LOGICAL_OLAP_SCAN0 -> LOGICAL_OLAP_SCAN2 [label=\"1.0\",arrowhead=none]\n"
+ + "LOGICAL_OLAP_SCAN0 -> LOGICAL_OLAP_SCAN3 [label=\"1.0\",arrowhead=none]\n"
+ + "LOGICAL_OLAP_SCAN0 -> LOGICAL_OLAP_SCAN4 [label=\"1.0\",arrowhead=none]\n"
+ + "}\n") : dottyGraph;
+ }
+}
---------------------------------------------------------------------
To unsubscribe, e-mail: commits-unsubscribe@doris.apache.org
For additional commands, e-mail: commits-help@doris.apache.org