This is an automated email from the ASF dual-hosted git repository.
qiaojialin pushed a commit to branch master
in repository https://gitbox.apache.org/repos/asf/incubator-iotdb.git
The following commit(s) were added to refs/heads/master by this push:
new 0391873 optimize tsfile expression
new 9b943d2 Merge pull request #894 from Ring-k/master
0391873 is described below
commit 0391873f8eadd8af56cf3dbb246a1595d6aa0aae
Author: Ring-k <[email protected]>
AuthorDate: Sun Mar 8 22:33:12 2020 +0800
optimize tsfile expression
---
.../SystemDesign/1-TsFile/4-Read.md | 4 +-
docs/Documentation/SystemDesign/1-TsFile/4-Read.md | 8 +--
.../read/expression/util/ExpressionOptimizer.java | 58 ++++++++++++++++++++--
.../read/filter/IExpressionOptimizerTest.java | 15 +++---
4 files changed, 69 insertions(+), 16 deletions(-)
diff --git a/docs/Documentation-CHN/SystemDesign/1-TsFile/4-Read.md
b/docs/Documentation-CHN/SystemDesign/1-TsFile/4-Read.md
index 1fde5ac..55450ab 100644
--- a/docs/Documentation-CHN/SystemDesign/1-TsFile/4-Read.md
+++ b/docs/Documentation-CHN/SystemDesign/1-TsFile/4-Read.md
@@ -384,8 +384,8 @@ IExpression 为查询过滤条件。一个 IExpression 可以是一个 SingleSer
*情况二*：GlobalTimeExpression 和 IExpression 的关系为 OR。该情况下的合并步骤如下：
1. 得到该查询所要投影的所有时间序列，其为一个 Path 的集合，以一个包含三个投影时间序列的查询为例，记所有要投影的列为
PathList{path1, path2, path3}。
- 2. 记 GlobalTimeExpression 的 Filter 为 tFilter，调用
pushGlobalTimeFilterToAllSeries() 方法为每个 Path 创建一个对应的 SingleSeriesExpression，且每个
SingleSeriesExpression 的 Filter 值均为 tFilter；将所有新创建的 SingleSeriesExpression 用 OR
运算符进行连接，得到一个 OrExpression，记其为 orExpression
- 3. 将步骤二得到的 orExpression 与 IExpression 按照关系 OR 进行合并，得到最终的结果。
+ 2. 记 GlobalTimeExpression 的 Filter 为 tFilter，调用
pushGlobalTimeFilterToAllSeries() 方法为每个 Path 创建一个对应的 SingleSeriesExpression，且每个
SingleSeriesExpression 的 Filter 值均为 tFilter；将所有新创建的 SingleSeriesExpression 用 OR
运算符进行连接，得到一个 OrExpression，记其为 orExpression。
+ 3. 调用 mergeSecondTreeToFirstTree 方法将 IExpression 中的节点与步骤二得到的 orExpression
中的节点进行合并，返回合并后的表达式。
例如，将如下 GlobaLTimeFilter 和 IExpression 按照关系 OR 进行合并，设该查询的被投影列为
PathList{path1, path2, path3}
diff --git a/docs/Documentation/SystemDesign/1-TsFile/4-Read.md
b/docs/Documentation/SystemDesign/1-TsFile/4-Read.md
index 3c3b710..59569f8 100644
--- a/docs/Documentation/SystemDesign/1-TsFile/4-Read.md
+++ b/docs/Documentation/SystemDesign/1-TsFile/4-Read.md
@@ -384,11 +384,11 @@ Before the introducing the optimize() method in detail,
we first show how to com
*Case 2*: The relation between GlobalTimeExpression and IExpression is OR.
In this case, the merge steps include:
1. Analyse the projected time series, which is a set of Path. To take a
query with 3 projected time series as an example, denote that projected time
series as a set, PathList{path1, path2, path3}。
2. Denote the Filter in GlobalTimeExpression to be tFilter. The method
calls pushGlobalTimeFilterToAllSeries() to generate a corresponding
SingleSeriesExpression for each Path. Set the Filters of
SingleSeriesExpressions to be tFilter. Join the generated
SingleSeriesExpression with OR operator to get an OrExpression, which is
denoted as orExpression.
- 3. Combine the result of step 2, the orExpression, and the IExpression
with OR operation, to generate the final result.
-
- For example, to combine the following GlobaLTimeFilter and IExpression
using OR relation, denote the projected time series as PathList{path1, path2,
path3}
+ 3. Call mergeSecondTreeToFirstTree method to combine the nodes in
IExpression with the nodes in the orExpression, which is generated from step 2.
The combined structure is the result expression.
+
+ For example, to combine the following GlobalTimeFilter and IExpression
using OR relation, denote the projected time series as PathList{path1, path2,
path3}
- 1. GlobaLTimeFilter(tFilter)
+ 1. GlobalTimeFilter(tFilter)
2. IExpression
AndExpression
SingleSeriesExpression("path1", filter1)
diff --git
a/tsfile/src/main/java/org/apache/iotdb/tsfile/read/expression/util/ExpressionOptimizer.java
b/tsfile/src/main/java/org/apache/iotdb/tsfile/read/expression/util/ExpressionOptimizer.java
index da83d1b..85af26c 100644
---
a/tsfile/src/main/java/org/apache/iotdb/tsfile/read/expression/util/ExpressionOptimizer.java
+++
b/tsfile/src/main/java/org/apache/iotdb/tsfile/read/expression/util/ExpressionOptimizer.java
@@ -45,7 +45,7 @@ public class ExpressionOptimizer {
/**
* try to remove GlobalTimeExpression.
*
- * @param expression IExpression to be transferred
+ * @param expression IExpression to be transferred
* @param selectedSeries selected series
* @return an executable query filter, whether a GlobalTimeExpression or All
leaf nodes are
* SingleSeriesExpression
@@ -108,14 +108,64 @@ public class ExpressionOptimizer {
addTimeFilterToQueryFilter((globalTimeExpression).getFilter(),
regularRightIExpression);
return regularRightIExpression;
} else if (relation == ExpressionType.OR) {
- return BinaryExpression
- .or(pushGlobalTimeFilterToAllSeries(globalTimeExpression,
selectedSeries),
- regularRightIExpression);
+ IExpression afterTransform =
pushGlobalTimeFilterToAllSeries(globalTimeExpression,
+ selectedSeries);
+ return mergeSecondTreeToFirstTree(afterTransform,
regularRightIExpression);
}
throw new QueryFilterOptimizationException("unknown relation in
IExpression:" + relation);
}
/**
+ * This method merge the second input, which is of tree structure, to the
first parameter. It
+ * visits all leaf nodes, which are SingleSeriesExpressions, or
AndExpression in right Expression,
+ * merge them to the right position in leftExpression.
+ *
+ * @param leftExpression The IExpression transformed from
GlobalTimeExpression, which might have
+ * already be updated and merged.
+ * @param rightExpression The IExpression to be merged into the first
IExpression
+ * @return a merged IExpression, which is initially based on the input
leftExpression
+ */
+ private IExpression mergeSecondTreeToFirstTree(IExpression leftExpression,
+ IExpression rightExpression) {
+ if (rightExpression.getType() == ExpressionType.SERIES) {
+ SingleSeriesExpression leaf = (SingleSeriesExpression) rightExpression;
+ updateFilterWithOr(leftExpression, leaf.getFilter(),
leaf.getSeriesPath());
+ return leftExpression;
+ } else if (rightExpression.getType() == ExpressionType.OR) {
+ IExpression leftChild = ((BinaryExpression) rightExpression).getLeft();
+ IExpression rightChild = ((BinaryExpression) rightExpression).getRight();
+ leftExpression = mergeSecondTreeToFirstTree(leftExpression, leftChild);
+ leftExpression = mergeSecondTreeToFirstTree(leftExpression, rightChild);
+ return leftExpression;
+ } else {
+ return BinaryExpression.or(leftExpression, rightExpression);
+ }
+ }
+
+ /**
+ * This method search the node in the input expression, whose path is
identical to the input
+ * path, then merges its filter and the input filter with relation OR.
+ *
+ * @return true if the input filter is merged.
+ */
+ private boolean updateFilterWithOr(IExpression expression, Filter filter,
Path path) {
+ if (expression.getType() == ExpressionType.SERIES &&
((SingleSeriesExpression) expression)
+ .getSeriesPath().equals(path)) {
+ Filter nodeFilter = ((SingleSeriesExpression) expression).getFilter();
+ nodeFilter = FilterFactory.or(nodeFilter, filter);
+ ((SingleSeriesExpression) expression).setFilter(nodeFilter);
+ return true;
+ } else if (expression.getType() == ExpressionType.OR) {
+ assert expression instanceof BinaryExpression;
+ IExpression left = ((BinaryExpression) expression).getLeft();
+ IExpression right = ((BinaryExpression) expression).getRight();
+ return updateFilterWithOr(left, filter, path) ||
updateFilterWithOr(right, filter, path);
+ } else {
+ return false;
+ }
+ }
+
+ /**
* Combine GlobalTimeExpression with all selected series. example: input:
* GlobalTimeExpression(timeFilter) Selected Series: path1, path2, path3
output: QueryFilterOR(
* QueryFilterOR( SingleSeriesExpression(path1, timeFilter),
SingleSeriesExpression(path2,
diff --git
a/tsfile/src/test/java/org/apache/iotdb/tsfile/read/filter/IExpressionOptimizerTest.java
b/tsfile/src/test/java/org/apache/iotdb/tsfile/read/filter/IExpressionOptimizerTest.java
index 8bf416d..d340b18 100644
---
a/tsfile/src/test/java/org/apache/iotdb/tsfile/read/filter/IExpressionOptimizerTest.java
+++
b/tsfile/src/test/java/org/apache/iotdb/tsfile/read/filter/IExpressionOptimizerTest.java
@@ -143,7 +143,7 @@ public class IExpressionOptimizerTest {
.or(BinaryExpression.and(singleSeriesExp1, globalTimeFilter),
globalTimeFilter2);
try {
- String rightRet = "[[[[[d1.s1:time > 1] || [d2.s1:time > 1]] ||
[d1.s2:time > 1]] || [d2.s2:time > 1]] || [d2.s1:((value > 100 || value < 50)
&& time < 14001234)]]";
+ String rightRet = "[[[[d1.s1:time > 1] || [d2.s1:(time > 1 || ((value >
100 || value < 50) && time < 14001234))]] || [d1.s2:time > 1]] || [d2.s2:time >
1]]";
IExpression regularFilter = expressionOptimizer.optimize(expression,
selectedSeries);
Assert.assertEquals(rightRet, regularFilter.toString());
} catch (QueryFilterOptimizationException e) {
@@ -189,8 +189,10 @@ public class IExpressionOptimizerTest {
try {
String rightRet =
- "[[[[[d1.s1:time < 14001234] || [d2.s1:time < 14001234]] ||
[d1.s2:time < 14001234]] "
- + "|| [d2.s2:time < 14001234]] || [[d2.s1:(value > 100 || value
< 50)] || [d1.s2:(value > 100.5 || value < 50.6)]]]";
+ "[[[[d1.s1:time < 14001234] "
+ + "|| [d2.s1:(time < 14001234 || (value > 100 || value < 50))]] "
+ + "|| [d1.s2:(time < 14001234 || (value > 100.5 || value <
50.6))]] "
+ + "|| [d2.s2:time < 14001234]]";
IExpression regularFilter = expressionOptimizer.optimize(expression,
selectedSeries);
Assert.assertEquals(rightRet, regularFilter.toString());
} catch (QueryFilterOptimizationException e) {
@@ -216,9 +218,10 @@ public class IExpressionOptimizerTest {
try {
String rightRet =
- "[[[[[d1.s1:(time < 14001234 && time > 14001000)] || [d2.s1:(time <
14001234 "
- + "&& time > 14001000)]] || [d1.s2:(time < 14001234 && time >
14001000)]] || [d2.s2:(time < 14001234 "
- + "&& time > 14001000)]] || [[d2.s1:(value > 100 || value < 50)]
|| [d1.s2:(value > 100.5 || value < 50.6)]]]";
+ "[[[[d1.s1:(time < 14001234 && time > 14001000)] "
+ + "|| [d2.s1:((time < 14001234 && time > 14001000) || (value >
100 || value < 50))]] "
+ + "|| [d1.s2:((time < 14001234 && time > 14001000) || (value >
100.5 || value < 50.6))]] "
+ + "|| [d2.s2:(time < 14001234 && time > 14001000)]]";
IExpression regularFilter = expressionOptimizer.optimize(expression,
selectedSeries);
Assert.assertEquals(rightRet, regularFilter.toString());
} catch (QueryFilterOptimizationException e) {
