Hive优化器原理与源码解析系列--统计信息中间结果大小计算

目录

• 背景

• 中间结果大小计算

• Calcite RelMdRowCount基于Operator记录数估算

• HiveRelMdRowCount基于Operator记录数估算

• 总结

背景

之前文章有写过关于基于Operator操作符Selectivity选择率和Predicate谓词的Selectivity选择率的讲解。这篇文章来讲一下基于每个Operator（TableScan、Project、Join、Union、Sort、Aggregate等等）返回记录数RowCount，即中间结果大小。Hive在估算每个Operator的返回结果RowCount，即中间结果大小，有的是使用元数据对象来进行估算的RowCount；有的使用RelNode自身实现方法估算的；有的是总行数乘以其选择率估算的等多种方法实现。

一个Operator返回记录数RowCount，即中间结果的大小直接影响到CostModel成本的大小（返回的RowCount是成本模型Cost Model的记录数、IO、CPU元素之一）。常见优化规则或SQL重写优化像减少中间结果规则“谓词下推”就是典型从数据源头减少中间结果记录数；等值判断的笛卡尔积转换为等值连接也是减少中间返回结果的优化。

举例说明：

    SELECT 

        T1.id, 

        T2.id  

    FROM T1,T2 

    WHERE T1.id = T2.id

两张表T1，T2先进行笛卡尔积后，返回T1 * T2 记录数乘积的返回结果，在进行笛卡尔积时，导致中间结果变大，再进行谓词条件判断。

等价变化后转换为INNER JOIN：

    SELECT 

        T1.id,

         T2.id  

    FROM T1 

    INNER JOIN T2  

    ON T1.id = T2.id

两张表T1，T2先进行内连接等值判断后，就直接返回结果，这种不改变输入和输出结果的等价交换实现中间结果相比较于笛卡尔积来说，会小很多。

基于成本优化器CBO会从RelNode的等价集合中，在通过动态规划算法选择整体成本最优的执行计划。在整个bestPlan最优执行计划构建过程中，一般会倾向于选择中间结果更小的RelNode。

Hive自身实现的优化规则约40条规则rules，这类优化规则后续，会在可插拔式的规则pluggable rules专题讲解，

这篇文章会用到总记录数RowCount乘以选择率Selectivity等于返回中间结果估算，为了方便讲述。这里还是先简单提一下Cardinality基数和Selectivity选择率概念：

• 基数：某列唯一键的数量，称为基数，即某列非重复值的数量。

• 选择率：某列基数与总行数的比值再乘以100%，则称为某列选择率

      当有多列组合的记录时，就把基于某列的基数和选择率概念扩展到元组或整个记录行的基数和选择率概念，分别非重复记录数（元组基数）和非重复记录与总记录的比率（元组选择率，以下提到的基数和选择率都是基于记录的）。

使用Selectivity选择率来估算对应结果集的Cardinality基数的，Selectivity选择率和Cardinality之间的关系如下：

Cardinality=NUM_ROWS*Selectivity

    其中，NUM_ROWS表示表的总行数。同时返回的RowCount也是成本模型Cost Model的记录数、IO、CPU元素之一。

中间结果RowCount大小估算

        Hive中计算中间返回结果的功能，有stats统计模块的HiveRelMdRowCount实现的，其继承了Calcite的RelMdRowCount类

讲解也分为两部份，首先一部分是从父类RelMdRowCount继承的实现；然后另一部分是HiveRelMdRowCount计算逻辑的实现。

RelMdRowCount内返回中间结果记录数的计算逻辑都是基础，但常用的Operator Tree操作树结点的RowCount或之间简单运算返回的记录数，这部分主要有Union、Project、Sort、Filter、Join、SemiJoin、Aggregate等Operator操作符返回记录数的估算，还有一些常量、计算、交、差等等估算。

HiveRelMdRowCount实现对Join、SemiJoin、Sort操作符进行逻辑覆盖重写，使这些Operator返回结果计算的更精确了，如Join的实现，计算Join的关系表达式对Join两侧记录数及记录是否重复进行分析返回PKFKRelationInfo对象，此对象主要功能确定Join两侧哪一侧PK side和哪一侧为FK side，选择率和选择率缩放因子，两侧各自记录数和非重复记录数NDV等。

这样做好处：

        两个RelNode进行Join时，Join返回记录数多少由的主键侧记录数选择率和外键侧非重复值共同决定的。通过对Join两侧的RelNode进行分析，确定哪一侧为非重复PK side，哪一侧为含有重复值FK side就显得异常重要了。

Join的RowCount = Math.min(1.0, 主键侧选择率 * 主键侧ndv缩放因子) * 非重复外键侧记录数

详解说明：

T1 join T2 on T1.x = T2.y

对于T1，在T1.X=T2.Y上连接T2。如果我们确定“Y”是T2的键，那么我们可以 将Join基数推断为：行数（T1）* 选择性（T2） 有点就像一个SemiJoin，其中T1（事实侧/FK侧）被一个基于维度表/PK端的选择性Selectivity因子过滤。 

    1.如果T1.X和T2.Y都是键，则使用较大的键作为PK侧。 

    2.在outer Join的情况下：

a）FK端应为保留NULL的端。将这种启发式方法应用于Dim 表 left join事实表或fact表 right join dim表 是没有意义的。也就是说对outer join外连接使用这种方法估算意义不大。

b）应用于Fact事实表上的选择率因子Selectivity应是1.0

• RelMdRowCount实现方法解析

1）计算Union的RowCount

        遍历Union的输入的RelNodes，通过元数据RelMetadataQuery对象获取各自的返回RowCount，然后进行累加，

如：

    select * from tab1

    Union

    select * from tab2

    Union

    select * from tab3

   Union的RowCount = tab1的记录数 + tab2的记录数 + tab3的记录数

public Double getRowCount(Union rel, RelMetadataQuery mq) {
   double rowCount = 0.0;
   for (RelNode input : rel.getInputs()) {
       Double partialRowCount = mq.getRowCount(input);
       if (partialRowCount == null) {
           return null;
      }
       rowCount += partialRowCount;
  }
   return rowCount;
}

2) 计算Project的RowCount

Project投影，类似指定需要返回的字段列表组成记录，其返回记录数大小，没有太多其他逻辑，直接通过元数据对象RelMetadataQuery来获取RowCount。

public Double getRowCount(Project rel, RelMetadataQuery mq) {
   return mq.getRowCount(rel.getInput());
}

3）计算Sort的RowCount

在讲解之前，我们先实现HiveSort的两个属性

• offset    在返回记录数前，丢的记录数偏移量 

• fetch  指定返回的记录数

 举例说明：

 select * from tab1 sort by id limit 100;

 总记录数=1000 ，那么offset = 总记录数 - fetch = 1000 - 100 = 900 

    结果：

      offset = 900      

      fetch = 100

如果丢的记录数偏移量offset不为null，则返回记录数 = 总记录数 - offset

如果fetch不为null并小于总记录数，则返回fetch指定的记录数，min（指定的记录数，总记录数）两者选最小。

public Double getRowCount(Sort rel, RelMetadataQuery mq) {
   Double rowCount = mq.getRowCount(rel.getInput()); //使用元数据获取记录数
   if (rowCount == null) {
       return null;
  }
   final int offset = rel.offset == null ? 0 : RexLiteral.intValue(rel.offset); //取当输入参数RelNode的offset，如果为null，默认为0，否则取自身
   rowCount = Math.max(rowCount - offset, 0D); //返回记录数大于等于0，并返回记录数 = 总记录数 - offset舍弃的记录数

   if (rel.fetch != null) { // 如果fetch不为null，即limit限制的返回的记录行数，如果limit小于总记录数，则返回返回limit，否则返回自身
       final int limit = RexLiteral.intValue(rel.fetch);
       if (limit < rowCount) {
           return (double) limit;
      }
  }
   return rowCount;
}

4）计算Join的RowCount

        使用了RelMdUtil.getJoinRowCount，传递了Join表达式和join条件及RelMetadataQuery对象进行估算的。

计算逻辑如下：join两侧各自记录数的积 * join的选择率

Join返回记录数  =（left侧记录数 * right侧记录数） * Join的Selectivity选择率 ，

public Double getRowCount(Join rel, RelMetadataQuery mq) {
   return RelMdUtil.getJoinRowCount(mq, rel, rel.getCondition());
}

5）计算SemiJoin的RowCount

Semijoin和Leftjoin是有区别的：

• Semijoin：Semijoin相当于in，即会过滤掉左表中关联不到右表的行，右表中有多行能join到时显示一行，并且只输出左表的字段、不输出右表的字段；

• Leftjoin：不会过滤掉左表中的行，右表中有多行能join到时显示多行，并且能够同时输出左表和右表中的字段。

计算computeSemiJoinSelectivity的选择率，然后用选择率创建一个常量表达式RexNode作为谓词，使用左RelNode关系表达式和Predicte求出选择率。有因为SemiJoin都是左侧记录数计算计算的

所以，返回记录数 = 左侧的选择率selectivity * 左侧的总记录数

public Double getRowCount(SemiJoin rel, RelMetadataQuery mq) {
   // create a RexNode representing the selectivity of the
   // semijoin filter and pass it to getSelectivity
   RexNode semiJoinSelectivity =
           RelMdUtil.makeSemiJoinSelectivityRexNode(mq, rel);//获取代表semijoin选择率的谓词，然后传递给getSelectivity

   return NumberUtil.multiply(
           mq.getSelectivity(rel.getLeft(), semiJoinSelectivity),
           mq.getRowCount(rel.getLeft()));
}

6）计算 Aggregate的RowCount

首先求GroupSet获取group by 列，其次求group by 列的基数（多列组合成非重复记录数），如果其基数不为null，

如果非重复记录为null，则Aggregate的基数 = Aggregate的记录数 / 10，否则Aggregate的RowCount = Aggregate的基数 * GroupSet集合的大小

public Double getRowCount(Aggregate rel, RelMetadataQuery mq) {
   ImmutableBitSet groupKey = rel.getGroupSet(); // .range(rel.getGroupCount());

   // rowCount is the cardinality of the group by columns
   //rowCount是group by列的基数
   //基数的概念是基于列的,可以是多列组合。
   Double distinctRowCount =
           mq.getDistinctRowCount(rel.getInput(), groupKey, null);//多列组成的非重复记录数
   if (distinctRowCount == null) {
       distinctRowCount = mq.getRowCount(rel.getInput()) / 10;
  }
   // Grouping sets multiply
   distinctRowCount *= rel.getGroupSets().size();
   return distinctRowCount;
}

7）计算Intersect的RowCount

求交集Intersect的记录数，在组成交集的子集中，求最小记录数返回。同样Minus求差集也是同样的逻辑，不赘述了。

public Double getRowCount(Intersect rel, RelMetadataQuery mq) {
   Double rowCount = null;
   for (RelNode input : rel.getInputs()) {//遍历RelNode输入，求最小的记录数
       Double partialRowCount = mq.getRowCount(input);
       if (rowCount == null
               || partialRowCount != null && partialRowCount < rowCount) {
           rowCount = partialRowCount;//选子集的最小
      }
  }
   return rowCount;
}

• HiveRelMdRowCount实现方法解析

1） 计算Join的RowCount

Hive对Calcite中RelMdRowCount父类的获取Join的记录数方法进行重写。

PKFKRelationInfo 为Join两侧输入RelNode，确定主键外键对应关系，里面包含了两侧记录数和非重复记录数（NDV）选择率Selectivity和非重复记录数放缩因子ndvScalingFactor。

首先，获取Join的PKFKRelationInfo对象，如果pkfk对象为null，则从RelMetadataQuery对象获取统计信息Join的总记录数作为返回值。其次，如果pkfk对象非null，从PKFKRelationInfo对象中获取pkInfo主键侧选择率乘以pkInfo主键侧ndv缩放因子作为选择率（取值范围[0-1]）。

Join的RowCount = Math.min(1.0, pkInfo主键侧选择率 * pkInfo主键侧ndv缩放因子) * fkInfo外键侧记录数

public Double getRowCount(Join join, RelMetadataQuery mq) {
 PKFKRelationInfo pkfk = analyzeJoinForPKFK(join, mq);//分析一个join左右两侧PK和FK
 if (pkfk != null) {

   double selectivity = (pkfk.pkInfo.selectivity * pkfk.ndvScalingFactor); //获取命中率

   selectivity = Math.min(1.0, selectivity); //命中率小于1
   if (LOG.isDebugEnabled()) {
     LOG.debug("Identified Primary - Foreign Key relation: {} {}",RelOptUtil.toString(join), pkfk);
  }
   return pkfk.fkInfo.rowCount * selectivity; //返回命中率 乘以 记录数
}
 return join.getRows();
}

2）计算SemiJoin的RowCount

实现逻辑和Join的逻辑大致相同。

唯一区别：

        在于pkfk对象为null时，semiJoin的实现逻辑使用父类的方法getRowCount。计算computeSemiJoinSelectivity的选择率，然后用选择率创建一个常量表达式RexNode作为谓词，使用左RelNode关系表达式和Predicte求出选择率。有因为SemiJoin都是左侧记录数计算计算的。返回记录数 = 左侧的选择率selectivity * 左侧的总记录数

public Double getRowCount(SemiJoin rel, RelMetadataQuery mq) {
 PKFKRelationInfo pkfk = analyzeJoinForPKFK(rel, mq);
 if (pkfk != null) {
   double selectivity = (pkfk.pkInfo.selectivity * pkfk.ndvScalingFactor);
   selectivity = Math.min(1.0, selectivity);
   if (LOG.isDebugEnabled()) {
     LOG.debug("Identified Primary - Foreign Key relation: {} {}", RelOptUtil.toString(rel), pkfk);
  }
   return pkfk.fkInfo.rowCount * selectivity;
}
 return super.getRowCount(rel, mq);
}

3）计算Sort的RowCount

对父类方法的覆盖。offset非空的情况下，Sort的RowCount = min（总rowCount，offset + limit），否则用总记录数作为返回值。

public Double getRowCount(Sort rel, RelMetadataQuery mq) {
 final Double rowCount = mq.getRowCount(rel.getInput());
 if (rowCount != null && rel.fetch != null) {
   final int offset = rel.offset == null ? 0 : RexLiteral.intValue(rel.offset);
   final int limit = RexLiteral.intValue(rel.fetch);
   final Double offsetLimit = new Double(offset + limit);
   // offsetLimit is smaller than rowCount of the input operator
   // thus, we return the offsetLimit
   if (offsetLimit < rowCount) {
     return offsetLimit;
  }
}
 return rowCount;
}

总结

        Hive继承了Calcite中RelMdRowCount类，HiveRelMdRowCount实现对Join、SemiJoin、Sort操作符进行逻辑覆盖重写，使这些Operator返回结果计算的更精确了，如Join的实现，计算Join的关系表达式对Join两侧记录数及记录是否重复进行分析返回PKFKRelationInfo对象，此对象主要功能确定Join两侧哪一侧PK side和哪一侧为FK side，选择率和选择率缩放因子，两侧各自记录数和非重复记录数NDV等。更精确的中间结果的估算，更有利于CBO优化器构建最优的执行计划。

        由于笔者知识及水平有限,因此文中错漏之处在所难免,恳请各位老师、专家不吝赐教。

往期文章：