前往小程序,Get更优阅读体验!
立即前往
首页
学习
活动
专区
圈层
工具
发布
首页
学习
活动
专区
圈层
工具
MCP广场
社区首页 >专栏 >分布式sql引擎原理分析-逻辑执行计划生成

分布式sql引擎原理分析-逻辑执行计划生成

原创
作者头像
sundyxiong
修改于 2018-08-25 16:12:10
修改于 2018-08-25 16:12:10
6.8K00
代码可运行
举报
运行总次数:0
代码可运行

不管是传统数据库或者基于sql的分布式大数据分析工具,基本原理都是把一个sql转换成sql语法树(AST),通过对语法树的分析转换成执行计划。传统数据库会根据执行计划通过执行引擎并返回结果;而大数据sql分析工具,由于针对更大数据量而生,为了更好的扩展性、容错性和高可用,会把执行计划分成逻辑执行计划和物理执行计划,并且根据查询sql的特点切分逻辑计划,这样可以把分块的逻辑计划分配到更具扩展性的并行节点,最后根据逻辑执行计划转成物理执行计划进行查询。

     本文档以当前流行的分布式大数据查询引擎Presto为切入点,分析一个query语句怎么生成为一个分段的逻辑计划。下图是当前流行大数据sql查询引擎(包括hive/sparksql),生成逻辑计划的过程:

SQL引擎生成逻辑计划
SQL引擎生成逻辑计划

         从图中可以看到,当用户通过presto-cli或者jdbc接口提交了一个query请求到Presto的Coordinator节点,首先会被解析器(Parser)转换成一颗sql语法树,这一步只是通过预定的分词规则把一个词组结构(List)转换成了树结构(Tree),但是这时候不能理解这颗树代表的含义是什么?所以被称作Unresovled AST,这时候需要再通过分析器(Analyzer)来绑定元数据(metaData)。

          数据结构和编译原理知识知道,Tree这种结构或者说AST这种结构有一个非常重要的特性就是可以等价变换,这个特性在其做分析元数据及优化查询时非常有用。在通过等价变换成Unresovled AST后,称为UnOptimized AST这时候通过这颗AST可以基本分析出提交了一个样的语句,其中关联了什么表,这些表的基本结构是怎样的,其中又使用了什么函数等等。绑定元数据的AST后还需针对具体的操作(主要是join)节点进行优化,使用优化器(Optimizer)进行优化转换成Optimized AST。最后把优化后AST进行逻辑分段,变成可供分布式分析的分段逻辑执行计划。

          下面以Presto为例具体实际分析怎么实施。

Parser

Parser的过程实际是一个把sql语句根据分词规则及语法规则再组装成基本AST的过程。当前大部分都是使用的Antlr4工具。从源码的角度看:

presto-main模块的execution包中SqlQueryManager的createQuery发起了Query操作,

Antlr4工具具体分为lexer和parser,lexer叫做词法分析器,而parser叫做语法分析器。举个小例子,以下面这个定义chars sp =100来说,会先根据定义好的tokens进行分词,再语法分析成AST:

一个生成AST示例(图片来源网络)
一个生成AST示例(图片来源网络)

而presto它的lexer是在presto-parser中定义,其中分词器:

presto-parser的分词器
presto-parser的分词器

由于Antlr4是业内使用最多也是最成熟的方案,所以资料也非常多,这里就不赘述了,工具更多内容可参考:https://legacy.gitbook.com/book/dohkoos/antlr4-short-course/details

https://github.com/antlr/antlr4

Analyzer

分析器Analyzer也叫做语义分析器(Semantic Analysis),主要是用于绑定元数据。SqlQuery的数据也即是DQL的数据通过SqlQueryExecution执行器被拉起。真正实现是doAnalyzeQuery方法中。

语义分析可以看作包括了语句(statement)分析和表达式(expression)分析。

Presto实现AST 和 Node的类图
Presto实现AST 和 Node的类图
Presto AST源码结构
Presto AST源码结构

其分析的实现是以典型的visitor模式使用元数据和会话(sesssion,presto在每个session中有自己的Catalog和Schema)信息遍历Unresolved AST来实现的。

Scope是其递归遍历时列描述符集:

对查询的select和showXXX语句返回了包含渠道的每一列,每一个filed代表一列。而insert /delete/create table as select返回只有一列表示操作的行数。

针对不同的statement将使用不用的statement实现类进行处理,在analyzer后将得到一个Analysis类的实例。其中除了statement为root的AST以外还有为了构建执行计划树所添加的信息。 

LogicalPlanner

在AST绑定相应元数据后,将把AST转换成逻辑计划树。

代码语言:javascript
代码运行次数:0
运行
AI代码解释
复制
public PlanNode planStatement(Analysis analysis, Statement statement)
    {
        if (statement instanceof CreateTableAsSelect && analysis.isCreateTableAsSelectNoOp()) {
            checkState(analysis.getCreateTableDestination().isPresent(), "Table destination is missing");
            Symbol symbol = symbolAllocator.newSymbol("rows", BIGINT);
            PlanNode source = new ValuesNode(idAllocator.getNextId(), ImmutableList.of(symbol), ImmutableList.of(ImmutableList.of(new LongLiteral("0"))));
            return new OutputNode(idAllocator.getNextId(), source, ImmutableList.of("rows"), ImmutableList.of(symbol));
        }
        //分成两步:1.planStatementWithoutOutput 根据不同sql语句生成不同relationPlan
        //        2.createOutputPlan 输出得到LogicalPlan
        return createOutputPlan(planStatementWithoutOutput(analysis, statement), analysis);
    }

    //依据statement划分成creat、insert、delete、query、explain五类logicalPlan,并执行不同的plan生成函数
    //其中,create、insert、delete的逻辑计划可直接生成,create/insert会生成TableWriterPlan,delete生成Plan,
    //而query将由依旧是根据visitor模式 RelationPlanner 生成RelationPlan后,在visitQuery中将使用QueryPlanner使用visitor模式来生成QueryPlan
    private RelationPlan planStatementWithoutOutput(Analysis analysis, Statement statement)
    {
        if (statement instanceof CreateTableAsSelect) {
            if (analysis.isCreateTableAsSelectNoOp()) {
                throw new PrestoException(NOT_SUPPORTED, "CREATE TABLE IF NOT EXISTS is not supported in this context " + statement.getClass().getSimpleName());
            }
            return createTableCreationPlan(analysis, ((CreateTableAsSelect) statement).getQuery());
        }
        else if (statement instanceof Insert) {
            checkState(analysis.getInsert().isPresent(), "Insert handle is missing");
            return createInsertPlan(analysis, (Insert) statement);
        }
        else if (statement instanceof Delete) {
            return createDeletePlan(analysis, (Delete) statement);
        }
        else if (statement instanceof Query) {
            return createRelationPlan(analysis, (Query) statement);
        }
        else if (statement instanceof Explain && ((Explain) statement).isAnalyze()) {
            return createExplainAnalyzePlan(analysis, (Explain) statement);
        }
        else {
            throw new PrestoException(NOT_SUPPORTED, "Unsupported statement type " + statement.getClass().getSimpleName());
        }
    }

insert和createTableAsSelec语句t会通过LoggiclaPlanner的createTableWriteerPlan方法 生成CreateTableWriteerPlan:

CreateTableWriteerPlan
CreateTableWriteerPlan

TableCommitNode可以防止数据写入失败导致的中间状态,确保成功后再进行commit。QueryPlan是指insert/creat table as select后面生成的执行计划树。

同理,Delete会生成DeletePlan:

DeletePlan
DeletePlan

Relation类型SQL语句会生成QueryPlan,由LoggiclaPlanner委托RelationPlanner进行分析。

代码语言:javascript
代码运行次数:0
运行
AI代码解释
复制
public Plan plan(Analysis analysis, Stage stage)
    {
        //生成逻辑计划树,返回的为planNode子类的实例
        PlanNode root = planStatement(analysis, analysis.getStatement());

        PlanSanityChecker.validateIntermediatePlan(root, session, metadata, sqlParser, symbolAllocator.getTypes());

        //使用针对的优化器optimizers,在presto1.90前,planOptimizers被初始化为一个list,顺序执行基于ruler的优化器。
        if (stage.ordinal() >= Stage.OPTIMIZED.ordinal()) {
            for (PlanOptimizer optimizer : planOptimizers) {
                root = optimizer.optimize(root, session, symbolAllocator.getTypes(), symbolAllocator, idAllocator);
                requireNonNull(root, format("%s returned a null plan", optimizer.getClass().getName()));
            }
        }

        if (stage.ordinal() >= Stage.OPTIMIZED_AND_VALIDATED.ordinal()) {
            // make sure we produce a valid plan after optimizations run. This is mainly to catch programming errors
            PlanSanityChecker.validateFinalPlan(root, session, metadata, sqlParser, symbolAllocator.getTypes());
        }

        Map<PlanNodeId, PlanNodeCost> planNodeCosts = costCalculator.calculateCostForPlan(session, symbolAllocator.getTypes(), root);

        return new Plan(root, symbolAllocator.getTypes(), planNodeCosts);
    }

而Query和QuerySpecification由RelationPlanner委托QueryPlanner来分析。

代码语言:javascript
代码运行次数:0
运行
AI代码解释
复制
private RelationPlan createRelationPlan(Analysis analysis, Query query)
    {
        return new RelationPlanner(analysis, symbolAllocator, idAllocator, buildLambdaDeclarationToSymbolMap(analysis, symbolAllocator), metadata, session)
                .process(query, null);
    }
    @Override
    protected RelationPlan visitQuery(Query node, Void context)
    {
        return new QueryPlanner(analysis, symbolAllocator, idAllocator, lambdaDeclarationToSymbolMap, metadata, session)
                .plan(node);
    }

Optimizer

     在sql的优化思路上最基本的分为基于规则和基于代价(rbo和cbo),基于规则是传统数据库积累的一套经验,指定一些规则,然后遍历逻辑执行树模式符合规则时则等价转换(AST转换)进行优化,比如谓词下推(Predicate Pushdown),常量累加(Constant Folding)等;而基于代价是计算所有执行路径的代价,并挑选代价最小的执行路径,这种思路当前针对分布式的执行引擎很流行但目前都做的都还不够好,大部分cbo都认为代价是以mem为主,但如何确定路径上代价就有很多思路。

更多讨论可参考:

presto 0.190前只支持rbo,在0.190后也开始支持cbo优化器伪代码:

代码语言:javascript
代码运行次数:0
运行
AI代码解释
复制
start:
- break up expression into single-assignment expression
- add each assignment to the memo in a separate equivalence class
- optimize(root class, unbounded cost, no physical reqs)

optimize(equivalence class, cost bound, requirements):
- initialize exploration queue (rule + top operator in equivalence class)
- find potential match candidates and add them to queue
- while queue is not empty
    - enumerate bindings for each named argument (by iterating over all expressions
      in each equivalence class that's part of the match)
    - if binding + physical requirements can be handled by rule
        - apply rule
        - for each expression generated by rule
            - add to memo
            - if top function is physical
                - determine cost bound for children
                - for each input
                    - derive required physical properties & cost upper bound
                    - optimize corresponding equivalence class
                      with required properties and upper bound
                    - update max bound for remaining children 
            - find additional potential matches and enqueue

一个分布式引擎执行的快不快,很大程度就来自于其优化器,本文档暂不讨论更多,presto优化器可参考:

(https://github.com/prestodb/presto/wiki/New-Optimizer

Plan Fragmenter

把逻辑执行计划分段的最重要目的就是能够以分片(splited)方式运输(shipped)和执行在分布式节点上。分布式sql引擎相比于传统数据库引擎最大的区别之一就是并发度理论上可以无限横向扩展,presto也不例外,presto切分的目的就是为了更好的分发到各个woker节点,但是sql执行的时候难免会被一些操作阻塞,比如join,aggregation,sort等,那么一个执行计划就在这些点切分(fragment)成多个子执行计划(SubPlan)。在相同的SubPlan(执行逻辑一样,数据split不通)中可以多个节点的task中并发执行。

下面我们还是以presto举例说明:

presto支持的阶段为Source、Fixed、Single和Coordinator_only。其中Source即是分片从数据源读数据;Fixed则是将读取的数据分散到分布式节点上进行处理,包括局部聚合、局部join及局部数据写入等;Single则是将所有结果进行汇总处理,并返回结果,只在单个节点上执行。Coordinator_onlye也是在单节点对insert和createtable的commitNode是这种类型。可以看到,不同subPlan间有明显层级关系,一般来说是SourceStage->FixedStage->SingleStage。

     在presto中的划分是依据logicalPlan逻辑执行计划树的PlanNode来决定的。通过PlanFragMenter深度优先遍历逻辑执行树,使用visitor模式遍历到需要分段的节点则加入不同的subPlan。 Exchange PlanNode即是其presto分段点,表示不同Stage之间交换数据,也即是常说的shuffle,因为需要等待分布式节点的数据的传输。在分段成subPlan后Exchangge PlanNode会转成多个RemoteSourceNode节点。 

代码语言:javascript
代码运行次数:0
运行
AI代码解释
复制
public PlanNode visitExchange(ExchangeNode exchange, RewriteContext<FragmentProperties> context)
        {
            if (exchange.getScope() != REMOTE) {
                return context.defaultRewrite(exchange, context.get());
            }

            PartitioningScheme partitioningScheme = exchange.getPartitioningScheme();

            if (exchange.getType() == ExchangeNode.Type.GATHER) {
                context.get().setSingleNodeDistribution();
            }
            else if (exchange.getType() == ExchangeNode.Type.REPARTITION) {
                context.get().setDistribution(partitioningScheme.getPartitioning().getHandle());
            }

            ImmutableList.Builder<SubPlan> builder = ImmutableList.builder();
            for (int sourceIndex = 0; sourceIndex < exchange.getSources().size(); sourceIndex++) {
                FragmentProperties childProperties = new FragmentProperties(partitioningScheme.translateOutputLayout(exchange.getInputs().get(sourceIndex)));
                builder.add(buildSubPlan(exchange.getSources().get(sourceIndex), childProperties, context));
            }

            List<SubPlan> children = builder.build();
            context.get().addChildren(children);

            List<PlanFragmentId> childrenIds = children.stream()
                    .map(SubPlan::getFragment)
                    .map(PlanFragment::getId)
                    .collect(toImmutableList());

            return new RemoteSourceNode(exchange.getId(), childrenIds, exchange.getOutputSymbols());
        }

后续

      在生成分段的逻辑执行计划后,是不能直接放到执行引擎中执行的,因为这里还是抽象的概念,比如Aggregation还是抽象的,其代表的是相同id进行合并,而实现方法具体到引擎比如mr需要hash shuffle来实现。所以需要根据不同执行引擎(presto/spark/mr/tez等)生成对应的物理执行计划,虽然不同执行引擎各有差异,但大体逻辑还是1.由分段逻辑计划生成task执行图;2.以及task的执行图转换成基于Operator的最小执行单元执行图。与生成逻辑计划都在master节点不同,1.和2.一般都会在worker节点中生成并运算。在生成物理计划时还需考虑执行引擎本身的特性,来确定最终的物理计划。比较重要的有几点:1.如何确保数据划分(source和parition)均匀;2.stage内并发度怎么提高同时又有比较高的效率;3.如何做数据交换,保证传输效率高同时容灾又有保障等。更多有关分析,请关注下一篇分析:分布式sql引擎--生成物理计划分布式执行。

原创声明:本文系作者授权腾讯云开发者社区发表,未经许可,不得转载。

如有侵权,请联系 cloudcommunity@tencent.com 删除。

原创声明:本文系作者授权腾讯云开发者社区发表,未经许可,不得转载。

如有侵权,请联系 cloudcommunity@tencent.com 删除。

评论
登录后参与评论
暂无评论
推荐阅读
编辑精选文章
换一批
Nebula Graph 源码解读系列 | Vol.03 Planner 的实现
上篇我们讲到 Validator 会将由 Parser 生成的抽象语法树(AST)转化为执行计划,这次,我们来讲下执行计划是如何生成的。
NebulaGraph
2021/09/25
6390
Presto系列 | Presto基本介绍
Presto是一款Facebook开源的MPP架构的OLAP查询引擎,可针对不同数据源执行大容量数据集的一款分布式SQL执行引擎。因为工作中接触到Presto,研究它对理解SQL Parser、常见算子的实现(如SQL中table scan,join,aggregation)、资源管理与调度、查询优化(如向量化执行、动态代码生成)、大数据下各个组件为何适用不同场景等等都有帮助。我希望通过这个系列可以了解一条SQL在大数据场景下该如何高效执行。233酱准备不定时持续更新这个系列,本文主要从Presto的使用举例,Presto的应用场景、Presto的基本概念三个部分来初步介绍Presto。
Monica2333
2020/09/24
4.5K0
Presto系列 | Presto基本介绍
聊聊分布式 SQL 数据库Doris(五)
Ryan_OVO
2023/11/28
3110
聊聊分布式 SQL 数据库Doris(五)
查看SQL执行计划的方法及优劣
作者 | 胡佳伟:云和恩墨技术工程师,有多年数据库优化经验,在一线执行过多个包括通信、保险等行业的优化项目。
数据和云
2018/07/27
1.2K0
查看SQL执行计划的方法及优劣
Spark SQL底层执行流程详解(好文收藏)
一、Apache Spark 二、Spark SQL发展历程 三、Spark SQL底层执行原理 四、Catalyst 的两大优化
五分钟学大数据
2022/05/22
5K0
Spark SQL底层执行流程详解(好文收藏)
Antlr4实战:统一SQL路由多引擎
ANTLR是一款功能强大的语法分析器生成器,可用来读取、处理、执行和转换结构化文本或二进制文件。它被广泛应用于学术界和工业界构建各种语言、工具和框架。Antlr在Hadoop整个生态系统应用较为广泛,如Hive 词法文件是Antlr3写的;Presto词法文件也Antlr4实现的;SparkSQL词法文件是用Presto的词法文件改写的;还有HBase的访问客户端Phoenix也用Antlr工具进行SQL解析的等等。
用户7600169
2022/04/25
10.3K1
Antlr4实战:统一SQL路由多引擎
Nebula Graph 源码解读系列 | Vol.02 详解 Validator
Nebula Graph Query Engine 主要分为四个模块,分别是 Parser、Validator、Optimizer 和 Executor。
NebulaGraph
2021/09/24
5600
Oracle固定SQL的执行计划(二)—SPM
之前写了一篇文章介绍的是用SQL Profile来调整、稳定目标SQL的执行计划,即使无法修改目标SQL的SQL文本。但SQL Profile实际上只是一种亡羊补牢、被动的技术手段,应用在那些执行计划已经发生了不好的变更的SQL上,即当我们发现这些SQL的执行计划已经出了问题时通过创建SQL Profile来纠正、稳定这些SQL的执行计划。即便通过创建SQL Profile解决了目标SQL执行计划变更的问题,依然不能保证系统后续执行的SQL的执行计划就不再发生不好的变更。这种不确定性会给Oracle数据库大版本升级(比如从Oracle 10g升级到Oracle 11g)带来一系列的麻烦,因为不清楚升级之后原先系统中哪些SQL的执行计划会发生不好的变更。
星哥玩云
2022/08/13
1.3K0
Oracle固定SQL的执行计划(二)—SPM
TiDB 优化器 | 执行计划管理及实践
在 TiDB 中,优化器的作用至关重要,它决定了 SQL 查询的执行计划,从而直接影响查询性能。尽管 TiDB 优化器采用了代价模型来选择最优执行计划,但由于统计信息、估算误差等因素,优化器并不能保证每次都选中最佳计划。本文深入解析了 TiDB 优化器的执行计划生成过程及其局限性,介绍了如何通过 Hint、SQL Binding、执行计划缓存等技术手段进行执行计划管理,确保查询性能的稳定性和高效性。
PingCAP
2024/12/12
1360
TiDB 优化器 | 执行计划管理及实践
Hive底层原理:explain执行计划详解
不懂hive中的explain,说明hive还没入门,学会explain,能够给我们工作中使用hive带来极大的便利!
五分钟学大数据
2021/02/20
3.6K0
Hive底层原理:explain执行计划详解
Postgresql源码(132)分布式行锁的原理分析
PG中的行锁在上一片中做了分析《Postgresql源码(131)行锁的原理分析》,本篇对分布式PG(PGXL)中的行锁做一些分析。(版本:Postgres-XL 10alpha2)
mingjie
2024/05/24
2090
Postgresql源码(132)分布式行锁的原理分析
SQL Server 执行计划缓存
概述 了解执行计划对数据库性能分析很重要,其中涉及到了语句性能分析与存储,这也是写这篇文章的目的,在了解执行计划之前先要了解一些基础知识,所以文章前面会讲一些概念,学起来会比较枯燥,但是这些基础知识非常重要。 目录 概述 基础概念 怎样缓存执行计划 SQL Server自动删除执行计划 重新编译执行计划 测试 执行计划相关系统视图 手动清空缓存执行计划 测试索引更改对执行计划的影响 测试增加字段对执行计划的影响 总结 基础概念 SQL Server 有一个用于存储执行计划和数据缓冲区
逸鹏
2018/04/11
2K0
SQL Server 执行计划缓存
从真实案例出发,全方位解读 NebulaGraph 中的执行计划
本文整理自 NebulaGraph 核心开发 Yee 在直播《聊聊执行计划这件事》中的主题分享。分享视频参见 B站:https://www.bilibili.com/video/BV1Cu4y1h7gn/
NebulaGraph
2023/11/15
3250
从真实案例出发,全方位解读 NebulaGraph 中的执行计划
盘点:SQL on Hadoop中用到的主要技术
自打Hive出现之后,经过几年的发展,SQL on Hadoop相关的系统已经百花齐放,速度越来越快,功能也越来越齐全。本文并不是要去比较所谓“交互式查询哪家强”,而是试图梳理出一个统一的视角,来看看各家系统有哪些技术上相通之处。
王知无-import_bigdata
2020/06/11
1.4K0
尝尝鲜|Spark 3.1自适应执行计划
每个框架产生都是为了解决一类问题,每个模块的优化也是为了解决一定的场景下的性能瓶颈。浪尖今天分享的关于Spark 3.1之后的自适应执行计划,主要针对以下几个场景,并且有百度率先研发的,不过社区之前一直没有采纳,spark 3.0的预发布版本参数也是不全,到了Spark 3.1的beta版已经可用,浪尖已经完成了测试。
Spark学习技巧
2021/03/05
9160
尝尝鲜|Spark 3.1自适应执行计划
Hive SQL底层执行过程详细剖析(好文收藏)
Hive是什么?Hive 是数据仓库工具,再具体点就是一个 SQL 解析引擎,因为它即不负责存储数据,也不负责计算数据,只负责解析 SQL,记录元数据。
五分钟学大数据
2021/07/07
9.6K0
Hive SQL底层执行过程详细剖析(好文收藏)
Presto 分布式SQL查询引擎及原理分析
Presto是由 Facebook 推出的一个基于Java开发的开源分布式SQL查询引擎,适用于交互式分析查询,数据量支持GB到PB字节。Presto本身并不存储数据,但是可以接入多种数据源,并且支持跨数据源的级联查询。
yuanyi928
2020/05/20
4.9K0
Mongodb执行计划
前面2篇文章讲到分页性能优化相关知识点,但并没有介绍如何找出系统中TOP SQL、对于如何清理SQL缓存执行计划(比如走错执行计划,存在数据倾斜的情况)、Mongo如何针对不同查询语句选择执行计划等相关知识点.
徐靖
2020/08/05
1K0
Mongodb执行计划
Oracle 执行计划查看方法汇总及优劣比较
执行计划是一条 SQL 语句在 Oracle 数据库中的执行过程或访问路径的描述。如下图所示,是一个比较完整的执行计划示意图。
JiekeXu之路
2022/12/07
1.5K0
Oracle 执行计划查看方法汇总及优劣比较
由浅入深了解Presto技术内幕
Presto是专为大数据实时查询计算而设计开发的产品,拥有如下特点: – 多数据源:通过自定义Connector能支持Mysql,Hive,Kafka等多种数据源 – 支持SQL:完全支持ANSI SQL – 扩展性:支持自定义开发Connector和UDF – 混合计算:可以根据需要将开源于不同数据源的多个Catalog进行混合join计算 – 高性能:10倍于Hive的查询性能 – 流水线:基于Pipeline设计,在数据处理过程当中不用等到所有数据都处理完成后再查看结果
大数据真好玩
2020/06/03
3.5K0
相关推荐
Nebula Graph 源码解读系列 | Vol.03 Planner 的实现
更多 >
领券
问题归档专栏文章快讯文章归档关键词归档开发者手册归档开发者手册 Section 归档
本文部分代码块支持一键运行,欢迎体验
本文部分代码块支持一键运行,欢迎体验