You are viewing a plain text version of this content. The canonical link for it is here.
Posted to commits@kylin.apache.org by li...@apache.org on 2015/06/18 09:31:21 UTC
[08/13] incubator-kylin git commit: KYLIN-780, query compile pass
http://git-wip-us.apache.org/repos/asf/incubator-kylin/blob/5d94f1aa/atopcalcite/src/main/java/org/apache/calcite/sql2rel/SqlToRelConverter.java
----------------------------------------------------------------------
diff --git a/atopcalcite/src/main/java/org/apache/calcite/sql2rel/SqlToRelConverter.java b/atopcalcite/src/main/java/org/apache/calcite/sql2rel/SqlToRelConverter.java
new file mode 100644
index 0000000..2508629
--- /dev/null
+++ b/atopcalcite/src/main/java/org/apache/calcite/sql2rel/SqlToRelConverter.java
@@ -0,0 +1,4978 @@
+/*
+ * OVERRIDE POINT:
+ * - getInSubqueryThreshold(), was `20`, now `Integer.MAX_VALUE`
+ * - isTrimUnusedFields(), override to false
+ * - AggConverter.visit(SqlCall), skip column reading for COUNT(COL), for https://jirap.corp.ebay.com/browse/KYLIN-104
+ */
+
+/*
+ * 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;
+
+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.RelOptQuery;
+import org.apache.calcite.plan.RelOptSamplingParameters;
+import org.apache.calcite.plan.RelOptTable;
+import org.apache.calcite.plan.RelOptUtil;
+import org.apache.calcite.prepare.Prepare;
+import org.apache.calcite.prepare.RelOptTableImpl;
+import org.apache.calcite.rel.RelCollation;
+import org.apache.calcite.rel.RelCollationImpl;
+import org.apache.calcite.rel.RelFieldCollation;
+import org.apache.calcite.rel.RelNode;
+import org.apache.calcite.rel.RelShuttle;
+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.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.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.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.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.RelColumnMapping;
+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.RexUtil;
+import org.apache.calcite.rex.RexVisitorImpl;
+import org.apache.calcite.rex.RexWindowBound;
+import org.apache.calcite.schema.ModifiableTable;
+import org.apache.calcite.schema.TranslatableTable;
+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.SqlDataTypeSpec;
+import org.apache.calcite.sql.SqlDelete;
+import org.apache.calcite.sql.SqlDynamicParam;
+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.SqlMerge;
+import org.apache.calcite.sql.SqlNode;
+import org.apache.calcite.sql.SqlNodeList;
+import org.apache.calcite.sql.SqlOperator;
+import org.apache.calcite.sql.SqlOperatorTable;
+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.SqlUpdate;
+import org.apache.calcite.sql.SqlUtil;
+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.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.SqlValidatorUtil;
+import org.apache.calcite.util.ImmutableBitSet;
+import org.apache.calcite.util.ImmutableIntList;
+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.mapping.Mappings;
+import org.apache.calcite.util.trace.CalciteTrace;
+import org.apache.calcite.sql.SqlNumericLiteral;
+
+import com.google.common.base.Function;
+import com.google.common.collect.ImmutableList;
+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 com.google.common.collect.Sets;
+
+import java.lang.reflect.Type;
+import java.math.BigDecimal;
+import java.util.AbstractList;
+import java.util.ArrayList;
+import java.util.Collection;
+import java.util.Collections;
+import java.util.EnumSet;
+import java.util.HashMap;
+import java.util.List;
+import java.util.Map;
+import java.util.Set;
+import java.util.Stack;
+import java.util.TreeSet;
+import java.util.logging.Level;
+import java.util.logging.Logger;
+
+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 Function<SubQuery, SqlNode> FN =
+ new Function<SubQuery, SqlNode>() {
+ public SqlNode apply(SubQuery input) {
+ return input.node;
+ }
+ };
+ private static final BigDecimal TWO = BigDecimal.valueOf(2L);
+
+ //~ Instance fields --------------------------------------------------------
+
+ protected final SqlValidator validator;
+ protected final RexBuilder rexBuilder;
+ protected final Prepare.CatalogReader catalogReader;
+ protected final RelOptCluster cluster;
+ private DefaultValueFactory defaultValueFactory;
+ private SubqueryConverter subqueryConverter;
+ protected final List<RelNode> leaves = new ArrayList<RelNode>();
+ private final List<SqlDynamicParam> dynamicParamSqlNodes =
+ new ArrayList<SqlDynamicParam>();
+ private final SqlOperatorTable opTab;
+ private boolean shouldConvertTableAccess;
+ protected final RelDataTypeFactory typeFactory;
+ private final SqlNodeToRexConverter exprConverter;
+ private boolean decorrelationEnabled;
+ private boolean trimUnusedFields;
+ private boolean shouldCreateValuesRel;
+ private boolean isExplain;
+ private int nDynamicParamsInExplain;
+
+ /**
+ * Fields used in name resolution for correlated subqueries.
+ */
+ private final Map<String, DeferredLookup> mapCorrelToDeferred =
+ new HashMap<String, DeferredLookup>();
+ private int nextCorrel = 0;
+
+ private static final String CORREL_PREFIX = "$cor";
+
+ /**
+ * Stack of names of datasets requested by the <code>
+ * TABLE(SAMPLE(<datasetName>, <query>))</code> construct.
+ */
+ private final Stack<String> datasetStack = new Stack<String>();
+
+ /**
+ * Mapping of non-correlated subqueries that have been converted to their
+ * equivalent constants. Used to avoid re-evaluating the subquery if it's
+ * already been evaluated.
+ */
+ private final Map<SqlNode, RexNode> mapConvertedNonCorrSubqs =
+ new HashMap<SqlNode, RexNode>();
+
+ 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
+ */
+ public SqlToRelConverter(
+ RelOptTable.ViewExpander viewExpander,
+ SqlValidator validator,
+ Prepare.CatalogReader catalogReader,
+ RelOptPlanner planner,
+ RexBuilder rexBuilder,
+ SqlRexConvertletTable convertletTable) {
+ this.viewExpander = viewExpander;
+ this.opTab =
+ (validator
+ == null) ? SqlStdOperatorTable.instance()
+ : validator.getOperatorTable();
+ this.validator = validator;
+ this.catalogReader = catalogReader;
+ this.defaultValueFactory = new NullDefaultValueFactory();
+ this.subqueryConverter = new NoOpSubqueryConverter();
+ this.rexBuilder = rexBuilder;
+ this.typeFactory = rexBuilder.getTypeFactory();
+ RelOptQuery query = new RelOptQuery(planner);
+ this.cluster = query.createCluster(typeFactory, rexBuilder);
+ this.shouldConvertTableAccess = true;
+ this.exprConverter =
+ new SqlNodeToRexConverterImpl(convertletTable);
+ decorrelationEnabled = true;
+ trimUnusedFields = false;
+ shouldCreateValuesRel = true;
+ isExplain = false;
+ nDynamicParamsInExplain = 0;
+ }
+
+ //~ 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 = nDynamicParamsInExplain;
+ if (increment) {
+ ++nDynamicParamsInExplain;
+ }
+ return retVal;
+ }
+
+ /**
+ * @return mapping of non-correlated subqueries 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 subqueries the
+ * elements from another map that contains non-correlated subqueries that
+ * have been converted by another SqlToRelConverter.
+ *
+ * @param alreadyConvertedNonCorrSubqs the other map
+ */
+ public void addConvertedNonCorrSubqs(
+ Map<SqlNode, RexNode> alreadyConvertedNonCorrSubqs) {
+ mapConvertedNonCorrSubqs.putAll(alreadyConvertedNonCorrSubqs);
+ }
+
+ /**
+ * Set a new DefaultValueFactory. To have any effect, this must be called
+ * before any convert method.
+ *
+ * @param factory new DefaultValueFactory
+ */
+ public void setDefaultValueFactory(DefaultValueFactory factory) {
+ defaultValueFactory = factory;
+ }
+
+ /**
+ * 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;
+ }
+
+ /**
+ * Indicates that the current statement is part of an EXPLAIN PLAN statement
+ *
+ * @param nDynamicParams number of dynamic parameters in the statement
+ */
+ public void setIsExplain(int nDynamicParams) {
+ isExplain = true;
+ nDynamicParamsInExplain = nDynamicParams;
+ }
+
+ /**
+ * Controls whether table access references are converted to physical rels
+ * immediately. The optimizer doesn't like leaf rels to have
+ * {@link Convention#NONE}. However, if we are doing further conversion
+ * passes (e.g. {@link RelStructuredTypeFlattener}), then we may need to
+ * defer conversion. To have any effect, this must be called before any
+ * convert method.
+ *
+ * @param enabled true for immediate conversion (the default); false to
+ * generate logical LogicalTableScan instances
+ */
+ public void enableTableAccessConversion(boolean enabled) {
+ shouldConvertTableAccess = enabled;
+ }
+
+ /**
+ * Controls whether instances of
+ * {@link org.apache.calcite.rel.logical.LogicalValues} are generated. These
+ * may not be supported by all physical implementations. To have any effect,
+ * this must be called before any convert method.
+ *
+ * @param enabled true to allow LogicalValues to be generated (the default);
+ * false to force substitution of Project+OneRow instead
+ */
+ public void enableValuesRelCreation(boolean enabled) {
+ shouldCreateValuesRel = enabled;
+ }
+
+ private void checkConvertedType(SqlNode query, RelNode result) {
+ if (!query.isA(SqlKind.DML)) {
+ // 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.)
+ RelDataType convertedRowType = result.getRowType();
+ if (!checkConvertedRowType(query, convertedRowType)) {
+ RelDataType validatedRowType =
+ validator.getValidatedNodeType(query);
+ validatedRowType = uniquifyFields(validatedRowType);
+ throw Util.newInternal("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());
+ return typeFlattener.rewrite(rootRel, restructure);
+ }
+
+ /**
+ * If subquery 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 rootRel Relational expression that is at the root of the tree
+ * @return Trimmed relational expression
+ */
+ public RelNode trimUnusedFields(RelNode rootRel) {
+ // Trim fields that are not used by their consumer.
+ if (isTrimUnusedFields()) {
+ final RelFieldTrimmer trimmer = newFieldTrimmer();
+ rootRel = trimmer.trim(rootRel);
+ boolean dumpPlan = SQL2REL_LOGGER.isLoggable(Level.FINE);
+ if (dumpPlan) {
+ SQL2REL_LOGGER.fine(
+ RelOptUtil.dumpPlan(
+ "Plan after trimming unused fields",
+ rootRel,
+ false,
+ SqlExplainLevel.EXPPLAN_ATTRIBUTES));
+ }
+ }
+ return rootRel;
+ }
+
+ /**
+ * Creates a RelFieldTrimmer.
+ *
+ * @return Field trimmer
+ */
+ protected RelFieldTrimmer newFieldTrimmer() {
+ return new RelFieldTrimmer(validator);
+ }
+
+ /**
+ * 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 RelNode convertQuery(
+ SqlNode query,
+ final boolean needsValidation,
+ final boolean top) {
+ if (needsValidation) {
+ query = validator.validate(query);
+ }
+
+ RelNode result = convertQueryRecursive(query, top, null);
+ checkConvertedType(query, result);
+
+ boolean dumpPlan = SQL2REL_LOGGER.isLoggable(Level.FINE);
+ if (dumpPlan) {
+ SQL2REL_LOGGER.fine(
+ RelOptUtil.dumpPlan(
+ "Plan after converting SqlNode to RelNode",
+ result,
+ false,
+ SqlExplainLevel.EXPPLAN_ATTRIBUTES));
+ }
+
+ return result;
+ }
+
+ protected boolean checkConvertedRowType(
+ SqlNode query,
+ RelDataType convertedRowType) {
+ RelDataType validatedRowType = validator.getValidatedNodeType(query);
+ validatedRowType = uniquifyFields(validatedRowType);
+
+ return RelOptUtil.equal(
+ "validated row type",
+ validatedRowType,
+ "converted row type",
+ convertedRowType,
+ false);
+ }
+
+ protected RelDataType uniquifyFields(RelDataType rowType) {
+ return validator.getTypeFactory().createStructType(
+ RelOptUtil.getFieldTypeList(rowType),
+ SqlValidatorUtil.uniquify(rowType.getFieldNames()));
+ }
+
+ /**
+ * Converts a SELECT statement's parse tree into a relational expression.
+ */
+ public RelNode convertSelect(SqlSelect select) {
+ final SqlValidatorScope selectScope = validator.getWhereScope(select);
+ final Blackboard bb = createBlackboard(selectScope, null);
+ convertSelectImpl(bb, select);
+ return bb.root;
+ }
+
+ /**
+ * Factory method for creating translation workspace.
+ */
+ protected Blackboard createBlackboard(
+ SqlValidatorScope scope,
+ Map<String, RexNode> nameToNodeMap) {
+ return new Blackboard(scope, nameToNodeMap);
+ }
+
+ /**
+ * Implementation of {@link #convertSelect(SqlSelect)}; derived class may
+ * override.
+ */
+ protected void convertSelectImpl(
+ final Blackboard bb,
+ SqlSelect select) {
+ convertFrom(
+ bb,
+ select.getFrom());
+ convertWhere(
+ bb,
+ select.getWhere());
+
+ List<SqlNode> orderExprList = new ArrayList<SqlNode>();
+ List<RelFieldCollation> collationList =
+ new ArrayList<RelFieldCollation>();
+ gatherOrderExprs(
+ bb,
+ select,
+ select.getOrderList(),
+ orderExprList,
+ collationList);
+ final RelCollation collation =
+ cluster.traitSetOf().canonize(RelCollationImpl.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();
+ List<Integer> origins = new ArrayList<Integer>();
+ 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 =
+ new LogicalProject(
+ cluster,
+ rel,
+ Pair.left(newProjects),
+ Pair.right(newProjects),
+ LogicalProject.Flags.BOXED);
+
+ 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 =
+ new LogicalProject(
+ cluster,
+ rel,
+ Pair.left(undoProjects),
+ Pair.right(undoProjects),
+ LogicalProject.Flags.BOXED);
+
+ 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) {
+ assert collation.getFieldCollations().isEmpty();
+ if (offset == null && fetch == null) {
+ return;
+ }
+ }
+
+ // Create a sorter using the previously constructed collations.
+ bb.setRoot(
+ new Sort(
+ cluster,
+ cluster.traitSetOf(Convention.NONE, collation),
+ 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.
+ if (orderExprList.size() > 0) {
+ List<RexNode> exprs = new ArrayList<RexNode>();
+ 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(
+ new LogicalProject(
+ cluster,
+ cluster.traitSetOf(RelCollationImpl.PRESERVE),
+ bb.root,
+ exprs,
+ cluster.getTypeFactory().createStructType(
+ rowType.getFieldList().subList(0, fieldCount)),
+ Project.Flags.BOXED),
+ 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 sqlNode the root node from which to look for NOT operators
+ * @return the transformed SqlNode representation with NOT pushed down.
+ */
+ private static SqlNode pushDownNotForIn(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(sqlOperands[i]);
+ }
+ return 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] =
+ SqlStdOperatorTable.NOT.createCall(
+ SqlParserPos.ZERO,
+ andOperands[i]);
+ }
+ for (int i = 0; i < orOperands.length; i++) {
+ orOperands[i] = pushDownNotForIn(orOperands[i]);
+ }
+ return 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] =
+ SqlStdOperatorTable.NOT.createCall(
+ SqlParserPos.ZERO,
+ orOperands[i]);
+ }
+ for (int i = 0; i < andOperands.length; i++) {
+ andOperands[i] = pushDownNotForIn(andOperands[i]);
+ }
+ return 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(notOperands[0]);
+ } else if (childSqlCall.getOperator() instanceof SqlInOperator) {
+ SqlNode[] inOperands = childSqlCall.getOperands();
+ SqlInOperator inOp =
+ (SqlInOperator) childSqlCall.getOperator();
+ if (inOp.isNotIn()) {
+ return SqlStdOperatorTable.IN.createCall(
+ SqlParserPos.ZERO,
+ inOperands[0],
+ inOperands[1]);
+ } else {
+ return 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;
+ }
+ }
+
+ /**
+ * 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(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()) {
+ bb.setRoot(
+ RelOptUtil.createFilter(bb.root, convertedWhere),
+ 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 Pair<RelNode, Boolean> converted;
+ switch (subQuery.node.getKind()) {
+ case CURSOR:
+ convertCursor(bb, subQuery);
+ return;
+
+ case MULTISET_QUERY_CONSTRUCTOR:
+ case MULTISET_VALUE_CONSTRUCTOR:
+ rel = convertMultisets(ImmutableList.of(subQuery.node), bb);
+ subQuery.expr = bb.register(rel, JoinRelType.INNER);
+ return;
+
+ case IN:
+ call = (SqlBasicCall) subQuery.node;
+ final SqlNode[] operands = call.getOperands();
+
+ SqlNode leftKeyNode = operands[0];
+ query = operands[1];
+
+ 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 isNotIn = ((SqlInOperator) call.getOperator()).isNotIn();
+ if (query instanceof SqlNodeList) {
+ SqlNodeList valueList = (SqlNodeList) query;
+ if (!containsNullLiteral(valueList)
+ && valueList.size() < getInSubqueryThreshold()) {
+ // We're under the threshold, so convert to OR.
+ subQuery.expr =
+ convertInToOr(
+ bb,
+ leftKeys,
+ valueList,
+ isNotIn);
+ 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 boolean outerJoin = bb.subqueryNeedsOuterJoin
+ || isNotIn
+ || subQuery.logic == RelOptUtil.Logic.TRUE_FALSE_UNKNOWN;
+ converted =
+ convertExists(query, RelOptUtil.SubqueryType.IN, subQuery.logic,
+ outerJoin);
+ if (converted.right) {
+ // 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.left.getInput(0); // fragile
+ final int keyCount = leftKeys.size();
+ final List<Integer> args = ImmutableIntList.range(0, keyCount);
+ LogicalAggregate aggregate =
+ new LogicalAggregate(cluster, seek, false, ImmutableBitSet.of(),
+ null,
+ ImmutableList.of(
+ new AggregateCall(SqlStdOperatorTable.COUNT, false,
+ ImmutableList.<Integer>of(), longType, null),
+ new AggregateCall(SqlStdOperatorTable.COUNT, false,
+ args, longType, null)));
+ LogicalJoin join =
+ new LogicalJoin(cluster, bb.root, aggregate,
+ rexBuilder.makeLiteral(true), JoinRelType.INNER,
+ ImmutableSet.<String>of());
+ bb.setRoot(join, false);
+ }
+ RexNode rex =
+ bb.register(converted.left,
+ outerJoin ? JoinRelType.LEFT : JoinRelType.INNER, leftKeys);
+
+ subQuery.expr = translateIn(subQuery, bb.root, rex);
+ if (isNotIn) {
+ 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 subquery 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 subquery returned 0 or >= 1 row.
+ call = (SqlBasicCall) subQuery.node;
+ query = call.getOperands()[0];
+ converted = convertExists(query, RelOptUtil.SubqueryType.EXISTS,
+ subQuery.logic, true);
+ assert !converted.right;
+ if (convertNonCorrelatedSubQuery(subQuery, bb, converted.left, true)) {
+ return;
+ }
+ subQuery.expr = bb.register(converted.left, JoinRelType.LEFT);
+ return;
+
+ case SCALAR_QUERY:
+ // Convert the subquery. If it's non-correlated, convert it
+ // to a constant expression.
+ call = (SqlBasicCall) subQuery.node;
+ query = call.getOperands()[0];
+ converted = convertExists(query, RelOptUtil.SubqueryType.SCALAR,
+ subQuery.logic, true);
+ assert !converted.right;
+ if (convertNonCorrelatedSubQuery(subQuery, bb, converted.left, false)) {
+ return;
+ }
+ rel = convertToSingleValueSubq(query, converted.left);
+ 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);
+ assert !converted.right;
+ subQuery.expr = bb.register(converted.left, JoinRelType.LEFT);
+ return;
+
+ default:
+ throw Util.newInternal("unexpected kind of subquery :" + subQuery.node);
+ }
+ }
+
+ private RexNode translateIn(SubQuery subQuery, RelNode root,
+ final RexNode rex) {
+ switch (subQuery.logic) {
+ case TRUE:
+ return rexBuilder.makeLiteral(true);
+
+ 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 subquery 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(0)).getLeft();
+ final int leftLeftCount = leftLeft.getRowType().getFieldCount();
+ final RelDataType nullableBooleanType =
+ typeFactory.createTypeWithNullability(
+ typeFactory.createSqlType(SqlTypeName.BOOLEAN), true);
+ 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(SqlTypeName.BOOLEAN);
+
+ 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(
+ nullableBooleanType,
+ SqlStdOperatorTable.CASE,
+ args.build());
+
+ default:
+ throw new AssertionError(subQuery.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 subquery is non-correlated and if so, converts it to a
+ * constant.
+ *
+ * @param subQuery the call that references the subquery
+ * @param bb blackboard used to convert the subquery
+ * @param converted RelNode tree corresponding to the subquery
+ * @param isExists true if the subquery is part of an EXISTS expression
+ * @return if the subquery 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 subquery has already been converted
+ // because it's a nested subquery. If so, don't re-evaluate
+ // it again.
+ RexNode constExpr = mapConvertedNonCorrSubqs.get(call);
+ if (constExpr == null) {
+ constExpr =
+ subqueryConverter.convertSubquery(
+ call,
+ this,
+ isExists,
+ 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 (selectExprCall.getOperator()
+ instanceof SqlAggFunction) {
+ 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) {
+ List<RexNode> comparisons = new ArrayList<RexNode>();
+ for (SqlNode rightVals : valuesList) {
+ RexNode rexComparison;
+ if (leftKeys.size() == 1) {
+ rexComparison =
+ rexBuilder.makeCall(
+ SqlStdOperatorTable.EQUALS,
+ leftKeys.get(0),
+ bb.convertExpression(rightVals));
+ } else {
+ assert rightVals instanceof SqlCall;
+ final SqlBasicCall call = (SqlBasicCall) rightVals;
+ assert (call.getOperator() instanceof SqlRowOperator)
+ && call.getOperands().length == 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, 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;
+ }
+
+ /**
+ * 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 20
+ */
+ protected int getInSubqueryThreshold() {
+ // OVERRIDE POINT
+ return Integer.MAX_VALUE; // was 20
+ }
+
+ /**
+ * Converts an EXISTS or IN predicate into a join. For EXISTS, the subquery
+ * 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 needsOuterJoin Whether an outer join is needed
+ * @return join expression
+ * @pre extraExpr == null || extraName != null
+ */
+ private Pair<RelNode, Boolean> convertExists(
+ SqlNode seek,
+ RelOptUtil.SubqueryType subqueryType,
+ RelOptUtil.Logic logic,
+ boolean needsOuterJoin) {
+ final SqlValidatorScope seekScope =
+ (seek instanceof SqlSelect)
+ ? validator.getSelectScope((SqlSelect) seek)
+ : null;
+ final Blackboard seekBb = createBlackboard(seekScope, null);
+ RelNode seekRel = convertQueryOrInList(seekBb, seek);
+
+ return RelOptUtil.createExistsPlan(seekRel, subqueryType, logic,
+ needsOuterJoin);
+ }
+
+ private RelNode convertQueryOrInList(
+ Blackboard bb,
+ SqlNode seek) {
+ // 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,
+ null);
+ } else {
+ return convertQueryRecursive(seek, false, null);
+ }
+ }
+
+ 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
+ // subqueries), 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);
+ }
+
+ List<RelNode> unionInputs = new ArrayList<RelNode>();
+ 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) || !shouldCreateValuesRel) {
+ // 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) && shouldCreateValuesRel) {
+ 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 =
+ new LogicalValues(
+ cluster,
+ rowType,
+ tupleList.build());
+ RelNode resultRel;
+ if (unionInputs.isEmpty()) {
+ resultRel = values;
+ } else {
+ if (!values.getTuples().isEmpty()) {
+ unionInputs.add(values);
+ }
+ LogicalUnion union =
+ new LogicalUnion(
+ cluster,
+ unionInputs,
+ true);
+ resultRel = union;
+ }
+ 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)) {
+ 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(
+ Util.rpad(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
+ * subquery
+ */
+ 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 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) {
+ if (kind == SqlKind.OR
+ || kind == SqlKind.NOT) {
+ // It's always correct to outer join subquery with
+ // containing query; however, when predicates involve Or
+ // or NOT, outer join might be necessary.
+ bb.subqueryNeedsOuterJoin = true;
+ }
+ for (SqlNode operand : ((SqlCall) node).getOperandList()) {
+ if (operand != null) {
+ // In the case of an IN expression, locate scalar
+ // subqueries 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 subqueries inside the IN
+ // expression, register the IN expression itself. We need to
+ // register the scalar subqueries first so they can be converted
+ // before the IN expression is converted.
+ if (kind == SqlKind.IN) {
+ if (logic == RelOptUtil.Logic.TRUE_FALSE_UNKNOWN
+ && !validator.getValidatedNodeType(node).isNullable()) {
+ logic = RelOptUtil.Logic.UNKNOWN_AS_FALSE;
+ }
+ // TODO: This conversion is only valid in the WHERE clause
+ if (logic == RelOptUtil.Logic.UNKNOWN_AS_FALSE
+ && !bb.subqueryNeedsOuterJoin) {
+ 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();
+ Blackboard bb =
+ createBlackboard(
+ new ParameterScope((SqlValidatorImpl) validator, nameToTypeMap),
+ null);
+ 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<String, RelDataType>();
+ for (Map.Entry<String, RexNode> entry : nameToNodeMap.entrySet()) {
+ nameToTypeMap.put(entry.getKey(), entry.getValue().getType());
+ }
+ Blackboard bb =
+ createBlackboard(
+ new ParameterScope((SqlValidatorImpl) validator, nameToTypeMap),
+ nameToNodeMap);
+ 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);
+ 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 {
+ Util.permAssert(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) {
+ SqlCall call;
+ final SqlNode[] operands;
+ switch (from.getKind()) {
+ case AS:
+ operands = ((SqlBasicCall) from).getOperands();
+ convertFrom(bb, operands[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 Util.newInternal(
+ "unknown TABLESAMPLE type: " + sampleSpec);
+ }
+ return;
+
+ case IDENTIFIER:
+ final SqlValidatorNamespace fromNamespace =
+ validator.getNamespace(from).resolve();
+ if (fromNamespace.getNode() != null) {
+ convertFrom(bb, fromNamespace.getNode());
+ return;
+ }
+ final String datasetName =
+ datasetStack.isEmpty() ? null : datasetStack.peek();
+ boolean[] usedDataset = {false};
+ RelOptTable table =
+ SqlValidatorUtil.getRelOptTable(
+ fromNamespace,
+ catalogReader,
+ datasetName,
+ usedDataset);
+ final RelNode tableRel;
+ if (shouldConvertTableAccess) {
+ tableRel = toRel(table);
+ } else {
+ tableRel = new LogicalTableScan(cluster, table);
+ }
+ bb.setRoot(tableRel, true);
+ if (usedDataset[0]) {
+ bb.setDataset(datasetName);
+ }
+ return;
+
+ case JOIN:
+ final SqlJoin join = (SqlJoin) from;
+ final Blackboard fromBlackboard =
+ createBlackboard(validator.getJoinScope(from), null);
+ SqlNode left = join.getLeft();
+ SqlNode right = join.getRight();
+ final boolean isNatural = join.isNatural();
+ final JoinType joinType = join.getJoinType();
+ final Blackboard leftBlackboard =
+ createBlackboard(
+ Util.first(validator.getJoinScope(left),
+ ((DelegatingScope) bb.scope).getParent()), null);
+ final Blackboard rightBlackboard =
+ createBlackboard(
+ Util.first(validator.getJoinScope(right),
+ ((DelegatingScope) bb.scope).getParent()), null);
+ convertFrom(leftBlackboard, left);
+ RelNode leftRel = leftBlackboard.root;
+ convertFrom(rightBlackboard, right);
+ RelNode rightRel = rightBlackboard.root;
+ JoinRelType convertedJoinType = convertJoinType(joinType);
+ RexNode conditionExp;
+ if (isNatural) {
+ final List<String> columnList =
+ SqlValidatorUtil.deriveNaturalJoinColumnList(
+ validator.getNamespace(left).getRowType(),
+ validator.getNamespace(right).getRowType());
+ conditionExp = convertUsing(leftRel, rightRel, columnList);
+ } else {
+ conditionExp =
+ convertJoinCondition(
+ fromBlackboard,
+ 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);
+ bb.setRoot(rel, true);
+ return;
+
+ case VALUES:
+ convertValuesImpl(bb, (SqlCall) from, null);
+ return;
+
+ case UNNEST:
+ final SqlNode node = ((SqlCall) from).operand(0);
+ replaceSubqueries(bb, node, RelOptUtil.Logic.TRUE_FALSE_UNKNOWN);
+ final RelNode childRel =
+ RelOptUtil.createProject(
+ (null != bb.root) ? bb.root : LogicalValues.createOneRow(cluster),
+ Collections.singletonList(bb.convertExpression(node)),
+ Collections.singletonList(validator.deriveAlias(node, 0)),
+ true);
+
+ Uncollect uncollect =
+ new Uncollect(cluster, cluster.traitSetOf(Convention.NONE),
+ childRel);
+ 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;
+ call = call.operand(0);
+ convertCollectionTable(bb, call);
+ return;
+
+ default:
+ throw Util.newInternal("not a join operator " + from);
+ }
+ }
+
+ protected void convertCollectionTable(
+ Blackboard bb,
+ SqlCall call) {
+ final SqlOperator operator = call.getOperator();
+ if (operator == SqlStdOperatorTable.TABLESAMPLE) {
+ final String sampleName =
+ SqlLiteral.stringValue(call.operand(0));
+ datasetStack.push(sampleName);
+ SqlCall cursorCall = call.operand(1);
+ SqlNode query = cursorCall.operand(0);
+ RelNode converted = convertQuery(query, false, false);
+ 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.
+ if (operator instanceof SqlUserDefinedTableMacro) {
+ final SqlUserDefinedTableMacro udf =
+ (SqlUserDefinedTableMacro) operator;
+ final TranslatableTable table = udf.getTable(typeFactory,
+ call.getOperandList());
+ final RelDataType rowType = table.getRowType(typeFactory);
+ RelOptTable relOptTable = RelOptTableImpl.create(null, rowType, table);
+ RelNode converted = toRel(relOptTable);
+ bb.setRoot(converted, true);
+ return;
+ }
+
+ Type elementType;
+ if (operator instanceof SqlUserDefinedTableFunction) {
+ SqlUserDefinedTableFunction udtf = (SqlUserDefinedTableFunction) operator;
+ elementType = udtf.getElementType(typeFactory, call.getOperandList());
+ } else {
+ elementType = null;
+ }
+
+ RexNode rexCall = bb.convertExpression(call);
+ final List<RelNode> inputs = bb.retrieveCursors();
+ Set<RelColumnMapping> columnMappings =
+ getColumnMappings(operator);
+ LogicalTableFunctionScan callRel =
+ new LogicalTableFunctionScan(
+ 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;
+
+ Set<String> correlatedVariables = RelOptUtil.getVariablesUsed(rightRel);
+ if (correlatedVariables.size() > 0) {
+ final ImmutableBitSet.Builder requiredColumns = ImmutableBitSet.builder();
+ final List<String> 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 (String correlName : correlatedVariables) {
+ DeferredLookup lookup = mapCorrelToDeferred.get(correlName);
+ RexFieldAccess fieldAccess = lookup.getFieldAccess(correlName);
+ String originalRelName = lookup.getOriginalRelName();
+ String originalFieldName = fieldAccess.getField().getName();
+
+ int[] nsIndexes = {-1};
+ final SqlValidatorScope[] ancestorScopes = {null};
+ SqlValidatorNamespace foundNs =
+ lookup.bb.scope.resolve(
+ ImmutableList.of(originalRelName),
+ ancestorScopes,
+ nsIndexes);
+
+ assert foundNs != null;
+ assert nsIndexes.length == 1;
+
+ int childNamespaceIndex = nsIndexes[0];
+
+ SqlValidatorScope ancestorScope = ancestorScopes[0];
+ 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();
+ }
+ }
+
+ RelDataTypeField field =
+ catalogReader.field(foundNs.getRowType(), originalFieldName);
+ int pos = namespaceOffset + field.getIndex();
+
+ assert field.getType()
+ == lookup.getFieldAccess(correlName).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);
+
+ // subquery 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 Util.newInternal(
+ "Identifier '" + originalRelName + "."
+ + originalFieldName + "' is not a group expr");
+ }
+ }
+
+ requiredColumns.set(pos);
+ correlNames.add(correlName);
+ }
+
+ if (!correlNames.isEmpty()) {
+ if (correlNames.size() > 1) {
+ // The same table was referenced more than once.
+ // So we deduplicate
+ RelShuttle dedup =
+ new DeduplicateCorrelateVariables(rexBuilder,
+ correlNames.get(0),
+ ImmutableSet.copyOf(Util.skip(correlNames)));
+ rightRel = rightRel.accept(dedup);
+ }
+ LogicalCorrelate corr = new LogicalCorrelate(
+ rightRel.getCluster(),
+ leftRel,
+ rightRel,
+ new CorrelationId(correlNames.get(0)),
+ requiredColumns.build(),
+ SemiJoinType.of(joinType));
+ if (!joinCond.isAlwaysTrue()) {
+ return RelOptUtil.createFilter(corr, joinCond);
+ }
+ return corr;
+ }
+ }
+
+ final List<RexNode> extraLeftExprs = new ArrayList<RexNode>();
+ final List<RexNode> extraRightExprs = new ArrayList<RexNode>();
+ final int leftCount = leftRel.getRowType().getFieldCount();
+ final int rightCount = rightRel.getRowType().getFieldCount();
+ if (!containsGet(joinCond)) {
+ joinCond = pushDownJoinConditions(
+ joinCond, leftCount, rightCount, extraLeftExprs, extraRightExprs);
+ }
+ if (!extraLeftExprs.isEmpty()) {
+ final List<RelDataTypeField> fields =
+ leftRel.getRowType().getFieldList();
+ leftRel = RelOptUtil.createProject(
+ leftRel,
+ new AbstractList<Pair<RexNode, String>>() {
+ @Override public int size() {
+ return leftCount + extraLeftExprs.size();
+ }
+
+ @Override public Pair<RexNode, String> get(int index) {
+ if (index < leftCount) {
+ RelDataTypeField field = fields.get(index);
+ return Pair.<RexNode, String>of(
+ new RexInputRef(index, field.getType()),
+ field.getName());
+ } else {
+ return Pair.<RexNode, String>of(
+ extraLeftExprs.get(index - leftCount), null);
+ }
+ }
+ },
+ true);
+ }
+ if (!extraRightExprs.isEmpty()) {
+ final List<RelDataTypeField> fields =
+ rightRel.getRowType().getFieldList();
+ final int newLeftCount = leftCount + extraLeftExprs.size();
+ rightRel = RelOptUtil.createProject(
+ rightRel,
+ new AbstractList<Pair<RexNode, String>>() {
+ @Override public int size() {
+ return rightCount + extraRightExprs.size();
+ }
+
+ @Override public Pair<RexNode, String> get(int index) {
+ if (index < rightCount) {
+ RelDataTypeField field = fields.get(index);
+ return Pair.<RexNode, String>of(
+ new RexInputRef(index, field.getType()),
+ field.getName());
+ } else {
+ return Pair.of(
+ RexUtil.shift(
+ extraRightExprs.get(index - rightCount),
+ -newLeftCount),
+ null);
+ }
+ }
+ },
+ true);
+ }
+ RelNode join = createJoin(
+ leftRel,
+ rightRel,
+ joinCond,
+ joinType,
+ ImmutableSet.<String>of());
+ if (!extraLeftExprs.isEmpty() || !extraRightExprs.isEmpty()) {
+ Mappings.TargetMapping mapping =
+ Mappings.createShiftMapping(
+ leftCount + extraLeftExprs.size()
+ + rightCount + extraRightExprs.size(),
+ 0, 0, leftCount,
+ leftCount, leftCount + extraLeftExprs.size(), rightCount);
+ return RelOptUtil.project(join, mapping);
+ }
+ return join;
+ }
+
+ private static boolean containsGet(RexNode node) {
+ try {
+ node.accept(
+ new RexVisitorImpl<Void>(true) {
+ @Override public Void visitCall(RexCall call) {
+ if (call.getOperator() == RexBuilder.GET_OPERATOR) {
+ throw Util.FoundOne.NULL;
+ }
+ return super.visitCall(call);
+ }
+ });
+ return false;
+ } catch (Util.FoundOne e) {
+ return true;
+ }
+ }
+
+ /**
+ * Pushes down parts of a join condition. For example, given
+ * "emp JOIN dept ON emp.deptno + 1 = dept.deptno", adds a project above
+ * "emp" that computes the expression
+ * "emp.deptno + 1". The resulting join condition is a simple combination
+ * of AND, equals, and input fields.
+ */
+ private RexNode pushDownJoinConditions(
+ RexNode node,
+ int leftCount,
+ int rightCount,
+ List<RexNode> extraLeftExprs,
+ List<RexNode> extraRightExprs) {
+ switch (node.getKind()) {
+ case AND:
+ case OR:
+ case EQUALS:
+ RexCall call = (RexCall) node;
+ List<RexNode> list = new ArrayList<RexNode>();
+ List<RexNode> operands = Lists.newArrayList(call.getOperands());
+ for (int i = 0; i < operands.size(); i++) {
+ RexNode operand = operands.get(i);
+ final int left2 = leftCount + extraLeftExprs.size();
+ final int right2 = rightCount + extraRightExprs.size();
+ final RexNode e =
+ pushDownJoinConditions(
+ operand,
+ leftCount,
+ rightCount,
+ extraLeftExprs,
+ extraRightExprs);
+ final List<RexNode> remainingOperands = Util.skip(operands, i + 1);
+ final int left3 = leftCount + extraLeftExprs.size();
+ final int right3 = rightCount + extraRightExprs.size();
+ fix(remainingOperands, left2, left3);
+ fix(list, left2, left3);
+ list.add(e);
+ }
+ if (!list.equals(call.getOperands())) {
+ return call.clone(call.getType(), list);
+ }
+ return call;
+ case INPUT_REF:
+ case LITERAL:
+ return node;
+ default:
+ ImmutableBitSet bits = RelOptUtil.InputFinder.bits(node);
+ final int mid = leftCount + extraLeftExprs.size();
+ switch (Side.of(bits, mid)) {
+ case LEFT:
+ fix(extraRightExprs, mid, mid + 1);
+ extraLeftExprs.add(node);
+ return new RexInputRef(mid, node.getType());
+ case RIGHT:
+ final int index2 = mid + rightCount + extraRightExprs.size();
+ extraRightExprs.add(node);
+ return new RexInputRef(index2, node.getType());
+ case BOTH:
+ case EMPTY:
+ default:
+ return node;
+ }
+ }
+ }
+
+ private void fix(List<RexNode> operands, int before, int after) {
+ if (before == after) {
+ return;
+ }
+ for (int i = 0; i < operands.size(); i++) {
+ RexNode node = operands.get(i);
+ operands.set(i, RexUtil.shift(node, before, after - before));
+ }
+ }
+
+ /**
+ * Categorizes whether a bit set contains bits left and right of a
+ * line.
+ */
+ enum Side {
+ LEFT, RIGHT, BOTH, EMPTY;
+
+ static Side of(ImmutableBitSet bitSet, int middle) {
+ final int firstBit = bitSet.nextSetBit(0);
+ if (firstBit < 0) {
+ return EMPTY;
+ }
+ if (firstBit >= middle) {
+ return RIGHT;
+ }
+ if (bitSet.nextSetBit(middle) < 0) {
+ return LEFT;
+ }
+ return BOTH;
+ }
+ }
+
+ /**
+ * Determines whether a subquery is non-correlated. Note that a
+ * non-correlated subquery can contain correlated references, provided those
+ * references do not reference select statements that are parents of the
+ * subquery.
+ *
+ * @param subq the subquery
+ * @param bb blackboard used while converting the subquery, i.e., the
+ * blackboard of the parent query of this subquery
+ * @return true if the subquery is non-correlated.
+ */
+ private boolean isSubQueryNonCorrelated(RelNode subq, Blackboard bb) {
+ Set<String> correlatedVariables = RelOptUtil.getVariablesUsed(subq);
+ for (String correlName : correlatedVariables) {
+ DeferredLookup lookup = mapCorrelToDeferred.get(correlName);
+ String originalRelName = lookup.getOriginalRelName();
+
+ int[] nsIndexes = {-1};
+ final SqlValidatorScope[] ancestorScopes = {null};
+ SqlValidatorNamespace foundNs =
+ lookup.bb.scope.resolve(
+ ImmutableList.of(originalRelName),
+ ancestorScopes,
+ nsIndexes);
+
+ assert foundNs != null;
+ assert nsIndexes.length == 1;
+
+ SqlValidatorScope ancestorScope = ancestorScopes[0];
+
+ // If the correlated reference is in a scope that's "above" the
+ // subquery, then this is a correlated subquery.
+ 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,
+ 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:
+ SqlNodeList list = (SqlNodeList) condition;
+ List<String> nameList = new ArrayList<String>();
+ for (SqlNode columnName : list) {
+ final SqlIdentifier id = (SqlIdentifier) columnName;
+ String name = id.getSimple();
+ nameList.add(name);
+ }
+ return convertUsing(leftRel, rightRel, 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 leftRel Left input to the join
+ * @param rightRel Right input to the 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(
+ RelNode leftRel,
+ RelNode rightRel,
+ List<String> nameList) {
+ final List<RexNode> list = Lists.newArrayList();
+ for (String name : nameList) {
+ final RelDataType leftRowType = leftRel.getRowType();
+ RelDataTypeField leftField = catalogReader.field(leftRowType, name);
+ RexNode left =
+ rexBuilder.makeInputRef(
+ leftField.getType(),
+ leftFiel
<TRUNCATED>