SQL Optimizer 解析｜青训营笔记

这是我参与「第四届青训营」笔记创作活动的的第1天。

1. 大数据体系和SQL介绍：SQL的处理流程、Parser、Analyzer、逻辑计划树、查询优化、物理执行计划、执行终端
2. 常见的查询优化器详解：Top-down/Bottom-up、RBO、CBO
3. 社区开源实践概览：Volcano/Cascade框架
4. SQL相关的前沿趋势介绍：存储计算分离、云原生、湖仓一体、智能化

1.0.1 生产系统中的平台

• 云计算:阿里云，腾讯云，华为云，Google Cloud
• 大数据处理:Amazon AWS，Microsoft Azure

1.0.2 大数据处理相关

• 批式计算（batch computing）：统一收集数据存储到数据库中，然后对数据进行批量处理；
• 流式计算（stream computing）：对数据流进行处理，实时计算；
• 交互分析引擎（interactive computing）：软件实时接收用户数据输入；
• YARN：是一种新的Hadoop资源管理器，它是一个通用资源管理系统，可为上层应用提供统一的资源管理和调度，它的引入为集群在利用率、资源统一管理和数据共享等方面带来了巨大好处；
• Kubernetes：可移植、可扩展的开源平台，用于管理容器化的工作负载和服务，方便进行声明式配置和自动化；

1.0.3 SQL基本用法

• 选择（SELECT）
• 投影（FROM...WHERE...）
• 连接（JOIN）
• 集合操作 并（UNION），交（INTERCEPT），差（EXCEPT）

1.0.4 编译原理

• 词法分析（Lexical Analysis）
• 语法分析（Syntactic Analysis）
• 抽象语法树（AST）

1.0.5 SQL执行计划

• 逻辑计划（Logical Plan）
• 物理计划（Physical Plan）
• 分布式执行计划（Plan Fragment）

1.0.6 SQL基本流程 DAG

1.0.7 分布式系统shuffle

• Broadcast shuffle
• Repartition shuffle

1.0.8 SQL group-by和join执行方式

• Hash-based
• Sort-based

大数据体系全景
业务应用	BI报表、数据挖掘、营销分析、精准推荐	-	管控运维
数据开发	Airflow、DAG	-	集群创建
权限管控	Apache Ranger、GDPR	-	集群创建
分析引擎	批式分析：Spark、Hive、MR实时分析：Flink；交互分析：Presto、ClickHouse、Doris	消息队列:Kafka、Pulsar、NSQ	集群管理、服务管理
资源调度	YARN、K8S	消息队列:Kafka、Pulsar、NSQ	用户管理
存储系统	HDFS、HBase、NAS、Object Store、Data Lake	消息队列:Kafka、Pulsar、NSQ	监控报警
基础设施	ECS、存储、VPC	消息队列:Kafka、Pulsar、NSQ	日志查询

• SQL交互语言数据库
• 数据库交互标准接口
• 便于使用数据同时无需复杂编程
• 大数据计算引擎支持SQL

1.3.1 Parser

• 文本String->抽象语法树AST
• 词法分析：拆分字符串得到关键词、数值常量、字符串常量、运算符号等TOKEN
• 语法分析：将TOKEN组成AST Node，最终组成AST
• 实现：递归下降（ClickHouse），Flex和Bison（PostgreSQL），javaCC（Flink），Antlr（Presto，Spark）

1.3.2 Analyzer

• 访问库/表源信息并绑定：检查并绑定Database、Table、Column等信息
• 判断Query是否合理：检查合法性
• 将AST转化为逻辑计划树

1.3.3 逻辑计划树

• 逻辑地描述SQL如何一步一步执行查询计算最终得到结果的分步计划

• 树中每个节点都是一个算子（Operator），定义对数据集合的计算操作

• 边代表数据流向 从子节点流向父节点

• 仅为逻辑流程，无实际的算法

• 左深树（Left-deep tree）：右边必须为表

1.3.4 查询优化

• SQL为声明式语言，没有定义数据库做法
• 目标：找到一个正确且执行代价最小的物理执行计划
• 复杂 NP-Hard
• SQL越复杂，JOIN表越多，数据量越大，优化意义就越大

1.3.5 物理执行计划 Physical Plan/Executor

拆分时充分考虑数据的亲和性，减少网络传输的Cost

Plan Fragment 执行计划子树

• 目标： 最小化网络数据传输
• 利用数据的物理分布（数据亲和性）
• 增加Shuffle算子

Executor 执行节点

• 单机并行：cache，pipeline，SIMD
• 多机并行：一个Fragment对应多实例

小结

• One SQL rules big data all
• SQL需要依次经过Parser，Analyzer，Optimizer和Executor处理
• 查询优化器是数据库的大脑，对查询性能至关重要
• 查询优化器需要感知数据分布，充分利用数据亲和性
• 查询优化器按照最小化网络数据传输的目标把逻辑计划拆分成多个物理计划片段

2.1.1 Top-Down & Bottom-up Optimizer

• Top-Down：从目标输出开始，由上往下遍历计算树，找到完整的最优执行计划
• Bottom-Up：从零开始，从下往上遍历计划树，找到完整的执行计划

2.1.2 RBO & CBO

• Rule-Based Optimizer： 根据关系代数等价语义重写查询，基于启发式规则，会访问表的原信息，不会涉及具体的表数据
• Cost-Based Optimizer：使用一个模型估算执行计划的代价，选择代价最小的执行计划

2.2.1 关系代数与匹配等价变换

• 运算符：Select($\sigma$), Project($\pi$), Join($\bowtie$), Rename($\rho$), Union($\cup$)
• 等价变换：结合律、交换律、传递性

2.2.2 优化原则

• 少读取、快读取：Read data less and faster（I/O）
• 少交换、快交换：Transfer data less and faster（Network）
• 少处理、快处理：Process data less and faster （CPU & Memory）

2.2.3 优化方法

列裁剪

• 尽早去掉不需要的列
• 从上向下进行扫描，计算上层算子需要的列，去除不需要的列，传递到下层算子再与下层算子需要的列进行集合，再向下传递...
• SELECT A,B FROM...

谓词下推

• 将过滤条件下推，实现数据提前过滤
• 下推取决于JOIN的类型，不同JOIN的下推方式不同
• SELECT A FROM...WHERE A.id>123;

传递闭包（高级）

• 根据表达式的等价关系及过滤条件，推导出更全面的过滤条件，实现更加完全的过滤
• SELECT...FROM...JOIN...ON A.id=B.id WHERE B.id>123; （推出A.id>123的新Filter）

Runtime Filter

• 运行时时才能产生，在数据库中广泛使用
• 在运行中扫描单边时对数据进行简单统计（min-max，in-list，bloom filter）得到扫描的数据范围并提供给另外一边，使得扫描另外半边表时可以得知需要的范围，进行提前过滤，节约数据传输
• 缺点：min-max只能处理数据比较集中的情况；in-list只能处理数据可取值相对较小的情况；

小结

• 主流RBO实现有几百条基于经验的优化规则
• 优点：实现简单，优化速度快
• 缺点：不保证得到最优的执行计划
• 单表扫描：索引扫描（随机IO）vs全表扫描（顺序IO）: 如果查询的数据分布非常不均衡，索引扫描不如全表
• Join的实现：无法区分Hash和SortMerge的优劣
• 两表Hash Join：无法识别小表构建哈希表
• 多表Join：无法确定最优连接顺序，无法确定是否需要探索每种组合（O(N!)），可能内存溢出

2.3.1 概念

• 使用一个模型估算执行计划的代价，选择代价最小的执行计划

• 执行计划的代价等于所有算子的执行代价之和

• 通过RBO得到所有（可能非所有）可能的等价执行计划

• 算子代价：CPU、内存、磁盘IO、网络IO代价

• 和算子输入数据的统计信息有关：输入输出结果的行数、每行大小。。。

• 叶子算子Scan：通过统计原始表数据

• 中间算子：根据一定的推导规则，从下层算子的统计信息推导得到

• 和具体的算子类型以及算子的物理实现有关

• e.g. Spark Join 算子代价$=weight* rowcount-（1.0-weight）* size$

2.3.2 统计信息

原始表统计信息：叶子算子Scan

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

原始统计信息收集方式：

• DDL里制定需要收集的统计信息，数据库在数据写入时收集或更新统计信息 PRPOPERTIES（缺点：影响实时导入的速率）
• 手动执行 explain analyze statement，触发数据库收集或更新信息 ANALYZE TABLE...COMPUTE STATISTICS FOR COLUMNS... （缺点：修改数据表后如果没有手动执行就会是旧状态）
• 动态采样 SELECT count(*) FROM table

推导统计信息：中间算子

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

统计信息推导规则：假设列和列之间是独立的，列的值均匀分布

Filter Selectivity (fs 选择率）

• 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; otherwise, 1/NDV;
• 小于条件 (x<literal): literal<min: 0;literal>max: 1; otherwise: (litera-min)/(max-min);

CARDINALITY（FILTER）=CARDINALITY（A）* SELECTIVITY（FILTER）

统计信息的问题

假设列列独立，列值均匀分布——与现实不符

• 列列之间可以关联：解决方法为用户指定/数据库自动识别相关联的列
• 列值不是均匀分布：解决方法为实用直方图处理

2.3.3 执行计划枚举

• 单表扫描：索引扫描（随机IO）vs全表扫描（顺序IO）: 如果查询的数据分布非常不均衡，索引扫描不如全表
• Join的实现：无法区分Hash和SortMerge的优劣
• 两表Hash Join：无法识别小表构建哈希表
• 多表Join：无法确定最优连接顺序，无法确定是否需要探索每种组合（O(N!)），可能内存溢出

通常使用贪心算法或动态规划选出最优执行计划，从局部最优解开始推导全局最优解

动态规划

• 分解到最低子问题，确定子问题的解决方案
• 寻找子问题的不同解决方法，计算Cost，选出每种方案的最低Cost实现方法
• 扩大化问题，计算下一步解决问题的不同方案及对应Cost
• 重复直至完成问题
• 计算每条经由的总Cost，得出最低Cost的经由路线，得到最优解

CBO效果 （见TPC-DS Q25）

• 关闭CBO：shuffle数据量太大，执行效率差
• 开启CBO：减少90%shuffle数据量，加速3.4倍
• 大概一半的查询无性能变化：RBO能找到最优执行计划；但16个查询在CBO下有更好的执行性能（总体性能提升30%，加速比2.2X～8X）

小结

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

数据库	SQL Optimizer选型
Hive、Flink、Alibaba MaxCompute等	基于Apache Calcite，属于Volcano/Cascade框架
Greenplum、HAWQ	自研Orca，属于Volcano/Cascade框架
Alibaba Hologres（定位HSAP）	基于Orca，属于Volcano/Cascade框架
TiDB	自研，属于Volcano/Cascade框架
Spark	自研，RBO+CBO
Presto	自研，RBO+CBO
Doris	自研，RBO+CBO
ClickHouse	自研，RBO
Alibaba OceanBase	自研，RBO+CBO

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

• 得到表达式-传递Parser语法解析-实现算子表达式-查询优化
• Expression Builder-实现算子表达式
• Metadata/Plugable rules-查询优化

Calcite RBO

• Help Planner
  • 优化规则（Rule）
    • pattern：匹配表达式子树
    • 等价变换：得到新的表达式
  • 内置100+优化规则
  • 四种匹配规则
    • ARBITRARY/DEPTH_FIRST：深度优先
    • TOP_DOWN：拓扑顺序
    • BOTTOM_UP：与TOP_DOWN相反
  • 遍历所有rule直到没有rule可以触发
  • 优化速度快、实现简单，但不保证最优

Calcite CBO

• Volcano Planner

  • 基于Volcano/Cascade框架

  • 成本最优假设

  • Memo：存储候选执行计划

    • Group：逻辑等价的计划集合
    • 本质是 AND/OR graph
    • 共享子树减少内存开销

  • 应用rule搜索候选计划，通过规则变换计算各种Group的最优代价，记录Group Winner（目前的最优计划）

  • 剪枝（branch-and-bound pruning）减少搜索空间：总Cost-自己的Cost=子节点Cost上限，在变换时可以去除子节点Cost大于上限的路径

  • Top-down遍历 动态规划搜索：选择winner构建最优执行计划

小结

• 主流的查询优化器都包含RBO和CBO
• Apache Calcite是大数据领域流行的查询优化器
• Apache Calcite RBO定义许多优化规则，使用pattern匹配子树执行等价变换
• Apache Clacite CBO基于volcano/Cascade框架
• Volcano/Cascade精髓在于Memo、动态规划、剪枝

• 对SQL优化器有新的要求
  • 引擎架构的进化 解耦、池化、一体化
    • 存储计算分离
    • 一体化（HTAP、HSAP、HTSAP）
  • Cloud 云原生/云中立 serverless
    • 根据负载规模调整计算节点流量，节约成本
  • 湖仓一体：统一SQL同时查询湖仓 Query Federation
    • 数据仓库：定义表原型、关系型表形成模型提前过滤存储
    • 数据湖：存储原始数据，但无统一规则
  • DATA+AI：数据查询AI结合 DB4AI&AI4DB

4.2.1 AI4DB

• 自配置
  • 智能调参（OtterTune、Qtune）
  • 负载预测、调度：提前扩源
• 自诊断和自愈合：错误恢复和迁移
• 自优化：
  • 统计信息估计（Learned cardinalities）：更准确
  • 代价估计
  • 学习型优化器（IBM DB2 LEO）
  • 索引/视图推荐：常用查询存储

4.2.2 DB4AI

• 内嵌人工智能算法（MLSQL、SQLFlow）
• 内嵌机器学习框架（SparkML、Alink、dl-on-flink）

小结

• SQL查询优化器仍然必不可少
• 引擎架构进化、云原生、湖仓一体对SQL查询优化器有新要求新挑战
• AI加持学习型查询优化器在不断进化

1. Hash和MergeSort分别如何实现？
   Hash比较哈希值，MergeSort通过两侧指针比较前移较小指针；
2. 计算和存储分离会产生通信开销，如何处理？ 趋势是云计算，在低谷期无需大量计算节点。云计算可以更好的调整计算节点；通信开销已经不是明显的bottleneck，而I/O，CBO等问题更大；
3. CBO使用贪心和动态规划的区别，适用场景？ 不需要很好的CBO-简单贪心；复杂Query贪心无法解决-动态规划；主要是实现上的考虑；

• Volcano/Cascade框架：详见前文3.1 Calcite CBO

Cascade Optimizer在搜索过程中，搜索空间由关系代数算子树组成森林（Memo）。森林中存在Expression Group，每个Group中保存逻辑等价的Group Expression。

Memo本质是AND/OR图，通过共享相同子树减少内存开销，记录搜索过的子树的最优执行计划（Group winner）

Branch-and-Bound Pruning：已搜索完成的physical计划代价最小值成为代价上限（Cost Upper Bound），当新搜索代价高于它时停止搜索。初始上限可有优化器根据启发式规则估算。

1. 复杂知识点

• RBO/CBO 对比，应用环境，优化方法
• Volcano如何实现搜索最优路径：Memo、动态规划、剪枝

2. 个人总结 本堂课我学习了SQL优化相关的知识，从底层了解了RBO、CBO不同优化的实现原理、优缺点等，并且通过实际框架简单认识了生产中采用的优化策略。同时，我还接触了SQL未来发展的方向，认识了AI在SQL和数据库中的运用。我个人原本SQL仅限于运用层面，对于SQL底层实现以及算法优化只略知皮毛。通过本节课的学习，我对于SQL及数据库计算有了更深层次的认识。

1. 【大数据专场 学习资料一】第四届字节跳动青训营 juejin.cn/post/712275…

• 笔记中课前学习、实践练习例的总结来源于本篇学习资料。