逻辑查询计划重构优化

       目前，IoTDB在查询引擎的逻辑查询计划上主要存在以下几个问题：

2.1.1 存在问题

  • 类继承关系设计不合理

       如下图2.2所示，当前逻辑查询运算符 QueryOperator 继承自SFWOperator，后者代表由Select、From、Where三个子句组成的逻辑运算符。一般来说，只有查询语句会同时包含这三个部分。但是由于IoTDB特殊的数据模型，Select子句中会包含时间序列的后缀路径，而From子句中会包含时间序列的前缀路径，为了能够简便的使用Select或From运算符中的路径存储结构，Insert或Delete等语句的逻辑运算符也继承了这一基类。这种继承关系的抽象显然是不合理的，造成了结构的混乱和存储的冗余，应该根据每个语句的实际情况增加相应的成员变量，例如DeleteDataOperator内只需要增加完整路径的数组即可。

图2.2 Queryoperator 类继承关系图

  • 类抽象不合理

       在IoTDB中，查询语句主要由四部分构成：Select子句、From子句、Where子句以及特殊声明部分，特殊声明部分主要包括特殊查询类型的声明，如Group by降采样查询，以及一些特殊限制声明，如limit子句，order by子句等。上文中已经说到，QueryOperator继承自SFWOperator，其中存储了Select、From以及Where三个部分，而QueryOperator内则主要存储了特殊声明部分，如下图2.3所示。

       但是QueryOperator并没有进行良好的抽象，随着IoTDB查询类型和查询功能不断增多，导致其内部结构逐渐复杂和臃肿，各类查询的特殊声明都聚集在一起，例如下图中第一个红框内代表Group by查询的特殊声明，而第二个红框内代表Fill查询的特殊声明。这种冗杂在一起的存储，不仅造成了内部存储的冗余，同时也必须为每一种查询类型建立一个标志位以在外部判断，从而造成了外部结构的混乱，导致了大量的冗余判断。

图2.3 QueryOperator内部成员变量图

  • 类内部存储结构不合理

       以SelectOperator为例，其内部存储结构如下图2.4所示。Select子句中一般包含后缀路径、聚合函数、UDF函数等部分，这里将这些部分进行分开存储。但是，这种存储结构把过多的判断交给了外部，首先需要用标志位判断查询类型，然后再对相应的数据结构进行对应操作，造成外部逻辑混乱，难以理解。

       一般，原始数据查询只会包含后缀路径，聚合函数会在聚合查询和降采样查询时出现，而UDF函数只会出现在UDF查询中。如果可以将这些分开存储的部分抽象为一个整体，而把这些部分作为子类，并利用多态重写基类方法，就可以将外部的判断和操作移到各部分内部进行，大幅减少外部逻辑判断，优化整体代码结构。

图2.4 SelectOperator内部存储结构图

2.1.2 解决方案

       首先，Insert和Delete等运算符继承SFWOperator是没有必要的，因此计划为其增加需要的路径变量后，直接作为基类Operator的子类。此时，只有QueryOperator继承自SFWOperator，因此可以将SFWOperator内部的成员变量，即Select、From、Where部分，直接移至QueryOperator，从而移除SFWOperator。

       对于QueryOperator内部的特殊声明部分，计划先将其抽象为一个整体，即SpeicalClauseComponent类，然后对于不同的查询特殊声明，再实现各自的子类。由此，QueryOperator包含如下图2.5所示的4个部分，简洁清晰。

图2.5 QueryOperator优化后内部成员变量图

       其次，我们计划为每一种查询类型实现一个逻辑运算符作为QueryOperator的子类，利用多态可以将外部的合法性判断、物理计划转化等操作都移至各个子类运算符内部进行，从而大幅减少外部判断逻辑，方便扩展和维护。其具体实现思路如下所示：

       查询语句的 SQL 解析按顺序主要分为 4 个部分：解析 SELECT 子句； 解析 FROM 子句；解析 WHERE 子句；解析 WHERE 子句后的特殊声明 SpecialClause（如 Group by，Limit 等）。在查询语句中，一部分查询的类型是由第一部分确定的，另一部分查询的类型是由第四部分确定的。如聚合查询, "select count(s1) from root.sg.d1"，显然由 SELECT 子句，即第一部分确定。而降采样查询，"select count(s1) from root.sg.d1 group by ([1, 10), 2ms)"，则由第四部分确定。因此，我们重点关注第一部分和第四部分。

       此前，查询SQL解析是按照 "SELECT -> FROM -> WHERE -> SpecialClause" 的顺序进行解析，这显然不再合理，因为没办法提前知道由第四部分决定的查询类型。因此，计划修改解析顺序为，"SpecialClause -> SELECT -> FROM -> WHERE"，这种解析顺序可以提前知道每一种查询的类型并新建该逻辑运算符。

       当前IoTDB中共有8种查询类型，其中由第一部分决定的查询类型有4种，分别是：原始数据查询、聚合查询、最新数据点last查询、用户自定义函数UDF查询；由第四部分决定的查询类型同样有4种，分别是：降采样查询，降采样自动填充查询、自动填充查询、按设备对齐查询。

       我们首先来看由第四部分确定的4种查询，这四种查询的主要区别在于特殊声明部分不同。我们计划先将所有查询共有的特殊声明部分抽象为SpecialClauseComponent，其中包括行数限制，行偏移量限制，是否需要包含空值列等信息。然后，再分别为这四种查询建立特殊声明子类，存储这些查询特有的信息。需要特别说明的是，AlignByDevice即按设备对齐查询是IoTDB为了满足用户对于关系表的需要设计的另一种结果集展示方式，其以时间和设备为主键，先按设备对齐，设备内再按时间对齐。该查询本质上可能是任意查询，差别仅在于结果集展示方式的不同。因此，我们计划将其作为特殊声明基类中的一个公共字段，可以与任何查询作笛卡尔积，而不是作为一个单独的特殊声明子类。

      

图2.6 特殊声明部分类继承结构图

       接着来看由第一部分确定的四种查询，这四种查询的主要区别自在于Select部分的对外表现不同，例如原始数据查询只包含时间序列路径，而聚合查询中还包含聚合函数。我们计划将原本分开的部分抽象为一个整体ResultColumn类，其可以根据Select部分有不同的子类表现形式，具体如下图所示（具体见宇荣部分）：

图2.7 ResultColumn及Expression部分成员结构图

       由此，我们对IoTDB每个查询的内部变量进行了重新设计，接下来我们需要为每个查询新建外部的逻辑运算符，其继承结构如下图所示：

图2.8 QueryOperator 继承结构图

       最后，我们得到的整体的类图，如下图所示：

图2.9 逻辑查询计划设计总类图



Select 子句

antlr语法定义

resultColumn
 : expression (AS ID)?
;

expression
 : LR_BRACKET unary=expression RR_BRACKET
 | (PLUS | MINUS) unary=expression
 | leftExpression=expression (STAR | DIV | MOD) rightExpression=expression
 | leftExpression=expression (PLUS | MINUS) rightExpression=expression
 | functionName=suffixPath LR_BRACKET expression (COMMA expression)* functionAttribute* RR_BRACKET
 | suffixPath
 | literal=SINGLE_QUOTE_STRING_LITERAL
 ;

functionAttribute
 : COMMA functionAttributeKey=stringLiteral OPERATOR_EQ functionAttributeValue=stringLiteral
 ;


数据结构

ResultColumn

包含Expression和alias两个字段，封装了对Expression的操作。


Expression

本质是ANTLR语法树的内存镜像。

BinaryExpression

  • expression (STAR | DIV | MOD) expression
    • 示例：a*b → MultiplicationExpression,   a/b → DivisionExpression,   a%3 → ModuloExpression
  • expression (PLUS | MINUS) expression
    • 示例：a+b → AdditionExpression,  a-b → SubtractionExpression

FunctionExpression

  • suffixPath LR_BRACKET expression (COMMA expression)* functionAttribute* RR_BRACKET
    • 示例： udf(a, b),  count(a)

MinusExpression

  •  MINUS expression 
    • 示例： -a

TimeSeriesOperand

  •  PLUS expression 
  •  suffixPath
    • 示例： +a, a
  • No labels