Apache Calcite 是獨立于存儲與執(zhí)行的SQL解析、優(yōu)化引擎驶兜，廣泛應(yīng)用于各種離線维费、搜索果元、實時查詢引擎，如Drill犀盟、Hive而晒、Kylin、Solr阅畴、flink倡怎、Samza等。本文結(jié)合hive中基于代價的優(yōu)化贱枣，解析calcite優(yōu)化引擎的實現(xiàn)原理监署。

Calcite架構(gòu)
??Calcite架構(gòu)圖如下，其中Operator Expressions 是查詢樹在calcite中的表示纽哥，可以直接通過calcite的SQL Parser解析得到钠乏，也可以通過Expressions Builder由Data Processing System中的查詢樹(本文對應(yīng)hive中的AST)轉(zhuǎn)換得到。Query Optimizer 根據(jù)Pluggable Rules對Operator Expressions進(jìn)行優(yōu)化春塌，其中會用到Metadata Providers提供的信息進(jìn)行代價計算等操作晓避。

Hive CBO
??本文中Data Processing System就是hive，本文主要解析hive如何利用calcite進(jìn)行基于代價的優(yōu)化（cost based optimization /CBO）只壳。Hive CBO的主要實現(xiàn)代碼在CalcitePlanner 這個類中, CalcitePlanner 繼承自SemanticAnalyzer俏拱，重寫了genOPTree 方法，由AST 生成 Operator Tree 吼句。其中CalcitePlanner.CalcitePlannerAction.genLogicalPlan 函數(shù)對應(yīng)上圖中的Expressions Builder锅必，把hive中的AST轉(zhuǎn)換成calcite 中的Operator Expressions，也就是節(jié)點為RelNode的查詢樹惕艳。這個過程這里不展開搞隐，繼續(xù)往下看。在CalcitePlanner.CalcitePlannerAction.HepPlan會對輸入的basePlan根據(jù)rules進(jìn)行優(yōu)化远搪，返回優(yōu)化過的plan劣纲，代碼如下：

主要數(shù)據(jù)結(jié)構(gòu)
??下圖列出了calcite中主要的相關(guān)接口和類恨憎，以及其中比較重要的成員蕊退。

優(yōu)化流程
??優(yōu)化的主入口是HepPlanner.findBestExp()芯勘，其中會調(diào)用executeProgram(mainProgram)，mainProgram 由Instructions組成腺逛，Instruction主要是RuleCollection荷愕，也有MatchOrder、MatchLimit等棍矛。對于RuleCollection安疗，executeInstruction就是對每一個rule進(jìn)行apply，這里以HiveReduceExpressionsRule為例往下分析够委，在HepPlanner.applyRule函數(shù)中可以看到荐类，首先調(diào)用matchOperands以及HiveReduceExpressionsRule.matches判斷此規(guī)則是否匹配，若匹配則調(diào)用fireRule(call)茁帽，會進(jìn)到HiveReduceExpressionsRule.onMatch函數(shù)進(jìn)行這條規(guī)則的具體優(yōu)化玉罐，時序圖如下：

private static RelMetadataProvider reflectiveSource(final Object target,
    final ImmutableList<Method> methods) {
  ...
  final Set<Class<RelNode>> classes = Sets.newHashSet();
  final Map<Pair<Class<RelNode>, Method>, Method> handlerMap =
      Maps.newHashMap();
  for (final Method handlerMethod : target.getClass().getMethods()) {
    for (Method method : methods) {
      if (couldImplement(handlerMethod, method)) {
        @SuppressWarnings("unchecked") final Class<RelNode> relNodeClass =
            (Class<RelNode>) handlerMethod.getParameterTypes()[0];
        classes.add(relNodeClass);
        handlerMap.put(Pair.of(relNodeClass, method), handlerMethod);
      }
    }
  }

  final ConcurrentMap<Class<RelNode>, UnboundMetadata> methodsMap = new ConcurrentHashMap<>();
  for (Class<RelNode> key : classes) {
    ImmutableNullableList.Builder<Method> builder =
        ImmutableNullableList.builder();
    for (final Method method : methods) {
      builder.add(find(handlerMap, key, method));
    }
    final List<Method> handlerMethods = builder.build();
    final UnboundMetadata function =
        new UnboundMetadata() {
          public Metadata bind(final RelNode rel,
              final RelMetadataQuery mq) {
            return (Metadata) Proxy.newProxyInstance(
                metadataClass0.getClassLoader(),
                new Class[]{metadataClass0},
                new InvocationHandler() {
                  public Object invoke(Object proxy, Method method,
                      Object[] args) throws Throwable {
     ...
                    try {
                      return handlerMethod.invoke(target, args1);
                    } catch (InvocationTargetException
                        | UndeclaredThrowableException e) {
                      Throwables.propagateIfPossible(e.getCause());
                      throw e;
                    } finally {
                      mq.set.remove(key);
                    }
                  }
                });
          }
        };
    methodsMap.put(key, function);
  }
  return new ReflectiveRelMetadataProvider(methodsMap, metadataClass0);
}

??函數(shù)的第一個參數(shù)target是hive實現(xiàn)的某個metadata的實現(xiàn)類疯搅，第二個參數(shù)methods是實現(xiàn)的目標(biāo)接口濒生。函數(shù)會找出target中對接口的實現(xiàn)函數(shù)，并將該實現(xiàn)函數(shù)的第一個參數(shù)作為key放在map中幔欧。之后在訪問matadata的時候罪治，會以當(dāng)前RelNode的實際類型為key，在map中查找實現(xiàn)函數(shù)礁蔗。如果沒有以當(dāng)前RelNode的實際類型為第一個參數(shù)的具體實現(xiàn)觉义，就會有空指針異常。這里有我向hive提交的一個patch(HIVE-19202)浴井，就是這樣的問題晒骇。

總結(jié)
本文介紹了calcite的架構(gòu)及hive利用calcite進(jìn)行CBO的部分源碼分析。我們了解了一個數(shù)據(jù)處理系統(tǒng)可以如何通過擴(kuò)展calcite的rule和metadata接口實現(xiàn)自定義的優(yōu)化處理磺浙。