目录
什么是查询优化器
查询优化器分类
Top-downOptimizer
Bottom-upOptimizer
RBO-关系代数
RBO-优化原则
RBO-列裁剪
RBO-谓词下推
RBO-传递闭包
RBO-RuntimeFilter
小结
CBO（Cost-basedOptimizer）
概念
CBO-统计信息
CBO-统计信息的收集方式
CBO-统计信息推导规则
CBO-统计信息的问题
CBO-执行计划枚举
CBO执行计划枚举-动态规划 编辑
CBO效果-TPC-DSQ25
CBO效果-TPC-DS
CBO小结
小结
什么是查询优化器
前面我们说到了查询的流程：
语法分析：检查SQL拼写和语法是否有问题。
语义检查：检查SQL语句中的访问对象是否存在，即表名、列名啥的；
经过语法分析和语义检查无误之后，就会生成一棵语法分析树，进行优化器优化，生成查询计划。
所以，查询优化器的目标就是找到当前SQL查询的最佳执行计划（或者说查询树），它是由一系列物理操作符组成，这些操作符按照一定的运算关系组成查询的执行计划。
而在查询优化器中，可以分为逻辑优化阶段和物理优化阶段。
逻辑优化，就是通过改变SQL语句的内容来使得查询更加高效，并为物理优化阶段提供更多的候选执行计划。
那逻辑优化是如何改变SQL语句的内容呢？
通常采用的方式是对SQL语句进行等价变换，（基于关系代数）做查询重写。比如说，对条件表达式做等价谓词重写、条件简化，对视图进行重写，对子查询进行优化，对连接语义进行外连接消除、嵌套连接消除等。
逻辑优化中的每一步都对应着物理计算，因此逻辑优化阶段输出若干候选执行计划之后，物理优化阶段会计算这些计划的代价，从中选择代价最小的作为执行计划。
因此逻辑优化属于语法层级的优化，而物理优化实际上是一种依据代价的估算模型，相当于是从连接路径中选择代价最小的路径，因此属于物理层面的优化。
查询优化器分类
Top-downOptimizer
从目标输出开始，由上往下遍历计划树，找到完整的最优执行计划
例子：Volcano/Cascade，SQLServer
Bottom-upOptimizer
从零开始，由下往上遍历计划树，找到完整的执行计划
例子：SystemR，PostgreSQL，IBMDB2
Rule-basedOptimizer（RBO）
根据关系代数等价语义，重写查询
基于启发式规则会访问表的元信息(catalog)，不会涉及具体的表数据(data)
Cost-basedOptimizer（CBO）
使用一个模型估算执行计划的代价，选择代价最小的执行计划
RBO-关系代数
RBO: Rule-Based Optimization也即“基于规则的优化器”，该优化器按照硬编码在数据库中的一系列规则来决定SQL的执行计划。
以Oracle数据库为例，RBO根据Oracle指定的优先顺序规则，对指定的表进行执行计划的选择。比如在规则中：索引的优先级大于全表扫描。
通过Oracle的这个例子我们可以感受到，在RBO中，有着一套严格的使用规则，只要你按照规则去写SQL语句，无论数据表中的内容怎样，也不会影响到你的“执行计划”，也就是说RBO对数据不“敏感”。这就要求开发人员非常了解RBO的各项细则，不熟悉规则的开发人员写出来的SQL性能可能非常差。
但在实际的过程中，数据的量级会严重影响同样SQL的性能，这也是RBO的缺陷所在。毕竟规则是死的，数据是变化的，所以RBO生成的执行计划往往是不可靠的，不是最优的。
变为：
RBO-优化原则
Readdatalessandfaster(I/O)
Transferdatalessandfaster(Network)
Processdatalessandfaster(CPU&Memory)
优化前的逻辑计划：
下面给出四个优化规则：
RBO-列裁剪
对应的算子有没用到的列，实际中就去掉这些列，这样就减少复杂度
RBO-谓词下推
尽早地过滤数据，也就是提前将id>123的数据过滤出来了，也会减少复杂度
RBO-传递闭包
根据表达式子中的pv.userId = user.id条件，其实可以推出 pv.userId也是可以筛选出大于123的数据
RBO-RuntimeFilter
小结
CBO（Cost-basedOptimizer）
概念
使用一个模型估算执行计划的代价，选择代价最小的执行计划
执行计划的代价等于所有算子的执行代价之和
通过RBO得到（所有）可能的等价执行计划
算子代价：CPU，内存，磁盘I/O，网络I/O等代价
和算子输入数据的统计信息有关：输入、输出结果的行数，每行大小...
叶子算子Scan：通过统计原始表数据得到
中间算子：根据一定的推导规则，从下层算子的统计信息推导得到
和具体的算子类型，以及算子的物理实现有关
例子：SparkJoin算子代价=weight*row_count+(1.0-weight)*size
CBO-统计信息
原始表统计信息
表或者分区级别：行数、行平均大小、表在磁盘中占用了多少字节等
列级别：min、max、numnulls、numnotnulls、numdistinctvalue(NDV)、histogram等
推导统计信息
选择率（selectivity）：对于某一个过滤条件，查询会从表中返回多大比例的数据
基数（cardinality）：在查询计划中常指算子需要处理的行数
CBO-统计信息的收集方式
在DDL里指定需要收集的统计信息，数据库会在数据写入时收集或者更新统计信息
手动执行explainanalyzestatement，触发数据库收集或者更新统计信息
动态采样
CBO-统计信息推导规则
假设列和列之间是独立的，列的值是均匀分布
CBO-统计信息的问题
假设列和列之间是独立的，列的值是均匀分布 -->这个假设经常与现实不符
CBO-执行计划枚举
通常使用贪心算法或者动态规划选出最优的执行计划
CBO执行计划枚举-动态规划 
CBO效果-TPC-DSQ25
CBO效果-TPC-DS
CBO小结
CBO使用代价模型和统计信息估算执行计划的代价
CBO使用贪心或者动态规划算法寻找最优执行计划
在大数据场景下CBO对查询性能非常重要
小结
主流RBO实现一般都有几百条基于经验归纳得到的优化规则
RBO实现简单，优化速度快
RBO不保证得到最优的执行计划
CBO使用代价模型和统计信息估算执行计划的代价
CBO使用贪心或者动态规划算法寻找最优执行计划
大数据场景下CBO对查询性能非常重要
