You are viewing a plain text version of this content. The canonical link for it is here.
Posted to commits@iotdb.apache.org by hu...@apache.org on 2023/05/21 12:04:02 UTC
[iotdb] 01/01: [IOTDB-5887] Optimize the construction performance of PathPatternTree without wildcards
This is an automated email from the ASF dual-hosted git repository.
hui pushed a commit to branch lmh/OptPPT1.1
in repository https://gitbox.apache.org/repos/asf/iotdb.git
commit a7a3488473621d7a7d24edb861de05e827d956e0
Author: liuminghui233 <36...@users.noreply.github.com>
AuthorDate: Sun May 21 19:43:43 2023 +0800
[IOTDB-5887] Optimize the construction performance of PathPatternTree without wildcards
(cherry picked from commit 67d70cea85f2e9e6339ae001ac3246bf4f9eac4e)
---
.../apache/iotdb/commons/path/PathPatternTree.java | 34 ++++++++----
.../iotdb/commons/path/PathPatternTreeTest.java | 61 ++++++++++++++++++----
.../iotdb/db/mpp/plan/analyze/AnalyzeVisitor.java | 2 +-
.../iotdb/db/mpp/plan/parser/ASTVisitor.java | 6 +++
.../db/mpp/plan/statement/crud/QueryStatement.java | 10 ++++
5 files changed, 90 insertions(+), 23 deletions(-)
diff --git a/node-commons/src/main/java/org/apache/iotdb/commons/path/PathPatternTree.java b/node-commons/src/main/java/org/apache/iotdb/commons/path/PathPatternTree.java
index 4c9179cce93..629195d4a63 100644
--- a/node-commons/src/main/java/org/apache/iotdb/commons/path/PathPatternTree.java
+++ b/node-commons/src/main/java/org/apache/iotdb/commons/path/PathPatternTree.java
@@ -43,6 +43,14 @@ public class PathPatternTree {
private List<PartialPath> pathPatternList;
+ // set the default value to TRUE to ensure correctness
+ private boolean useWildcard = true;
+
+ public PathPatternTree(boolean useWildcard) {
+ this();
+ this.useWildcard = useWildcard;
+ }
+
public PathPatternTree() {
this.root = new PathPatternNode<>(IoTDBConstant.PATH_ROOT, VoidSerializer.getInstance());
this.pathPatternList = new LinkedList<>();
@@ -77,18 +85,22 @@ public class PathPatternTree {
/** Add a pathPattern (may contain wildcards) to pathPatternList. */
public void appendPathPattern(PartialPath pathPattern) {
- boolean isExist = false;
- for (PartialPath path : pathPatternList) {
- if (path.include(pathPattern)) {
- // path already exists in pathPatternList
- isExist = true;
- break;
+ if (useWildcard) {
+ boolean isExist = false;
+ for (PartialPath path : pathPatternList) {
+ if (path.include(pathPattern)) {
+ // path already exists in pathPatternList
+ isExist = true;
+ break;
+ }
}
- }
- if (!isExist) {
- // remove duplicate path in pathPatternList
- pathPatternList.removeIf(pathPattern::include);
- pathPatternList.add(pathPattern);
+ if (!isExist) {
+ // remove duplicate path in pathPatternList
+ pathPatternList.removeIf(pathPattern::include);
+ pathPatternList.add(pathPattern);
+ }
+ } else {
+ appendBranchWithoutPrune(root, pathPattern.getNodes(), 0);
}
}
diff --git a/node-commons/src/test/java/org/apache/iotdb/commons/path/PathPatternTreeTest.java b/node-commons/src/test/java/org/apache/iotdb/commons/path/PathPatternTreeTest.java
index 08dcbbe6d8e..ed30c293b38 100644
--- a/node-commons/src/test/java/org/apache/iotdb/commons/path/PathPatternTreeTest.java
+++ b/node-commons/src/test/java/org/apache/iotdb/commons/path/PathPatternTreeTest.java
@@ -43,7 +43,8 @@ public class PathPatternTreeTest {
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")));
+ Collections.singletonList(new PartialPath("root.sg1.d1")),
+ true);
}
@Test
@@ -55,7 +56,8 @@ public class PathPatternTreeTest {
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.*")));
+ Arrays.asList(new PartialPath("root.sg1.d1.t2"), new PartialPath("root.sg1.*")),
+ true);
}
@Test
@@ -74,7 +76,8 @@ public class PathPatternTreeTest {
Arrays.asList(
new PartialPath("root.sg1.d1"),
new PartialPath("root.sg1.d1.t1"),
- new PartialPath("root.sg1.*")));
+ new PartialPath("root.sg1.*")),
+ true);
}
@Test
@@ -91,7 +94,8 @@ public class PathPatternTreeTest {
new PartialPath("root.sg1.d1.t1.s1"),
new PartialPath("root.sg1.d2.s3")),
Collections.singletonList(new PartialPath("root.**")),
- Collections.singletonList(new PartialPath("root.**")));
+ Collections.singletonList(new PartialPath("root.**")),
+ true);
}
@Test
@@ -104,7 +108,8 @@ public class PathPatternTreeTest {
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.**")));
+ Arrays.asList(new PartialPath("root.sg1.d1"), new PartialPath("root.sg1.**")),
+ true);
}
@Test
@@ -132,7 +137,8 @@ public class PathPatternTreeTest {
new PartialPath("root.sg1.d2"),
new PartialPath("root.sg1.**"),
new PartialPath("root.sg1.*"),
- new PartialPath("root.sg1.d3.t1")));
+ new PartialPath("root.sg1.d3.t1")),
+ true);
}
/** This use case is used to test the de-duplication of getAllPathPatterns results */
@@ -146,7 +152,8 @@ public class PathPatternTreeTest {
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.**")));
+ Arrays.asList(new PartialPath("root.sg1.*"), new PartialPath("root.sg1.**")),
+ true);
}
/** This use case is used to test the de-duplication of getAllDevicePatterns results */
@@ -155,7 +162,8 @@ public class PathPatternTreeTest {
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")));
+ Collections.singletonList(new PartialPath("root.sg1.d1")),
+ true);
}
/**
@@ -177,7 +185,37 @@ public class PathPatternTreeTest {
Arrays.asList(
new PartialPath("root.sg1"),
new PartialPath("root.sg1.d1"),
- new PartialPath("root.sg1.d1.**")));
+ new PartialPath("root.sg1.d1.**")),
+ true);
+ }
+
+ @Test
+ public void pathPatternTreeWithoutWildcardTest() throws IllegalPathException, IOException {
+ checkPathPatternTree(
+ Arrays.asList(
+ new PartialPath("root.sg1.d1.s1"),
+ new PartialPath("root.sg1.d2.s1"),
+ new PartialPath("root.sg1.d1.s2"),
+ new PartialPath("root.sg1.d1.t1.s1"),
+ new PartialPath("root.sg1.d1.t2.s2"),
+ new PartialPath("root.sg1.d2.s1"),
+ new PartialPath("root.sg1.d2.s2"),
+ new PartialPath("root.sg1.d1.t1.s1"),
+ new PartialPath("root.sg1.d1.t2.s2"),
+ new PartialPath("root.sg1.d1.s1")),
+ Arrays.asList(
+ new PartialPath("root.sg1.d1.s1"),
+ new PartialPath("root.sg1.d1.s2"),
+ new PartialPath("root.sg1.d2.s1"),
+ new PartialPath("root.sg1.d2.s2"),
+ new PartialPath("root.sg1.d1.t1.s1"),
+ new PartialPath("root.sg1.d1.t2.s2")),
+ Arrays.asList(
+ new PartialPath("root.sg1.d1"),
+ new PartialPath("root.sg1.d2"),
+ new PartialPath("root.sg1.d1.t1"),
+ new PartialPath("root.sg1.d1.t2")),
+ false);
}
/**
@@ -189,9 +227,10 @@ public class PathPatternTreeTest {
private void checkPathPatternTree(
List<PartialPath> paths,
List<PartialPath> compressedPaths,
- List<PartialPath> compressedDevicePaths)
+ List<PartialPath> compressedDevicePaths,
+ boolean useWildcard)
throws IOException {
- PathPatternTree patternTree = new PathPatternTree();
+ PathPatternTree patternTree = new PathPatternTree(useWildcard);
for (PartialPath path : paths) {
patternTree.appendPathPattern(path);
}
diff --git a/server/src/main/java/org/apache/iotdb/db/mpp/plan/analyze/AnalyzeVisitor.java b/server/src/main/java/org/apache/iotdb/db/mpp/plan/analyze/AnalyzeVisitor.java
index 3307138f4b9..af47f31565c 100644
--- a/server/src/main/java/org/apache/iotdb/db/mpp/plan/analyze/AnalyzeVisitor.java
+++ b/server/src/main/java/org/apache/iotdb/db/mpp/plan/analyze/AnalyzeVisitor.java
@@ -230,7 +230,7 @@ public class AnalyzeVisitor extends StatementVisitor<Analysis, MPPQueryContext>
queryStatement.semanticCheck();
// concat path and construct path pattern tree
- PathPatternTree patternTree = new PathPatternTree();
+ PathPatternTree patternTree = new PathPatternTree(queryStatement.useWildcard());
queryStatement =
(QueryStatement) new ConcatPathRewriter().rewrite(queryStatement, patternTree);
analysis.setStatement(queryStatement);
diff --git a/server/src/main/java/org/apache/iotdb/db/mpp/plan/parser/ASTVisitor.java b/server/src/main/java/org/apache/iotdb/db/mpp/plan/parser/ASTVisitor.java
index 3169456672e..8669ef72975 100644
--- a/server/src/main/java/org/apache/iotdb/db/mpp/plan/parser/ASTVisitor.java
+++ b/server/src/main/java/org/apache/iotdb/db/mpp/plan/parser/ASTVisitor.java
@@ -224,6 +224,8 @@ public class ASTVisitor extends IoTDBSqlParserBaseVisitor<Statement> {
private ZoneId zoneId;
+ private boolean useWildcard = false;
+
public void setZoneId(ZoneId zoneId) {
this.zoneId = zoneId;
}
@@ -1037,6 +1039,7 @@ public class ASTVisitor extends IoTDBSqlParserBaseVisitor<Statement> {
queryStatement.setResultSetFormat(parseAlignBy(ctx.alignByClause()));
}
+ queryStatement.setUseWildcard(useWildcard);
return queryStatement;
}
@@ -1596,6 +1599,9 @@ public class ASTVisitor extends IoTDBSqlParserBaseVisitor<Statement> {
}
private String parseNodeName(IoTDBSqlParser.NodeNameContext ctx) {
+ if (!useWildcard && !ctx.wildcard().isEmpty()) {
+ useWildcard = true;
+ }
return parseNodeString(ctx.getText());
}
diff --git a/server/src/main/java/org/apache/iotdb/db/mpp/plan/statement/crud/QueryStatement.java b/server/src/main/java/org/apache/iotdb/db/mpp/plan/statement/crud/QueryStatement.java
index 2ee9e9a7451..7ffb1b7299f 100644
--- a/server/src/main/java/org/apache/iotdb/db/mpp/plan/statement/crud/QueryStatement.java
+++ b/server/src/main/java/org/apache/iotdb/db/mpp/plan/statement/crud/QueryStatement.java
@@ -112,6 +112,8 @@ public class QueryStatement extends Statement {
private boolean isOutputEndTime = false;
+ private boolean useWildcard = true;
+
public QueryStatement() {
this.statementType = StatementType.QUERY;
}
@@ -388,6 +390,14 @@ public class QueryStatement extends Statement {
return rowOffset > 0;
}
+ public void setUseWildcard(boolean useWildcard) {
+ this.useWildcard = useWildcard;
+ }
+
+ public boolean useWildcard() {
+ return useWildcard;
+ }
+
public void semanticCheck() {
if (isAggregationQuery()) {
if (disableAlign()) {