DorisDB之CBO优化器结构原理

1.DorisDB架构
Doris 是分布式、面向交互式查询的分布式数据库，主要部分是 SQL，内部用到 MPP 技术。

所谓MPP ( Massively Parallel Processing )，即大规模并行处理，在数据库非共享集群中，每个节点都有独立的磁盘存储系统和内存系统，业务数据根据数据库模型和应用特点划分到各个节点上，每台数据节点通过专用网络或者商业通用网络互相连接，彼此协同计算，作为整体提供数据库服务。非共享数据库集群有完全的可伸缩性、高可用、高性能、的性价比、资源共享等优势。简单来说，MPP 是将任务并行的分散到多个服务器和节点上，在每个节点上计算完成后，将各自部分的结果汇总在一起得到终的结果 ( 与 Hadoop 相似 )。

当然MPP也有一些缺点，比如弹性扩容支持复杂，需要数据重分布；受限于关系型数据库设计思路，在湖仓一体架构中难以开展等，本文暂时不深究。

在数据分析处理框架中，Doris 主要做的是 Online 层面的数据服务，主要处理的是数据分析方面的服务。其目标是：实现低成本（主要针对商业产品），可线性扩展，支持云化部署，高可用，高查询性能，高加载性能。

2.Optimizer简介
(1)业界上SQL引擎优化流程一般如下：
SQL Rewriter：输入SQL重写，如删除注释等。

Parser：将SQL转化为抽象语法树

Binder：查询数据库元信息，将表(如表名)和列(如列名和类型)绑定在抽象语法树上，终生成逻辑语法树

Tree Rewrite：将逻辑执行树优化，大部分是RBO规则。

Optimizer：基于CBO规则，引入了Cost estimates模型，估算出所有推导出的plan，选择代价小的plan作为physical plan

(2)经典Tree Rewriter介绍
①Tree Rewriter中逻辑执行计划有两种结果，一种是优化逻辑计划，另一种是生成物理执行计划
优化Logical Plan：如多表关联查询时，如果调整顺序结果不变则会从多种顺序结果中选择代价小的顺序
生成physical plan：不同数据库中join具体实现有多种，如hash join、merge join或nested join等。

②Expression Reuse：
表达式重写的目的是为了减少重复性操作，如下面的select中case被代表了Logic Project节点操作，原来case when语法中MONTH(t0.date)执行了 六次 ， DATE_DIFF(MONTH(t0.date),now())执行 3次 ，因此可以优化表达式只执行一次。

比如谓词下推场景中：where过滤条件需要下推到源数据库，如果未下推则是先扫描三张表返回，然后再平台上执行where过滤。这样JDBC传输数据量不仅加大，而且数据库扫表时间也耗时。

还有其他Rewriter场景，如列裁剪、Join转换、Limit下推、子查询重写、分区分桶裁剪、公共谓词提取、范围谓词推导、Lateral Join化简、Empty Node优化等等，以后详细展示。

3.DorisDB CBO Optimizer
DorisBD基于Cascades & Orca论文原理实现，其特性优化如：分布式执行计算、子查询优化、表达式复用、多阶段聚合等。

Parser：同上生成抽象语法树

Analyzer：查询元信息进行验证和解析，然后转成Relation结构，方便做逻辑转换

Transformer：生成逻辑执行树

Rewriter：优化逻辑执行树

Optimizer：基于CBO规则，生成分布式Physical Plan

(1)Parse阶段
一条select语句被拆分为多个部分转成抽象语法树，如：

selectList：select中查询的内容

FromClause：查询的表

WhereClause：子查询（子查询相当于又是一个新的SelectStmt，具体结构看SQL类型）或者过滤条件

GroupByClause、HavingClause和OrderByClause一一填充即可（其他类似产品可能会有LimitClause等结构，这个要看它支持什么种类数据库）

(2)Analyze阶段
元数据的识别和解析（Binder）：检查表权限，列是否存在类型是否支持等，然后解析(Binder)出来

SQL合法性检查

SQL重写：如select * 重写为 select col1,col2...

函数检查

别名处理

(3)Transformer阶段
抽象语法树转出逻辑语法树，改逻辑树的节点只是代表了SQL中特殊数据操作，不指定如何处理它。如：

FromClause转(子查询中from supplier)换成了Logical Scan扫表操作，即从数据库中读取一张表完整数据

WhereClause(子查询中where s_nationkey=15)转成了Logical Filter：

selectList(子查询中s_suppkey)转成了Logical Project做投影操作

Logical Apply(父查询中where xx in)后续将用做子查询优

(4)Rewriter阶段
常量折叠：某些表达式可以直接求出来，或者说本身结果就是常量。因此直接在Rewriter阶段写成常量

谓词化简：所谓谓词就是返回值为真值（TRUE/FALSE/UNKNOWN）的函数，如OR、AND、LKIE、BETWEEN、IS NULL、IS NOT NULL、IN、EXISTS等。如果这些含义谓词的表达式本身可以直接求出来那么也进行化简，如化简为常量。

等价推导：如两个表做join时连接的列，SQL中t0表列有过滤而t1表列无过滤，那么可以推导出t1表其实也有等价的（t1.v1+1）>2，这样可以极大的减少join两表的数据量并提高性能。

另外还有一些重写功能和Tree Rewriter类似。

(5)Optimizer阶段
基于CBO原理，首先拿取表的元信息(表行数、列类型)然后计算并选取优代价。

Join场景(类型和顺序)

1.T2 left outer join T1与T1 right outer join T2虽然结果相同，但效率不同。left outer join中T1表做Hash表存入内存（数仓一般数据量大会用Hash表数据库多表连接方式介绍－HASH-JOIN - _雨 - 博客园），但如果内存不够5000W行不能一次性装下则源数据库优化器会将它分割成若干不同的分区，不能放入内存的部分就把该分区写入磁盘的临时段，此时要有较大的临时段从而尽量提高I/O 的性能。

2.在多个表做inner join时顺序可以任意选择。左边T1和T2表做Inner join是5000W和1000W得到1000W，而右边T1和T3做Join是5000W和100的得到100结果，然后第二层都是1000W和100做Inner join没有区别。

Aggregation(聚合函数，接受多个输入，并按照一定的规则运算以后输出一个结果值)

Aggregation()改为两阶段操作。阶段BE节点扫表得到数据，然后在本地做Local Aggregate计算一部分。第二阶段shuffle方式发出去对剩余的数据

数据Shuffle方式

1.数据重分布：如T1和T2扫表后，Shuffle重新分布到多台机器上Join操作

2.Broadcast：如T2扫表后分配到多个BE节点上，这些BE节点分布扫表了T1表不同部分，然后分别做Join。这些可以减少Shuffle操作

3."分区"分布：和上述一些，可以在同一个机架上的不同节点之间扫表T1和T2表不同部分，然后分别做Join。这样可以减少网络延迟，避免Shuffle操作。

4.CBO Optimizer架构(完善中)
Memo：所有推导出的执行计划会存放在Memo中，以便后续进行搜索

Rule：逻辑执行树转换和逻辑执行树实现

Task scheduler：调度任务

Property Enforcement：DorisDB数据会打上两种属性，是否有序和分区方式

Cost Estimation：代价评估方式

(1)Memo Init
将逻辑执行树表示为Memo内部能够识别的结构，如Goup5中存放的Project 4，即根节点Logical Project，Group4中存放Join 3&2 即代表两个结果被Join

5.Cost Estimation
(1)Statistics
①Statistics Collection表统计所有信息如下

②统计数据使用过程：

(a)Join逻辑执行计划中有两个子节点Scan T1.a (group 1)和Scan T2.b (group 2)

(b)DorisDB开始统计列信息

(c)和(d)拿到统计信息后准备在Join节点之后更新统计信息，另外还估算输出结果RowCount

③统计计算部分公式表：

(2)Cost Calculate
在统计估计结果输出后开始模拟计算真实场景下Cost，一般大的开销为CpuCost和MemoryCost(如Join时创建Hash表)

其次，总Cost为每个节点的Cost之和

————————————————
版权声明：本文为CSDN博主「Bro大表哥」的原创文章，遵循CC 4.0 BY-SA版权协议，转载请附上原文出处链接及本声明。
原文链接：https://blog.csdn.net/qq_35494772/article/details/119720619