Ring-k commented on a change in pull request #825: [IOTDB-499] Add query engine
decument
URL: https://github.com/apache/incubator-iotdb/pull/825#discussion_r382958594
##########
File path: docs/Documentation-CHN/SystemDesign/2-QueryEngine/2-Planner.md
##########
@@ -50,14 +68,193 @@ mvn clean compile
之后生成代码位置：server/target/generated-sources/ant
谓词去非优化器，将谓词逻辑中的非操作符去掉。
* org.apache.iotdb.db.qp.strategy.optimizer.DnfFilterOptimizer
-
+
将谓词转化为析取范式。
-
+
* org.apache.iotdb.db.qp.strategy.optimizer.MergeSingleFilterOptimizer
将相同路径的谓词逻辑合并。
-
+
+### ConcatPathOptimizer
+
+ConcatPathOptimizer 使用其中的 transform() 方法将给定查询中 FROM 子句中的前缀路径与 SELECT 子句， WHERE
子句中的后缀路径进行拼接。该方法的申明如下：
+
+ Operator transform(Operator operator)
+ 输入：待转化的 SFWOperator
+ 输出：路径经过连接处理后的 SFWOperator
+
+
+该方法的主要步骤如下：
+
+1. 取出 FROM 子句和 SELECT 子句中的路径，前者称为前缀路径，后者称为后缀路径。进入步骤2.
+2. 判断该查询是否包含 ALIGN BY DEVICE 子句。如果不包含，则可进入步骤3；否则，进入步骤4.
+3. 则调用 concatSelect() 方法将前缀路径和后缀路径合并补全（包括带 * 的路径），形成全路径。如果查询中包含 SLIMIT 子句，则对
SELECT 子句中的路径做相应的筛选。进入步骤5.
+4. 对每一条 FROM 子句中的路径分析其设备名，如果不为空则抛出异常。进入步骤5.
+5. 对 WHERE 子句过滤条件中包含的后缀路径做补全。完成后，SELECT 子句和 WHERE 子句中的路径都是完整的路径。
+
+### RemoveNotOptimizer
+
+RemoveNotOptimizer 类中的 removeNot() 和 reverseFilter() 方法共同实现了删去 NOT
关键字的功能。removeNot() 方法的申明如下：
+
+ FilterOperator removeNot(FilterOperator filter)
+ 输入：待优化的可能含有 NOT 关键字的谓词
+ 输出：优化后，不包含 NOT 关键字的谓词
+
+该方法的输入为待优化的谓词，并且递归地优化该谓词中的每个子部分。将输入的谓词看作一棵二叉树，其中叶子节点是 BasicFunctionOperator （如
s0 > 10），非叶子节点是“与”、“或”、“非”操作符。 方法的逻辑如下：
+
+1. 判断该节点是否为叶子节点。如果是叶子节点则返回该节点。如果不是叶子节点则进入步骤2.
+2. 判断关系类型。如果是“与”、“或”关系，则进入步骤3；如果是“非”关系，则进入步骤4；如果不是“与”、“或”、“非”关系，则抛出异常。
+3. 此时的“与”、“或”关系一定包含2个孩子节点。对左右孩子递归调用 removeNot() 方法，去除左右子树中的 NOT 关键词，再将该节点返回。
+4. 对该节点调用 reverseFilter() 方法，取反，并且去除 NOT 关键字。
+
+reverseFilter() 方法的申明如下：
+
+ FilterOperator reverseFilter(FilterOperator filter)
+ 输入：待取反的节点
+ 输出：该节点取反后的结果
+
+reverseFilter() 方法的逻辑如下：
+
+1. 判断节点是否为叶子节点，如果是，则调用该节点自身的 reverseFunc() 方法取反。其中，reverseFunc() 方法只用设定的 Map
来对关键字取反，如将 < 映射为 >= ,将 AND 映射为 OR。如果不是叶子节点，则进入步骤2.
+2.
如果不是叶子节点，分两种情况。如果是“与”、“或”关系，则进入步骤3；如果是“非”关系则进入步骤4；如果既不是“与”、“或”关系，也不是“非”关系，则抛出异常。
+3. 对该节点的左右子树递归调用 reverseFilter() 方法，得到两个取反后的子树，并将该节点返回。
+4. 对孩子节点调用 removeNot() 方法，并将去除 NOT 关键字的孩子节点返回。
+
+removeNot() 和 reverseFilter() 之间存在一定的耦合关系。removeNot() 访问非 NOT 关系的节点，确保不含有 NOT
关键字；reverseFilter() 访问 NOT 关系节点以及子节点，并进行取反转换，删去 NOT 关键字。
+
+### DnfFilterOptimizer
+
+DNF 是 Disjuctive Normal Form 的缩写，即析取范式。DnfFilterOptimizer 中的 optimize() 方法来依靠
getDnf() 来实现，对过滤条件进行优化，将过滤条件转化为析取范式的形式。该方法的申明如下：
+
+ FilterOperator getDnf(FilterOperator filter)
+ 输入：待优化的 FilterOperator
+ 输出：优化后的 FilterOperator，以析取范式为形式
+
+该方法的步骤如下：
+
+1. 如果当前节点是叶子节点，则返回该节点
+2. 如果当前节点表示关系“或”，则
+ 1. 获取当前节点所有的子节点（子节点数目为2），并对左右子节点分别递归地调用 getDnf() 方法，使得左右字节点都为析取范式。
+ 2.
对该节点的左子节点和右子节点分别分析。如果子节点是叶子节点或表示关系“与”，则保持不变；否则，说明该子节点的关系为“或”，则将子节点的所有子节点也添加到当前节点的子节点中。即
(OR (OR A, B), C) 转换为 (OR A, B, C)。
+ 3. 返回当前节点。
+3. 如果当前节点表示关系“与”，则
+ 1. 获取当前节点所有的子节点（子节点数目为2），并对左右子节点分别递归地调用 getDnf() 方法，使得左右字节点都为析取范式。
+ 2. 对该节点的左子节点和右子节点分别分析。
+ 1.
如果左右子节点都不是“或”关系，则说明左右子节点要么是叶子节点，要么是关系“与”，如果是叶子节点，则保持不变，如果是关系“与”，则将该子节点的子节点添加到当前节点的孩子节点中，如
(AND A, (AND B, C)) 就转化为 (AND A, B, C)。
+ 2. 如果左右子节点包含为两个“或”关系，将其中一个子节点的两个子节点标记为 A 和 B ，另一子节点的两个子节点标记为 C 和 D，则将
{A, B} 与 {C, D} 两个集合中的元素两两组合，(A, C), (A, D), (B, C), (B, D), 对每一组组合调用
mergeToConjunction() 方法生成合取式作为当前节点的子节点，并将当前节点设为关系“或”，即，把 (AND (OR A, B), (OR C,
D)) 转换为 (OR (AND A, C), (AND A, D), (AND B, C), (AND B, D))。
+ 3. 如果左右子节点包含一个“或”关系，一个“与”关系或叶子节点。将“或”子节点的两个子节点标记为 X, Y，将另一子节点标记为
Z，则只要将 {X, Y} 与 {Z} 集合种的元素两两组合，对 (X, Z), (Y,Z) 调用 mergeToConjunction()
方法生成合取式作为当前节点的子节点，并将当前节点设为关系“或”，即，把 (AND (OR X, Y), Z) 转换为 (OR (AND X, Z), (AND
Y, Z))。
+ 3. 返回当前节点。
+
+
+对于以上提到的 mergeToConjunction() 方法，申明如下：
+
+ FilterOperator mergeToConjunction(FilterOperator operator1, FilterOperator
operator2)
+ 输入：两个子 FilterOperator
+ 输出：合并后的合取式
+
+该方法将输入的两个子合取式 Operator 合并为一个合取式，例如：(a and b) merge (c) -> (a and b and c)
+
+
+### MergeSingleFilterOptimizer
+
+
+MergeSingleFilterOptimizer 类主要通过 mergeSamePathFilter() 方法对节点进行合并。该方法的申明如下：
+
+ Path mergeSamePathFilter(FilterOperator filter)
+ 输入：待转换（合并）的 Filter
+ 输出：处理后（合并）的 Filter
+
+该方法的步骤如下：
+
+1. 如果该节点是叶子节点，则直接返回节点中包含的路径，进入步骤2.
+2. 对当前节点依次递归地使用 mergeSamePathFilter()
方法访问子节点并获取子节点所表示的路径，如果子节点路径不同，则将当前节点所表示的路径设为 null，进入步骤3；否则，设为子节点的公共路径，并返回该路径。
+3. 如果子节点均为 BasicFunctionOperator，则对子节点按照路径进行排序。进入步骤4.
+4. 对当前节点调用 mergeSingleFilters() 方法获得当前节点内子节点表示的路径非 null
的最大序号。该操作会将子节点中路径相同的节点合并，同时保留路径非 null 子节点。
+5. 将剩余的路径为 null 的节点依次设为当前节点的子节点。
+
+mergeSingleFilter() 方法将子节点中路径相同的节点进行合并。具体实现上，将生成新的 FilterOperator
作为子节点，并将操作符类型与当前节点设为相同，再将那些路径相同的子节点设为新节点的子节点，最后返回子节点中非 null
的最大序号。例如，下图表示合并同路径过滤条件的过程（圆形表示非叶子节点，长方形表示叶子节点。冒号前表示节点的类别或过滤条件，冒号后表示当前节点存储的路径）：
+
+
+
+### 举例说明
+
+假设输入的 SQL 语句为 <center>SELECT * FROM root.v0.d0 WHERE (NOT time<200) AND (s1 <
10 OR s2 > 50 OR s1 > 20)</center>
+
+则生成的选择条件树状结构如下：
+
+
+
## 物理计划生成器
* org.apache.iotdb.db.qp.strategy.PhysicalGenerator
+### TransformToPhysicalPlan()
+
+PhysicalGenerator 类中的 transformToPhysicalPlan() 方法将 Planner
中生成的逻辑计划转化为物理计划。其声明如下：
+
+```java
+PhysicalPlan transformToPhysicalPlan(Operator operator)
+输入：Planner 中经过优化的逻辑计划 operator
+输出：通过解析 operator 生成的物理计划
+```
+
+transformToPhysicalPlan() 方法的逻辑较为简单，即通过 operator.getType()
方法判断逻辑计划的类型，然后创建相对应的物理计划。
+
+其中只有 Query 类型需要额外调用 transformQuery() 方法进行进一步转化，其余类型均可以直接创建物理计划。
+
+#### TransformQuery()
+
+transformQuery() 方法主要分为两部分，一部分是原始数据查询 RawDataQueryPlan 的转化（按时间对齐），另一部分是按设备对齐
AlignByDevicePlan 的转化。
+
+RawDataQueryPlan 有三个子类，分别为 GroupByPlan、FillQueryPlan 和 AggregationPlan。在分开处理
RawDataQueryPlan 和 AlignByDevicePlan 前，首先处理这三个子类，将需要的参数保存供之后使用。
+
+以 GroupByPlan 为例，其中调用了
setInterval()、setSlidingStep()、setStartTime()、setEndTime() 方法存储了 GroupByPlan
的时间间隔、步长、开始时间、结束时间等参数。
+
+##### AlignByDevicePlan 转化
+
+首先解释一下 AlignByDevicePlan 中一些重要字段的作用。
+
+- prefixPaths：FROM 子句中的前缀路径，如 root.*.*, root.sg.d1;
+- devices：对 prefixPaths 进行去星和设备去重后得到的设备列表;
+- suffixPaths：SELECT 子句中的后缀路径，如 s0, temperature, *;
+- measurements：存储实际存在且非常量的 Measurement，在 measurementSetOfGivenSuffix
所举示例中，measurements = [s1,s2,s3,s1];
Review comment:
好的。
----------------------------------------------------------------
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.
For queries about this service, please contact Infrastructure at:
[email protected]
With regards,
Apache Git Services
