SQL Optimizer 解析｜青训营笔记

课程资料

• 完整手册：https://bytedance.feishu.cn/docx/doxcnECGEFkCKYqbxaDipK1qrVf
• 课程链接：https://live.juejin.cn/4354/yc_SQL
• 学员手册：https://juejin.cn/post/7122754431371706404#heading-0
• 课程PPT：https://bytedance.feishu.cn/file/boxcn9uWBTLWg2a8GIUSRJ0Txqb

一、大数据体系和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 行数，在查询计划中常指算子需要处理的行数

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

四、前沿趋势

推荐资料

以下资料引用自学生手册：

1. CMU 数据库相关课程，第一个是初级课程，第二个是高级课程。

• 15445.courses.cs.cmu.edu/fall2021/

• 15721.courses.cs.cmu.edu/spring2020/

1. Access Path Selection in a Relational Database Management System

如果说选一篇在优化器框架上，被引用次数最多的文献，应该非这篇论文莫属了，这篇文章介绍了 System R 的优化器，其中关于 Join order enumeration，Selinger 可以说是开创了 dynamic programing based 的 bottom-up 的搜索空间算法的先河，直至今日，很多成熟的商业或开源数据库系统仍在沿用这套框架，比如Oracle / DB2 / PostgreSQL ...

1. Volcano/Cascades 框架相关论文

• The Volcano Optimizer Generator : Extensibility and Efficient Search

• The Cascades Framework for Query Optimization

• Efficiency in the Columbia Database Query Optimizer

  这篇 paper 从实现的角度详细讲解了 columbia optimizer 的设计和实现，它完全参考了 volcano/cascades 中的概念和 top-down 的搜索策略，并做了一系列优化来改善 volcano/cascades 的优化效率。

1. Apache Calcite: A Foundational Framework for Optimized Query Processing Over Heterogeneous Data Sources

1. github.com/pingcap/awe…

1. 以下这几篇文章从各自的角度回顾大数据系统的过去和展望大数据系统的未来，拓展大家的视野，激发大家投身大数据的热情。

• 解读数据架构的2021：大数据1.0体系基本建成，但头上仍有几朵乌云架构关涛 Tony_InfoQ精选文章

• 面向未来的HTSAP一体化数据平台该是什么样子？文化 & 方法张翔_InfoQ精选文章

• 云原生数据库设计新思路