Spark SQL核心是Catalyst, Catalyst执行流程主要分4个阶段, 语句解析, 逻辑计划与优化, 物理计划与优化, 代码生成
前三个阶段都由Catalyst负责, 其中, 逻辑计划的优化采用RBO思路, 物理计划的优化采用CBO思路

RBO (Rule Based Optimization)

基于规则优化, 通过一系列预定好的规则(Rule)对逻辑计划进行等价转换, 以提高查询效率
两个主要思路

• 减少参与计算的数据量
• 降低重复计算的代价

常用的规则都基于经验指定, 可覆盖大部分查询场景, 且方便扩展, 缺点是不够灵活
常用规则例如

• 常量折叠(ConstantFolding)
  把纯常量运算表达式预先转化, 比如把1+2转化为3.0, 消除不必要的重复计算

• 谓词下推(PushdownPredicate)
  最常见的用于减少参与计算的数据量的方法
  谓词, where条件, join on中的过滤条件
  将SQL语句中的谓词逻辑尽量提前执行, 参与join的数据量大大减少, 使得join操作速度大大提高

• 列裁剪(ColumnPruning)
  在扫描表时, 只筛选出符合后续逻辑计划的最小列集合, 节省掉扫描全部列的资源
  如果使用的Parquet,ORC等列式存储格式持久化的, 效率会更高

CBO (Cost Based Optimization)

基于代价优化
CBO优化主要在物理计划层, 原理是计算所有可能的物理计划的代价, 并挑选出代价最小的计划
充分考虑了数据本身的特点(大小, 分布)以及操作算子的特点(中间结果集的分布及大小)及代价, 从而更好的选择执行代价最小的计划

物理执行计划是一个树状结构, 其代价等于每个执行节点的代价总和
每个执行节点的代价, 分为两个部分

1. 该执行节点对数据集的影响, 即该节点输出数据集的大小与分布, 又分为两个部分
   • 初始数据集, 其大小与分布可直接通过统计得到
   • 中间节点输出数据集的大小与分布, 可由其输入数据集的信息与操作本身的特点推算
2. 该执行节点操作算子的代价, 相对固定, 可用规则来描述

CBO优化有, Build侧选择, 优化Join类型, 优化多表Join顺序等

CBO的问题
数据统计信息普遍缺失, 统计信息的收集代价较高
储存计算分离的架构, 使得收集到的统计信息可能不再准确
Spark部署在某个单一硬件架构上, cost很难被估计
Spark的UDF简单易用, 种类繁多, 但是对于CBO来说是黑盒, 无法估计cost

AQE (Adaptive Query Execution)

CBO是一种静态优化策略, 一旦执行计划交付运行, 就不能再对物理计划进行修改
在分布式系统中使用CBO是一个极其复杂的问题, 在Spark中收集和维护一组准确和最新的统计数据是昂贵的

AQE是Spark SQL的一种动态优化机制, 在运行时, 每当Shuffle Map阶段执行完毕, AQE都会
结合这个阶段的统计信息, 基于既定的规则动态的调整, 修正尚未执行的逻辑计划和物理计划, 来
完成对原始查询语句的运行时优化

AQE的统计信息与CBO不同, 不是关于表, 而是Shuffle Map阶段输出的中间文件
AQE从运行时获取统计信息, 在条件允许的情况下, 优化决策会分别作用到逻辑计划和物理计划

AQE三大特性

• 自动分区合并
  在Shuffle过后, Reduce Task数据分布参差不齐, AQE将自动合并过小的数据分区

• Join策略调整
  如果某张表在过滤后, 尺寸小于广播变量阈值, 这张表参与的Join就会从Shuffle Sort
  Merge Join 降级为执行效率更高的Broadcast Hash Join

• 自动倾斜处理
  结合配置项, AQE自动拆分Reduce阶段过大的数据分区, 降低单个Reduce Task的工作负载

参考文献

CBO探究
Spark AQE新特性
CBO 基于代价的优化
Catalyst 内部原理 与 RBO