Hive优化器原理与源码解析系列—统计信息之选择性
背景
Hive基于成本优化器CBO是0.14版本引入的新功能。
Hive优化器是使用Apache Calcite动态数据管理框架实现的，其中包含VolcanoPlanner基于成本优化器（CBO）和HelpPlaner基于规则的启发式优化器（RBO）优化器。根据用户HiveConf配置信息使用不同的优化器。
这里简单讲一下两种优化器特性
基于规则的优化器(RBO，Rule-Based Optimizer)
根据预先准备写的优化规则rule，不考虑数据动态变化，在关系表达式等价转换的前提下，对符合匹配规则条件的关系表达式，替换掉原来的关系表达式，达到优化的目的。
基于代价的优化器(CBO，Cost-Based Optimizer)
根据预先准备写的优化规则rule，在关系表达式等价转换的前提下，对符合匹配规则条件的关系表达式，保留原来的关系表达式并把匹配上新关系表达式加入等价关系表达式集合，根据成本模型和统计信息和算法（Calcite使用的是动态规划算法），从等价关系表达式集合，构建出成本最优执行计划。
VolcanoPlanner基于成本优化器如何从关系表达式等价集合RelSet中，根据成本模型CostModel和统计信息stats，再使用动态规划算法，选出最优成本的执行计划？这是最大的、也是最核心的一部分，其原理及源码解析后续文章会推出，敬请期待。
选择性计算
我们先从成本模型和统计信息入手，这也是理解基于成本优化器很重要的基础准备（看懂这些知识，门槛可能稍高，需要了解一个SQL从词法分析、语法分析、抽象语法树、构建逻辑执行计划、生成物理执行计划及物理执行计划的算法实现等知识，不过没关系，后续都会这些相关的文章来）。CBO是根据成本模型和统计信息，估算一个关系表达式成本高低，选出整体成本最优的执行计划。所以对于基于成本优化器的来讲，成本模型设计的是否合理和完善，统计信息收集是否准确，直接影响优化器生成的执行计划的准确性。
Hive统计源码stats模块有：排序信息收集、NDV（Number of Distinct Value）非重复值个记录数、分布式信息收集、占用内存信息收集、并行度信息收集、记录数信息收集、列大小信息收集、唯一关键列信息收集、通用选择性Selectivity收集、计算谓词Selectivity选择性信息收集。
先介绍成本优化器，常使用选择性和基数开始
基数Cardinality：
基数的官方定义来自数学概念：一个集合中的值的数量。但当应用于数据库时，其含义有点不同：某列唯一键的数量，称为基数，即某列非重复值的数量。如性别列，男女两个值，即此列的基数为2。
在实际应用中，我们通常不会将基数作为数字来讨论。简单地说“高”和“低”基数更为常见。很多不同的值是高基数；很多重复的值是低基数。基数对性能影响很大，因为它影响查询执行计划。优化器将检查列统计数据，并使用它们来计算查询可能匹配的值数量，以及其他内容。根据发现的内容，它可能会使用不同的查询执行计划来尝试获得最佳性能。
选择性Selectivity：
某列基数与总行数的比值再乘以100%，则称为某列选择性。可选择率的取值范围显然是0～1，它的值越小，就表明可选择性越好。当可选择率为1时的可选择性是最差的。CBO就是用可选择率来估算对应结果集的基数Cardinality的。选择性、基数、总记录数之间关系如下：
Cardinality=NUM_ROWS*selectivity
其中，NUM_ROWS表示表的总行数。
Hive统计模块的选择性计算不是根据简单地计算某列的选择Selectivity，而是基于Operator操作符综合来选择性Selectivity的，TableScan（类似From 后跟的数据源扫描）、Join（关联）、Aggregation（汇总操作、如Sum、Count等）、Project（投影，相当于SQL select 后面的字段）、Filter（谓词，相当于Where条件）等等。
Hive主要负责选择性计算的HiveRelMdSelectivity 是继承了Calcite框架中的RelMdSelectivity类。从父类RelMdSelectivity的继承来计算Union、Sort 、Filter、Aggregate、Project、SemiJoin等选择性计算方法，大部分可从RelMetadataQuery对象的getSelectivity()方法中直接获取，这里不做过多详解，可参考Calcite相关API或源码。
接下来我们详解一下这些选择性在源码中如何实现的
1）计算HiveTableScan的选择性Selectivity：
如果谓词Predicate（可理解Where条件）为空，Tablescan会全表返回，则选择性为100%；如果Predicate不为null，则使用FilterSelectivityEstimator.estimateSelectivity(谓词)估算选择性
/*** @param t TableScan操作数
* @param mq RelMetadataQuery访问Hive收集元数据信息，如记录数、非空记录数、记录长度大小等用于计算成本
* @param predicate 行表达式，calcite RexNode 相当于SQL where条件部分
* @return 选择性
*/
public Double getSelectivity(HiveTableScan t, RelMetadataQuery mq, RexNode predicate) {
if (predicate != null) { //如果谓词不为null，则传递谓词进行估算，否则，即tablescan
FilterSelectivityEstimator filterSelEstmator = new FilterSelectivityEstimator(t); //使用FilterSelectivityEstimator来选择性
return filterSelEstmator.estimateSelectivity(predicate);
}
return 1.0; //谓词为null，则选择性100%
}
2）计算Join的选择性Selectivity：
Join分为三种情况：内连接、左右连接、其他（全连接或笛卡尔积）
根据j.getJoinType()返回关联类型分别做如下计算：
INNER JOIN：
返回内连接的选择性computeInnerJoinSelectivity(j, mq, predicate)，关于内连接的选择性计算详细逻辑会下面进行详解。
LEFT或RIGHT JOIN：
通过RelMetadataQuery对象的getRowCount()方法，分别计算左右两表的记录数，再计算两张表记录数的乘积。
Left join 则其选择性为Max（内连接的选择性，左侧表记录数/右侧表记录数*左侧表记录数）两者中取最大值
Right join 则其选择性为Max（内连接的选择性，右侧表记录数/右侧表记录数*左侧表记录数）两者中取最大值
其他（全连接或笛卡尔积）
则返回返回值100%
public Double getSelectivity(Join j, RelMetadataQuery mq, RexNode predicate) {if (j.getJoinType().equals(JoinRelType.INNER)) {//如果是inner join，返回inner join的选择性，相见下面函数
return computeInnerJoinSelectivity(j, mq, predicate);
} else if (j.getJoinType().equals(JoinRelType.LEFT) ||
j.getJoinType().equals(JoinRelType.RIGHT)) {//如是 左连接 或 右连接 ，分别通过mq获取左右两侧的记录数
double left = mq.getRowCount(j.getLeft());
double right = mq.getRowCount(j.getRight());
double product = left * right; //左右两边记录数的积
double innerJoinSelectivity = computeInnerJoinSelectivity(j, mq, predicate); //再计算此Join如果改成Inner join的选择性
if (j.getJoinType().equals(JoinRelType.LEFT)) {
return Math.max(innerJoinSelectivity, left/product); //如果是leftjion 则inner join选择性和1/right记录数 取最大
}
return Math.max(innerJoinSelectivity, right/product);//如果是rightjion 则inner join选择性和1/left记录数 取最大
}
return 1.0;
}
3）计算Inner Join内连接的选择性Selectivity
对于内连接的选择性稍微复杂一些，
首先判断Join是否带有谓词即Where条件，则使用FilterSelectivityEstimator.estimateSelectivity(谓词)估算选择性。
否则就开始仅带有On条件的Inner join的选择性估算。计算inner join的选择性大致步骤如下：
a 使用JoinPredicateInfo.getProjsFromLeftPartOfJoinKeysInChildSchema()获取左侧投影列集合，对左侧投影的index指向的列进行遍历，获取其NDV（number of distinct value），构建左侧Project投影列与其NDV的映射关系。
b 同样的方式，对右侧进行计算，构建右侧Project投影列与其NDV的映射关系。最终构建成一个左右两侧Project投影列与其NDV的映射关系map。
c 获取等值关联的谓词信息列表List<JoinLeafPredicateInfo>，如果此列表元素个数大于0，则使用exponentialBackoff(peLst, colStatMap)计算ndvCrossProduct初始值。
如果join类型为semiJoin则左侧表记录数与初始化ndvCrossProduct两者中取最小值
ndvCrossProduct = Math.min(mq.getRowCount(j.getLeft()),ndvCrossProduct);如果join类型为HiveJoin则左侧表记录数*右侧表记录数与初始化ndvCrossProduct两者中取最小值
ndvCrossProduct = Math.min(mq.getRowCount(j.getLeft()) * mq.getRowCount(j.getRight()), ndvCrossProduct);d 返回1/ndvCrossProduct 作为选择性
private Double computeInnerJoinSelectivity(Join j, RelMetadataQuery mq, RexNode predicate) {Pair<Boolean, RexNode> predInfo =
getCombinedPredicateForJoin(j, predicate); //返回joinConditon和谓词是否相等的boolean标志及谓词并集
if (!predInfo.getKey()) { //说明含有谓词，并与joinCondition是不相等的，则FilterSelectivityEstimator估算join的谓词选择性
return
new FilterSelectivityEstimator(j).
estimateSelectivity(predInfo.getValue());
}
/**
* 以下是join，仅有joinCondition而没有谓词即where条件的情况分析：
*/
RexNode combinedPredicate = predInfo.getValue(); //获取联合的谓词
JoinPredicateInfo jpi;
try {
jpi = JoinPredicateInfo.constructJoinPredicateInfo(j,
combinedPredicate); //创建JoinPredicateInfo对象
} catch (CalciteSemanticException e) {
throw new RuntimeException(e);
}
ImmutableMap.Builder<Integer, Double> colStatMapBuilder = ImmutableMap
.builder();
ImmutableMap<Integer, Double> colStatMap;
int rightOffSet = j.getLeft().getRowType().getFieldCount(); //获取左侧字段个数，索引+1是右侧索引的起点
// 1. Update Col Stats Map with col stats for columns from left side of
// Join which are part of join keys
//使用stats模块功能，更新Join左侧关联字段join keys这些列统计信息映射
//
for (Integer ljk : jpi.getProjsFromLeftPartOfJoinKeysInChildSchema()) {//从JoinLeafPredicateInfo对象其Join key在Join Schema中，获取左侧投影列集合·
colStatMapBuilder.put(ljk,
HiveRelMdDistinctRowCount.getDistinctRowCount(j.getLeft(), mq, ljk));//取得左侧投影列的，基数，并添加到投影列索引与基数的映射关系
}
// 2. Update Col Stats Map with col stats for columns from right side of
// Join which are part of join keys
//使用stats模块功能，更新Join右侧关联字段join keys这些列统计信息映射
for (Integer rjk : jpi.getProjsFromRightPartOfJoinKeysInChildSchema()) {//取得右侧投影列的，基数，并添加到投影列索引与基数的映射关系
colStatMapBuilder.put(rjk + rightOffSet, // 这里在左侧投影列索引的基础上
HiveRelMdDistinctRowCount.getDistinctRowCount(j.getRight(), mq, rjk));
}
colStatMap = colStatMapBuilder.build();
// 3. Walk through the Join Condition Building NDV for selectivity
// NDV of the join can not exceed the cardinality of cross join.
//遍历Join Condition关联条件（考虑的是没where条件的模块），来构建非重复记录数的选择性。join的非重复记录数不能超过cross join的基数
List<JoinLeafPredicateInfo> peLst = jpi.getEquiJoinPredicateElements();
int noOfPE = peLst.size();
double ndvCrossProduct = 1;
if (noOfPE > 0) {
ndvCrossProduct = exponentialBackoff(peLst, colStatMap); //使用指数后退来计算ndvCrossProduct
if (j instanceof SemiJoin) { //如果join是SemiJoin类，ndvCrossProduct取值为 ndvCrossProduct 和 join左侧记录数取最小值
ndvCrossProduct = Math.min(mq.getRowCount(j.getLeft()),
ndvCrossProduct);
}else if (j instanceof HiveJoin){ //如果join是Join类，ndvCrossProduct取值为 ndvCrossProduct 和 join左侧记录数*join右侧记录数取最小值
ndvCrossProduct = Math.min(mq.getRowCount(j.getLeft())
* mq.getRowCount(j.getRight()), ndvCrossProduct);
} else {
throw new RuntimeException("Unexpected Join type: " + j.getClass().getName());
}
}
// 4. Join Selectivity = 1/NDV
return (1 / ndvCrossProduct);
}
4）计算join谓词信息列表list的综合选择性Selectivity
计算List<JoinLeafPredicateInfo>集合中join两侧中最大的基数集合，然后对基数集合倒排序，以指数后退的形式，综合计算cross product ndv结果形式如下：ndvCrossProduct = ndv(pe0) * ndv(pe1) ^(1/2) * ndv(pe2) ^(1/4) * ndv(pe3) ^(1/8) ...
protected double exponentialBackoff(List<JoinLeafPredicateInfo> peLst,ImmutableMap<Integer, Double> colStatMap) {
int noOfPE = peLst.size();
List<Double> ndvs = new ArrayList<Double>(noOfPE);
for (int i = 0; i < noOfPE; i++) {
ndvs.add(getMaxNDVForJoinSelectivity(peLst.get(i), colStatMap));
}
Collections.sort(ndvs);
Collections.reverse(ndvs);//倒排序
double ndvCrossProduct = 1.0;
for (int i = 0; i < ndvs.size(); i++) {
double n = Math.pow(ndvs.get(i), Math.pow(1 / 2.0, i));
ndvCrossProduct *= n;
}
return ndvCrossProduct;
}
5）从给定投影Project集合和投影列序数与基数（非重复列记录数）映射关系Map，选择最大NDV（非重复值个数量number of distinct value）
/*** 从投影列集合中选列最大基数
*
* @param colStatMap 投影列序数，基数（非重复列记录数）映射关系
* @param projectionSet 投影列序数集合
* @param defaultMaxNDV 默认最大基数
* @return 返回投影列中最大的基数
*/
private static Double getMaxNDVFromProjections(Map<Integer, Double> colStatMap,
Set<Integer> projectionSet, Double defaultMaxNDV) {
Double colNDV = null;
Double maxNDVSoFar = defaultMaxNDV;
for (Integer projIndx : projectionSet) { //遍历投影列集合，比较投影列序数，基数（非重复列记录数）映射关系，最大基数并返回
colNDV = colStatMap.get(projIndx);
if (colNDV > maxNDVSoFar)
maxNDVSoFar = colNDV;//取最大NDV
}
return maxNDVSoFar;
}
}
6）计算join谓词信息对象中，join左右两侧中最大NDV
private static Double getMaxNDVForJoinSelectivity(JoinLeafPredicateInfo jlpi,ImmutableMap<Integer, Double> colStatMap) {
Double maxNDVSoFar = 1.0; //初始最大NDV为1
maxNDVSoFar = getMaxNDVFromProjections(colStatMap,
jlpi.getProjsFromLeftPartOfJoinKeysInJoinSchema(), maxNDVSoFar);//取得左侧投影列集合中最大NDV
maxNDVSoFar = getMaxNDVFromProjections(colStatMap,
jlpi.getProjsFromRightPartOfJoinKeysInJoinSchema(), maxNDVSoFar);//使用左侧投影列集合中最大NDV作为参考，再选取左右两侧中最大的NDV
return maxNDVSoFar;
}
7）根据Join谓词信息对象列表和投影列集合对应的基数Map计算出更平滑的选择性
cross product是通过所有连接谓词中最大NDV乘以其余连接谓词降级NDV。NDV是使用log函数来降级的。ndvCrossProduct圈定了Join的范围，cross product确保NDV不会超过最坏情况下的join
计算方法大致和exponentialBackoff思路相同，只是计算方式换了log函数对选择性结果进行平滑
大致步骤为：
a 先取列表中第一个JoinLeafPredicateInfo元素，并计算左右两侧中最大NDV作为比较默认值，如果List<JoinLeafPredicateInfo>大小大于1，则将比较默认值最大当前最大NDV带入进行下面计算
b 在list集合大小大于1的情况下，遍历开始
c ndvCrossProduct = (ndvCrossProduct / ndvToBeSmoothed) * tmpNDV;特别强调的是ndvToBeSmoothed平滑ndv大于3，则开始使用Math.log进行平滑
protected double logSmoothing(List<JoinLeafPredicateInfo> peLst, ImmutableMap<Integer, Double> colStatMap) {int noOfPE = peLst.size();
double ndvCrossProduct = getMaxNDVForJoinSelectivity(peLst.get(0), colStatMap);
if (noOfPE > 1) {
double maxNDVSoFar = ndvCrossProduct;
double ndvToBeSmoothed;
double tmpNDV;
for (int i = 1; i < noOfPE; i++) {
tmpNDV = getMaxNDVForJoinSelectivity(peLst.get(i), colStatMap);
if (tmpNDV > maxNDVSoFar) {
ndvToBeSmoothed = maxNDVSoFar;
maxNDVSoFar = tmpNDV;
ndvCrossProduct = (ndvCrossProduct / ndvToBeSmoothed) * tmpNDV;
} else {
ndvToBeSmoothed = tmpNDV;
}
// TODO: revisit the fence
if (ndvToBeSmoothed > 3)
ndvCrossProduct *= Math.log(ndvToBeSmoothed);//使用log函数进行平滑计算
else
ndvCrossProduct *= ndvToBeSmoothed;
}
}
return ndvCrossProduct;
}
总结
在开头我们就介绍了选择性和基数的概念，这些都是理论概念，在实际代码实现往往又是复杂而多样的。上述选择性Selectivity就是基于抽象语法树中Operator操作算子的计算。
上述是选择性计算方法或方式的源码讲解，由于笔者知识及水平有限,因此文中错漏之处在所难免,恳请各位老师、专家不吝赐教
后续文章会推出Hive优化器统计stats模块的抽象语法树中各种操作符operators内存使用