You are viewing a plain text version of this content. The canonical link for it is here.
Posted to commits@iotdb.apache.org by ja...@apache.org on 2022/04/12 00:46:26 UTC
[iotdb] branch master updated: Implement serialize and deserialize method for PathPatternTree (#5476)
This is an automated email from the ASF dual-hosted git repository.
jackietien pushed a commit to branch master
in repository https://gitbox.apache.org/repos/asf/iotdb.git
The following commit(s) were added to refs/heads/master by this push:
new e6e0d7407e Implement serialize and deserialize method for PathPatternTree (#5476)
e6e0d7407e is described below
commit e6e0d7407efe64c871f453c8d8c8f3f1dda0464d
Author: liuminghui233 <36...@users.noreply.github.com>
AuthorDate: Tue Apr 12 08:46:20 2022 +0800
Implement serialize and deserialize method for PathPatternTree (#5476)
---
.../db/mpp/common/schematree/PathPatternNode.java | 35 ++--
.../db/mpp/common/schematree/PathPatternTree.java | 85 +++++++--
.../iotdb/db/mpp/common/PathPatternTreeTest.java | 199 +++++++++++++--------
3 files changed, 210 insertions(+), 109 deletions(-)
diff --git a/server/src/main/java/org/apache/iotdb/db/mpp/common/schematree/PathPatternNode.java b/server/src/main/java/org/apache/iotdb/db/mpp/common/schematree/PathPatternNode.java
index 2a425ad40c..d780c52045 100644
--- a/server/src/main/java/org/apache/iotdb/db/mpp/common/schematree/PathPatternNode.java
+++ b/server/src/main/java/org/apache/iotdb/db/mpp/common/schematree/PathPatternNode.java
@@ -20,15 +20,18 @@
package org.apache.iotdb.db.mpp.common.schematree;
import org.apache.iotdb.commons.utils.TestOnly;
+import org.apache.iotdb.tsfile.utils.PublicBAOS;
+import org.apache.iotdb.tsfile.utils.ReadWriteIOUtils;
+import java.io.IOException;
import java.util.HashMap;
import java.util.Map;
import java.util.Objects;
public class PathPatternNode {
- private String name;
- private Map<String, PathPatternNode> children;
+ private final String name;
+ private final Map<String, PathPatternNode> children;
public PathPatternNode(String name) {
this.name = name;
@@ -39,10 +42,6 @@ public class PathPatternNode {
return name;
}
- public void setName(String name) {
- this.name = name;
- }
-
public PathPatternNode getChildren(String nodeName) {
return children.getOrDefault(nodeName, null);
}
@@ -51,18 +50,18 @@ public class PathPatternNode {
return children;
}
- public void setChildren(Map<String, PathPatternNode> children) {
- this.children = children;
- }
-
- public void addChild(String nodeName, PathPatternNode newNode) {
- this.children.put(nodeName, newNode);
+ public void addChild(PathPatternNode tmpNode) {
+ children.put(tmpNode.getName(), tmpNode);
}
public boolean isLeaf() {
return children.isEmpty();
}
+ public boolean isWildcard() {
+ return name.equals("*") || name.equals("**");
+ }
+
@TestOnly
public boolean equalWith(PathPatternNode that) {
if (this == that) {
@@ -89,4 +88,16 @@ public class PathPatternNode {
}
return true;
}
+
+ public void serialize(PublicBAOS outputStream) throws IOException {
+ ReadWriteIOUtils.write(name, outputStream);
+ ReadWriteIOUtils.write(children.size(), outputStream);
+ serializeChildren(outputStream);
+ }
+
+ void serializeChildren(PublicBAOS outputStream) throws IOException {
+ for (PathPatternNode childNode : children.values()) {
+ childNode.serialize(outputStream);
+ }
+ }
}
diff --git a/server/src/main/java/org/apache/iotdb/db/mpp/common/schematree/PathPatternTree.java b/server/src/main/java/org/apache/iotdb/db/mpp/common/schematree/PathPatternTree.java
index 6f6b281c6b..96f0428fc6 100644
--- a/server/src/main/java/org/apache/iotdb/db/mpp/common/schematree/PathPatternTree.java
+++ b/server/src/main/java/org/apache/iotdb/db/mpp/common/schematree/PathPatternTree.java
@@ -23,10 +23,14 @@ import org.apache.iotdb.commons.utils.TestOnly;
import org.apache.iotdb.db.exception.metadata.IllegalPathException;
import org.apache.iotdb.db.metadata.path.PartialPath;
import org.apache.iotdb.db.qp.constant.SQLConstant;
+import org.apache.iotdb.tsfile.common.constant.TsFileConstant;
+import org.apache.iotdb.tsfile.utils.PublicBAOS;
+import org.apache.iotdb.tsfile.utils.ReadWriteIOUtils;
import java.io.IOException;
import java.nio.ByteBuffer;
import java.util.ArrayList;
+import java.util.Arrays;
import java.util.List;
import java.util.Map;
import java.util.stream.Collectors;
@@ -35,25 +39,25 @@ public class PathPatternTree {
private PathPatternNode root;
- private final List<PartialPath> pathList;
+ private List<PartialPath> pathList;
- /**
- * Since IoTDB v0.13, all DDL and DML use patternMatch as default. Before IoTDB v0.13, all DDL and
- * DML use prefixMatch.
- */
- protected boolean isPrefixMatchPath;
+ public PathPatternTree(PathPatternNode root) {
+ this.root = root;
+ }
public PathPatternTree(PartialPath deivcePath, String[] measurements) {
- // TODO
this.root = new PathPatternNode(SQLConstant.ROOT);
this.pathList = new ArrayList<>();
+ appendPaths(deivcePath, Arrays.asList(measurements));
}
- public PathPatternTree(Map<PartialPath, List<String>> devices) {
- // TODO
+ public PathPatternTree(Map<PartialPath, List<String>> deviceToMeasurementsMap) {
this.root = new PathPatternNode(SQLConstant.ROOT);
this.pathList = new ArrayList<>();
- };
+ for (Map.Entry<PartialPath, List<String>> entry : deviceToMeasurementsMap.entrySet()) {
+ appendPaths(entry.getKey(), entry.getValue());
+ }
+ }
public PathPatternTree() {
this.root = new PathPatternNode(SQLConstant.ROOT);
@@ -68,12 +72,43 @@ public class PathPatternTree {
this.root = root;
}
- public boolean isPrefixMatchPath() {
- return isPrefixMatchPath;
+ /** @return all device path patterns in the path pattern tree. */
+ public List<String> findAllDevicePaths() {
+ List<String> nodes = new ArrayList<>();
+ List<String> pathPatternList = new ArrayList<>();
+ findAllDevicePaths(root, nodes, pathPatternList);
+ return pathPatternList;
+ }
+
+ private void findAllDevicePaths(
+ PathPatternNode curNode, List<String> nodes, List<String> pathPatternList) {
+ nodes.add(curNode.getName());
+ if (curNode.isLeaf()) {
+ if (!curNode.getName().equals("**")) {
+ pathPatternList.add(parseNodesToString(nodes.subList(0, nodes.size() - 1)));
+ } else {
+ pathPatternList.add(parseNodesToString(nodes));
+ }
+ nodes.remove(nodes.size() - 1);
+ return;
+ }
+ if (curNode.isWildcard()) {
+ pathPatternList.add(parseNodesToString(nodes));
+ nodes.remove(nodes.size() - 1);
+ return;
+ }
+ for (PathPatternNode childNode : curNode.getChildren().values()) {
+ findAllDevicePaths(childNode, nodes, pathPatternList);
+ }
+ nodes.remove(nodes.size() - 1);
}
- public void setPrefixMatchPath(boolean prefixMatchPath) {
- isPrefixMatchPath = prefixMatchPath;
+ private String parseNodesToString(List<String> nodes) {
+ StringBuilder fullPathBuilder = new StringBuilder(nodes.get(0));
+ for (int i = 1; i < nodes.size(); i++) {
+ fullPathBuilder.append(TsFileConstant.PATH_SEPARATOR).append(nodes.get(i));
+ }
+ return fullPathBuilder.toString();
}
// append path to pathList
@@ -129,18 +164,30 @@ public class PathPatternTree {
private void appendTree(PathPatternNode curNode, String[] pathNodes, int pos) {
for (int i = pos; i < pathNodes.length; i++) {
PathPatternNode newNode = new PathPatternNode(pathNodes[i]);
- curNode.addChild(newNode.getName(), newNode);
+ curNode.addChild(newNode);
curNode = newNode;
}
}
- public void serialize(ByteBuffer buffer) throws IOException {
+ public void serialize(PublicBAOS outputStream) throws IOException {
constructTree();
- // TODO
+ root.serialize(outputStream);
+ }
+
+ public static PathPatternTree deserialize(ByteBuffer buffer) {
+ PathPatternNode root = deserializeNode(buffer);
+ return new PathPatternTree(root);
}
- public void deserialize(ByteBuffer buffer) throws IOException {
- // TODO
+ private static PathPatternNode deserializeNode(ByteBuffer buffer) {
+ PathPatternNode node = new PathPatternNode(ReadWriteIOUtils.readString(buffer));
+ int childrenSize = ReadWriteIOUtils.readInt(buffer);
+ while (childrenSize > 0) {
+ PathPatternNode tmpNode = deserializeNode(buffer);
+ node.addChild(tmpNode);
+ childrenSize--;
+ }
+ return node;
}
@TestOnly
diff --git a/server/src/test/java/org/apache/iotdb/db/mpp/common/PathPatternTreeTest.java b/server/src/test/java/org/apache/iotdb/db/mpp/common/PathPatternTreeTest.java
index 30c0d82215..3d2d9e83c2 100644
--- a/server/src/test/java/org/apache/iotdb/db/mpp/common/PathPatternTreeTest.java
+++ b/server/src/test/java/org/apache/iotdb/db/mpp/common/PathPatternTreeTest.java
@@ -22,110 +22,153 @@ package org.apache.iotdb.db.mpp.common;
import org.apache.iotdb.db.exception.metadata.IllegalPathException;
import org.apache.iotdb.db.metadata.path.PartialPath;
import org.apache.iotdb.db.mpp.common.schematree.PathPatternTree;
+import org.apache.iotdb.tsfile.utils.PublicBAOS;
import org.junit.Assert;
import org.junit.Test;
+import java.io.IOException;
+import java.nio.ByteBuffer;
+import java.util.Arrays;
+import java.util.Collections;
+import java.util.List;
+import java.util.stream.Collectors;
+
public class PathPatternTreeTest {
@Test
- public void pathPatternTreeTest1() throws IllegalPathException {
- PathPatternTree patternTree = new PathPatternTree();
- patternTree.appendPath(new PartialPath("root.sg1.d1.s1"));
- patternTree.appendPath(new PartialPath("root.sg1.d1.s2"));
- patternTree.appendPath(new PartialPath("root.sg1.d1.*"));
- patternTree.appendPath(new PartialPath("root.sg1.d1.s3"));
- patternTree.constructTree();
-
- PathPatternTree resultPatternTree = new PathPatternTree();
- resultPatternTree.appendPath(new PartialPath("root.sg1.d1.*"));
- resultPatternTree.constructTree();
-
- Assert.assertTrue(resultPatternTree.equalWith(patternTree));
+ public void pathPatternTreeTest1() throws IllegalPathException, IOException {
+ checkPathPatternTree(
+ Arrays.asList(
+ new PartialPath("root.sg1.d1.s1"),
+ new PartialPath("root.sg1.d1.s2"),
+ new PartialPath("root.sg1.d1.*"),
+ new PartialPath("root.sg1.d1.s3")),
+ Collections.singletonList(new PartialPath("root.sg1.d1.*")),
+ Collections.singletonList(new PartialPath("root.sg1.d1")));
}
@Test
- public void pathPatternTreeTest2() throws IllegalPathException {
- PathPatternTree patternTree = new PathPatternTree();
- patternTree.appendPath(new PartialPath("root.sg1.d1.s1"));
- patternTree.appendPath(new PartialPath("root.sg1.d1.s2"));
- patternTree.appendPath(new PartialPath("root.sg1.d1.t1.s1"));
- patternTree.appendPath(new PartialPath("root.sg1.*.s1"));
- patternTree.appendPath(new PartialPath("root.sg1.d2.s1"));
- patternTree.constructTree();
-
- PathPatternTree resultPatternTree = new PathPatternTree();
- resultPatternTree.appendPath(new PartialPath("root.sg1.d1.s2"));
- resultPatternTree.appendPath(new PartialPath("root.sg1.d1.t1.s1"));
- resultPatternTree.appendPath(new PartialPath("root.sg1.*.s1"));
- resultPatternTree.constructTree();
-
- Assert.assertTrue(resultPatternTree.equalWith(patternTree));
+ public void pathPatternTreeTest2() throws IllegalPathException, IOException {
+ checkPathPatternTree(
+ Arrays.asList(
+ new PartialPath("root.sg1.d1.t1.s1"),
+ new PartialPath("root.sg1.d1.t2.s2"),
+ new PartialPath("root.sg1.*.t1.s1"),
+ new PartialPath("root.sg1.d2.t1.s1")),
+ Arrays.asList(new PartialPath("root.sg1.d1.t2.s2"), new PartialPath("root.sg1.*.t1.s1")),
+ Arrays.asList(new PartialPath("root.sg1.d1.t2"), new PartialPath("root.sg1.*")));
}
@Test
- public void pathPatternTreeTest3() throws IllegalPathException {
- PathPatternTree patternTree = new PathPatternTree();
- patternTree.appendPath(new PartialPath("root.sg1.d1.s1"));
- patternTree.appendPath(new PartialPath("root.sg1.d1.s2"));
- patternTree.appendPath(new PartialPath("root.sg1.d1.t1.s1"));
- patternTree.appendPath(new PartialPath("root.sg1.d2.s3"));
- patternTree.appendPath(new PartialPath("root.**"));
- patternTree.appendPath(new PartialPath("root.sg1.d1.s1"));
- patternTree.appendPath(new PartialPath("root.sg1.d1.s2"));
- patternTree.appendPath(new PartialPath("root.sg1.d1.t1.s1"));
- patternTree.appendPath(new PartialPath("root.sg1.d2.s3"));
- patternTree.constructTree();
-
- PathPatternTree resultPatternTree = new PathPatternTree();
- resultPatternTree.appendPath(new PartialPath("root.**"));
- resultPatternTree.constructTree();
-
- Assert.assertTrue(resultPatternTree.equalWith(patternTree));
+ public void pathPatternTreeTest3() throws IllegalPathException, IOException {
+ checkPathPatternTree(
+ Arrays.asList(
+ new PartialPath("root.sg1.d1.s1"),
+ new PartialPath("root.sg1.d1.s2"),
+ new PartialPath("root.sg1.d1.t1.s1"),
+ new PartialPath("root.sg1.*.s1"),
+ new PartialPath("root.sg1.d2.s1")),
+ Arrays.asList(
+ new PartialPath("root.sg1.d1.s2"),
+ new PartialPath("root.sg1.d1.t1.s1"),
+ new PartialPath("root.sg1.*.s1")),
+ Arrays.asList(
+ new PartialPath("root.sg1.d1"),
+ new PartialPath("root.sg1.d1.t1"),
+ new PartialPath("root.sg1.*")));
}
@Test
- public void pathPatternTreeTest4() throws IllegalPathException {
- PathPatternTree patternTree = new PathPatternTree();
- patternTree.appendPath(new PartialPath("root.sg1.d1.s1"));
- patternTree.appendPath(new PartialPath("root.sg1.d1.s2"));
- patternTree.appendPath(new PartialPath("root.sg1.d1.t1.s1"));
- patternTree.appendPath(new PartialPath("root.sg1.d2.s1"));
- patternTree.appendPath(new PartialPath("root.sg1.**.s1"));
- patternTree.constructTree();
-
- PathPatternTree resultPatternTree = new PathPatternTree();
- resultPatternTree.appendPath(new PartialPath("root.sg1.d1.s2"));
- resultPatternTree.appendPath(new PartialPath("root.sg1.**.s1"));
- resultPatternTree.constructTree();
+ public void pathPatternTreeTest4() throws IllegalPathException, IOException {
+ checkPathPatternTree(
+ Arrays.asList(
+ new PartialPath("root.sg1.d1.s1"),
+ new PartialPath("root.sg1.d1.s2"),
+ new PartialPath("root.sg1.d1.t1.s1"),
+ new PartialPath("root.sg1.d2.s3"),
+ new PartialPath("root.**"),
+ new PartialPath("root.sg1.d1.s1"),
+ new PartialPath("root.sg1.d1.s2"),
+ new PartialPath("root.sg1.d1.t1.s1"),
+ new PartialPath("root.sg1.d2.s3")),
+ Collections.singletonList(new PartialPath("root.**")),
+ Collections.singletonList(new PartialPath("root.**")));
+ }
- Assert.assertTrue(resultPatternTree.equalWith(patternTree));
+ @Test
+ public void pathPatternTreeTest5() throws IllegalPathException, IOException {
+ checkPathPatternTree(
+ Arrays.asList(
+ new PartialPath("root.sg1.d1.s1"),
+ new PartialPath("root.sg1.d1.s2"),
+ new PartialPath("root.sg1.d1.t1.s1"),
+ new PartialPath("root.sg1.d2.s1"),
+ new PartialPath("root.sg1.**.s1")),
+ Arrays.asList(new PartialPath("root.sg1.d1.s2"), new PartialPath("root.sg1.**.s1")),
+ Arrays.asList(new PartialPath("root.sg1.d1"), new PartialPath("root.sg1.**")));
}
@Test
- public void pathPatternTreeTest5() throws IllegalPathException {
+ public void pathPatternTreeTest6() throws IllegalPathException, IOException {
+ checkPathPatternTree(
+ Arrays.asList(
+ new PartialPath("root.sg1.d1.s1"),
+ new PartialPath("root.sg1.d1.s2"),
+ new PartialPath("root.sg1.d1.t1.s1"),
+ new PartialPath("root.sg1.d2.s1"),
+ new PartialPath("root.sg1.d2.s2"),
+ new PartialPath("root.sg1.d2.*"),
+ new PartialPath("root.sg1.**.s1"),
+ new PartialPath("root.sg1.*.s2"),
+ new PartialPath("root.sg1.d3.s1"),
+ new PartialPath("root.sg1.d3.s2"),
+ new PartialPath("root.sg1.d3.t1.s1"),
+ new PartialPath("root.sg1.d3.t1.s2")),
+ Arrays.asList(
+ new PartialPath("root.sg1.d2.*"),
+ new PartialPath("root.sg1.**.s1"),
+ new PartialPath("root.sg1.*.s2"),
+ new PartialPath("root.sg1.d3.t1.s2")),
+ Arrays.asList(
+ new PartialPath("root.sg1.d2"),
+ new PartialPath("root.sg1.**"),
+ new PartialPath("root.sg1.*"),
+ new PartialPath("root.sg1.d3.t1")));
+ }
+
+ public void checkPathPatternTree(
+ List<PartialPath> paths,
+ List<PartialPath> compressedPaths,
+ List<PartialPath> compressedDevicePaths)
+ throws IOException {
PathPatternTree patternTree = new PathPatternTree();
- patternTree.appendPath(new PartialPath("root.sg1.d1.s1"));
- patternTree.appendPath(new PartialPath("root.sg1.d1.s2"));
- patternTree.appendPath(new PartialPath("root.sg1.d1.t1.s1"));
- patternTree.appendPath(new PartialPath("root.sg1.d2.s1"));
- patternTree.appendPath(new PartialPath("root.sg1.d2.s2"));
- patternTree.appendPath(new PartialPath("root.sg1.d2.*"));
- patternTree.appendPath(new PartialPath("root.sg1.**.s1"));
- patternTree.appendPath(new PartialPath("root.sg1.*.s2"));
- patternTree.appendPath(new PartialPath("root.sg1.d3.s1"));
- patternTree.appendPath(new PartialPath("root.sg1.d3.s2"));
- patternTree.appendPath(new PartialPath("root.sg1.d3.t1.s1"));
- patternTree.appendPath(new PartialPath("root.sg1.d3.t1.s2"));
+ for (PartialPath path : paths) {
+ patternTree.appendPath(path);
+ }
patternTree.constructTree();
PathPatternTree resultPatternTree = new PathPatternTree();
- resultPatternTree.appendPath(new PartialPath("root.sg1.d2.*"));
- resultPatternTree.appendPath(new PartialPath("root.sg1.**.s1"));
- resultPatternTree.appendPath(new PartialPath("root.sg1.*.s2"));
- resultPatternTree.appendPath(new PartialPath("root.sg1.d3.t1.s2"));
+ for (PartialPath path : compressedPaths) {
+ resultPatternTree.appendPath(path);
+ }
resultPatternTree.constructTree();
Assert.assertTrue(resultPatternTree.equalWith(patternTree));
+
+ Assert.assertEquals(
+ compressedDevicePaths.stream()
+ .map(PartialPath::getFullPath)
+ .sorted()
+ .collect(Collectors.toList()),
+ patternTree.findAllDevicePaths().stream().sorted().collect(Collectors.toList()));
+
+ PublicBAOS outputStream = new PublicBAOS();
+ resultPatternTree.serialize(outputStream);
+ ByteBuffer buffer = ByteBuffer.allocate(outputStream.size() * 8);
+ buffer.put(outputStream.getBuf());
+ buffer.flip();
+ PathPatternTree tmpPathPatternTree = PathPatternTree.deserialize(buffer);
+ Assert.assertTrue(resultPatternTree.equalWith(tmpPathPatternTree));
}
}