生成查询执行计划(上)

基本概念

  • Node
    语法解析后生成AST(抽象语法树),其中的每一个节点都是一个Node(抽象类),包含的子类如下:

    • Approximate:近似查询
    • ExplainOption:表示Explain中的可选参数
    • Expression:SQL中出现的表达式
    • FrameBound:用于窗口函数中的滑动窗口参数
    • Relation:抽象类,包含多个节点或者多个节点的关系,如Union,Join
    • Select:表示查询的Select部分
    • SelectItem:表示Select中的列(AllColumns表示*)
    • SortItem:表示排序列和其类型
    • Statement:表示presto中所有可用的SQL语句
    • TableElement:表示建表语句中描述表的每一列
    • Window:表示一个窗口函数
    • WindowFrame:表示窗口函数中的滑动窗口函数
    • With:表示查询中所有的With语句
    • WithQuery:表示一个With语句
  • MetadataAPI
    提供了对元数据进行操作的接口,将不同Connector对其元数据的操作抽象为统一接口,不同的Connector都实现了ConnectorNetadata接口,包含Metadata API中元数据的操作接口。

词法和语法分析

通过sqlParser.createStatement(query)分析语法并创建Statement

  • 规则
    Presto使用ANTLR4编写SQL语法。
  • 词法分析

  • 语法分析

采用Visitor的模式进行语法分析,通过递归遍历整棵树,根据不同的Node调用不同的visit***方法,返回对应的对象,最终返回一颗抽象语法树,即Statement对象

获取QueryExecution

QueryExecution表示一次查询执行,用于启动,停止和管理一个查询,以及这个查询的相关信息。包含如下三个实现类
– DataDefinitionExecution
– SqlQueryExecution
– FailedQueryExecution

  • 获取QueryExecutionFactory
    根据不同的Statement类型,从executionFactoriesMap中获取对应Statement类型与QueryExecutionFactory实现类的关系。该Map通过Guice注入传递到SqlQueryManager中

    • DataDefinitionExecutionFactory:负责Create table等DDL操作的SQL语句
    • SqlQueryExecutionFactory:负责除了DDL操作的其他SQL语句
  • 创建QueryExecution
    1. 当上文词法语法解析错误时,或遇到未知Statement时,会返回FailedQueryExecution
    2. 调用QueryExecutionFactory.createQueryExecution(),返回对应的QueryExecution(当返回DataDefinitionExecution时,会将对应的DataDefinitionTask绑定到这个QueryExecution上)
  • 启动QueryExecution
    将QueryExecution与配置的队列规则进行匹配,如果满足条件且队列未满,就加入队列。队列查询按FIFO规则调度查询

    • 启动DataDefinitionExecution
      1. 直接调用与之绑定的DataDefinitionTask
    • 启动SqlQueryExecution
      1. 调用analyzeQuery生成查询计划
      2. 在集群上调度运行查询计划

语义分析

  • Statement分析

StatementAnalyzer对Statement进行语义分析,针对不同的Statement类型使用不同方法进行分析

  • Relation分析
    TupleAnalyzer针对Query中的Relation进行分析

    • Unnest
      Unnest语句用于展开Array,Map

      1. 分析Unnest使用的列
        使用ExpressAnalyzer分析获得每一列的类型,Array展开为单列,Mpa展开为双列
      2. 如果有With Ordinality关键字,则添加一行 bigint类型
    • Table
      1. 分析是否是With:
        • 记录Table和Query的关系
        • 获取分析With语句得到的列描述符
        • 根据TableDescriptor包含的列名和类型构造新的TableDescriptor并返回
      2. 分析是否是View:
        • 解析View并获取对应Query
        • 记录Table和Query的关系
        • 获取分析With语句得到的列描述符
        • 根据TableDescriptor包含的列名和类型构造新的TableDescriptor并返回
      3. 分析Table是否存在
        使用Metadata获取TableHandle,如果为空则:

        • 检查catalog是否存在,否则Throw
        • 检查schema是否存在
        • 如果有DUAL前缀,则抛出不再支持
        • 抛出表不存在的错误消息
      4. 构造列描述符TableDescriptor
        • 根据TableHandle获取TableMetadataColumnHandle
        • 根据每个ColumnMetadata构造Field,记录和ColumnHandle的对应关系
        • 记录TableTableHandle的对应关系
        • 构造TableDescriptor 并返回
    • AliasedRelation
      带别名的Relation

      • 获取列描述符TableDescriptor
      • 如果定义了columnNames则判断列表是否能与上述返回的描述符对应,否则抛出异常
      • 构造一个新的TableDescriptor 返回
    • SampledRelation
      对表进行抽样

      • 异常处理
        • 新版本不再支持Stratify on预发
        • 抽样比例表达式不能包含抽样表的列名
        • 抽样比例计算结果必须为数值
        • 抽样比例必须>=0
        • 当抽样类型无诶BERNOULLI 和 SYSTEM;或者为POISSONIZED且指定了RESCALED时,抽样比例必须<=100
      • 获取记录抽样表的列描述符
      • 记录抽样比例
    • TableSubquery
      子查询即使用分析Query返回的列描述符
    • QuerySpecification
      1. 分析From语句,存在则返回子查询列描述符,否咋返回空
      2. 如果Where存在
        • 包含聚合或窗口函数则抛出异常
        • 分析Where字句,记录过滤条件
        • 如果Where子句输出的不是BOOLEAN或者NULL,则报错
        • 记录QuerySpecification和Where的对应关系
      3. 分析Select子句
        返回FieldOrExpression的列表,每一项代表一个列,存储了索引下标或者该列表达式。对于Select子句的每一项,执行:

        • 如果列为* 或者 T.* 则找到列描述符中相关Field,存入FieldOrExpression
        • 如果为单列,则使用表达式分析器进行分析,并存入列表达式
      4. 分析GroupBy子句
        返回FieldOrExpression的列表。对于GroupBy子句的每一项,执行:

        • 如果列为Long类型,则查找Select子句返回的FieldOrExpression列表,返回一个FieldOrExpression
        • 如果是表达式,则使用表达式分析器进行分析,并存入列表达式
        • 如果包含窗口和聚合操作,报错
        • 如果列类型不可比较,报错
      5. 分析OrderBy子句
        返回FieldOrExpression的列表。先获取Select子句的别名信息,再循环OrderBy的每一项

        • 如果列为QualifiedNameReference且无前缀,则从Select子句中查找
        • 如果列为Long类型,则则查找Select子句返回的FieldOrExpression列表,返回一个FieldOrExpression
        • 如果是表达式,则使用表达式分析器进行分析,得到FieldOrExpression
        • 如果上述列不可排序,报错
        • 如果有Select Distinct语句,且OrderBy列不是Select列的子集,报错
      6. Hiving子句
        • 使用表达式分析器进行分析,如果不是Boolean或者Unknown类型,则报错
      7. 分析聚合操作
        记录聚合操作并检验聚合操作的有效性

        • 获取Select,OrderBy,Having中的聚合函数或窗口函数
        • 如果聚合中有Distinct且Sql为近似查询,报错
        • 对Select,OrderBy,Having字句应用表达式验证
        • 如果某些列没有应用聚合或窗口函数,且不再GroupBy中,报错
      8. 分析窗口函数
        • 解析出Select,OrderBy中的所有窗口函数,并检验语法是否合法
        • 分析窗口函数中是否嵌套了其他的窗口函数,报错
        • 如果窗口函数中有Distinct 报错
        • 检验窗口函数WindowFrame属性有效性
        • 获取每个参数并与系统中注册的窗口函数比对,如果找不到对应函数则报错
      9. 获取输出的列描述符
        根据From的子语句的输出列和Select中的输出列,计算得出最终需要输出的列描述符
    • Union
      • 检验Union的语句个数是否大于等于2
      • 分析第一个子句,获取列描述符
      • 分许余下子句,并与第一个子句的列描述符比对,如果数量或者类型不匹配则报错
    • Intersect
      不支持
    • Except
      不支持
    • Join
      1. 获取Join的链接条件,如果为自然链接 报错
      2. 对Join左右的relation分别进行分析,获取列描述符
      3. 如果Join两边有重复的列名或列别名,报错
      4. 合并两侧的列描述符,作为Join的输出列描述符
      5. 如果Join类型为CrossJoin或者ImplicitJoin则输出上述描述符,否则继续
      6. 如果Join条件为Join Using,则对于Using中的每一行
        • 分析Join两边的列表达式
        • 如果类型不匹配则添加类型转换
        • 根据这些列拼成普通的相等比较的JoinOn语句并记录
      7. 如果Join条件为JoinOn
        • 分析JoinOn条件的表达式
        • 如果链接条件中有聚合或窗口函数,报错
        • 对链接条件语句进行标准化(时间函数和If转化为Case when等)
        • 对上一步的语句应用ExpressionInterpreter优化
        • 使用 0=0 或 0=1 替换转化为布尔值的表达式
        • 如果最终条件语句不是布尔值,报错
        • 使用表达式分析器重新分析优化后的语句,避免类型转换异常
        • 针对每一组链接条件,区别其中表达式属于左表还是右表,并分别进行分析
      8. 如果不是上述的Join种类 则报错
      9. 记录以上合并后的列描述符
    • Values
      • 获取每行每一个元素的类型
      • 获取每列中所有元素的共同超类([double,bigint] -> double)
      • 将不是超类的类型转换为超类
      • 根据每一列转换后的类型返回列描述符
  • 表达式分析
    使用ExpressionAnalyzer对Sql语句中的表达式进行分析。主要功能:

    • 获取表达式类型
    • 获取需要进行类型转换的表达式和转换的目的类型
    • 获取表达式中的函数信息
    • 获取表达式中合法的列名和对应的编号
    • 获取表达式IN语句中的子查询