浅谈SQL Optimizer 解析
大数据体系&SQL
一、大数据体系
大数据体系自上而下有七层，分别是：
- 业务应用
业务应用层次，主要业务应用包括BI报表、数据挖掘、营销分析、精准推荐等，主要工作是管控运维。 - 数据开发
数据开发层次，主要技术包括Airflow、DAG等，主要工作是集群创建。 - 权限管控
权限管控层次，主要技术包括Apache Ranger、GDPR等，主要工作是集群创建。 - 分析引擎（SQL）
分析引擎分为批式分析、实时分析、交互分析等，主要工作是集群管理、服务管理。
（1）批式分析
主要包括Spark、Hive、MR等技术。
（2）实时分析
主要包括Flink技术。
（3）交互分析
主要包括Presto、ClickHouse、Doris等技术。 - 资源调度
资源调度层次主要包括YARN、K8S等技术，主要工作是用户管理。 - 存储系统
存储系统层次主要包括HDFS、HBase、NAS、Object Store、数据湖等技术，主要工作是监控报警。 - 基础设施
基础设施层次主要包括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）统计信息
原始表统计信息
- 表或者分区级别：行数、行平均大小、表在磁盘中占用多少字节等
- 列级别：min、max、num nulls、num not nulls、num distinct value(NDV)、histogram等
推导统计信息 - 选择率(selectivity): 对于某一个过滤条件，查询会从表中返回多大比例的数据
- 基数(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