http://git-wip-us.apache.org/repos/asf/flink/blob/2d33c0be/flink-libraries/flink-table/src/main/java/org/apache/calcite/sql2rel/SqlToRelConverter.java ---------------------------------------------------------------------- diff --git a/flink-libraries/flink-table/src/main/java/org/apache/calcite/sql2rel/SqlToRelConverter.java b/flink-libraries/flink-table/src/main/java/org/apache/calcite/sql2rel/SqlToRelConverter.java new file mode 100644 index 0000000..b7f9ce7 --- /dev/null +++ b/flink-libraries/flink-table/src/main/java/org/apache/calcite/sql2rel/SqlToRelConverter.java @@ -0,0 +1,5356 @@ +/* + * 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.calcite.sql2rel; + +/* + * THIS FILE HAS BEEN COPIED FROM THE APACHE CALCITE PROJECT UNTIL CALCITE-1761 IS FIXED. + */ + +import org.apache.calcite.avatica.util.Spaces; +import org.apache.calcite.linq4j.Ord; +import org.apache.calcite.plan.Convention; +import org.apache.calcite.plan.RelOptCluster; +import org.apache.calcite.plan.RelOptPlanner; +import org.apache.calcite.plan.RelOptSamplingParameters; +import org.apache.calcite.plan.RelOptTable; +import org.apache.calcite.plan.RelOptUtil; +import org.apache.calcite.plan.RelTraitSet; +import org.apache.calcite.prepare.Prepare; +import org.apache.calcite.prepare.RelOptTableImpl; +import org.apache.calcite.rel.RelCollation; +import org.apache.calcite.rel.RelCollationTraitDef; +import org.apache.calcite.rel.RelCollations; +import org.apache.calcite.rel.RelFieldCollation; +import org.apache.calcite.rel.RelNode; +import org.apache.calcite.rel.RelRoot; +import org.apache.calcite.rel.SingleRel; +import org.apache.calcite.rel.core.Aggregate; +import org.apache.calcite.rel.core.AggregateCall; +import org.apache.calcite.rel.core.Collect; +import org.apache.calcite.rel.core.CorrelationId; +import org.apache.calcite.rel.core.Filter; +import org.apache.calcite.rel.core.Join; +import org.apache.calcite.rel.core.JoinInfo; +import org.apache.calcite.rel.core.JoinRelType; +import org.apache.calcite.rel.core.Project; +import org.apache.calcite.rel.core.RelFactories; +import org.apache.calcite.rel.core.Sample; +import org.apache.calcite.rel.core.Sort; +import org.apache.calcite.rel.core.Uncollect; +import org.apache.calcite.rel.logical.LogicalAggregate; +import org.apache.calcite.rel.logical.LogicalCorrelate; +import org.apache.calcite.rel.logical.LogicalFilter; +import org.apache.calcite.rel.logical.LogicalIntersect; +import org.apache.calcite.rel.logical.LogicalJoin; +import org.apache.calcite.rel.logical.LogicalMinus; +import org.apache.calcite.rel.logical.LogicalProject; +import org.apache.calcite.rel.logical.LogicalSort; +import org.apache.calcite.rel.logical.LogicalTableFunctionScan; +import org.apache.calcite.rel.logical.LogicalTableModify; +import org.apache.calcite.rel.logical.LogicalTableScan; +import org.apache.calcite.rel.logical.LogicalUnion; +import org.apache.calcite.rel.logical.LogicalValues; +import org.apache.calcite.rel.metadata.JaninoRelMetadataProvider; +import org.apache.calcite.rel.metadata.RelColumnMapping; +import org.apache.calcite.rel.metadata.RelMetadataQuery; +import org.apache.calcite.rel.stream.Delta; +import org.apache.calcite.rel.stream.LogicalDelta; +import org.apache.calcite.rel.type.RelDataType; +import org.apache.calcite.rel.type.RelDataTypeFactory; +import org.apache.calcite.rel.type.RelDataTypeField; +import org.apache.calcite.rex.RexBuilder; +import org.apache.calcite.rex.RexCall; +import org.apache.calcite.rex.RexCallBinding; +import org.apache.calcite.rex.RexCorrelVariable; +import org.apache.calcite.rex.RexDynamicParam; +import org.apache.calcite.rex.RexFieldAccess; +import org.apache.calcite.rex.RexFieldCollation; +import org.apache.calcite.rex.RexInputRef; +import org.apache.calcite.rex.RexLiteral; +import org.apache.calcite.rex.RexNode; +import org.apache.calcite.rex.RexRangeRef; +import org.apache.calcite.rex.RexShuttle; +import org.apache.calcite.rex.RexSubQuery; +import org.apache.calcite.rex.RexUtil; +import org.apache.calcite.rex.RexWindowBound; +import org.apache.calcite.schema.ModifiableTable; +import org.apache.calcite.schema.ModifiableView; +import org.apache.calcite.schema.Table; +import org.apache.calcite.schema.TranslatableTable; +import org.apache.calcite.schema.Wrapper; +import org.apache.calcite.sql.JoinConditionType; +import org.apache.calcite.sql.JoinType; +import org.apache.calcite.sql.SemiJoinType; +import org.apache.calcite.sql.SqlAggFunction; +import org.apache.calcite.sql.SqlBasicCall; +import org.apache.calcite.sql.SqlCall; +import org.apache.calcite.sql.SqlCallBinding; +import org.apache.calcite.sql.SqlDataTypeSpec; +import org.apache.calcite.sql.SqlDelete; +import org.apache.calcite.sql.SqlDynamicParam; +import org.apache.calcite.sql.SqlExplainFormat; +import org.apache.calcite.sql.SqlExplainLevel; +import org.apache.calcite.sql.SqlFunction; +import org.apache.calcite.sql.SqlIdentifier; +import org.apache.calcite.sql.SqlInsert; +import org.apache.calcite.sql.SqlIntervalQualifier; +import org.apache.calcite.sql.SqlJoin; +import org.apache.calcite.sql.SqlKind; +import org.apache.calcite.sql.SqlLiteral; +import org.apache.calcite.sql.SqlMatchRecognize; +import org.apache.calcite.sql.SqlMerge; +import org.apache.calcite.sql.SqlNode; +import org.apache.calcite.sql.SqlNodeList; +import org.apache.calcite.sql.SqlNumericLiteral; +import org.apache.calcite.sql.SqlOperator; +import org.apache.calcite.sql.SqlOperatorTable; +import org.apache.calcite.sql.SqlOrderBy; +import org.apache.calcite.sql.SqlSampleSpec; +import org.apache.calcite.sql.SqlSelect; +import org.apache.calcite.sql.SqlSelectKeyword; +import org.apache.calcite.sql.SqlSetOperator; +import org.apache.calcite.sql.SqlUnnestOperator; +import org.apache.calcite.sql.SqlUpdate; +import org.apache.calcite.sql.SqlUtil; +import org.apache.calcite.sql.SqlValuesOperator; +import org.apache.calcite.sql.SqlWindow; +import org.apache.calcite.sql.SqlWith; +import org.apache.calcite.sql.SqlWithItem; +import org.apache.calcite.sql.fun.SqlCountAggFunction; +import org.apache.calcite.sql.fun.SqlInOperator; +import org.apache.calcite.sql.fun.SqlRowOperator; +import org.apache.calcite.sql.fun.SqlStdOperatorTable; +import org.apache.calcite.sql.parser.SqlParserPos; +import org.apache.calcite.sql.type.SqlReturnTypeInference; +import org.apache.calcite.sql.type.SqlTypeName; +import org.apache.calcite.sql.type.SqlTypeUtil; +import org.apache.calcite.sql.type.TableFunctionReturnTypeInference; +import org.apache.calcite.sql.util.SqlBasicVisitor; +import org.apache.calcite.sql.util.SqlVisitor; +import org.apache.calcite.sql.validate.AggregatingSelectScope; +import org.apache.calcite.sql.validate.CollectNamespace; +import org.apache.calcite.sql.validate.DelegatingScope; +import org.apache.calcite.sql.validate.ListScope; +import org.apache.calcite.sql.validate.ParameterScope; +import org.apache.calcite.sql.validate.SelectScope; +import org.apache.calcite.sql.validate.SqlMonotonicity; +import org.apache.calcite.sql.validate.SqlNameMatcher; +import org.apache.calcite.sql.validate.SqlQualified; +import org.apache.calcite.sql.validate.SqlUserDefinedTableFunction; +import org.apache.calcite.sql.validate.SqlUserDefinedTableMacro; +import org.apache.calcite.sql.validate.SqlValidator; +import org.apache.calcite.sql.validate.SqlValidatorImpl; +import org.apache.calcite.sql.validate.SqlValidatorNamespace; +import org.apache.calcite.sql.validate.SqlValidatorScope; +import org.apache.calcite.sql.validate.SqlValidatorTable; +import org.apache.calcite.sql.validate.SqlValidatorUtil; +import org.apache.calcite.tools.RelBuilder; +import org.apache.calcite.util.ImmutableBitSet; +import org.apache.calcite.util.ImmutableIntList; +import org.apache.calcite.util.Litmus; +import org.apache.calcite.util.NlsString; +import org.apache.calcite.util.NumberUtil; +import org.apache.calcite.util.Pair; +import org.apache.calcite.util.Util; +import org.apache.calcite.util.trace.CalciteTrace; + +import com.google.common.base.Function; +import org.apache.flink.util.Preconditions; +import com.google.common.collect.ImmutableList; +import com.google.common.collect.ImmutableList.Builder; +import com.google.common.collect.ImmutableMap; +import com.google.common.collect.ImmutableSet; +import com.google.common.collect.Iterables; +import com.google.common.collect.Lists; +import com.google.common.collect.Maps; + +import org.slf4j.Logger; + +import java.lang.reflect.Type; +import java.math.BigDecimal; +import java.util.AbstractList; +import java.util.ArrayDeque; +import java.util.ArrayList; +import java.util.Collection; +import java.util.Collections; +import java.util.Deque; +import java.util.EnumSet; +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 java.util.TreeSet; + +import static org.apache.calcite.sql.SqlUtil.stripAs; +import static org.apache.calcite.util.Static.RESOURCE; + +/** + * Converts a SQL parse tree (consisting of + * {@link org.apache.calcite.sql.SqlNode} objects) into a relational algebra + * expression (consisting of {@link org.apache.calcite.rel.RelNode} objects). + * + * <p>The public entry points are: {@link #convertQuery}, + * {@link #convertExpression(SqlNode)}. + */ +public class SqlToRelConverter { + //~ Static fields/initializers --------------------------------------------- + + protected static final Logger SQL2REL_LOGGER = + CalciteTrace.getSqlToRelTracer(); + + private static final BigDecimal TWO = BigDecimal.valueOf(2L); + + /** Size of the smallest IN list that will be converted to a semijoin to a + * static table. */ + public static final int DEFAULT_IN_SUB_QUERY_THRESHOLD = 20; + + @Deprecated // to be removed before 2.0 + public static final int DEFAULT_IN_SUBQUERY_THRESHOLD = + DEFAULT_IN_SUB_QUERY_THRESHOLD; + + //~ Instance fields -------------------------------------------------------- + + protected final SqlValidator validator; + protected final RexBuilder rexBuilder; + protected final Prepare.CatalogReader catalogReader; + protected final RelOptCluster cluster; + private SubQueryConverter subQueryConverter; + protected final List<RelNode> leaves = new ArrayList<>(); + private final List<SqlDynamicParam> dynamicParamSqlNodes = new ArrayList<>(); + private final SqlOperatorTable opTab; + protected final RelDataTypeFactory typeFactory; + private final SqlNodeToRexConverter exprConverter; + private int explainParamCount; + public final SqlToRelConverter.Config config; + + /** + * Fields used in name resolution for correlated sub-queries. + */ + private final Map<CorrelationId, DeferredLookup> mapCorrelToDeferred = + new HashMap<>(); + + /** + * Stack of names of datasets requested by the <code> + * TABLE(SAMPLE(<datasetName>, <query>))</code> construct. + */ + private final Deque<String> datasetStack = new ArrayDeque<>(); + + /** + * Mapping of non-correlated sub-queries that have been converted to their + * equivalent constants. Used to avoid re-evaluating the sub-query if it's + * already been evaluated. + */ + private final Map<SqlNode, RexNode> mapConvertedNonCorrSubqs = + new HashMap<>(); + + public final RelOptTable.ViewExpander viewExpander; + + //~ Constructors ----------------------------------------------------------- + /** + * Creates a converter. + * + * @param viewExpander Preparing statement + * @param validator Validator + * @param catalogReader Schema + * @param planner Planner + * @param rexBuilder Rex builder + * @param convertletTable Expression converter + */ + @Deprecated // to be removed before 2.0 + public SqlToRelConverter( + RelOptTable.ViewExpander viewExpander, + SqlValidator validator, + Prepare.CatalogReader catalogReader, + RelOptPlanner planner, + RexBuilder rexBuilder, + SqlRexConvertletTable convertletTable) { + this(viewExpander, validator, catalogReader, + RelOptCluster.create(planner, rexBuilder), convertletTable, + Config.DEFAULT); + } + + @Deprecated // to be removed before 2.0 + public SqlToRelConverter( + RelOptTable.ViewExpander viewExpander, + SqlValidator validator, + Prepare.CatalogReader catalogReader, + RelOptCluster cluster, + SqlRexConvertletTable convertletTable) { + this(viewExpander, validator, catalogReader, cluster, convertletTable, + Config.DEFAULT); + } + + /* Creates a converter. */ + public SqlToRelConverter( + RelOptTable.ViewExpander viewExpander, + SqlValidator validator, + Prepare.CatalogReader catalogReader, + RelOptCluster cluster, + SqlRexConvertletTable convertletTable, + Config config) { + this.viewExpander = viewExpander; + this.opTab = + (validator + == null) ? SqlStdOperatorTable.instance() + : validator.getOperatorTable(); + this.validator = validator; + this.catalogReader = catalogReader; + this.subQueryConverter = new NoOpSubQueryConverter(); + this.rexBuilder = cluster.getRexBuilder(); + this.typeFactory = rexBuilder.getTypeFactory(); + this.cluster = Preconditions.checkNotNull(cluster); + this.exprConverter = new SqlNodeToRexConverterImpl(convertletTable); + this.explainParamCount = 0; + this.config = new ConfigBuilder().withConfig(config).build(); + } + + //~ Methods ---------------------------------------------------------------- + + /** + * @return the RelOptCluster in use. + */ + public RelOptCluster getCluster() { + return cluster; + } + + /** + * Returns the row-expression builder. + */ + public RexBuilder getRexBuilder() { + return rexBuilder; + } + + /** + * Returns the number of dynamic parameters encountered during translation; + * this must only be called after {@link #convertQuery}. + * + * @return number of dynamic parameters + */ + public int getDynamicParamCount() { + return dynamicParamSqlNodes.size(); + } + + /** + * Returns the type inferred for a dynamic parameter. + * + * @param index 0-based index of dynamic parameter + * @return inferred type, never null + */ + public RelDataType getDynamicParamType(int index) { + SqlNode sqlNode = dynamicParamSqlNodes.get(index); + if (sqlNode == null) { + throw Util.needToImplement("dynamic param type inference"); + } + return validator.getValidatedNodeType(sqlNode); + } + + /** + * Returns the current count of the number of dynamic parameters in an + * EXPLAIN PLAN statement. + * + * @param increment if true, increment the count + * @return the current count before the optional increment + */ + public int getDynamicParamCountInExplain(boolean increment) { + int retVal = explainParamCount; + if (increment) { + ++explainParamCount; + } + return retVal; + } + + /** + * @return mapping of non-correlated sub-queries that have been converted to + * the constants that they evaluate to + */ + public Map<SqlNode, RexNode> getMapConvertedNonCorrSubqs() { + return mapConvertedNonCorrSubqs; + } + + /** + * Adds to the current map of non-correlated converted sub-queries the + * elements from another map that contains non-correlated sub-queries that + * have been converted by another SqlToRelConverter. + * + * @param alreadyConvertedNonCorrSubqs the other map + */ + public void addConvertedNonCorrSubqs( + Map<SqlNode, RexNode> alreadyConvertedNonCorrSubqs) { + mapConvertedNonCorrSubqs.putAll(alreadyConvertedNonCorrSubqs); + } + + /** + * Sets a new SubQueryConverter. To have any effect, this must be called + * before any convert method. + * + * @param converter new SubQueryConverter + */ + public void setSubQueryConverter(SubQueryConverter converter) { + subQueryConverter = converter; + } + + /** + * Sets the number of dynamic parameters in the current EXPLAIN PLAN + * statement. + * + * @param explainParamCount number of dynamic parameters in the statement + */ + public void setDynamicParamCountInExplain(int explainParamCount) { + assert config.isExplain(); + this.explainParamCount = explainParamCount; + } + + private void checkConvertedType(SqlNode query, RelNode result) { + if (query.isA(SqlKind.DML)) { + return; + } + // Verify that conversion from SQL to relational algebra did + // not perturb any type information. (We can't do this if the + // SQL statement is something like an INSERT which has no + // validator type information associated with its result, + // hence the namespace check above.) + final List<RelDataTypeField> validatedFields = + validator.getValidatedNodeType(query).getFieldList(); + final RelDataType validatedRowType = + validator.getTypeFactory().createStructType( + Pair.right(validatedFields), + SqlValidatorUtil.uniquify(Pair.left(validatedFields), + catalogReader.nameMatcher().isCaseSensitive())); + + final List<RelDataTypeField> convertedFields = + result.getRowType().getFieldList().subList(0, validatedFields.size()); + final RelDataType convertedRowType = + validator.getTypeFactory().createStructType(convertedFields); + + if (!RelOptUtil.equal("validated row type", validatedRowType, + "converted row type", convertedRowType, Litmus.IGNORE)) { + throw new AssertionError("Conversion to relational algebra failed to " + + "preserve datatypes:\n" + + "validated type:\n" + + validatedRowType.getFullTypeString() + + "\nconverted type:\n" + + convertedRowType.getFullTypeString() + + "\nrel:\n" + + RelOptUtil.toString(result)); + } + } + + public RelNode flattenTypes( + RelNode rootRel, + boolean restructure) { + RelStructuredTypeFlattener typeFlattener = + new RelStructuredTypeFlattener(rexBuilder, createToRelContext(), restructure); + return typeFlattener.rewrite(rootRel); + } + + /** + * If sub-query is correlated and decorrelation is enabled, performs + * decorrelation. + * + * @param query Query + * @param rootRel Root relational expression + * @return New root relational expression after decorrelation + */ + public RelNode decorrelate(SqlNode query, RelNode rootRel) { + if (!enableDecorrelation()) { + return rootRel; + } + final RelNode result = decorrelateQuery(rootRel); + if (result != rootRel) { + checkConvertedType(query, result); + } + return result; + } + + /** + * Walks over a tree of relational expressions, replacing each + * {@link RelNode} with a 'slimmed down' relational expression that projects + * only the fields required by its consumer. + * + * <p>This may make things easier for the optimizer, by removing crud that + * would expand the search space, but is difficult for the optimizer itself + * to do it, because optimizer rules must preserve the number and type of + * fields. Hence, this transform that operates on the entire tree, similar + * to the {@link RelStructuredTypeFlattener type-flattening transform}. + * + * <p>Currently this functionality is disabled in farrago/luciddb; the + * default implementation of this method does nothing. + * + * @param ordered Whether the relational expression must produce results in + * a particular order (typically because it has an ORDER BY at top level) + * @param rootRel Relational expression that is at the root of the tree + * @return Trimmed relational expression + */ + public RelNode trimUnusedFields(boolean ordered, RelNode rootRel) { + // Trim fields that are not used by their consumer. + if (isTrimUnusedFields()) { + final RelFieldTrimmer trimmer = newFieldTrimmer(); + final List<RelCollation> collations = + rootRel.getTraitSet().getTraits(RelCollationTraitDef.INSTANCE); + rootRel = trimmer.trim(rootRel); + if (!ordered + && collations != null + && !collations.isEmpty() + && !collations.equals(ImmutableList.of(RelCollations.EMPTY))) { + final RelTraitSet traitSet = rootRel.getTraitSet() + .replace(RelCollationTraitDef.INSTANCE, collations); + rootRel = rootRel.copy(traitSet, rootRel.getInputs()); + } + if (SQL2REL_LOGGER.isDebugEnabled()) { + SQL2REL_LOGGER.debug( + RelOptUtil.dumpPlan("Plan after trimming unused fields", rootRel, + SqlExplainFormat.TEXT, SqlExplainLevel.EXPPLAN_ATTRIBUTES)); + } + } + return rootRel; + } + + /** + * Creates a RelFieldTrimmer. + * + * @return Field trimmer + */ + protected RelFieldTrimmer newFieldTrimmer() { + final RelBuilder relBuilder = + RelFactories.LOGICAL_BUILDER.create(cluster, null); + return new RelFieldTrimmer(validator, relBuilder); + } + + /** + * Converts an unvalidated query's parse tree into a relational expression. + * + * @param query Query to convert + * @param needsValidation Whether to validate the query before converting; + * <code>false</code> if the query has already been + * validated. + * @param top Whether the query is top-level, say if its result + * will become a JDBC result set; <code>false</code> if + * the query will be part of a view. + */ + public RelRoot convertQuery( + SqlNode query, + final boolean needsValidation, + final boolean top) { + if (needsValidation) { + query = validator.validate(query); + } + + RelMetadataQuery.THREAD_PROVIDERS.set( + JaninoRelMetadataProvider.of(cluster.getMetadataProvider())); + RelNode result = convertQueryRecursive(query, top, null).rel; + if (top) { + if (isStream(query)) { + result = new LogicalDelta(cluster, result.getTraitSet(), result); + } + } + RelCollation collation = RelCollations.EMPTY; + if (!query.isA(SqlKind.DML)) { + if (isOrdered(query)) { + collation = requiredCollation(result); + } + } + checkConvertedType(query, result); + + if (SQL2REL_LOGGER.isDebugEnabled()) { + SQL2REL_LOGGER.debug( + RelOptUtil.dumpPlan("Plan after converting SqlNode to RelNode", + result, SqlExplainFormat.TEXT, + SqlExplainLevel.EXPPLAN_ATTRIBUTES)); + } + + final RelDataType validatedRowType = validator.getValidatedNodeType(query); + return RelRoot.of(result, validatedRowType, query.getKind()) + .withCollation(collation); + } + + private static boolean isStream(SqlNode query) { + return query instanceof SqlSelect + && ((SqlSelect) query).isKeywordPresent(SqlSelectKeyword.STREAM); + } + + public static boolean isOrdered(SqlNode query) { + switch (query.getKind()) { + case SELECT: + return ((SqlSelect) query).getOrderList() != null + && ((SqlSelect) query).getOrderList().size() > 0; + case WITH: + return isOrdered(((SqlWith) query).body); + case ORDER_BY: + return ((SqlOrderBy) query).orderList.size() > 0; + default: + return false; + } + } + + private RelCollation requiredCollation(RelNode r) { + if (r instanceof Sort) { + return ((Sort) r).collation; + } + if (r instanceof Project) { + return requiredCollation(((Project) r).getInput()); + } + if (r instanceof Delta) { + return requiredCollation(((Delta) r).getInput()); + } + throw new AssertionError(); + } + + /** + * Converts a SELECT statement's parse tree into a relational expression. + */ + public RelNode convertSelect(SqlSelect select, boolean top) { + final SqlValidatorScope selectScope = validator.getWhereScope(select); + final Blackboard bb = createBlackboard(selectScope, null, top); + convertSelectImpl(bb, select); + return bb.root; + } + + /** + * Factory method for creating translation workspace. + */ + protected Blackboard createBlackboard(SqlValidatorScope scope, + Map<String, RexNode> nameToNodeMap, boolean top) { + return new Blackboard(scope, nameToNodeMap, top); + } + + /** + * Implementation of {@link #convertSelect(SqlSelect, boolean)}; + * derived class may override. + */ + protected void convertSelectImpl( + final Blackboard bb, + SqlSelect select) { + convertFrom( + bb, + select.getFrom()); + convertWhere( + bb, + select.getWhere()); + + final List<SqlNode> orderExprList = new ArrayList<>(); + final List<RelFieldCollation> collationList = new ArrayList<>(); + gatherOrderExprs( + bb, + select, + select.getOrderList(), + orderExprList, + collationList); + final RelCollation collation = + cluster.traitSet().canonize(RelCollations.of(collationList)); + + if (validator.isAggregate(select)) { + convertAgg( + bb, + select, + orderExprList); + } else { + convertSelectList( + bb, + select, + orderExprList); + } + + if (select.isDistinct()) { + distinctify(bb, true); + } + convertOrder( + select, bb, collation, orderExprList, select.getOffset(), + select.getFetch()); + bb.setRoot(bb.root, true); + } + + /** + * Having translated 'SELECT ... FROM ... [GROUP BY ...] [HAVING ...]', adds + * a relational expression to make the results unique. + * + * <p>If the SELECT clause contains duplicate expressions, adds + * {@link org.apache.calcite.rel.logical.LogicalProject}s so that we are + * grouping on the minimal set of keys. The performance gain isn't huge, but + * it is difficult to detect these duplicate expressions later. + * + * @param bb Blackboard + * @param checkForDupExprs Check for duplicate expressions + */ + private void distinctify( + Blackboard bb, + boolean checkForDupExprs) { + // Look for duplicate expressions in the project. + // Say we have 'select x, y, x, z'. + // Then dups will be {[2, 0]} + // and oldToNew will be {[0, 0], [1, 1], [2, 0], [3, 2]} + RelNode rel = bb.root; + if (checkForDupExprs && (rel instanceof LogicalProject)) { + LogicalProject project = (LogicalProject) rel; + final List<RexNode> projectExprs = project.getProjects(); + final List<Integer> origins = new ArrayList<>(); + int dupCount = 0; + for (int i = 0; i < projectExprs.size(); i++) { + int x = findExpr(projectExprs.get(i), projectExprs, i); + if (x >= 0) { + origins.add(x); + ++dupCount; + } else { + origins.add(i); + } + } + if (dupCount == 0) { + distinctify(bb, false); + return; + } + + final Map<Integer, Integer> squished = Maps.newHashMap(); + final List<RelDataTypeField> fields = rel.getRowType().getFieldList(); + final List<Pair<RexNode, String>> newProjects = Lists.newArrayList(); + for (int i = 0; i < fields.size(); i++) { + if (origins.get(i) == i) { + squished.put(i, newProjects.size()); + newProjects.add(RexInputRef.of2(i, fields)); + } + } + rel = + LogicalProject.create(rel, Pair.left(newProjects), + Pair.right(newProjects)); + bb.root = rel; + distinctify(bb, false); + rel = bb.root; + + // Create the expressions to reverse the mapping. + // Project($0, $1, $0, $2). + final List<Pair<RexNode, String>> undoProjects = Lists.newArrayList(); + for (int i = 0; i < fields.size(); i++) { + final int origin = origins.get(i); + RelDataTypeField field = fields.get(i); + undoProjects.add( + Pair.of( + (RexNode) new RexInputRef( + squished.get(origin), field.getType()), + field.getName())); + } + + rel = + LogicalProject.create(rel, Pair.left(undoProjects), + Pair.right(undoProjects)); + bb.setRoot( + rel, + false); + + return; + } + + // Usual case: all of the expressions in the SELECT clause are + // different. + final ImmutableBitSet groupSet = + ImmutableBitSet.range(rel.getRowType().getFieldCount()); + rel = + createAggregate(bb, false, groupSet, ImmutableList.of(groupSet), + ImmutableList.<AggregateCall>of()); + + bb.setRoot( + rel, + false); + } + + private int findExpr(RexNode seek, List<RexNode> exprs, int count) { + for (int i = 0; i < count; i++) { + RexNode expr = exprs.get(i); + if (expr.toString().equals(seek.toString())) { + return i; + } + } + return -1; + } + + /** + * Converts a query's ORDER BY clause, if any. + * + * @param select Query + * @param bb Blackboard + * @param collation Collation list + * @param orderExprList Method populates this list with orderBy expressions + * not present in selectList + * @param offset Expression for number of rows to discard before + * returning first row + * @param fetch Expression for number of rows to fetch + */ + protected void convertOrder( + SqlSelect select, + Blackboard bb, + RelCollation collation, + List<SqlNode> orderExprList, + SqlNode offset, + SqlNode fetch) { + if (select.getOrderList() == null + || select.getOrderList().getList().isEmpty()) { + assert collation.getFieldCollations().isEmpty(); + if ((offset == null + || ((SqlLiteral) offset).bigDecimalValue().equals(BigDecimal.ZERO)) + && fetch == null) { + return; + } + } + + // Create a sorter using the previously constructed collations. + bb.setRoot( + LogicalSort.create(bb.root, collation, + offset == null ? null : convertExpression(offset), + fetch == null ? null : convertExpression(fetch)), + false); + + // If extra expressions were added to the project list for sorting, + // add another project to remove them. But make the collation empty, because + // we can't represent the real collation. + // + // If it is the top node, use the real collation, but don't trim fields. + if (orderExprList.size() > 0 && !bb.top) { + final List<RexNode> exprs = new ArrayList<>(); + final RelDataType rowType = bb.root.getRowType(); + final int fieldCount = + rowType.getFieldCount() - orderExprList.size(); + for (int i = 0; i < fieldCount; i++) { + exprs.add(rexBuilder.makeInputRef(bb.root, i)); + } + bb.setRoot( + LogicalProject.create(bb.root, exprs, + rowType.getFieldNames().subList(0, fieldCount)), + false); + } + } + + /** + * Returns whether a given node contains a {@link SqlInOperator}. + * + * @param node a RexNode tree + */ + private static boolean containsInOperator( + SqlNode node) { + try { + SqlVisitor<Void> visitor = + new SqlBasicVisitor<Void>() { + public Void visit(SqlCall call) { + if (call.getOperator() instanceof SqlInOperator) { + throw new Util.FoundOne(call); + } + return super.visit(call); + } + }; + node.accept(visitor); + return false; + } catch (Util.FoundOne e) { + Util.swallow(e, null); + return true; + } + } + + /** + * Push down all the NOT logical operators into any IN/NOT IN operators. + * + * @param scope Scope where {@code sqlNode} occurs + * @param sqlNode the root node from which to look for NOT operators + * @return the transformed SqlNode representation with NOT pushed down. + */ + private static SqlNode pushDownNotForIn(SqlValidatorScope scope, + SqlNode sqlNode) { + if ((sqlNode instanceof SqlCall) && containsInOperator(sqlNode)) { + SqlCall sqlCall = (SqlCall) sqlNode; + if ((sqlCall.getOperator() == SqlStdOperatorTable.AND) + || (sqlCall.getOperator() == SqlStdOperatorTable.OR)) { + SqlNode[] sqlOperands = ((SqlBasicCall) sqlCall).operands; + for (int i = 0; i < sqlOperands.length; i++) { + sqlOperands[i] = pushDownNotForIn(scope, sqlOperands[i]); + } + return reg(scope, sqlNode); + } else if (sqlCall.getOperator() == SqlStdOperatorTable.NOT) { + SqlNode childNode = sqlCall.operand(0); + assert childNode instanceof SqlCall; + SqlBasicCall childSqlCall = (SqlBasicCall) childNode; + if (childSqlCall.getOperator() == SqlStdOperatorTable.AND) { + SqlNode[] andOperands = childSqlCall.getOperands(); + SqlNode[] orOperands = new SqlNode[andOperands.length]; + for (int i = 0; i < orOperands.length; i++) { + orOperands[i] = reg(scope, + SqlStdOperatorTable.NOT.createCall(SqlParserPos.ZERO, + andOperands[i])); + } + for (int i = 0; i < orOperands.length; i++) { + orOperands[i] = pushDownNotForIn(scope, orOperands[i]); + } + return reg(scope, + SqlStdOperatorTable.OR.createCall(SqlParserPos.ZERO, + orOperands[0], orOperands[1])); + } else if (childSqlCall.getOperator() == SqlStdOperatorTable.OR) { + SqlNode[] orOperands = childSqlCall.getOperands(); + SqlNode[] andOperands = new SqlNode[orOperands.length]; + for (int i = 0; i < andOperands.length; i++) { + andOperands[i] = reg(scope, + SqlStdOperatorTable.NOT.createCall(SqlParserPos.ZERO, + orOperands[i])); + } + for (int i = 0; i < andOperands.length; i++) { + andOperands[i] = pushDownNotForIn(scope, andOperands[i]); + } + return reg(scope, + SqlStdOperatorTable.AND.createCall(SqlParserPos.ZERO, + andOperands[0], andOperands[1])); + } else if (childSqlCall.getOperator() == SqlStdOperatorTable.NOT) { + SqlNode[] notOperands = childSqlCall.getOperands(); + assert notOperands.length == 1; + return pushDownNotForIn(scope, notOperands[0]); + } else if (childSqlCall.getOperator() instanceof SqlInOperator) { + SqlNode[] inOperands = childSqlCall.getOperands(); + SqlInOperator inOp = + (SqlInOperator) childSqlCall.getOperator(); + if (inOp.isNotIn()) { + return reg(scope, + SqlStdOperatorTable.IN.createCall(SqlParserPos.ZERO, + inOperands[0], inOperands[1])); + } else { + return reg(scope, + SqlStdOperatorTable.NOT_IN.createCall(SqlParserPos.ZERO, + inOperands[0], inOperands[1])); + } + } else { + // childSqlCall is "leaf" node in a logical expression tree + // (only considering AND, OR, NOT) + return sqlNode; + } + } else { + // sqlNode is "leaf" node in a logical expression tree + // (only considering AND, OR, NOT) + return sqlNode; + } + } else { + // tree rooted at sqlNode does not contain inOperator + return sqlNode; + } + } + + /** Registers with the validator a {@link SqlNode} that has been created + * during the Sql-to-Rel process. */ + private static SqlNode reg(SqlValidatorScope scope, SqlNode e) { + scope.getValidator().deriveType(scope, e); + return e; + } + + /** + * Converts a WHERE clause. + * + * @param bb Blackboard + * @param where WHERE clause, may be null + */ + private void convertWhere( + final Blackboard bb, + final SqlNode where) { + if (where == null) { + return; + } + SqlNode newWhere = pushDownNotForIn(bb.scope, where); + replaceSubQueries(bb, newWhere, RelOptUtil.Logic.UNKNOWN_AS_FALSE); + final RexNode convertedWhere = bb.convertExpression(newWhere); + + // only allocate filter if the condition is not TRUE + if (convertedWhere.isAlwaysTrue()) { + return; + } + + final RelFactories.FilterFactory factory = + RelFactories.DEFAULT_FILTER_FACTORY; + final RelNode filter = factory.createFilter(bb.root, convertedWhere); + final RelNode r; + final CorrelationUse p = getCorrelationUse(bb, filter); + if (p != null) { + assert p.r instanceof Filter; + Filter f = (Filter) p.r; + r = LogicalFilter.create(f.getInput(), f.getCondition(), + ImmutableSet.of(p.id)); + } else { + r = filter; + } + + bb.setRoot(r, false); + } + + private void replaceSubQueries( + final Blackboard bb, + final SqlNode expr, + RelOptUtil.Logic logic) { + findSubQueries(bb, expr, logic, false); + for (SubQuery node : bb.subQueryList) { + substituteSubQuery(bb, node); + } + } + + private void substituteSubQuery(Blackboard bb, SubQuery subQuery) { + final RexNode expr = subQuery.expr; + if (expr != null) { + // Already done. + return; + } + + final SqlBasicCall call; + final RelNode rel; + final SqlNode query; + final RelOptUtil.Exists converted; + switch (subQuery.node.getKind()) { + case CURSOR: + convertCursor(bb, subQuery); + return; + + case MULTISET_QUERY_CONSTRUCTOR: + case MULTISET_VALUE_CONSTRUCTOR: + case ARRAY_QUERY_CONSTRUCTOR: + rel = convertMultisets(ImmutableList.of(subQuery.node), bb); + subQuery.expr = bb.register(rel, JoinRelType.INNER); + return; + + case IN: + call = (SqlBasicCall) subQuery.node; + query = call.operand(1); + if (!config.isExpand() && !(query instanceof SqlNodeList)) { + return; + } + final SqlNode leftKeyNode = call.operand(0); + + final List<RexNode> leftKeys; + switch (leftKeyNode.getKind()) { + case ROW: + leftKeys = Lists.newArrayList(); + for (SqlNode sqlExpr : ((SqlBasicCall) leftKeyNode).getOperandList()) { + leftKeys.add(bb.convertExpression(sqlExpr)); + } + break; + default: + leftKeys = ImmutableList.of(bb.convertExpression(leftKeyNode)); + } + + final boolean notIn = ((SqlInOperator) call.getOperator()).isNotIn(); + if (query instanceof SqlNodeList) { + SqlNodeList valueList = (SqlNodeList) query; + if (!containsNullLiteral(valueList) + && valueList.size() < config.getInSubQueryThreshold()) { + // We're under the threshold, so convert to OR. + subQuery.expr = + convertInToOr( + bb, + leftKeys, + valueList, + notIn); + return; + } + + // Otherwise, let convertExists translate + // values list into an inline table for the + // reference to Q below. + } + + // Project out the search columns from the left side + + // Q1: + // "select from emp where emp.deptno in (select col1 from T)" + // + // is converted to + // + // "select from + // emp inner join (select distinct col1 from T)) q + // on emp.deptno = q.col1 + // + // Q2: + // "select from emp where emp.deptno not in (Q)" + // + // is converted to + // + // "select from + // emp left outer join (select distinct col1, TRUE from T) q + // on emp.deptno = q.col1 + // where emp.deptno <> null + // and q.indicator <> TRUE" + // + final RelDataType targetRowType = + SqlTypeUtil.promoteToRowType(typeFactory, + validator.getValidatedNodeType(leftKeyNode), null); + converted = + convertExists(query, RelOptUtil.SubQueryType.IN, subQuery.logic, + notIn, targetRowType); + if (converted.indicator) { + // Generate + // emp CROSS JOIN (SELECT COUNT(*) AS c, + // COUNT(deptno) AS ck FROM dept) + final RelDataType longType = + typeFactory.createSqlType(SqlTypeName.BIGINT); + final RelNode seek = converted.r.getInput(0); // fragile + final int keyCount = leftKeys.size(); + final List<Integer> args = ImmutableIntList.range(0, keyCount); + LogicalAggregate aggregate = + LogicalAggregate.create(seek, false, ImmutableBitSet.of(), null, + ImmutableList.of( + AggregateCall.create(SqlStdOperatorTable.COUNT, false, + ImmutableList.<Integer>of(), -1, longType, null), + AggregateCall.create(SqlStdOperatorTable.COUNT, false, + args, -1, longType, null))); + LogicalJoin join = + LogicalJoin.create(bb.root, aggregate, rexBuilder.makeLiteral(true), + ImmutableSet.<CorrelationId>of(), JoinRelType.INNER); + bb.setRoot(join, false); + } + final RexNode rex = + bb.register(converted.r, + converted.outerJoin ? JoinRelType.LEFT : JoinRelType.INNER, + leftKeys); + + RelOptUtil.Logic logic = subQuery.logic; + switch (logic) { + case TRUE_FALSE_UNKNOWN: + case UNKNOWN_AS_TRUE: + if (!converted.indicator) { + logic = RelOptUtil.Logic.TRUE_FALSE; + } + } + subQuery.expr = translateIn(logic, bb.root, rex); + if (notIn) { + subQuery.expr = + rexBuilder.makeCall(SqlStdOperatorTable.NOT, subQuery.expr); + } + return; + + case EXISTS: + // "select from emp where exists (select a from T)" + // + // is converted to the following if the sub-query is correlated: + // + // "select from emp left outer join (select AGG_TRUE() as indicator + // from T group by corr_var) q where q.indicator is true" + // + // If there is no correlation, the expression is replaced with a + // boolean indicating whether the sub-query returned 0 or >= 1 row. + call = (SqlBasicCall) subQuery.node; + query = call.operand(0); + if (!config.isExpand()) { + return; + } + converted = convertExists(query, RelOptUtil.SubQueryType.EXISTS, + subQuery.logic, true, null); + assert !converted.indicator; + if (convertNonCorrelatedSubQuery(subQuery, bb, converted.r, true)) { + return; + } + subQuery.expr = bb.register(converted.r, JoinRelType.LEFT); + return; + + case SCALAR_QUERY: + // Convert the sub-query. If it's non-correlated, convert it + // to a constant expression. + if (!config.isExpand()) { + return; + } + call = (SqlBasicCall) subQuery.node; + query = call.operand(0); + converted = convertExists(query, RelOptUtil.SubQueryType.SCALAR, + subQuery.logic, true, null); + assert !converted.indicator; + if (convertNonCorrelatedSubQuery(subQuery, bb, converted.r, false)) { + return; + } + rel = convertToSingleValueSubq(query, converted.r); + subQuery.expr = bb.register(rel, JoinRelType.LEFT); + return; + + case SELECT: + // This is used when converting multiset queries: + // + // select * from unnest(select multiset[deptno] from emps); + // + converted = convertExists(subQuery.node, RelOptUtil.SubQueryType.SCALAR, + subQuery.logic, true, null); + assert !converted.indicator; + subQuery.expr = bb.register(converted.r, JoinRelType.LEFT); + return; + + default: + throw new AssertionError("unexpected kind of sub-query: " + + subQuery.node); + } + } + + private RexNode translateIn(RelOptUtil.Logic logic, RelNode root, + final RexNode rex) { + switch (logic) { + case TRUE: + return rexBuilder.makeLiteral(true); + + case TRUE_FALSE: + case UNKNOWN_AS_FALSE: + assert rex instanceof RexRangeRef; + final int fieldCount = rex.getType().getFieldCount(); + RexNode rexNode = rexBuilder.makeFieldAccess(rex, fieldCount - 1); + rexNode = rexBuilder.makeCall(SqlStdOperatorTable.IS_TRUE, rexNode); + + // Then append the IS NOT NULL(leftKeysForIn). + // + // RexRangeRef contains the following fields: + // leftKeysForIn, + // rightKeysForIn (the original sub-query select list), + // nullIndicator + // + // The first two lists contain the same number of fields. + final int k = (fieldCount - 1) / 2; + for (int i = 0; i < k; i++) { + rexNode = + rexBuilder.makeCall( + SqlStdOperatorTable.AND, + rexNode, + rexBuilder.makeCall( + SqlStdOperatorTable.IS_NOT_NULL, + rexBuilder.makeFieldAccess(rex, i))); + } + return rexNode; + + case TRUE_FALSE_UNKNOWN: + case UNKNOWN_AS_TRUE: + // select e.deptno, + // case + // when ct.c = 0 then false + // when dt.i is not null then true + // when e.deptno is null then null + // when ct.ck < ct.c then null + // else false + // end + // from e + // cross join (select count(*) as c, count(deptno) as ck from v) as ct + // left join (select distinct deptno, true as i from v) as dt + // on e.deptno = dt.deptno + final Join join = (Join) root; + final Project left = (Project) join.getLeft(); + final RelNode leftLeft = ((Join) left.getInput()).getLeft(); + final int leftLeftCount = leftLeft.getRowType().getFieldCount(); + final RelDataType longType = + typeFactory.createSqlType(SqlTypeName.BIGINT); + final RexNode cRef = rexBuilder.makeInputRef(root, leftLeftCount); + final RexNode ckRef = rexBuilder.makeInputRef(root, leftLeftCount + 1); + final RexNode iRef = + rexBuilder.makeInputRef(root, root.getRowType().getFieldCount() - 1); + + final RexLiteral zero = + rexBuilder.makeExactLiteral(BigDecimal.ZERO, longType); + final RexLiteral trueLiteral = rexBuilder.makeLiteral(true); + final RexLiteral falseLiteral = rexBuilder.makeLiteral(false); + final RexNode unknownLiteral = + rexBuilder.makeNullLiteral(trueLiteral.getType()); + + final ImmutableList.Builder<RexNode> args = ImmutableList.builder(); + args.add(rexBuilder.makeCall(SqlStdOperatorTable.EQUALS, cRef, zero), + falseLiteral, + rexBuilder.makeCall(SqlStdOperatorTable.IS_NOT_NULL, iRef), + trueLiteral); + final JoinInfo joinInfo = join.analyzeCondition(); + for (int leftKey : joinInfo.leftKeys) { + final RexNode kRef = rexBuilder.makeInputRef(root, leftKey); + args.add(rexBuilder.makeCall(SqlStdOperatorTable.IS_NULL, kRef), + unknownLiteral); + } + args.add(rexBuilder.makeCall(SqlStdOperatorTable.LESS_THAN, ckRef, cRef), + unknownLiteral, + falseLiteral); + + return rexBuilder.makeCall(SqlStdOperatorTable.CASE, args.build()); + + default: + throw new AssertionError(logic); + } + } + + private static boolean containsNullLiteral(SqlNodeList valueList) { + for (SqlNode node : valueList.getList()) { + if (node instanceof SqlLiteral) { + SqlLiteral lit = (SqlLiteral) node; + if (lit.getValue() == null) { + return true; + } + } + } + return false; + } + + /** + * Determines if a sub-query is non-correlated and if so, converts it to a + * constant. + * + * @param subQuery the call that references the sub-query + * @param bb blackboard used to convert the sub-query + * @param converted RelNode tree corresponding to the sub-query + * @param isExists true if the sub-query is part of an EXISTS expression + * @return Whether the sub-query can be converted to a constant + */ + private boolean convertNonCorrelatedSubQuery( + SubQuery subQuery, + Blackboard bb, + RelNode converted, + boolean isExists) { + SqlCall call = (SqlBasicCall) subQuery.node; + if (subQueryConverter.canConvertSubQuery() + && isSubQueryNonCorrelated(converted, bb)) { + // First check if the sub-query has already been converted + // because it's a nested sub-query. If so, don't re-evaluate + // it again. + RexNode constExpr = mapConvertedNonCorrSubqs.get(call); + if (constExpr == null) { + constExpr = + subQueryConverter.convertSubQuery( + call, + this, + isExists, + config.isExplain()); + } + if (constExpr != null) { + subQuery.expr = constExpr; + mapConvertedNonCorrSubqs.put(call, constExpr); + return true; + } + } + return false; + } + + /** + * Converts the RelNode tree for a select statement to a select that + * produces a single value. + * + * @param query the query + * @param plan the original RelNode tree corresponding to the statement + * @return the converted RelNode tree + */ + public RelNode convertToSingleValueSubq( + SqlNode query, + RelNode plan) { + // Check whether query is guaranteed to produce a single value. + if (query instanceof SqlSelect) { + SqlSelect select = (SqlSelect) query; + SqlNodeList selectList = select.getSelectList(); + SqlNodeList groupList = select.getGroup(); + + if ((selectList.size() == 1) + && ((groupList == null) || (groupList.size() == 0))) { + SqlNode selectExpr = selectList.get(0); + if (selectExpr instanceof SqlCall) { + SqlCall selectExprCall = (SqlCall) selectExpr; + if (Util.isSingleValue(selectExprCall)) { + return plan; + } + } + + // If there is a limit with 0 or 1, + // it is ensured to produce a single value + if (select.getFetch() != null + && select.getFetch() instanceof SqlNumericLiteral) { + SqlNumericLiteral limitNum = (SqlNumericLiteral) select.getFetch(); + if (((BigDecimal) limitNum.getValue()).intValue() < 2) { + return plan; + } + } + } + } else if (query instanceof SqlCall) { + // If the query is (values ...), + // it is necessary to look into the operands to determine + // whether SingleValueAgg is necessary + SqlCall exprCall = (SqlCall) query; + if (exprCall.getOperator() + instanceof SqlValuesOperator + && Util.isSingleValue(exprCall)) { + return plan; + } + } + + // If not, project SingleValueAgg + return RelOptUtil.createSingleValueAggRel( + cluster, + plan); + } + + /** + * Converts "x IN (1, 2, ...)" to "x=1 OR x=2 OR ...". + * + * @param leftKeys LHS + * @param valuesList RHS + * @param isNotIn is this a NOT IN operator + * @return converted expression + */ + private RexNode convertInToOr( + final Blackboard bb, + final List<RexNode> leftKeys, + SqlNodeList valuesList, + boolean isNotIn) { + final List<RexNode> comparisons = new ArrayList<>(); + for (SqlNode rightVals : valuesList) { + RexNode rexComparison; + if (leftKeys.size() == 1) { + rexComparison = + rexBuilder.makeCall(SqlStdOperatorTable.EQUALS, + leftKeys.get(0), + ensureSqlType(leftKeys.get(0).getType(), + bb.convertExpression(rightVals))); + } else { + assert rightVals instanceof SqlCall; + final SqlBasicCall call = (SqlBasicCall) rightVals; + assert (call.getOperator() instanceof SqlRowOperator) + && call.operandCount() == leftKeys.size(); + rexComparison = + RexUtil.composeConjunction( + rexBuilder, + Iterables.transform( + Pair.zip(leftKeys, call.getOperandList()), + new Function<Pair<RexNode, SqlNode>, RexNode>() { + public RexNode apply(Pair<RexNode, SqlNode> pair) { + return rexBuilder.makeCall(SqlStdOperatorTable.EQUALS, + pair.left, + ensureSqlType(pair.left.getType(), + bb.convertExpression(pair.right))); + } + }), + false); + } + comparisons.add(rexComparison); + } + + RexNode result = + RexUtil.composeDisjunction(rexBuilder, comparisons, true); + assert result != null; + + if (isNotIn) { + result = + rexBuilder.makeCall( + SqlStdOperatorTable.NOT, + result); + } + + return result; + } + + /** Ensures that an expression has a given {@link SqlTypeName}, applying a + * cast if necessary. If the expression already has the right type family, + * returns the expression unchanged. */ + private RexNode ensureSqlType(RelDataType type, RexNode node) { + if (type.getSqlTypeName() == node.getType().getSqlTypeName() + || (type.getSqlTypeName() == SqlTypeName.VARCHAR + && node.getType().getSqlTypeName() == SqlTypeName.CHAR)) { + return node; + } + return rexBuilder.ensureType(type, node, true); + } + + /** + * Gets the list size threshold under which {@link #convertInToOr} is used. + * Lists of this size or greater will instead be converted to use a join + * against an inline table + * ({@link org.apache.calcite.rel.logical.LogicalValues}) rather than a + * predicate. A threshold of 0 forces usage of an inline table in all cases; a + * threshold of Integer.MAX_VALUE forces usage of OR in all cases + * + * @return threshold, default {@link #DEFAULT_IN_SUB_QUERY_THRESHOLD} + */ + @Deprecated // to be removed before 2.0 + protected int getInSubqueryThreshold() { + return config.getInSubQueryThreshold(); + } + + /** + * Converts an EXISTS or IN predicate into a join. For EXISTS, the sub-query + * produces an indicator variable, and the result is a relational expression + * which outer joins that indicator to the original query. After performing + * the outer join, the condition will be TRUE if the EXISTS condition holds, + * NULL otherwise. + * + * @param seek A query, for example 'select * from emp' or + * 'values (1,2,3)' or '('Foo', 34)'. + * @param subQueryType Whether sub-query is IN, EXISTS or scalar + * @param logic Whether the answer needs to be in full 3-valued logic (TRUE, + * FALSE, UNKNOWN) will be required, or whether we can accept an + * approximation (say representing UNKNOWN as FALSE) + * @param notIn Whether the operation is NOT IN + * @return join expression + */ + private RelOptUtil.Exists convertExists( + SqlNode seek, + RelOptUtil.SubQueryType subQueryType, + RelOptUtil.Logic logic, + boolean notIn, + RelDataType targetDataType) { + final SqlValidatorScope seekScope = + (seek instanceof SqlSelect) + ? validator.getSelectScope((SqlSelect) seek) + : null; + final Blackboard seekBb = createBlackboard(seekScope, null, false); + RelNode seekRel = convertQueryOrInList(seekBb, seek, targetDataType); + + return RelOptUtil.createExistsPlan(seekRel, subQueryType, logic, notIn); + } + + private RelNode convertQueryOrInList( + Blackboard bb, + SqlNode seek, + RelDataType targetRowType) { + // NOTE: Once we start accepting single-row queries as row constructors, + // there will be an ambiguity here for a case like X IN ((SELECT Y FROM + // Z)). The SQL standard resolves the ambiguity by saying that a lone + // select should be interpreted as a table expression, not a row + // expression. The semantic difference is that a table expression can + // return multiple rows. + if (seek instanceof SqlNodeList) { + return convertRowValues( + bb, + seek, + ((SqlNodeList) seek).getList(), + false, + targetRowType); + } else { + return convertQueryRecursive(seek, false, null).project(); + } + } + + private RelNode convertRowValues( + Blackboard bb, + SqlNode rowList, + Collection<SqlNode> rows, + boolean allowLiteralsOnly, + RelDataType targetRowType) { + // NOTE jvs 30-Apr-2006: We combine all rows consisting entirely of + // literals into a single LogicalValues; this gives the optimizer a smaller + // input tree. For everything else (computed expressions, row + // sub-queries), we union each row in as a projection on top of a + // LogicalOneRow. + + final ImmutableList.Builder<ImmutableList<RexLiteral>> tupleList = + ImmutableList.builder(); + final RelDataType rowType; + if (targetRowType != null) { + rowType = targetRowType; + } else { + rowType = + SqlTypeUtil.promoteToRowType( + typeFactory, + validator.getValidatedNodeType(rowList), + null); + } + + final List<RelNode> unionInputs = new ArrayList<>(); + for (SqlNode node : rows) { + SqlBasicCall call; + if (isRowConstructor(node)) { + call = (SqlBasicCall) node; + ImmutableList.Builder<RexLiteral> tuple = ImmutableList.builder(); + for (Ord<SqlNode> operand : Ord.zip(call.operands)) { + RexLiteral rexLiteral = + convertLiteralInValuesList( + operand.e, + bb, + rowType, + operand.i); + if ((rexLiteral == null) && allowLiteralsOnly) { + return null; + } + if ((rexLiteral == null) || !config.isCreateValuesRel()) { + // fallback to convertRowConstructor + tuple = null; + break; + } + tuple.add(rexLiteral); + } + if (tuple != null) { + tupleList.add(tuple.build()); + continue; + } + } else { + RexLiteral rexLiteral = + convertLiteralInValuesList( + node, + bb, + rowType, + 0); + if ((rexLiteral != null) && config.isCreateValuesRel()) { + tupleList.add(ImmutableList.of(rexLiteral)); + continue; + } else { + if ((rexLiteral == null) && allowLiteralsOnly) { + return null; + } + } + + // convert "1" to "row(1)" + call = + (SqlBasicCall) SqlStdOperatorTable.ROW.createCall( + SqlParserPos.ZERO, + node); + } + unionInputs.add(convertRowConstructor(bb, call)); + } + LogicalValues values = + LogicalValues.create(cluster, rowType, tupleList.build()); + RelNode resultRel; + if (unionInputs.isEmpty()) { + resultRel = values; + } else { + if (!values.getTuples().isEmpty()) { + unionInputs.add(values); + } + resultRel = LogicalUnion.create(unionInputs, true); + } + leaves.add(resultRel); + return resultRel; + } + + private RexLiteral convertLiteralInValuesList( + SqlNode sqlNode, + Blackboard bb, + RelDataType rowType, + int iField) { + if (!(sqlNode instanceof SqlLiteral)) { + return null; + } + RelDataTypeField field = rowType.getFieldList().get(iField); + RelDataType type = field.getType(); + if (type.isStruct()) { + // null literals for weird stuff like UDT's need + // special handling during type flattening, so + // don't use LogicalValues for those + return null; + } + + RexNode literalExpr = + exprConverter.convertLiteral( + bb, + (SqlLiteral) sqlNode); + + if (!(literalExpr instanceof RexLiteral)) { + assert literalExpr.isA(SqlKind.CAST); + RexNode child = ((RexCall) literalExpr).getOperands().get(0); + assert RexLiteral.isNullLiteral(child); + + // NOTE jvs 22-Nov-2006: we preserve type info + // in LogicalValues digest, so it's OK to lose it here + return (RexLiteral) child; + } + + RexLiteral literal = (RexLiteral) literalExpr; + + Comparable value = literal.getValue(); + + if (SqlTypeUtil.isExactNumeric(type) && SqlTypeUtil.hasScale(type)) { + BigDecimal roundedValue = + NumberUtil.rescaleBigDecimal( + (BigDecimal) value, + type.getScale()); + return rexBuilder.makeExactLiteral( + roundedValue, + type); + } + + if ((value instanceof NlsString) + && (type.getSqlTypeName() == SqlTypeName.CHAR)) { + // pad fixed character type + NlsString unpadded = (NlsString) value; + return rexBuilder.makeCharLiteral( + new NlsString( + Spaces.padRight(unpadded.getValue(), type.getPrecision()), + unpadded.getCharsetName(), + unpadded.getCollation())); + } + return literal; + } + + private boolean isRowConstructor(SqlNode node) { + if (!(node.getKind() == SqlKind.ROW)) { + return false; + } + SqlCall call = (SqlCall) node; + return call.getOperator().getName().equalsIgnoreCase("row"); + } + + /** + * Builds a list of all <code>IN</code> or <code>EXISTS</code> operators + * inside SQL parse tree. Does not traverse inside queries. + * + * @param bb blackboard + * @param node the SQL parse tree + * @param logic Whether the answer needs to be in full 3-valued logic (TRUE, + * FALSE, UNKNOWN) will be required, or whether we can accept + * an approximation (say representing UNKNOWN as FALSE) + * @param registerOnlyScalarSubQueries if set to true and the parse tree + * corresponds to a variation of a select + * node, only register it if it's a scalar + * sub-query + */ + private void findSubQueries( + Blackboard bb, + SqlNode node, + RelOptUtil.Logic logic, + boolean registerOnlyScalarSubQueries) { + final SqlKind kind = node.getKind(); + switch (kind) { + case EXISTS: + case SELECT: + case MULTISET_QUERY_CONSTRUCTOR: + case MULTISET_VALUE_CONSTRUCTOR: + case ARRAY_QUERY_CONSTRUCTOR: + case CURSOR: + case SCALAR_QUERY: + if (!registerOnlyScalarSubQueries + || (kind == SqlKind.SCALAR_QUERY)) { + bb.registerSubQuery(node, RelOptUtil.Logic.TRUE_FALSE); + } + return; + case IN: + if (((SqlCall) node).getOperator() == SqlStdOperatorTable.NOT_IN) { + logic = logic.negate(); + } + break; + case NOT: + logic = logic.negate(); + break; + } + if (node instanceof SqlCall) { + for (SqlNode operand : ((SqlCall) node).getOperandList()) { + if (operand != null) { + // In the case of an IN expression, locate scalar + // sub-queries so we can convert them to constants + findSubQueries( + bb, + operand, + logic, + kind == SqlKind.IN || registerOnlyScalarSubQueries); + } + } + } else if (node instanceof SqlNodeList) { + for (SqlNode child : (SqlNodeList) node) { + findSubQueries( + bb, + child, + logic, + kind == SqlKind.IN || registerOnlyScalarSubQueries); + } + } + + // Now that we've located any scalar sub-queries inside the IN + // expression, register the IN expression itself. We need to + // register the scalar sub-queries first so they can be converted + // before the IN expression is converted. + if (kind == SqlKind.IN) { + switch (logic) { + case TRUE_FALSE_UNKNOWN: + if (validator.getValidatedNodeType(node).isNullable()) { + break; + } else if (true) { + break; + } + // fall through + case UNKNOWN_AS_FALSE: + logic = RelOptUtil.Logic.TRUE; + } + bb.registerSubQuery(node, logic); + } + } + + /** + * Converts an expression from {@link SqlNode} to {@link RexNode} format. + * + * @param node Expression to translate + * @return Converted expression + */ + public RexNode convertExpression( + SqlNode node) { + Map<String, RelDataType> nameToTypeMap = Collections.emptyMap(); + final ParameterScope scope = + new ParameterScope((SqlValidatorImpl) validator, nameToTypeMap); + final Blackboard bb = createBlackboard(scope, null, false); + return bb.convertExpression(node); + } + + /** + * Converts an expression from {@link SqlNode} to {@link RexNode} format, + * mapping identifier references to predefined expressions. + * + * @param node Expression to translate + * @param nameToNodeMap map from String to {@link RexNode}; when an + * {@link SqlIdentifier} is encountered, it is used as a + * key and translated to the corresponding value from + * this map + * @return Converted expression + */ + public RexNode convertExpression( + SqlNode node, + Map<String, RexNode> nameToNodeMap) { + final Map<String, RelDataType> nameToTypeMap = new HashMap<>(); + for (Map.Entry<String, RexNode> entry : nameToNodeMap.entrySet()) { + nameToTypeMap.put(entry.getKey(), entry.getValue().getType()); + } + final ParameterScope scope = + new ParameterScope((SqlValidatorImpl) validator, nameToTypeMap); + final Blackboard bb = createBlackboard(scope, nameToNodeMap, false); + return bb.convertExpression(node); + } + + /** + * Converts a non-standard expression. + * + * <p>This method is an extension-point that derived classes can override. If + * this method returns a null result, the normal expression translation + * process will proceed. The default implementation always returns null. + * + * @param node Expression + * @param bb Blackboard + * @return null to proceed with the usual expression translation process + */ + protected RexNode convertExtendedExpression( + SqlNode node, + Blackboard bb) { + return null; + } + + private RexNode convertOver(Blackboard bb, SqlNode node) { + SqlCall call = (SqlCall) node; + SqlCall aggCall = call.operand(0); + SqlNode windowOrRef = call.operand(1); + final SqlWindow window = + validator.resolveWindow(windowOrRef, bb.scope, true); + + // ROW_NUMBER() expects specific kind of framing. + if (aggCall.getKind() == SqlKind.ROW_NUMBER) { + window.setLowerBound(SqlWindow.createUnboundedPreceding(SqlParserPos.ZERO)); + window.setUpperBound(SqlWindow.createCurrentRow(SqlParserPos.ZERO)); + window.setRows(SqlLiteral.createBoolean(true, SqlParserPos.ZERO)); + } + final SqlNodeList partitionList = window.getPartitionList(); + final ImmutableList.Builder<RexNode> partitionKeys = + ImmutableList.builder(); + for (SqlNode partition : partitionList) { + partitionKeys.add(bb.convertExpression(partition)); + } + RexNode lowerBound = bb.convertExpression(window.getLowerBound()); + RexNode upperBound = bb.convertExpression(window.getUpperBound()); + SqlNodeList orderList = window.getOrderList(); + if ((orderList.size() == 0) && !window.isRows()) { + // A logical range requires an ORDER BY clause. Use the implicit + // ordering of this relation. There must be one, otherwise it would + // have failed validation. + orderList = bb.scope.getOrderList(); + if (orderList == null) { + throw new AssertionError( + "Relation should have sort key for implicit ORDER BY"); + } + } + final ImmutableList.Builder<RexFieldCollation> orderKeys = + ImmutableList.builder(); + final Set<SqlKind> flags = EnumSet.noneOf(SqlKind.class); + for (SqlNode order : orderList) { + flags.clear(); + RexNode e = bb.convertSortExpression(order, flags); + orderKeys.add(new RexFieldCollation(e, flags)); + } + try { + Preconditions.checkArgument(bb.window == null, + "already in window agg mode"); + bb.window = window; + RexNode rexAgg = exprConverter.convertCall(bb, aggCall); + rexAgg = + rexBuilder.ensureType( + validator.getValidatedNodeType(call), rexAgg, false); + + // Walk over the tree and apply 'over' to all agg functions. This is + // necessary because the returned expression is not necessarily a call + // to an agg function. For example, AVG(x) becomes SUM(x) / COUNT(x). + final RexShuttle visitor = + new HistogramShuttle( + partitionKeys.build(), orderKeys.build(), + RexWindowBound.create(window.getLowerBound(), lowerBound), + RexWindowBound.create(window.getUpperBound(), upperBound), + window); + return rexAgg.accept(visitor); + } finally { + bb.window = null; + } + } + + /** + * Converts a FROM clause into a relational expression. + * + * @param bb Scope within which to resolve identifiers + * @param from FROM clause of a query. Examples include: + * + * <ul> + * <li>a single table ("SALES.EMP"), + * <li>an aliased table ("EMP AS E"), + * <li>a list of tables ("EMP, DEPT"), + * <li>an ANSI Join expression ("EMP JOIN DEPT ON EMP.DEPTNO = + * DEPT.DEPTNO"), + * <li>a VALUES clause ("VALUES ('Fred', 20)"), + * <li>a query ("(SELECT * FROM EMP WHERE GENDER = 'F')"), + * <li>or any combination of the above. + * </ul> + */ + protected void convertFrom( + Blackboard bb, + SqlNode from) { + if (from == null) { + bb.setRoot(LogicalValues.createOneRow(cluster), false); + return; + } + + final SqlCall call; + final SqlNode[] operands; + switch (from.getKind()) { + case MATCH_RECOGNIZE: + convertMatchRecognize(bb, (SqlCall) from); + return; + + case AS: + convertFrom(bb, ((SqlCall) from).operand(0)); + return; + + case WITH_ITEM: + convertFrom(bb, ((SqlWithItem) from).query); + return; + + case WITH: + convertFrom(bb, ((SqlWith) from).body); + return; + + case TABLESAMPLE: + operands = ((SqlBasicCall) from).getOperands(); + SqlSampleSpec sampleSpec = SqlLiteral.sampleValue(operands[1]); + if (sampleSpec instanceof SqlSampleSpec.SqlSubstitutionSampleSpec) { + String sampleName = + ((SqlSampleSpec.SqlSubstitutionSampleSpec) sampleSpec) + .getName(); + datasetStack.push(sampleName); + convertFrom(bb, operands[0]); + datasetStack.pop(); + } else if (sampleSpec instanceof SqlSampleSpec.SqlTableSampleSpec) { + SqlSampleSpec.SqlTableSampleSpec tableSampleSpec = + (SqlSampleSpec.SqlTableSampleSpec) sampleSpec; + convertFrom(bb, operands[0]); + RelOptSamplingParameters params = + new RelOptSamplingParameters( + tableSampleSpec.isBernoulli(), + tableSampleSpec.getSamplePercentage(), + tableSampleSpec.isRepeatable(), + tableSampleSpec.getRepeatableSeed()); + bb.setRoot(new Sample(cluster, bb.root, params), false); + } else { + throw new AssertionError("unknown TABLESAMPLE type: " + sampleSpec); + } + return; + + case IDENTIFIER: + convertIdentifier(bb, (SqlIdentifier) from, null); + return; + + case EXTEND: + call = (SqlCall) from; + SqlIdentifier id = (SqlIdentifier) call.getOperandList().get(0); + SqlNodeList extendedColumns = (SqlNodeList) call.getOperandList().get(1); + convertIdentifier(bb, id, extendedColumns); + return; + + case JOIN: + final SqlJoin join = (SqlJoin) from; + final SqlValidatorScope scope = validator.getJoinScope(from); + final Blackboard fromBlackboard = createBlackboard(scope, null, false); + SqlNode left = join.getLeft(); + SqlNode right = join.getRight(); + final boolean isNatural = join.isNatural(); + final JoinType joinType = join.getJoinType(); + final SqlValidatorScope leftScope = + Util.first(validator.getJoinScope(left), + ((DelegatingScope) bb.scope).getParent()); + final Blackboard leftBlackboard = + createBlackboard(leftScope, null, false); + final SqlValidatorScope rightScope = + Util.first(validator.getJoinScope(right), + ((DelegatingScope) bb.scope).getParent()); + final Blackboard rightBlackboard = + createBlackboard(rightScope, null, false); + convertFrom(leftBlackboard, left); + RelNode leftRel = leftBlackboard.root; + convertFrom(rightBlackboard, right); + RelNode rightRel = rightBlackboard.root; + JoinRelType convertedJoinType = convertJoinType(joinType); + RexNode conditionExp; + final SqlValidatorNamespace leftNamespace = validator.getNamespace(left); + final SqlValidatorNamespace rightNamespace = validator.getNamespace(right); + if (isNatural) { + final RelDataType leftRowType = leftNamespace.getRowType(); + final RelDataType rightRowType = rightNamespace.getRowType(); + final List<String> columnList = + SqlValidatorUtil.deriveNaturalJoinColumnList(leftRowType, + rightRowType); + conditionExp = convertUsing(leftNamespace, rightNamespace, + columnList); + } else { + conditionExp = + convertJoinCondition( + fromBlackboard, + leftNamespace, + rightNamespace, + join.getCondition(), + join.getConditionType(), + leftRel, + rightRel); + } + + final RelNode joinRel = + createJoin( + fromBlackboard, + leftRel, + rightRel, + conditionExp, + convertedJoinType); + bb.setRoot(joinRel, false); + return; + + case SELECT: + case INTERSECT: + case EXCEPT: + case UNION: + final RelNode rel = convertQueryRecursive(from, false, null).project(); + bb.setRoot(rel, true); + return; + + case VALUES: + convertValuesImpl(bb, (SqlCall) from, null); + return; + + case UNNEST: + call = (SqlCall) from; + final List<SqlNode> nodes = call.getOperandList(); + final SqlUnnestOperator operator = (SqlUnnestOperator) call.getOperator(); + for (SqlNode node : nodes) { + replaceSubQueries(bb, node, RelOptUtil.Logic.TRUE_FALSE_UNKNOWN); + } + final List<RexNode> exprs = new ArrayList<>(); + final List<String> fieldNames = new ArrayList<>(); + for (Ord<SqlNode> node : Ord.zip(nodes)) { + exprs.add(bb.convertExpression(node.e)); + fieldNames.add(validator.deriveAlias(node.e, node.i)); + } + final RelNode input = + RelOptUtil.createProject( + (null != bb.root) ? bb.root : LogicalValues.createOneRow(cluster), + exprs, fieldNames, true); + + Uncollect uncollect = + new Uncollect(cluster, cluster.traitSetOf(Convention.NONE), + input, operator.withOrdinality); + bb.setRoot(uncollect, true); + return; + + case COLLECTION_TABLE: + call = (SqlCall) from; + + // Dig out real call; TABLE() wrapper is just syntactic. + assert call.getOperandList().size() == 1; + final SqlCall call2 = call.operand(0); + convertCollectionTable(bb, call2); + return; + + default: + throw new AssertionError("not a join operator " + from); + } + } + + protected void convertMatchRecognize(Blackboard bb, SqlCall call) { + final SqlMatchRecognize matchRecognize = (SqlMatchRecognize) call; + final SqlValidatorNamespace ns = validator.getNamespace(matchRecognize); + final SqlValidatorScope scope = validator.getMatchRecognizeScope(matchRecognize); + + final Blackboard mrBlackBoard = createBlackboard(scope, null, false); + final RelDataType rowType = ns.getRowType(); + // convert inner query, could be a table name or a derived table + SqlNode expr = matchRecognize.getTableRef(); + convertFrom(mrBlackBoard, expr); + final RelNode input = mrBlackBoard.root; + + // convert pattern + final Set<String> patternVarsSet = new HashSet<>(); + SqlNode pattern = matchRecognize.getPattern(); + final SqlBasicVisitor<RexNode> patternVarVisitor = + new SqlBasicVisitor<RexNode>() { + @Override public RexNode visit(SqlCall call) { + List<SqlNode> operands = call.getOperandList(); + List<RexNode> newOperands = Lists.newArrayList(); + for (SqlNode node : operands) { + newOperands.add(node.accept(this)); + } + return rexBuilder.makeCall( + validator.getUnknownType(), call.getOperator(), newOperands); + } + + @Override public RexNode visit(SqlIdentifier id) { + assert id.isSimple(); + patternVarsSet.add(id.getSimple()); + return rexBuilder.makeLiteral(id.getSimple()); + } + + @Override public RexNode visit(SqlLiteral literal) { + if (literal instanceof SqlNumericLiteral) { + return rexBuilder.makeExactLiteral(BigDecimal.valueOf(literal.intValue(true))); + } else { + return rexBuilder.makeLiteral(literal.booleanValue()); + } + } + }; + final RexNode patternNode = pattern.accept(patternVarVisitor); + + mrBlackBoard.setPatternVarRef(true); + + // convert definitions + final ImmutableMap.Builder<String, RexNode> definitionNodes = + ImmutableMap.builder(); + for (SqlNode def : matchRecognize.getPatternDefList()) { + List<SqlNode> operands = ((SqlCall) def).getOperandList(); + String alias = ((SqlIdentifier) operands.get(1)).getSimple(); + RexNode rex = mrBlackBoard.convertExpression(operands.get(0)); + definitionNodes.put(alias, rex); + } + + mrBlackBoard.setPatternVarRef(false); + + final RelFactories.MatchFactory factory = + RelFactories.DEFAULT_MATCH_FACTORY; + final RelNode rel = + factory.createMatchRecognize(input, patternNode, + matchRecognize.getStrictStart().booleanValue(), + matchRecognize.getStrictEnd().booleanValue(), + definitionNodes.build(), + rowType); + bb.setRoot(rel, false); + } + + private void convertIdentifier(Blackboard bb, SqlIdentifier id, + SqlNodeList extendedColumns) { + final SqlValidatorNamespace fromNamespace = + validator.getNamespace(id).resolve(); + if (fromNamespace.getNode() != null) { + convertFrom(bb, fromNamespace.getNode()); + return; + } + final String datasetName = + datasetStack.isEmpty() ? null : datasetStack.peek(); + final boolean[] usedDataset = {false}; + RelOptTable table = + SqlValidatorUtil.getRelOptTable(fromNamespace, catalogReader, + datasetName, usedDataset); + if (extendedColumns != null && extendedColumns.size() > 0) { + assert table != null; + final SqlValidatorTable validatorTable = + table.unwrap(SqlValidatorTable.class); + final List<RelDataTypeField> extendedFields = + SqlValidatorUtil.getExtendedColumns(validator, validatorTable, + extendedColumns); + table = table.extend(extendedFields); + } + final RelNode tableRel; + if (config.isConvertTableAccess()) { + tableRel = toRel(table); + } else { + tableRel = LogicalTableScan.create(cluster, table); + } + bb.setRoot(tableRel, true); + if (usedDataset[0]) { + bb.setDataset(datasetName); + } + } + + protected void convertCollectionTable( + Blackboard bb, + SqlCall call) { + final SqlOperator operator = call.getOperator(); + if (operator == SqlStdOperatorTable.TABLESAMPLE) { + final String sampleName = (String) SqlLiteral.value(call.operand(0)); + datasetStack.push(sampleName); + SqlCall cursorCall = call.operand(1); + SqlNode query = cursorCall.operand(0); + RelNode converted = convertQuery(query, false, false).rel; + bb.setRoot(converted, false); + datasetStack.pop(); + return; + } + replaceSubQueries(bb, call, RelOptUtil.Logic.TRUE_FALSE_UNKNOWN); + + // Expand table macro if possible. It's more efficient than + // LogicalTableFunctionScan. + final SqlCallBinding callBinding = + new SqlCallBinding(bb.scope.getValidator(), bb.scope, call); + if (operator instanceof SqlUserDefinedTableMacro) { + final SqlUserDefinedTableMacro udf = + (SqlUserDefinedTableMacro) operator; + final TranslatableTable table = + udf.getTable(typeFactory, callBinding.operands()); + final RelDataType rowType = table.getRowType(typeFactory); + RelOptTable relOptTable = RelOptTableImpl.create(null, rowType, table, + udf.getNameAsId().names); + RelNode converted = toRel(relOptTable); + bb.setRoot(converted, true); + return; + } + + Type elementType; + if (operator instanceof SqlUserDefinedTableFunction) { + SqlUserDefinedTableFunction udtf = (SqlUserDefinedTableFunction) operator; + elementType = udtf.getElementType(typeFactory, callBinding.operands()); + } else { + elementType = null; + } + + RexNode rexCall = bb.convertExpression(call); + final List<RelNode> inputs = bb.retrieveCursors(); + Set<RelColumnMapping> columnMappings = + getColumnMappings(operator); + LogicalTableFunctionScan callRel = + LogicalTableFunctionScan.create( + cluster, + inputs, + rexCall, + elementType, + validator.getValidatedNodeType(call), + columnMappings); + bb.setRoot(callRel, true); + afterTableFunction(bb, call, callRel); + } + + protected void afterTableFunction( + SqlToRelConverter.Blackboard bb, + SqlCall call, + LogicalTableFunctionScan callRel) { + } + + private Set<RelColumnMapping> getColumnMappings(SqlOperator op) { + SqlReturnTypeInference rti = op.getReturnTypeInference(); + if (rti == null) { + return null; + } + if (rti instanceof TableFunctionReturnTypeInference) { + TableFunctionReturnTypeInference tfrti = + (TableFunctionReturnTypeInference) rti; + return tfrti.getColumnMappings(); + } else { + return null; + } + } + + protected RelNode createJoin( + Blackboard bb, + RelNode leftRel, + RelNode rightRel, + RexNode joinCond, + JoinRelType joinType) { + assert joinCond != null; + + final CorrelationUse p = getCorrelationUse(bb, rightRel); + if (p != null) { + LogicalCorrelate corr = LogicalCorrelate.create(leftRel, p.r, + p.id, p.requiredColumns, SemiJoinType.of(joinType)); + if (!joinCond.isAlwaysTrue()) { + final RelFactories.FilterFactory factory = + RelFactories.DEFAULT_FILTER_FACTORY; + return factory.createFilter(corr, joinCond); + } + return corr; + } + + final Join originalJoin = + (Join) RelFactories.DEFAULT_JOIN_FACTORY.createJoin(leftRel, rightRel, + joinCond, ImmutableSet.<CorrelationId>of(), joinType, false); + + return RelOptUtil.pushDownJoinConditions(originalJoin); + } + + private CorrelationUse getCorrelationUse(Blackboard bb, final RelNode r0) { + final Set<CorrelationId> correlatedVariables = + RelOptUtil.getVariablesUsed(r0); + if (correlatedVariables.isEmpty()) { + return null; + } + final ImmutableBitSet.Builder requiredColumns = ImmutableBitSet.builder(); + final List<CorrelationId> correlNames = Lists.newArrayList(); + + // All correlations must refer the same namespace since correlation + // produces exactly one correlation source. + // The same source might be referenced by different variables since + // DeferredLookups are not de-duplicated at create time. + SqlValidatorNamespace prevNs = null; + + for (CorrelationId correlName : correlatedVariables) { + DeferredLookup lookup = + mapCorrelToDeferred.get(correlName); + RexFieldAccess fieldAccess = lookup.getFieldAccess(correlName); + String originalRelName = lookup.getOriginalRelName(); + String originalFieldName = fieldAccess.getField().getName(); + + final SqlNameMatcher nameMatcher = + lookup.bb.scope.getValidator().getCatalogReader().nameMatcher(); + final SqlValidatorScope.ResolvedImpl resolved = + new SqlValidatorScope.ResolvedImpl(); + lookup.bb.scope.resolve(ImmutableList.of(originalRelName), + nameMatcher, false, resolved); + assert resolved.count() == 1; + final SqlValidatorScope.Resolve resolve = resolved.only(); + final SqlValidatorNamespace foundNs = resolve.namespace; + final RelDataType rowType = resolve.rowType(); + final int childNamespaceIndex = resolve.path.steps().get(0).i; + final SqlValidatorScope ancestorScope = resolve.scope; + boolean correlInCurrentScope = ancestorScope == bb.scope; + + if (!correlInCurrentScope) { + continue; + } + + if (prevNs == null) { + prevNs = foundNs; + } else { + assert prevNs == foundNs : "All correlation variables should resolve" + + " to the same namespace." + + " Prev ns=" + prevNs + + ", new ns=" + foundNs; + } + + int namespaceOffset = 0; + if (childNamespaceIndex > 0) { + // If not the first child, need to figure out the width + // of output types from all the preceding namespaces + assert ancestorScope instanceof ListScope; + List<SqlValidatorNamespace> children = + ((ListScope) ancestorScope).getChildren(); + + for (int i = 0; i < childNamespaceIndex; i++) { + SqlValidatorNamespace child = children.get(i); + namespaceOffset += + child.getRowType().getFieldCount(); + } + } + + RexFieldAccess topLevelFieldAccess = fieldAccess; + while (topLevelFieldAccess.getReferenceExpr() instanceof RexFieldAccess) { + topLevelFieldAccess = (RexFieldAccess) topLevelFieldAccess.getReferenceExpr(); + } + final RelDataTypeField field = rowType.getFieldList() + .get(topLevelFieldAccess.getField().getIndex() - namespaceOffset); + int pos = namespaceOffset + field.getIndex(); + + assert field.getType() + == topLevelFieldAccess.getField().getType(); + + assert pos != -1; + + if (bb.mapRootRelToFieldProjection.containsKey(bb.root)) { + // bb.root is an aggregate and only projects group by + // keys. + Map<Integer, Integer> exprProjection = + bb.mapRootRelToFieldProjection.get(bb.root); + + // sub-query can reference group by keys projected from + // the root of the outer relation. + if (exprProjection.containsKey(pos)) { + pos = exprProjection.get(pos); + } else { + // correl not grouped + throw new AssertionError("Identifier '" + originalRelName + "." + + originalFieldName + "' is not a group expr"); + } + } + + requiredColumns.set(pos); + correlNames.add(correlName); + } + + if (correlNames.isEmpty()) { + // None of the correlating variables originated in this scope. + return null; + } + + RelNode r = r0; + if (correlNames.size() > 1) { + // The same table was referenced more than once. + // So we deduplicate + r = DeduplicateCorrelateVariables.go(rexBuilder, correlNames.get(0), + Util.skip(correlNames), r0); + } + return new CorrelationUse(correlNames.get(0), requiredColumns.build(), r); + } + + /** + * Determines whether a sub-query is non-correlated. Note that a + * non-correlated sub-query can contain correlated references, provided those + * references do not reference select statements that are parents of the + * sub-query. + * + * @param subq the sub-query + * @param bb blackboard used while converting the sub-query, i.e., the + * blackboard of the parent query of this sub-query + * @return true if the sub-query is non-correlated + */ + private boolean isSubQueryNonCorrelated(RelNode subq, Blackboard bb) { + Set<CorrelationId> correlatedVariables = RelOptUtil.getVariablesUsed(subq); + for (CorrelationId correlName : correlatedVariables) { + DeferredLookup lookup = mapCorrelToDeferred.get(correlName); + String originalRelName = lookup.getOriginalRelName(); + + final SqlNameMatcher nameMatcher = + lookup.bb.scope.getValidator().getCatalogReader().nameMatcher(); + final SqlValidatorScope.ResolvedImpl resolved = + new SqlValidatorScope.ResolvedImpl(); + lookup.bb.scope.resolve(ImmutableList.of(originalRelName), nameMatcher, + false, resolved); + + SqlValidatorScope ancestorScope = resolved.only().scope; + + // If the correlated reference is in a scope that's "above" the + // sub-query, then this is a correlated sub-query. + SqlValidatorScope parentScope = bb.scope; + do { + if (ancestorScope == parentScope) { + return false; + } + if (parentScope instanceof DelegatingScope) { + parentScope = ((DelegatingScope) parentScope).getParent(); + } else { + break; + } + } while (parentScope != null); + } + return true; + } + + /** + * Returns a list of fields to be prefixed to each relational expression. + * + * @return List of system fields + */ + protected List<RelDataTypeField> getSystemFields() { + return Collections.emptyList(); + } + + private RexNode convertJoinCondition(Blackboard bb, + SqlValidatorNamespace leftNamespace, + SqlValidatorNamespace rightNamespace, + SqlNode condition, + JoinConditionType conditionType, + RelNode leftRel, + RelNode rightRel) { + if (condition == null) { + return rexBuilder.makeLiteral(true); + } + bb.setRoot(ImmutableList.of(leftRel, rightRel)); + replaceSubQueries(bb, condition, RelOptUtil.Logic.UNKNOWN_AS_FALSE); + switch (conditionType) { + case ON: + bb.setRoot(ImmutableList.of(leftRel, rightRel)); + return bb.convertExpression(condition); + case USING: + final SqlNodeList list = (SqlNodeList) condition; + final List<String> nameList = new ArrayList<>(); + for (SqlNode columnName : list) { + final SqlIdentifier id = (SqlIdentifier) columnName; + String name = id.getSimple(); + nameList.add(name); + } + return convertUsing(leftNamespace, rightNamespace, nameList); + default: + throw Util.unexpected(conditionType); + } + } + + /** + * Returns an expression for matching columns of a USING clause or inferred + * from NATURAL JOIN. "a JOIN b USING (x, y)" becomes "a.x = b.x AND a.y = + * b.y". Returns null if the column list is empty. + * + * @param leftNamespace Namespace of left input to join + * @param rightNamespace Namespace of right input to join + * @param nameList List of column names to join on + * @return Expression to match columns from name list, or true if name list + * is empty + */ + private RexNode convertUsing(SqlValidatorNamespace leftNamespace, + SqlValidatorNamespace rightNamespace, + List<String> nameList) { + final SqlNameMatcher nameMatcher = catalogReader.nameMatcher(); + final List<RexNode> list = Lists.newArrayList(); + for (String name : nameList) { + List<RexNode> operands = new ArrayList<>(); + int offset = 0; + for (SqlValidatorNamespace n : ImmutableList.of(leftNamespace, + rightNamespace)) { + final RelDataType rowType = n.getRowType(); + final RelDataTypeField field = nameMatcher.field(rowType, name); + operands.add( + rexBuilder.makeInputRef(field.getType(), + offset + field.getIndex())); + offset += rowType.getFieldList().size(); + } + list.add(rexBuilder.makeCall(SqlStdOperatorTable.EQUALS, operands)); + } + return RexUtil.composeConjunction(rexBuilder, list, false); + } + + private static JoinRelType convertJoinType(JoinType joinType) { + switch (joinType) { + case COMMA: + case INNER: + case CROSS: + return JoinRelType.INNER; + case FULL: + return JoinRelType.FULL; + case LEFT: + return JoinRelType.LEFT; + case RIGHT: + return JoinRelType.RIGHT; + default: + throw Util.unexpected(joinType); + } + } + + /** + * Converts the SELECT, GROUP BY and HAVING clauses of an aggregate query. + * + * <p>This method extracts SELECT, GROUP BY and HAVING clauses, and creates + * an {@link AggConverter}, then delegates to {@link #createAggImpl}. + * Derived class may override this method to change any of those clauses or + * specify a different {@link AggConverter}. + * + * @param bb Scope within which to resolve identifiers + * @param select Query + * @param orderExprList Additional expressions needed to implement ORDER BY + */ + protected void convertAgg( + Blackboard bb, + SqlSelect select, + List<SqlNode> orderExprList) { + assert bb.root != null : "precondition: child != null"; + SqlNodeList groupList = select.getGroup(); + SqlNodeList selectList = select.getSelectList(); + SqlNode having = select.getHaving(); + + final AggConverter aggConverter = new AggConverter(bb, select); + createAggImpl( + bb, + aggConverter, + selectList, + groupList, + having, + orderExprList); + } + + protected final void createAggImpl( + Blackboard bb, + final AggConverter aggConverter, + SqlNodeList selectList, + SqlNodeList groupList, + SqlNode having, + List<SqlNode> orderExprList) { + // Find aggregate functions in SELECT and HAVING clause + final AggregateFinder aggregateFinder = new AggregateFinder(); + selectList.accept(aggregateFinder); + if (having != null) { + having.accept(aggregateFinder); + } + + // first replace the sub-queries inside the aggregates + // because they will provide input rows to the aggregates. + replaceSubQueries(bb, aggregateFinder.list, + RelOptUtil.Logic.TRUE_FALSE_UNKNOWN); + + // If group-by clause is missing, pretend that it has zero elements. + if (groupList == null) { + groupList = SqlNodeList.EMPTY; + } + + replaceSubQueries(bb, groupList, RelOptUtil.Logic.TRUE_FALSE_UNKNOWN); + + // register the group exprs
<TRUNCATED>
