You are viewing a plain text version of this content. The canonical link for it is here.
Posted to commits@calcite.apache.org by jh...@apache.org on 2016/01/23 01:31:04 UTC
[46/50] [abbrv] calcite git commit: [CALCITE-1056] In RelBuilder,
simplify predicates, and optimize away WHERE FALSE
[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 <jh...@apache.org>
Authored: Wed Jan 13 16:07:01 2016 -0800
Committer: Julian Hyde <jh...@apache.org>
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)");