文章导读：
RBO优化器执行过程
CBO优化器执行过程
CBO的基本实现步骤
通过我们对于SQL优化器及常用优化规则的一些介绍，我们知道RBO和CBO等优化器就是在这些优化规则的基础上对关系表达式做出相应的等价转换，从而生成执行计划。接下来我们一起来看一下RBO和CBO两种优化器的执行过程。
RBO
RBO的执行过程比较简单，主要包含两个步骤：Transformation
和Build Physical Plan
。
Transformation
：遍历关系表达式，只要模式满足特定的优化规则则进行转换。Build Physical Plan
：把上一步生成的逻辑执行计划Build成物理执行计划。即觉得各个Operator的具体实现，如Join算子对应的物理算子到底是BroadcastHashJoin还是SortMereJoin等。
CBO
相对于RBO来说，CBO的优化过程主要包含三步：Exploration
、Build Physical Plan
和Find Best Plan
。
Exploration
：根据优化规则进行等价转换，生成多个逻辑执行计划。Build Physical Plan
：同RBO一样，决定各个Operator的具体实现。Find Best Plan
：根据统计信息计算各个执行计划的Cost，选出Cost最小的执行计划。
CBO有两种实现模型：Volcano
和Cascades
。两者优化思想基本相同，不同点在于Volcano
是先Explore后Build，而Cascades
是边Explore边Build，从而进一步裁剪掉一些执行计划。有兴趣的可以看一下相关论文，我表示没看懂。
CBO优化的关键步骤
我们总是听到CBO的优化是基于成本的、基于代价的。那么都是哪些成本和代价？要想实现CBO又要经历哪几步呢？
第一步：采集数据源的基本信息
采集数据源的基本信息是CBO最基础的一项工作，采集的主要信息包括表级别指标和列级别指标，如：
estimatedSize
: 每个LogicalPlan节点输出数据大小（表级别）rowCount
: 每个LogicalPlan节点输出数据总条数（表级别）basicStats
: 基本列信息，包括列类型、Max、Min、number of nulls, number of distinct values, max column length, average column length等（列级别）Histograms
: Histograms of columns, i.e., equi-width histogram (for numeric and string types) and equi-height histogram (only for numeric types).（列级别）
为什么要采集这些信息？很显然，estimatedSize和rowCount这两个值是算子代价评估的直观体现，这两个值越大，给定算子执行代价必然越大，所以这两个值后续会用来评估实际算子的执行代价。而basicStats和Histograms为了顺着执行语法树往上一层一层推导出所有中间结果的基本信息。
在实际SQL查询时对于大数据量的表我们不可能临时进行全表扫描统计相关的信息，支持CBO的系统一般都实现了相关信息统计的方法。比如Hive
的metastore
中就存储了相关的统计信息，ORC
列式存储格式也存储了该文件相关的统计信息，或者通过Hive
的Analyze
命令、Impala
的Compute
命令可以获取。
第二步：定义核心算子的基数推导规则
规则推导意思是说在当前子节点统计信息的基础上，计算父节点相关统计信息的一套推导规则。对于不同算子，推导规则必然不一样，比如fliter、group by、limit等等的评估推导是不同的。
比如我们执行SQL内又t1.b > 5
这一条件，我们就需要根据我们第一步的统计信息来评估查询成本了。通过第一步的basicStats
信息我们知道了t1.b列的最大最小值，可以直接与常量5
进行判断，看是否满足该条件，如果满足则根据第一步的Histograms
预估满足的数量以便于进行代价计算。
第三步：核心算子实际代价计算
首先，我们提到的代价可以从两个维度进行定义，分别是CPU Cost
和IO Cost
。而实际的代价计算就是依据我们统计信息和推导规则预估出数据的总条数，数据平均大小，数据分布情况等因素。计算出各个执行路径的执行成本。
第四步：选择最优的执行路径
经过前面三步的工作，我们可以很容易的计算出任意一条路径的执行代价。我们将SQL解析出的逻辑计划一个一个计算，必然能得到一个代价最小的也就是最优的执行路径。但是我们这里的讲的最优的执行路径并不一定是代价最小的。
原因是所有的可执行的执行路径实在太多了，所有路径都计算一遍需要耗费大量的时间，那么我们所谓的SQL优化也就没有意义了。那么CBO所作的就是动态规划。选择一条相对稳定且成本较小的执行路径从而达到SQL优化的目的。
SQL优化的基本概念我们都已经过完了，那么是时候再看一眼Calcite了。
参考资料：
https://zhuanlan.zhihu.com/p/40478975
http://hbasefly.com/2017/05/04/bigdata%EF%BC%8Dcbo/
扶我起来，我还能更新~
