[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 <[email protected]> Authored: Fri Feb 24 21:40:42 2017 +0530 Committer: Julian Hyde <[email protected]> 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
