[CALCITE-1056] In RelBuilder, simplify predicates, and optimize away WHERE FALSE
Project: http://git-wip-us.apache.org/repos/asf/calcite/repo Commit: http://git-wip-us.apache.org/repos/asf/calcite/commit/ee52f691 Tree: http://git-wip-us.apache.org/repos/asf/calcite/tree/ee52f691 Diff: http://git-wip-us.apache.org/repos/asf/calcite/diff/ee52f691 Branch: refs/remotes/julianhyde/master Commit: ee52f691b844d97919a8c0ca211a7c78b86165ef Parents: 6201013 Author: Julian Hyde <[email protected]> Authored: Wed Jan 13 16:07:01 2016 -0800 Committer: Julian Hyde <[email protected]> Committed: Thu Jan 21 15:03:41 2016 -0800 ---------------------------------------------------------------------- .../org/apache/calcite/plan/RelOptUtil.java | 32 +++++++--- .../java/org/apache/calcite/rex/RexUtil.java | 61 +++++++++++++------- .../org/apache/calcite/tools/RelBuilder.java | 21 ++++--- .../calcite/test/MaterializationTest.java | 2 +- .../org/apache/calcite/test/RelBuilderTest.java | 58 +++++++++++++++++-- .../org/apache/calcite/test/RexProgramTest.java | 20 +++++++ 6 files changed, 150 insertions(+), 44 deletions(-) ---------------------------------------------------------------------- http://git-wip-us.apache.org/repos/asf/calcite/blob/ee52f691/core/src/main/java/org/apache/calcite/plan/RelOptUtil.java ---------------------------------------------------------------------- diff --git a/core/src/main/java/org/apache/calcite/plan/RelOptUtil.java b/core/src/main/java/org/apache/calcite/plan/RelOptUtil.java index eeaea21..610867a 100644 --- a/core/src/main/java/org/apache/calcite/plan/RelOptUtil.java +++ b/core/src/main/java/org/apache/calcite/plan/RelOptUtil.java @@ -678,15 +678,11 @@ public abstract class RelOptUtil { RexUtil.generateCastExpressions(rexBuilder, castRowType, rowType); if (rename) { // Use names and types from castRowType. - return projectFactory.createProject( - rel, - castExps, + return projectFactory.createProject(rel, castExps, castRowType.getFieldNames()); } else { // Use names from rowType, types from castRowType. - return projectFactory.createProject( - rel, - castExps, + return projectFactory.createProject(rel, castExps, rowType.getFieldNames()); } } @@ -1928,8 +1924,30 @@ public abstract class RelOptUtil { if (e.isAlwaysFalse()) { return; } - notList.add(e); + switch (e.getKind()) { + case OR: + final List<RexNode> ors = new ArrayList<>(); + decomposeDisjunction(e, ors); + for (RexNode or : ors) { + switch (or.getKind()) { + case NOT: + rexList.add(((RexCall) or).operands.get(0)); + break; + default: + notList.add(or); + } + } + break; + default: + notList.add(e); + } break; + case LITERAL: + if (!RexLiteral.isNullLiteral(rexPredicate) + && RexLiteral.booleanValue(rexPredicate)) { + return; // ignore TRUE + } + // fall through default: rexList.add(rexPredicate); break; http://git-wip-us.apache.org/repos/asf/calcite/blob/ee52f691/core/src/main/java/org/apache/calcite/rex/RexUtil.java ---------------------------------------------------------------------- diff --git a/core/src/main/java/org/apache/calcite/rex/RexUtil.java b/core/src/main/java/org/apache/calcite/rex/RexUtil.java index b766590..ce3e936 100644 --- a/core/src/main/java/org/apache/calcite/rex/RexUtil.java +++ b/core/src/main/java/org/apache/calcite/rex/RexUtil.java @@ -1308,6 +1308,19 @@ public class RexUtil { } } + /** + * Simplifies a conjunction of boolean expressions. + */ + public static RexNode simplifyAnds(RexBuilder rexBuilder, + Iterable<? extends RexNode> nodes) { + final List<RexNode> terms = new ArrayList<>(); + final List<RexNode> notTerms = new ArrayList<>(); + for (RexNode e : nodes) { + RelOptUtil.decomposeConjunction(e, terms, notTerms); + } + return simplifyAnd2(rexBuilder, terms, notTerms); + } + private static RexNode simplifyNot(RexBuilder rexBuilder, RexCall call) { final RexNode a = call.getOperands().get(0); switch (a.getKind()) { @@ -1324,6 +1337,17 @@ public class RexUtil { return call; } + /** Negates a logical expression by adding or removing a NOT. */ + public static RexNode not(RexNode e) { + switch (e.getKind()) { + case NOT: + return ((RexCall) e).getOperands().get(0); + default: + return new RexCall(e.getType(), SqlStdOperatorTable.NOT, + ImmutableList.of(e)); + } + } + private static RexNode simplifyIs(RexBuilder rexBuilder, RexCall call) { final SqlKind kind = call.getKind(); final RexNode a = call.getOperands().get(0); @@ -1461,31 +1485,24 @@ public class RexUtil { } public static RexNode simplifyAnd(RexBuilder rexBuilder, RexCall e) { - final List<RexNode> terms = RelOptUtil.conjunctions(e); + final List<RexNode> terms = new ArrayList<>(); final List<RexNode> notTerms = new ArrayList<>(); - for (int i = 0; i < terms.size(); i++) { - final RexNode term = terms.get(i); - switch (term.getKind()) { - case NOT: - notTerms.add( - ((RexCall) term).getOperands().get(0)); - terms.remove(i); - --i; - break; - case LITERAL: - if (!RexLiteral.isNullLiteral(term)) { - if (!RexLiteral.booleanValue(term)) { - return term; // false - } else { - terms.remove(i); - --i; - } - } - } + RelOptUtil.decomposeConjunction(e, terms, notTerms); + return simplifyAnd2(rexBuilder, terms, notTerms); + } + + public static RexNode simplifyAnd2(RexBuilder rexBuilder, + List<RexNode> terms, List<RexNode> notTerms) { + if (terms.contains(rexBuilder.makeLiteral(false))) { + return rexBuilder.makeLiteral(false); } if (terms.isEmpty() && notTerms.isEmpty()) { return rexBuilder.makeLiteral(true); } + if (terms.size() == 1 && notTerms.isEmpty()) { + // Make sure "x OR y OR x" (a single-term conjunction) gets simplified. + return simplify(rexBuilder, terms.get(0)); + } // If one of the not-disjunctions is a disjunction that is wholly // contained in the disjunctions list, the expression is not // satisfiable. @@ -1502,8 +1519,8 @@ public class RexUtil { // Add the NOT disjunctions back in. for (RexNode notDisjunction : notTerms) { terms.add( - rexBuilder.makeCall( - SqlStdOperatorTable.NOT, notDisjunction)); + simplify(rexBuilder, + rexBuilder.makeCall(SqlStdOperatorTable.NOT, notDisjunction))); } return composeConjunction(rexBuilder, terms, false); } http://git-wip-us.apache.org/repos/asf/calcite/blob/ee52f691/core/src/main/java/org/apache/calcite/tools/RelBuilder.java ---------------------------------------------------------------------- diff --git a/core/src/main/java/org/apache/calcite/tools/RelBuilder.java b/core/src/main/java/org/apache/calcite/tools/RelBuilder.java index cf9fcb6..32d3b6b 100644 --- a/core/src/main/java/org/apache/calcite/tools/RelBuilder.java +++ b/core/src/main/java/org/apache/calcite/tools/RelBuilder.java @@ -452,9 +452,13 @@ public class RelBuilder { return and(ImmutableList.copyOf(operands)); } - /** Creates an AND. */ + /** Creates an AND. + * + * <p>Simplifies the expression a little: + * {@code e AND TRUE} becomes {@code e}; + * {@code e AND e2 AND NOT e} becomes {@code e2}. */ public RexNode and(Iterable<? extends RexNode> operands) { - return RexUtil.composeConjunction(cluster.getRexBuilder(), operands, false); + return RexUtil.simplifyAnds(cluster.getRexBuilder(), operands); } /** Creates an OR. */ @@ -692,8 +696,10 @@ public class RelBuilder { * and optimized in a similar way to the {@link #and} method. * If the result is TRUE no filter is created. */ public RelBuilder filter(Iterable<? extends RexNode> predicates) { - final RexNode x = RexUtil.simplify(cluster.getRexBuilder(), - RexUtil.composeConjunction(cluster.getRexBuilder(), predicates, false)); + final RexNode x = RexUtil.simplifyAnds(cluster.getRexBuilder(), predicates); + if (x.isAlwaysFalse()) { + return empty(); + } if (!x.isAlwaysTrue()) { final Frame frame = Stacks.pop(stack); final RelNode filter = filterFactory.createFilter(frame.rel, x); @@ -991,8 +997,7 @@ public class RelBuilder { * conditions. */ public RelBuilder join(JoinRelType joinType, Iterable<? extends RexNode> conditions) { - return join(joinType, - RexUtil.composeConjunction(cluster.getRexBuilder(), conditions, false), + return join(joinType, and(conditions), ImmutableSet.<CorrelationId>of()); } @@ -1057,9 +1062,7 @@ public class RelBuilder { final Frame right = Stacks.pop(stack); final Frame left = Stacks.pop(stack); final RelNode semiJoin = - semiJoinFactory.createSemiJoin(left.rel, right.rel, - RexUtil.composeConjunction(cluster.getRexBuilder(), conditions, - false)); + semiJoinFactory.createSemiJoin(left.rel, right.rel, and(conditions)); Stacks.push(stack, new Frame(semiJoin, left.right)); return this; } http://git-wip-us.apache.org/repos/asf/calcite/blob/ee52f691/core/src/test/java/org/apache/calcite/test/MaterializationTest.java ---------------------------------------------------------------------- diff --git a/core/src/test/java/org/apache/calcite/test/MaterializationTest.java b/core/src/test/java/org/apache/calcite/test/MaterializationTest.java index 05726b3..389d3ec 100644 --- a/core/src/test/java/org/apache/calcite/test/MaterializationTest.java +++ b/core/src/test/java/org/apache/calcite/test/MaterializationTest.java @@ -259,7 +259,7 @@ public class MaterializationTest { MaterializationService.setThreadLocal(); final String m = "select \"salary\", \"commission\",\n" + "\"deptno\", \"empid\", \"name\" from \"emps\""; - final String v = "select * from \"emps\" where \"salary\" is null"; + final String v = "select * from \"emps\" where \"name\" is null"; final String q = "select * from V where \"commission\" is null"; final JsonBuilder builder = new JsonBuilder(); final String model = "{\n" http://git-wip-us.apache.org/repos/asf/calcite/blob/ee52f691/core/src/test/java/org/apache/calcite/test/RelBuilderTest.java ---------------------------------------------------------------------- diff --git a/core/src/test/java/org/apache/calcite/test/RelBuilderTest.java b/core/src/test/java/org/apache/calcite/test/RelBuilderTest.java index db13a02..8a164c5 100644 --- a/core/src/test/java/org/apache/calcite/test/RelBuilderTest.java +++ b/core/src/test/java/org/apache/calcite/test/RelBuilderTest.java @@ -207,6 +207,10 @@ public class RelBuilderTest { // SELECT * // FROM emp // WHERE deptno = 20 OR deptno = 20 + // simplifies to + // SELECT * + // FROM emp + // WHERE deptno = 20 final RelBuilder builder = RelBuilder.create(config().build()); RelNode root = builder.scan("EMP") @@ -224,6 +228,45 @@ public class RelBuilderTest { + " LogicalTableScan(table=[[scott, EMP]])\n")); } + @Test public void testScanFilterAndFalse() { + // Equivalent SQL: + // SELECT * + // FROM emp + // WHERE deptno = 20 AND FALSE + // simplifies to + // VALUES + final RelBuilder builder = RelBuilder.create(config().build()); + RelNode root = + builder.scan("EMP") + .filter( + builder.call(SqlStdOperatorTable.GREATER_THAN, + builder.field("DEPTNO"), + builder.literal(20)), + builder.literal(false)) + .build(); + final String plan = "LogicalValues(tuples=[[]])\n"; + assertThat(str(root), is(plan)); + } + + @Test public void testScanFilterAndTrue() { + // Equivalent SQL: + // SELECT * + // FROM emp + // WHERE deptno = 20 AND TRUE + final RelBuilder builder = RelBuilder.create(config().build()); + RelNode root = + builder.scan("EMP") + .filter( + builder.call(SqlStdOperatorTable.GREATER_THAN, + builder.field("DEPTNO"), + builder.literal(20)), + builder.literal(true)) + .build(); + final String plan = "LogicalFilter(condition=[>($7, 20)])\n" + + " LogicalTableScan(table=[[scott, EMP]])\n"; + assertThat(str(root), is(plan)); + } + @Test public void testBadFieldName() { final RelBuilder builder = RelBuilder.create(config().build()); try { @@ -295,7 +338,7 @@ public class RelBuilderTest { builder.or( builder.equals(builder.field("DEPTNO"), builder.literal(20)), - builder.and(builder.literal(false), + builder.and(builder.literal(null), builder.equals(builder.field("DEPTNO"), builder.literal(10)), builder.and(builder.isNull(builder.field(6)), @@ -312,8 +355,8 @@ public class RelBuilderTest { .build(); assertThat(str(root), is("LogicalProject(DEPTNO=[$7], COMM=[CAST($6):SMALLINT NOT NULL]," - + " $f2=[OR(=($7, 20), AND(false, =($7, 10), IS NULL($6)," - + " NOT(IS NOT NULL($7))), =($7, 30))], n2=[IS NULL($2)]," + + " $f2=[OR(=($7, 20), AND(null, =($7, 10), IS NULL($6)," + + " IS NULL($7)), =($7, 30))], n2=[IS NULL($2)]," + " nn2=[IS NOT NULL($3)], $f5=[20], COMM6=[$6], C=[$6])\n" + " LogicalTableScan(table=[[scott, EMP]])\n")); } @@ -760,7 +803,9 @@ public class RelBuilderTest { // Equivalent SQL: // SELECT * // FROM emp - // LEFT JOIN dept ON emp.deptno = dept.deptno AND emp.empno = 123 + // LEFT JOIN dept ON emp.deptno = dept.deptno + // AND emp.empno = 123 + // AND dept.deptno IS NOT NULL final RelBuilder builder = RelBuilder.create(config().build()); RelNode root = builder.scan("EMP") @@ -771,8 +816,11 @@ public class RelBuilderTest { builder.field(2, 1, "DEPTNO")), builder.call(SqlStdOperatorTable.EQUALS, builder.field(2, 0, "EMPNO"), - builder.literal(123))) + builder.literal(123)), + builder.call(SqlStdOperatorTable.IS_NOT_NULL, + builder.field(2, 1, "DEPTNO"))) .build(); + // Note that "dept.deptno IS NOT NULL" has been simplified away. final String expected = "" + "LogicalJoin(condition=[AND(=($7, $0), =($0, 123))], joinType=[left])\n" + " LogicalTableScan(table=[[scott, EMP]])\n" http://git-wip-us.apache.org/repos/asf/calcite/blob/ee52f691/core/src/test/java/org/apache/calcite/test/RexProgramTest.java ---------------------------------------------------------------------- diff --git a/core/src/test/java/org/apache/calcite/test/RexProgramTest.java b/core/src/test/java/org/apache/calcite/test/RexProgramTest.java index 7b50427..1efb8cc 100644 --- a/core/src/test/java/org/apache/calcite/test/RexProgramTest.java +++ b/core/src/test/java/org/apache/calcite/test/RexProgramTest.java @@ -771,6 +771,26 @@ public class RexProgramTest { checkSimplify(and(aRef, bRef, false_), "false"); + // and: remove duplicate "not"s + checkSimplify(and(not(aRef), bRef, not(cRef), not(aRef)), + "AND(?0.b, NOT(?0.a), NOT(?0.c))"); + + // and: "not true" falsifies + checkSimplify(and(not(aRef), bRef, not(true_)), + "false"); + + // and: flatten and remove duplicates + checkSimplify( + and(aRef, and(and(bRef, not(cRef), dRef, not(eRef)), not(eRef))), + "AND(?0.a, ?0.b, ?0.d, NOT(?0.c), NOT(?0.e))"); + + // and: expand "... and not(or(x, y))" to "... and not(x) and not(y)" + checkSimplify(and(aRef, bRef, not(or(cRef, or(dRef, eRef)))), + "AND(?0.a, ?0.b, NOT(?0.c), NOT(?0.d), NOT(?0.e))"); + + checkSimplify(and(aRef, bRef, not(or(not(cRef), dRef, not(eRef)))), + "AND(?0.a, ?0.b, ?0.c, ?0.e, NOT(?0.d))"); + // or: remove duplicates checkSimplify(or(aRef, bRef, aRef), "OR(?0.a, ?0.b)");
