This is an automated email from the ASF dual-hosted git repository. hui pushed a commit to branch lmh/PathPatternTreeOpt in repository https://gitbox.apache.org/repos/asf/iotdb.git
commit dafb2b611a79d289a28339bd86b3dab200fa98ab Author: Minghui Liu <[email protected]> AuthorDate: Wed Jun 15 14:18:03 2022 +0800 refactor PathPatternTree structure --- .../db/mpp/common/schematree/PathPatternTree.java | 211 +++++++++++---------- .../db/mpp/plan/analyze/ClusterSchemaFetcher.java | 8 +- .../mpp/plan/analyze/StandaloneSchemaFetcher.java | 4 +- 3 files changed, 118 insertions(+), 105 deletions(-) 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 2fb3219d8c..b86f8c3f44 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 @@ -19,7 +19,6 @@ package org.apache.iotdb.db.mpp.common.schematree; -import org.apache.iotdb.commons.exception.IllegalPathException; import org.apache.iotdb.commons.path.PartialPath; import org.apache.iotdb.commons.utils.TestOnly; import org.apache.iotdb.db.qp.constant.SQLConstant; @@ -41,7 +40,7 @@ public class PathPatternTree { private PathPatternNode root; - private List<PartialPath> pathList; + @Deprecated private List<PartialPath> pathList; public PathPatternTree() { this.root = new PathPatternNode(SQLConstant.ROOT); @@ -56,59 +55,29 @@ public class PathPatternTree { this.root = root; } + ///////////////////////////////////////////////////////////////////////////////////////////////// + // Operations for time series paths + ///////////////////////////////////////////////////////////////////////////////////////////////// + + /** @param fullPath */ public void appendFullPath(PartialPath fullPath) { - searchAndConstruct(root, fullPath.getNodes(), 0); + appendBranchWithoutPrune(root, fullPath.getNodes(), 0); } + /** + * @param devicePath + * @param measurement + */ public void appendFullPath(PartialPath devicePath, String measurement) { int deviceNodeLength = devicePath.getNodeLength(); String[] pathNodes = new String[deviceNodeLength + 1]; System.arraycopy(devicePath.getNodes(), 0, pathNodes, 0, deviceNodeLength); pathNodes[deviceNodeLength] = measurement; - searchAndConstruct(root, pathNodes, 0); + appendBranchWithoutPrune(root, pathNodes, 0); } - /** @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); - } - - 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 + /** @param pathPattern */ public void appendPathPattern(PartialPath pathPattern) { boolean isExist = false; for (PartialPath path : pathList) { @@ -126,25 +95,16 @@ public class PathPatternTree { } } - public void appendPaths(PartialPath device, List<String> measurementNameList) { - try { - for (String measurementName : measurementNameList) { - appendPathPattern(new PartialPath(device.getFullPath(), measurementName)); - } - } catch (IllegalPathException e) { - e.printStackTrace(); - } - } - - // construct tree according to pathList + /** */ + @Deprecated public void constructTree() { for (PartialPath path : pathList) { - searchAndConstruct(root, path.getNodes(), 0); + appendBranchWithoutPrune(root, path.getNodes(), 0); } pathList.clear(); } - private void searchAndConstruct(PathPatternNode curNode, String[] pathNodes, int pos) { + private void appendBranchWithoutPrune(PathPatternNode curNode, String[] pathNodes, int pos) { if (pos == pathNodes.length - 1) { return; } @@ -152,13 +112,13 @@ public class PathPatternTree { PathPatternNode nextNode = curNode.getChildren(pathNodes[pos + 1]); if (nextNode != null) { - searchAndConstruct(nextNode, pathNodes, pos + 1); + appendBranchWithoutPrune(nextNode, pathNodes, pos + 1); } else { - appendTree(curNode, pathNodes, pos + 1); + constructBranch(curNode, pathNodes, pos + 1); } } - private void appendTree(PathPatternNode curNode, String[] pathNodes, int pos) { + private void constructBranch(PathPatternNode curNode, String[] pathNodes, int pos) { for (int i = pos; i < pathNodes.length; i++) { PathPatternNode newNode = new PathPatternNode(pathNodes[i]); curNode.addChild(newNode); @@ -166,44 +126,69 @@ public class PathPatternTree { } } - public void serialize(PublicBAOS outputStream) throws IOException { - constructTree(); - root.serialize(outputStream); + ///////////////////////////////////////////////////////////////////////////////////////////////// + // Operations for time series paths + ///////////////////////////////////////////////////////////////////////////////////////////////// + + public boolean isEmpty() { + return (root.getChildren() == null || root.getChildren().isEmpty()) + && (pathList == null || pathList.isEmpty()); } - public void serialize(DataOutputStream stream) throws IOException { - constructTree(); - root.serialize(stream); + /** @return */ + public List<String> findAllDevicePaths() { + List<String> nodes = new ArrayList<>(); + List<String> pathPatternList = new ArrayList<>(); + findAllDevicePaths(root, nodes, pathPatternList); + return pathPatternList; } - public void serialize(ByteBuffer buffer) { - constructTree(); - root.serialize(buffer); + /** @return */ + public List<PartialPath> splitToPathList() { + List<PartialPath> result = new ArrayList<>(); + Deque<String> ancestors = new ArrayDeque<>(); + searchFullPath(root, ancestors, result); + return result; } - public static PathPatternTree deserialize(ByteBuffer buffer) { - PathPatternNode root = deserializeNode(buffer); - PathPatternTree deserializedPatternTree = new PathPatternTree(); - deserializedPatternTree.setRoot(root); - return deserializedPatternTree; + /** @return */ + public PathPatternTree findOverlappedPattern(PartialPath pattern) { + PathPatternTree patternTree = new PathPatternTree(); + for (PartialPath pathPattern : findOverlappedPaths(pattern)) { + patternTree.appendPathPattern(pathPattern); + } + return patternTree; } - 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--; + 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; } - return node; + 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 List<PartialPath> splitToPathList() { - List<PartialPath> result = new ArrayList<>(); - Deque<String> ancestors = new ArrayDeque<>(); - searchFullPath(root, ancestors, result); - return result; + 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(); } private void searchFullPath( @@ -230,15 +215,7 @@ public class PathPatternTree { return new PartialPath(nodeList.toArray(new String[0])); } - public PathPatternTree findOverlappedPattern(PartialPath pattern) { - PathPatternTree patternTree = new PathPatternTree(); - for (PartialPath pathPattern : findOverlappedPaths(pattern)) { - patternTree.appendPathPattern(pathPattern); - } - return patternTree; - } - - public List<PartialPath> findOverlappedPaths(PartialPath pattern) { + private List<PartialPath> findOverlappedPaths(PartialPath pattern) { if (pathList.isEmpty()) { pathList = splitToPathList(); } @@ -252,6 +229,43 @@ public class PathPatternTree { return results; } + ///////////////////////////////////////////////////////////////////////////////////////////////// + // serialize & deserialize + ///////////////////////////////////////////////////////////////////////////////////////////////// + + public void serialize(PublicBAOS outputStream) throws IOException { + constructTree(); + root.serialize(outputStream); + } + + public void serialize(DataOutputStream stream) throws IOException { + constructTree(); + root.serialize(stream); + } + + public void serialize(ByteBuffer buffer) { + constructTree(); + root.serialize(buffer); + } + + public static PathPatternTree deserialize(ByteBuffer buffer) { + PathPatternNode root = deserializeNode(buffer); + PathPatternTree deserializedPatternTree = new PathPatternTree(); + deserializedPatternTree.setRoot(root); + return deserializedPatternTree; + } + + 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 public boolean equalWith(PathPatternTree that) { if (this == that) { @@ -262,9 +276,4 @@ public class PathPatternTree { } return this.getRoot().equalWith(that.getRoot()); } - - public boolean isEmpty() { - return (root.getChildren() == null || root.getChildren().isEmpty()) - && (pathList == null || pathList.isEmpty()); - } } diff --git a/server/src/main/java/org/apache/iotdb/db/mpp/plan/analyze/ClusterSchemaFetcher.java b/server/src/main/java/org/apache/iotdb/db/mpp/plan/analyze/ClusterSchemaFetcher.java index 431b820d7c..4309c7e8ae 100644 --- a/server/src/main/java/org/apache/iotdb/db/mpp/plan/analyze/ClusterSchemaFetcher.java +++ b/server/src/main/java/org/apache/iotdb/db/mpp/plan/analyze/ClusterSchemaFetcher.java @@ -187,14 +187,16 @@ public class ClusterSchemaFetcher implements ISchemaFetcher { PathPatternTree patternTree = new PathPatternTree(); for (int i = 0; i < devicePathList.size(); i++) { schemaTree.mergeSchemaTree(schemaCache.get(devicePathList.get(i), measurementsList.get(i))); - patternTree.appendPaths( - devicePathList.get(i), + List<String> missingMeasurements = checkMissingMeasurements( schemaTree, devicePathList.get(i), measurementsList.get(i), tsDataTypesList.get(i)) - .left); + .left; + for (String measurement : missingMeasurements) { + patternTree.appendFullPath(devicePathList.get(i), measurement); + } } if (patternTree.isEmpty()) { diff --git a/server/src/main/java/org/apache/iotdb/db/mpp/plan/analyze/StandaloneSchemaFetcher.java b/server/src/main/java/org/apache/iotdb/db/mpp/plan/analyze/StandaloneSchemaFetcher.java index ca361d5bf9..a83d25c484 100644 --- a/server/src/main/java/org/apache/iotdb/db/mpp/plan/analyze/StandaloneSchemaFetcher.java +++ b/server/src/main/java/org/apache/iotdb/db/mpp/plan/analyze/StandaloneSchemaFetcher.java @@ -153,7 +153,9 @@ public class StandaloneSchemaFetcher implements ISchemaFetcher { SchemaTree schemaTree = new SchemaTree(); PathPatternTree patternTree = new PathPatternTree(); for (int i = 0; i < devicePathList.size(); i++) { - patternTree.appendPaths(devicePathList.get(i), Arrays.asList(measurementsList.get(i))); + for (String measurement : measurementsList.get(i)) { + patternTree.appendFullPath(devicePathList.get(i), measurement); + } } if (patternTree.isEmpty()) {
