SQL Optimizer 详细解析

亲爱的编程学习爱好者，如果你点开了这篇文章，说明你对《SQL Optimizer 详细解析》很感兴趣。本篇文章就来给大家详细解析一下，主要介绍一下SQLOptimizer，希望所有认真读完的童鞋们，都有实质性的提高。

一、 大数据体系和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 max : 0
    • 1/NDV
• 小于条件(x
• literal<0>