Hive CBO原理介绍

Hive CBO原理介绍

CBO，全称是Cost Based Optimization，即基于代价的优化器。

其优化目标是：

在编译阶段，根据查询语句中涉及到的表和查询条件，计算出产生中间结果少的高效join顺序，从而减少查询时间和资源消耗。

Hive中实现CBO的总体过程如下：

Hive使用开源组件Apache Calcite实现CBO。首先SQL语句转化成Hive的AST，然后转成Calcite可以识别的RelNodes。Calcite将RelNode中的Join顺序调整后，再由Hive将RelNode转成AST，继续Hive的逻辑优化和物理优化过程。流程图如图1所示：

图1 实现流程图

Calcite调整Join顺序的具体过程如下：

1. 针对所有参与Join的表，依次选取一个表作为第一张表。
2. 依据选取的第一张表，根据代价选择第二张表，第三张表。由此可以得到多个不同的执行计划。
3. 计算出代价最小的一个计划，作为最终的顺序优化结果。

代价的具体计算方法：

当前版本，代价的衡量基于Join出来的数据条数：Join出来的条数越少，代价越小。Join条数的多少，取决于参与Join的表的选择率。表的数据条数，取自表级别的统计信息。

过滤条件过滤后的条数，由列级别的统计信息，max，min，以及NDV（Number of Distinct Values）来估算出来。

例如存在一张表table_a，其统计信息如下：数据总条数1000000，NDV 50，查询条件如下：

Select * from table_a where colum_a='value1';

则估算查询的最终条数为1000000 * 1/50 = 20000条，选择率为2%。

以下以TPC-DS Q3为例来介绍CBO是如何调整Join顺序的。

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 
group by dt.d_year , item.i_brand , item.i_brand_id 
order by dt.d_year , sum_agg desc , brand_id 
limit 10;

语句解释：这个语句由三张表来做Inner join，其中store_sales是事实表，有约2900000000条数据，date_dim是维度表，有约73000条数据，item是维度表，有约18000条数据。每一个表上都有过滤条件，其Join关系如所图2示：

图2 Join关系

CBO应该先选择能起到更好过滤效果的表来Join。

通过分析min，max，NDV，以及数据条数。CBO估算出不同维度表的选择率，详情如表1所示。

上述表格获取到原始表的数据条数，估算出过滤后的数据条数后，计算出选择率=过滤后条数/原始条数。

从上表可以看出，item表具有较好的过滤效果，因此CBO将item表的Join顺序提前。

CBO未开启时的Join示意图如图3所示：

图3 未开启CBO

CBO开启后的Join示意图如图4所示：

图4 开启CBO

可以看出，优化后中间结果由495000000条减少到了2900000条，执行时间也大幅减少。