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 2017/03/04 21:03:22 UTC
[03/10] calcite git commit: [CALCITE-1656] Improve cost function in
DruidQuery to encourage early column pruning (Nishant Bangarwa)
[CALCITE-1656] Improve cost function in DruidQuery to encourage early column pruning (Nishant Bangarwa)
The cost function now includes:
* Number of fields being queried
* Type of DruidQuery generated
Close apache/calcite#382
Project: http://git-wip-us.apache.org/repos/asf/calcite/repo
Commit: http://git-wip-us.apache.org/repos/asf/calcite/commit/c90fddfb
Tree: http://git-wip-us.apache.org/repos/asf/calcite/tree/c90fddfb
Diff: http://git-wip-us.apache.org/repos/asf/calcite/diff/c90fddfb
Branch: refs/heads/master
Commit: c90fddfb1c600e6c870558778c50ebfbcd5f1799
Parents: 33f9d0f
Author: Nishant <ni...@gmail.com>
Authored: Fri Feb 24 21:40:42 2017 +0530
Committer: Julian Hyde <jh...@apache.org>
Committed: Fri Mar 3 10:13:36 2017 -0800
----------------------------------------------------------------------
.../apache/calcite/rel/metadata/RelMdUtil.java | 31 +++++++++++++++
.../apache/calcite/test/RelMetadataTest.java | 11 ++++++
.../calcite/adapter/druid/DruidQuery.java | 27 ++++++++++++-
.../org/apache/calcite/test/DruidAdapterIT.java | 41 +++++++++++++++++++-
4 files changed, 108 insertions(+), 2 deletions(-)
----------------------------------------------------------------------
http://git-wip-us.apache.org/repos/asf/calcite/blob/c90fddfb/core/src/main/java/org/apache/calcite/rel/metadata/RelMdUtil.java
----------------------------------------------------------------------
diff --git a/core/src/main/java/org/apache/calcite/rel/metadata/RelMdUtil.java b/core/src/main/java/org/apache/calcite/rel/metadata/RelMdUtil.java
index 089f551..7b63ac9 100644
--- a/core/src/main/java/org/apache/calcite/rel/metadata/RelMdUtil.java
+++ b/core/src/main/java/org/apache/calcite/rel/metadata/RelMdUtil.java
@@ -44,6 +44,7 @@ import org.apache.calcite.sql.type.ReturnTypes;
import org.apache.calcite.util.ImmutableBitSet;
import org.apache.calcite.util.NumberUtil;
+import com.google.common.base.Preconditions;
import com.google.common.collect.ImmutableList;
import java.math.BigDecimal;
@@ -719,6 +720,36 @@ public class RelMdUtil {
* mq.getSelectivity(child, condition);
}
+ /** Returns a point on a line.
+ *
+ * <p>The result is always a value between {@code minY} and {@code maxY},
+ * even if {@code x} is not between {@code minX} and {@code maxX}.
+ *
+ * <p>Examples:<ul>
+ * <li>{@code linear(0, 0, 10, 100, 200}} returns 100 because 0 is minX
+ * <li>{@code linear(5, 0, 10, 100, 200}} returns 150 because 5 is
+ * mid-way between minX and maxX
+ * <li>{@code linear(5, 0, 10, 100, 200}} returns 160
+ * <li>{@code linear(10, 0, 10, 100, 200}} returns 200 because 10 is maxX
+ * <li>{@code linear(-2, 0, 10, 100, 200}} returns 100 because -2 is
+ * less than minX and is therefore treated as minX
+ * <li>{@code linear(12, 0, 10, 100, 200}} returns 100 because 12 is
+ * greater than maxX and is therefore treated as maxX
+ * </ul>
+ */
+ public static double linear(int x, int minX, int maxX, double minY, double
+ maxY) {
+ Preconditions.checkArgument(minX < maxX);
+ Preconditions.checkArgument(minY < maxY);
+ if (x < minX) {
+ return minY;
+ }
+ if (x > maxX) {
+ return maxY;
+ }
+ return minY + (double) (x - minX) / (double) (maxX - minX) * (maxY - minY);
+ }
+
//~ Inner Classes ----------------------------------------------------------
/** Visitor that walks over a scalar expression and computes the
http://git-wip-us.apache.org/repos/asf/calcite/blob/c90fddfb/core/src/test/java/org/apache/calcite/test/RelMetadataTest.java
----------------------------------------------------------------------
diff --git a/core/src/test/java/org/apache/calcite/test/RelMetadataTest.java b/core/src/test/java/org/apache/calcite/test/RelMetadataTest.java
index 54e3b5e..234b666 100644
--- a/core/src/test/java/org/apache/calcite/test/RelMetadataTest.java
+++ b/core/src/test/java/org/apache/calcite/test/RelMetadataTest.java
@@ -60,6 +60,7 @@ import org.apache.calcite.rel.metadata.MetadataHandler;
import org.apache.calcite.rel.metadata.ReflectiveRelMetadataProvider;
import org.apache.calcite.rel.metadata.RelColumnOrigin;
import org.apache.calcite.rel.metadata.RelMdCollation;
+import org.apache.calcite.rel.metadata.RelMdUtil;
import org.apache.calcite.rel.metadata.RelMetadataProvider;
import org.apache.calcite.rel.metadata.RelMetadataQuery;
import org.apache.calcite.rel.type.RelDataType;
@@ -1470,6 +1471,16 @@ public class RelMetadataTest extends SqlToRelTestBase {
assertThat(d, is(dist));
}
+ /** Unit test for {@link RelMdUtil#linear(int, int, int, double, double)}. */
+ @Test public void testLinear() {
+ assertThat(RelMdUtil.linear(0, 0, 10, 100, 200), is(100d));
+ assertThat(RelMdUtil.linear(5, 0, 10, 100, 200), is(150d));
+ assertThat(RelMdUtil.linear(6, 0, 10, 100, 200), is(160d));
+ assertThat(RelMdUtil.linear(10, 0, 10, 100, 200), is(200d));
+ assertThat(RelMdUtil.linear(-2, 0, 10, 100, 200), is(100d));
+ assertThat(RelMdUtil.linear(12, 0, 10, 100, 200), is(200d));
+ }
+
/**
* Matcher that succeeds for any collection that, when converted to strings
* and sorted on those strings, matches the given reference string.
http://git-wip-us.apache.org/repos/asf/calcite/blob/c90fddfb/druid/src/main/java/org/apache/calcite/adapter/druid/DruidQuery.java
----------------------------------------------------------------------
diff --git a/druid/src/main/java/org/apache/calcite/adapter/druid/DruidQuery.java b/druid/src/main/java/org/apache/calcite/adapter/druid/DruidQuery.java
index b76652c..17ddd05 100644
--- a/druid/src/main/java/org/apache/calcite/adapter/druid/DruidQuery.java
+++ b/druid/src/main/java/org/apache/calcite/adapter/druid/DruidQuery.java
@@ -44,6 +44,7 @@ import org.apache.calcite.rel.core.Filter;
import org.apache.calcite.rel.core.Project;
import org.apache.calcite.rel.core.Sort;
import org.apache.calcite.rel.core.TableScan;
+import org.apache.calcite.rel.metadata.RelMdUtil;
import org.apache.calcite.rel.metadata.RelMetadataQuery;
import org.apache.calcite.rel.type.RelDataType;
import org.apache.calcite.rel.type.RelDataTypeField;
@@ -346,7 +347,31 @@ public class DruidQuery extends AbstractRelNode implements BindableRel {
@Override public RelOptCost computeSelfCost(RelOptPlanner planner,
RelMetadataQuery mq) {
- return Util.last(rels).computeSelfCost(planner, mq).multiplyBy(.1);
+ return Util.last(rels)
+ .computeSelfCost(planner, mq)
+ // Cost increases with the number of fields queried.
+ // A plan returning 100 or more columns will have 2x the cost of a
+ // plan returning 2 columns.
+ // A plan where all extra columns are pruned will be preferred.
+ .multiplyBy(
+ RelMdUtil.linear(querySpec.fieldNames.size(), 2, 100, 1d, 2d))
+ .multiplyBy(getQueryTypeCostMultiplier());
+ }
+
+ private double getQueryTypeCostMultiplier() {
+ // Cost of Select > GroupBy > Timeseries > TopN
+ switch (querySpec.queryType) {
+ case SELECT:
+ return .1;
+ case GROUP_BY:
+ return .08;
+ case TIMESERIES:
+ return .06;
+ case TOP_N:
+ return .04;
+ default:
+ return .2;
+ }
}
@Override public void register(RelOptPlanner planner) {
http://git-wip-us.apache.org/repos/asf/calcite/blob/c90fddfb/druid/src/test/java/org/apache/calcite/test/DruidAdapterIT.java
----------------------------------------------------------------------
diff --git a/druid/src/test/java/org/apache/calcite/test/DruidAdapterIT.java b/druid/src/test/java/org/apache/calcite/test/DruidAdapterIT.java
index 15cf7e0..cd28362 100644
--- a/druid/src/test/java/org/apache/calcite/test/DruidAdapterIT.java
+++ b/druid/src/test/java/org/apache/calcite/test/DruidAdapterIT.java
@@ -1335,7 +1335,7 @@ public class DruidAdapterIT {
final String explain = "EnumerableInterpreter\n"
+ " BindableAggregate(group=[{}], C=[COUNT()])\n"
+ " BindableFilter(condition=[AND(>=(/INT(Reinterpret($0), 86400000), 1997-01-01), <(/INT(Reinterpret($0), 86400000), 1998-01-01), OR(AND(>=(/INT(Reinterpret($0), 86400000), 1997-04-01), <(/INT(Reinterpret($0), 86400000), 1997-05-01)), AND(>=(/INT(Reinterpret($0), 86400000), 1997-06-01), <(/INT(Reinterpret($0), 86400000), 1997-07-01))))])\n"
- + " DruidQuery(table=[[foodmart, foodmart]], intervals=[[1900-01-09T00:00:00.000/2992-01-10T00:00:00.000]])";
+ + " DruidQuery(table=[[foodmart, foodmart]], intervals=[[1900-01-09T00:00:00.000/2992-01-10T00:00:00.000]], projects=[[$0]])";
sql(sql)
.explainContains(explain)
.returnsUnordered("C=13500");
@@ -1368,6 +1368,45 @@ public class DruidAdapterIT {
sql(sql, WIKI)
.returnsCount(9);
}
+
+
+ /** Test case for
+ * <a href="https://issues.apache.org/jira/browse/CALCITE-1656">[CALCITE-1656]
+ * Improve cost function in DruidQuery to encourage early column
+ * pruning</a>. */
+ @Test public void testFieldBasedCostColumnPruning() {
+ // A query where filter cannot be pushed to Druid but
+ // the project can still be pushed in order to prune extra columns.
+ String sql = "select \"countryName\", floor(\"time\" to DAY),\n"
+ + " cast(count(*) as integer) as c\n"
+ + "from \"wiki\"\n"
+ + "where floor(\"time\" to DAY) >= '1997-01-01 00:00:00'\n"
+ + "and floor(\"time\" to DAY) < '1997-09-01 00:00:00'\n"
+ + "group by \"countryName\", floor(\"time\" TO DAY)\n"
+ + "order by c limit 5";
+
+ String plan = "BindableProject(countryName=[$0], EXPR$1=[$1], C=[CAST($2):INTEGER NOT NULL])\n"
+ + " BindableSort(sort0=[$2], dir0=[ASC], fetch=[5])\n"
+ + " BindableAggregate(group=[{0, 1}], agg#0=[COUNT()])\n"
+ + " BindableProject(countryName=[$1], EXPR$1=[FLOOR($0, FLAG(DAY))])\n"
+ + " BindableFilter(condition=[AND(>=(FLOOR($0, FLAG(DAY)), 1997-01-01 00:00:00), <(FLOOR($0, FLAG(DAY)), 1997-09-01 00:00:00))])\n"
+ + " DruidQuery(table=[[wiki, wiki]], intervals=[[1900-01-09T00:00:00.000/2992-01-10T00:00:00.000]], projects=[[$0, $5]])";
+
+ // NOTE: Druid query only has countryName as the dimension
+ // being queried after project is pushed to druid query.
+ String druidQuery = "{\"queryType\":\"select\","
+ + "\"dataSource\":\"wikiticker\","
+ + "\"descending\":false,"
+ + "\"intervals\":[\"1900-01-09T00:00:00.000/2992-01-10T00:00:00.000\"],"
+ + "\"dimensions\":[\"countryName\"],"
+ + "\"metrics\":[],"
+ + "\"granularity\":\"all\","
+ + "\"pagingSpec\":{\"threshold\":16384,\"fromNext\":true},"
+ + "\"context\":{\"druid.query.fetch\":false}}";
+ sql(sql, WIKI).explainContains(plan);
+ sql(sql, WIKI).queryContains(druidChecker(druidQuery));
+ }
+
}
// End DruidAdapterIT.java