Skip to content

Latest commit

 

History

History
161 lines (152 loc) · 6 KB

拆分过滤条件.md

File metadata and controls

161 lines (152 loc) · 6 KB

背景

需要做物化视图匹配, 例如以下例子

Query: SELECT a, c FROM t WHERE x = 5 AND b = 4
Target (materialized view definition): SELECT a, b, c FROM t WHERE x = 5
Result: SELECT a, c FROM mv WHERE b = 4

这个例子里面需要对WHERE中的条件去进行匹配，query 的 x = 5 AND b = 4， 再被mv 替代的时候， x = 5 已经是mv的过滤条件需要抽取出来 b = 4作为保留的过滤条件 下面看calcite中做这个拆分的方法

/**
   * 用当前的condition 和target的mv进行匹配.
   *
   * 1. 如果当前的condition比target的范围更严格，我们返回匹配上意外的剩余的条件
   * 2. 如果当前的condition和target的一样，返回常量true，过滤条件相同
   * 3. 如果当前的condition比target的限制条件还要弱，说明这里target的范围无法满足condition，返回null 无法做匹配
   *
   * 表达式关系如下
   *
   * <blockquote>
   * <pre>{@code condition = target AND residue}</pre>
   * </blockquote>
   *
   * 同时剩余的部分限制关系约弱越好
   *
   * <p>Example #1: condition stronger than target</p>
   * <ul>
   * <li>condition: x = 1 AND y = 2</li>
   * <li>target: x = 1</li>
   * <li>residue: y = 2</li>
   * </ul>
   *
   * <p>Example #2: target weaker than condition (valid, but not currently
   * implemented)</p>
   * <ul>
   * <li>condition: x = 1</li>
   * <li>target: x = 1 OR z = 3</li>
   * <li>residue: x = 1</li>
   * </ul>
   *
   * <p>Example #3: condition and target are equivalent</p>
   * <ul>
   * <li>condition: x = 1 AND y = 2</li>
   * <li>target: y = 2 AND x = 1</li>
   * <li>residue: TRUE</li>
   * </ul>
   *
   * <p>Example #4: condition weaker than target</p>
   * <ul>
   * <li>condition: x = 1</li>
   * <li>target: x = 1 AND y = 2</li>
   * <li>residue: null (i.e. no match)</li>
   * </ul>
   *
   * <p>There are many other possible examples. It amounts to solving
   * whether {@code condition AND NOT target} can ever evaluate to
   * true, and therefore is a form of the NP-complete
   * <a href="http://en.wikipedia.org/wiki/Satisfiability">Satisfiability</a>
   * problem.</p>
   */
  @VisibleForTesting
  public static RexNode splitFilter(final RexSimplify simplify,
      RexNode condition, RexNode target) {
    final RexBuilder rexBuilder = simplify.rexBuilder;
    // 给两个表达是做规范化（排序）
    RexNode condition2 = canonizeNode(rexBuilder, condition);
    RexNode target2 = canonizeNode(rexBuilder, target);

    // First, try splitting into ORs.
    // Given target    c1 OR c2 OR c3 OR c4
    // and condition   c2 OR c4
    // residue is      c2 OR c4
    // Also deals with case target [x] condition [x] yields residue [true].
    // 这个地方对于or条件单独的处理， 因为或条件的特殊性， 如果target的或条件组合
    // 比condition的或条件组合范围更大是，Filter(residue, target) 这是后拿出来才是
    // condition 所需要的数据范围
    // mv =Filter(a > 1 or b > 10, project)
    // query = Filter(a > 1, project)
    // result = Filter(a > 1, mv)
    RexNode z = splitOr(rexBuilder, condition2, target2);
    if (z != null) {
      return z;
    }

    if (isEquivalent(rexBuilder, condition2, target2)) {
      return rexBuilder.makeLiteral(true);
    }

    RexNode x = andNot(rexBuilder, target2, condition2);
    if (mayBeSatisfiable(x)) {
      RexNode x2 = RexUtil.composeConjunction(rexBuilder,
          ImmutableList.of(condition2, target2));
      RexNode r = canonizeNode(rexBuilder,
          simplify.simplifyUnknownAsFalse(x2));
      if (!r.isAlwaysFalse() && isEquivalent(rexBuilder, condition2, r)) {
        List<RexNode> conjs = RelOptUtil.conjunctions(r);
        for (RexNode e : RelOptUtil.conjunctions(target2)) {
          removeAll(conjs, e);
        }
        return RexUtil.composeConjunction(rexBuilder, conjs);
      }
    }
    return null;
  }

拆分共同的or条件

这个地方对于or条件单独的处理， 因为或条件的特殊性， 如果target的或条件组合
比condition的或条件组合范围更大是，Filter(residue, target) 这是后拿出来才是
condition 所需要的数据范围
mv =Filter(a > 1 or b > 10, project)
query = Filter(a > 1, project)
result = Filter(a > 1, mv)

  private static RexNode splitOr(
      final RexBuilder rexBuilder, RexNode condition, RexNode target) {
    // 获取析取范式
    List<RexNode> conditions = RelOptUtil.disjunctions(condition);
    int conditionsLength = conditions.size();
    int targetsLength = 0;
    // target的析取范式
    for (RexNode e : RelOptUtil.disjunctions(target)) {
      removeAll(conditions, e);
      targetsLength++;
    }
    // condition 为空表示 target的析取范式范围 >= condition的析取范式范围
    // 长度相同的时候，说明相等一样，恒为true
    if (conditions.isEmpty() && conditionsLength == targetsLength) {
      return rexBuilder.makeLiteral(true);
    } else if (conditions.isEmpty()) {
      // 不想等的时候， 且condition为空，说明target的范围更大，返回condition作为剩余条件
      return condition;
    }
    return null;
  }

判断表达式相等

在这里，当两个合取范式的结果一样的时候，认为两个表达式是一样的， 合取范式参考合取范式和析取范式

  // 合取范式相等的时候两个表达式相等
  private static boolean isEquivalent(RexBuilder rexBuilder, RexNode condition, RexNode target) {
    // Example:
    //  e: x = 1 AND y = 2 AND z = 3 AND NOT (x = 1 AND y = 2)
    //  disjunctions: {x = 1, y = 2, z = 3}
    //  notDisjunctions: {x = 1 AND y = 2}
    final Set<String> conditionDisjunctions = new HashSet<>(
        RexUtil.strings(RelOptUtil.conjunctions(condition)));
    final Set<String> targetDisjunctions = new HashSet<>(
        RexUtil.strings(RelOptUtil.conjunctions(target)));
    if (conditionDisjunctions.equals(targetDisjunctions)) {
      return true;
    }
    return false;
  }