聊聊分布式 SQL 数据库Doris(九)

2023-11-30 08:42 由又见阿郎发表于 #数据库

优化器的作用是优化查询语句的执行效率，它通过评估不同的执行计划并选择最优的执行计划来实现这一目标。

CBO: 一种基于成本的优化器，它通过评估不同查询执行计划的成本来选择最优的执行计划。CBO会根据数据库系统定义的统计信息以及其他因素，对不同的执行计划进行评估，并选择成本最低的执行计划。CBO的目标是找到一个最优的执行计划，使得查询的执行成本最低。

RBO: 一种基于规则的优化器，它通过应用一系列的优化规则来选择最优的执行计划。RBO会根据预定义的规则对查询进行优化，这些规则基于数据库系统的特定逻辑和语义。RBO的优点是实现简单，适用于特定的查询模式和数据分布。然而，RBO可能无法找到最优的执行计划，特别是对于复杂的查询和大规模的数据集。

Doris主要整合了Google Mesa（数据模型），Apache Impala（MPP查询引擎)和Apache ORCFile (存储格式，编码和压缩) 的技术。 Doris的查询优化器则是基于Impala改造实现的。Doris官方提供的 Nereids优化器文档。

优化器组件

查询优化器由多个部分组成，分别是: 词法语法解析、语义解析、query改写、生成执行计划。最后这步根据算法实现与业务场景的不同会有些许差异。

词法语法解析

这个步骤，其实是做两件事情，首先是解析SQL文本，提取关键字出来，比如(select、from等); 然后分析SQL文本是否满足SQL语法，最终生成一个AST树。其结构如下:

对于不同类型的SQL，其语法树的根节点类型也是不一样的。一般是InsertStmt、UpdateStmt、DeleteStmt、SelectStmt等。而这些概念其实是impala中的，Doris的SQL查询引擎是参考自impala。在其源码中有这么一段注释:

Impala是用于处理存储在Hadoop集群中的大量数据的MPP（大规模并行处理）sql查询引擎。它是一个用C ++和Java编写的开源软件。与其他Hadoop的SQL引擎相比，它提供了高性能和低延迟。其相关信息及文档可参考: impala中文手册

语义解析

根据AST树与元数据中的表、列信息等做一个语义校验，比如，表、字段是否在元数据中存在。其步骤一般如下:

query改写

对原始的sql文本做一定程度的改写使得SQL更简单，执行效率更高；一般是条件表达式改写、子查询改写等。

在Doris中，有一个接口 ExprRewriteRule 负责表达式的改写规则，基于该接口与各种不同的规则有不同的实现，在 Analyzer类的内部类 GlobalState 构造函数中，注册了诸多的规则到rules集合中，而该list会被传递到ExprRewriter类中被应用。

StmtRewriter 类处理子查询改写逻辑，其中的方法会处理各种场景下的子查询改写，比如rewriteSelectStatement方法.

这一步骤的处理是基于词法语法解析后生成的AST树进行的。

public class GlobalState(Env env, ConnectContext context) {
    this.env = env;
    this.context = context;
    List<ExprRewriteRule> rules = Lists.newArrayList();
    // BetweenPredicates must be rewritten to be executable. Other non-essential
    // expr rewrites can be disabled via a query option. When rewrites are enabled
    // BetweenPredicates should be rewritten first to help trigger other rules.
    rules.add(BetweenToCompoundRule.INSTANCE);
    // Binary predicates must be rewritten to a canonical form for both predicate
    // pushdown and Parquet row group pruning based on min/max statistics.
    rules.add(NormalizeBinaryPredicatesRule.INSTANCE);
    // Put it after NormalizeBinaryPredicatesRule, make sure slotRef is on the left and Literal is on the right.
    rules.add(RewriteBinaryPredicatesRule.INSTANCE);
    rules.add(RewriteImplicitCastRule.INSTANCE);
    rules.add(RoundLiteralInBinaryPredicatesRule.INSTANCE);
    rules.add(FoldConstantsRule.INSTANCE);
    rules.add(EraseRedundantCastExpr.INSTANCE);
    rules.add(RewriteFromUnixTimeRule.INSTANCE);
    rules.add(CompoundPredicateWriteRule.INSTANCE);
    rules.add(RewriteDateLiteralRule.INSTANCE);
    rules.add(RewriteEncryptKeyRule.INSTANCE);
    rules.add(RewriteInPredicateRule.INSTANCE);
    rules.add(RewriteAliasFunctionRule.INSTANCE);
    rules.add(RewriteIsNullIsNotNullRule.INSTANCE);
    rules.add(MatchPredicateRule.INSTANCE);
    rules.add(EliminateUnnecessaryFunctions.INSTANCE);
    List<ExprRewriteRule> onceRules = Lists.newArrayList();
    onceRules.add(ExtractCommonFactorsRule.INSTANCE);
    onceRules.add(InferFiltersRule.INSTANCE);
    exprRewriter = new ExprRewriter(rules, onceRules);
    // init mv rewriter
    List<ExprRewriteRule> mvRewriteRules = Lists.newArrayList();
    mvRewriteRules.add(new ExprToSlotRefRule());
    mvRewriteRules.add(ToBitmapToSlotRefRule.INSTANCE);
    mvRewriteRules.add(CountDistinctToBitmapOrHLLRule.INSTANCE);
    mvRewriteRules.add(CountDistinctToBitmap.INSTANCE);
    mvRewriteRules.add(NDVToHll.INSTANCE);
    mvRewriteRules.add(HLLHashToSlotRefRule.INSTANCE);
    mvExprRewriter = new ExprRewriter(mvRewriteRules);

    // context maybe null. eg, for StreamLoadPlanner.
    // and autoBroadcastJoinThreshold is only used for Query's DistributedPlanner.
    // so it is ok to not set autoBroadcastJoinThreshold if context is null
    if (context != null) {
        // compute max exec mem could be used for broadcast join
        long perNodeMemLimit = context.getSessionVariable().getMaxExecMemByte();
        double autoBroadcastJoinThresholdPercentage = context.getSessionVariable().autoBroadcastJoinThreshold;
        if (autoBroadcastJoinThresholdPercentage > 1) {
            autoBroadcastJoinThresholdPercentage = 1.0;
        } else if (autoBroadcastJoinThresholdPercentage <= 0) {
            autoBroadcastJoinThresholdPercentage = -1.0;
        }
        autoBroadcastJoinThreshold = (long) (perNodeMemLimit * autoBroadcastJoinThresholdPercentage);
    } else {
        // autoBroadcastJoinThreshold is a "final" field, must set an initial value for it
        autoBroadcastJoinThreshold = 0;
    }
}

单机执行计划

这一过程会生成PlanNodeTree，一般用于处理Join Reorder场景下的join调优与谓词下推等下推优化。

SingleNodePlanner类用于生成单击执行计划，该类其实也是基于impala框架改写适用于Doris的。在这个类中，除了谓词下推与join reorder外，还有类似列裁剪之类的优化，都在这个类中有处理。

分布式执行计划

DistributedPlanner类负责分布式执行计划的优化，其中会处理Join场景下的分布式执行，选择最优的Join执行路径；其次就是Agg聚合函数的分布式执行逻辑，Agg会分两步执行，先会在local本地scan，然后再Agg Node上在做一次scan聚合；当然还有一些算子需要做分布式逻辑执行优化. 都可以在这个类中找到。当然这个类也是基于impala框架改写的。

如下是AggNode的分布式执行计划优化:

总结

Doris的很多设计，其实都是有据可依，参考借鉴已有的框架/论文，再依据实际的业务场景做改写；这也正是我们要学习了解的东西，通过一个点，然后铺开去了解学习相关的其他点，慢慢的串联起来形成面。查询优化器结合如下博客再加上自己去阅读一下代码，对整个脉络及机制就算是掌握了。

聊聊分布式 SQL 数据库Doris(五) 这是之前写的对查询优化器相关的一些知识普及.

查询优化器详解 Doris团队针对查询优化器的视频讲解.

Doris SQL 原理解析小米工程师写的，更深入的剖析.