This is an automated email from the ASF dual-hosted git repository.
zyk 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 641e2b9e4d [IOTDB-4356] De-duplication of PathPatternTree (#7289)
641e2b9e4d is described below
commit 641e2b9e4ddf580f3082eee0d0a8b36fb83e3d81
Author: Chen YZ <[email protected]>
AuthorDate: Tue Sep 13 14:06:42 2022 +0800
[IOTDB-4356] De-duplication of PathPatternTree (#7289)
[IOTDB-4356] De-duplication of PathPatternTree #7289
---
.../org/apache/iotdb/commons/path/PartialPath.java | 58 ++++++++++++++++++++++
.../apache/iotdb/commons/path/PartialPathTest.java | 43 ++++++++++++++++
.../db/mpp/common/schematree/PathPatternTree.java | 12 +++--
.../mpp/common/schematree/PathPatternTreeTest.java | 33 ++++++++++++
4 files changed, 141 insertions(+), 5 deletions(-)
diff --git
a/node-commons/src/main/java/org/apache/iotdb/commons/path/PartialPath.java
b/node-commons/src/main/java/org/apache/iotdb/commons/path/PartialPath.java
index bec99ab45f..d3cae160db 100644
--- a/node-commons/src/main/java/org/apache/iotdb/commons/path/PartialPath.java
+++ b/node-commons/src/main/java/org/apache/iotdb/commons/path/PartialPath.java
@@ -356,6 +356,64 @@ public class PartialPath extends Path implements
Comparable<Path>, Cloneable {
return true;
}
+ /**
+ * Test if this path pattern includes input path pattern. e.g. "root.**"
includes "root.sg.**",
+ * "root.*.d.s" includes "root.sg.d.s", "root.sg.**" does not include
"root.**.s", "root.*.d.s"
+ * does not include "root.sg.d1.*"
+ *
+ * @param rPath a pattern path of a timeseries
+ * @return true if this path pattern includes input path pattern, otherwise
return false
+ */
+ public boolean include(PartialPath rPath) {
+ String[] rNodes = rPath.getNodes();
+ String[] lNodes = nodes.clone();
+ // Replace * with ** if they are adjacent to each other
+ for (int i = 1; i < lNodes.length; i++) {
+ if (MULTI_LEVEL_PATH_WILDCARD.equals(lNodes[i - 1])
+ && ONE_LEVEL_PATH_WILDCARD.equals(lNodes[i])) {
+ lNodes[i] = MULTI_LEVEL_PATH_WILDCARD;
+ }
+ if (MULTI_LEVEL_PATH_WILDCARD.equals(lNodes[lNodes.length - i])
+ && ONE_LEVEL_PATH_WILDCARD.equals(lNodes[lNodes.length - 1 - i])) {
+ lNodes[lNodes.length - 1 - i] = MULTI_LEVEL_PATH_WILDCARD;
+ }
+ }
+ // dp[i][j] means if nodes1[0:i) includes nodes[0:j)
+ // for example: "root.sg.**" includes "root.sg.d1.*"
+ // 1 0 0 0 0 |→| 1 0 0 0 0 |→| 1 0 0 0 0 |→| 1 0 0 0 0
+ // 0 0 0 0 0 |↓| 0 1 0 0 0 |→| 0 1 0 0 0 |→| 0 1 0 0 0
+ // 0 0 0 0 0 |↓| 0 0 0 0 0 |↓| 0 0 1 0 0 |→| 0 0 1 0 0
+ // 0 0 0 0 0 |↓| 0 0 0 0 0 |↓| 0 0 0 0 0 |↓| 0 0 0 1 1
+ // Since the derivation of the next row depends only on the previous row,
the calculation can
+ // be performed using a one-dimensional array
+ boolean[] dp = new boolean[rNodes.length + 1];
+ dp[0] = true;
+ for (int i = 1; i <= lNodes.length; i++) {
+ boolean[] newDp = new boolean[rNodes.length + 1];
+ for (int j = i; j <= rNodes.length; j++) {
+ if (lNodes[i - 1].equals(MULTI_LEVEL_PATH_WILDCARD)) {
+ // if encounter MULTI_LEVEL_PATH_WILDCARD
+ if (dp[j - 1]) {
+ for (int k = j; k <= rNodes.length; k++) {
+ newDp[k] = true;
+ }
+ break;
+ }
+ } else {
+ // if without MULTI_LEVEL_PATH_WILDCARD, scan and check
+ if (!rNodes[j - 1].equals(MULTI_LEVEL_PATH_WILDCARD)
+ && (lNodes[i - 1].equals(ONE_LEVEL_PATH_WILDCARD)
+ || lNodes[i - 1].equals(rNodes[j - 1]))) {
+ // if nodes1[i-1] includes rNodes[j-1], dp[i][j] = dp[i-1][j-1]
+ newDp[j] |= dp[j - 1];
+ }
+ }
+ }
+ dp = newDp;
+ }
+ return dp[rNodes.length];
+ }
+
/**
* Test if this path pattern overlaps with input path pattern. Overlap means
the result sets
* generated by two path pattern share some common elements. e.g.
"root.sg.**" overlaps with
diff --git
a/node-commons/src/test/java/org/apache/iotdb/commons/path/PartialPathTest.java
b/node-commons/src/test/java/org/apache/iotdb/commons/path/PartialPathTest.java
index 273e7e12c2..1b606dc210 100644
---
a/node-commons/src/test/java/org/apache/iotdb/commons/path/PartialPathTest.java
+++
b/node-commons/src/test/java/org/apache/iotdb/commons/path/PartialPathTest.java
@@ -699,6 +699,49 @@ public class PartialPathTest {
}
}
+ @Test
+ public void testInclude() throws IllegalPathException {
+ PartialPath[][] pathPairs =
+ new PartialPath[][] {
+ new PartialPath[] {new PartialPath("root.**"), new
PartialPath("root.sg.**")},
+ new PartialPath[] {new PartialPath("root.**.*"), new
PartialPath("root.**")},
+ new PartialPath[] {new PartialPath("root.**.*"), new
PartialPath("root.sg.**")},
+ new PartialPath[] {new PartialPath("root.**.s"), new
PartialPath("root.sg.**")},
+ new PartialPath[] {new PartialPath("root.*.**"), new
PartialPath("root.sg.**")},
+ new PartialPath[] {new PartialPath("root.*.d.s"), new
PartialPath("root.sg1.d.s")},
+ new PartialPath[] {new PartialPath("root.**.s"), new
PartialPath("root.*.d.s")},
+ new PartialPath[] {new PartialPath("root.*.d.s"), new
PartialPath("root.**.s")},
+ new PartialPath[] {new PartialPath("root.*.d.s"), new
PartialPath("root.sg.*.s")},
+ new PartialPath[] {new PartialPath("root.*.d.s"), new
PartialPath("root.sg.d2.s")},
+ new PartialPath[] {new PartialPath("root.*.d.s.*"), new
PartialPath("root.sg.d.s")},
+ new PartialPath[] {new PartialPath("root.**.d.s"), new
PartialPath("root.**.d2.s")},
+ new PartialPath[] {new PartialPath("root.**.*.s"), new
PartialPath("root.**.d2.s")},
+ new PartialPath[] {new PartialPath("root.**.d1.*"), new
PartialPath("root.*")},
+ new PartialPath[] {new PartialPath("root.**.d1.*"), new
PartialPath("root.d2.*.s")},
+ new PartialPath[] {new PartialPath("root.**.d1.**"), new
PartialPath("root.d2.**")},
+ new PartialPath[] {
+ new PartialPath("root.**.*.**.**"), new
PartialPath("root.d2.*.s1.**")
+ },
+ new PartialPath[] {new PartialPath("root.**.s1.d1"), new
PartialPath("root.s1.d1.**")},
+ new PartialPath[] {new PartialPath("root.**.s1"), new
PartialPath("root.**.s2.s1")},
+ new PartialPath[] {
+ new PartialPath("root.**.s1.s2.**"), new
PartialPath("root.d1.s1.s2.*")
+ },
+ new PartialPath[] {new PartialPath("root.**.s1"), new
PartialPath("root.**.s2")},
+ new PartialPath[] {new PartialPath("root.*.*.**"), new
PartialPath("root.**.*")},
+ new PartialPath[] {new PartialPath("root.**.**"), new
PartialPath("root.*.**.**.*")},
+ };
+ boolean[] results =
+ new boolean[] {
+ true, false, true, false, true, true, true, false, false, false,
false, false, true,
+ false, false, false, true, false, true, true, false, false, true
+ };
+ Assert.assertEquals(pathPairs.length, results.length);
+ for (int i = 0; i < pathPairs.length; i++) {
+ Assert.assertEquals(results[i],
pathPairs[i][0].include(pathPairs[i][1]));
+ }
+ }
+
private void checkNodes(String[] expected, String[] actual) {
Assert.assertEquals(expected.length, actual.length);
for (int i = 0; i < expected.length; i++) {
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 ef0e7a4e97..df8b8f3b35 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
@@ -33,8 +33,10 @@ import java.nio.ByteBuffer;
import java.util.ArrayDeque;
import java.util.ArrayList;
import java.util.Deque;
+import java.util.HashSet;
import java.util.Iterator;
import java.util.List;
+import java.util.Set;
import java.util.stream.Collectors;
public class PathPatternTree {
@@ -79,7 +81,7 @@ public class PathPatternTree {
public void appendPathPattern(PartialPath pathPattern) {
boolean isExist = false;
for (PartialPath path : pathPatternList) {
- if (path.matchFullPath(pathPattern)) {
+ if (path.include(pathPattern)) {
// path already exists in pathPatternList
isExist = true;
break;
@@ -88,7 +90,7 @@ public class PathPatternTree {
if (!isExist) {
// remove duplicate path in pathPatternList
pathPatternList.removeAll(
-
pathPatternList.stream().filter(pathPattern::matchFullPath).collect(Collectors.toList()));
+
pathPatternList.stream().filter(pathPattern::include).collect(Collectors.toList()));
pathPatternList.add(pathPattern);
}
}
@@ -134,13 +136,13 @@ public class PathPatternTree {
public List<String> getAllDevicePatterns() {
List<String> nodes = new ArrayList<>();
- List<String> results = new ArrayList<>();
+ Set<String> results = new HashSet<>();
searchDevicePattern(root, nodes, results);
- return results;
+ return new ArrayList<>(results);
}
private void searchDevicePattern(
- PathPatternNode curNode, List<String> nodes, List<String> results) {
+ PathPatternNode curNode, List<String> nodes, Set<String> results) {
nodes.add(curNode.getName());
if (curNode.isLeaf()) {
if (!curNode.getName().equals(IoTDBConstant.MULTI_LEVEL_PATH_WILDCARD)) {
diff --git
a/server/src/test/java/org/apache/iotdb/db/mpp/common/schematree/PathPatternTreeTest.java
b/server/src/test/java/org/apache/iotdb/db/mpp/common/schematree/PathPatternTreeTest.java
index 614430f4fb..eff740e1b2 100644
---
a/server/src/test/java/org/apache/iotdb/db/mpp/common/schematree/PathPatternTreeTest.java
+++
b/server/src/test/java/org/apache/iotdb/db/mpp/common/schematree/PathPatternTreeTest.java
@@ -136,6 +136,35 @@ public class PathPatternTreeTest {
new PartialPath("root.sg1.d3.t1")));
}
+ /** This use case is used to test the de-duplication of getAllPathPatterns
results */
+ @Test
+ public void pathPatternTreeTest7() throws IllegalPathException, IOException {
+ checkPathPatternTree(
+ Arrays.asList(
+ new PartialPath("root.sg1.d1.s1"),
+ new PartialPath("root.sg1.*.s2"),
+ new PartialPath("root.sg1.d1.t1.s1"),
+ new PartialPath("root.sg1.*.s1"),
+ new PartialPath("root.sg1.**.s1")),
+ Arrays.asList(new PartialPath("root.sg1.*.s2"), new
PartialPath("root.sg1.**.s1")),
+ Arrays.asList(new PartialPath("root.sg1.*"), new
PartialPath("root.sg1.**")));
+ }
+
+ /** This use case is used to test the de-duplication of getAllDevicePatterns
results */
+ @Test
+ public void pathPatternTreeTest8() throws IllegalPathException, IOException {
+ checkPathPatternTree(
+ Arrays.asList(new PartialPath("root.sg1.d1.s1"), new
PartialPath("root.sg1.d1.s2")),
+ Arrays.asList(new PartialPath("root.sg1.d1.s1"), new
PartialPath("root.sg1.d1.s2")),
+ Collections.singletonList(new PartialPath("root.sg1.d1")));
+ }
+
+ /**
+ * @param paths PartialPath list to create PathPatternTree
+ * @param compressedPaths Expected PartialPath list of getAllPathPatterns
+ * @param compressedDevicePaths Expected PartialPath list of
getAllDevicePatterns
+ * @throws IOException
+ */
private void checkPathPatternTree(
List<PartialPath> paths,
List<PartialPath> compressedPaths,
@@ -147,6 +176,10 @@ public class PathPatternTreeTest {
}
patternTree.constructTree();
+ Assert.assertEquals(
+ compressedPaths.stream().sorted().collect(Collectors.toList()),
+
patternTree.getAllPathPatterns().stream().sorted().collect(Collectors.toList()));
+
PathPatternTree resultPatternTree = new PathPatternTree();
for (PartialPath path : compressedPaths) {
resultPatternTree.appendPathPattern(path);
