qiaojialin commented on a change in pull request #713: [IOTDB-418] New series
reader
URL: https://github.com/apache/incubator-iotdb/pull/713#discussion_r377466069
##########
File path: docs/Documentation-CHN/SystemDesign/1-TsFile/4-Read.md
##########
@@ -21,7 +21,545 @@
# TsFile 读流程
-* org.apache.iotdb.tsfile.read.*
+本章节介绍 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
+
+Filter 表示基本的过滤条件。用户可以在时间戳上、或某一列的值上给出具体的过滤条件。将时间戳和列值的过滤条件加以区分后，设 t
表示某一时间戳常量，Filter 有以下12种基本类型，在实现上是继承关系。
+
+Filter|类型|含义|示例
+----|----|---|------
+TimeEq|时间过滤条件|时间戳等于某个值|TimeEq(t)，表示时间戳等于 t
+TimeGt|时间过滤条件|时间戳大于某个值|TimeGt(t)，表示时间戳大 t
+TimeGtEq|时间过滤条件|时间戳大于等于某个值|TimeGtEq(t)，表示时间戳大于等 t
+TimeLt|时间过滤条件|时间戳小于某个值|TimeLt(t)，表示时间戳小 t
+TimeLtEq|时间过滤条件|时间戳小于等于某个值|TimeLtEq(t)，表示时间戳小于等 t
+TimeNotEq|时间过滤条件|时间戳不等于某个值|TimeNotEq(t)，表示时间戳不等 t
+ValueEq|值过滤条件|该列数值等于某个值|ValueEq(2147483649)，表示该列数值等于2147483649
+ValueGt|值过滤条件|该列数值大于某个值|ValueGt(100.5)，表示该列数值大于100.5
+ValueGtEq|值过滤条件|该列数值大于等于某个值|ValueGtEq(2)，表示该列数值大于等于2
+ValueLt|值过滤条件|该列数值小于某个值|ValueLt("string")，表示该列数值字典序小于"string"
+ValueLtEq|值过滤条件|该列数值小于等于某个值|ValueLtEq(-100)，表示该列数值小于等于-100
+ValueNotEq|值过滤条件|该列数值不等于某个值|ValueNotEq(true)，表示该列数值的值不能为true
+
+Filter 可以由一个或两个子 Filter 组成。如果 Filter 由单一 Filter 构成，则称之为一元过滤条件，及 UnaryFilter
。若包含两个子 Filter，则称之为二元过滤条件，及 BinaryFilter。在二元过滤条件中，两个子 Filter
之间通过逻辑关系“与”、“或”进行连接，前者称为 AndFilter，后者称为 OrFilter。AndFilter 和 OrFilter
都是二元过滤条件。UnaryFilter 和 BinaryFilter 都是 Filter。
+
+下面给出一些 AndFilter 和 OrFilter 的示例，其中“&&”表示关系“与”，“||”表示关系“或”。
+
+1. AndFilter(TimeGt(100), TimeLt(200)) 表示“timestamp > 100 && timestamp < 200”
+2. AndFilter (TimeGt(100), ValueGt(0.5)) 表示“timestamp > 100 && value > 0.5”
+3. AndFilter (AndFilter (TimeGt(100), TimeLt(200)), ValueGt(0.5))
表示“(timestamp > 100 && timestamp < 200) && value > 0.5”
+4. OrFilter(TimeGt(100), ValueGt(0.5)) 表示“timestamp > 100 || value > 0.5”
+5. OrFilter (AndFilter(TimeGt(100), TimeLt(200)), ValueGt(0.5)) 表示“(timestamp
> 100 && timestamp < 200) || value > 0.5”
+
+下面，给出“Filter”、“AndFilter”和“OrFilter”的形式化定义：
+
+ Filter := Basic Filter | AndFilter | OrFilter
+ AndFilter := Filter && Filter
+ OrFilter := Filter && Filter
+
+为了便于表示，下面给出 Basic Filter、AndFilter 和 OrFilter 的符号化表示方法，其中 t 表示数据类型为 INT64
的变量；v表示数据类型为 BOOLEAN、INT32、INT64、FLOAT、DOUBLE 或 BINARY 的变量。
+
+<style> table th:nth-of-type(2) { width: 150px; } </style>
+名称|符号化表示方法|示例
+----|------------|------
+TimeEq| time == t| time == 14152176545，表示 timestamp 等于 14152176545
+TimeGt| time > t| time > 14152176545，表示 timestamp 大于 14152176545
+TimeGtEq| time >= t| time >= 14152176545，表示 timestamp 大于等于 14152176545
+TimeLt| time < t| time < 14152176545，表示 timestamp 小于 14152176545
+TimeLtEq| time <= t| time <= 14152176545，表示 timestamp 小于等于 14152176545
+TimeNotEq| time != t| time != 14152176545，表示 timestamp 等于 14152176545
+ValueEq| value == v| value == 10，表示 value 等于 10
+ValueGt| value > v| value > 100.5，表示 value 大于 100.5
+ValueGtEq| value >= v| value >= 2，表示 value 大于等于 2
+ValueLt| value < v| value < “string”，表示 value [1e小于“string”
+ValueLtEq| value <= v| value <= -100，表示 value 小于等于-100
+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表达式
+
+当给过滤条件赋予一定的时间序列含义时，我们就可以得到表达式。例如，“数值大于10”仅表示过滤条件，无实际的查询意义；然而“序列‘d1.s1’的数值大于10”就一条表达式。特殊地，如果仅对时间戳做限定的过滤条件，由于本身具有“时间戳”这一属性，可以构成表达式，称为
GlobalTimeExpression。以下章节将对表达式进行展开介绍。
+
+#### 1.2.1 SingleSeriesExpression表达式
+
+SingleSeriesExpression 表示针对某一指定时间序列的过滤条件，一个 SingleSeriesExpression 包含一个 Path
和一个 Filter。Path 表示该时间序列的路径；Filter 即为2.1章节中介绍的 Filter，表示相应的过滤条件。
+
+SingleSeriesExpression 的结构如下：
+
+ SingleSeriesExpression
+ Path: 该 SingleSeriesExpression 指定的时间序列的路径
+ Filter：过滤条件
+
+在一次查询中，一个 SingleSeriesExpression 表示该时间序列的数据点必须满足 Filter所表示的过滤条件。下面给出
SingleSeriesExpression 的示例及对应的表示方法。
+
+例1.
+
+ SingleSeriesExpression
+ Path: "d1.s1"
+ Filter: AndFilter(ValueGt(100), ValueLt(200))
+
+该 SingleSeriesExpression 表示"d1.s1"这一时间序列必须满足条件“值大于100且值小于200”。
+
+其符号化的表达方式为：SingleSeriesExpression(“d1.s1”, value > 100 && value < 200)
+
+---------------------------
+例2.
+
+ SingleSeriesExpression
+ Path：“d1.s1”
+ Filter：AndFilter(AndFilter(ValueGt(100), ValueLt(200)),
TimeGt(14152176545))
+
+该 SingleSeriesExpression 表示"d1.s1"这一时间序列必须满足条件“值大于100且小于200且时间戳大于14152176545”。
+
+其符号化表达方式为：SingleSeriesExpression(“d1.s1”, (value > 100 && value < 200) && time
> 14152176545)
+
+#### 1.2.2 GlobalTimeExpression 表达式
+GlobalTimeExpression 表示全局的时间过滤条件，一个 GlobalTimeExpression 包含一个 Filter，且该 Filter
中包含的子 Filter 必须全为时间过滤条件。在一次查询中，一个 GlobalTimeExpression 表示所有被选择列的数据点必须满足该表达式中
Filter 所表示的过滤条件。GlobalTimeExpression 的结构如下：
+
+
+ GlobalTimeExpression
+ Filter: 由一个或多个时间过滤条件组成的 Filter。
+ 此处的Filter形式化定义如下：
+ Filter := TimeFilter | AndExpression | OrExpression
+ AndExpression := Filter && Filter
+ OrExpression := Filter && Filter
+
+下面给出 GlobalTimeExpression 的一些例子，均采用符号化表示方法。
+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 表达式
+IExpression 表示一次查询的所有列上的过滤条件总和。一个 IExpression 可以是一个 SingleSeriesExpression
或者一个 GlobalTimeExpression，这种情况下，IExpression 也称为一元表达式，即 UnaryExpression。一个
IExpression 也可以由两个 IExpression
通过逻辑关系“与”、“或”进行连接。通过关系“与”连接得到的表达式又称为“与表达式”，即“AndExpression”。同理，通过关系“或”连接的表达式称为“或表达式”，即“OrExpression”。由两个
IExpression 连接成的表达式又称为二元表达式，即 BinaryExpression。一元表达式、二元表达式都是 IExpression。
+
+下面给出 IExpression 的形式化定义。
+
+ IExpression := SingleSeriesExpression | GlobalTimeExpression |
AndExpression | OrExpression
+ AndExpression := IExpression && IExpression
+ OrExpression := IExpression || IExpression
+
+我们采用一种类似于树形结构的表示方法来表示 IExpression，其中 SingleSeriesExpression 和
GlobalTimeExpression 均采用上文中介绍的符号化表示方法。下面给出示例。
+
+1. 只包含一个 SingleSeriesExpression 的 IExpression：
+
+ IExpression(SingleSeriesExpression(“d1.s1”, value > 100 && value <
200))
+
+2. 只包含一个 GlobalTimeExpression 的 IExpression：
+
+ IExpression(GlobalTimeExpression (time > 14152176545 && time <
14152176645))
+3. 包含多个 SingleSeriesExpression 的 IExpression：
+
+ IExpression(
+ AndExpression
+ SingleSeriesExpression(“d1.s1”, (value > 100 && value < 200)
|| time > 14152176645)
+ SingleSeriesExpression(“d1.s2”, value > 0.5 && value < 1.5)
+ )
+
+ **解释**：该 IExpression 为一个 AndExpression，其中要求"d1.s1"和"d1.s2"必须同时满足其对应的
Filter。
+
+4. 同时包含 SingleSeriesExpression 和 GlobalTimeExpression 的 IExpression
+
+ IExpression(
+ AndExpression
+ AndExpression
+ SingleSeriesExpression(“d1.s1”, (value > 100 && value <
200) || time > 14152176645)
+ SingleSeriesExpression(“d1.s2”, value > 0.5 && value < 1.5)
+ GlobalTimeExpression(time > 14152176545 && time < 14152176645)
+ )
+
+ **解释**：该 IExpression 为一个 AndExpression，其要求"d1.s1"和"d1.s2"必须同时满足其对应的
Filter，且时间列必须满足 GlobalTimeExpression 定义的 Filter 条件。
+
+
+#### 1.2.4 可执行表达式
+
+便于理解执行过程，定义可执行表达式的概念。可执行表达式是带有一定限制条件的 IExpression。用户输入的查询条件或构造的 IExpression
将经过特定的优化算法（该算法将在后面章节中介绍）转化为可执行表达式。满足下面任意条件的 IExpression 即为可执行表达式。
+1. IExpression 为单一的 GlobalTimeExpression
+2. IExpression 为单一的 SingleSeriesExpression
+3. IExpression 为 AndExpression，且叶子节点均为 SingleSeriesExpression
+4. IExpression 为 OrExpression，且叶子节点均为 SingleSeriesExpression
+
+可执行表达式的形式化定义为：
+
+ executable expression := SingleSeriesExpression| GlobalTimeExpression |
AndExpression | OrExpression
+ AndExpression := < ExpressionUNIT > && < ExpressionUNIT >
+ OrExpression := < ExpressionUNIT > || < ExpressionUNIT >
+ ExpressionUNIT := SingleSeriesExpression | AndExpression | OrExpression
+
+下面给出 一些可执行表达式和非可执行表达式的示例：
+
+例1：
+
+ IExpression(SingleSeriesExpression(“d1.s1”, value > 100 && value < 200))
+
+是否为可执行表达式：是
+
+**解释**：该 IExpression 为一个 SingleSeriesExpression，满足条件1
+
+----------------------------------
+例2：
+
+ IExpression(GlobalTimeExpression (time > 14152176545 && time <
14152176645))
+
+是否为可执行表达式：是
+
+**解释**：该 IExpression 为一个 GlobalTimeExpression，满足条件2
+
+-----------------------
+例3：
+
+ IExpression(
+ AndExpression
+ GlobalTimeExpression (time > 14152176545)
+ GlobalTimeExpression (time < 14152176645)
+ )
+
+是否为可执行表达式：否
+
+**解释**：该 IExpression 为一个 AndExpression，但其中包含了 GlobalTimeExpression，不满足条件3
+
+--------------------------
+
+例4：
+
+ IExpression(
+ OrExpression
+ AndExpression
+ SingleSeriesExpression(“d1.s1”, (value > 100 && value < 200)
|| time > 14152176645)
+ SingleSeriesExpression(“d1.s2”, value > 0.5 && value < 1.5)
+ SingleSeriesExpression(“d1.s3”, value > “test” && value < “test100”)
+ )
+
+是否为可执行表达式：是
+
+**解释**：该 IExpression 作为一个 OrExpression，其中叶子结点都是 SingleSeriesExpression，满足条件4.
+
+----------------------------
+
+例5：
+
+ IExpression(
+ AndExpression
+ AndExpression
+ SingleSeriesExpression(“d1.s1”, (value > 100 && value < 200)
|| time > 14152176645)
+ SingleSeriesExpression(“d1.s2”, value > 0.5 && value < 1.5)
+ GlobalTimeExpression(time > 14152176545 && time < 14152176645)
+ )
+
+是否为可执行表达式：否
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:
us...@infra.apache.org
With regards,
Apache Git Services
