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

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

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 原理解析 小米工程师写的,更深入的剖析.

热门相关:婚期一年   全系灵师:魔帝嗜宠兽神妃   睡服BOSS:老公,躺下!   惊世第一妃   傲娇总裁:蜜宠小甜妻!