HIVE-13316: Upgrade to Calcite 1.10 (Jesus Camacho Rodriguez, reviewed by Ashutosh Chauhan)
Project: http://git-wip-us.apache.org/repos/asf/hive/repo Commit: http://git-wip-us.apache.org/repos/asf/hive/commit/b597ab2a Tree: http://git-wip-us.apache.org/repos/asf/hive/tree/b597ab2a Diff: http://git-wip-us.apache.org/repos/asf/hive/diff/b597ab2a Branch: refs/heads/hive-14535 Commit: b597ab2a07034b9c82e4bb0591123c3a115f27eb Parents: 4b7f373 Author: Jesus Camacho Rodriguez <jcama...@apache.org> Authored: Wed Sep 28 20:23:33 2016 +0100 Committer: Jesus Camacho Rodriguez <jcama...@apache.org> Committed: Tue Oct 18 12:27:41 2016 +0100 ---------------------------------------------------------------------- .../druid/HiveDruidQueryBasedInputFormat.java | 6 +- .../serde/DruidGroupByQueryRecordReader.java | 2 +- .../serde/DruidSelectQueryRecordReader.java | 2 +- .../hadoop/hive/druid/serde/DruidSerDe.java | 2 +- .../serde/DruidTimeseriesQueryRecordReader.java | 2 +- .../druid/serde/DruidTopNQueryRecordReader.java | 2 +- pom.xml | 3 +- ql/pom.xml | 7 +- .../calcite/HiveDefaultRelMetadataProvider.java | 2 +- .../optimizer/calcite/HivePlannerContext.java | 9 +- .../ql/optimizer/calcite/HiveRelBuilder.java | 18 +- .../ql/optimizer/calcite/HiveRelOptUtil.java | 8 +- .../hive/ql/optimizer/calcite/HiveRexUtil.java | 821 -------------- .../optimizer/calcite/HiveTypeSystemImpl.java | 39 +- .../calcite/cost/HiveDefaultCostModel.java | 7 +- .../optimizer/calcite/cost/HiveRelMdCost.java | 10 +- .../calcite/druid/DruidIntervalUtils.java | 466 -------- .../ql/optimizer/calcite/druid/DruidQuery.java | 1053 ------------------ .../optimizer/calcite/druid/DruidQueryType.java | 42 - .../ql/optimizer/calcite/druid/DruidRules.java | 591 ---------- .../ql/optimizer/calcite/druid/DruidSchema.java | 51 - .../ql/optimizer/calcite/druid/DruidTable.java | 121 -- .../optimizer/calcite/druid/HiveDruidConf.java | 33 - .../calcite/reloperators/HiveAggregate.java | 3 +- .../reloperators/HiveDateGranularity.java | 54 - .../calcite/reloperators/HiveExtractDate.java | 50 + .../calcite/reloperators/HiveFloorDate.java | 64 ++ .../rules/HiveAggregateJoinTransposeRule.java | 9 +- .../rules/HiveAggregateProjectMergeRule.java | 3 +- .../rules/HiveFilterProjectTSTransposeRule.java | 16 +- .../rules/HiveFilterProjectTransposeRule.java | 21 +- .../calcite/rules/HivePreFilteringRule.java | 7 +- .../rules/HiveReduceExpressionsRule.java | 914 ++------------- .../HiveReduceExpressionsWithStatsRule.java | 5 +- .../calcite/rules/HiveRelFieldTrimmer.java | 243 +--- .../calcite/stats/HiveRelMdCollation.java | 10 +- .../calcite/stats/HiveRelMdDistribution.java | 10 +- .../calcite/stats/HiveRelMdPredicates.java | 31 +- .../calcite/stats/HiveRelMdSelectivity.java | 28 +- .../optimizer/calcite/stats/HiveRelMdSize.java | 13 +- .../calcite/stats/HiveRelMdUniqueKeys.java | 72 +- .../calcite/translator/ASTBuilder.java | 49 +- .../calcite/translator/ASTConverter.java | 51 +- .../calcite/translator/ExprNodeConverter.java | 49 +- .../translator/PlanModifierForASTConv.java | 5 + .../calcite/translator/RexNodeConverter.java | 61 +- .../translator/SqlFunctionConverter.java | 37 +- .../calcite/translator/TypeConverter.java | 41 +- .../hadoop/hive/ql/parse/CalcitePlanner.java | 40 +- .../hive/ql/parse/TypeCheckProcFactory.java | 2 +- .../optimizer/calcite/TestCBOMaxNumToCNF.java | 5 +- .../calcite/TestCBORuleFiredOnlyOnce.java | 2 +- .../results/clientpositive/druid_basic2.q.out | 48 +- .../clientpositive/druid_intervals.q.out | 40 +- .../clientpositive/druid_timeseries.q.out | 52 +- .../results/clientpositive/druid_topn.q.out | 32 +- .../clientpositive/explain_logical.q.out | 48 +- .../clientpositive/groupby_sort_1_23.q.out | 40 +- .../clientpositive/groupby_sort_skew_1_23.q.out | 40 +- .../results/clientpositive/limit_pushdown.q.out | 12 +- .../clientpositive/limit_pushdown3.q.out | 12 +- .../clientpositive/llap/explainuser_4.q.out | 32 +- .../clientpositive/llap/limit_pushdown.q.out | 9 +- .../results/clientpositive/llap/lineage3.q.out | 2 +- .../llap/table_access_keys_stats.q.out | 6 +- .../llap/tez_dynpart_hashjoin_1.q.out | 42 +- .../llap/tez_vector_dynpart_hashjoin_1.q.out | 42 +- .../offset_limit_ppd_optimizer.q.out | 12 +- .../results/clientpositive/perf/query75.q.out | 12 +- .../spark/groupby_sort_1_23.q.out | 32 +- .../spark/groupby_sort_skew_1_23.q.out | 32 +- .../clientpositive/spark/limit_pushdown.q.out | 9 +- .../spark/table_access_keys_stats.q.out | 6 +- .../clientpositive/tez/explainanalyze_4.q.out | 32 +- .../tez/vectorization_limit.q.out | 9 +- .../clientpositive/vectorization_limit.q.out | 12 +- 76 files changed, 1136 insertions(+), 4669 deletions(-) ---------------------------------------------------------------------- http://git-wip-us.apache.org/repos/asf/hive/blob/b597ab2a/druid-handler/src/java/org/apache/hadoop/hive/druid/HiveDruidQueryBasedInputFormat.java ---------------------------------------------------------------------- diff --git a/druid-handler/src/java/org/apache/hadoop/hive/druid/HiveDruidQueryBasedInputFormat.java b/druid-handler/src/java/org/apache/hadoop/hive/druid/HiveDruidQueryBasedInputFormat.java index 3df1452..a18e590 100644 --- a/druid-handler/src/java/org/apache/hadoop/hive/druid/HiveDruidQueryBasedInputFormat.java +++ b/druid-handler/src/java/org/apache/hadoop/hive/druid/HiveDruidQueryBasedInputFormat.java @@ -25,6 +25,8 @@ import java.util.HashMap; import java.util.List; import java.util.Map; +import org.apache.calcite.adapter.druid.DruidDateTimeUtils; +import org.apache.calcite.adapter.druid.DruidTable; import org.apache.commons.lang3.StringEscapeUtils; import org.apache.commons.lang3.StringUtils; import org.apache.hadoop.conf.Configuration; @@ -37,8 +39,6 @@ import org.apache.hadoop.hive.druid.serde.DruidSelectQueryRecordReader; import org.apache.hadoop.hive.druid.serde.DruidTimeseriesQueryRecordReader; import org.apache.hadoop.hive.druid.serde.DruidTopNQueryRecordReader; import org.apache.hadoop.hive.druid.serde.DruidWritable; -import org.apache.hadoop.hive.ql.optimizer.calcite.druid.DruidIntervalUtils; -import org.apache.hadoop.hive.ql.optimizer.calcite.druid.DruidTable; import org.apache.hadoop.hive.shims.ShimLoader; import org.apache.hadoop.io.NullWritable; import org.apache.hadoop.mapred.JobConf; @@ -273,7 +273,7 @@ public class HiveDruidQueryBasedInputFormat extends InputFormat<NullWritable, Dr } private static List<List<Interval>> createSplitsIntervals(List<Interval> intervals, int numSplits) { - final long totalTime = DruidIntervalUtils.extractTotalTime(intervals); + final long totalTime = DruidDateTimeUtils.extractTotalTime(intervals); long startTime = intervals.get(0).getStartMillis(); long endTime = startTime; long currTime = 0; http://git-wip-us.apache.org/repos/asf/hive/blob/b597ab2a/druid-handler/src/java/org/apache/hadoop/hive/druid/serde/DruidGroupByQueryRecordReader.java ---------------------------------------------------------------------- diff --git a/druid-handler/src/java/org/apache/hadoop/hive/druid/serde/DruidGroupByQueryRecordReader.java b/druid-handler/src/java/org/apache/hadoop/hive/druid/serde/DruidGroupByQueryRecordReader.java index 226060f..49e096b 100644 --- a/druid-handler/src/java/org/apache/hadoop/hive/druid/serde/DruidGroupByQueryRecordReader.java +++ b/druid-handler/src/java/org/apache/hadoop/hive/druid/serde/DruidGroupByQueryRecordReader.java @@ -21,9 +21,9 @@ import java.io.IOException; import java.io.InputStream; import java.util.List; +import org.apache.calcite.adapter.druid.DruidTable; import org.apache.hadoop.conf.Configuration; import org.apache.hadoop.hive.druid.DruidStorageHandlerUtils; -import org.apache.hadoop.hive.ql.optimizer.calcite.druid.DruidTable; import org.apache.hadoop.io.NullWritable; import org.apache.hadoop.mapreduce.InputSplit; http://git-wip-us.apache.org/repos/asf/hive/blob/b597ab2a/druid-handler/src/java/org/apache/hadoop/hive/druid/serde/DruidSelectQueryRecordReader.java ---------------------------------------------------------------------- diff --git a/druid-handler/src/java/org/apache/hadoop/hive/druid/serde/DruidSelectQueryRecordReader.java b/druid-handler/src/java/org/apache/hadoop/hive/druid/serde/DruidSelectQueryRecordReader.java index 70b493c..fccf7c4 100644 --- a/druid-handler/src/java/org/apache/hadoop/hive/druid/serde/DruidSelectQueryRecordReader.java +++ b/druid-handler/src/java/org/apache/hadoop/hive/druid/serde/DruidSelectQueryRecordReader.java @@ -22,8 +22,8 @@ import java.io.InputStream; import java.util.Iterator; import java.util.List; +import org.apache.calcite.adapter.druid.DruidTable; import org.apache.hadoop.hive.druid.DruidStorageHandlerUtils; -import org.apache.hadoop.hive.ql.optimizer.calcite.druid.DruidTable; import org.apache.hadoop.io.NullWritable; import com.fasterxml.jackson.core.type.TypeReference; http://git-wip-us.apache.org/repos/asf/hive/blob/b597ab2a/druid-handler/src/java/org/apache/hadoop/hive/druid/serde/DruidSerDe.java ---------------------------------------------------------------------- diff --git a/druid-handler/src/java/org/apache/hadoop/hive/druid/serde/DruidSerDe.java b/druid-handler/src/java/org/apache/hadoop/hive/druid/serde/DruidSerDe.java index 8f53d4a..238f7a3 100644 --- a/druid-handler/src/java/org/apache/hadoop/hive/druid/serde/DruidSerDe.java +++ b/druid-handler/src/java/org/apache/hadoop/hive/druid/serde/DruidSerDe.java @@ -25,11 +25,11 @@ import java.util.List; import java.util.Map.Entry; import java.util.Properties; +import org.apache.calcite.adapter.druid.DruidTable; import org.apache.hadoop.conf.Configuration; import org.apache.hadoop.hive.conf.Constants; import org.apache.hadoop.hive.conf.HiveConf; import org.apache.hadoop.hive.druid.DruidStorageHandlerUtils; -import org.apache.hadoop.hive.ql.optimizer.calcite.druid.DruidTable; import org.apache.hadoop.hive.serde2.AbstractSerDe; import org.apache.hadoop.hive.serde2.SerDeException; import org.apache.hadoop.hive.serde2.SerDeSpec; http://git-wip-us.apache.org/repos/asf/hive/blob/b597ab2a/druid-handler/src/java/org/apache/hadoop/hive/druid/serde/DruidTimeseriesQueryRecordReader.java ---------------------------------------------------------------------- diff --git a/druid-handler/src/java/org/apache/hadoop/hive/druid/serde/DruidTimeseriesQueryRecordReader.java b/druid-handler/src/java/org/apache/hadoop/hive/druid/serde/DruidTimeseriesQueryRecordReader.java index 812ae03..b91178c 100644 --- a/druid-handler/src/java/org/apache/hadoop/hive/druid/serde/DruidTimeseriesQueryRecordReader.java +++ b/druid-handler/src/java/org/apache/hadoop/hive/druid/serde/DruidTimeseriesQueryRecordReader.java @@ -21,8 +21,8 @@ import java.io.IOException; import java.io.InputStream; import java.util.List; +import org.apache.calcite.adapter.druid.DruidTable; import org.apache.hadoop.hive.druid.DruidStorageHandlerUtils; -import org.apache.hadoop.hive.ql.optimizer.calcite.druid.DruidTable; import org.apache.hadoop.io.NullWritable; import com.fasterxml.jackson.core.type.TypeReference; http://git-wip-us.apache.org/repos/asf/hive/blob/b597ab2a/druid-handler/src/java/org/apache/hadoop/hive/druid/serde/DruidTopNQueryRecordReader.java ---------------------------------------------------------------------- diff --git a/druid-handler/src/java/org/apache/hadoop/hive/druid/serde/DruidTopNQueryRecordReader.java b/druid-handler/src/java/org/apache/hadoop/hive/druid/serde/DruidTopNQueryRecordReader.java index 0b87976..0b77a9b 100644 --- a/druid-handler/src/java/org/apache/hadoop/hive/druid/serde/DruidTopNQueryRecordReader.java +++ b/druid-handler/src/java/org/apache/hadoop/hive/druid/serde/DruidTopNQueryRecordReader.java @@ -22,8 +22,8 @@ import java.io.InputStream; import java.util.Iterator; import java.util.List; +import org.apache.calcite.adapter.druid.DruidTable; import org.apache.hadoop.hive.druid.DruidStorageHandlerUtils; -import org.apache.hadoop.hive.ql.optimizer.calcite.druid.DruidTable; import org.apache.hadoop.io.NullWritable; import com.fasterxml.jackson.core.type.TypeReference; http://git-wip-us.apache.org/repos/asf/hive/blob/b597ab2a/pom.xml ---------------------------------------------------------------------- diff --git a/pom.xml b/pom.xml index 5d13344..98d2dc2 100644 --- a/pom.xml +++ b/pom.xml @@ -112,9 +112,10 @@ <antlr.version>3.4</antlr.version> <apache-directory-server.version>1.5.6</apache-directory-server.version> <apache-directory-clientapi.version>0.1</apache-directory-clientapi.version> + <avatica.version>1.8.0</avatica.version> <avro.version>1.7.7</avro.version> <bonecp.version>0.8.0.RELEASE</bonecp.version> - <calcite.version>1.6.0</calcite.version> + <calcite.version>1.10.0</calcite.version> <datanucleus-api-jdo.version>4.2.1</datanucleus-api-jdo.version> <datanucleus-core.version>4.1.6</datanucleus-core.version> <datanucleus-rdbms.version>4.1.7</datanucleus-rdbms.version> http://git-wip-us.apache.org/repos/asf/hive/blob/b597ab2a/ql/pom.xml ---------------------------------------------------------------------- diff --git a/ql/pom.xml b/ql/pom.xml index 2a93bb7..489c6f3 100644 --- a/ql/pom.xml +++ b/ql/pom.xml @@ -383,8 +383,13 @@ </dependency> <dependency> <groupId>org.apache.calcite</groupId> - <artifactId>calcite-avatica</artifactId> + <artifactId>calcite-druid</artifactId> <version>${calcite.version}</version> + </dependency> + <dependency> + <groupId>org.apache.calcite.avatica</groupId> + <artifactId>avatica</artifactId> + <version>${avatica.version}</version> <exclusions> <!-- hsqldb interferes with the use of derby as the default db in hive's use of datanucleus. http://git-wip-us.apache.org/repos/asf/hive/blob/b597ab2a/ql/src/java/org/apache/hadoop/hive/ql/optimizer/calcite/HiveDefaultRelMetadataProvider.java ---------------------------------------------------------------------- diff --git a/ql/src/java/org/apache/hadoop/hive/ql/optimizer/calcite/HiveDefaultRelMetadataProvider.java b/ql/src/java/org/apache/hadoop/hive/ql/optimizer/calcite/HiveDefaultRelMetadataProvider.java index c0609d7..75fb916 100644 --- a/ql/src/java/org/apache/hadoop/hive/ql/optimizer/calcite/HiveDefaultRelMetadataProvider.java +++ b/ql/src/java/org/apache/hadoop/hive/ql/optimizer/calcite/HiveDefaultRelMetadataProvider.java @@ -77,7 +77,7 @@ public class HiveDefaultRelMetadataProvider { HiveRelMdDistribution.SOURCE, HiveRelMdCollation.SOURCE, HiveRelMdPredicates.SOURCE, - new DefaultRelMetadataProvider())); + DefaultRelMetadataProvider.INSTANCE)); } } http://git-wip-us.apache.org/repos/asf/hive/blob/b597ab2a/ql/src/java/org/apache/hadoop/hive/ql/optimizer/calcite/HivePlannerContext.java ---------------------------------------------------------------------- diff --git a/ql/src/java/org/apache/hadoop/hive/ql/optimizer/calcite/HivePlannerContext.java b/ql/src/java/org/apache/hadoop/hive/ql/optimizer/calcite/HivePlannerContext.java index 890aea1..8beb0dd 100644 --- a/ql/src/java/org/apache/hadoop/hive/ql/optimizer/calcite/HivePlannerContext.java +++ b/ql/src/java/org/apache/hadoop/hive/ql/optimizer/calcite/HivePlannerContext.java @@ -19,19 +19,15 @@ package org.apache.hadoop.hive.ql.optimizer.calcite; import org.apache.calcite.plan.Context; import org.apache.hadoop.hive.ql.optimizer.calcite.cost.HiveAlgorithmsConf; -import org.apache.hadoop.hive.ql.optimizer.calcite.druid.HiveDruidConf; import org.apache.hadoop.hive.ql.optimizer.calcite.rules.HiveRulesRegistry; public class HivePlannerContext implements Context { private HiveAlgorithmsConf algoConfig; - private HiveDruidConf druidConf; private HiveRulesRegistry registry; - public HivePlannerContext(HiveAlgorithmsConf algoConfig, HiveDruidConf druidConf, - HiveRulesRegistry registry) { + public HivePlannerContext(HiveAlgorithmsConf algoConfig, HiveRulesRegistry registry) { this.algoConfig = algoConfig; - this.druidConf = druidConf; this.registry = registry; } @@ -39,9 +35,6 @@ public class HivePlannerContext implements Context { if (clazz.isInstance(algoConfig)) { return clazz.cast(algoConfig); } - if (clazz.isInstance(druidConf)) { - return clazz.cast(druidConf); - } if (clazz.isInstance(registry)) { return clazz.cast(registry); } http://git-wip-us.apache.org/repos/asf/hive/blob/b597ab2a/ql/src/java/org/apache/hadoop/hive/ql/optimizer/calcite/HiveRelBuilder.java ---------------------------------------------------------------------- diff --git a/ql/src/java/org/apache/hadoop/hive/ql/optimizer/calcite/HiveRelBuilder.java b/ql/src/java/org/apache/hadoop/hive/ql/optimizer/calcite/HiveRelBuilder.java index 1c64d64..bc160d8 100644 --- a/ql/src/java/org/apache/hadoop/hive/ql/optimizer/calcite/HiveRelBuilder.java +++ b/ql/src/java/org/apache/hadoop/hive/ql/optimizer/calcite/HiveRelBuilder.java @@ -81,7 +81,7 @@ public class HiveRelBuilder extends RelBuilder { @Override public RelBuilder filter(Iterable<? extends RexNode> predicates) { - final RexNode x = HiveRexUtil.simplify(cluster.getRexBuilder(), + final RexNode x = RexUtil.simplify(cluster.getRexBuilder(), RexUtil.composeConjunction(cluster.getRexBuilder(), predicates, false)); if (!x.isAlwaysTrue()) { final RelNode input = build(); @@ -91,4 +91,20 @@ public class HiveRelBuilder extends RelBuilder { return this; } + /** + * Empty relationship can be expressed in many different ways, e.g., + * filter(cond=false), empty LogicalValues(), etc. Calcite default implementation + * uses empty LogicalValues(); however, currently there is not an equivalent to + * this expression in Hive. Thus, we use limit 0, since Hive already includes + * optimizations that will do early pruning of the result tree when it is found, + * e.g., GlobalLimitOptimizer. + */ + @Override + public RelBuilder empty() { + final RelNode input = build(); + final RelNode sort = HiveRelFactories.HIVE_SORT_FACTORY.createSort( + input, RelCollations.of(), null, literal(0)); + return this.push(sort); + } + } http://git-wip-us.apache.org/repos/asf/hive/blob/b597ab2a/ql/src/java/org/apache/hadoop/hive/ql/optimizer/calcite/HiveRelOptUtil.java ---------------------------------------------------------------------- diff --git a/ql/src/java/org/apache/hadoop/hive/ql/optimizer/calcite/HiveRelOptUtil.java b/ql/src/java/org/apache/hadoop/hive/ql/optimizer/calcite/HiveRelOptUtil.java index 4c154d0..50fbb78 100644 --- a/ql/src/java/org/apache/hadoop/hive/ql/optimizer/calcite/HiveRelOptUtil.java +++ b/ql/src/java/org/apache/hadoop/hive/ql/optimizer/calcite/HiveRelOptUtil.java @@ -24,7 +24,6 @@ import java.util.List; import org.apache.calcite.plan.RelOptCluster; import org.apache.calcite.plan.RelOptUtil; import org.apache.calcite.rel.RelNode; -import org.apache.calcite.rel.core.RelFactories; import org.apache.calcite.rel.type.RelDataType; import org.apache.calcite.rel.type.RelDataTypeField; import org.apache.calcite.rex.RexBuilder; @@ -34,6 +33,7 @@ import org.apache.calcite.rex.RexUtil; import org.apache.calcite.sql.SqlKind; import org.apache.calcite.sql.SqlOperator; import org.apache.calcite.sql.fun.SqlStdOperatorTable; +import org.apache.calcite.tools.RelBuilder; import org.apache.calcite.util.ImmutableBitSet; import org.apache.hadoop.hive.ql.exec.FunctionRegistry; import org.apache.hadoop.hive.ql.optimizer.calcite.translator.TypeConverter; @@ -314,12 +314,12 @@ public class HiveRelOptUtil extends RelOptUtil { * * <p>Optimizes if the fields are the identity projection. * - * @param factory ProjectFactory + * @param relBuilder RelBuilder * @param child Input relational expression * @param posList Source of each projected field * @return Relational expression that projects given fields */ - public static RelNode createProject(final RelFactories.ProjectFactory factory, + public static RelNode createProject(final RelBuilder relBuilder, final RelNode child, final List<Integer> posList) { RelDataType rowType = child.getRowType(); final List<String> fieldNames = rowType.getFieldNames(); @@ -344,7 +344,7 @@ public class HiveRelOptUtil extends RelOptUtil { final int pos = posList.get(index); return fieldNames.get(pos); } - }, true, factory); + }, true, relBuilder); } } http://git-wip-us.apache.org/repos/asf/hive/blob/b597ab2a/ql/src/java/org/apache/hadoop/hive/ql/optimizer/calcite/HiveRexUtil.java ---------------------------------------------------------------------- diff --git a/ql/src/java/org/apache/hadoop/hive/ql/optimizer/calcite/HiveRexUtil.java b/ql/src/java/org/apache/hadoop/hive/ql/optimizer/calcite/HiveRexUtil.java deleted file mode 100644 index 15707c1..0000000 --- a/ql/src/java/org/apache/hadoop/hive/ql/optimizer/calcite/HiveRexUtil.java +++ /dev/null @@ -1,821 +0,0 @@ -/* - * Licensed to the Apache Software Foundation (ASF) under one - * or more contributor license agreements. See the NOTICE file - * distributed with this work for additional information - * regarding copyright ownership. The ASF licenses this file - * to you under the Apache License, Version 2.0 (the - * "License"); you may not use this file except in compliance - * with the License. You may obtain a copy of the License at - * - * http://www.apache.org/licenses/LICENSE-2.0 - * - * Unless required by applicable law or agreed to in writing, software - * distributed under the License is distributed on an "AS IS" BASIS, - * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. - * See the License for the specific language governing permissions and - * limitations under the License. - */ -package org.apache.hadoop.hive.ql.optimizer.calcite; - -import java.util.ArrayList; -import java.util.Collection; -import java.util.Collections; -import java.util.HashMap; -import java.util.HashSet; -import java.util.LinkedHashSet; -import java.util.List; -import java.util.Map; -import java.util.Set; - -import org.apache.calcite.linq4j.Ord; -import org.apache.calcite.plan.RelOptUtil; -import org.apache.calcite.rex.RexBuilder; -import org.apache.calcite.rex.RexCall; -import org.apache.calcite.rex.RexInputRef; -import org.apache.calcite.rex.RexLiteral; -import org.apache.calcite.rex.RexNode; -import org.apache.calcite.rex.RexShuttle; -import org.apache.calcite.rex.RexUtil; -import org.apache.calcite.sql.SqlKind; -import org.apache.calcite.sql.SqlOperator; -import org.apache.calcite.sql.fun.SqlStdOperatorTable; -import org.apache.calcite.sql.type.SqlTypeName; -import org.apache.calcite.util.ControlFlowException; -import org.apache.calcite.util.Pair; -import org.apache.calcite.util.Util; -import org.slf4j.Logger; -import org.slf4j.LoggerFactory; - -import com.google.common.collect.ArrayListMultimap; -import com.google.common.collect.ImmutableList; -import com.google.common.collect.Lists; -import com.google.common.collect.Multimap; - - -public class HiveRexUtil { - - protected static final Logger LOG = LoggerFactory.getLogger(HiveRexUtil.class); - - - /** Converts an expression to conjunctive normal form (CNF). - * - * <p>The following expression is in CNF: - * - * <blockquote>(a OR b) AND (c OR d)</blockquote> - * - * <p>The following expression is not in CNF: - * - * <blockquote>(a AND b) OR c</blockquote> - * - * but can be converted to CNF: - * - * <blockquote>(a OR c) AND (b OR c)</blockquote> - * - * <p>The following expression is not in CNF: - * - * <blockquote>NOT (a OR NOT b)</blockquote> - * - * but can be converted to CNF by applying de Morgan's theorem: - * - * <blockquote>NOT a AND b</blockquote> - * - * <p>Expressions not involving AND, OR or NOT at the top level are in CNF. - */ - public static RexNode toCnf(RexBuilder rexBuilder, RexNode rex) { - return new CnfHelper(rexBuilder).toCnf(rex); - } - - public static RexNode toCnf(RexBuilder rexBuilder, int maxCNFNodeCount, RexNode rex) { - return new CnfHelper(rexBuilder, maxCNFNodeCount).toCnf(rex); - } - - /** Helps {@link org.apache.calcite.rex.RexUtil#toCnf}. */ - private static class CnfHelper { - final RexBuilder rexBuilder; - int currentCount; - final int maxNodeCount; - - private CnfHelper(RexBuilder rexBuilder) { - this(rexBuilder, Integer.MAX_VALUE); - } - - private CnfHelper(RexBuilder rexBuilder, int maxNodeCount) { - this.rexBuilder = rexBuilder; - this.maxNodeCount = maxNodeCount == -1 ? Integer.MAX_VALUE : maxNodeCount; - } - - public RexNode toCnf(RexNode rex) { - try { - this.currentCount = 0; - return toCnf2(rex); - } catch (OverflowError e) { - if (LOG.isDebugEnabled()) { - LOG.debug("Transformation to CNF not carried out as number of resulting nodes " - + "in expression is greater than the max number of nodes allowed"); - } - Util.swallow(e, null); - return rex; - } - } - - private RexNode toCnf2(RexNode rex) { - final List<RexNode> operands; - switch (rex.getKind()) { - case AND: - incrementAndCheck(); - operands = RexUtil.flattenAnd(((RexCall) rex).getOperands()); - final List<RexNode> cnfOperands = Lists.newArrayList(); - for (RexNode node : operands) { - RexNode cnf = toCnf2(node); - switch (cnf.getKind()) { - case AND: - incrementAndCheck(); - cnfOperands.addAll(((RexCall) cnf).getOperands()); - break; - default: - incrementAndCheck(); - cnfOperands.add(cnf); - } - } - return and(cnfOperands); - case OR: - incrementAndCheck(); - operands = RexUtil.flattenOr(((RexCall) rex).getOperands()); - final RexNode head = operands.get(0); - final RexNode headCnf = toCnf2(head); - final List<RexNode> headCnfs = RelOptUtil.conjunctions(headCnf); - final RexNode tail = or(Util.skip(operands)); - final RexNode tailCnf = toCnf2(tail); - final List<RexNode> tailCnfs = RelOptUtil.conjunctions(tailCnf); - final List<RexNode> list = Lists.newArrayList(); - for (RexNode h : headCnfs) { - for (RexNode t : tailCnfs) { - list.add(or(ImmutableList.of(h, t))); - } - } - return and(list); - case NOT: - final RexNode arg = ((RexCall) rex).getOperands().get(0); - switch (arg.getKind()) { - case NOT: - return toCnf2(((RexCall) arg).getOperands().get(0)); - case OR: - operands = ((RexCall) arg).getOperands(); - List<RexNode> transformedDisj = new ArrayList<>(); - for (RexNode input : RexUtil.flattenOr(operands)) { - transformedDisj.add(rexBuilder.makeCall(input.getType(), SqlStdOperatorTable.NOT, - ImmutableList.of(input))); - } - return toCnf2(and(transformedDisj)); - case AND: - operands = ((RexCall) arg).getOperands(); - List<RexNode> transformedConj = new ArrayList<>(); - for (RexNode input : RexUtil.flattenAnd(operands)) { - transformedConj.add(rexBuilder.makeCall(input.getType(), SqlStdOperatorTable.NOT, - ImmutableList.of(input))); - } - return toCnf2(or(transformedConj)); - default: - incrementAndCheck(); - return rex; - } - default: - incrementAndCheck(); - return rex; - } - } - - private RexNode and(Iterable<? extends RexNode> nodes) { - return RexUtil.composeConjunction(rexBuilder, nodes, false); - } - - private RexNode or(Iterable<? extends RexNode> nodes) { - return RexUtil.composeDisjunction(rexBuilder, nodes, false); - } - - private void incrementAndCheck() { - this.currentCount++; - if (this.currentCount > this.maxNodeCount) { - throw OverflowError.INSTANCE; - } - } - - @SuppressWarnings("serial") - private static class OverflowError extends ControlFlowException { - - public static final OverflowError INSTANCE = new OverflowError(); - - private OverflowError() {} - } - } - - - /** - * Simplifies a boolean expression. - * - * <p>In particular:</p> - * <ul> - * <li>{@code simplify(x = 1 AND y = 2 AND NOT x = 1)} - * returns {@code y = 2}</li> - * <li>{@code simplify(x = 1 AND FALSE)} - * returns {@code FALSE}</li> - * </ul> - */ - public static RexNode simplify(RexBuilder rexBuilder, RexNode e) { - return simplify(rexBuilder, e, false); - } - - public static RexNode simplify(RexBuilder rexBuilder, RexNode e, - boolean unknownAsFalse) { - switch (e.getKind()) { - case AND: - return simplifyAnd(rexBuilder, (RexCall) e, unknownAsFalse); - case OR: - return simplifyOr(rexBuilder, (RexCall) e); - case NOT: - return simplifyNot(rexBuilder, (RexCall) e); - case CASE: - return simplifyCase(rexBuilder, (RexCall) e, unknownAsFalse); - case IS_NULL: - return ((RexCall) e).getOperands().get(0).getType().isNullable() - ? e : rexBuilder.makeLiteral(false); - case IS_NOT_NULL: - return ((RexCall) e).getOperands().get(0).getType().isNullable() - ? e : rexBuilder.makeLiteral(true); - default: - return e; - } - } - - private static RexNode simplifyNot(RexBuilder rexBuilder, RexCall call) { - final RexNode a = call.getOperands().get(0); - switch (a.getKind()) { - case NOT: - // NOT NOT x ==> x - return simplify(rexBuilder, ((RexCall) a).getOperands().get(0)); - } - final SqlKind negateKind = a.getKind().negate(); - if (a.getKind() != negateKind) { - return simplify(rexBuilder, - rexBuilder.makeCall(op(negateKind), - ImmutableList.of(((RexCall) a).getOperands().get(0)))); - } - final SqlKind negateKind2 = negate(a.getKind()); - if (a.getKind() != negateKind2) { - return simplify(rexBuilder, - rexBuilder.makeCall(op(negateKind2), ((RexCall) a).getOperands())); - } - if (a.getKind() == SqlKind.AND) { - // NOT distributivity for AND - final List<RexNode> newOperands = new ArrayList<>(); - for (RexNode operand : ((RexCall) a).getOperands()) { - newOperands.add(simplify(rexBuilder, - rexBuilder.makeCall(SqlStdOperatorTable.NOT, operand))); - } - return simplify(rexBuilder, - rexBuilder.makeCall(SqlStdOperatorTable.OR, newOperands)); - } - if (a.getKind() == SqlKind.OR) { - // NOT distributivity for OR - final List<RexNode> newOperands = new ArrayList<>(); - for (RexNode operand : ((RexCall) a).getOperands()) { - newOperands.add(simplify(rexBuilder, - rexBuilder.makeCall(SqlStdOperatorTable.NOT, operand))); - } - return simplify(rexBuilder, - rexBuilder.makeCall(SqlStdOperatorTable.AND, newOperands)); - } - return call; - } - - private static RexNode simplifyCase(RexBuilder rexBuilder, RexCall call, - boolean unknownAsFalse) { - final List<RexNode> operands = call.getOperands(); - final List<RexNode> newOperands = new ArrayList<>(); - final Set<String> values = new HashSet<>(); - for (int i = 0; i < operands.size(); i++) { - RexNode operand = operands.get(i); - if (RexUtil.isCasePredicate(call, i)) { - if (operand.isAlwaysTrue()) { - // Predicate is always TRUE. Make value the ELSE and quit. - newOperands.add(operands.get(i + 1)); - if (unknownAsFalse && RexUtil.isNull(operands.get(i + 1))) { - values.add(rexBuilder.makeLiteral(false).toString()); - } else { - values.add(operands.get(i + 1).toString()); - } - break; - } else if (operand.isAlwaysFalse() || RexUtil.isNull(operand)) { - // Predicate is always FALSE or NULL. Skip predicate and value. - ++i; - continue; - } - } else { - if (unknownAsFalse && RexUtil.isNull(operand)) { - values.add(rexBuilder.makeLiteral(false).toString()); - } else { - values.add(operand.toString()); - } - } - newOperands.add(operand); - } - assert newOperands.size() % 2 == 1; - if (newOperands.size() == 1 || values.size() == 1) { - return rexBuilder.makeCast(call.getType(), newOperands.get(newOperands.size() - 1)); - } - trueFalse: - if (call.getType().getSqlTypeName() == SqlTypeName.BOOLEAN) { - // Optimize CASE where every branch returns constant true or constant - // false. - final List<Pair<RexNode, RexNode>> pairs = - casePairs(rexBuilder, newOperands); - // 1) Possible simplification if unknown is treated as false: - // CASE - // WHEN p1 THEN TRUE - // WHEN p2 THEN TRUE - // ELSE FALSE - // END - // can be rewritten to: (p1 or p2) - if (unknownAsFalse) { - final List<RexNode> terms = new ArrayList<>(); - int pos = 0; - for (; pos < pairs.size(); pos++) { - // True block - Pair<RexNode, RexNode> pair = pairs.get(pos); - if (!pair.getValue().isAlwaysTrue()) { - break; - } - terms.add(pair.getKey()); - } - for (; pos < pairs.size(); pos++) { - // False block - Pair<RexNode, RexNode> pair = pairs.get(pos); - if (!pair.getValue().isAlwaysFalse() && !RexUtil.isNull(pair.getValue())) { - break; - } - } - if (pos == pairs.size()) { - return RexUtil.composeDisjunction(rexBuilder, terms, false); - } - } - // 2) Another simplification - // CASE - // WHEN p1 THEN TRUE - // WHEN p2 THEN FALSE - // WHEN p3 THEN TRUE - // ELSE FALSE - // END - // if p1...pn cannot be nullable - for (Ord<Pair<RexNode, RexNode>> pair : Ord.zip(pairs)) { - if (pair.e.getKey().getType().isNullable()) { - break trueFalse; - } - if (!pair.e.getValue().isAlwaysTrue() - && !pair.e.getValue().isAlwaysFalse() - && (!unknownAsFalse || !RexUtil.isNull(pair.e.getValue()))) { - break trueFalse; - } - } - final List<RexNode> terms = new ArrayList<>(); - final List<RexNode> notTerms = new ArrayList<>(); - for (Ord<Pair<RexNode, RexNode>> pair : Ord.zip(pairs)) { - if (pair.e.getValue().isAlwaysTrue()) { - terms.add(RexUtil.andNot(rexBuilder, pair.e.getKey(), notTerms)); - } else { - notTerms.add(pair.e.getKey()); - } - } - return RexUtil.composeDisjunction(rexBuilder, terms, false); - } - if (newOperands.equals(operands)) { - return call; - } - return call.clone(call.getType(), newOperands); - } - - /** Given "CASE WHEN p1 THEN v1 ... ELSE e END" - * returns [(p1, v1), ..., (true, e)]. */ - private static List<Pair<RexNode, RexNode>> casePairs(RexBuilder rexBuilder, - List<RexNode> operands) { - final ImmutableList.Builder<Pair<RexNode, RexNode>> builder = - ImmutableList.builder(); - for (int i = 0; i < operands.size() - 1; i += 2) { - builder.add(Pair.of(operands.get(i), operands.get(i + 1))); - } - builder.add( - Pair.of((RexNode) rexBuilder.makeLiteral(true), Util.last(operands))); - return builder.build(); - } - - public static RexNode simplifyAnd(RexBuilder rexBuilder, RexCall e, - boolean unknownAsFalse) { - final List<RexNode> terms = new ArrayList<>(); - final List<RexNode> notTerms = new ArrayList<>(); - RelOptUtil.decomposeConjunction(e, terms, notTerms); - if (unknownAsFalse) { - return simplifyAnd2ForUnknownAsFalse(rexBuilder, terms, notTerms); - } - return simplifyAnd2(rexBuilder, terms, notTerms); - } - - public static RexNode simplifyAnd2(RexBuilder rexBuilder, - List<RexNode> terms, List<RexNode> notTerms) { - for (RexNode term : terms) { - if (term.isAlwaysFalse()) { - 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. - // - // Example #1. x AND y AND z AND NOT (x AND y) - not satisfiable - // Example #2. x AND y AND NOT (x AND y) - not satisfiable - // Example #3. x AND y AND NOT (x AND y AND z) - may be satisfiable - for (RexNode notDisjunction : notTerms) { - final List<RexNode> terms2 = RelOptUtil.conjunctions(notDisjunction); - if (terms.containsAll(terms2)) { - return rexBuilder.makeLiteral(false); - } - } - // Add the NOT disjunctions back in. - for (RexNode notDisjunction : notTerms) { - terms.add( - simplify(rexBuilder, - rexBuilder.makeCall(SqlStdOperatorTable.NOT, notDisjunction))); - } - return RexUtil.composeConjunction(rexBuilder, terms, false); - } - - /** As {@link #simplifyAnd2(RexBuilder, List, List)} but we assume that if the expression returns - * UNKNOWN it will be interpreted as FALSE. */ - public static RexNode simplifyAnd2ForUnknownAsFalse(RexBuilder rexBuilder, - List<RexNode> terms, List<RexNode> notTerms) { - for (RexNode term : terms) { - if (term.isAlwaysFalse()) { - 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), true); - } - // Try to simplify the expression - final Multimap<String,Pair<String,RexNode>> equalityTerms = ArrayListMultimap.create(); - final Map<String,String> equalityConstantTerms = new HashMap<>(); - final Set<String> negatedTerms = new HashSet<>(); - final Set<String> nullOperands = new HashSet<>(); - final Set<RexNode> notNullOperands = new LinkedHashSet<>(); - final Set<String> comparedOperands = new HashSet<>(); - for (int i = 0; i < terms.size(); i++) { - RexNode term = terms.get(i); - if (!HiveCalciteUtil.isDeterministic(term)) { - continue; - } - // Simplify BOOLEAN expressions if possible - while (term.getKind() == SqlKind.EQUALS) { - RexCall call = (RexCall) term; - if (call.getOperands().get(0).isAlwaysTrue()) { - term = call.getOperands().get(1); - terms.remove(i); - terms.add(i, term); - continue; - } else if (call.getOperands().get(1).isAlwaysTrue()) { - term = call.getOperands().get(0); - terms.remove(i); - terms.add(i, term); - continue; - } - break; - } - switch (term.getKind()) { - case EQUALS: - case NOT_EQUALS: - case LESS_THAN: - case GREATER_THAN: - case LESS_THAN_OR_EQUAL: - case GREATER_THAN_OR_EQUAL: - RexCall call = (RexCall) term; - RexNode left = call.getOperands().get(0); - comparedOperands.add(left.toString()); - RexCall leftCast = null; - // if it is a cast, we include the inner reference - if (left.getKind() == SqlKind.CAST) { - leftCast = (RexCall) left; - comparedOperands.add(leftCast.getOperands().get(0).toString()); - } - RexNode right = call.getOperands().get(1); - comparedOperands.add(right.toString()); - RexCall rightCast = null; - // if it is a cast, we include the inner reference - if (right.getKind() == SqlKind.CAST) { - rightCast = (RexCall) right; - comparedOperands.add(rightCast.getOperands().get(0).toString()); - } - // Check for equality on different constants. If the same ref or CAST(ref) - // is equal to different constants, this condition cannot be satisfied, - // and hence it can be evaluated to FALSE - if (term.getKind() == SqlKind.EQUALS) { - boolean leftRef = left instanceof RexInputRef || - (leftCast != null && leftCast.getOperands().get(0) instanceof RexInputRef); - boolean rightRef = right instanceof RexInputRef || - (rightCast != null && rightCast.getOperands().get(0) instanceof RexInputRef); - if (right instanceof RexLiteral && leftRef) { - final String literal = right.toString(); - final String prevLiteral = equalityConstantTerms.put(left.toString(), literal); - if (prevLiteral != null && !literal.equals(prevLiteral)) { - return rexBuilder.makeLiteral(false); - } - } else if (left instanceof RexLiteral && rightRef) { - final String literal = left.toString(); - final String prevLiteral = equalityConstantTerms.put(right.toString(), literal); - if (prevLiteral != null && !literal.equals(prevLiteral)) { - return rexBuilder.makeLiteral(false); - } - } else if (leftRef && rightRef) { - equalityTerms.put(left.toString(), Pair.of(right.toString(), term)); - } - } - // Assume the expression a > 5 is part of a Filter condition. - // Then we can derive the negated term: a <= 5. - // But as the comparison is string based and thus operands order dependent, - // we should also add the inverted negated term: 5 >= a. - // Observe that for creating the inverted term we invert the list of operands. - RexNode negatedTerm = negate(rexBuilder, call); - if (negatedTerm != null) { - negatedTerms.add(negatedTerm.toString()); - RexNode invertNegatedTerm = invert(rexBuilder, (RexCall) negatedTerm); - if (invertNegatedTerm != null) { - negatedTerms.add(invertNegatedTerm.toString()); - } - } - break; - case IN: - comparedOperands.add(((RexCall) term).operands.get(0).toString()); - break; - case BETWEEN: - comparedOperands.add(((RexCall) term).operands.get(1).toString()); - break; - case IS_NOT_NULL: - notNullOperands.add(((RexCall) term).getOperands().get(0)); - terms.remove(i); - --i; - break; - case IS_NULL: - nullOperands.add(((RexCall) term).getOperands().get(0).toString()); - } - } - // If one column should be null and is in a comparison predicate, - // it is not satisfiable. - // Example. IS NULL(x) AND x < 5 - not satisfiable - if (!Collections.disjoint(nullOperands, comparedOperands)) { - return rexBuilder.makeLiteral(false); - } - // Check for equality of two refs wrt equality with constants - // Example #1. x=5 AND y=5 AND x=y : x=5 AND y=5 - // Example #2. x=5 AND y=6 AND x=y - not satisfiable - for (String ref1 : equalityTerms.keySet()) { - final String literal1 = equalityConstantTerms.get(ref1); - if (literal1 == null) { - continue; - } - Collection<Pair<String, RexNode>> references = equalityTerms.get(ref1); - for (Pair<String,RexNode> ref2 : references) { - final String literal2 = equalityConstantTerms.get(ref2.left); - if (literal2 == null) { - continue; - } - if (!literal1.equals(literal2)) { - // If an expression is equal to two different constants, - // it is not satisfiable - return rexBuilder.makeLiteral(false); - } - // Otherwise we can remove the term, as we already know that - // the expression is equal to two constants - terms.remove(ref2.right); - } - } - // Remove not necessary IS NOT NULL expressions. - // - // Example. IS NOT NULL(x) AND x < 5 : x < 5 - for (RexNode operand : notNullOperands) { - if (!comparedOperands.contains(operand.toString())) { - terms.add( - rexBuilder.makeCall(SqlStdOperatorTable.IS_NOT_NULL, operand)); - } - } - // If one of the not-disjunctions is a disjunction that is wholly - // contained in the disjunctions list, the expression is not - // satisfiable. - // - // Example #1. x AND y AND z AND NOT (x AND y) - not satisfiable - // Example #2. x AND y AND NOT (x AND y) - not satisfiable - // Example #3. x AND y AND NOT (x AND y AND z) - may be satisfiable - final Set<String> termsSet = new HashSet<String>( - Lists.transform(terms, HiveCalciteUtil.REX_STR_FN)); - for (RexNode notDisjunction : notTerms) { - if (!HiveCalciteUtil.isDeterministic(notDisjunction)) { - continue; - } - final List<String> terms2Set = Lists.transform( - RelOptUtil.conjunctions(notDisjunction), HiveCalciteUtil.REX_STR_FN); - if (termsSet.containsAll(terms2Set)) { - return rexBuilder.makeLiteral(false); - } - } - // Add the NOT disjunctions back in. - for (RexNode notDisjunction : notTerms) { - terms.add( - simplify(rexBuilder, - rexBuilder.makeCall(SqlStdOperatorTable.NOT, notDisjunction), true)); - } - // The negated terms: only deterministic expressions - for (String negatedTerm : negatedTerms) { - if (termsSet.contains(negatedTerm)) { - return rexBuilder.makeLiteral(false); - } - } - return RexUtil.composeConjunction(rexBuilder, terms, false); - } - - /** Simplifies OR(x, x) into x, and similar. */ - public static RexNode simplifyOr(RexBuilder rexBuilder, RexCall call) { - assert call.getKind() == SqlKind.OR; - final List<RexNode> terms = RelOptUtil.disjunctions(call); - for (int i = 0; i < terms.size(); i++) { - final RexNode term = terms.get(i); - switch (term.getKind()) { - case LITERAL: - if (!RexLiteral.isNullLiteral(term)) { - if (RexLiteral.booleanValue(term)) { - return term; // true - } else { - terms.remove(i); - --i; - } - } - } - } - return RexUtil.composeDisjunction(rexBuilder, terms, false); - } - - private static RexCall negate(RexBuilder rexBuilder, RexCall call) { - switch (call.getKind()) { - case EQUALS: - case NOT_EQUALS: - case LESS_THAN: - case GREATER_THAN: - case LESS_THAN_OR_EQUAL: - case GREATER_THAN_OR_EQUAL: - return (RexCall) rexBuilder.makeCall(op(negate(call.getKind())), call.getOperands()); - } - return null; - } - - private static SqlKind negate(SqlKind kind) { - switch (kind) { - case EQUALS: - return SqlKind.NOT_EQUALS; - case NOT_EQUALS: - return SqlKind.EQUALS; - case LESS_THAN: - return SqlKind.GREATER_THAN_OR_EQUAL; - case GREATER_THAN: - return SqlKind.LESS_THAN_OR_EQUAL; - case LESS_THAN_OR_EQUAL: - return SqlKind.GREATER_THAN; - case GREATER_THAN_OR_EQUAL: - return SqlKind.LESS_THAN; - } - return kind; - } - - private static RexCall invert(RexBuilder rexBuilder, RexCall call) { - switch (call.getKind()) { - case EQUALS: - return (RexCall) rexBuilder.makeCall(SqlStdOperatorTable.EQUALS, - Lists.reverse(call.getOperands())); - case NOT_EQUALS: - return (RexCall) rexBuilder.makeCall(SqlStdOperatorTable.NOT_EQUALS, - Lists.reverse(call.getOperands())); - case LESS_THAN: - return (RexCall) rexBuilder.makeCall(SqlStdOperatorTable.GREATER_THAN, - Lists.reverse(call.getOperands())); - case GREATER_THAN: - return (RexCall) rexBuilder.makeCall(SqlStdOperatorTable.LESS_THAN, - Lists.reverse(call.getOperands())); - case LESS_THAN_OR_EQUAL: - return (RexCall) rexBuilder.makeCall(SqlStdOperatorTable.GREATER_THAN_OR_EQUAL, - Lists.reverse(call.getOperands())); - case GREATER_THAN_OR_EQUAL: - return (RexCall) rexBuilder.makeCall(SqlStdOperatorTable.LESS_THAN_OR_EQUAL, - Lists.reverse(call.getOperands())); - } - return null; - } - - private static SqlOperator op(SqlKind kind) { - switch (kind) { - case IS_FALSE: - return SqlStdOperatorTable.IS_FALSE; - case IS_TRUE: - return SqlStdOperatorTable.IS_TRUE; - case IS_UNKNOWN: - return SqlStdOperatorTable.IS_UNKNOWN; - case IS_NULL: - return SqlStdOperatorTable.IS_NULL; - case IS_NOT_FALSE: - return SqlStdOperatorTable.IS_NOT_FALSE; - case IS_NOT_TRUE: - return SqlStdOperatorTable.IS_NOT_TRUE; - case IS_NOT_NULL: - return SqlStdOperatorTable.IS_NOT_NULL; - case EQUALS: - return SqlStdOperatorTable.EQUALS; - case NOT_EQUALS: - return SqlStdOperatorTable.NOT_EQUALS; - case LESS_THAN: - return SqlStdOperatorTable.LESS_THAN; - case GREATER_THAN: - return SqlStdOperatorTable.GREATER_THAN; - case LESS_THAN_OR_EQUAL: - return SqlStdOperatorTable.LESS_THAN_OR_EQUAL; - case GREATER_THAN_OR_EQUAL: - return SqlStdOperatorTable.GREATER_THAN_OR_EQUAL; - default: - throw new AssertionError(kind); - } - } - - public static SqlKind invert(SqlKind kind) { - switch (kind) { - case EQUALS: - return SqlKind.EQUALS; - case NOT_EQUALS: - return SqlKind.NOT_EQUALS; - case LESS_THAN: - return SqlKind.GREATER_THAN; - case GREATER_THAN: - return SqlKind.LESS_THAN; - case LESS_THAN_OR_EQUAL: - return SqlKind.GREATER_THAN_OR_EQUAL; - case GREATER_THAN_OR_EQUAL: - return SqlKind.LESS_THAN_OR_EQUAL; - } - return null; - } - - public static class ExprSimplifier extends RexShuttle { - private final RexBuilder rexBuilder; - private final boolean unknownAsFalse; - private final Map<RexNode,Boolean> unknownAsFalseMap; - - public ExprSimplifier(RexBuilder rexBuilder, boolean unknownAsFalse) { - this.rexBuilder = rexBuilder; - this.unknownAsFalse = unknownAsFalse; - this.unknownAsFalseMap = new HashMap<>(); - } - - @Override - public RexNode visitCall(RexCall call) { - Boolean unknownAsFalseCall = unknownAsFalse; - if (unknownAsFalseCall) { - switch (call.getKind()) { - case AND: - case CASE: - unknownAsFalseCall = this.unknownAsFalseMap.get(call); - if (unknownAsFalseCall == null) { - // Top operator - unknownAsFalseCall = true; - } - break; - default: - unknownAsFalseCall = false; - } - for (RexNode operand : call.operands) { - this.unknownAsFalseMap.put(operand, unknownAsFalseCall); - } - } - RexNode node = super.visitCall(call); - RexNode simplifiedNode = HiveRexUtil.simplify(rexBuilder, node, unknownAsFalseCall); - if (node == simplifiedNode) { - return node; - } - if (simplifiedNode.getType().equals(call.getType())) { - return simplifiedNode; - } - return rexBuilder.makeCast(call.getType(), simplifiedNode, true); - } - } - -} http://git-wip-us.apache.org/repos/asf/hive/blob/b597ab2a/ql/src/java/org/apache/hadoop/hive/ql/optimizer/calcite/HiveTypeSystemImpl.java ---------------------------------------------------------------------- diff --git a/ql/src/java/org/apache/hadoop/hive/ql/optimizer/calcite/HiveTypeSystemImpl.java b/ql/src/java/org/apache/hadoop/hive/ql/optimizer/calcite/HiveTypeSystemImpl.java index 10fdcc6..279d101 100644 --- a/ql/src/java/org/apache/hadoop/hive/ql/optimizer/calcite/HiveTypeSystemImpl.java +++ b/ql/src/java/org/apache/hadoop/hive/ql/optimizer/calcite/HiveTypeSystemImpl.java @@ -36,8 +36,19 @@ public class HiveTypeSystemImpl extends RelDataTypeSystemImpl { switch (typeName) { case DECIMAL: return getMaxNumericScale(); - case INTERVAL_DAY_TIME: + case INTERVAL_YEAR: + case INTERVAL_MONTH: case INTERVAL_YEAR_MONTH: + case INTERVAL_DAY: + case INTERVAL_DAY_HOUR: + case INTERVAL_DAY_MINUTE: + case INTERVAL_DAY_SECOND: + case INTERVAL_HOUR: + case INTERVAL_HOUR_MINUTE: + case INTERVAL_HOUR_SECOND: + case INTERVAL_MINUTE: + case INTERVAL_MINUTE_SECOND: + case INTERVAL_SECOND: return SqlTypeName.MAX_INTERVAL_FRACTIONAL_SECOND_PRECISION; default: return -1; @@ -58,8 +69,19 @@ public class HiveTypeSystemImpl extends RelDataTypeSystemImpl { return getMaxPrecision(typeName); case DECIMAL: return DEFAULT_DECIMAL_PRECISION; - case INTERVAL_DAY_TIME: + case INTERVAL_YEAR: + case INTERVAL_MONTH: case INTERVAL_YEAR_MONTH: + case INTERVAL_DAY: + case INTERVAL_DAY_HOUR: + case INTERVAL_DAY_MINUTE: + case INTERVAL_DAY_SECOND: + case INTERVAL_HOUR: + case INTERVAL_HOUR_MINUTE: + case INTERVAL_HOUR_SECOND: + case INTERVAL_MINUTE: + case INTERVAL_MINUTE_SECOND: + case INTERVAL_SECOND: return SqlTypeName.DEFAULT_INTERVAL_START_PRECISION; default: return -1; @@ -81,8 +103,19 @@ public class HiveTypeSystemImpl extends RelDataTypeSystemImpl { case TIME: case TIMESTAMP: return MAX_TIMESTAMP_PRECISION; - case INTERVAL_DAY_TIME: + case INTERVAL_YEAR: + case INTERVAL_MONTH: case INTERVAL_YEAR_MONTH: + case INTERVAL_DAY: + case INTERVAL_DAY_HOUR: + case INTERVAL_DAY_MINUTE: + case INTERVAL_DAY_SECOND: + case INTERVAL_HOUR: + case INTERVAL_HOUR_MINUTE: + case INTERVAL_HOUR_SECOND: + case INTERVAL_MINUTE: + case INTERVAL_MINUTE_SECOND: + case INTERVAL_SECOND: return SqlTypeName.MAX_INTERVAL_START_PRECISION; default: return -1; http://git-wip-us.apache.org/repos/asf/hive/blob/b597ab2a/ql/src/java/org/apache/hadoop/hive/ql/optimizer/calcite/cost/HiveDefaultCostModel.java ---------------------------------------------------------------------- diff --git a/ql/src/java/org/apache/hadoop/hive/ql/optimizer/calcite/cost/HiveDefaultCostModel.java b/ql/src/java/org/apache/hadoop/hive/ql/optimizer/calcite/cost/HiveDefaultCostModel.java index badb8ca..40f2cef 100644 --- a/ql/src/java/org/apache/hadoop/hive/ql/optimizer/calcite/cost/HiveDefaultCostModel.java +++ b/ql/src/java/org/apache/hadoop/hive/ql/optimizer/calcite/cost/HiveDefaultCostModel.java @@ -20,6 +20,7 @@ package org.apache.hadoop.hive.ql.optimizer.calcite.cost; import org.apache.calcite.plan.RelOptCost; import org.apache.calcite.rel.RelCollation; import org.apache.calcite.rel.RelDistribution; +import org.apache.calcite.rel.RelDistributions; import org.apache.calcite.rel.metadata.RelMetadataQuery; import org.apache.hadoop.hive.ql.optimizer.calcite.reloperators.HiveAggregate; import org.apache.hadoop.hive.ql.optimizer.calcite.reloperators.HiveJoin; @@ -92,12 +93,12 @@ public class HiveDefaultCostModel extends HiveCostModel { @Override public ImmutableList<RelCollation> getCollation(HiveJoin join) { - return null; + return ImmutableList.of(); } @Override public RelDistribution getDistribution(HiveJoin join) { - return null; + return RelDistributions.SINGLETON; } @Override @@ -117,7 +118,7 @@ public class HiveDefaultCostModel extends HiveCostModel { @Override public Integer getSplitCount(HiveJoin join) { - return null; + return 1; } } http://git-wip-us.apache.org/repos/asf/hive/blob/b597ab2a/ql/src/java/org/apache/hadoop/hive/ql/optimizer/calcite/cost/HiveRelMdCost.java ---------------------------------------------------------------------- diff --git a/ql/src/java/org/apache/hadoop/hive/ql/optimizer/calcite/cost/HiveRelMdCost.java b/ql/src/java/org/apache/hadoop/hive/ql/optimizer/calcite/cost/HiveRelMdCost.java index ed45ab3..cbea307 100644 --- a/ql/src/java/org/apache/hadoop/hive/ql/optimizer/calcite/cost/HiveRelMdCost.java +++ b/ql/src/java/org/apache/hadoop/hive/ql/optimizer/calcite/cost/HiveRelMdCost.java @@ -19,7 +19,10 @@ package org.apache.hadoop.hive.ql.optimizer.calcite.cost; import org.apache.calcite.plan.RelOptCost; import org.apache.calcite.rel.RelNode; +import org.apache.calcite.rel.metadata.BuiltInMetadata; import org.apache.calcite.rel.metadata.ChainedRelMetadataProvider; +import org.apache.calcite.rel.metadata.MetadataDef; +import org.apache.calcite.rel.metadata.MetadataHandler; import org.apache.calcite.rel.metadata.ReflectiveRelMetadataProvider; import org.apache.calcite.rel.metadata.RelMdPercentageOriginalRows; import org.apache.calcite.rel.metadata.RelMetadataProvider; @@ -34,7 +37,7 @@ import com.google.common.collect.ImmutableList; /** * HiveRelMdCost supplies the implementation of cost model. */ -public class HiveRelMdCost { +public class HiveRelMdCost implements MetadataHandler<BuiltInMetadata.NonCumulativeCost> { private final HiveCostModel hiveCostModel; @@ -50,6 +53,11 @@ public class HiveRelMdCost { RelMdPercentageOriginalRows.SOURCE)); } + @Override + public MetadataDef<BuiltInMetadata.NonCumulativeCost> getDef() { + return BuiltInMetadata.NonCumulativeCost.DEF; + } + public RelOptCost getNonCumulativeCost(HiveAggregate aggregate, RelMetadataQuery mq) { return hiveCostModel.getAggregateCost(aggregate); } http://git-wip-us.apache.org/repos/asf/hive/blob/b597ab2a/ql/src/java/org/apache/hadoop/hive/ql/optimizer/calcite/druid/DruidIntervalUtils.java ---------------------------------------------------------------------- diff --git a/ql/src/java/org/apache/hadoop/hive/ql/optimizer/calcite/druid/DruidIntervalUtils.java b/ql/src/java/org/apache/hadoop/hive/ql/optimizer/calcite/druid/DruidIntervalUtils.java deleted file mode 100644 index 82ab4d7..0000000 --- a/ql/src/java/org/apache/hadoop/hive/ql/optimizer/calcite/druid/DruidIntervalUtils.java +++ /dev/null @@ -1,466 +0,0 @@ -/** - * Licensed to the Apache Software Foundation (ASF) under one - * or more contributor license agreements. See the NOTICE file - * distributed with this work for additional information - * regarding copyright ownership. The ASF licenses this file - * to you under the Apache License, Version 2.0 (the - * "License"); you may not use this file except in compliance - * with the License. You may obtain a copy of the License at - * - * http://www.apache.org/licenses/LICENSE-2.0 - * - * Unless required by applicable law or agreed to in writing, software - * distributed under the License is distributed on an "AS IS" BASIS, - * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. - * See the License for the specific language governing permissions and - * limitations under the License. - */ -package org.apache.hadoop.hive.ql.optimizer.calcite.druid; - -import java.sql.Timestamp; -import java.text.DateFormat; -import java.text.ParseException; -import java.util.ArrayList; -import java.util.Arrays; -import java.util.Comparator; -import java.util.Date; -import java.util.Iterator; -import java.util.List; -import java.util.TreeSet; - -import org.apache.calcite.rel.type.RelDataType; -import org.apache.calcite.rex.RexCall; -import org.apache.calcite.rex.RexInputRef; -import org.apache.calcite.rex.RexLiteral; -import org.apache.calcite.rex.RexNode; -import org.apache.calcite.sql.SqlKind; -import org.apache.commons.lang.StringUtils; -import org.joda.time.Interval; -import org.slf4j.Logger; -import org.slf4j.LoggerFactory; - -import com.google.common.base.Function; -import com.google.common.collect.BoundType; -import com.google.common.collect.Lists; -import com.google.common.collect.Range; -import com.google.common.collect.Sets; - -/** - * Utilities for generating intervals from RexNode. - * - * Based on Navis logic implemented on Hive data structures. - * See <a href="https://github.com/druid-io/druid/pull/2880";>Druid PR-2880</a> - * - */ -@SuppressWarnings({"rawtypes","unchecked"}) -public class DruidIntervalUtils { - - protected static final Logger LOG = LoggerFactory.getLogger(DruidIntervalUtils.class); - - - /** - * Given a list of predicates, it generates the equivalent Interval - * (if possible). It assumes that all the predicates in the input - * reference a single column : the timestamp column. - * - * @param conjs list of conditions to use for the transformation - * @return interval representing the conditions in the input list - */ - public static List<Interval> createInterval(RelDataType type, List<RexNode> conjs) { - List<Range> ranges = new ArrayList<>(); - for (RexNode child : conjs) { - List<Range> extractedRanges = extractRanges(type, child, false); - if (extractedRanges == null || extractedRanges.isEmpty()) { - // We could not extract, we bail out - return null; - } - if (ranges.isEmpty()) { - ranges.addAll(extractedRanges); - continue; - } - List<Range> overlapped = Lists.newArrayList(); - for (Range current : ranges) { - for (Range interval : extractedRanges) { - if (current.isConnected(interval)) { - overlapped.add(current.intersection(interval)); - } - } - } - ranges = overlapped; - } - List<Range> compactRanges = condenseRanges(ranges); - LOG.debug("Inferred ranges on interval : " + compactRanges); - return toInterval(compactRanges); - } - - protected static List<Interval> toInterval(List<Range> ranges) { - List<Interval> intervals = Lists.transform(ranges, new Function<Range, Interval>() { - @Override - public Interval apply(Range range) { - if (!range.hasLowerBound() && !range.hasUpperBound()) { - return DruidTable.DEFAULT_INTERVAL; - } - long start = range.hasLowerBound() ? toLong(range.lowerEndpoint()) : - DruidTable.DEFAULT_INTERVAL.getStartMillis(); - long end = range.hasUpperBound() ? toLong(range.upperEndpoint()) : - DruidTable.DEFAULT_INTERVAL.getEndMillis(); - if (range.hasLowerBound() && range.lowerBoundType() == BoundType.OPEN) { - start++; - } - if (range.hasUpperBound() && range.upperBoundType() == BoundType.CLOSED) { - end++; - } - return new Interval(start, end); - } - }); - LOG.info("Converted time ranges " + ranges + " to interval " + intervals); - return intervals; - } - - protected static List<Range> extractRanges(RelDataType type, RexNode node, - boolean withNot) { - switch (node.getKind()) { - case EQUALS: - case LESS_THAN: - case LESS_THAN_OR_EQUAL: - case GREATER_THAN: - case GREATER_THAN_OR_EQUAL: - case BETWEEN: - case IN: - return leafToRanges(type, (RexCall) node, withNot); - - case NOT: - return extractRanges(type, ((RexCall) node).getOperands().get(0), !withNot); - - case OR: - RexCall call = (RexCall) node; - List<Range> intervals = Lists.newArrayList(); - for (RexNode child : call.getOperands()) { - List<Range> extracted = extractRanges(type, child, withNot); - if (extracted != null) { - intervals.addAll(extracted); - } - } - return intervals; - - default: - return null; - } - } - - protected static List<Range> leafToRanges(RelDataType type, RexCall call, - boolean withNot) { - switch (call.getKind()) { - case EQUALS: - case LESS_THAN: - case LESS_THAN_OR_EQUAL: - case GREATER_THAN: - case GREATER_THAN_OR_EQUAL: - { - RexLiteral literal = null; - if (call.getOperands().get(0) instanceof RexInputRef && - call.getOperands().get(1) instanceof RexLiteral) { - literal = extractLiteral(call.getOperands().get(1)); - } else if (call.getOperands().get(0) instanceof RexInputRef && - call.getOperands().get(1).getKind() == SqlKind.CAST) { - literal = extractLiteral(call.getOperands().get(1)); - } else if (call.getOperands().get(1) instanceof RexInputRef && - call.getOperands().get(0) instanceof RexLiteral) { - literal = extractLiteral(call.getOperands().get(0)); - } else if (call.getOperands().get(1) instanceof RexInputRef && - call.getOperands().get(0).getKind() == SqlKind.CAST) { - literal = extractLiteral(call.getOperands().get(0)); - } - if (literal == null) { - return null; - } - Comparable value = literalToType(literal, type); - if (value == null) { - return null; - } - if (call.getKind() == SqlKind.LESS_THAN) { - return Arrays.<Range> asList(withNot ? Range.atLeast(value) : Range.lessThan(value)); - } else if (call.getKind() == SqlKind.LESS_THAN_OR_EQUAL) { - return Arrays.<Range> asList(withNot ? Range.greaterThan(value) : Range.atMost(value)); - } else if (call.getKind() == SqlKind.GREATER_THAN) { - return Arrays.<Range> asList(withNot ? Range.atMost(value) : Range.greaterThan(value)); - } else if (call.getKind() == SqlKind.GREATER_THAN_OR_EQUAL) { - return Arrays.<Range> asList(withNot ? Range.lessThan(value) : Range.atLeast(value)); - } else { //EQUALS - if (!withNot) { - return Arrays.<Range> asList(Range.closed(value, value)); - } - return Arrays.<Range> asList(Range.lessThan(value), Range.greaterThan(value)); - } - } - case BETWEEN: - { - RexLiteral literal1 = extractLiteral(call.getOperands().get(2)); - if (literal1 == null) { - return null; - } - RexLiteral literal2 = extractLiteral(call.getOperands().get(3)); - if (literal2 == null) { - return null; - } - Comparable value1 = literalToType(literal1, type); - Comparable value2 = literalToType(literal2, type); - if (value1 == null || value2 == null) { - return null; - } - boolean inverted = value1.compareTo(value2) > 0; - if (!withNot) { - return Arrays.<Range> asList( - inverted ? Range.closed(value2, value1) : Range.closed(value1, value2)); - } - return Arrays.<Range> asList(Range.lessThan(inverted ? value2 : value1), - Range.greaterThan(inverted ? value1 : value2)); - } - case IN: - { - List<Range> ranges = Lists.newArrayList(); - for (int i = 1; i < call.getOperands().size(); i++) { - RexLiteral literal = extractLiteral(call.getOperands().get(i)); - if (literal == null) { - return null; - } - Comparable element = literalToType(literal, type); - if (element == null) { - return null; - } - if (withNot) { - ranges.addAll( - Arrays.<Range> asList(Range.lessThan(element), Range.greaterThan(element))); - } else { - ranges.add(Range.closed(element, element)); - } - } - return ranges; - } - default: - return null; - } - } - - @SuppressWarnings("incomplete-switch") - protected static Comparable literalToType(RexLiteral literal, RelDataType type) { - // Extract - Object value = null; - switch (literal.getType().getSqlTypeName()) { - case DATE: - case TIME: - case TIMESTAMP: - case INTERVAL_YEAR_MONTH: - case INTERVAL_DAY_TIME: - value = literal.getValue(); - break; - case TINYINT: - case SMALLINT: - case INTEGER: - case BIGINT: - case DOUBLE: - case DECIMAL: - case FLOAT: - case REAL: - case VARCHAR: - case CHAR: - case BOOLEAN: - value = literal.getValue3(); - } - if (value == null) { - return null; - } - - // Convert - switch (type.getSqlTypeName()) { - case BIGINT: - return toLong(value); - case INTEGER: - return toInt(value); - case FLOAT: - return toFloat(value); - case DOUBLE: - return toDouble(value); - case VARCHAR: - case CHAR: - return String.valueOf(value); - case TIMESTAMP: - return toTimestamp(value); - } - return null; - } - - private static RexLiteral extractLiteral(RexNode node) { - RexNode target = node; - if (node.getKind() == SqlKind.CAST) { - target = ((RexCall)node).getOperands().get(0); - } - if (!(target instanceof RexLiteral)) { - return null; - } - return (RexLiteral) target; - } - - private static Comparable toTimestamp(Object literal) { - if (literal instanceof Timestamp) { - return (Timestamp) literal; - } - if (literal instanceof Date) { - return new Timestamp(((Date) literal).getTime()); - } - if (literal instanceof Number) { - return new Timestamp(((Number) literal).longValue()); - } - if (literal instanceof String) { - String string = (String) literal; - if (StringUtils.isNumeric(string)) { - return new Timestamp(Long.valueOf(string)); - } - try { - return Timestamp.valueOf(string); - } catch (NumberFormatException e) { - // ignore - } - } - return null; - } - - private static Long toLong(Object literal) { - if (literal instanceof Number) { - return ((Number) literal).longValue(); - } - if (literal instanceof Date) { - return ((Date) literal).getTime(); - } - if (literal instanceof Timestamp) { - return ((Timestamp) literal).getTime(); - } - if (literal instanceof String) { - try { - return Long.valueOf((String) literal); - } catch (NumberFormatException e) { - // ignore - } - try { - return DateFormat.getDateInstance().parse((String) literal).getTime(); - } catch (ParseException e) { - // best effort. ignore - } - } - return null; - } - - - private static Integer toInt(Object literal) { - if (literal instanceof Number) { - return ((Number) literal).intValue(); - } - if (literal instanceof String) { - try { - return Integer.valueOf((String) literal); - } catch (NumberFormatException e) { - // ignore - } - } - return null; - } - - private static Float toFloat(Object literal) { - if (literal instanceof Number) { - return ((Number) literal).floatValue(); - } - if (literal instanceof String) { - try { - return Float.valueOf((String) literal); - } catch (NumberFormatException e) { - // ignore - } - } - return null; - } - - private static Double toDouble(Object literal) { - if (literal instanceof Number) { - return ((Number) literal).doubleValue(); - } - if (literal instanceof String) { - try { - return Double.valueOf((String) literal); - } catch (NumberFormatException e) { - // ignore - } - } - return null; - } - - protected static List<Range> condenseRanges(List<Range> ranges) { - if (ranges.size() <= 1) { - return ranges; - } - - Comparator<Range> startThenEnd = new Comparator<Range>() { - @Override - public int compare(Range lhs, Range rhs) { - int compare = 0; - if (lhs.hasLowerBound() && rhs.hasLowerBound()) { - compare = lhs.lowerEndpoint().compareTo(rhs.lowerEndpoint()); - } else if (!lhs.hasLowerBound() && rhs.hasLowerBound()) { - compare = -1; - } else if (lhs.hasLowerBound() && !rhs.hasLowerBound()) { - compare = 1; - } - if (compare != 0) { - return compare; - } - if (lhs.hasUpperBound() && rhs.hasUpperBound()) { - compare = lhs.upperEndpoint().compareTo(rhs.upperEndpoint()); - } else if (!lhs.hasUpperBound() && rhs.hasUpperBound()) { - compare = -1; - } else if (lhs.hasUpperBound() && !rhs.hasUpperBound()) { - compare = 1; - } - return compare; - } - }; - - TreeSet<Range> sortedIntervals = Sets.newTreeSet(startThenEnd); - sortedIntervals.addAll(ranges); - - List<Range> retVal = Lists.newArrayList(); - - Iterator<Range> intervalsIter = sortedIntervals.iterator(); - Range currInterval = intervalsIter.next(); - while (intervalsIter.hasNext()) { - Range next = intervalsIter.next(); - if (currInterval.encloses(next)) { - continue; - } - if (mergeable(currInterval, next)) { - currInterval = currInterval.span(next); - } else { - retVal.add(currInterval); - currInterval = next; - } - } - retVal.add(currInterval); - - return retVal; - } - - protected static boolean mergeable(Range range1, Range range2) { - Comparable x1 = range1.upperEndpoint(); - Comparable x2 = range2.lowerEndpoint(); - int compare = x1.compareTo(x2); - return compare > 0 || (compare == 0 && range1.upperBoundType() == BoundType.CLOSED - && range2.lowerBoundType() == BoundType.CLOSED); - } - - public static long extractTotalTime(List<Interval> intervals) { - long totalTime = 0; - for (Interval interval : intervals) { - totalTime += (interval.getEndMillis() - interval.getStartMillis()); - } - return totalTime; - } - -}
