You are viewing a plain text version of this content. The canonical link for it is here.
Posted to reviews@iotdb.apache.org by GitBox <gi...@apache.org> on 2022/03/26 02:02:30 UTC
[GitHub] [iotdb] JackieTien97 commented on a change in pull request #5343: [IOTDB-2713] Generate Analysis for query statement
JackieTien97 commented on a change in pull request #5343:
URL: https://github.com/apache/iotdb/pull/5343#discussion_r835690068
##########
File path: server/src/main/java/org/apache/iotdb/db/mpp/common/schematree/PathPatternTree.java
##########
@@ -19,25 +19,123 @@
package org.apache.iotdb.db.mpp.common.schematree;
+import org.apache.iotdb.db.metadata.path.PartialPath;
+import org.apache.iotdb.db.qp.constant.SQLConstant;
+
import java.io.IOException;
-import java.io.OutputStream;
import java.nio.ByteBuffer;
+import java.util.ArrayList;
+import java.util.List;
+import java.util.Objects;
+import java.util.stream.Collectors;
public class PathPatternTree {
private PathPatternNode root;
+ private final 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 void serialize(OutputStream baos) throws IOException {
+ public PathPatternTree() {
+ this.root = new PathPatternNode(SQLConstant.ROOT);
+ this.pathList = new ArrayList<>();
+ }
+
+ public PathPatternNode getRoot() {
+ return root;
+ }
+
+ public void setRoot(PathPatternNode root) {
+ this.root = root;
+ }
+
+ public boolean isPrefixMatchPath() {
+ return isPrefixMatchPath;
+ }
+
+ public void setPrefixMatchPath(boolean prefixMatchPath) {
+ isPrefixMatchPath = prefixMatchPath;
+ }
+
+ // append path to pathList
+ public void appendPath(PartialPath newPath) {
Review comment:
The time complexity of this methods is `O((N * M)^2)`, N is the number of `PartitalPath`, M is the average length of `PartialPath`, it's not very efficient.
You can use the `Trie Tree`, in most cases, you can save the compare operations and memory foorprint for the same prefix like`root.sg`.
##########
File path: server/src/main/java/org/apache/iotdb/db/mpp/common/schematree/PathPatternTree.java
##########
@@ -19,25 +19,123 @@
package org.apache.iotdb.db.mpp.common.schematree;
+import org.apache.iotdb.db.metadata.path.PartialPath;
+import org.apache.iotdb.db.qp.constant.SQLConstant;
+
import java.io.IOException;
-import java.io.OutputStream;
import java.nio.ByteBuffer;
+import java.util.ArrayList;
+import java.util.List;
+import java.util.Objects;
+import java.util.stream.Collectors;
public class PathPatternTree {
private PathPatternNode root;
+ private final 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 void serialize(OutputStream baos) throws IOException {
+ public PathPatternTree() {
+ this.root = new PathPatternNode(SQLConstant.ROOT);
+ this.pathList = new ArrayList<>();
+ }
+
+ public PathPatternNode getRoot() {
+ return root;
+ }
+
+ public void setRoot(PathPatternNode root) {
+ this.root = root;
+ }
+
+ public boolean isPrefixMatchPath() {
+ return isPrefixMatchPath;
+ }
+
+ public void setPrefixMatchPath(boolean prefixMatchPath) {
+ isPrefixMatchPath = prefixMatchPath;
+ }
+
+ // append path to pathList
+ public void appendPath(PartialPath newPath) {
+ boolean isExist = false;
+ for (PartialPath path : pathList) {
+ if (path.matchFullPath(newPath)) {
+ // path already exists in pathList
+ isExist = true;
+ break;
+ }
+ }
+ if (!isExist) {
+ // remove duplicate path in pathList
+ pathList.removeAll(
+ pathList.stream().filter(newPath::matchFullPath).collect(Collectors.toList()));
+ pathList.add(newPath);
+ }
+ }
+
+ // construct tree according to pathList
+ public void constructTree() {
+ for (PartialPath path : pathList) {
+ searchAndConstruct(root, path.getNodes(), 0);
+ }
+ pathList.clear();
+ }
+
+ public void searchAndConstruct(PathPatternNode curNode, String[] pathNodes, int pos) {
+ if (pos == pathNodes.length - 1) {
+ return;
+ }
+
+ boolean isExist = false;
+ PathPatternNode nextNode = null;
+ for (PathPatternNode childNode : curNode.getChilds()) {
+ if (!Objects.equals(childNode.getName(), pathNodes[pos + 1])) {
+ isExist = true;
+ nextNode = childNode;
+ break;
+ }
+ }
+
+ if (isExist) {
+ searchAndConstruct(nextNode, pathNodes, pos + 1);
+ } else {
+ appendTree(curNode, pathNodes, pos + 1);
+ }
+ }
+
+ 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);
+ curNode = newNode;
+ }
+ }
+
+ public void serialize(ByteBuffer buffer) throws IOException {
+ constructTree();
// TODO
}
public void deserialize(ByteBuffer buffer) throws IOException {
// TODO
}
+
+ @Override
+ public boolean equals(Object o) {
Review comment:
Still that question, when need we use this `equals` methods of a tree.
##########
File path: server/src/main/java/org/apache/iotdb/db/mpp/sql/statement/component/SelectComponent.java
##########
@@ -110,15 +108,7 @@ public void setAliasSet(Set<String> aliasSet) {
if (pathsCache == null) {
pathsCache = new ArrayList<>();
for (ResultColumn resultColumn : resultColumns) {
- Expression expression = resultColumn.getExpression();
- if (expression instanceof TimeSeriesOperand) {
- pathsCache.add(((TimeSeriesOperand) expression).getPath());
- } else if (expression instanceof FunctionExpression
- && expression.isPlainAggregationFunctionExpression()) {
- pathsCache.add(((TimeSeriesOperand) expression.getExpressions().get(0)).getPath());
- } else {
- pathsCache.add(null);
- }
+ pathsCache.addAll(resultColumn.collectPaths());
Review comment:
It seems that `pathsCache.addAll(resultColumn.collectPaths());` is not equivalent to the previous.
##########
File path: server/src/main/java/org/apache/iotdb/db/mpp/common/schematree/PathPatternNode.java
##########
@@ -19,10 +19,67 @@
package org.apache.iotdb.db.mpp.common.schematree;
+import java.util.ArrayList;
import java.util.List;
+import java.util.Objects;
public class PathPatternNode {
private String name;
private List<PathPatternNode> childs;
+
+ public PathPatternNode(String name) {
+ this.name = name;
+ this.childs = new ArrayList<>();
+ }
+
+ public String getName() {
+ return name;
+ }
+
+ public void setName(String name) {
+ this.name = name;
+ }
+
+ public List<PathPatternNode> getChilds() {
+ return childs;
+ }
+
+ public void setChilds(List<PathPatternNode> childs) {
+ this.childs = childs;
+ }
+
+ public void addChild(PathPatternNode newNode) {
+ this.childs.add(newNode);
+ }
+
+ public boolean isLeaf() {
+ return childs.isEmpty();
+ }
+
+ @Override
+ public boolean equals(Object o) {
Review comment:
better to override `equals` and `hashCode` methods at the same time, and BTW, why we need to override `equals` methods, we use it in `Map`?
##########
File path: server/src/main/java/org/apache/iotdb/db/mpp/common/schematree/PathPatternTree.java
##########
@@ -19,25 +19,123 @@
package org.apache.iotdb.db.mpp.common.schematree;
+import org.apache.iotdb.db.metadata.path.PartialPath;
+import org.apache.iotdb.db.qp.constant.SQLConstant;
+
import java.io.IOException;
-import java.io.OutputStream;
import java.nio.ByteBuffer;
+import java.util.ArrayList;
+import java.util.List;
+import java.util.Objects;
+import java.util.stream.Collectors;
public class PathPatternTree {
private PathPatternNode root;
+ private final 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 void serialize(OutputStream baos) throws IOException {
+ public PathPatternTree() {
+ this.root = new PathPatternNode(SQLConstant.ROOT);
+ this.pathList = new ArrayList<>();
+ }
+
+ public PathPatternNode getRoot() {
+ return root;
+ }
+
+ public void setRoot(PathPatternNode root) {
+ this.root = root;
+ }
+
+ public boolean isPrefixMatchPath() {
+ return isPrefixMatchPath;
+ }
+
+ public void setPrefixMatchPath(boolean prefixMatchPath) {
+ isPrefixMatchPath = prefixMatchPath;
+ }
+
+ // append path to pathList
+ public void appendPath(PartialPath newPath) {
+ boolean isExist = false;
+ for (PartialPath path : pathList) {
+ if (path.matchFullPath(newPath)) {
+ // path already exists in pathList
+ isExist = true;
+ break;
+ }
+ }
+ if (!isExist) {
+ // remove duplicate path in pathList
+ pathList.removeAll(
+ pathList.stream().filter(newPath::matchFullPath).collect(Collectors.toList()));
+ pathList.add(newPath);
+ }
Review comment:
If you use `Trie Tree`, you don't need this step, time complexity of this check step is also `O((N * M)^2)`
##########
File path: server/src/main/java/org/apache/iotdb/db/mpp/common/schematree/PathPatternTree.java
##########
@@ -19,25 +19,123 @@
package org.apache.iotdb.db.mpp.common.schematree;
+import org.apache.iotdb.db.metadata.path.PartialPath;
+import org.apache.iotdb.db.qp.constant.SQLConstant;
+
import java.io.IOException;
-import java.io.OutputStream;
import java.nio.ByteBuffer;
+import java.util.ArrayList;
+import java.util.List;
+import java.util.Objects;
+import java.util.stream.Collectors;
public class PathPatternTree {
private PathPatternNode root;
+ private final 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 void serialize(OutputStream baos) throws IOException {
+ public PathPatternTree() {
+ this.root = new PathPatternNode(SQLConstant.ROOT);
+ this.pathList = new ArrayList<>();
+ }
+
+ public PathPatternNode getRoot() {
+ return root;
+ }
+
+ public void setRoot(PathPatternNode root) {
+ this.root = root;
+ }
+
+ public boolean isPrefixMatchPath() {
+ return isPrefixMatchPath;
+ }
+
+ public void setPrefixMatchPath(boolean prefixMatchPath) {
+ isPrefixMatchPath = prefixMatchPath;
+ }
+
+ // append path to pathList
+ public void appendPath(PartialPath newPath) {
+ boolean isExist = false;
+ for (PartialPath path : pathList) {
+ if (path.matchFullPath(newPath)) {
+ // path already exists in pathList
+ isExist = true;
+ break;
+ }
+ }
+ if (!isExist) {
+ // remove duplicate path in pathList
+ pathList.removeAll(
+ pathList.stream().filter(newPath::matchFullPath).collect(Collectors.toList()));
+ pathList.add(newPath);
+ }
+ }
+
+ // construct tree according to pathList
+ public void constructTree() {
+ for (PartialPath path : pathList) {
+ searchAndConstruct(root, path.getNodes(), 0);
+ }
+ pathList.clear();
+ }
+
+ public void searchAndConstruct(PathPatternNode curNode, String[] pathNodes, int pos) {
+ if (pos == pathNodes.length - 1) {
+ return;
+ }
+
+ boolean isExist = false;
+ PathPatternNode nextNode = null;
+ for (PathPatternNode childNode : curNode.getChilds()) {
Review comment:
use `Map` instead of `List`, you won't need to traverse all the children here.
##########
File path: server/src/main/java/org/apache/iotdb/db/mpp/sql/analyze/Analysis.java
##########
@@ -49,6 +50,10 @@
private Map<String, MeasurementSchema> schemaMap;
Review comment:
If we have `SchemaTree`, still we need this field?
##########
File path: server/src/main/java/org/apache/iotdb/db/mpp/common/schematree/PathPatternNode.java
##########
@@ -19,10 +19,67 @@
package org.apache.iotdb.db.mpp.common.schematree;
+import java.util.ArrayList;
import java.util.List;
+import java.util.Objects;
public class PathPatternNode {
private String name;
private List<PathPatternNode> childs;
Review comment:
```suggestion
private List<PathPatternNode> children;
```
##########
File path: server/src/main/java/org/apache/iotdb/db/mpp/sql/rewriter/ConcatPathRewriter.java
##########
@@ -292,104 +195,63 @@ private QueryFilter concatWhereWithFromAndRemoveWildcards(
fromPaths.forEach(fromPath -> concatPaths.add(fromPath.concatPath(filterPath)));
}
- List<PartialPath> noStarPaths = removeWildcardsInConcatPaths(concatPaths, isPrefixMatch);
- filterPaths.addAll(noStarPaths);
- if (noStarPaths.size() == 1) {
+ filterPaths.addAll(concatPaths);
+ if (concatPaths.size() == 1) {
// Transform "select s1 from root.car.* where s1 > 10" to
// "select s1 from root.car.* where root.car.*.s1 > 10"
- functionOperator.setSinglePath(noStarPaths.get(0));
+ functionOperator.setSinglePath(concatPaths.get(0));
+ patternTree.appendPath(filter.getSinglePath());
return filter;
} else {
// Transform "select s1 from root.car.d1, root.car.d2 where s1 > 10" to
// "select s1 from root.car.d1, root.car.d2 where root.car.d1.s1 > 10 and root.car.d2.s1 > 10"
// Note that,
// two fork tree has to be maintained while removing stars in paths for DnfFilterOptimizer
// requirement.
- return constructBinaryFilterTreeWithAnd(noStarPaths, filter);
+ return constructBinaryFilterTreeWithAnd(concatPaths, filter);
Review comment:
`constructBinaryFilterTreeWithAnd` should be called after remove wilcards
##########
File path: server/src/main/java/org/apache/iotdb/db/mpp/sql/rewriter/ConcatPathRewriter.java
##########
@@ -292,104 +195,63 @@ private QueryFilter concatWhereWithFromAndRemoveWildcards(
fromPaths.forEach(fromPath -> concatPaths.add(fromPath.concatPath(filterPath)));
}
- List<PartialPath> noStarPaths = removeWildcardsInConcatPaths(concatPaths, isPrefixMatch);
- filterPaths.addAll(noStarPaths);
- if (noStarPaths.size() == 1) {
+ filterPaths.addAll(concatPaths);
+ if (concatPaths.size() == 1) {
Review comment:
You cannot do this judgement as before, because you don't remove stars here, this `concatPaths.size() == 1` is meaningless.
##########
File path: server/src/main/java/org/apache/iotdb/db/mpp/common/schematree/PathPatternNode.java
##########
@@ -19,10 +19,67 @@
package org.apache.iotdb.db.mpp.common.schematree;
+import java.util.ArrayList;
import java.util.List;
+import java.util.Objects;
public class PathPatternNode {
private String name;
private List<PathPatternNode> childs;
Review comment:
rename all the `childs` in this class to `children`.
##########
File path: server/src/main/java/org/apache/iotdb/db/mpp/common/schematree/SchemaTree.java
##########
@@ -39,16 +40,20 @@
* @param pathPattern can be a pattern or a full path of timeseries.
* @param isPrefixMatch if true, the path pattern is used to match prefix path
*/
- public List<MeasurementPath> searchMeasurementPaths(
+ public Pair<List<MeasurementPath>, Integer> searchMeasurementPaths(
Review comment:
add some java doc for the returned value, explain what's the meaning of ths pair.rght
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
To unsubscribe, e-mail: reviews-unsubscribe@iotdb.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org