CMU Peloton Optimizer

Posted on | In

优化器

BuildParseTree

  • libpg_query：裁剪出的postgresql的语法解析和词法解析。

  • BuildParseTree：对parser生成的语法树进行解析，得到SelectStatement，其中记录了语句的各个组件。

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    class SelectStatement : public SQLStatement {
      std::unique_ptr<TableRef> from_table;
      bool select_distinct;
      std::vector<std::unique_ptr<expression::AbstractExpression>> select_list;
      std::unique_ptr<expression::AbstractExpression> where_clause;
      std::unique_ptr<GroupByDescription> group_by;

      std::unique_ptr<SelectStatement> union_select;
      std::unique_ptr<OrderDescription> order;
      std::unique_ptr<LimitDescription> limit;
    };

BindNameToNode

  • 主要是用于检查SelectStatement中涉及的列的合法性，并将列的属性（如属于哪一张表）填入各表达式。

BuildPelotonPlanTree

Optimizer::InsertQueryTree

  • QueryToOperatorTransformer::ConvertToOpExpression：将SelectStatement转换为一棵树。树中节点如下

    • LogicalQueryDerivedGet：用于from中的子查询。
    • LogicalInnerJoin：默认对from中的表进行Join，解析到from时会生成join树，不带条件。
      • 如果from中显示的指定了哪一类Join，会生成对应类型的Join，如LogicalLeftJoin。
    • LogicalGet：递归解析from中的元素时会解析到底层的TableRef，生成此节点。
    • LogicalFilter：根据where中的谓词生成。having子句也会生成LogicalFilter。
    • LogicalMarkJoin：用于IN和EXISTS子链接。
    • LogicalSingleJoin：用于expr op sublink，op为比较运算符时生成。
    • LogicalAggregateAndGroupBy
    • LogicalDistinct：单独的节点，在LogicalAggregateAndGroupBy之后生成。
    • LogicalLimit：在LogicalDistinct后生成。

  • OptimizerMetadata::RecordTransformedExpression：

    • 将上一步生成的树中的节点逐个转换为group_expression，每个group_expression。
      • 封装层次：Group <- GroupExpression <- Operator <- BaseOperatorNode <- <LogicalFilter...>

Optimizer::GetQueryInfo

  • 提取output_exprs和sort_exprs作为后面优化的参考。

Optimizer::OptimizeLoop

  • 通过TaskStack来遍历树，具体规则应用顺序：

    • BottomUpRewrite -> TopDownRewrite -> DeriveStats -> OptimizeGroup

  • BottomUpRewrite和 TopDownRewrite 都是应用规则直接替换原来的节点。

  • DeriveStats

    • 通过栈实现自底向上的方式统计。主要统计以下信息：

      1
      2
      3
      4
      5
      6
      size_t num_rows;
      double cardinality;
      double frac_null;
      std::vector<double> most_common_vals,
      std::vector<double> most_common_freqs;
      std::vector<double> histogram_bounds;

  • OptimizeGroup

    • 先对LogicalExpression通过OptimizeExpression应用TransformationRule和ImplementationRule，得到多个group，并且Expression转换为了PhysicalExpression。
    • OptimizeExpression
      • 对当前GroupExpression添加ApplyRule，规则为所有TransformationRule和ImplementationRule。
      • 对当前的child Group调用ExploreGroup。
    • ExploreGroup
      • 对Group内的所有LogicalExpressions调用ExploreExpression。
    • ExploreExpression
      • 对当前GroupExpression添加ApplyRule，规则为所有TransformationRule和ImplementationRule。并且此ApplyRule设置了explore_only标志。
      • 对当前的child Group调用ExploreGroup。
    • ApplyRule
      • 每次对以当前GroupExpression为根节点的子树应用规则。
      • 通过GroupExprBindingIterator遍历子节点的Group，但是每次Next()返回都是当前GroupExpression，只是子节点在每次调用HasNext()时变化。
      • 通过GroupBindingIterator遍历其中的LogicalExpression。
      • 在应用TransformationRule后会重新调用DeriveStats。
      • 应用规则后得到的新的子树的根节点GroupExpression会被放到原来的GroupExpression所在的Group中，其新生成的子节点都会位于不同的Group。
    • OptimizeInputs
      • ChildPropertyDeriver：有的算子可能会要求前置节点的数据有序，如（PhysicalSortGroupBy），将此种属性下推到子节点。
      • 选择每个Group中开销最小的GroupExpression作为最佳节点，之后转换为PhysicalPlan节点。

优化规则

TransformationRule

  • InnerJoinCommutativity


—–>


+ InnerJoinAssociativity



—–>


### ImplementationRule

+ LogicalGroupByToHashGroupBy
+ LogicalAggregateToPhysical
+ GetToSeqScan
+ LogicalQueryDerivedGetToPhysical
+ InnerJoinToInnerNLJoin
+ InnerJoinToInnerHashJoin
+ ImplementDistinct
+ ImplementLimit

### RewriteRule

+ Bottom Up：UNNEST_SUBQUERY

+ PullFilterThroughMarkJoin



—–>

  • PullFilterThroughAggregation



    —–>

  • MarkJoinToInnerJoin：即算子转换。

  • Top Down：PREDICATE_PUSH_DOWN

    • PushFilterThroughJoin



      —–>

    • PushFilterThroughAggregation



      —–>

    • CombineConsecutiveFilter



      —–>

    • EmbedFilterIntoGet：即选择下推。

其它

  • visitor模式在遍历子树时较方便。