@Override public boolean matches(RelOptRuleCall call) {
  // It avoids adding the rule match to the match queue in case the rule is known to be a no-op
  final SetOp topOp = call.rel(0);
  @SuppressWarnings("unchecked") final Class<? extends SetOp> setOpClass =
      (Class<? extends SetOp>) operands.get(0).getMatchedClass();
  final SetOp bottomOp;
  if (setOpClass.isInstance(call.rel(2))
      && !Minus.class.isAssignableFrom(setOpClass)) {
    bottomOp = call.rel(2);
  } else if (setOpClass.isInstance(call.rel(1))) {
    bottomOp = call.rel(1);
  } else {
    return false;
  }

  if (topOp.all && !bottomOp.all) {
    return false;
  }

  return true;
}
 

/** Returns an estimate of the number of rows returned by a {@link Minus}. */
public static double getMinusRowCount(RelMetadataQuery mq, Minus minus) {
  // REVIEW jvs 30-May-2005:  I just pulled this out of a hat.
  final List<RelNode> inputs = minus.getInputs();
  double dRows = mq.getRowCount(inputs.get(0));
  for (int i = 1; i < inputs.size(); i++) {
    dRows -= 0.5 * mq.getRowCount(inputs.get(i));
  }
  if (dRows < 0) {
    dRows = 0;
  }
  return dRows;
}
 

public Boolean areColumnsUnique(Minus rel, RelMetadataQuery mq,
    ImmutableBitSet columns, boolean ignoreNulls) {
  if (areColumnsUnique((SetOp) rel, mq, columns, ignoreNulls)) {
    return true;
  }
  return mq.areColumnsUnique(rel.getInput(0), columns, ignoreNulls);
}
 

public Double getRowCount(Minus rel, RelMetadataQuery mq) {
  Double rowCount = null;
  for (RelNode input : rel.getInputs()) {
    Double partialRowCount = mq.getRowCount(input);
    if (rowCount == null
        || partialRowCount != null && partialRowCount < rowCount) {
      rowCount = partialRowCount;
    }
  }
  return rowCount;
}
 

public Result visitChild(int i, RelNode e) {
  if (e instanceof Union) {
    return visitUnion((Union) e);
  } else if (e instanceof Join) {
    return visitJoin((Join) e);
  } else if (e instanceof Filter) {
    return visitFilter((Filter) e);
  } else if (e instanceof Project) {
    return visitProject((Project) e);
  } else if (e instanceof Aggregate) {
    return visitAggregate((Aggregate) e);
  } else if (e instanceof TableScan) {
    return visitTableScan((TableScan) e);
  } else if (e instanceof Intersect) {
    return visitIntersect((Intersect) e);
  } else if (e instanceof Minus) {
    return visitMinus((Minus) e);
  } else if (e instanceof Calc) {
    return visitCalc((Calc) e);
  } else if (e instanceof Sort) {
    return visitSort((Sort) e);
  } else if (e instanceof TableModify) {
    return visitTableModify((TableModify) e);
  } else if (e instanceof Limit) {
    return visitLimit((Limit) e);
  } else {
    throw new AssertionError("Need to Implement for " + e.getClass().getName()); // TODO:
  }
}
 

/** Returns an estimate of the number of rows returned by a {@link Minus}. */
public static double getMinusRowCount(RelMetadataQuery mq, Minus minus) {
  // REVIEW jvs 30-May-2005:  I just pulled this out of a hat.
  final List<RelNode> inputs = minus.getInputs();
  double dRows = mq.getRowCount(inputs.get(0));
  for (int i = 1; i < inputs.size(); i++) {
    dRows -= 0.5 * mq.getRowCount(inputs.get(i));
  }
  if (dRows < 0) {
    dRows = 0;
  }
  return dRows;
}
 

public Boolean areColumnsUnique(Minus rel, RelMetadataQuery mq,
    ImmutableBitSet columns, boolean ignoreNulls) {
  columns = decorateWithConstantColumnsFromPredicates(columns, rel, mq);
  if (areColumnsUnique((SetOp) rel, mq, columns, ignoreNulls)) {
    return true;
  }
  return mq.areColumnsUnique(rel.getInput(0), columns, ignoreNulls);
}
 

public Double getRowCount(Minus rel, RelMetadataQuery mq) {
  Double rowCount = null;
  for (RelNode input : rel.getInputs()) {
    Double partialRowCount = mq.getRowCount(input);
    if (rowCount == null
        || partialRowCount != null && partialRowCount < rowCount) {
      rowCount = partialRowCount;
    }
  }
  return rowCount;
}
 

public RelNode convert(RelNode rel) {
  final Minus minus = (Minus) rel;
  if (minus.all) {
    return null; // EXCEPT ALL not implemented
  }
  final RelTraitSet traitSet =
      rel.getTraitSet().replace(out);
  return new JdbcMinus(rel.getCluster(), traitSet,
      convertList(minus.getInputs(), out), false);
}
 

@Test void testNodeTypeCountMinusOnFinite() {
  final String sql = "select ename from (select * from emp limit 100)\n"
      + "except\n"
      + "select name from (select * from dept limit 40)";
  final Map<Class<? extends RelNode>, Integer> expected = new HashMap<>();
  expected.put(TableScan.class, 2);
  expected.put(Minus.class, 1);
  expected.put(Project.class, 4);
  expected.put(Sort.class, 2);
  checkNodeTypeCount(sql, expected);
}
 

public Multimap<Class<? extends RelNode>, RelNode> getNodeTypes(Minus rel,
    RelMetadataQuery mq) {
  return getNodeTypes(rel, Minus.class, mq);
}
 

public List<Double> averageColumnSizes(Minus rel, RelMetadataQuery mq) {
  return mq.getAverageColumnSizes(rel.getInput(0));
}
 

public Double getMaxRowCount(Minus rel, RelMetadataQuery mq) {
  return mq.getMaxRowCount(rel.getInput(0));
}
 

public Double getMinRowCount(Minus rel, RelMetadataQuery mq) {
  return 0d; // no lower bound
}
 

public void onMatch(RelOptRuleCall call) {
  final SetOp topOp = call.rel(0);
  @SuppressWarnings("unchecked") final Class<? extends SetOp> setOpClass =
      (Class) operands.get(0).getMatchedClass();

  // For Union and Intersect, we want to combine the set-op that's in the
  // second input first.
  //
  // For example, we reduce
  //    Union(Union(a, b), Union(c, d))
  // to
  //    Union(Union(a, b), c, d)
  // in preference to
  //    Union(a, b, Union(c, d))
  //
  // But for Minus, we can only reduce the left input. It is not valid to
  // reduce
  //    Minus(a, Minus(b, c))
  // to
  //    Minus(a, b, c)
  //
  // Hence, that's why the rule pattern matches on generic RelNodes rather
  // than explicit sub-classes of SetOp.  By doing so, and firing this rule
  // in a bottom-up order, it allows us to only specify a single
  // pattern for this rule.
  final SetOp bottomOp;
  if (setOpClass.isInstance(call.rel(2))
      && !Minus.class.isAssignableFrom(setOpClass)) {
    bottomOp = call.rel(2);
  } else if (setOpClass.isInstance(call.rel(1))) {
    bottomOp = call.rel(1);
  } else {
    return;
  }

  // Can only combine (1) if all operators are ALL,
  // or (2) top operator is DISTINCT (i.e. not ALL).
  // In case (2), all operators become DISTINCT.
  if (topOp.all && !bottomOp.all) {
    return;
  }

  // Combine the inputs from the bottom set-op with the other inputs from
  // the top set-op.
  final RelBuilder relBuilder = call.builder();
  if (setOpClass.isInstance(call.rel(2))
      && !Minus.class.isAssignableFrom(setOpClass)) {
    relBuilder.push(topOp.getInput(0));
    relBuilder.pushAll(bottomOp.getInputs());
    // topOp.getInputs().size() may be more than 2
    for (int index = 2; index < topOp.getInputs().size(); index++) {
      relBuilder.push(topOp.getInput(index));
    }
  } else {
    relBuilder.pushAll(bottomOp.getInputs());
    relBuilder.pushAll(Util.skip(topOp.getInputs()));
  }
  int n = bottomOp.getInputs().size()
      + topOp.getInputs().size()
      - 1;
  if (topOp instanceof Union) {
    relBuilder.union(topOp.all, n);
  } else if (topOp instanceof Intersect) {
    relBuilder.intersect(topOp.all, n);
  } else if (topOp instanceof Minus) {
    relBuilder.minus(topOp.all, n);
  }
  call.transformTo(relBuilder.build());
}
 

/** @see #dispatch */
public Result visit(Minus e) {
  return setOpToSql(e.all
      ? SqlStdOperatorTable.EXCEPT_ALL
      : SqlStdOperatorTable.EXCEPT, e);
}
 

/**
 * @see #dispatch
 */
public Result visit(Minus e) {
  return setOpToSql(e.all
    ? SqlStdOperatorTable.EXCEPT_ALL
    : SqlStdOperatorTable.EXCEPT, e);
}
 

public Result visitMinus(Minus e) {
  return setOpToSql(e.all
      ? SqlStdOperatorTable.EXCEPT_ALL
      : SqlStdOperatorTable.EXCEPT, e);
}
 

public Multimap<Class<? extends RelNode>, RelNode> getNodeTypes(Minus rel,
    RelMetadataQuery mq) {
  return getNodeTypes(rel, Minus.class, mq);
}
 

public List<Double> averageColumnSizes(Minus rel, RelMetadataQuery mq) {
  return mq.getAverageColumnSizes(rel.getInput(0));
}
 

public Double getMaxRowCount(Minus rel, RelMetadataQuery mq) {
  return mq.getMaxRowCount(rel.getInput(0));
}
 

public Double getMinRowCount(Minus rel, RelMetadataQuery mq) {
  return 0d; // no lower bound
}
 

/**
 * Infers predicates for a Minus.
 */
public RelOptPredicateList getPredicates(Minus minus, RelMetadataQuery mq) {
  return mq.getPulledUpPredicates(minus.getInput(0));
}
 

public void onMatch(RelOptRuleCall call) {
  final SetOp topOp = call.rel(0);
  @SuppressWarnings("unchecked") final Class<? extends SetOp> setOpClass =
      (Class) operands.get(0).getMatchedClass();

  // For Union and Intersect, we want to combine the set-op that's in the
  // second input first.
  //
  // For example, we reduce
  //    Union(Union(a, b), Union(c, d))
  // to
  //    Union(Union(a, b), c, d)
  // in preference to
  //    Union(a, b, Union(c, d))
  //
  // But for Minus, we can only reduce the left input. It is not valid to
  // reduce
  //    Minus(a, Minus(b, c))
  // to
  //    Minus(a, b, c)
  //
  // Hence, that's why the rule pattern matches on generic RelNodes rather
  // than explicit sub-classes of SetOp.  By doing so, and firing this rule
  // in a bottom-up order, it allows us to only specify a single
  // pattern for this rule.
  final SetOp bottomOp;
  if (setOpClass.isInstance(call.rel(2))
      && !Minus.class.isAssignableFrom(setOpClass)) {
    bottomOp = call.rel(2);
  } else if (setOpClass.isInstance(call.rel(1))) {
    bottomOp = call.rel(1);
  } else {
    return;
  }

  // Can only combine (1) if all operators are ALL,
  // or (2) top operator is DISTINCT (i.e. not ALL).
  // In case (2), all operators become DISTINCT.
  if (topOp.all && !bottomOp.all) {
    return;
  }

  // Combine the inputs from the bottom set-op with the other inputs from
  // the top set-op.
  final RelBuilder relBuilder = call.builder();
  if (setOpClass.isInstance(call.rel(2))
      && !Minus.class.isAssignableFrom(setOpClass)) {
    relBuilder.push(topOp.getInput(0));
    relBuilder.pushAll(bottomOp.getInputs());
    // topOp.getInputs().size() may be more than 2
    for (int index = 2; index < topOp.getInputs().size(); index++) {
      relBuilder.push(topOp.getInput(index));
    }
  } else {
    relBuilder.pushAll(bottomOp.getInputs());
    relBuilder.pushAll(Util.skip(topOp.getInputs()));
  }
  int n = bottomOp.getInputs().size()
      + topOp.getInputs().size()
      - 1;
  if (topOp instanceof Union) {
    relBuilder.union(topOp.all, n);
  } else if (topOp instanceof Intersect) {
    relBuilder.intersect(topOp.all, n);
  } else if (topOp instanceof Minus) {
    relBuilder.minus(topOp.all, n);
  }
  call.transformTo(relBuilder.build());
}
 

/** @see #dispatch */
public Result visit(Minus e) {
  return setOpToSql(e.all
      ? SqlStdOperatorTable.EXCEPT_ALL
      : SqlStdOperatorTable.EXCEPT, e);
}
 

/** Creates a JdbcMinusRule. */
private JdbcMinusRule(JdbcConvention out,
    RelBuilderFactory relBuilderFactory) {
  super(Minus.class, (Predicate<RelNode>) r -> true, Convention.NONE, out,
      relBuilderFactory, "JdbcMinusRule");
}