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 2015/10/22 02:43:27 UTC
[3/3] incubator-calcite git commit: [CALCITE-925] Match materialized
views when predicates contain strings and ranges (Amogh Margoor)
[CALCITE-925] Match materialized views when predicates contain strings and ranges (Amogh Margoor)
Adding support for solving predicates specifying ranges in optimizing using Materialized Views.
Adding Logs to RexImplicationChecker
Adding support for Handling String for Partitions
Close apache/incubator-calcite#156
Project: http://git-wip-us.apache.org/repos/asf/incubator-calcite/repo
Commit: http://git-wip-us.apache.org/repos/asf/incubator-calcite/commit/9db3b023
Tree: http://git-wip-us.apache.org/repos/asf/incubator-calcite/tree/9db3b023
Diff: http://git-wip-us.apache.org/repos/asf/incubator-calcite/diff/9db3b023
Branch: refs/heads/master
Commit: 9db3b023d003b44b005cff5013ffe1ef4f00f221
Parents: 56a612a
Author: Amogh Margoor <am...@qubole.com>
Authored: Fri Oct 16 05:32:22 2015 -0400
Committer: Julian Hyde <jh...@apache.org>
Committed: Wed Oct 21 14:34:15 2015 -0700
----------------------------------------------------------------------
.../calcite/plan/RexImplicationChecker.java | 176 ++++++++++++++-----
.../apache/calcite/plan/VisitorDataContext.java | 27 ++-
.../calcite/test/RexImplicationCheckerTest.java | 51 ++++++
3 files changed, 208 insertions(+), 46 deletions(-)
----------------------------------------------------------------------
http://git-wip-us.apache.org/repos/asf/incubator-calcite/blob/9db3b023/core/src/main/java/org/apache/calcite/plan/RexImplicationChecker.java
----------------------------------------------------------------------
diff --git a/core/src/main/java/org/apache/calcite/plan/RexImplicationChecker.java b/core/src/main/java/org/apache/calcite/plan/RexImplicationChecker.java
index 42c7b43..0ce82a4 100644
--- a/core/src/main/java/org/apache/calcite/plan/RexImplicationChecker.java
+++ b/core/src/main/java/org/apache/calcite/plan/RexImplicationChecker.java
@@ -30,13 +30,18 @@ import org.apache.calcite.sql.SqlKind;
import org.apache.calcite.sql.SqlOperator;
import org.apache.calcite.sql.fun.SqlCastFunction;
import org.apache.calcite.util.Pair;
+import org.apache.calcite.util.trace.CalciteLogger;
import com.google.common.collect.ImmutableList;
+import com.google.common.collect.ImmutableSet;
+import com.google.common.collect.Sets;
import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.Map;
+import java.util.Set;
+import java.util.logging.Logger;
/**
* Checks whether one condition logically implies another.
@@ -50,6 +55,9 @@ import java.util.Map;
* </ul>
*/
public class RexImplicationChecker {
+ private static final CalciteLogger LOGGER =
+ new CalciteLogger(Logger.getLogger(RexImplicationChecker.class.getName()));
+
final RexBuilder builder;
final RexExecutorImpl executor;
final RelDataType rowType;
@@ -81,6 +89,8 @@ public class RexImplicationChecker {
return false;
}
+ LOGGER.fine("Checking if " + first.toString() + " => " + second.toString());
+
RexCall firstCond = (RexCall) first;
RexCall secondCond = (RexCall) second;
@@ -130,11 +140,13 @@ public class RexImplicationChecker {
// If f could not imply even one conjunction in
// secondDnfs, then final implication may be false
if (!implyOneConjunction) {
+ LOGGER.fine(first + " doesnot imply " + second);
return false;
}
}
}
+ LOGGER.fine(first + " implies " + second);
return true;
}
@@ -148,28 +160,51 @@ public class RexImplicationChecker {
// Check Support
if (!checkSupport(firstUsageFinder, secondUsageFinder)) {
+ LOGGER.warning("Support for checking " + first
+ + " => " + second + " is not there");
return false;
}
- List<Pair<RexInputRef, RexNode>> usageList = new ArrayList<>();
+ ImmutableList.Builder<Set<Pair<RexInputRef, RexNode>>> usagesBuilder =
+ ImmutableList.builder();
for (Map.Entry<RexInputRef, InputRefUsage<SqlOperator, RexNode>> entry
: firstUsageFinder.usageMap.entrySet()) {
- final Pair<SqlOperator, RexNode> pair = entry.getValue().usageList.get(0);
- usageList.add(Pair.of(entry.getKey(), pair.getValue()));
+ ImmutableSet.Builder<Pair<RexInputRef, RexNode>> usageBuilder =
+ ImmutableSet.builder();
+ if (entry.getValue().usageList.size() > 0) {
+ for (final Pair<SqlOperator, RexNode> pair
+ : entry.getValue().usageList) {
+ usageBuilder.add(Pair.of(entry.getKey(), pair.getValue()));
+ }
+ usagesBuilder.add(usageBuilder.build());
+ }
}
- // Get the literals from first conjunction and executes second conjunction
- // using them.
- //
- // E.g., for
- // x > 30 ⇒ x > 10,
- // we will replace x by 30 in second expression and execute it i.e.,
- // 30 > 10
- //
- // If it's true then we infer implication.
- final DataContext dataValues =
- VisitorDataContext.of(rowType, usageList);
+ final Set<List<Pair<RexInputRef, RexNode>>> usages =
+ Sets.cartesianProduct(usagesBuilder.build());
+
+ for (List usageList : usages) {
+ // Get the literals from first conjunction and executes second conjunction
+ // using them.
+ //
+ // E.g., for
+ // x > 30 ⇒ x > 10,
+ // we will replace x by 30 in second expression and execute it i.e.,
+ // 30 > 10
+ //
+ // If it's true then we infer implication.
+ final DataContext dataValues =
+ VisitorDataContext.of(rowType, usageList);
+
+ if (!isSatisfiable(second, dataValues)) {
+ return false;
+ }
+ }
+ return true;
+ }
+
+ private boolean isSatisfiable(RexNode second, DataContext dataValues) {
if (dataValues == null) {
return false;
}
@@ -185,6 +220,7 @@ public class RexImplicationChecker {
} catch (Exception e) {
// TODO: CheckSupport should not allow this exception to be thrown
// Need to monitor it and handle all the cases raising them.
+ LOGGER.warning("Exception thrown while checking if => " + second + ": " + e.getMessage());
return false;
}
return result != null
@@ -215,6 +251,10 @@ public class RexImplicationChecker {
* <li>(=) X (>, >=, <, <=, =, !=)
* <li>(!=, =)
* </ul>
+ *
+ * <li>We support utmost 2 operators to be be used for a variable in first
+ * and second usages
+ *
* </ol>
*
* @return whether input usage pattern is supported
@@ -227,53 +267,101 @@ public class RexImplicationChecker {
secondUsageFinder.usageMap;
for (Map.Entry<RexInputRef, InputRefUsage<SqlOperator, RexNode>> entry
- : firstUsageMap.entrySet()) {
- if (entry.getValue().usageCount > 1) {
- return false;
- }
- }
-
- for (Map.Entry<RexInputRef, InputRefUsage<SqlOperator, RexNode>> entry
: secondUsageMap.entrySet()) {
final InputRefUsage<SqlOperator, RexNode> secondUsage = entry.getValue();
- if (secondUsage.usageCount > 1
- || secondUsage.usageList.size() != 1) {
+ final List<Pair<SqlOperator, RexNode>> secondUsageList = secondUsage.usageList;
+ final int secondLen = secondUsageList.size();
+
+ if (secondUsage.usageCount != secondLen || secondLen > 2) {
return false;
}
final InputRefUsage<SqlOperator, RexNode> firstUsage =
firstUsageMap.get(entry.getKey());
+
if (firstUsage == null
- || firstUsage.usageList.size() != 1) {
+ || firstUsage.usageList.size() != firstUsage.usageCount
+ || firstUsage.usageCount > 2) {
return false;
}
- final Pair<SqlOperator, RexNode> fUse = firstUsage.usageList.get(0);
- final Pair<SqlOperator, RexNode> sUse = secondUsage.usageList.get(0);
+ final List<Pair<SqlOperator, RexNode>> firstUsageList = firstUsage.usageList;
+ final int firstLen = firstUsageList.size();
- final SqlKind fKind = fUse.getKey().getKind();
+ final SqlKind fKind = firstUsageList.get(0).getKey().getKind();
+ final SqlKind sKind = secondUsageList.get(0).getKey().getKind();
+ final SqlKind fKind2 =
+ (firstUsageList.size() == 2) ? firstUsageList.get(1).getKey().getKind() : null;
+ final SqlKind sKind2 =
+ (secondUsageList.size() == 2) ? secondUsageList.get(1).getKey().getKind() : null;
- if (fKind != SqlKind.EQUALS) {
- switch (sUse.getKey().getKind()) {
- case GREATER_THAN:
- case GREATER_THAN_OR_EQUAL:
- if (!(fKind == SqlKind.GREATER_THAN)
- && !(fKind == SqlKind.GREATER_THAN_OR_EQUAL)) {
- return false;
- }
- break;
- case LESS_THAN:
- case LESS_THAN_OR_EQUAL:
- if (!(fKind == SqlKind.LESS_THAN)
- && !(fKind == SqlKind.LESS_THAN_OR_EQUAL)) {
- return false;
- }
- break;
- default:
+ if (firstLen == 2 && secondLen == 2
+ && !(isEquivalentOp(fKind, sKind) && isEquivalentOp(fKind2, sKind2))
+ && !(isEquivalentOp(fKind, sKind2) && isEquivalentOp(fKind2, sKind))) {
+ return false;
+ } else if (firstLen == 1 && secondLen == 1
+ && fKind != SqlKind.EQUALS && !isEquivalentOp(fKind, sKind)) {
+ return false;
+ } else if (firstLen == 1 && secondLen == 2 && fKind != SqlKind.EQUALS) {
+ return false;
+ } else if (firstLen == 2 && secondLen == 1) {
+ // Allow only cases like
+ // x < 30 and x < 40 implies x < 70
+ // x > 30 and x < 40 implies x < 70
+ // But disallow cases like
+ // x > 30 and x > 40 implies x < 70
+ if (!isOppositeOp(fKind, fKind2)
+ && !(isEquivalentOp(fKind, fKind2) && isEquivalentOp(fKind, sKind))) {
return false;
}
}
}
+
+ return true;
+ }
+
+ private boolean isEquivalentOp(SqlKind fKind, SqlKind sKind) {
+ switch (sKind) {
+ case GREATER_THAN:
+ case GREATER_THAN_OR_EQUAL:
+ if (!(fKind == SqlKind.GREATER_THAN)
+ && !(fKind == SqlKind.GREATER_THAN_OR_EQUAL)) {
+ return false;
+ }
+ break;
+ case LESS_THAN:
+ case LESS_THAN_OR_EQUAL:
+ if (!(fKind == SqlKind.LESS_THAN)
+ && !(fKind == SqlKind.LESS_THAN_OR_EQUAL)) {
+ return false;
+ }
+ break;
+ default:
+ return false;
+ }
+
+ return true;
+ }
+
+ private boolean isOppositeOp(SqlKind fKind, SqlKind sKind) {
+ switch (sKind) {
+ case GREATER_THAN:
+ case GREATER_THAN_OR_EQUAL:
+ if (!(fKind == SqlKind.LESS_THAN)
+ && !(fKind == SqlKind.LESS_THAN_OR_EQUAL)) {
+ return false;
+ }
+ break;
+ case LESS_THAN:
+ case LESS_THAN_OR_EQUAL:
+ if (!(fKind == SqlKind.GREATER_THAN)
+ && !(fKind == SqlKind.GREATER_THAN_OR_EQUAL)) {
+ return false;
+ }
+ break;
+ default:
+ return false;
+ }
return true;
}
http://git-wip-us.apache.org/repos/asf/incubator-calcite/blob/9db3b023/core/src/main/java/org/apache/calcite/plan/VisitorDataContext.java
----------------------------------------------------------------------
diff --git a/core/src/main/java/org/apache/calcite/plan/VisitorDataContext.java b/core/src/main/java/org/apache/calcite/plan/VisitorDataContext.java
index c0fe8a8..2d43389 100644
--- a/core/src/main/java/org/apache/calcite/plan/VisitorDataContext.java
+++ b/core/src/main/java/org/apache/calcite/plan/VisitorDataContext.java
@@ -32,16 +32,21 @@ import org.apache.calcite.sql.SqlOperator;
import org.apache.calcite.sql.fun.SqlCastFunction;
import org.apache.calcite.util.NlsString;
import org.apache.calcite.util.Pair;
+import org.apache.calcite.util.trace.CalciteLogger;
import java.math.BigDecimal;
import java.sql.Date;
import java.util.Calendar;
import java.util.List;
+import java.util.logging.Logger;
/**
* DataContext for evaluating an RexExpression
*/
public class VisitorDataContext implements DataContext {
+ private static final CalciteLogger LOGGER =
+ new CalciteLogger(Logger.getLogger(VisitorDataContext.class.getName()));
+
private final Object[] values;
public VisitorDataContext(Object[] values) {
@@ -94,6 +99,8 @@ public class VisitorDataContext implements DataContext {
for (Pair<RexInputRef, RexNode> elem : usageList) {
Pair<Integer, ?> value = getValue(elem.getKey(), elem.getValue());
if (value == null) {
+ LOGGER.warning(elem.getKey() + " is not handled for " + elem.getValue()
+ + " for checking implication");
return null;
}
int index = value.getKey();
@@ -112,6 +119,11 @@ public class VisitorDataContext implements DataContext {
Object value = ((RexLiteral) literal).getValue();
final RelDataType type = inputRef.getType();
+ if (type.getSqlTypeName() == null) {
+ LOGGER.warning(inputRef.toString() + " returned null SqlTypeName");
+ return null;
+ }
+
switch (type.getSqlTypeName()) {
case INTEGER:
if (value instanceof BigDecimal) {
@@ -156,9 +168,20 @@ public class VisitorDataContext implements DataContext {
final NlsString nl = (NlsString) value;
return Pair.of(index, nl.getValue().charAt(0));
}
+ case VARCHAR:
+ if (value instanceof NlsString) {
+ // TODO: Support coallation. Not supported in {@link #NlsString} compare too.
+ return Pair.of(index, ((NlsString) value).getValue());
+ }
default:
- // TODO: Support few more supported cases
- return Pair.of(index, value);
+ //TODO: Support few more supported cases
+ LOGGER.warning(type.getSqlTypeName() + " for value of class " + value.getClass()
+ + " is being handled in default way");
+ if (value instanceof NlsString) {
+ return Pair.of(index, ((NlsString) value).getValue());
+ } else {
+ return Pair.of(index, value);
+ }
}
}
http://git-wip-us.apache.org/repos/asf/incubator-calcite/blob/9db3b023/core/src/test/java/org/apache/calcite/test/RexImplicationCheckerTest.java
----------------------------------------------------------------------
diff --git a/core/src/test/java/org/apache/calcite/test/RexImplicationCheckerTest.java b/core/src/test/java/org/apache/calcite/test/RexImplicationCheckerTest.java
index 720798e..f55628f 100644
--- a/core/src/test/java/org/apache/calcite/test/RexImplicationCheckerTest.java
+++ b/core/src/test/java/org/apache/calcite/test/RexImplicationCheckerTest.java
@@ -164,6 +164,13 @@ public class RexImplicationCheckerTest {
f.checkNotImplies(node2, node1);
}
+ @Test public void testSimpleString() {
+ final Fixture f = new Fixture();
+ final RexNode node1 = f.eq(f.str, f.rexBuilder.makeLiteral("en"));
+
+ f.checkImplies(node1, node1);
+ }
+
@Ignore("work in progress")
@Test public void testSimpleDate() {
final Fixture f = new Fixture();
@@ -197,6 +204,41 @@ public class RexImplicationCheckerTest {
f.checkNotImplies(node2, node1);
}
+ @Test public void testSimpleBetween() {
+ final Fixture f = new Fixture();
+ final RexNode node1 = f.ge(f.i, f.literal(30));
+ final RexNode node2 = f.lt(f.i, f.literal(70));
+ final RexNode node3 = f.and(node1, node2);
+ final RexNode node4 = f.ge(f.i, f.literal(50));
+ final RexNode node5 = f.lt(f.i, f.literal(60));
+ final RexNode node6 = f.and(node4, node5);
+
+ f.checkNotImplies(node3, node4);
+ f.checkNotImplies(node3, node5);
+ f.checkNotImplies(node3, node6);
+ f.checkNotImplies(node1, node6);
+ f.checkNotImplies(node2, node6);
+ f.checkImplies(node6, node3);
+ f.checkImplies(node6, node2);
+ f.checkImplies(node6, node1);
+ }
+
+ @Test public void testSimpleBetweenCornerCases() {
+ final Fixture f = new Fixture();
+ final RexNode node1 = f.gt(f.i, f.literal(30));
+ final RexNode node2 = f.gt(f.i, f.literal(50));
+ final RexNode node3 = f.lt(f.i, f.literal(60));
+ final RexNode node4 = f.lt(f.i, f.literal(80));
+ final RexNode node5 = f.lt(f.i, f.literal(90));
+ final RexNode node6 = f.lt(f.i, f.literal(100));
+
+ f.checkNotImplies(f.and(node1, node2), f.and(node3, node4));
+ f.checkNotImplies(f.and(node5, node6), f.and(node3, node4));
+ f.checkNotImplies(f.and(node1, node2), node6);
+ f.checkNotImplies(node6, f.and(node1, node2));
+ f.checkImplies(f.and(node3, node4), f.and(node5, node6));
+ }
+
/** Contains all the nourishment a test case could possibly need.
*
* <p>We put the data in here, rather than as fields in the test case, so that
@@ -215,6 +257,7 @@ public class RexImplicationCheckerTest {
private final RexNode ch;
private final RexNode ts;
private final RexNode t;
+ private final RexNode str;
private final RelDataType boolRelDataType;
private final RelDataType intRelDataType;
@@ -227,6 +270,7 @@ public class RexImplicationCheckerTest {
private final RelDataType dateDataType;
private final RelDataType timeStampDataType;
private final RelDataType timeDataType;
+ private final RelDataType stringDataType;
private final RelDataTypeFactory typeFactory;
private final RexImplicationChecker checker;
private final RelDataType rowType;
@@ -246,6 +290,7 @@ public class RexImplicationCheckerTest {
dateDataType = typeFactory.createJavaType(Date.class);
timeStampDataType = typeFactory.createJavaType(Timestamp.class);
timeDataType = typeFactory.createJavaType(Time.class);
+ stringDataType = typeFactory.createJavaType(String.class);
bl = ref(0, this.boolRelDataType);
i = ref(1, intRelDataType);
@@ -258,6 +303,7 @@ public class RexImplicationCheckerTest {
dt = ref(8, dateDataType);
ts = ref(9, timeStampDataType);
t = ref(10, timeDataType);
+ str = ref(11, stringDataType);
rowType = typeFactory.builder()
.add("bool", this.boolRelDataType)
@@ -271,6 +317,7 @@ public class RexImplicationCheckerTest {
.add("date", dateDataType)
.add("timestamp", timeStampDataType)
.add("time", timeDataType)
+ .add("string", stringDataType)
.build();
final Holder<RexExecutorImpl> holder = Holder.of(null);
@@ -326,6 +373,10 @@ public class RexImplicationCheckerTest {
node2);
}
+ RexNode and(RexNode node1, RexNode node2) {
+ return rexBuilder.makeCall(SqlStdOperatorTable.AND, node1, node2);
+ }
+
RexNode longLiteral(long value) {
return rexBuilder.makeLiteral(value, longRelDataType, true);
}