SQL Optimizer 详细解析

目录

一、>

1、SQL的处理流程

1.1>

String -> AST (Abstruct Syntax Tree)：

词法分析:拆分字符串，得到关键词、数值常量、字符串常量、运算符号等token语法分析:将token组成ASTnode，最终得到一个AST

实现：递归下降 (ClickHouse)，Flex 和 Bison (PostgreSQL)，JavaCC (Flink)，Antlr (Presto，Spark)

1.2>

 Analyzer：

检查并绑定Database, Table, Column等元信息SQL的合法性检查，比如min/max/avg的输入是数值AST -> Logical Plan

 Logical Plan：

逻辑地描述SQL对应的分步骤计算操作计算操作:算子( operator )







1.3>

 Physical Plan: 执行计划子树

目标:最小化网络数据传输利用上数据的物理分布(数据亲和性)增加Shuffle算子

 Executor

单机并行: cache，pipeline, SIMD多机并行: 一个fragment对应多个实例

1.4>

One SQL rules big data allSQL 需要依次经过Parser，Analyzer，Optimizer和Executor的处理查询优化器是数据库的大脑，在大数据场景下对查询性能至关重要查询优化器需要感知数据分布，充分利用数据的亲和性查询优化器按照最小化网络数据传输的目标把逻辑计划拆分成多个物理计划片段

二、>

1、查询优化器分类





2、RBO（Rule-based>

2.1>

运算符：Select Project Join Rename Union等价变换：结合律、交换律、传递性

2.2>



2.3>

扫描表格中所需要的列，而不是全部

2.4>

where的表达式是谓词。谓词尽快过滤数据，减少开销2（条件：join是inter）

2.5>

根据表达式等价关系，过滤条件，推导出一个新的过滤条件

2.6>

对一个join如果能在查询端提早过滤不必要数据，可减少开销

min-max的缺点：范围必须很紧密in-list：只需要扫描in-list里的数据。缺点：集合个数很多时，in-list也很大bloom filter：特性：大小不随集合大小改变，固定大小，给一个数可以判断在不在

2.7>

主流RBO实现一般都有几百条基于经验归纳得到的优化规则优点:实现简单，优化速度快缺点:不保证得到最优的执行计划



3、CBO（Cost-based>

3.1>

△使用一个模型估算执行计划的代价，选择代价最小的执行计划

执行计划的代价等于所有算子的执行代价之和通过RBO得到(所有)可能的等价执行计划

△算子代价:CPU，内存，磁盘IO，网络I/O等代价

统计信息+推导规则→计算算子代价→计算执行计划代价→执行计划枚举

3.2>

原始表统计信息

表或者分区级别:行数、行平均大小、表在磁盘中占用了多少字节等列级别: min、max、num nulls、num not nulls、num distinct value(NDV)、histogram 等

推导统计信息

选择率( selecthwty)：对于某一个过滤条件查询会从表中返回多大比例的数据基数( careinality )：在查询计划中常指算子需要处理的行数

3.2.1 CBO-统计信息的收集方式

在DDL里指定需要收集的统计信息，数据库会在数据写入时收集或者更新统计信息

CREATE TABLE REGION( R_ REGIONKEY INT NOT NULL, R NAME CHAR(25) NOT NULL, R_ COMMENT VARCHAR(152) ) DUPLICATE KEY(R_ REGIONKEY) DISTRIBUTED BY HASH(R_ REGIONKEY) BUCKETS 1 PROPERTIES (" sotumnselelR w");

手动执行explain analyze statement，出发数据库收集或者更新统计信息

ANALYZE TABLE table_name COMPUTE STATISICS FOR COLUMNS column-name1,column-name2....

动态采样：

SELECT count(*) FROM table_name

3.2.2 CBO-统计信息推导规则

Filter Selectivity
AND条件:fs(a AND b)=fs(a)* fs(b)OR条件: fs(a OR b) = fs(a) + fs(b) - (fs(a) * fs(b))NOT条件: fs(NOT a)= 1.0 - fs(a)等于条件(x = literal )
literal < min && literal > max : 01/NDV小于条件(x < literal )
literal<min:0literal>max:1(literal-min)/(max-min)

3.3>

单表扫描:索引扫描(随机I/O) vs 全表扫描(顺序IO)
如果查询的数据分布非常不均衡，索引扫描可能不如全表扫描Join的实现: Hash Join Vs. SortMerge Join两表Hash Join :用小表构建哈希表如何识别小表?多表Join :
哪种连接顺序是最优的?是否要对每种组合都探索?N个表连接,仅仅是left-deep tree就有差不多N!种连接顺序
e.g. N= 10->总共3, 628, 800个连接顺序



3.4>

CBO使用代价模型和统计信息估算执行计划的代价CBO使用贪心或者动态规划算法寻找最优执行计划在大数据场景下CBO对查询性能非常重要

4、总结

主流RBO实现-般都有几百条基于经验归纳得到的优化规则RBO实现简单，优化速度快RBO不保证得到最优的执行计划CBO使用代价模型和统计信息估算执行计划的代价CBO使用贪心或者动态规划算法寻找最优执行计划大数据场景下CBO对查询性能非常重要

三、>

1、Apache>

One size fitsall：统一的SQL查询引擎模块化,插件化，稳定可靠支持异构数据模型
关系型半结构化流式地理空间数据内置RBO和CBO

1.1>

HepPlanner

优化规则(Rule)
Pattern :匹配表达式子树等价变换:得到新的表达式内置有100+优化规则四种匹配规则
ARBITRARY/DEPTH FIRST :深度优先TOP DOWN :拓扑顺序BOTTOM_ UP :与TOP_ DOWN相反遍历所有的rule ,直到没有rule可以被触发优化速度快,实现简单,但是不保证最优

1.2>

VolcanoPlanner

基于Wolcano/Cascade 框架成本最优假设Memo :存储候选执行计划
Group :等价计划集合Top-down 动态规划搜索应用Rule搜索候选计划Memo
本质: AND/OR graph共享子树减少内存开销Group winner:目前的最优计划剪枝：减少搜索空间Top-down遍历：选择winner构建最优执行计划

1.3>

主流的查询优化器都包含RBO和CBOApache Calcite是大数据领域很流行的查询优化器Apache Calcite RBO定义了许多优化规则，使用pattern匹配子树，执行等价变换Apache Calcite CBO基于Volcano/Cascade框架Volcano/Cascade的精髓: Memo、动态规划、剪枝

四、>

1、AI4DB

自配置
智能调参(>负载预测/调度自诊断和自愈合:错误恢复和迁移自优化:
统计信息估计( Learned cardinalities )代价估计学习型优化器( IBM DB2 LEQ )索引/视图推荐

2、DB4AI

内嵌人工智能算法(>内嵌机器学习框架( SparkML，Alink,dl-on-fink )

3、总结

大数据创业如火如荼,>引擎架构的进化、云原生、湖仓一体等对SQL查询优化器有新的要求和挑战AI加持,学习型查询优化器在不断进化

五、>



到此这篇关于SQL Optimizer 解析的文章就介绍到这了,更多相关SQL Optimizer内容请搜索易采站长站以前的文章或继续浏览下面的相关文章希望大家以后多多支持易采站长站！