BigData－‘基于代价优化’究竟是如何一回事？

　　BigData－‘基于代价优化’究竟是如何一回事？

　　本文系转载，如有侵权，立删

　　还记得笔者在下篇文章无意中挖的一个坑么？如若不知，强烈建议看官先行阅读上面两文－《SparkSQL – 有必要坐出来说说Join》和《BigData – Join中居然也有子句下推!?》。第一篇文章主要剖析了大数据领域Join的三种基础算法以及各自的适用场景，第二篇文章在第一篇的基础上进一步深入，讨论了Join基础算法的一种优化方案 – Runtime Filter，文章最后还引申地聊了聊子句下推技术。同时，在第二篇文章开头，笔者引出了两个问题，SQL执行引擎怎么知晓参与Join的两波数据集大小？衡量两波数据集大小的是化学大小还是纪录多少甚或二者都有？这关系到SQL解析器怎样正确选择Join算法的问题。好了，这些就是这篇文章要为你们带来的议程－基于代价优化（Cost-Based Optimization，简称CBO）。

　　CBO基本原理

　　提到CBO，就不得不提起一位’老熟人’ – 基于规则优化（Rule-Based Optimization，简称RBO）。RBO是一种经验式、启发式的优化思路，优化规则都早已预先定义好，只须要将SQL往这种规则上套就可以（对RBO还不了解的童鞋，可以参考笔者的另一篇文章 – 《从0到1认识Catalyst》)。说白了，RBO如同是一个经验丰富的老司机，基本套路全都晓得。

　　然而世界上有一种东西称作 – 不按套路来，与其说它不按套路来，倒不如说它本身并没有哪些套路。最典型的莫过于复杂Join算子优化，对于那些Join来说，通常有两个选择题要做：

　　1. Join应当选择哪种算法策略来执行？BroadcastJoin or ShuffleHashJoin or SortMergeJoin？不同的执行策略对系统的资源要求不同，执行效率也有天壤之别，同一个SQL，选择到合适的策略执行可能只须要几秒钟，而假如没有选择到合适的执行策略就可能会造成系统OOM。

　　2. 对于雪花模型或则星型模型来讲，多表Join应当选择什么样的次序执行？不同的Join次序意味着不同的执行效率，比如A join B join C，A、B表都很大，C表太小，那A join B很显然须要大量的系统资源来运算，执行时间必然不会短。而假如使用A join C join B的执行次序，因为C表太小，所以A join C会很快得到结果，而且结果游行太小，再使用小的结果集 join B，性能显而易见会好于前一种方案。

　　大家想想，这有哪些固定的优化规则么？并没有。说白了，你须要晓得更多关于表的基础信息（表大小、表记录总条数等），再通过一定规则代价评估能够从中选择一条最优的执行计划。CBO意为基于代价优化策略，就是从多个可能的语法树中选择一条代价最小的语法树来执行，换个说法，CBO的核心在于评估出一条给定语法树的实际代价。比如下边这颗SQL语法树：

　　

　　要评估给定整棵树的代价，分而治之只须要评估每位节点执行的代价，最后将所有节点代价累加即可。而要评估单个节点执行实际代价，又须要晓得两点，其一是这些算子的代价规则，每种算子的代价估算规则必然都不同，比如Merge-Sort Join、Shuffle Hash Join、GroupBy都有自己的一套代价估算算法。其二是参与操作的数据集基本信息（大小、总记录条数），比如实际参与Merge-Sort Join的两表大小，作为节点实际执行代价的一个重要诱因，当然特别重要。试想，同样是Table Scan操作，大表和小表的执行代价必然不同。

　　为给定算子的代价进行评估说究竟也是一种算法，算法都是死的，暂且不表，下文简述。而参与的数据集基本信息却是活的，为什么这么说，因为这种数据集都是原创表经过过滤、聚合以后的中间结果，没有规则直接告诉你这个中间结果有多少数据！那中间结果的基本信息怎样评估呢？推导！对，原创表基本信息我们是可以晓得的，如果能够一层一层向下推论，是不是就有可能晓得所求中间结果信息！

　　这里又将任意节点中间结果信息评估分拆为两个子问题：首先评估叶子节点（原创表）的基本信息，其次一层一层往上推论。评估原创表基本信息想想总是有办法的，粗暴点就全表扫描，获取记录条数、最大值、最小值，总之是可以做到的。那基本信息怎样一层一层往上推论呢？规则！比如原创表经过 id = 12这个Filter过滤以后的数据集信息（数据集大小等）就可以经过一定的规则推论下来，不同算子有不同的规则，下文阐述！

　　好吧，上文耗费了大量时间将一个完整的CBO解剖的零零碎碎，变成了一堆规则加原创表的扫描。相信你们都有点懵懵的。莫慌，我们再来理一遍：

　　1. 基于代价优化（CBO）原理是估算所有执行路径的代价，并选购代价最小的执行路径。问题转化为：如何估算一条给定执行路径的代价

　　2. 计算给定路径的执行代价，只须要估算这条路径上每位节点的执行代价，最后相乘即可。问题转化为：如何估算其中任意一个节点的执行代价

　　3. 计算任意节点的执行代价，只须要晓得当前节点算子的代价估算规则以及参与估算的数据集（中间结果）基本信息（数据量大小、数据条数等）。问题转化为：如何估算中间结果的基本信息以及定义算子代价估算规则

　　4. 算子代价估算规则是一种死的规则，可定义。而任意中间结果基本信息须要通过原创表基本信息沿着语法树一层一层往上推论得出。问题转化为：如何估算原创表基本信息以及定义推论规则

　　很显然，上述过程是思维过程，真正工程实践是反着由下往上一步一步执行，最终得到代价最小的执行路径。现在再把它从一个个零件组装上去：

　　1. 首先采集原创表基本信息

　　2. 再定义每种算子的基数评估规则，即一个数据集经过此算子执行以后基本信息变化规则。这两步完成以后就可以推论出整个执行计划树上所有中间结果集的数据基本信息

　　3. 定义每种算子的执行代价，结合中间结果集的基本信息，此时可以得出任意节点的执行代价

　　4. 将给定执行路径上所有算子的代价累加得到整棵语法树的代价

　　5. 计算出所有可能语法树代价，并选出一条代价最小的

　　CBO基本实现思路

　　上文从理论层面剖析了CBO的实现思路，将完整的CBO功能分拆为了多个子功能，接下来谈谈对每一个子功能的实现。

　　第一步：采集参原创表基本信息

　　这个操作是CBO最基础的一项工作，采集的主要信息包括表级别指标和列级别指标，如下所示，estimatedSize和rowCount为表级别信息，basicStats和Histograms为列级别信息，后者细度更细，对优化愈发重要。

　　这里有两个问题值得思索：

　　1. 为什么要采集这些信息？每个对象在优化过程中起到哪些作用？

　　2. 实际工程通常是怎样实现这种数据采集的？

　　为什么要采集这些信息？很显然，estimatedSize和rowCount这两个值是算子代价评估的直观彰显，这两个值越大，给定算子执行代价必然越大，所以这两个值后续会拿来评估实际算子的执行代价。那basicStats和Histograms这俩拿来干啥呢，要不忘初心，之所以采集原创表的这种信息，是为了沿着执行语法树往上一层一层推论出所有中间结果的基本信息，这俩就是来干这个的，至于如何实现的，下一小节会举个事例解释。

　　实际工程怎么实现这种数据采集？一般有两种比较可行的方案：打开所有表扫描一遍，这样最简单，而且统计信息确切，缺点是对于大表来说代价比较大；针对一些大表，扫描一遍代价很大，可以采用取样（sample）的形式统计估算。

　　支持CBO的系统都有命令对原创数据信息进行统计，比如Hive的Analyze命令、Impala的Compute命令、Greenplum的Analyze命令等，但是须要注意那些命令并不是随时都应当执行的，首先在表数据没有大变动的情况下没必要执行，其次在系统查询高发期也不应当执行。这里有个最佳实践：尽可能在业务低峰期对表数据有较大变动的表单独执行统计命令，这句话有三个重点，不知道你看下来没有？

　　第二步：定义核心算子的基数推论规则

　　规则推论意思是说在当前子节点统计信息的基础上，计算父节点相关统计信息的一套推论规则。对于不同算子，推导规则必然不一样，比如fliter、group by、limit等等的评估推论是不同的。这里以filter为例进行讲解。先来瞧瞧这样一个SQL：select * from A , C where A.id = C.c_id and C.c_id > N，经过RBO以后的语法树如下图所示：

　　

　　问题定义为：假如如今早已晓得表C的基本统计信息（estimatedSize、rowCount、basicStats以及histograms），如何推论出经过C.c_id > N过滤后中间结果的基本统计信息。我们来瞧瞧：

　　1. 假设已知C列的最小值c_id.Min、最大值c_id.Max以及总行数c_id.Distinct，同时假定数据分布均匀，如下图所示：

　　

　　2. 现在分别有三种情况须要说明，其一是N大于c_id.Min，其二是N小于c_id.Max，其三是N介于c_id.Min和c_id.Max之间。前两种场景是第三种场景的特殊情况，这里简单的针对第三种场景说明。如下图所示：

　　

　　在C.c_id > N过滤条件下，c_id.Min会减小到N，c_id.Max保持不变。而过滤后总行数c_id.distinct(after filter) ＝ (c_id.Max – N) / (c_id.Max – c_id.Min) * c_id.distinct(before filter)

　　简单吧，但是注意哈，上面估算是在假定数据分布均匀的前提下完成的，而实际场景中数据分布很显然不可能均衡。数据分布一般成机率分布，histograms在这里就要登场了，说白了它就是一个柱状分布图，如下图：

　　

　　柱状图横座标表示列值大小分布，纵座标表示频度。假设N在如图所示位置，那过滤后总行数c_id.distinct(after filter) ＝ height(>N) / height(All) * c_id.distinct(before filter)

　　当然，上述所有估算都只是示意性估算，真实算法会复杂好多。另外，如果你们对group by 、limit等子句的评估规则比较感兴趣的话，可以阅读SparkSQL CBO设计文档，在此不再赘言。至此，通过各类评估规则以及原创表统计信息就可以估算出语法树中所有中间节点的基本统计信息了，这是万里长征的第二步，也是至关重要的一步。接下来继续往前走，看看怎样估算每种核心算子的实际代价。

　　第三步：核心算子实际代价估算

　　打文章一开始就开口闭口代价代价的，可究竟哪些是代价，怎么定义代价？这么说吧，每个系统对代价的定义并不十分一致，有的由于实现的诱因设置的比较简单，有的会比较复杂。这一节主要来简单说说每位节点的执行代价，上文说了，一条执行路径的总代价就是这条路径上所有节点的代价累加之和。

　　通常来讲，节点实际执行代价主要从两个维度来定义：CPU Cost以及IO Cost。为后续讲解便捷起见，需要先行定义一些基本参数：

　　Table Scan算子

　　Scan算子通常坐落语法树的叶子结点，直观上来讲这类算子只有IO Cost，CPU Cost为0。Table Scan Cost = IO Cost = Tr * Tsz * Hr，很简单，Tr * Tsz表示须要scan的数据总大小，再减去Hr就是所需代价。OK，很直观，很简单。

　　Hash Join算子

　　以Broadcast Hash Join为例（如果看官对Broadcast Hash Join工作原理还不了解，可戳这儿），假设大表分布在n个节点上，每个节点的数据条数\平均大小分别为Tr(R1)\Tsz(R1)，Tr(R2)\Tsz(R2), … Tr(Rn)\Tsz(Rn)，小表数据条数为Tr(Rsmall)\Tsz(Rsmall)，那么CPU代价和IO代价分别为：

　　CPU Cost = 小表建立Hash Table代价 ＋ 大表侦测代价 ＝ Tr(Rsmall) * CPUc + (Tr(R1) + Tr(R2) + … + Tr(Rn)) * N * CPUc，此处假定HashTable建立所需CPU资源远远低于两值简单比较代价，为N * CPUc

　　IO Cost = 小表scan代价 ＋ 小表广播代价 ＋ 大表scan代价 ＝ Tr(Rsmall) * Tsz(Rsmall) * Hr + n * Tr(Rsmall) * Tsz(Rsmall) * NEt + (Tr(R1)* Tsz(R1) + … + Tr(Rn) * Tsz(Rn)) * Hr

　　很显然，Hash Join算子相比Table Scan算子来讲稍微复杂了一点，但是无论哪种算子，代价估算都和参与的数据总条数、数据平均大小等诱因直接相关，这也就是为何在之前两个步骤中要不懈余力地估算中间结果相关详尽的真正缘由。可谓是步步为营、环环相扣。这下好了，任意节点的实际代价都能评估下来，那么给定任意执行路径的代价必然也就很简单喽。

　　第四步：选择最优执行路径（代价最小执行路径）

　　这个思路很容易理解的，经过上述三步的努力，可以很容易地估算出任意一条给定路径的代价。那么你只须要找出所有可行的执行路径，一个一个估算，就必然能找到一个代价最小的，也就是最优的执行路径。

　　这条路看起来确实很简单，但实际做上去却并不这么容易，为什么？所有可行的执行路径实在太多，所有路径都估算一遍，黄花菜都凉了。那么有哪些好的解决方案么？当然，其实听到这个标题－选择代价最小执行路径，就应当很容易想到－动态规划，如果你没有想到，那只能说明你没有读过《数学之美》、没刷过LeetCode、没玩过ACM，ACM、LeetCode假如认为很沉闷，那就去瞧瞧《数学之美》，它会告诉你从当前这个你所在的地方驾车去上海，如何使用动态规划选择一条最短的路线。在此不再赘言。

　　至此，笔者粗线条地介绍了当前主流SQL引擎是怎样将CBO如此一个看似深奥的技术一步一步落地的。接下来，笔者将会借用Hive、Impala这两大SQL引擎开启CBO以后的优化疗效使你们对CBO有一个更直观的理解。

　　Hive – CBO优化疗效

　　Hive本身没有去从头实现一个SQL优化器，而是借助于Apache Calcite，Calcite是一个开源的、基于CBO的企业级SQL查询优化框架，目前包括Hive、Phoniex、Kylin以及Flink等项目都使用了Calcite作为其执行优化器，这也挺好理解，执行优化器原本就可以具象成一个系统模块，并没有必要耗费大量时间去重复造轮子。

　　hortonworks以前对Hive的CBO特点做了相关的测试，测试结果觉得CBO起码对查询有三个重要的影响：Join ordering optimization、Bushy join support以及Join simplification，本文只简单介绍一下Join ordering optimization，有兴趣的朋友可以继续阅读这篇文章来更多地了解其他两个重要影响。（下面数据以及*敏*感*词*也来自于该篇文章，特此标明）

　　hortonworks对TPCDS的部份Query进行了研究，发现对于大部分星型\雪花模型，都存在多Join问题，这些Join次序假如组织不好，性能还会太差，如果组织得当，性能还会挺好。比如Query Q3：

　　

select

dt.d_year,

item.i_brand_id brand_id,

item.i_brand brand,

sum(ss_ext_sales_price) sum_agg

from

date_dim dt,

store_sales,

item

where

dt.d_date_sk = store_sales.ss_sold_date_sk

and store_sales.ss_item_sk = item.i_item_sk

and item.i_manufact_id =436

and dt.d_moy =12

groupby dt.d_year , item.i_brand , item.i_brand_id

order by dt.d_year , sum_agg desc , brand_id

limit 10

　　上述Query涉及到3张表，一张事实表store_sales（数据量大）和两张维度表（数据量小），三表之间的关系如下图所示：

　　

　　这里就涉及上文提及的Join次序问题，从原创表来看，date_dim有73049条记录，而item有462000条记录。很显然，如果没有其他暗示的话，Join次序必然是store_sales join date_dim join item。但是，where条件中还带有两个条件，CBO会依照过滤条件对过滤后的数据进行评估，结果如下：

　　

　　Table

　　Cardinality

　　Cardinality after filter

　　Selectivity

　　date_dim

　　73,049

　　6200

　　8.5%

　　item

　　462,000

　　484

　　0.1%

　　根据上表所示，过滤后的数据量item显著比date_dim小的多，剧情反转的有点快。于是乎，经过CBO以后Join次序就弄成了store_sales join item join date_time，为了进一步确认，可以在开启CBO前后分别记录该SQL的执行计划，如下图所示：

　　左图是未开启CBO特点时Q3的执行计划，store_sales先与date_dim进行join，join后的中间结果数据集有140亿条。而再看下图，store_sales先于item进行join，中间结果只有8200w条。很显然，后者执行效率会更高，实践出真知，来瞧瞧二者的实际执行时间：

　　Test

　　Query Response Time(seconds)

　　Intermediate Rows

　　CPU(seconds)

　　Q3 CBO OFF

　　255

　　13,987,506,884

　　51,967

　　Q3 CBO ON

　　142

　　86,217,653

　　35,036

　　上图很明显的看出Q3在CBO的优化下性能将近提高了1倍，与此同时，CPU资源使用率也减少了一半左右。不得不说，TPCDS中有好多相像的Query，有兴趣的朋友可以深入进一步深入了解。

　　Impala – CBO优化疗效

　　和Hive优化的原理相同，也是针对复杂join的执行次序、Join的执行策略选择优化等方面进行的优化，本人使用TPC-DS对Impala在开启CBO特点前后的部份Query进行了性能测试，测试结果如下图所示：

　　

　　CBO总结

　　这篇文章其实很早就开始构思了，前前后后花了将近3个月时间断断续续来写，写了删、删了写，记得第二稿早已写了好多内容，有天一大早睡醒完完整整地看了一遍，发现写的东西并不是自己想要的，准确说，写的缺乏这么一些些条理智，改又不好改，索性就全删了。另一方面，也有由于当前网路上并没有太多关于CBO的完整介绍，倒是找到一些中文资料，但总觉得还是缺少条理性，很难理解。本文第一节重点从思维上带你们认识CBO，第二节更多的从实现的视角一步一步将整个原理粗线条地落地，第三节选购Hive与Impala两款产品对比介绍开启CBO以后的优化疗效，使你们有一个更直观的体味。

　　好了，关于Join这个话题，洋洋洒洒前前后后写了三篇文章，能看到这儿的只能说是真爱！说实话，笔者并没有完整的看过RuntimeFilter的代码实现，也没有系统地学过任何一套CBO的代码实现，所写内容大体来自于三个方面：官方博客文档、分析理解、撸起衣袖实践。所以看官可要批判性地去阅读，有错误的地方在所难免，希望还能多多交流见谅。后期笔者一定会阅读相关的代码实现，有新的发觉再和你们一起分享～

　　参考资料

　　1. Enhancements on Spark SQL optimizer :

　　2. Impala Table and Column Statistics :

　　3. Enhancing Spark SQL Optimizer with Reliable Statistics :

　　4. Cost-based Optimizer framework :

　　5.

　　6.

　　本文系转载，如有侵权，立删

　　原文链接：%EF%BC%8Dcbo/?lovyta=rrfzx3