SQL Optimizer 解析｜青训营笔记

​

一、大数据体系和SQL

1.1 大数据体系中的SQL

1.2 SQL的处理流程

Parser

1. 把文本变成抽象语法树结构
2. 涉及词法分析阶段（拆分字符串、得到关键词、数值常量、字符串常量、运算符等）和语法分析阶段（把词条按照定义的语法规则组装成抽象语法树结构）

Analyzer

1. 检查并绑定Database、Table、Column等信息
2. SQL的合法性检查
3. 将AST转换成逻辑计划树

Logical Plan

1. 逻辑地描述SQL对应的分步骤计算操作
2. 计算操作：算子（operator）

树中每个节点是是一个算子，定义了对数据集合的计算操作（过滤，排序，聚合，连接），边代表了数据的流向，从孩子节点流向父节点。之所以称它为逻辑的，是因为算子定义的是逻辑的计算操作，没有指定实际的算法，比如对于逻辑的排序算子，逻辑计划树里没有指定使用快排还是堆排。

Optimizer

1. SQL是一种声明式的语言，用户只描述做什么，没有告诉数据库怎么做
2. 查询优化的目标是为SQL找到一个正确且执行代价最小的执行计划
3. 查询优化器是数据库的大脑，最复杂的模块，很多相关问题都是NP的
4. 一般SQL越复杂，Join的表越多。数据量越大，查询优化的意义就越大，因为不同执行方式的性能差别可能有成百上千倍

Physical Plan

1. 优化器的输出是一个分布式的物理执行计划
2. 分布式物理执行计划的目标是在单机Plan的基础上最小化数据移动和最大化本地Scan，生成Plan Fragment树
3. 一个Plan Fragment封装了在一台机器上对数据集的操作逻辑。每个Plan Fragment可以在每个executor节点生成1个或多个实例，不同执行实例处理不同的数据集，通过并发来提升查询性能
4. Plan分布式化的方法是增加shuffle算子，执行计划树会以shuffle算子为边界拆分为Plan Fragment

Executor

1. Executor按照物理执行计划扫描和处理数据，充分利用机器资源（CPU流水线、乱序执行、cache、SIMD）

二、常见的查询优化器

2.1 RBO

• 根据关系代数等价语义，重写查询
• 基于启发式规则
• 会访问表的元信息，不会涉及具体的表数据

优化规则

SQL语句

列裁剪>>谓词下推>>传递闭包>>运行时优化

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

2.2 CBO

• 使用一个模型估算执行计划的代价，选择代价最小的执行计划
• 分而治之，执行计划的代价等价于所有算子的执行代价之和
• 通过RBO得到（所有）可能的等价执行计划
• 算子代价包括：CPU、内存、磁盘I/O、网络I/O
• 使用贪心或动态规划算法寻找最优执行计划

基表统计信息

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

推导统计信息

• 选择率：对于某一个过滤条件，查询会从表中返回多大比例的数据
• 基数：基本含义是表的 unique 行数，在查询计划中常指算子需要处理的行数

三、查询优化器的社区开源实践

四、前沿趋势