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

• 有 MySQL、Oracle 之类使用 SQL 作为交互语言的数据库
• 有 JDBC、ODBC 之类和各种数据库交互的标准接口
• 有大量数据科学家和数据分析师等不太会编程语言但又要使用数据的人
• 多个大数据计算引擎都支持 SQL 作为更高抽象层次的计算入口
  1. MapReduce -> Hive SQL
  2. Spark -> Spark SQL
  3. Flink -> Flink SQL

SQL的处理流程经过了四个组件，分别是Parser、Analyzer、Optimizer、Executor

Parser

1. 把文本变成抽象语法树结构（AST）
2. 涉及词法分析阶段（拆分字符串，提取关键字，字符串，数值等）和语法分析阶段（把词条按照定义的语法规则组装成抽象语法树结构）
3. 和编译原理课程里的“前端”知识相关

Analyzer

1. 访问库/表元信息并绑定
2. 判断 SQL 是否合理，比如数据库，表和列名是否存在，列的数据类型是否正确
3. 将 AST 转换成逻辑计划树（在某些系统中这个工作由一个 Converter 完成）

所谓逻辑计划树，可以理解为逻辑地描述一个 SQL 如何一步步地执行查询和计算，最终得到执行结果的一个分步骤地计划。树中每个节点是是一个算子，定义了对数据集合的计算操作（过滤，排序，聚合，连接），边代表了数据的流向，从孩子节点流向父节点。之所以称它为逻辑的，是因为算子定义的是逻辑的计算操作，没有指定实际的算法，比如对于逻辑的排序算子，逻辑计划树里没有指定使用快排还是堆排。

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

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

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

查询优化器在大数据场景下对查询性能至关重要

• 从目标开始输出从上往下遍历计划树，找到完整的最优执行计划
• 例如：Volcano、Cascade、SQLServer

• 从零开始，从下往上遍历计划树，找到完整的执行计划
• 例如：System R、PostgreSQL、IBM、DB2

基于关系代数等价规则对逻辑计划进行变换 实现上：

• Pattern：定义了特定结构的 Operator 子树（结构）
• Rule：定义了如何将其匹配的节点替换（Substitute）为新形态，从而生成新的、等价的Operator 树（原地替换）
• 优化器搜索过程被抽象为不断匹配 Pattern 然后应用 Rule 转换，直到没有可以匹配的 rule 局限性：
• 无法解决多表连接问题
• 无法确定和选择最优的分布式 Join/Aggregate 执行方式 优化规则：
• 列裁剪
• 谓词下推
• 传递闭包
• Runtime Filter(min-max filter，in-list filter，bloom filter)
• Join 消除
• 谓词合并 优点：实现简单，优化速度快

缺点：不保证得到最优的执行计划

大数据场景下CBO对查询性能非常重要

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

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

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

• 算子代价包含 CPU，cache misses，memory，disk I/O，network I/O 等代价

  • 和算子的统计信息有关，比如输入、输出结果的行数，每行大小等

  • 叶子算子 scan：通过统计原始表数据得到

    • 中间算子：根据一定的推导规则，从下层算子的统计信息推导得到
    • 和具体的算子类型，以及算子的物理实现有关（e.g. hash join vs. sort join）

• 使用动态规划枚举所有执行计划，选出执行代价最小的执行计划 统计信息

• 基表统计信息

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

• 推导统计信息

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

Apache Calcit 是大数据领域很流行的查询优化器，包含RBO和CBO，实际上，主流的查询优化器都包含RBO和CBO

• Apache Calcit RBO定义了很多优化规则，使用pattern匹配子树，执行等价代换来实现最终性能最优
• Apache Calcit CBO基于Volcano/Cascade框架通过对成本进行最优假设来实现最终性能最优，该框架的精髓是Memo、动态规划、剪枝

• 存储计算分离
• HSAP, HTAP, HTSAP
• Cloud Native, Serverless
• 数据仓库，数据湖，湖仓一体，联邦查询
• 智能化
  • AI4DB
    • 自配置：智能调参、负载预测、负载调度
    • 自诊断和自愈合：软硬件错误、错误恢复和迁移
    • 自优化：统计信息估计，索引推荐，视图推荐
  • DB4AI
    • 内嵌人工智能算法（MLSQL，SQLFlow）
    • 内嵌机器学习框架（SparkML， Alink， dl-on-flink ）

最重要的是：SQL查询优化器仍然是必不可少的组件