目录
背景
优化规则HivePreFilteringRule
- matches方法逻辑详解
- onMatch方法逻辑详解
总结
背景
这篇文章来讲Hive优化规则HivePreFilteringRule，称为前置过滤器优化规则或谓词下推优化规则。其主要功能是通过哪些谓词下推到离数据源最近的位置，即提前过滤记录数，减少不必要的数据量IO。大致优化过程，是通过把谓词集合从析取范式(DNF) 和合取范式(CNF)根据需要可相互转换，再确定谓词表达式或函数的确定性或非确定性以及是否可下推的优化。
那么何为合取范式(CNF)和析取范式(DNF)，补充一点相关知识。
合取范式定义：
一个命题公式称为合取范式，当且仅当它具有型式:
称为子式，它们都是命题 变元或其否定组成的析取式[10]。
例如
是一个合取范式。
析取范式定义：
一个命题公式称为析取范式，当且仅当它具有型式:
称为子式，它们都是命题 变元或其否定组成的合取式[10]。
例如
是一个析取范式。
任何一个合取范式都可以通过演算转化为一个析取范 式。
例如:
总之，合取范式(CNF)为AND连接谓词表达式，析取范式(DNF)为OR连接的谓词表达式，并且OR连接谓词表达式和AND连接的表达式可相互转换。合取范式(CNF)即AND连接的谓词表达式，拆分为各个谓词表达式元素集合提取析取范式(DNF)中公共谓词表达式因子。从谓词表达式元素集合在分类为确定性、非确定的和可下推的谓词表达式集合，把可下推谓词进行下推到离数据源头最近的地方，提前减少不必要的数据量。这些都是此HivePreFilteringRule前置过滤器要做的事情。
优化规则HivePreFilteringRule
1）matches方法逻辑详解
matches方法返回此规则Rule是否可能与给定的操作数operands匹配，但是此方法的任何实现都可以给出误报，也就是说虽然规则与操作数匹配，但随后具OnMatch（ReloptRuleCall）而不生成任何后续任务。
判断由RelOptCall调用的优化规则Rule是否与输入参数RelNode关系表达式匹配，即此优化规则Rule能否应用到一个RelNode关系表达式树上。
满足此优化规则条件至少有两条如下：
- 必须形如：Filter - TableScan操作符树
- 此优化规则没有被访问优化过
@Override
public boolean matches(RelOptRuleCall call) {
final Filter filter = call.rel(0);
final RelNode filterChild = call.rel(1);
if (filterChild instanceof TableScan) {//如果Filter子输入不是Tablescan则推出优化
return false;
}
HiveRulesRegistry registry = call.getPlanner().getContext().unwrap(HiveRulesRegistry.class);
//如果操作符 已经被rule访问了，我们就不需要在应用优化
if (registry != null && registry.getVisited(this).contains(filter)) {
return false;
}
return true;
}2）onMatch方法逻辑详解
接收有关一条规则匹配的通知。同时此方法被调用，call.rels保存了与规则Rule的操作数Operands匹配上的关系表达式RelNode集合；call.rels[0]是根表达式。通常一条规则Rule会检查这些节点是否有效匹配，创建一个新表达式RelNode（等价的）然后调用RelOptRuleCall.transformTo(org.apache.calcite.rel.RelNode, java.util.Map<org.apache.calcite.rel.RelNode, org.apache.calcite.rel.RelNode>)注册表达式。而RelOptRuleCall用一系列RelNode关系表达式集合作为参数，对RelOptRule优化规则的调用。
首先，call.rel(0)获取Filter过滤器，也是RelNode关系表达式树的根。
call.getPlanner().getContext().unwrap方法是为库用户提供一种在计划程序会话中，存储数据并在规则中访问数据的方法框架可以实现自己的上下文实现，并将其作为FrameworkConfig的一部分传递。只需实现Wrapper.unwrap（java.lang.Class<C>）方法即可返回您希望提供的任何子对象。这里存储在会话中的会话是HiveRulesRegistry对象。其存储了当前优化规则Rule与访问RelNode映射关系，以免重复访问或变换。
HiveRulesRegistry是两种关系集合的封装：1、当前rule规则与已访问RelNode关系节点的map映射2、RelNode与所属关系相关表达式（字符串表示）Set集合registry.registerVisited(this, filter)把当前规则即HivePreFilteringRule访问Filter对象访问记录存储成映射关系。通过从DNF表达式（析取范式 OR）中提取公共元素来重新编译过滤器。
代码语言：javascript复制final Filter filter = call.rel(0); //先取第一个操作符
//获取当前库用户会话的HiveRulesRegistry对象
HiveRulesRegistry registry = call.getPlanner().getContext().unwrap(HiveRulesRegistry.class);
if (registry != null) {
registry.registerVisited(this, filter); //把当前rule与relnode的map，
}
//获取行表达式的RexNode构建器
final RexBuilder rexBuilder = filter.getCluster().getRexBuilder();
RexNode topFilterCondition = RexUtil.pullFactors(rexBuilder, filter.getCondition());RexUtil.pullFactors把Ors表达式中相同的因子上拉， 并创建一个等价的RexNode行表达式topFilterCondition。
一个字段有多个值也只有Or连接表达式中出现，一个字段有多个值的谓词判断在And连接是错的。所以才会从or连接中提取公共元素，上拉之后，就变成了AND连接,如:
- （a=1 and b=2）or (a=1 and b= 3) -> a=1 and ( b=2 or b= 3) 能提取出公共因子的情况，变成AND连接
- （a=2 and b=2）or (a=1 and b= 3) -> a=1 and ( b=2 or b= 3) 不能提取出公共因子的情况，还是OR连接
再分别创建可下推的谓词、确定性和非确定性RexNode行表达式集合。一个表达式确定性与非确定性的区别是给定函数同一个确定值，是否永远返回同一个确定值。刚好相反的是非确定性函数，如随机函数Randow()每次返回的值都不确定。
代码语言：javascript复制//我们提取可能被下推的候选行表达式RexNode
List<RexNode> operandsToPushDown = new ArrayList<>(); //可下推的rexnode
List<RexNode> deterministicExprs = new ArrayList<>(); //确定性表达式rexnode
List<RexNode> nonDeterministicExprs = new ArrayList<>(); //非确定性表达式rexnode如果提取完公共元素的RexNode是AND组成，则用RexUtil.flattenAnd把系列AND节点，转换为一个List，null节点作为常量True，提取共同的可以下推谓词表达式。
遍历由上述AND节点，组成的List，步骤：1、如果AND节点内再含有OR表达式，再使用extractCommonOperands对OR表达式提供出公共因子，类似where条件多个or的表达式内公共的限制条件2、对上述1，OR表达式内含有的公共因子的列表进行遍历3、并把每个公共因子的描述信息Digest和因子RexNode添加到可能需要下推的集合中4、如果AND节点的行表达式RexNode是确定的RexNode，则把此RexNode添加到确定的行表达式集合，否则添加到非确定的行表达式集合
代码语言：javascript复制switch (topFilterCondition.getKind()) {//Returns the kind of node this is.
case AND: //如果公共元素是and组成
//把一系列AND节点，转换为一个List，null节点作为常量True */
ImmutableList<RexNode> operands = RexUtil.flattenAnd(((RexCall) topFilterCondition)
.getOperands());
//存放进行下推操作数的描述的集合
Set<String> operandsToPushDownDigest = new HashSet<String>();
List<RexNode> extractedCommonOperands = null; //抽取出公共操作因子集合
for (RexNode operand : operands) {// 遍历and的 RexNode
if (operand.getKind() == SqlKind.OR) {//如果有and内，再含or表达式
extractedCommonOperands = extractCommonOperands(rexBuilder, operand, maxCNFNodeCount); //再次提取公共元素
for (RexNode extractedExpr : extractedCommonOperands) {
if (operandsToPushDownDigest.add(extractedExpr.toString())) {//如果集合不存在：返回true
operandsToPushDown.add(extractedExpr); //添加到可能操作符集合
}
}
}
//分拣出确定表达式和非确定表达式
if (HiveCalciteUtil.isDeterministic(operand)) {
deterministicExprs.add(operand);
} else {
nonDeterministicExprs.add(operand);
}
}
//从非确定性的集合个数大于0， 并遍历确定性的表达式结合 并把其元素RexNode添加到可能下推的集合中
*/
if (nonDeterministicExprs.size() > 0) {
for (RexNode expr : deterministicExprs) {
if (!operandsToPushDownDigest.contains(expr.toString())) {
operandsToPushDown.add(expr);
operandsToPushDownDigest.add(expr.toString());
}
}
//即Or表达式中，相同的因子被上拉。
//转换一个表达式集合 转换为and连接，如果有0个表达式，则返回true，如果有一个表达式，则只返回此表达式，
//如果表达式任意一个为false，则返回false，移除表达式总是认为是true，如果nullonempty并表达式为true，则返回null
topFilterCondition = RexUtil.pullFactors(rexBuilder,
RexUtil.composeConjunction(rexBuilder, nonDeterministicExprs, false));
}
break;
case OR://如果此Kind为Or，则使用extractCommonOperands函数提取公共因子，作为可能下推的集合operandsToPushDown
operandsToPushDown = extractCommonOperands(rexBuilder, topFilterCondition, maxCNFNodeCount);
break;
default:
return;
}
//如果没有找到可下推的 表达式，则跳出
if (operandsToPushDown.isEmpty()) {
return;
}上述讲述了topFilterCondition.getKind()是AND连接的情况。那么如果topFilterCondition.getKind()为OR连接的话，直接使用extractCommonOperands提取公用谓词表达式作为可下推的谓词表达式集合对象。HiveCalciteUtil.getPredsNotPushedAlready给定一个谓词可能下推的列表，此方法返回一个需要下推的谓词的集合，返回值：需要谓词下推的集合
需排除以下:
- 已经排除在外的，谓词的String字符串表达形式的集合，不应该包括在内
- 或他们已经是输入节点在子树根节点root的也应该排除在外
然后再次提取公用谓词表达式确定可下推的谓词表达式集合对象，创建新已下推的Filter注册到RelNode等价的RelNode集合。
代码语言：javascript复制// 3. If the new conjuncts are already present in the plan, we bail out
//如果一个新的and连接，已经在现有的执行计划中，则跳出优化
final List<RexNode> newConjuncts = HiveCalciteUtil.getPredsNotPushedAlready(filter.getInput(),
operandsToPushDown);
RexNode newPredicate = RexUtil.composeConjunction(rexBuilder, newConjuncts, false); //返回的and连接的行表达式
if (newPredicate.isAlwaysTrue()) {
return;
}
// 4. Otherwise, we create a new condition
// 提取Ors当中的共同因子并创建一个新的等价的节点
final RexNode newChildFilterCondition = RexUtil.pullFactors(rexBuilder, newPredicate);
// 5. We create the new filter that might be pushed down
RelNode newChildFilter = filterFactory.createFilter(filter.getInput(), newChildFilterCondition);
RelNode newTopFilter = filterFactory.createFilter(newChildFilter, topFilterCondition);
// 6. We register both so we do not fire the rule on them again
if (registry != null) {
registry.registerVisited(this, newChildFilter);
registry.registerVisited(this, newTopFilter);
}
call.transformTo(newTopFilter); 总结
HivePreFilteringRule优化规则可称为前置过滤器或谓词下推，估计有不少熟悉SQL的童鞋，都知道这一优化规则或方式，但可能不清楚优化器是如何识别哪些可下推的谓词表达式集合。进行下推等价变换，达到优化目的。
