hsyuan commented on a change in pull request #1451: [CALCITE-3334] Refinement
for Substitution-Based MV Matching
URL: https://github.com/apache/calcite/pull/1451#discussion_r338816965
##########
File path: core/src/main/java/org/apache/calcite/plan/SubstitutionVisitor.java
##########
@@ -997,233 +1021,493 @@ public UnifyResult apply(UnifyRuleCall call) {
}
}
- /** Implementation of {@link UnifyRule} that matches
- * {@link org.apache.calcite.rel.core.TableScan}. */
- private static class ScanToProjectUnifyRule extends AbstractUnifyRule {
- public static final ScanToProjectUnifyRule INSTANCE =
- new ScanToProjectUnifyRule();
+ /**
+ * A {@link SubstitutionVisitor.UnifyRule} that matches a
+ * {@link MutableScan} to a {@link MutableCalc}
+ * which has {@link MutableScan} as child.
+ */
+ private static class ScanToCalcUnifyRule extends AbstractUnifyRule {
+
+ public static final ScanToCalcUnifyRule INSTANCE = new
ScanToCalcUnifyRule();
- private ScanToProjectUnifyRule() {
+ private ScanToCalcUnifyRule() {
super(any(MutableScan.class),
- any(MutableProject.class), 0);
+ operand(MutableCalc.class, any(MutableScan.class)), 0);
}
- public UnifyResult apply(UnifyRuleCall call) {
- final MutableProject target = (MutableProject) call.target;
+ @Override protected UnifyResult apply(UnifyRuleCall call) {
+
final MutableScan query = (MutableScan) call.query;
- // We do not need to check query's parent type to avoid duplication
- // of ProjectToProjectUnifyRule or FilterToProjectUnifyRule, since
- // SubstitutionVisitor performs a top-down match.
- if (!query.equals(target.getInput())) {
+
+ final MutableCalc target = (MutableCalc) call.target;
+ final MutableScan targetInput = (MutableScan) target.getInput();
+ final Pair<RexNode, List<RexNode>> targetExplained = explainCalc(target);
+ final RexNode targetCond = targetExplained.left;
+ final List<RexNode> targetProjs = targetExplained.right;
+
+ final RexBuilder rexBuilder = call.getCluster().getRexBuilder();
+
+ if (!query.equals(targetInput) || !targetCond.isAlwaysTrue()) {
return null;
}
- final RexShuttle shuttle = getRexShuttle(target);
- final RexBuilder rexBuilder = target.cluster.getRexBuilder();
- final List<RexNode> newProjects;
+ final RexShuttle shuttle = getRexShuttle(targetProjs);
+ final List<RexNode> compenProjs;
try {
- newProjects = (List<RexNode>)
- shuttle.apply(rexBuilder.identityProjects(query.rowType));
+ compenProjs = (List<RexNode>) shuttle.apply(
+ rexBuilder.identityProjects(query.rowType));
} catch (MatchFailed e) {
return null;
}
- final MutableProject newProject =
- MutableProject.of(query.rowType, target, newProjects);
- final MutableRel newProject2 = MutableRels.strip(newProject);
- return call.result(newProject2);
+ if (RexUtil.isIdentity(compenProjs, target.rowType)) {
+ return call.result(target);
+ } else {
+ RexProgram compenRexProgram = RexProgram.create(
+ target.rowType, compenProjs, null, query.rowType, rexBuilder);
+ MutableCalc compenCalc = MutableCalc.of(target, compenRexProgram);
+ return tryMergeParentCalcAndGenResult(call, compenCalc);
+ }
}
}
- /** Implementation of {@link UnifyRule} that matches
- * {@link org.apache.calcite.rel.core.Project}. */
- private static class ProjectToProjectUnifyRule extends AbstractUnifyRule {
- public static final ProjectToProjectUnifyRule INSTANCE =
- new ProjectToProjectUnifyRule();
+ /**
+ * A {@link SubstitutionVisitor.UnifyRule} that matches a
+ * {@link MutableCalc} to a {@link MutableCalc}.
+ * The matching condition is as below:
+ * 1. All columns of query can be expressed by target;
+ * 2. The filtering condition of query must equals to or be weaker than
target.
+ */
+ private static class CalcToCalcUnifyRule extends AbstractUnifyRule {
- private ProjectToProjectUnifyRule() {
- super(operand(MutableProject.class, query(0)),
- operand(MutableProject.class, target(0)), 1);
- }
+ public static final CalcToCalcUnifyRule INSTANCE =
+ new CalcToCalcUnifyRule();
- public UnifyResult apply(UnifyRuleCall call) {
- final MutableProject target = (MutableProject) call.target;
- final MutableProject query = (MutableProject) call.query;
- final RexShuttle shuttle = getRexShuttle(target);
- final List<RexNode> newProjects;
- try {
- newProjects = shuttle.apply(query.projects);
- } catch (MatchFailed e) {
- return null;
- }
- final MutableProject newProject =
- MutableProject.of(query.rowType, target, newProjects);
- final MutableRel newProject2 = MutableRels.strip(newProject);
- return call.result(newProject2);
+ private CalcToCalcUnifyRule() {
+ super(operand(MutableCalc.class, query(0)),
+ operand(MutableCalc.class, target(0)), 1);
}
- }
+ public UnifyResult apply(UnifyRuleCall call) {
+ final MutableCalc query = (MutableCalc) call.query;
+ final Pair<RexNode, List<RexNode>> queryExplained = explainCalc(query);
+ final RexNode queryCond = queryExplained.left;
+ final List<RexNode> queryProjs = queryExplained.right;
- /** Implementation of {@link UnifyRule} that matches a {@link MutableFilter}
- * to a {@link MutableProject}. */
- private static class FilterToProjectUnifyRule extends AbstractUnifyRule {
- public static final FilterToProjectUnifyRule INSTANCE =
- new FilterToProjectUnifyRule();
+ final MutableCalc target = (MutableCalc) call.target;
+ final Pair<RexNode, List<RexNode>> targetExplained = explainCalc(target);
+ final RexNode targetCond = targetExplained.left;
+ final List<RexNode> targetProjs = targetExplained.right;
- private FilterToProjectUnifyRule() {
- super(operand(MutableFilter.class, query(0)),
- operand(MutableProject.class, target(0)), 1);
- }
+ final RexBuilder rexBuilder = call.getCluster().getRexBuilder();
- public UnifyResult apply(UnifyRuleCall call) {
- // Child of projectTarget is equivalent to child of filterQuery.
try {
- // TODO: make sure that constants are ok
- final MutableProject target = (MutableProject) call.target;
- final RexShuttle shuttle = getRexShuttle(target);
- final RexNode newCondition;
- final MutableFilter query = (MutableFilter) call.query;
- try {
- newCondition = query.condition.accept(shuttle);
- } catch (MatchFailed e) {
+ final RexShuttle shuttle = getRexShuttle(targetProjs);
+ final RexNode splitted =
+ splitFilter(call.getSimplify(), queryCond, targetCond);
+
+ final RexNode compenCond;
+ if (splitted != null) {
+ if (splitted.isAlwaysTrue()) {
+ compenCond = null;
+ } else {
+ // Compensate the residual filtering condition.
+ compenCond = shuttle.apply(splitted);
+ }
+ } else if (implies(
+ call.getCluster(), queryCond, targetCond,
query.getInput().rowType)) {
+ // Fail to split filtering condition, but implies that target
contains
+ // all lines of query, thus just set compensating filtering condition
+ // as the filtering condition of query.
+ compenCond = shuttle.apply(queryCond);
+ } else {
return null;
}
- final MutableFilter newFilter = MutableFilter.of(target, newCondition);
- if (query.getParent() instanceof MutableProject) {
- final MutableRel inverse =
- invert(((MutableProject) query.getParent()).getNamedProjects(),
- newFilter, shuttle);
- return call.create(query.getParent()).result(inverse);
+
+ final List<RexNode> compenProjs = shuttle.apply(queryProjs);
+ if (compenCond == null
+ && RexUtil.isIdentity(compenProjs, target.rowType)) {
+ return call.result(target);
} else {
- final MutableRel inverse = invert(query, newFilter, target);
- return call.result(inverse);
+ RexProgram compenRexProgram = RexProgram.create(
+ target.rowType, compenProjs, compenCond,
+ query.rowType, rexBuilder);
+ MutableCalc compenCalc = MutableCalc.of(target, compenRexProgram);
+ return tryMergeParentCalcAndGenResult(call, compenCalc);
}
} catch (MatchFailed e) {
return null;
}
}
+ }
- protected MutableRel invert(List<Pair<RexNode, String>> namedProjects,
- MutableRel input,
- RexShuttle shuttle) {
- LOGGER.trace("SubstitutionVisitor: invert:\nprojects: {}\ninput:
{}\nproject: {}\n",
- namedProjects, input, shuttle);
- final List<RexNode> exprList = new ArrayList<>();
- final RexBuilder rexBuilder = input.cluster.getRexBuilder();
- final List<RexNode> projects = Pair.left(namedProjects);
- for (RexNode expr : projects) {
- exprList.add(rexBuilder.makeZeroLiteral(expr.getType()));
- }
- for (Ord<RexNode> expr : Ord.zip(projects)) {
- final RexNode node = expr.e.accept(shuttle);
- if (node == null) {
- throw MatchFailed.INSTANCE;
- }
- exprList.set(expr.i, node);
- }
- return MutableProject.of(input, exprList, Pair.right(namedProjects));
+ /**
+ * A {@link SubstitutionVisitor.UnifyRule} that matches a {@link MutableJoin}
+ * which has {@link MutableCalc} as left child to a {@link MutableJoin}.
+ * We try to pull up the {@link MutableCalc} to top of {@link MutableJoin},
+ * then match the {@link MutableJoin} in query to {@link MutableJoin} in
target.
+ */
+ private static class JoinOnLeftCalcToJoinUnifyRule extends AbstractUnifyRule
{
+
+ public static final JoinOnLeftCalcToJoinUnifyRule INSTANCE =
+ new JoinOnLeftCalcToJoinUnifyRule();
+
+ private JoinOnLeftCalcToJoinUnifyRule() {
+ super(
+ operand(MutableJoin.class, operand(MutableCalc.class, query(0)),
query(1)),
+ operand(MutableJoin.class, target(0), target(1)), 2);
}
- protected MutableRel invert(MutableRel model, MutableRel input,
- MutableProject project) {
- LOGGER.trace("SubstitutionVisitor: invert:\nmodel: {}\ninput:
{}\nproject: {}\n",
- model, input, project);
- if (project.projects.size() < model.rowType.getFieldCount()) {
- throw MatchFailed.INSTANCE;
- }
- final List<RexNode> exprList = new ArrayList<>();
- final RexBuilder rexBuilder = model.cluster.getRexBuilder();
- for (int i = 0; i < model.rowType.getFieldCount(); i++) {
- exprList.add(null);
+ @Override protected UnifyResult apply(UnifyRuleCall call) {
+ final MutableJoin query = (MutableJoin) call.query;
+ final MutableCalc qInput0 = (MutableCalc) query.getLeft();
+ final MutableRel qInput1 = query.getRight();
+ final Pair<RexNode, List<RexNode>> qInput0Explained =
explainCalc(qInput0);
+ final RexNode qInput0Cond = qInput0Explained.left;
+ final List<RexNode> qInput0Projs = qInput0Explained.right;
+
+ final MutableJoin target = (MutableJoin) call.target;
+
+ final RexBuilder rexBuilder = call.getCluster().getRexBuilder();
+
+ // Try pulling up MutableCalc only when:
+ // 1. it's inner join;
+ // 2. it's outer join but no filttering condition from MutableCalc.
+ JoinRelType joinRelType = sameJoinType(query.joinType, target.joinType);
+ if (joinRelType == null) {
+ return null;
}
- for (Ord<RexNode> expr : Ord.zip(project.projects)) {
- if (expr.e instanceof RexInputRef) {
- final int target = ((RexInputRef) expr.e).getIndex();
- if (exprList.get(target) == null) {
- exprList.set(target,
- rexBuilder.ensureType(expr.e.getType(),
- RexInputRef.of(expr.i, input.rowType),
- false));
+ if (joinRelType == JoinRelType.INNER
+ || (joinRelType.isOuterJoin() && qInput0Cond.isAlwaysTrue())) {
+ // Try pulling up MutableCalc only when Join condition references
mapping.
+ List<RexNode> identityProjects =
+ (List<RexNode>) rexBuilder.identityProjects(qInput1.rowType);
+ if (referenceByMapping(query.condition, qInput0Projs,
identityProjects)) {
+ RexNode newQueryJoinCond = new RexShuttle() {
+ @Override public RexNode visitInputRef(RexInputRef inputRef) {
+ int idx = inputRef.getIndex();
+ if (idx < fieldCnt(qInput0)) {
+ int newIdx = ((RexInputRef) qInput0Projs.get(idx)).getIndex();
+ return new RexInputRef(newIdx, inputRef.getType());
+ } else {
+ int newIdx = idx - fieldCnt(qInput0) +
fieldCnt(qInput0.getInput());
+ return new RexInputRef(newIdx, inputRef.getType());
+ }
+ }
+ }.apply(query.condition);
+
+ RexNode splitted =
+ splitFilter(call.getSimplify(), newQueryJoinCond,
target.condition);
+ // MutableJoin matches only when the conditions are analyzed to be
same.
+ if (splitted != null && splitted.isAlwaysTrue()) {
+ final RexNode compenCond = qInput0Cond;
+ final List<RexNode> compenProjs = new ArrayList<>();
+ for (int i = 0; i < fieldCnt(query); i++) {
+ if (i < fieldCnt(qInput0)) {
+ compenProjs.add(qInput0Projs.get(i));
+ } else {
+ int newIdx = i - fieldCnt(qInput0) +
fieldCnt(qInput0.getInput());
+ compenProjs.add(
+ new RexInputRef(newIdx,
query.rowType.getFieldList().get(i).getType()));
+ }
+ }
+ RexProgram compenRexProgram = RexProgram.create(
+ target.rowType, compenProjs, compenCond,
+ query.rowType, rexBuilder);
+ MutableCalc compenCalc = MutableCalc.of(target, compenRexProgram);
+ return tryMergeParentCalcAndGenResult(call, compenCalc);
}
}
}
- if (exprList.indexOf(null) != -1) {
- throw MatchFailed.INSTANCE;
- }
- return MutableProject.of(model.rowType, input, exprList);
+ return null;
}
}
- /** Implementation of {@link UnifyRule} that matches a
- * {@link MutableFilter}. */
- private static class FilterToFilterUnifyRule extends AbstractUnifyRule {
- public static final FilterToFilterUnifyRule INSTANCE =
- new FilterToFilterUnifyRule();
+ /**
+ * A {@link SubstitutionVisitor.UnifyRule} that matches a {@link MutableJoin}
+ * which has {@link MutableCalc} as right child to a {@link MutableJoin}.
+ * We try to pull up the {@link MutableCalc} to top of {@link MutableJoin},
+ * then match the {@link MutableJoin} in query to {@link MutableJoin} in
target.
+ */
+ private static class JoinOnRightCalcToJoinUnifyRule extends
AbstractUnifyRule {
+
+ public static final JoinOnRightCalcToJoinUnifyRule INSTANCE =
+ new JoinOnRightCalcToJoinUnifyRule();
- private FilterToFilterUnifyRule() {
- super(operand(MutableFilter.class, query(0)),
- operand(MutableFilter.class, target(0)), 1);
+ private JoinOnRightCalcToJoinUnifyRule() {
+ super(
+ operand(MutableJoin.class, query(0), operand(MutableCalc.class,
query(1))),
+ operand(MutableJoin.class, target(0), target(1)), 2);
}
- public UnifyResult apply(UnifyRuleCall call) {
- // in.query can be rewritten in terms of in.target if its condition
- // is weaker. For example:
- // query: SELECT * FROM t WHERE x = 1 AND y = 2
- // target: SELECT * FROM t WHERE x = 1
- // transforms to
- // result: SELECT * FROM (target) WHERE y = 2
- final MutableFilter query = (MutableFilter) call.query;
- final MutableFilter target = (MutableFilter) call.target;
- final MutableFilter newFilter =
- createFilter(call, query, target);
- if (newFilter == null) {
+ @Override protected UnifyResult apply(UnifyRuleCall call) {
+ final MutableJoin query = (MutableJoin) call.query;
+ final MutableRel qInput0 = query.getLeft();
+ final MutableCalc qInput1 = (MutableCalc) query.getRight();
+ final Pair<RexNode, List<RexNode>> qInput1Explained =
explainCalc(qInput1);
+ final RexNode qInput1Cond = qInput1Explained.left;
+ final List<RexNode> qInput1Projs = qInput1Explained.right;
+
+ final MutableJoin target = (MutableJoin) call.target;
+
+ final RexBuilder rexBuilder = call.getCluster().getRexBuilder();
+
+ // Try pulling up MutableCalc only when:
+ // 1. it's inner join;
+ // 2. it's outer join but no filttering condition from MutableCalc.
+ JoinRelType joinRelType = sameJoinType(query.joinType, target.joinType);
+ if (joinRelType == null) {
return null;
}
- return call.result(newFilter);
+ if (joinRelType == JoinRelType.INNER
+ || (joinRelType.isOuterJoin() && qInput1Cond.isAlwaysTrue())) {
+ // Try pulling up MutableCalc only when Join condition references
mapping.
+ List<RexNode> identityProjects =
+ (List<RexNode>) rexBuilder.identityProjects(qInput0.rowType);
+ if (referenceByMapping(query.condition, identityProjects,
qInput1Projs)) {
+ RexNode newQueryJoinCond = new RexShuttle() {
+ @Override public RexNode visitInputRef(RexInputRef inputRef) {
+ int idx = inputRef.getIndex();
+ if (idx < fieldCnt(qInput0)) {
+ return inputRef;
+ } else {
+ int newIdx = ((RexInputRef) qInput1Projs.get(idx -
fieldCnt(qInput0)))
+ .getIndex() + fieldCnt(qInput0);
+ return new RexInputRef(newIdx, inputRef.getType());
+ }
+ }
+ }.apply(query.condition);
+
+ RexNode splitted =
+ splitFilter(call.getSimplify(), newQueryJoinCond,
target.condition);
+ // MutableJoin matches only when the conditions are analyzed to be
same.
+ if (splitted != null && splitted.isAlwaysTrue()) {
+ RexShuttle shuttle4Right =
+ new RexShuttle() {
+ @Override public RexNode visitInputRef(RexInputRef inputRef)
{
+ return new RexInputRef(
+ inputRef.getIndex() + qInput0.rowType.getFieldCount(),
+ inputRef.getType());
+ }
+ };
+ final RexNode compenCond = shuttle4Right.apply(qInput1Cond);
+ final List<RexNode> compenProjs = new ArrayList<>();
+ for (int i = 0; i < query.rowType.getFieldCount(); i++) {
+ if (i < fieldCnt(qInput0)) {
+ compenProjs.add(
+ new RexInputRef(i,
query.rowType.getFieldList().get(i).getType()));
+ } else {
+ compenProjs.add(
+ shuttle4Right.apply(qInput1Projs.get(i -
fieldCnt(qInput0))));
+ }
+ }
+ RexProgram compensatingRexProgram = RexProgram.create(
+ target.rowType, compenProjs, compenCond,
+ query.rowType, rexBuilder);
+ MutableCalc compenCalc = MutableCalc.of(target,
compensatingRexProgram);
+ return tryMergeParentCalcAndGenResult(call, compenCalc);
+ }
+ }
+ }
+ return null;
}
+ }
+
+ /**
+ * A {@link SubstitutionVisitor.UnifyRule} that matches a {@link MutableJoin}
+ * which has {@link MutableCalc} as children to a {@link MutableJoin}.
+ * We try to pull up the {@link MutableCalc} to top of {@link MutableJoin},
+ * then match the {@link MutableJoin} in query to {@link MutableJoin} in
target.
+ */
+ private static class JoinOnCalcsToJoinUnifyRule extends AbstractUnifyRule {
- MutableFilter createFilter(UnifyRuleCall call, MutableFilter query,
- MutableFilter target) {
- final RexNode newCondition =
- splitFilter(call.getSimplify(), query.condition,
- target.condition);
- if (newCondition == null) {
- // Could not map query onto target.
+ public static final JoinOnCalcsToJoinUnifyRule INSTANCE =
+ new JoinOnCalcsToJoinUnifyRule();
+
+ private JoinOnCalcsToJoinUnifyRule() {
+ super(
+ operand(MutableJoin.class,
+ operand(MutableCalc.class, query(0)), operand(MutableCalc.class,
query(1))),
+ operand(MutableJoin.class, target(0), target(1)), 2);
+ }
+
+ @Override protected UnifyResult apply(UnifyRuleCall call) {
+ final MutableJoin query = (MutableJoin) call.query;
+ final MutableCalc qInput0 = (MutableCalc) query.getLeft();
+ final MutableCalc qInput1 = (MutableCalc) query.getRight();
+ final Pair<RexNode, List<RexNode>> qInput0Explained =
explainCalc(qInput0);
+ final RexNode qInput0Cond = qInput0Explained.left;
+ final List<RexNode> qInput0Projs = qInput0Explained.right;
+ final Pair<RexNode, List<RexNode>> qInput1Explained =
explainCalc(qInput1);
+ final RexNode qInput1Cond = qInput1Explained.left;
+ final List<RexNode> qInput1Projs = qInput1Explained.right;
+
+ final MutableJoin target = (MutableJoin) call.target;
+
+ final RexBuilder rexBuilder = call.getCluster().getRexBuilder();
+
+ // Try pulling up MutableCalc only when:
+ // 1. it's inner join;
+ // 2. it's outer join but no filttering condition from MutableCalc.
+ JoinRelType joinRelType = sameJoinType(query.joinType, target.joinType);
+ if (joinRelType == null) {
return null;
}
- if (newCondition.isAlwaysTrue()) {
- return target;
+ if (joinRelType == JoinRelType.INNER
+ || (joinRelType.isOuterJoin()
+ && qInput0Cond.isAlwaysTrue()
+ && qInput1Cond.isAlwaysTrue())) {
+ // Try pulling up MutableCalc only when Join condition references
mapping.
+ if (referenceByMapping(query.condition, qInput0Projs, qInput1Projs)) {
+ RexNode newQueryJoinCond = new RexShuttle() {
+ @Override public RexNode visitInputRef(RexInputRef inputRef) {
+ int idx = inputRef.getIndex();
+ if (idx < fieldCnt(qInput0)) {
+ int newIdx = ((RexInputRef) qInput0Projs.get(idx)).getIndex();
+ return new RexInputRef(newIdx, inputRef.getType());
+ } else {
+ int newIdx = ((RexInputRef) qInput1Projs.get(idx -
fieldCnt(qInput0)))
+ .getIndex() + fieldCnt(qInput0.getInput());
+ return new RexInputRef(newIdx, inputRef.getType());
+ }
+ }
+ }.apply(query.condition);
+ RexNode splitted =
+ splitFilter(call.getSimplify(), newQueryJoinCond,
target.condition);
+ // MutableJoin matches only when the conditions are analyzed to be
same.
+ if (splitted != null && splitted.isAlwaysTrue()) {
+ RexShuttle shuttle4Right =
+ new RexShuttle() {
+ @Override public RexNode visitInputRef(RexInputRef inputRef)
{
+ int newIdx =
+ inputRef.getIndex() + fieldCnt(qInput0.getInput());
+ return new RexInputRef(newIdx, inputRef.getType());
+ }
+ };
Review comment:
Can we use `RexUtils.shift` if it is applicable?
----------------------------------------------------------------
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
For queries about this service, please contact Infrastructure at:
[email protected]
With regards,
Apache Git Services
