浅谈SQL Optimizer 解析

大数据体系&SQL
一、大数据体系
大数据体系自上而下有七层，分别是：

1. 业务应用
   业务应用层次，主要业务应用包括BI报表、数据挖掘、营销分析、精准推荐等，主要工作是管控运维。
2. 数据开发
   数据开发层次，主要技术包括Airflow、DAG等，主要工作是集群创建。
3. 权限管控
   权限管控层次，主要技术包括Apache Ranger、GDPR等，主要工作是集群创建。
4. 分析引擎（SQL）
   分析引擎分为批式分析、实时分析、交互分析等，主要工作是集群管理、服务管理。
   （1）批式分析
   主要包括Spark、Hive、MR等技术。
   （2）实时分析
   主要包括Flink技术。
   （3）交互分析
   主要包括Presto、ClickHouse、Doris等技术。
5. 资源调度
   资源调度层次主要包括YARN、K8S等技术，主要工作是用户管理。
6. 存储系统
   存储系统层次主要包括HDFS、HBase、NAS、Object Store、数据湖等技术，主要工作是监控报警。
7. 基础设施
   基础设施层次主要包括ECS、存储、VPC等技术，主要工作是日志查询。
   二、SQL的处理流程
   SQL的处理需经过Parser，Analyzer，Optimizer和Executor处理过程。

1.Parser
（1）把文本变成抽象语法树结构（AST）
（2）经过词法分析（拆分字符串，得到关键词、数值常量、字符串常量、运算符号等）得到token
(3)经过语法分析将token组成AST node组成AST node，最终得到一个AST
2.Analyzer
检查并绑定Database，Table，Column等元信息
SQL的合法性检查，比如min/max/avg的输入是数值
AST->Logical Plan
Logical Plan
1.逻辑的描述SQL对应的分布骤计算操作
2.计算操作：算子（operator）
3.Optimizer
Optimizer是查询优化，它的主要工作是优化数据访问，根据提交的SQL语句，综合各种已有的信息（主要是系统编目表）来产生最优的可执行的访问方案。
physical plan
1.目标：最小化网络传输
2.利用上数据的物理分布（数据亲和性）
3.增加shullfe算子
4.Executor
Executor分为单机与多机并行。
单机并行包括：cache，pipeline，SIMD。
多机并行包括：一个fragment对应多个实例。
常见的查询优化器
一、查询优化器的分类
1、Top-down Optimizer
从目标输出开始，自上而下遍历计划树，找到完整的最优执行计划
2、Bottom-up Optimizer
从零开始，自下而上遍历计划树，找到完整的执行计划
3、Rule-based Optimizer
根据关系代数等价语义，重写查询；基于启发式规则；会访问表的元信息（catalog），不会涉及具体表数据（data）。
4、Cost-based Optimizer
使用一个模型估算执行计划的代价，选择代价最小的执行计划
二、RBO（Rule-based Optimizer）
1、RBO（Rule-based Optimizer）原理
ROB（Rule-based Optimizer)是基于规则的优化器，原理包括两方面：
(1)利用关系代数，即运算符select，project，join等
(2)利用等价变换，即结合律、交换律、传递性等
2、RBO（Rule-based Optimizer）优化原则
（1）读数据操作尽可能少，尽可能快（I/O）
（2）传输数据尽可能少，尽可能快（Network）
（3）处理数据尽可能少，尽可能快（CPU & Memory）
3、RBO（Rule-based Optimizer）主要优化方式
（1）列剪裁
将不需要的列信息直接裁剪，大幅度减少查询时读取的读取数据量

（2）谓词下推
将数据过滤条件向下推，大幅度减少join操作时所需要读取的数据量

（3）传递闭包
利用等价条件和过滤条件推出新的过滤条件，从而在谓词下推操作的基础上再次减少join操作所需要读取的数据量

（4）Runtime Filter
在运行时利用列数据的min-max，in-list等信息减少Filter操作时所需要读取的数据量

4、RBO（Rule-based Optimizer）小结

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

三、CBO（Cost-based Optimizer）
1、CBO概念
CBO（Cost-Based Potimizer）是基于成本的优化器，它使用一个模型估算执行计划，选择代价最优的执行计划，执行计划的代价等于所有算子的执行代价之和，通过RBO得到（所有）可能的等价执行计划。
算子的代价包括CPU、内存、磁盘IO、网络IO等代价。
2、CBO过程
统计信息+推导规则->计算算子代价->计算执行计划代价->执行计划枚举

3、统计信息
（1）统计信息
原始表统计信息

1. 表或者分区级别：行数、行平均大小、表在磁盘中占用多少字节等
2. 列级别：min、max、num nulls、num not nulls、num distinct value(NDV)、histogram等
   推导统计信息
3. 选择率(selectivity): 对于某一个过滤条件，查询会从表中返回多大比例的数据
4. 基数(cardinality): 在查询计划中常指算子需要处理的行数
   （2）统计信息的收集方式
   1.在DDL指定需要收集的统计信息，数据库会在数据写入时收集或更新统计信息

2.手动执行explain、analyze、statement触发数据库收集或者更新统计信息

3.动态采样等

（3）统计信息推导规则（前提假设列和列之间独立，列的值是均匀分布）
①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: 0 V1/NDV
⑤小于条件 (x < literal) literal < min: 0 literal > max: 1 (literal - min) / (max - min)
4、执行计划枚举
通常使用贪心算法或动态选出最优的执行计划
5、CBO小结

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

社区开源实践
一、概览
目前社区开源实践的数据库包含以下几类

二、Apache Calcite
1、概览

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

2、Calcite RBO
HepPlanner
1.优化规则(rule)>>>>pattern:匹配表达式子树>>>>>等价交换：得到新的表达式
2.内置100+种优化规则
3.四种匹配规则
(1) ARBITRARY/DEPTH_FIRST:深度优先
(2) TOP DOWN:拓扑顺序
(3) BOTTOM_UP:与TOP_DOWN 相反
4.遍历所有的rule直到没有rule可以被触发
5.优化速度快，实现简单，但是不保证最优
3、Calcite CBO
VolcanoPlanner

基于Volcano/Cascadek框架
成本最优假设
Mome：存储候选执行计划
Group：等价计划合集
Top-down：动态规划搜索
Volcano/Cascadek精髓：Memo、动态规划、剪枝

前沿趋势
一、引擎架构的进化

存储计算分离
一体化（HTAP、HSAP、HTSAP）

二、Cloud云原生

serverless

三、湖仓一体

Query Federation

四、DATA + AI
1、AI4DB

自配置（智能调参、负载预测/调度）
自诊断和自愈合（错误恢复和迁移）
自优化（统计信息估计、代价估计、学习型优化器、索引/视图推荐）

2、DB4AI