SQL Optimizer

一、 大数据体系和SQL

1、SQL的处理流程

1.1 Parser

String -> AST (Abstruct Syntax Tree)：

• 词法分析:拆分字符串，得到关键词、数值常量、字符串常量、运算符号等token
• 语法分析:将token组成ASTnode，最终得到一个AST

实现：递归下降 (ClickHouse)，Flex 和 Bison (PostgreSQL)，JavaCC (Flink)，Antlr (Presto，Spark)

1.2 Analyzer和Logical Plan

 Analyzer：

• 检查并绑定Database, Table, Column等元信息
• SQL的合法性检查，比如min/max/avg的输入是数值
• AST -> Logical Plan

 Logical Plan：

• 逻辑地描述SQL对应的分步骤计算操作
• 计算操作:算子( operator )

1.3 Physical Plan 和 Executor

 Physical Plan: 执行计划子树

• 目标:最小化网络数据传输
• 利用上数据的物理分布(数据亲和性)
• 增加Shuffle算子

 Executor

• 单机并行: cache，pipeline, SIMD
• 多机并行: 一个fragment对应多个实例

1.4 小结

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

二、 常见的查询优化器

1、查询优化器分类

2、RBO（Rule-based optimizer）

2.1 关系代数

• 运算符：Select Project Join Rename Union
• 等价变换：结合律、交换律、传递性

2.2 优化原则

2.3 RBO-列裁剪

• 扫描表格中所需要的列，而不是全部

2.4 RBO-谓词下推

• where的表达式是谓词。谓词尽快过滤数据，减少开销2（条件：join是inter）

2.5 RBO-传递闭包

• 根据表达式等价关系，过滤条件，推导出一个新的过滤条件

2.6 RBO-Runtime Filter

对一个join如果能在查询端提早过滤不必要数据，可减少开销

• min-max的缺点：范围必须很紧密
• in-list：只需要扫描in-list里的数据。缺点：集合个数很多时，in-list也很大
• bloom filter：特性：大小不随集合大小改变，固定大小，给一个数可以判断在不在

2.7 小结

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

3、CBO（Cost-based optimizer）

3.1 CBO-概念

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

• 执行计划的代价等于所有算子的执行代价之和
• 通过RBO得到(所有)可能的等价执行计划

△算子代价:CPU，内存，磁盘IO，网络I/O等代价

统计信息+推导规则→计算算子代价→计算执行计划代价→执行计划枚举

3.2 CBO-统计信息

原始表统计信息

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

推导统计信息

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

3.2.1 CBO-统计信息的收集方式

• 在DDL里指定需要收集的统计信息，数据库会在数据写入时收集或者更新统计信息

CREATE TABLE REGION( R_ REGIONKEY INT NOT NULL, R NAME CHAR(25) NOT NULL, R_ COMMENT VARCHAR(152) ) DUPLICATE KEY(R_ REGIONKEY) DISTRIBUTED BY HASH(R_ REGIONKEY) BUCKETS 1 PROPERTIES (" sotumnselelR w");

• 手动执行explain analyze statement，出发数据库收集或者更新统计信息

ANALYZE TABLE table_name COMPUTE STATISICS FOR COLUMNS column-name1,column-name2....

动态采样：

SELECT count(*) FROM table_name

3.2.2 CBO-统计信息推导规则

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

3.3 CBO-执行计划枚举

• 单表扫描:索引扫描(随机I/O) vs 全表扫描(顺序IO)
  • 如果查询的数据分布非常不均衡，索引扫描可能不如全表扫描
• Join的实现: Hash Join Vs. SortMerge Join
• 两表Hash Join :用小表构建哈希表如何识别小表?
• 多表Join :
  • 哪种连接顺序是最优的?
  • 是否要对每种组合都探索?
• N个表连接,仅仅是left-deep tree就有差不多N!种连接顺序
  • e.g. N= 10->总共3, 628, 800个连接顺序

3.4 CBO-小结

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

4、总结

• 主流RBO实现-般都有几百条基于经验归纳得到的优化规则
• RBO实现简单，优化速度快
• RBO不保证得到最优的执行计划
• CBO使用代价模型和统计信息估算执行计划的代价
• CBO使用贪心或者动态规划算法寻找最优执行计划
• 大数据场景下CBO对查询性能非常重要

三、 社区开源实践

1、Apache Calcite概览

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

1.1 Calcite RBO

HepPlanner

• 优化规则(Rule)
  • Pattern :匹配表达式子树
  • 等价变换:得到新的表达式
• 内置有100+优化规则
• 四种匹配规则
  • ARBITRARY/DEPTH FIRST :深度优先
  • TOP DOWN :拓扑顺序
  • BOTTOM_ UP :与TOP_ DOWN相反
• 遍历所有的rule ,直到没有rule可以被触发
• 优化速度快,实现简单,但是不保证最优

1.2 Calcite CBO

VolcanoPlanner

• 基于Wolcano/Cascade 框架
• 成本最优假设
• Memo :存储候选执行计划
  • Group :等价计划集合
• Top-down 动态规划搜索
• 应用Rule搜索候选计划
• Memo
  • 本质: AND/OR graph
  • 共享子树减少内存开销
• Group winner:目前的最优计划
• 剪枝：减少搜索空间
• Top-down遍历：选择winner构建最优执行计划

1.3 小结

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

四、 前沿趋势

1、AI4DB

• 自配置
  • 智能调参( OtterTune , QTune )
  • 负载预测/调度
• 自诊断和自愈合:错误恢复和迁移
• 自优化:
  • 统计信息估计( Learned cardinalities )
  • 代价估计
  • 学习型优化器( IBM DB2 LEQ )
  • 索引/视图推荐

2、DB4AI

• 内嵌人工智能算法( MLSQL,SOLFlow )
• 内嵌机器学习框架( SparkML，Alink,dl-on-fink )

3、总结

• 大数据创业如火如荼, SQL查询优化器仍然是必不可少的一个重要组件
• 引擎架构的进化、云原生、湖仓一体等对SQL查询优化器有新的要求和挑战
• AI加持,学习型查询优化器在不断进化

五、 大总结