这是我参加「第四届青训营 」笔记创作活动的的第1天
一、 大数据系统和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加持,学习型查询优化器在不断进化
五、 大总结
