更新时间:2023-11-07 GMT+08:00

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所示。

表1 数据过滤

表名

原始数据条数

过滤后数据条数

选择率

date_dim

73000

6200

8.5%

item

18000

19

0.1%

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

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

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

图3 未开启CBO

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

图4 开启CBO

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