You are viewing a plain text version of this content. The canonical link for it is here.
Posted to commits@calcite.apache.org by hy...@apache.org on 2019/04/09 16:16:16 UTC
[calcite] branch master updated: [CALCITE-2456] VolcanoRuleCall
doesn't match unordered child operand when the operand is not the first
operand. PruneEmptyRules UNION and MINUS with empty inputs cause infinite
cycle. (Zuozhi Wang)
This is an automated email from the ASF dual-hosted git repository.
hyuan pushed a commit to branch master
in repository https://gitbox.apache.org/repos/asf/calcite.git
The following commit(s) were added to refs/heads/master by this push:
new 72e952d [CALCITE-2456] VolcanoRuleCall doesn't match unordered child operand when the operand is not the first operand. PruneEmptyRules UNION and MINUS with empty inputs cause infinite cycle. (Zuozhi Wang)
72e952d is described below
commit 72e952d1a79ee2d7ba05de88cbc2ac11f65cd879
Author: zuozhiw <zu...@gmail.com>
AuthorDate: Thu Aug 9 16:13:58 2018 +0800
[CALCITE-2456] VolcanoRuleCall doesn't match unordered child operand when the operand is not the first operand. PruneEmptyRules UNION and MINUS with empty inputs cause infinite cycle. (Zuozhi Wang)
UNION and MINUS corrected by Vladimir Sitnikov.
Note: call.getChildRels(RelNode) was used previously to get inputs of UNION/MINUS,
and it looks like the method is ill-defined (at least, it returns wrong results).
fixes #784
---
.../org/apache/calcite/plan/RelOptRuleCall.java | 2 +
.../calcite/plan/volcano/VolcanoRuleCall.java | 41 +++++-
.../apache/calcite/rel/rules/PruneEmptyRules.java | 85 ++++++------
.../calcite/plan/volcano/VolcanoPlannerTest.java | 1 -
.../calcite/rel/rules/SortRemoveRuleTest.java | 3 +-
.../java/org/apache/calcite/tools/PlannerTest.java | 147 +++++++++++++++++++++
6 files changed, 231 insertions(+), 48 deletions(-)
diff --git a/core/src/main/java/org/apache/calcite/plan/RelOptRuleCall.java b/core/src/main/java/org/apache/calcite/plan/RelOptRuleCall.java
index 2654b54..d8e459e 100644
--- a/core/src/main/java/org/apache/calcite/plan/RelOptRuleCall.java
+++ b/core/src/main/java/org/apache/calcite/plan/RelOptRuleCall.java
@@ -165,6 +165,8 @@ public abstract class RelOptRuleCall {
* children, and hence where the matched children are not retrievable by any
* other means.
*
+ * <p>Warning: it produces wrong result for {@code unordered(...)} case.
+ *
* @param rel Relational expression
* @return Children of relational expression
*/
diff --git a/core/src/main/java/org/apache/calcite/plan/volcano/VolcanoRuleCall.java b/core/src/main/java/org/apache/calcite/plan/volcano/VolcanoRuleCall.java
index 908a166..5aca507 100644
--- a/core/src/main/java/org/apache/calcite/plan/volcano/VolcanoRuleCall.java
+++ b/core/src/main/java/org/apache/calcite/plan/volcano/VolcanoRuleCall.java
@@ -19,6 +19,7 @@ package org.apache.calcite.plan.volcano;
import org.apache.calcite.plan.RelOptListener;
import org.apache.calcite.plan.RelOptRuleCall;
import org.apache.calcite.plan.RelOptRuleOperand;
+import org.apache.calcite.plan.RelOptRuleOperandChildPolicy;
import org.apache.calcite.rel.RelNode;
import com.google.common.collect.ImmutableList;
@@ -28,8 +29,10 @@ import com.google.common.collect.Lists;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collection;
+import java.util.HashSet;
import java.util.List;
import java.util.Map;
+import java.util.Set;
/**
* <code>VolcanoRuleCall</code> implements the {@link RelOptRuleCall} interface
@@ -281,11 +284,38 @@ public class VolcanoRuleCall extends RelOptRuleCall {
final int parentOrdinal = operand.getParent().ordinalInRule;
final RelNode parentRel = rels[parentOrdinal];
final List<RelNode> inputs = parentRel.getInputs();
- if (operand.ordinalInParent < inputs.size()) {
+ // if the child is unordered, then add all rels in all input subsets to the successors list
+ // because unordered can match child in any ordinal
+ if (parentOperand.childPolicy == RelOptRuleOperandChildPolicy.UNORDERED) {
+ if (operand.getMatchedClass() == RelSubset.class) {
+ successors = inputs;
+ } else {
+ List<RelNode> allRelsInAllSubsets = new ArrayList<>();
+ Set<RelNode> duplicates = new HashSet<>();
+ for (RelNode input : inputs) {
+ if (!duplicates.add(input)) {
+ // Ignore duplicate subsets
+ continue;
+ }
+ RelSubset inputSubset = (RelSubset) input;
+ for (RelNode rel : inputSubset.getRels()) {
+ if (!duplicates.add(rel)) {
+ // Ignore duplicate relations
+ continue;
+ }
+ allRelsInAllSubsets.add(rel);
+ }
+ }
+ successors = allRelsInAllSubsets;
+ }
+ } else if (operand.ordinalInParent < inputs.size()) {
+ // child policy is not unordered
+ // we need to find the exact input node based on child operand's ordinalInParent
final RelSubset subset =
(RelSubset) inputs.get(operand.ordinalInParent);
if (operand.getMatchedClass() == RelSubset.class) {
- successors = subset.set.subsets;
+ // If the rule wants the whole subset, we just provide it
+ successors = ImmutableList.of(subset);
} else {
successors = subset.getRelList();
}
@@ -300,7 +330,7 @@ public class VolcanoRuleCall extends RelOptRuleCall {
if (!operand.matches(rel)) {
continue;
}
- if (ascending) {
+ if (ascending && operand.childPolicy != RelOptRuleOperandChildPolicy.UNORDERED) {
// We know that the previous operand was *a* child of its parent,
// but now check that it is the *correct* child.
final RelSubset input =
@@ -314,6 +344,11 @@ public class VolcanoRuleCall extends RelOptRuleCall {
// Assign "childRels" if the operand is UNORDERED.
switch (parentOperand.childPolicy) {
case UNORDERED:
+ // Note: below is ill-defined. Suppose there's a union with 3 inputs,
+ // and the rule is written as Union.class, unordered(...)
+ // What should be provided for the rest 2 arguments?
+ // RelSubsets? Random relations from those subsets?
+ // For now, Calcite code does not use getChildRels, so the bug is just waiting its day
if (ascending) {
final List<RelNode> inputs = Lists.newArrayList(rel.getInputs());
inputs.set(previousOperand.ordinalInParent, previous);
diff --git a/core/src/main/java/org/apache/calcite/rel/rules/PruneEmptyRules.java b/core/src/main/java/org/apache/calcite/rel/rules/PruneEmptyRules.java
index 1cc48b5..64f20d1 100644
--- a/core/src/main/java/org/apache/calcite/rel/rules/PruneEmptyRules.java
+++ b/core/src/main/java/org/apache/calcite/rel/rules/PruneEmptyRules.java
@@ -19,6 +19,8 @@ package org.apache.calcite.rel.rules;
import org.apache.calcite.plan.RelOptRule;
import org.apache.calcite.plan.RelOptRuleCall;
import org.apache.calcite.plan.RelOptUtil;
+import org.apache.calcite.plan.hep.HepRelVertex;
+import org.apache.calcite.plan.volcano.RelSubset;
import org.apache.calcite.rel.RelNode;
import org.apache.calcite.rel.SingleRel;
import org.apache.calcite.rel.core.Aggregate;
@@ -37,7 +39,6 @@ import org.apache.calcite.rex.RexLiteral;
import org.apache.calcite.tools.RelBuilder;
import org.apache.calcite.tools.RelBuilderFactory;
-import java.util.ArrayList;
import java.util.List;
import java.util.function.Predicate;
@@ -79,31 +80,23 @@ public abstract class PruneEmptyRules {
"Union") {
public void onMatch(RelOptRuleCall call) {
final LogicalUnion union = call.rel(0);
- final List<RelNode> inputs = call.getChildRels(union);
+ final List<RelNode> inputs = union.getInputs();
assert inputs != null;
- final List<RelNode> newInputs = new ArrayList<>();
+ final RelBuilder builder = call.builder();
+ int nonEmptyInputs = 0;
for (RelNode input : inputs) {
if (!isEmpty(input)) {
- newInputs.add(input);
+ builder.push(input);
+ nonEmptyInputs++;
}
}
- assert newInputs.size() < inputs.size()
- : "planner promised us at least one Empty child";
- final RelBuilder builder = call.builder();
- switch (newInputs.size()) {
- case 0:
+ assert nonEmptyInputs < inputs.size()
+ : "planner promised us at least one Empty child: " + RelOptUtil.toString(union);
+ if (nonEmptyInputs == 0) {
builder.push(union).empty();
- break;
- case 1:
- builder.push(
- RelOptUtil.createCastRel(
- newInputs.get(0),
- union.getRowType(),
- true));
- break;
- default:
- builder.push(LogicalUnion.create(newInputs, union.all));
- break;
+ } else {
+ builder.union(union.all, nonEmptyInputs);
+ builder.convert(union.getRowType(), true);
}
call.transformTo(builder.build());
}
@@ -128,35 +121,27 @@ public abstract class PruneEmptyRules {
"Minus") {
public void onMatch(RelOptRuleCall call) {
final LogicalMinus minus = call.rel(0);
- final List<RelNode> inputs = call.getChildRels(minus);
+ final List<RelNode> inputs = minus.getInputs();
assert inputs != null;
- final List<RelNode> newInputs = new ArrayList<>();
+ int nonEmptyInputs = 0;
+ final RelBuilder builder = call.builder();
for (RelNode input : inputs) {
if (!isEmpty(input)) {
- newInputs.add(input);
- } else if (newInputs.isEmpty()) {
+ builder.push(input);
+ nonEmptyInputs++;
+ } else if (nonEmptyInputs == 0) {
// If the first input of Minus is empty, the whole thing is
// empty.
break;
}
}
- assert newInputs.size() < inputs.size()
- : "planner promised us at least one Empty child";
- final RelBuilder builder = call.builder();
- switch (newInputs.size()) {
- case 0:
+ assert nonEmptyInputs < inputs.size()
+ : "planner promised us at least one Empty child: " + RelOptUtil.toString(minus);
+ if (nonEmptyInputs == 0) {
builder.push(minus).empty();
- break;
- case 1:
- builder.push(
- RelOptUtil.createCastRel(
- newInputs.get(0),
- minus.getRowType(),
- true));
- break;
- default:
- builder.push(LogicalMinus.create(newInputs, minus.all));
- break;
+ } else {
+ builder.minus(minus.all, nonEmptyInputs);
+ builder.convert(minus.getRowType(), true);
}
call.transformTo(builder.build());
}
@@ -189,8 +174,24 @@ public abstract class PruneEmptyRules {
};
private static boolean isEmpty(RelNode node) {
- return node instanceof Values
- && ((Values) node).getTuples().isEmpty();
+ if (node instanceof Values) {
+ return ((Values) node).getTuples().isEmpty();
+ }
+ if (node instanceof HepRelVertex) {
+ return isEmpty(((HepRelVertex) node).getCurrentRel());
+ }
+ // Note: relation input might be a RelSubset, so we just iterate over the relations
+ // in order to check if the subset is equivalent to an empty relation.
+ if (!(node instanceof RelSubset)) {
+ return false;
+ }
+ RelSubset subset = (RelSubset) node;
+ for (RelNode rel : subset.getRels()) {
+ if (isEmpty(rel)) {
+ return true;
+ }
+ }
+ return false;
}
/**
diff --git a/core/src/test/java/org/apache/calcite/plan/volcano/VolcanoPlannerTest.java b/core/src/test/java/org/apache/calcite/plan/volcano/VolcanoPlannerTest.java
index 959073d..d2349d7 100644
--- a/core/src/test/java/org/apache/calcite/plan/volcano/VolcanoPlannerTest.java
+++ b/core/src/test/java/org/apache/calcite/plan/volcano/VolcanoPlannerTest.java
@@ -155,7 +155,6 @@ public class VolcanoPlannerTest {
equalTo(
sort(
"NoneSingleRel:Subset#0.NONE",
- "PhysSingleRel:Subset#0.NONE",
"PhysSingleRel:Subset#0.PHYS")));
}
diff --git a/core/src/test/java/org/apache/calcite/rel/rules/SortRemoveRuleTest.java b/core/src/test/java/org/apache/calcite/rel/rules/SortRemoveRuleTest.java
index 00778b9..7500ba0 100644
--- a/core/src/test/java/org/apache/calcite/rel/rules/SortRemoveRuleTest.java
+++ b/core/src/test/java/org/apache/calcite/rel/rules/SortRemoveRuleTest.java
@@ -73,8 +73,7 @@ public final class SortRemoveRuleTest {
RelRoot planRoot = planner.rel(validate);
RelNode planBefore = planRoot.rel;
RelTraitSet desiredTraits = planBefore.getTraitSet()
- .replace(EnumerableConvention.INSTANCE)
- .replace(planRoot.collation).simplify();
+ .replace(EnumerableConvention.INSTANCE);
RelNode planAfter = planner.transform(0, desiredTraits, planBefore);
return planner.transform(1, desiredTraits, planAfter);
}
diff --git a/core/src/test/java/org/apache/calcite/tools/PlannerTest.java b/core/src/test/java/org/apache/calcite/tools/PlannerTest.java
index 802756a..4e73edd 100644
--- a/core/src/test/java/org/apache/calcite/tools/PlannerTest.java
+++ b/core/src/test/java/org/apache/calcite/tools/PlannerTest.java
@@ -49,9 +49,12 @@ import org.apache.calcite.rel.metadata.RelMetadataQuery;
import org.apache.calcite.rel.rules.FilterMergeRule;
import org.apache.calcite.rel.rules.ProjectMergeRule;
import org.apache.calcite.rel.rules.ProjectToWindowRule;
+import org.apache.calcite.rel.rules.PruneEmptyRules;
import org.apache.calcite.rel.rules.SortJoinTransposeRule;
import org.apache.calcite.rel.rules.SortProjectTransposeRule;
import org.apache.calcite.rel.rules.SortRemoveRule;
+import org.apache.calcite.rel.rules.UnionMergeRule;
+import org.apache.calcite.rel.rules.ValuesReduceRule;
import org.apache.calcite.rel.type.RelDataType;
import org.apache.calcite.rel.type.RelDataTypeFactory;
import org.apache.calcite.schema.SchemaPlus;
@@ -75,6 +78,7 @@ import org.apache.calcite.sql.util.ListSqlOperatorTable;
import org.apache.calcite.sql.validate.SqlValidator;
import org.apache.calcite.sql.validate.SqlValidatorScope;
import org.apache.calcite.test.CalciteAssert;
+import org.apache.calcite.test.RelBuilderTest;
import org.apache.calcite.util.Optionality;
import org.apache.calcite.util.Util;
@@ -82,6 +86,7 @@ import com.google.common.base.Throwables;
import com.google.common.collect.ImmutableList;
import org.hamcrest.Matcher;
+import org.junit.Ignore;
import org.junit.Test;
import java.util.ArrayList;
@@ -372,6 +377,148 @@ public class PlannerTest {
+ " EnumerableTableScan(table=[[hr, emps]])\n"));
}
+ /** Unit test that parses, validates, converts and plans. */
+ @Test public void trimEmptyUnion2() throws Exception {
+ checkUnionPruning("values(1) union all select * from (values(2)) where false",
+ "EnumerableValues(type=[RecordType(INTEGER EXPR$0)], tuples=[[{ 1 }]])\n");
+
+ checkUnionPruning("select * from (values(2)) where false union all values(1)",
+ "EnumerableValues(type=[RecordType(INTEGER EXPR$0)], tuples=[[{ 1 }]])\n");
+ }
+
+ @Test public void trimEmptyUnion31() throws Exception {
+ emptyUnions31();
+ }
+
+ @Test public void trimEmptyUnion31withUnionMerge() throws Exception {
+ emptyUnions31(UnionMergeRule.INSTANCE);
+ }
+
+ private void emptyUnions31(UnionMergeRule... extraRules)
+ throws SqlParseException, ValidationException, RelConversionException {
+ String plan = "EnumerableValues(type=[RecordType(INTEGER EXPR$0)], tuples=[[{ 1 }]])\n";
+ checkUnionPruning("values(1)"
+ + " union all select * from (values(2)) where false"
+ + " union all select * from (values(3)) where false",
+ plan, extraRules);
+
+ checkUnionPruning("select * from (values(2)) where false"
+ + " union all values(1)"
+ + " union all select * from (values(3)) where false",
+ plan, extraRules);
+
+ checkUnionPruning("select * from (values(2)) where false"
+ + " union all select * from (values(3)) where false"
+ + " union all values(1)",
+ plan, extraRules);
+ }
+
+ @Ignore("[CALCITE-2773] java.lang.AssertionError: rel"
+ + " [rel#69:EnumerableUnion.ENUMERABLE.[](input#0=RelSubset#78,input#1=RelSubset#71,all=true)]"
+ + " has lower cost {4.0 rows, 4.0 cpu, 0.0 io} than best cost {5.0 rows, 5.0 cpu, 0.0 io}"
+ + " of subset [rel#67:Subset#6.ENUMERABLE.[]]")
+ @Test public void trimEmptyUnion32() throws Exception {
+ emptyUnions32();
+ }
+
+ @Test public void trimEmptyUnion32withUnionMerge() throws Exception {
+ emptyUnions32(UnionMergeRule.INSTANCE);
+ }
+
+ private void emptyUnions32(UnionMergeRule... extraRules)
+ throws SqlParseException, ValidationException, RelConversionException {
+ String plan = "EnumerableUnion(all=[true])\n"
+ + " EnumerableValues(type=[RecordType(INTEGER EXPR$0)], tuples=[[{ 1 }]])\n"
+ + " EnumerableValues(type=[RecordType(INTEGER EXPR$0)], tuples=[[{ 2 }]])\n";
+
+ checkUnionPruning("values(1)"
+ + " union all values(2)"
+ + " union all select * from (values(3)) where false",
+ plan, extraRules);
+
+ checkUnionPruning("values(1)"
+ + " union all select * from (values(3)) where false"
+ + " union all values(2)",
+ plan, extraRules);
+
+ checkUnionPruning("select * from (values(2)) where false"
+ + " union all values(1)"
+ + " union all values(2)",
+ plan, extraRules);
+ }
+
+ private void checkUnionPruning(String sql, String plan, RelOptRule... extraRules)
+ throws SqlParseException, ValidationException, RelConversionException {
+ ImmutableList.Builder<RelOptRule> rules = ImmutableList.<RelOptRule>builder().add(
+ PruneEmptyRules.UNION_INSTANCE,
+ ValuesReduceRule.PROJECT_FILTER_INSTANCE,
+ EnumerableRules.ENUMERABLE_PROJECT_RULE,
+ EnumerableRules.ENUMERABLE_FILTER_RULE,
+ EnumerableRules.ENUMERABLE_VALUES_RULE,
+ EnumerableRules.ENUMERABLE_UNION_RULE
+ );
+ rules.add(extraRules);
+ Program program = Programs.ofRules(rules.build());
+ Planner planner = getPlanner(null, program);
+ SqlNode parse = planner.parse(sql);
+ SqlNode validate = planner.validate(parse);
+ RelNode convert = planner.rel(validate).project();
+ RelTraitSet traitSet = convert.getTraitSet()
+ .replace(EnumerableConvention.INSTANCE);
+ RelNode transform = planner.transform(0, traitSet, convert);
+ assertThat("Empty values should be removed from " + sql,
+ toString(transform), equalTo(plan));
+ }
+
+ @Ignore("[CALCITE-2773] java.lang.AssertionError: rel"
+ + " [rel#17:EnumerableUnion.ENUMERABLE.[](input#0=RelSubset#26,input#1=RelSubset#19,all=true)]"
+ + " has lower cost {4.0 rows, 4.0 cpu, 0.0 io}"
+ + " than best cost {5.0 rows, 5.0 cpu, 0.0 io} of subset [rel#15:Subset#5.ENUMERABLE.[]]")
+ @Test public void trimEmptyUnion32viaRelBuidler() throws Exception {
+ RelBuilder relBuilder = RelBuilder.create(RelBuilderTest.config().build());
+
+ // This somehow blows up (see trimEmptyUnion32, the second case)
+ // (values(1) union all select * from (values(3)) where false)
+ // union all values(2)
+
+ // Non-trivial filter is important for the test to fail
+ RelNode relNode = relBuilder
+ .values(new String[]{"x"}, "1")
+ .values(new String[]{"x"}, "3")
+ .filter(relBuilder.equals(relBuilder.field("x"), relBuilder.literal("30")))
+ .union(true)
+ .values(new String[]{"x"}, "2")
+ .union(true)
+ .build();
+
+ RelOptPlanner planner = relNode.getCluster().getPlanner();
+ RuleSet ruleSet =
+ RuleSets.ofList(
+ PruneEmptyRules.UNION_INSTANCE,
+ ValuesReduceRule.FILTER_INSTANCE,
+ EnumerableRules.ENUMERABLE_PROJECT_RULE,
+ EnumerableRules.ENUMERABLE_FILTER_RULE,
+ EnumerableRules.ENUMERABLE_VALUES_RULE,
+ EnumerableRules.ENUMERABLE_UNION_RULE);
+ Program program = Programs.of(ruleSet);
+
+ RelTraitSet toTraits = relNode.getTraitSet()
+ .replace(EnumerableConvention.INSTANCE);
+
+ RelNode output = program.run(planner, relNode, toTraits,
+ ImmutableList.of(), ImmutableList.of());
+
+ // Expected outcomes are:
+ // 1) relation is optimized to simple VALUES
+ // 2) the number of rule invocations is reasonable
+ // 3) planner does not throw OutOfMemoryError
+ assertThat("empty union should be pruned out of " + toString(relNode),
+ Util.toLinux(toString(output)),
+ equalTo("EnumerableUnion(all=[true])\n"
+ + " EnumerableValues(type=[RecordType(INTEGER EXPR$0)], tuples=[[{ 1 }]])\n"
+ + " EnumerableValues(type=[RecordType(INTEGER EXPR$0)], tuples=[[{ 2 }]])\n"));
+ }
+
/** Unit test that parses, validates, converts and
* plans for query using order by */
@Test public void testSortPlan() throws Exception {