kylin-commits mailing list archives

Site index · List index
Message view « Date » · « Thread »
Top « Date » · « Thread »
From shaofeng...@apache.org
Subject [20/50] [abbrv] kylin git commit: KYLIN-1343 Upgrade to calcite 1.6 (with Edward Zhang)
Date Wed, 23 Mar 2016 09:15:04 GMT
http://git-wip-us.apache.org/repos/asf/kylin/blob/f73abf6c/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
index c184f0b..aed7c27 100644
--- a/atopcalcite/src/main/java/org/apache/calcite/sql2rel/SqlToRelConverter.java
+++ b/atopcalcite/src/main/java/org/apache/calcite/sql2rel/SqlToRelConverter.java
@@ -18,6 +18,7 @@
 
 package org.apache.calcite.sql2rel;
 
+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;
@@ -25,26 +26,32 @@ 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.RelShuttle;
+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;
@@ -56,6 +63,7 @@ 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.stream.Delta;
 import org.apache.calcite.rel.stream.LogicalDelta;
 import org.apache.calcite.rel.type.RelDataType;
 import org.apache.calcite.rel.type.RelDataTypeFactory;
@@ -72,8 +80,8 @@ 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.RexVisitorImpl;
 import org.apache.calcite.rex.RexWindowBound;
 import org.apache.calcite.schema.ModifiableTable;
 import org.apache.calcite.schema.ModifiableView;
@@ -85,6 +93,7 @@ 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;
@@ -102,10 +111,12 @@ 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;
@@ -138,8 +149,10 @@ 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.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;
@@ -158,15 +171,16 @@ import com.google.common.collect.Sets;
 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.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;
@@ -178,7 +192,7 @@ import static org.apache.calcite.util.Static.RESOURCE;
  * 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
+ * - AggConverter.translateAgg(...), skip column reading for COUNT(COL), for https://jirap.corp.ebay.com/browse/KYLIN-104
  */
 
 /**
@@ -190,3851 +204,4825 @@ import static org.apache.calcite.util.Static.RESOURCE;
  * {@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);
-
-    //~ 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<>();
-    private final List<SqlDynamicParam> dynamicParamSqlNodes = new ArrayList<>();
-    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<>();
-    private int nextCorrel = 0;
-
-    private static final String CORREL_PREFIX = "$cor";
-
-    /**
-     * Stack of names of datasets requested by the <code>
-     * TABLE(SAMPLE(&lt;datasetName&gt;, &lt;query&gt;))</code> construct.
-     */
-    private final Stack<String> datasetStack = new Stack<>();
-
-    /**
-     * 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<>();
-
-    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
-    // will 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);
-    }
-
-    /* Creates a converter. */
-    public SqlToRelConverter(RelOptTable.ViewExpander viewExpander, SqlValidator validator, Prepare.CatalogReader catalogReader, RelOptCluster cluster, 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 = cluster.getRexBuilder();
-        this.typeFactory = rexBuilder.getTypeFactory();
-        this.cluster = Preconditions.checkNotNull(cluster);
-        this.shouldConvertTableAccess = true;
-        this.exprConverter = new SqlNodeToRexConverterImpl(convertletTable);
-        decorrelationEnabled = true;
-        trimUnusedFields = false;
-        shouldCreateValuesRel = true;
-        isExplain = false;
-        nDynamicParamsInExplain = 0;
-    }
-
-    //~ Methods ----------------------------------------------------------------
+  //~ 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 IN_SUBQUERY_THRESHOLD = 20;
+
+  //~ 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<>();
+  private final List<SqlDynamicParam> dynamicParamSqlNodes = new ArrayList<>();
+  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<CorrelationId, DeferredLookup> mapCorrelToDeferred =
+      new HashMap<>();
+
+  /**
+   * Stack of names of datasets requested by the <code>
+   * TABLE(SAMPLE(&lt;datasetName&gt;, &lt;query&gt;))</code> construct.
+   */
+  private final Deque<String> datasetStack = new ArrayDeque<>();
+
+  /**
+   * 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<>();
+
+  public final RelOptTable.ViewExpander viewExpander;
+
+  /** Whether to expand sub-queries. If false, each sub-query becomes a
+   * {@link org.apache.calcite.rex.RexSubQuery}. */
+  private boolean expand = true;
+
+  //~ 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 // will 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);
+  }
+
+  /* Creates a converter. */
+  public SqlToRelConverter(
+      RelOptTable.ViewExpander viewExpander,
+      SqlValidator validator,
+      Prepare.CatalogReader catalogReader,
+      RelOptCluster cluster,
+      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 = cluster.getRexBuilder();
+    this.typeFactory = rexBuilder.getTypeFactory();
+    this.cluster = Preconditions.checkNotNull(cluster);
+    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)) {
+      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)));
+
+    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());
+    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 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());
+      }
+      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() {
+    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);
+    }
 
-    /**
-     * @return the RelOptCluster in use.
-     */
-    public RelOptCluster getCluster() {
-        return cluster;
+    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);
+
+    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));
     }
 
-    /**
-     * Returns the row-expression builder.
-     */
-    public RexBuilder getRexBuilder() {
-        return rexBuilder;
+    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;
     }
+  }
 
-    /**
-     * 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();
+  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);
     }
 
-    /**
-     * 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);
+    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;
     }
 
-    /**
-     * 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;
+    // 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;
+      }
     }
 
-    /**
-     * @return mapping of non-correlated subqueries that have been converted to
-     * the constants that they evaluate to
-     */
-    public Map<SqlNode, RexNode> getMapConvertedNonCorrSubqs() {
-        return mapConvertedNonCorrSubqs;
+    // 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 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);
 
-    /**
-     * 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);
+    // only allocate filter if the condition is not TRUE
+    if (convertedWhere.isAlwaysTrue()) {
+      return;
     }
 
-    /**
-     * 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;
+    final RelNode filter = RelOptUtil.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;
     }
 
-    /**
-     * 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;
+    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);
     }
+  }
 
-    /**
-     * 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;
+  private void substituteSubquery(Blackboard bb, SubQuery subQuery) {
+    final RexNode expr = subQuery.expr;
+    if (expr != null) {
+      // Already done.
+      return;
     }
 
-    /**
-     * 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;
+    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:
+    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 (!expand && !(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 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;
+      final RelDataType targetRowType =
+          SqlTypeUtil.promoteToRowType(typeFactory,
+              validator.getValidatedNodeType(leftKeyNode), null);
+      converted =
+          convertExists(query, RelOptUtil.SubqueryType.IN, subQuery.logic,
+              outerJoin, targetRowType);
+      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 =
+            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);
+      }
+      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.operand(0);
+      if (!expand) {
+        return;
+      }
+      converted = convertExists(query, RelOptUtil.SubqueryType.EXISTS,
+          subQuery.logic, true, null);
+      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.
+      if (!expand) {
+        return;
+      }
+      call = (SqlBasicCall) subQuery.node;
+      query = call.operand(0);
+      converted = convertExists(query, RelOptUtil.SubqueryType.SCALAR,
+          subQuery.logic, true, null);
+      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, null);
+      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()).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);
     }
+  }
 
-    /**
-     * 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));
-            }
+  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;
         }
+      }
     }
-
-    public RelNode flattenTypes(RelNode rootRel, boolean restructure) {
-        RelStructuredTypeFlattener typeFlattener = new RelStructuredTypeFlattener(rexBuilder, createToRelContext());
-        return typeFlattener.rewrite(rootRel, restructure);
+    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 (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 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;
+    // 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),
+                rexBuilder.ensureType(leftKeys.get(0).getType(),
+                    bb.convertExpression(rightVals), true));
+      } 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,
+                            rexBuilder.ensureType(pair.left.getType(),
+                                bb.convertExpression(pair.right), true));
+                      }
+                    }),
+                false);
+      }
+      comparisons.add(rexComparison);
     }
 
-    /**
-     * 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;
+    RexNode result =
+        RexUtil.composeDisjunction(rexBuilder, comparisons, true);
+    assert result != null;
+
+    if (isNotIn) {
+      result =
+          rexBuilder.makeCall(
+              SqlStdOperatorTable.NOT,
+              result);
     }
 
-    /**
-     * Creates a RelFieldTrimmer.
-     *
-     * @return Field trimmer
-     */
-    protected RelFieldTrimmer newFieldTrimmer() {
-        return new RelFieldTrimmer(validator);
+    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 {@link #IN_SUBQUERY_THRESHOLD}
+   */
+  protected int getInSubqueryThreshold() {
+    /* OVERRIDE POINT */
+    return Integer.MAX_VALUE;
+  }
+
+  /**
+   * 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,
+      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,
+        needsOuterJoin);
+  }
+
+  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
+    // 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);
     }
 
-    /**
-     * 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);
+    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) || !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;
+          }
         }
 
-        RelNode result = convertQueryRecursive(query, top, null);
-        if (top && isStream(query)) {
-            result = new LogicalDelta(cluster, result.getTraitSet(), result);
-        }
-        checkConvertedType(query, result);
+        // 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;
+    }
 
-        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));
-        }
+    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);
 
-        return result;
+      // NOTE jvs 22-Nov-2006:  we preserve type info
+      // in LogicalValues digest, so it's OK to lose it here
+      return (RexLiteral) child;
     }
 
-    private static boolean isStream(SqlNode query) {
-        return query instanceof SqlSelect && ((SqlSelect) query).isKeywordPresent(SqlSelectKeyword.STREAM);
+    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);
     }
 
-    protected boolean checkConvertedRowType(SqlNode query, RelDataType convertedRowType) {
-        RelDataType validatedRowType = validator.getValidatedNodeType(query);
-        validatedRowType = uniquifyFields(validatedRowType);
+    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;
+  }
 
-        return RelOptUtil.equal("validated row type", validatedRowType, "converted row type", convertedRowType, false);
+  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 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) {
+      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);
+      }
     }
 
-    protected RelDataType uniquifyFields(RelDataType rowType) {
-        return validator.getTypeFactory().createStructType(RelOptUtil.getFieldTypeList(rowType), SqlValidatorUtil.uniquify(rowType.getFieldNames()));
+    // 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();
+    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.getOperator() == SqlStdOperatorTable.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 {
+      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) {
+    final SqlCall call;
+    final SqlNode[] operands;
+    switch (from.getKind()) {
+    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 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 = LogicalTableScan.create(cluster, table);
+      }
+      bb.setRoot(tableRel, true);
+      if (usedDataset[0]) {
+        bb.setDataset(datasetName);
+      }
+      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 SqlNode node = call.operand(0);
+      final SqlUnnestOperator operator = (SqlUnnestOperator) call.getOperator();
+      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, 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 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).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);
+      RelNode converted = toRel(relOptTable);
+      bb.setRoot(converted, true);
+      return;
     }
 
-    /**
-     * 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;
+    Type elementType;
+    if 

<TRUNCATED>

Mime
View raw message