This is an automated email from the ASF dual-hosted git repository.
qiaojialin pushed a commit to branch new_series_reader
in repository https://gitbox.apache.org/repos/asf/incubator-iotdb.git
The following commit(s) were added to refs/heads/new_series_reader by this push:
new dd6025b split tsfile read document (#835)
dd6025b is described below
commit dd6025b6ad2c4229414ca3217fd747d497986cfd
Author: Ring-k <[email protected]>
AuthorDate: Wed Feb 26 13:44:31 2020 +0800
split tsfile read document (#835)
* split tsfile read document into filter and query execution
---
.../1-TsFile/{4-Read.md => 4-Filter.md} | 178 ++------------------
.../SystemDesign/1-TsFile/5-QueryExecution.md | 164 +++++++++++++++++++
docs/Documentation/SystemDesign/0-Content.md | 3 +-
.../1-TsFile/{4-Read.md => 4-Filter.md} | 179 +++------------------
.../SystemDesign/1-TsFile/5-QueryExecution.md | 158 ++++++++++++++++++
5 files changed, 361 insertions(+), 321 deletions(-)
diff --git a/docs/Documentation-CHN/SystemDesign/1-TsFile/4-Read.md
b/docs/Documentation-CHN/SystemDesign/1-TsFile/4-Filter.md
similarity index 72%
rename from docs/Documentation-CHN/SystemDesign/1-TsFile/4-Read.md
rename to docs/Documentation-CHN/SystemDesign/1-TsFile/4-Filter.md
index 1fde5ac..9a762f1 100644
--- a/docs/Documentation-CHN/SystemDesign/1-TsFile/4-Read.md
+++ b/docs/Documentation-CHN/SystemDesign/1-TsFile/4-Filter.md
@@ -19,34 +19,19 @@
-->
-# TsFile 读流程
-
-本章节介绍 TsFile 的读取流程，内容总体上分为两部分，对过滤条件和时间表达式的介绍，以及对查询流程的详细介绍。
-
-* 1 过滤条件和查询表达式
- * 1.1 Filter
- * 1.2 Expression表达式
- * 1.2.1 SingleSeriesExpression 表达式
- * 1.2.2 GlobalTimeExpression 表达式
- * 1.2.3 IExpression 表达式
- * 1.2.4 可执行表达式
- * 1.2.5 IExpression 转化为可执行表达式的优化算法
-* 2 TsFile 查询执行过程
- * 2.1 设计原理
- * 2.2 三大查询组件
- * 2.2.1 FileSeriesReader 组件
- * 2.2.2 FileSeriesReaderByTimestamp 组件
- * 2.2.3 TimeGeneratorImpl 组件
- * 2.3 归并查询
- * 2.4 连接查询
- * 2.5 查询入口
- * 2.6 相关代码介绍
-
-## 1 过滤条件和查询表达式
+# 过滤条件和查询表达式
本章节首先介绍 Tsfile 文件读取时需要用到的过滤条件和查询表达式的相关定义；其次介绍如何将用户输入的过滤条件转化为系统可以执行的查询条件。
-### 1.1 Filter
+* 1 Filter
+* 2 Expression表达式
+ * 2.1 SingleSeriesExpression 表达式
+ * 2.2 GlobalTimeExpression 表达式
+ * 2.3 IExpression 表达式
+ * 2.4 可执行表达式
+ * 2.5 IExpression 转化为可执行表达式的优化算法
+
+## 1 Filter
Filter 表示基本的过滤条件。用户可以在时间戳上、或某一列的值上给出具体的过滤条件。将时间戳和列值的过滤条件加以区分后，设 t
表示某一时间戳常量，Filter 有以下12种基本类型，在实现上是继承关系。
@@ -101,11 +86,11 @@ ValueNotEq| value != v| value != true，表示 value 的值不能为true
AndFilter| \<Filter> && \<Filter>| 1. value > 100 && value < 200,表示
value大于100且小于200； <br>2. (value >= 100 && value <= 200) && time >
14152176545,表示“value 大于等于100 且 value 小于等于200” 且 “时间戳大于 14152176545”
OrFilter| \<Filter> || \<Filter>| 1. value > 100 || time >
14152176545，表示value大于100或时间戳大于14152176545；<br>2. (value > 100 && value <
200)|| time > 14152176545，表示“value大于100且value小于200”或“时间戳大于14152176545”
-### 1.2 Expression表达式
+## 2 Expression表达式
当一个过滤条件作用到一个时间序列上，就成为一个表达式。例如，“数值大于10” 是一个过滤条件；而 “序列 d1.s1 的数值大于10”
就是一条表达式。特殊地，对时间的过滤条件也是一个表达式，称为 GlobalTimeExpression。以下章节将对表达式进行展开介绍。
-#### 1.2.1 SingleSeriesExpression表达式
+### 2.1 SingleSeriesExpression表达式
SingleSeriesExpression 表示针对某一指定时间序列的过滤条件，一个 SingleSeriesExpression 包含一个 Path
和一个 Filter。Path 表示该时间序列的路径；Filter 即为2.1章节中介绍的 Filter，表示相应的过滤条件。
@@ -138,7 +123,7 @@ SingleSeriesExpression 的结构如下：
其符号化表达方式为：SingleSeriesExpression(“d1.s1”, (value > 100 && value < 200) && time
> 14152176545)
-#### 1.2.2 GlobalTimeExpression 表达式
+### 2.2 GlobalTimeExpression 表达式
GlobalTimeExpression 表示全局的时间过滤条件，一个 GlobalTimeExpression 包含一个 Filter，且该 Filter
中包含的子 Filter 必须全为时间过滤条件。在一次查询中，一个 GlobalTimeExpression 表示查询返回数据点必须满足该表达式中
Filter 所表示的过滤条件。GlobalTimeExpression 的结构如下：
@@ -153,7 +138,7 @@ GlobalTimeExpression 表示全局的时间过滤条件，一个 GlobalTimeExpres
1. GlobalTimeExpression(time > 14152176545 && time <
14152176645)表示所有被选择的列的时间戳必须满足“大于14152176545且小于14152176645”
2. GlobalTimeExpression((time > 100 && time < 200) || (time > 400 && time <
500))表示所有被选择列的时间戳必须满足“大于100且小于200”或“大于400且小于500”
-#### 1.2.3 IExpression 表达式
+### 2.3 IExpression 表达式
IExpression 为查询过滤条件。一个 IExpression 可以是一个 SingleSeriesExpression 或者一个
GlobalTimeExpression，这种情况下，IExpression 也称为一元表达式，即 UnaryExpression。一个
IExpression 也可以由两个 IExpression 通过逻辑关系“与”、“或”进行连接得到 “AndExpression” 或
“OrExpression” 二元表达式，即 BinaryExpression。
下面给出 IExpression 的形式化定义。
@@ -194,7 +179,7 @@ IExpression 为查询过滤条件。一个 IExpression 可以是一个 SingleSer
**解释**：该 IExpression 为一个 AndExpression，其要求"d1.s1"和"d1.s2"必须同时满足其对应的
Filter，且时间列必须满足 GlobalTimeExpression 定义的 Filter 条件。
-#### 1.2.4 可执行表达式
+### 2.4 可执行表达式
便于理解执行过程，定义可执行表达式的概念。可执行表达式是带有一定限制条件的 IExpression。用户输入的查询条件或构造的 IExpression
将经过特定的优化算法（该算法将在后面章节中介绍）转化为可执行表达式。满足下面任意条件的 IExpression 即为可执行表达式。
@@ -274,7 +259,7 @@ IExpression 为查询过滤条件。一个 IExpression 可以是一个 SingleSer
**解释**：该 IExpression 为一个 AndExpression，但其叶子结点中包含了 GlobalTimeExpression，不满足条件3
-#### 1.2.5 IExpression转化为可执行表达式的优化算法
+### 2.5 IExpression转化为可执行表达式的优化算法
本章节介绍将 IExpression 转化为一个可执行表达式的算法。
@@ -433,134 +418,3 @@ IExpression 为查询过滤条件。一个 IExpression 可以是一个 SingleSer
c. 如果 LeftIExpression 不是 GlobalTimeExpression，而 RightIExpression 是
GlobalTimeExpression，则调用 handleOneGlobalTimeExpressionr()方法进行合并。
d. 如果 LeftIExpression 和 RightIExpression 均不是 GlobalTimeExpression，则对
LeftIExpression 递归调用 optimize() 方法得到左可执行表达式；对 RightIExpression 递归调用 optimize()
方法得到右可执行表达式。使用 MergeIExpression 方法，根据 type 的值将左可执行表达式和右可执行表达式合并为一个 IExpression。
-
-## 2 TsFile 查询执行过程
-
-### 2.1 设计原理
-
-TsFile 文件层查询接口只包含原始数据查询，根据是否包含值过滤条件，可以将查询分为两类“无过滤条件或仅包含时间过滤条件查询”和“包含值过滤条件的查询”
-
-为了执行以上两类查询，有两套查询流程
-
-* 归并查询
-
- 生成多个 reader，按照 time 对齐，返回结果集。
-
-* 连接查询
-
- 根据查询条件生成满足过滤条件的时间戳，通过满足条件的时间戳查询投影列的值，返回结果集。
-
-### 2.2 三大查询组件
-
-#### 2.2.1 FileSeriesReader 组件
-org.apache.iotdb.tsfile.read.reader.series.FileSeriesReader
-
-**功能**：该组件用于查询一个文件中单个时间序列满足过滤条件的数据点。根据给定的查询路径和被查询的文件，按照时间戳递增的顺序查询出该时间序列在文件中的所有数据点。其中过滤条件可为空。
-
-**实现**：该组件首先获取给定的路径查询出所有 Chunk 的信息，然后按照起始时间戳从小到大的顺序遍历每个 Chunk，并从中读取出满足条件的数据点。
-
-#### 2.2.2 FileSeriesReaderByTimestamp 组件
-
-org.apache.iotdb.tsfile.read.reader.series.FileSeriesReaderByTimestamp
-
-**功能**：该组件主要用于查询一个文件中单个时间序列在指定时间戳上的数据点。
-
-**实现**：该组件提供一个接口，getValueInTimestamp(long
timestamp)，通过接口依次传入递增的时间戳，返回时间序列上与该时间戳相对应的数据点。如果满足该时间戳的数据点不存在，则返回 null。
-
-#### 2.2.3 TsFileTimeGenerator 组件
-org.apache.iotdb.tsfile.read.query.timegenerator.TsFileTimeGenerator
-
-**功能**：根据“选择条件”，计算出满足该“选择条件”的时间戳，先将“选择条件”转化为一棵二叉树，然后递归地计算满足“选择条件”的时间戳。主要用于连接查询。
-
-一个可执行的过滤条件由一个或多个 SingleSeriesExpression 构成，且 SingleSeriesExpression
之间具有相应的与或关系。所以，一个可执行的过滤条件可以转为一棵表示“查询条件”的二叉树，二叉树的叶子节点（ LeafNode ）为
FileSeriesReader，中间节点为 AndNode 或 OrNode。特殊地，当可执行的过滤条件仅由一个
SingleSeriesExpression 构成时，该二叉树仅包含一个节点。得到由“选择条件”转化后的二叉树后，便可以计算“满足该选择条件”的时间戳。
-该组件提供两个基本的功能：
-
-1. 判断是否还有下一个满足“选择条件”的时间戳
-
-2. 返回下一个满足“选择条件”的时间戳
-
-
-### 2.3 归并查询
-org.apache.iotdb.tsfile.read.query.dataset.DataSetWithoutTimeGenerator
-
-设当查询 n 个时间序列，为每个时间序列构建一个 FileSeriesReader，如果有 GlobalTimeExpression，则将其中的
Filter 传入 FileSeriesReader。
-
-根据所有的 FileSeriesReader 生成一个 DataSetWithoutTimeGenerator，由于每个 FileSeriesReader
会按照时间戳从小到大的顺序迭代地返回数据点，所以可以采用“多路归并”对所有 FileSeriesReader 的结果进行按时间戳对齐。
-
-数据合并的步骤为：
-
-（1） 创建一个最小堆，堆里面存储“时间戳”，该堆将按照每个时间戳的大小进行组织。
-
-（2） 初始化堆，依次访问每一个 FileSeriesReader，如果该 FileSeriesReader
中还有数据点，则获取数据点的时间戳并放入堆中。此时每个时间序列最多有1个时间戳被放入到堆中，即该序列最小的时间戳。
-
-（3） 如果堆的 size > 0，获取堆顶的时间戳，记为t，并将其在堆中删除，进入步骤（4）；如果堆的 size
等于0，则跳到步骤（5），结束数据合并过程。
-
-（4） 创建新的 RowRecord。依次遍历每一条时间序列。在处理其中一条时间序列时，如果该序列没有更多的数据点，则将该列标记为 null 并添加在
RowRecord 中；否则，判断最小的时间戳是否与 t 相同，若不相同，则将该列标记为 null 并添加在 RowRecord 中。若相同，将该数据点添加在
RowRecord 中，同时判断该时间序列是否有新的数据点，若存在，则将下一个时间戳 t' 添加在堆中，并将 t'
设为当前时间序列的最小时间戳。最后，返回步骤（3）。
-
-（5） 结束数据合并过程。
-
-### 2.4 连接查询
-
-org.apache.iotdb.tsfile.read.query.executor.ExecutorWithTimeGenerator
-
-连接查询生成满足“选择条件”的时间戳、查询被投影列在对应时间戳下的数据点、合成 RowRecord。主要流程如下：
-
-（1） 根据 QueryExpression，初始化时间戳计算模块 TimeGeneratorImpl
-
-（2） 为每个被投影的时间序列创建 FileSeriesReaderByTimestamp
-
-（3） 如果“时间戳计算模块”中还有下一个时间戳，则计算出下一个时间戳 t ，进入步骤（4）；否则，结束查询。
-
-（4） 根据 t，在每个时间序列上使用 FileSeriesReaderByTimestamp 组件获取在时间戳 t
下的数据点；如果在该时间戳下没有对应的数据点，则用 null 表示。
-
-（5） 将步骤（4）中得到的所有数据点合并成一个 RowRecord，此时得到一条查询结果，返回步骤（3）计算下一个查询结果。
-
-
-### 2.5 查询入口
-
- org.apache.iotdb.tsfile.read.query.executor.TsFileExecutor
-
-TsFileExecutor 接收一个 QueryExpression ，执行该查询并返回相应的 QueryDataSet。基本工作流程如下：
-
-（1）接收一个 QueryExpression
-
-（2）如果无过滤条件，执行归并查询。如果该 QueryExpression 包含 Filter（过滤条件），则通过 ExpressionOptimizer
对该 QueryExpression 的 Filter 进行优化。如果是 GlobalTimeExpression，执行归并查询。如果包含值过滤，交给
ExecutorWithTimeGenerator 执行连接查询。
-
-（3） 生成对应的 QueryDataSet，迭代地生成 RowRecord，将查询结果返回。
-
-
-
-### 2.6 相关代码介绍
-
-* Chunk：一段时间序列的内存结构，可供 IChunkReader 进行读取。
-
-* ChunkMetaData：记录对应 Chunk 在文件中的偏移量及数据类型和编码方式，便于对 Chunk 进行读取。
-
-* IMetadataQuerier：一个 TsFile 的元数据加载器。可以加载整个文件的元数据和一个序列的所有 ChunkMetaData。
-
-* IChunkLoader： IChunkLoader 为 Chunk 的加载器，主要功能为，给定一个 ChunkMetaData，返回对应的 Chunk。
-
-* IChunkReader：对一个 Chunk 中的数据进行读取，其接收一个 Chunk，根据其中 ChunkHeader 中的相关信息，对该 Chunk
进行解析。其提供两套接口：
-
- * hasNextSatisfiedPage & nextPageData：迭代式的返回一个一个的 Page
- * getPageReaderList：一次返回所有 PageReader
-
-* IPageReader：对一个 Page 中的数据进行读取，提供两个基本的接口：
-
- * getAllSatisfiedPageData()：一次返回所有满足条件的值
- * getStatistics()：返回 Page 的统计信息
-
-* QueryExpression
-
- QueryExpression 为查询表达式，包含投影的时间序列和过滤条件。
-
-* QueryDataSet
-
- 一次查询所返回的结果，具有相同时间戳的数据点合并为一个 RowRecord。 QueryDataSet 提供两个基本的功能：
-
- * 判断是否还有下一个 RowRecord
- * 返回下一个 RowRecord
-
-
-
-
diff --git a/docs/Documentation-CHN/SystemDesign/1-TsFile/5-QueryExecution.md
b/docs/Documentation-CHN/SystemDesign/1-TsFile/5-QueryExecution.md
new file mode 100644
index 0000000..0852429
--- /dev/null
+++ b/docs/Documentation-CHN/SystemDesign/1-TsFile/5-QueryExecution.md
@@ -0,0 +1,164 @@
+<!--
+
+ Licensed to the Apache Software Foundation (ASF) under one
+ or more contributor license agreements. See the NOTICE file
+ distributed with this work for additional information
+ regarding copyright ownership. The ASF licenses this file
+ to you under the Apache License, Version 2.0 (the
+ "License"); you may not use this file except in compliance
+ with the License. You may obtain a copy of the License at
+
+ http://www.apache.org/licenses/LICENSE-2.0
+
+ Unless required by applicable law or agreed to in writing,
+ software distributed under the License is distributed on an
+ "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY
+ KIND, either express or implied. See the License for the
+ specific language governing permissions and limitations
+ under the License.
+
+-->
+
+# TsFile 查询执行过程
+
+本章节介绍 TsFile 的查询执行过程，即如何利用查询表达式得到结果集。
+
+
+* 1 设计原理
+* 2 三大查询组件
+ * 2.1 FileSeriesReader 组件
+ * 2.2 FileSeriesReaderByTimestamp 组件
+ * 2.3 TimeGeneratorImpl 组件
+* 3 归并查询
+* 4 连接查询
+* 5 查询入口
+* 6 相关代码介绍
+
+## 1 设计原理
+
+TsFile 文件层查询接口只包含原始数据查询，根据是否包含值过滤条件，可以将查询分为两类“无过滤条件或仅包含时间过滤条件查询”和“包含值过滤条件的查询”
+
+为了执行以上两类查询，有两套查询流程
+
+* 归并查询
+
+ 生成多个 reader，按照 time 对齐，返回结果集。
+
+* 连接查询
+
+ 根据查询条件生成满足过滤条件的时间戳，通过满足条件的时间戳查询投影列的值，返回结果集。
+
+## 2 三大查询组件
+
+### 2.1 FileSeriesReader 组件
+org.apache.iotdb.tsfile.read.reader.series.FileSeriesReader
+
+**功能**：该组件用于查询一个文件中单个时间序列满足过滤条件的数据点。根据给定的查询路径和被查询的文件，按照时间戳递增的顺序查询出该时间序列在文件中的所有数据点。其中过滤条件可为空。
+
+**实现**：该组件首先获取给定的路径查询出所有 Chunk 的信息，然后按照起始时间戳从小到大的顺序遍历每个 Chunk，并从中读取出满足条件的数据点。
+
+### 2.2 FileSeriesReaderByTimestamp 组件
+
+org.apache.iotdb.tsfile.read.reader.series.FileSeriesReaderByTimestamp
+
+**功能**：该组件主要用于查询一个文件中单个时间序列在指定时间戳上的数据点。
+
+**实现**：该组件提供一个接口，getValueInTimestamp(long
timestamp)，通过接口依次传入递增的时间戳，返回时间序列上与该时间戳相对应的数据点。如果满足该时间戳的数据点不存在，则返回 null。
+
+### 2.3 TsFileTimeGenerator 组件
+org.apache.iotdb.tsfile.read.query.timegenerator.TsFileTimeGenerator
+
+**功能**：根据“选择条件”，计算出满足该“选择条件”的时间戳，先将“选择条件”转化为一棵二叉树，然后递归地计算满足“选择条件”的时间戳。主要用于连接查询。
+
+一个可执行的过滤条件由一个或多个 SingleSeriesExpression 构成，且 SingleSeriesExpression
之间具有相应的与或关系。所以，一个可执行的过滤条件可以转为一棵表示“查询条件”的二叉树，二叉树的叶子节点（ LeafNode ）为
FileSeriesReader，中间节点为 AndNode 或 OrNode。特殊地，当可执行的过滤条件仅由一个
SingleSeriesExpression 构成时，该二叉树仅包含一个节点。得到由“选择条件”转化后的二叉树后，便可以计算“满足该选择条件”的时间戳。
+该组件提供两个基本的功能：
+
+1. 判断是否还有下一个满足“选择条件”的时间戳
+
+2. 返回下一个满足“选择条件”的时间戳
+
+
+## 3 归并查询
+org.apache.iotdb.tsfile.read.query.dataset.DataSetWithoutTimeGenerator
+
+设当查询 n 个时间序列，为每个时间序列构建一个 FileSeriesReader，如果有 GlobalTimeExpression，则将其中的
Filter 传入 FileSeriesReader。
+
+根据所有的 FileSeriesReader 生成一个 DataSetWithoutTimeGenerator，由于每个 FileSeriesReader
会按照时间戳从小到大的顺序迭代地返回数据点，所以可以采用“多路归并”对所有 FileSeriesReader 的结果进行按时间戳对齐。
+
+数据合并的步骤为：
+
+（1） 创建一个最小堆，堆里面存储“时间戳”，该堆将按照每个时间戳的大小进行组织。
+
+（2） 初始化堆，依次访问每一个 FileSeriesReader，如果该 FileSeriesReader
中还有数据点，则获取数据点的时间戳并放入堆中。此时每个时间序列最多有1个时间戳被放入到堆中，即该序列最小的时间戳。
+
+（3） 如果堆的 size > 0，获取堆顶的时间戳，记为t，并将其在堆中删除，进入步骤（4）；如果堆的 size
等于0，则跳到步骤（5），结束数据合并过程。
+
+（4） 创建新的 RowRecord。依次遍历每一条时间序列。在处理其中一条时间序列时，如果该序列没有更多的数据点，则将该列标记为 null 并添加在
RowRecord 中；否则，判断最小的时间戳是否与 t 相同，若不相同，则将该列标记为 null 并添加在 RowRecord 中。若相同，将该数据点添加在
RowRecord 中，同时判断该时间序列是否有新的数据点，若存在，则将下一个时间戳 t' 添加在堆中，并将 t'
设为当前时间序列的最小时间戳。最后，返回步骤（3）。
+
+（5） 结束数据合并过程。
+
+## 4 连接查询
+
+org.apache.iotdb.tsfile.read.query.executor.ExecutorWithTimeGenerator
+
+连接查询生成满足“选择条件”的时间戳、查询被投影列在对应时间戳下的数据点、合成 RowRecord。主要流程如下：
+
+（1） 根据 QueryExpression，初始化时间戳计算模块 TimeGeneratorImpl
+
+（2） 为每个被投影的时间序列创建 FileSeriesReaderByTimestamp
+
+（3） 如果“时间戳计算模块”中还有下一个时间戳，则计算出下一个时间戳 t ，进入步骤（4）；否则，结束查询。
+
+（4） 根据 t，在每个时间序列上使用 FileSeriesReaderByTimestamp 组件获取在时间戳 t
下的数据点；如果在该时间戳下没有对应的数据点，则用 null 表示。
+
+（5） 将步骤（4）中得到的所有数据点合并成一个 RowRecord，此时得到一条查询结果，返回步骤（3）计算下一个查询结果。
+
+
+## 5 查询入口
+
+ org.apache.iotdb.tsfile.read.query.executor.TsFileExecutor
+
+TsFileExecutor 接收一个 QueryExpression ，执行该查询并返回相应的 QueryDataSet。基本工作流程如下：
+
+（1）接收一个 QueryExpression
+
+（2）如果无过滤条件，执行归并查询。如果该 QueryExpression 包含 Filter（过滤条件），则通过 ExpressionOptimizer
对该 QueryExpression 的 Filter 进行优化。如果是 GlobalTimeExpression，执行归并查询。如果包含值过滤，交给
ExecutorWithTimeGenerator 执行连接查询。
+
+（3） 生成对应的 QueryDataSet，迭代地生成 RowRecord，将查询结果返回。
+
+
+
+## 6 相关代码介绍
+
+* Chunk：一段时间序列的内存结构，可供 IChunkReader 进行读取。
+
+* ChunkMetaData：记录对应 Chunk 在文件中的偏移量及数据类型和编码方式，便于对 Chunk 进行读取。
+
+* IMetadataQuerier：一个 TsFile 的元数据加载器。可以加载整个文件的元数据和一个序列的所有 ChunkMetaData。
+
+* IChunkLoader： IChunkLoader 为 Chunk 的加载器，主要功能为，给定一个 ChunkMetaData，返回对应的 Chunk。
+
+* IChunkReader：对一个 Chunk 中的数据进行读取，其接收一个 Chunk，根据其中 ChunkHeader 中的相关信息，对该 Chunk
进行解析。其提供两套接口：
+
+ * hasNextSatisfiedPage & nextPageData：迭代式的返回一个一个的 Page
+ * getPageReaderList：一次返回所有 PageReader
+
+* IPageReader：对一个 Page 中的数据进行读取，提供两个基本的接口：
+
+ * getAllSatisfiedPageData()：一次返回所有满足条件的值
+ * getStatistics()：返回 Page 的统计信息
+
+* QueryExpression
+
+ QueryExpression 为查询表达式，包含投影的时间序列和过滤条件。
+
+* QueryDataSet
+
+ 一次查询所返回的结果，具有相同时间戳的数据点合并为一个 RowRecord。 QueryDataSet 提供两个基本的功能：
+
+ * 判断是否还有下一个 RowRecord
+ * 返回下一个 RowRecord
+
+
+
+
diff --git a/docs/Documentation/SystemDesign/0-Content.md
b/docs/Documentation/SystemDesign/0-Content.md
index 2374355..8e71682 100644
--- a/docs/Documentation/SystemDesign/0-Content.md
+++ b/docs/Documentation/SystemDesign/0-Content.md
@@ -26,7 +26,8 @@
* 1-TsFile
* 2-Format
* 3-Write
-* 4-Read
+* 4-Filter
+* 5-QueryExecution
# Chapter 2: QueryEngine
* 1-QueryEngine
* 2-Planner
diff --git a/docs/Documentation/SystemDesign/1-TsFile/4-Read.md
b/docs/Documentation/SystemDesign/1-TsFile/4-Filter.md
similarity index 71%
rename from docs/Documentation/SystemDesign/1-TsFile/4-Read.md
rename to docs/Documentation/SystemDesign/1-TsFile/4-Filter.md
index 3c3b710..b2b6826 100644
--- a/docs/Documentation/SystemDesign/1-TsFile/4-Read.md
+++ b/docs/Documentation/SystemDesign/1-TsFile/4-Filter.md
@@ -19,32 +19,21 @@
-->
-# TsFile Read Process
-
-This chapter introduces how to read TsFile. The content is mainly divided into
two parts, the introduction of Filters and Expressions , and the detailed
illustration of query process in TsFile.
-
-- [TsFile Read Process](#TsFile-Read-Process)
- - [1 Filters and Expressions](#1-Filters-and-Expressions)
- - [1.1 Filter](#11-Filter)
- - [1.2 Expression](#12-Expression)
- - [1.2.1 SingleSeriesExpression](#121-SingleSeriesExpression)
- - [1.2.2 GlobalTimeExpression](#122-GlobalTimeExpression)
- - [1.2.3 IExpression](#123-IExpression)
- - [1.2.4 Executable Expression](#124-Executable-Expression)
- - [1.2.5 The Algorithm Transforming IExpression to an Executable
Expression](#125-The-Algorithm-Transforming-IExpression-to-an-Executable-Expression)
- - [2 Query Execution of TsFile](#2-Query-Execution-of-TsFile)
- - [2.1 Design](#21-Design)
- - [2.2 Three Components](#22-Three-Components)
- - [2.2.1 FileSeriesReader](#221-FileSeriesReader)
- - [2.2.2 FileSeriesReaderByTimestamp](#222-FileSeriesReaderByTimestamp)
- - [2.2.3 TimeGeneratorImpl](#223-TimeGeneratorImpl)
- - [2.3 Merge Query](#23-Merge-Query)
- - [2.4 Join Query](#24-Join-Query)
- - [2.5 Query of TsFile](#25-Query-of-TsFile)
- - [2.6 Related Concepts](#26-Related-Concepts)
-## 1 Filters and Expressions
-
-### 1.1 Filter
+# Filters and Query Expressions
+
+This chapter introduces Filters and Expressions, which will be used in
execution.
+
+
+- [1 Filter](#1-Filter)
+- [2 Expression](#2-Expression)
+ - [2.1 SingleSeriesExpression](#21-SingleSeriesExpression)
+ - [2.2 GlobalTimeExpression](#22-GlobalTimeExpression)
+ - [2.3 IExpression](#23-IExpression)
+ - [2.4 Executable Expression](#24-Executable-Expression)
+ - [2.5 The Algorithm Transforming IExpression to an Executable
Expression](#25-The-Algorithm-Transforming-IExpression-to-an-Executable-Expression)
+
+
+## 1 Filter
In this document, the term Filter means filter conditions. Users can customize
filter conditions on timestamp, or the value of time series. We distinguish the
filters which are on timestamp from those on column values. Assume t to be a
timestamp constant, there are 12 basic types of Filters. In implementation,
they all inherit from the super class Filter.
@@ -100,11 +89,11 @@ ValueNotEq| value != v| value != true means value should
not be true
AndFilter| \<Filter> && \<Filter>| 1. value > 100 && value < 200 means value
should be greanter than 100 and less than 200; <br>2. (value >= 100 && value <=
200) && time > 14152176545 means "value should be greater than or equal to 100
and value should be less than or equal to" and "timestamp should be greater
than 14152176545"
OrFilter| \<Filter> || \<Filter>| 1. value > 100 || time >
14152176545, means value should be greater than 100 or timestamp should be
greater than 14152176545;<br>2. (value > 100 && value < 200)|| time >
14152176545, means "value should be greater than 100 and value should be less
than 200" or "timestamp should be greater than 14152176545"
-### 1.2 Expression
+## 2 Expression
When we assign a particular time series (including the timestamp) to a Filter,
it becomes an expression. For example, "value > 10" can only describe a Filter,
without the taste of a query. However, "the value of time series 'd1.s1' should
be greater than 10" is an expression. Specifically, if the Filter only works on
timestamp, it can be seen as an expression, which is called
GlobalTimeExpression. The following sections introduces Expression in detail,
-#### 1.2.1 SingleSeriesExpression
+### 2.1 SingleSeriesExpression
SingleSeriesExpression is an expression on a time series (excluding the
timestamp column) with a Filter. A SingleSeriesExpression contains a Path and a
Filter. The Path is the path of the time series, and the Filter indicate the
filter condition, as is introduced in section 1.1.
@@ -139,7 +128,7 @@ The SingleSeriesExpression claims that time series "d1.s1"
should satisfy that "
We formalize the rule as SingleSeriesExpression("d1.s1", (value > 100 && value
< 200) && time > 14152176545)
-#### 1.2.2 GlobalTimeExpression
+### 2.2 GlobalTimeExpression
GlobalTimeExpression means a global time filter. A GlobalTimeExpression
contains a Filter, which is only composed of time filters (value filters not
allowed). When querying, a GlobalTimeExpression claims that data points of all
selected time series should satisfy the constraints in the Filter. The
structure of GlobalTimeExpression is shown below:
GlobalTimeExpression
@@ -153,7 +142,7 @@ Some formalized examples of GlobalTimeExpression are shown
below:
1. GlobalTimeExpression(time > 14152176545 && time < 14152176645) claims that
the all selected time series should satisfy that the timestamp should be
"greater than 14152176545 and less than 14152176645"
2. GlobalTimeExpression((time > 100 && time < 200) || (time > 400 && time <
500)) claims that all selected time series should satisfy that the timestamp
should be "greater than 100 and less than 200" or "greater than 400 and less
than 500"
-#### 1.2.3 IExpression
+### 2.3 IExpression
IExpression indicates the all filters with the corresponding columns in a
query.
An IExpression can be a SingleSeriesExpression or a GlobalTimeExpression. In
this case, the IExpression is a UnaryExpression. An IExpression can also
contains two IExpressions, connected with relation AND or OR. Two IExpressions
joined with AND relation is termed as AndExpression. Likewise, two IExpressions
joined with OR relation is termed as OrExpression. An IExpression containing
two children is termed BinaryExpression. UnaryExpression and BinaryExpression
are both IExpression.
@@ -195,7 +184,7 @@ We use a tree-like structure to formalize an IExpression.
Here are some examples
**Note**: The IExpression is an AndExpression, where the time series
"d1.s1" and "d1.s2" should not only satisfy the constraints in corresponding
Filters in SingleSeriesExpression, but also the constraints of the
GlobalTimeExpression.
-#### 1.2.4 Executable Expression
+### 2.4 Executable Expression
To make the query execution more comprehensible, we give the concept of
executable expression. An executable expression is a particular kinds of
IExpression. The IExpression customized by system user can be transformed to an
executable expression by some algorithm, which will be introduced in the
following sections. An executable expression is an IExpression satisfying one
of the following constraints:
1. The IExpression is a single GlobalTimeExpression
@@ -274,7 +263,7 @@ Is an executable expression? No
**Hint**: The IExpression is an AndExpression, but one of the leaf nodes is a
GlobalTimeExpression, which is against constraint 3.
-#### 1.2.5 The Algorithm Transforming IExpression to an Executable Expression
+### 2.5 The Algorithm Transforming IExpression to an Executable Expression
In this section, we introduce how to transform an IExpression to be executable.
@@ -431,129 +420,3 @@ Using the above four combination methods, the steps of
optimize() include:
c. If LeftIExpression is not a GlobalTimeExpression, while RightIExpression
is, call handleOneGlobalExpression() to combine them.
d. If neither LeftIExpression nor RightIExpression is a
GlobalTimeExpression, recursively call optimize() method on both
LeftIExpression and RightIExpression to get the left executable expression and
the right executable expression. Then use mergeIExpression method to generate a
final IExpression which is executable.
-
-## 2 Query Execution of TsFile
-
-### 2.1 Design
-
-The interface of TsFile on file level is intended only for queries on original
data. According to the existence of value filter, the query can be divided into
two groups: those without filters or only with a time filter, and those
containing value filters.
-
-To execute the two kinds of queries, we design two query execution methods:
-
-* merge query
-
- It generates multiple readers, aligns the result in time, and returns the
result set.
-
-* join query
-
- According to the query conditions, it generates satisfying timestamp,
which is used for generating result set.
-
-### 2.2 Three Components
-
-#### 2.2.1 FileSeriesReader
-org.apache.iotdb.tsfile.read.reader.series.FileSeriesReader
-
-**Functions**: FileSeriesReader queries the data points of a time series in a
file, which satisfies the filter conditions. It outputs the data points of the
given time series in the given file in timestamp ascending order. There can be
no filters at all.
-
-**Implementation**: FileSeriesReader retrieves the Chunk information of the
given time series according to the Path, it then traverses each Chunk in
timestamp ascending order, and outputs the satisfying data points.
-
-#### 2.2.2 FileSeriesReaderByTimestamp
-
-org.apache.iotdb.tsfile.read.reader.series.FileSeriesReaderByTimestamp
-
-**Functions**: FileSeriesReaderByTimestamp queries the data points of a time
series in a file, whose timestamp satisfies the timestamp constraints.
-
-**Implementation**: This component provides an interface,
getValueInTimestamp(long timestamp), which receives increasing timestamp value,
and outputs the data points on the time series whose timestamp is identical.
If there's no such data point, the result is null.
-
-#### 2.2.3 TsFileTimeGenerator
-org.apache.iotdb.tsfile.read.query.timegenerator.TsFileTimeGenerator
-
-**Functions**: According to the filter condition, TimeGeneratorImpl generates
the satisfying timestamp. It first transforms the filter conditions to be a
binary tree, and recursively generate the satisfying timestamp. This component
is used in executing join query.
-
-An executable expression contains one or nultiple SingleSeriesExpressions. The
relation between two SingleSeriesExpressions is either AND or OR. Therefore,
the filter in an executable expression can be transformed to a binary tree,
where the leaf nodes are FileSeriesReader, and the non-leaf nodes are AndNode
or OrNode. Particularly, when the expression only contains a single
SingleSeriesExpression, the binary tree only has one node. The satisfying
timestamp can be generated using the bin [...]
-
-This component provides two basic functions:
-
-1. check if there exists a next satisfying timestamp
-
-2. get the next satisfying timestamp
-
-### 2.3 Merge Query
-org.apache.iotdb.tsfile.read.query.dataset.DataSetWithoutTimeGenerator
-
-Suppose there are n time series. For each one of them, a FileSeriesReader will
be generated. If there's a GlobalTimeExpression, the filter in it will be input
to the FileSeriesReaders.
-
-A DataSetWithoutTimeGenerator will be generated using these FileSeriesReaders.
Since each FileSeriesReader outputs data points in time stamp ascending order,
we can use the idea of k-way merge to align the result data points.
-
-The steps include:
-
-(1) Create a min-heap, which stores timestamps. The min-heap is organized
according to the value of the timestamp.
-
-(2) Initialize the min-heap. Access each FileSeriesReader once. If there's a
next data point in the FileSeriesReader, add its timestamp to the min-heap.
Till now, the heap contains at most one timestamp of each time series, which is
the minimum in its corresponding time series.
-
-(3) If the size of the heap is greater than 0, take the timestamp on the top
of the heap, denote it as t, and remove it from the heap, then go to step (4).
If the number of the heap is 0, go to step (5).
-
-(4) Create a new RowRecord. In turns access each time series. When dealing
with a time series, first check if there's a next data point, if it fails, set
the result data point to be null. Otherwise, check if minimum timestamp in the
time series is identical to t. If it is not, set the result data point to be
null. Otherwise, get the data point and set it to be the result data point. If
there exists a next data point after that. If it has, then set timestamp of the
next data point in the [...]
-
-(5) Terminate the process.
-
-### 2.4 Join Query
-
-org.apache.iotdb.tsfile.read.query.executor.ExecutorWithTimeGenerator
-
-Join query execution generates timestamp according to the filter conditions,
and retrieves the data point on the projected time series to form a RowRecord.
Main steps include;
-
-(1) According to QueryExpression, initialize the timestamp generation module,
TimeGeneratorImpl
-
-(2) Generate FileSeriesReaderByTimestamp for each projected time series.
-
-(3) If there exists a next timestamp in the "timestamp generation module",
denote the timestamp t, go to step (4).Otherwise, terminate the query execution.
-
-(4) According to t, utilize FileSeriesReaderByTimestamp on each time series to
retrieve the data point whose corresponding timestamp is t. If there's no such
data point, use null to represent it.
-
-(5) Combine the data points in step (4) to form a RowRecord, then go to step
(3) to generate another row of records.
-
-### 2.5 Query of TsFile
-
- org.apache.iotdb.tsfile.read.query.executor.TsFileExecutor
-
-TsFileExecutor receives a QueryExpression, execute the query and outputs the
QueryDataSet。The work flow includes the following steps:
-
-(1) Receive a QueryExpression.
-
-(2) If the QueryExpression contains no filter conditions, execute merge query.
If it contains any Filters, use ExpressionOptimizer to optimize the IExpression
in QueryExpression. If the optimized IExpression is a GlobalTimeExpression,
execute merge query. If it contains value filters, it sends a message to
ExecutorWithTimeGenerator to execute join query.
-
-(3) Generate the QueryDataSet. It iteratively generates RowRecord and returns
the results.
-
-
-### 2.6 Related Concepts
-
-* Chunk: Chunk is the storage structure of a chunk of time series.
IChunkReader is for reading the content。
-
-* ChunkMetaData: ChunkMetaData records the offset, data type and encoding info
of the Chunk in the File.
-
-* IMetadataQuerier: IMetadataQuerier is a querier for TsFile metadata. It
queries the metadata of a file, and the ChunkMetaData of a time series.
-
-* IChunkLoader: IChunkLoader is the loader for Chunk, whose main function is
getting the corresponding Chunk of the given the ChunkMetaData.
-
-* IChunkReader: IChunkReader reads the data in a Chunk. It receives a Chunk
and parse it according to the info in the ChunkHeader. It provides two
interface:
-
- * hasNextSatisfiedPage & nextPageData: iteratively returns a Page
- * getPageReaderList: return all PageReader
-
-* IPageReader: IPageReader reads the data in a Page. It provides two interface:
-
- * getAllSatisfiedPageData(): return all satisfying values
- * getStatistics(): return the statistic information of the Page
-
-* QueryExpression
-
- QueryExpression is the query expression, which contains the time series to
project, and filter constraints.
-
-* QueryDataSet
-
- The result of a query. It contains one or multiple RowRecord, which
combines data points having identical time stamp together. QueryDataSet
provides two interface:
-
- * check if there's a next RowRecord.
- * return the next RowRecord.
-
diff --git a/docs/Documentation/SystemDesign/1-TsFile/5-QueryExecution.md
b/docs/Documentation/SystemDesign/1-TsFile/5-QueryExecution.md
new file mode 100644
index 0000000..7a5c545
--- /dev/null
+++ b/docs/Documentation/SystemDesign/1-TsFile/5-QueryExecution.md
@@ -0,0 +1,158 @@
+<!--
+
+ Licensed to the Apache Software Foundation (ASF) under one
+ or more contributor license agreements. See the NOTICE file
+ distributed with this work for additional information
+ regarding copyright ownership. The ASF licenses this file
+ to you under the Apache License, Version 2.0 (the
+ "License"); you may not use this file except in compliance
+ with the License. You may obtain a copy of the License at
+
+ http://www.apache.org/licenses/LICENSE-2.0
+
+ Unless required by applicable law or agreed to in writing,
+ software distributed under the License is distributed on an
+ "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY
+ KIND, either express or implied. See the License for the
+ specific language governing permissions and limitations
+ under the License.
+
+-->
+
+# Query Execution
+
+This chapter introduces how to answer queries using filters and query
expressions.
+
+- [1 Design](#1-Design)
+- [2 Three Components](#2-Three-Components)
+ - [2.1 FileSeriesReader](#21-FileSeriesReader)
+ - [2.2 FileSeriesReaderByTimestamp](#22-FileSeriesReaderByTimestamp)
+ - [2.3 TsFileTimeGenerator](#23-TsFileTimeGenerator)
+- [3 Merge Query](#3-Merge-Query)
+- [4 Join Query](#4-Join-Query)
+- [5 Query of TsFile](#5-Query-of-TsFile)
+- [6 Related Concepts](#6-Related-Concepts)
+
+## 1 Design
+
+The interface of TsFile on file level is intended only for queries on original
data. According to the existence of value filter, the query can be divided into
two groups: those without filters or only with a time filter, and those
containing value filters.
+
+To execute the two kinds of queries, we design two query execution methods:
+
+* merge query
+
+ It generates multiple readers, aligns the result in time, and returns the
result set.
+
+* join query
+
+ According to the query conditions, it generates satisfying timestamp,
which is used for generating result set.
+
+## 2 Three Components
+
+### 2.1 FileSeriesReader
+org.apache.iotdb.tsfile.read.reader.series.FileSeriesReader
+
+**Functions**: FileSeriesReader queries the data points of a time series in a
file, which satisfies the filter conditions. It outputs the data points of the
given time series in the given file in timestamp ascending order. There can be
no filters at all.
+
+**Implementation**: FileSeriesReader retrieves the Chunk information of the
given time series according to the Path, it then traverses each Chunk in
timestamp ascending order, and outputs the satisfying data points.
+
+### 2.2 FileSeriesReaderByTimestamp
+
+org.apache.iotdb.tsfile.read.reader.series.FileSeriesReaderByTimestamp
+
+**Functions**: FileSeriesReaderByTimestamp queries the data points of a time
series in a file, whose timestamp satisfies the timestamp constraints.
+
+**Implementation**: This component provides an interface,
getValueInTimestamp(long timestamp), which receives increasing timestamp value,
and outputs the data points on the time series whose timestamp is identical.
If there's no such data point, the result is null.
+
+### 2.3 TsFileTimeGenerator
+org.apache.iotdb.tsfile.read.query.timegenerator.TsFileTimeGenerator
+
+**Functions**: According to the filter condition, TimeGeneratorImpl generates
the satisfying timestamp. It first transforms the filter conditions to be a
binary tree, and recursively generate the satisfying timestamp. This component
is used in executing join query.
+
+An executable expression contains one or nultiple SingleSeriesExpressions. The
relation between two SingleSeriesExpressions is either AND or OR. Therefore,
the filter in an executable expression can be transformed to a binary tree,
where the leaf nodes are FileSeriesReader, and the non-leaf nodes are AndNode
or OrNode. Particularly, when the expression only contains a single
SingleSeriesExpression, the binary tree only has one node. The satisfying
timestamp can be generated using the bin [...]
+
+This component provides two basic functions:
+
+1. check if there exists a next satisfying timestamp
+
+2. get the next satisfying timestamp
+
+## 3 Merge Query
+org.apache.iotdb.tsfile.read.query.dataset.DataSetWithoutTimeGenerator
+
+Suppose there are n time series. For each one of them, a FileSeriesReader will
be generated. If there's a GlobalTimeExpression, the filter in it will be input
to the FileSeriesReaders.
+
+A DataSetWithoutTimeGenerator will be generated using these FileSeriesReaders.
Since each FileSeriesReader outputs data points in time stamp ascending order,
we can use the idea of k-way merge to align the result data points.
+
+The steps include:
+
+(1) Create a min-heap, which stores timestamps. The min-heap is organized
according to the value of the timestamp.
+
+(2) Initialize the min-heap. Access each FileSeriesReader once. If there's a
next data point in the FileSeriesReader, add its timestamp to the min-heap.
Till now, the heap contains at most one timestamp of each time series, which is
the minimum in its corresponding time series.
+
+(3) If the size of the heap is greater than 0, take the timestamp on the top
of the heap, denote it as t, and remove it from the heap, then go to step (4).
If the number of the heap is 0, go to step (5).
+
+(4) Create a new RowRecord. In turns access each time series. When dealing
with a time series, first check if there's a next data point, if it fails, set
the result data point to be null. Otherwise, check if minimum timestamp in the
time series is identical to t. If it is not, set the result data point to be
null. Otherwise, get the data point and set it to be the result data point. If
there exists a next data point after that. If it has, then set timestamp of the
next data point in the [...]
+
+(5) Terminate the process.
+
+## 4 Join Query
+
+org.apache.iotdb.tsfile.read.query.executor.ExecutorWithTimeGenerator
+
+Join query execution generates timestamp according to the filter conditions,
and retrieves the data point on the projected time series to form a RowRecord.
Main steps include;
+
+(1) According to QueryExpression, initialize the timestamp generation module,
TimeGeneratorImpl
+
+(2) Generate FileSeriesReaderByTimestamp for each projected time series.
+
+(3) If there exists a next timestamp in the "timestamp generation module",
denote the timestamp t, go to step (4).Otherwise, terminate the query execution.
+
+(4) According to t, utilize FileSeriesReaderByTimestamp on each time series to
retrieve the data point whose corresponding timestamp is t. If there's no such
data point, use null to represent it.
+
+(5) Combine the data points in step (4) to form a RowRecord, then go to step
(3) to generate another row of records.
+
+## 5 Query of TsFile
+
+ org.apache.iotdb.tsfile.read.query.executor.TsFileExecutor
+
+TsFileExecutor receives a QueryExpression, execute the query and outputs the
QueryDataSet。The work flow includes the following steps:
+
+(1) Receive a QueryExpression.
+
+(2) If the QueryExpression contains no filter conditions, execute merge query.
If it contains any Filters, use ExpressionOptimizer to optimize the IExpression
in QueryExpression. If the optimized IExpression is a GlobalTimeExpression,
execute merge query. If it contains value filters, it sends a message to
ExecutorWithTimeGenerator to execute join query.
+
+(3) Generate the QueryDataSet. It iteratively generates RowRecord and returns
the results.
+
+
+## 6 Related Concepts
+
+* Chunk: Chunk is the storage structure of a chunk of time series.
IChunkReader is for reading the content。
+
+* ChunkMetaData: ChunkMetaData records the offset, data type and encoding info
of the Chunk in the File.
+
+* IMetadataQuerier: IMetadataQuerier is a querier for TsFile metadata. It
queries the metadata of a file, and the ChunkMetaData of a time series.
+
+* IChunkLoader: IChunkLoader is the loader for Chunk, whose main function is
getting the corresponding Chunk of the given the ChunkMetaData.
+
+* IChunkReader: IChunkReader reads the data in a Chunk. It receives a Chunk
and parse it according to the info in the ChunkHeader. It provides two
interface:
+
+ * hasNextSatisfiedPage & nextPageData: iteratively returns a Page
+ * getPageReaderList: return all PageReader
+
+* IPageReader: IPageReader reads the data in a Page. It provides two interface:
+
+ * getAllSatisfiedPageData(): return all satisfying values
+ * getStatistics(): return the statistic information of the Page
+
+* QueryExpression
+
+ QueryExpression is the query expression, which contains the time series to
project, and filter constraints.
+
+* QueryDataSet
+
+ The result of a query. It contains one or multiple RowRecord, which
combines data points having identical time stamp together. QueryDataSet
provides two interface:
+
+ * check if there's a next RowRecord.
+ * return the next RowRecord.
+
