You are viewing a plain text version of this content. The canonical link for it is here.
Posted to commits@impala.apache.org by ta...@apache.org on 2018/03/20 20:44:03 UTC
[05/21] impala git commit: IMPALA-5270: Pass resolved exprs into
analytic SortInfo.
IMPALA-5270: Pass resolved exprs into analytic SortInfo.
The bug was that the SortInfo of analytics was given
ordering exprs that were not fully resolved against their
input (e.g. inline views were not resolved).
As a result, the SortInfo logic did not materialize exprs
like rand() coming from inline views.
The fix is to pass fully resolved exprs to the analytic
SortInfo, and then the existing materialization logic
properly handles non-deterministic built-ins and UDFs.
The code around sort generation was rather convoluted
and difficult to understand. I overhauled SortInfo to
unify the different uses of it under a common codepath
After that cleanup, the fix for this issue was trivial.
Testing:
- Locally ran planner tests
- Locally ran analytic EE tests in test_queries.py
- Core/hdfs run passed
Change-Id: Id2b3f4e5e3f1fd441a63160db3c703c432fbb072
Reviewed-on: http://gerrit.cloudera.org:8080/9631
Reviewed-by: Alex Behm <al...@cloudera.com>
Tested-by: Impala Public Jenkins
Reviewed-on: http://gerrit.cloudera.org:8080/9708
Reviewed-by: Vuk Ercegovac <ve...@cloudera.com>
Project: http://git-wip-us.apache.org/repos/asf/impala/repo
Commit: http://git-wip-us.apache.org/repos/asf/impala/commit/c5e1f24e
Tree: http://git-wip-us.apache.org/repos/asf/impala/tree/c5e1f24e
Diff: http://git-wip-us.apache.org/repos/asf/impala/diff/c5e1f24e
Branch: refs/heads/2.x
Commit: c5e1f24ec14e1743c3fc2e332adcaec0e7aba96c
Parents: f6ad4e6
Author: Alex Behm <al...@cloudera.com>
Authored: Tue Mar 13 10:26:55 2018 -0700
Committer: Impala Public Jenkins <im...@gerrit.cloudera.org>
Committed: Sat Mar 17 22:41:31 2018 +0000
----------------------------------------------------------------------
.../org/apache/impala/analysis/QueryStmt.java | 7 +-
.../org/apache/impala/analysis/SelectStmt.java | 18 +-
.../org/apache/impala/analysis/SortInfo.java | 274 +++++++++----------
.../apache/impala/planner/AnalyticPlanner.java | 57 ++--
.../org/apache/impala/planner/ExchangeNode.java | 6 +-
.../java/org/apache/impala/planner/Planner.java | 7 +-
.../org/apache/impala/planner/SortNode.java | 41 +--
.../PlannerTest/sort-expr-materialization.test | 41 +++
8 files changed, 225 insertions(+), 226 deletions(-)
----------------------------------------------------------------------
http://git-wip-us.apache.org/repos/asf/impala/blob/c5e1f24e/fe/src/main/java/org/apache/impala/analysis/QueryStmt.java
----------------------------------------------------------------------
diff --git a/fe/src/main/java/org/apache/impala/analysis/QueryStmt.java b/fe/src/main/java/org/apache/impala/analysis/QueryStmt.java
index 3f2eec5..05e47d5 100644
--- a/fe/src/main/java/org/apache/impala/analysis/QueryStmt.java
+++ b/fe/src/main/java/org/apache/impala/analysis/QueryStmt.java
@@ -265,17 +265,16 @@ public abstract class QueryStmt extends StatementBase {
*/
protected void createSortTupleInfo(Analyzer analyzer) throws AnalysisException {
Preconditions.checkState(evaluateOrderBy_);
-
- for (Expr orderingExpr: sortInfo_.getOrderingExprs()) {
+ for (Expr orderingExpr: sortInfo_.getSortExprs()) {
if (orderingExpr.getType().isComplexType()) {
throw new AnalysisException(String.format("ORDER BY expression '%s' with " +
"complex type '%s' is not supported.", orderingExpr.toSql(),
orderingExpr.getType().toSql()));
}
}
+ sortInfo_.createSortTupleInfo(resultExprs_, analyzer);
- ExprSubstitutionMap smap = sortInfo_.createSortTupleInfo(resultExprs_, analyzer);
-
+ ExprSubstitutionMap smap = sortInfo_.getOutputSmap();
for (int i = 0; i < smap.size(); ++i) {
if (!(smap.getLhs().get(i) instanceof SlotRef)
|| !(smap.getRhs().get(i) instanceof SlotRef)) {
http://git-wip-us.apache.org/repos/asf/impala/blob/c5e1f24e/fe/src/main/java/org/apache/impala/analysis/SelectStmt.java
----------------------------------------------------------------------
diff --git a/fe/src/main/java/org/apache/impala/analysis/SelectStmt.java b/fe/src/main/java/org/apache/impala/analysis/SelectStmt.java
index ab18f85..71e7e8e 100644
--- a/fe/src/main/java/org/apache/impala/analysis/SelectStmt.java
+++ b/fe/src/main/java/org/apache/impala/analysis/SelectStmt.java
@@ -270,7 +270,7 @@ public class SelectStmt extends QueryStmt {
if (sortInfo_ != null && hasLimit()) {
// When there is a LIMIT clause in conjunction with an ORDER BY, the ordering exprs
// must be added in the column lineage graph.
- graph.addDependencyPredicates(sortInfo_.getOrderingExprs());
+ graph.addDependencyPredicates(sortInfo_.getSortExprs());
}
if (aggInfo_ != null) {
@@ -563,7 +563,7 @@ public class SelectStmt extends QueryStmt {
&& (havingPred_ == null
|| !havingPred_.contains(Expr.isAggregatePredicate()))
&& (sortInfo_ == null
- || !TreeNode.contains(sortInfo_.getOrderingExprs(),
+ || !TreeNode.contains(sortInfo_.getSortExprs(),
Expr.isAggregatePredicate()))) {
// We're not computing aggregates but we still need to register the HAVING
// clause which could, e.g., contain a constant expression evaluating to false.
@@ -644,7 +644,7 @@ public class SelectStmt extends QueryStmt {
}
if (sortInfo_ != null) {
// TODO: Avoid evaluating aggs in ignored order-bys
- TreeNode.collect(sortInfo_.getOrderingExprs(), Expr.isAggregatePredicate(),
+ TreeNode.collect(sortInfo_.getSortExprs(), Expr.isAggregatePredicate(),
aggExprs);
}
@@ -723,10 +723,10 @@ public class SelectStmt extends QueryStmt {
}
}
if (sortInfo_ != null) {
- sortInfo_.substituteOrderingExprs(combinedSmap, analyzer);
+ sortInfo_.substituteSortExprs(combinedSmap, analyzer);
if (LOG.isTraceEnabled()) {
LOG.trace("post-agg orderingExprs: " +
- Expr.debugString(sortInfo_.getOrderingExprs()));
+ Expr.debugString(sortInfo_.getSortExprs()));
}
}
@@ -742,7 +742,7 @@ public class SelectStmt extends QueryStmt {
}
if (orderByElements_ != null) {
for (int i = 0; i < orderByElements_.size(); ++i) {
- if (!sortInfo_.getOrderingExprs().get(i).isBound(
+ if (!sortInfo_.getSortExprs().get(i).isBound(
finalAggInfo.getOutputTupleId())) {
throw new AnalysisException(
"ORDER BY expression not produced by aggregation output "
@@ -840,7 +840,7 @@ public class SelectStmt extends QueryStmt {
ArrayList<Expr> analyticExprs = Lists.newArrayList();
TreeNode.collect(resultExprs_, AnalyticExpr.class, analyticExprs);
if (sortInfo_ != null) {
- TreeNode.collect(sortInfo_.getOrderingExprs(), AnalyticExpr.class,
+ TreeNode.collect(sortInfo_.getSortExprs(), AnalyticExpr.class,
analyticExprs);
}
if (analyticExprs.isEmpty()) return;
@@ -880,10 +880,10 @@ public class SelectStmt extends QueryStmt {
LOG.trace("post-analytic selectListExprs: " + Expr.debugString(resultExprs_));
}
if (sortInfo_ != null) {
- sortInfo_.substituteOrderingExprs(smap, analyzer);
+ sortInfo_.substituteSortExprs(smap, analyzer);
if (LOG.isTraceEnabled()) {
LOG.trace("post-analytic orderingExprs: " +
- Expr.debugString(sortInfo_.getOrderingExprs()));
+ Expr.debugString(sortInfo_.getSortExprs()));
}
}
}
http://git-wip-us.apache.org/repos/asf/impala/blob/c5e1f24e/fe/src/main/java/org/apache/impala/analysis/SortInfo.java
----------------------------------------------------------------------
diff --git a/fe/src/main/java/org/apache/impala/analysis/SortInfo.java b/fe/src/main/java/org/apache/impala/analysis/SortInfo.java
index 745de6d..fba7286 100644
--- a/fe/src/main/java/org/apache/impala/analysis/SortInfo.java
+++ b/fe/src/main/java/org/apache/impala/analysis/SortInfo.java
@@ -16,13 +16,12 @@
// under the License.
package org.apache.impala.analysis;
-import org.apache.impala.common.TreeNode;
-
-import java.util.ArrayList;
+import java.util.Collection;
import java.util.List;
-import java.util.ListIterator;
import java.util.Set;
+import org.apache.impala.common.TreeNode;
+
import com.google.common.base.Preconditions;
import com.google.common.base.Predicates;
import com.google.common.collect.Lists;
@@ -36,7 +35,7 @@ import com.google.common.collect.Sets;
* particular input row (materialize all row slots)
*/
public class SortInfo {
- // All ordering exprs with cost greater than this will be materialized. Since we don't
+ // All sort exprs with cost greater than this will be materialized. Since we don't
// currently have any information about actual function costs, this value is intended to
// ensure that all expensive functions will be materialized while still leaving simple
// operations unmaterialized, for example 'SlotRef + SlotRef' should have a cost below
@@ -45,74 +44,56 @@ public class SortInfo {
private static final float SORT_MATERIALIZATION_COST_THRESHOLD =
Expr.FUNCTION_CALL_COST;
- private List<Expr> orderingExprs_;
+ private List<Expr> sortExprs_;
private final List<Boolean> isAscOrder_;
// True if "NULLS FIRST", false if "NULLS LAST", null if not specified.
private final List<Boolean> nullsFirstParams_;
- // Subset of ordering exprs that are materialized. Populated in
- // createMaterializedOrderExprs(), used for EXPLAIN output.
- private List<Expr> materializedOrderingExprs_;
- // The single tuple that is materialized, sorted, and output by a sort operator
- // (i.e. SortNode or TopNNode)
+ // Descriptor of tuples materialized, sorted, and output by a SortNode/TopNNode.
private TupleDescriptor sortTupleDesc_;
- // Input expressions materialized into sortTupleDesc_. One expr per slot in
- // sortTupleDesc_.
- private List<Expr> sortTupleSlotExprs_;
+ // List of exprs evaluated against the sort input and materialized into the sort tuple.
+ // One expr per slot in 'sortTupleDesc_'.
+ private final List<Expr> materializedExprs_;
+ // Maps from exprs materialized into the sort tuple to their corresponding SlotRefs.
+ private final ExprSubstitutionMap outputSmap_;
- public SortInfo(List<Expr> orderingExprs, List<Boolean> isAscOrder,
+ public SortInfo(List<Expr> sortExprs, List<Boolean> isAscOrder,
List<Boolean> nullsFirstParams) {
- Preconditions.checkArgument(orderingExprs.size() == isAscOrder.size());
- Preconditions.checkArgument(orderingExprs.size() == nullsFirstParams.size());
- orderingExprs_ = orderingExprs;
+ Preconditions.checkArgument(sortExprs.size() == isAscOrder.size());
+ Preconditions.checkArgument(sortExprs.size() == nullsFirstParams.size());
+ sortExprs_ = sortExprs;
isAscOrder_ = isAscOrder;
nullsFirstParams_ = nullsFirstParams;
- materializedOrderingExprs_ = Lists.newArrayList();
+ materializedExprs_ = Lists.newArrayList();
+ outputSmap_ = new ExprSubstitutionMap();
}
/**
* C'tor for cloning.
*/
private SortInfo(SortInfo other) {
- orderingExprs_ = Expr.cloneList(other.orderingExprs_);
+ sortExprs_ = Expr.cloneList(other.sortExprs_);
isAscOrder_ = Lists.newArrayList(other.isAscOrder_);
nullsFirstParams_ = Lists.newArrayList(other.nullsFirstParams_);
- materializedOrderingExprs_ = Expr.cloneList(other.materializedOrderingExprs_);
+ materializedExprs_ = Expr.cloneList(other.materializedExprs_);
sortTupleDesc_ = other.sortTupleDesc_;
- if (other.sortTupleSlotExprs_ != null) {
- sortTupleSlotExprs_ = Expr.cloneList(other.sortTupleSlotExprs_);
- }
+ outputSmap_ = other.outputSmap_.clone();
}
- /**
- * Sets sortTupleDesc_, which is the internal row representation to be materialized and
- * sorted. The source exprs of the slots in sortTupleDesc_ are changed to those in
- * tupleSlotExprs.
- */
- public void setMaterializedTupleInfo(
- TupleDescriptor tupleDesc, List<Expr> tupleSlotExprs) {
- Preconditions.checkState(tupleDesc.getSlots().size() == tupleSlotExprs.size());
- sortTupleDesc_ = tupleDesc;
- sortTupleSlotExprs_ = tupleSlotExprs;
- for (int i = 0; i < sortTupleDesc_.getSlots().size(); ++i) {
- SlotDescriptor slotDesc = sortTupleDesc_.getSlots().get(i);
- slotDesc.setSourceExpr(sortTupleSlotExprs_.get(i));
- }
- }
- public List<Expr> getOrderingExprs() { return orderingExprs_; }
+ public List<Expr> getSortExprs() { return sortExprs_; }
public List<Boolean> getIsAscOrder() { return isAscOrder_; }
public List<Boolean> getNullsFirstParams() { return nullsFirstParams_; }
- public List<Expr> getMaterializedOrderingExprs() { return materializedOrderingExprs_; }
- public List<Expr> getSortTupleSlotExprs() { return sortTupleSlotExprs_; }
+ public List<Expr> getMaterializedExprs() { return materializedExprs_; }
public TupleDescriptor getSortTupleDescriptor() { return sortTupleDesc_; }
+ public ExprSubstitutionMap getOutputSmap() { return outputSmap_; }
/**
* Gets the list of booleans indicating whether nulls come first or last, independent
* of asc/desc.
*/
public List<Boolean> getNullsFirst() {
- Preconditions.checkState(orderingExprs_.size() == nullsFirstParams_.size());
+ Preconditions.checkState(sortExprs_.size() == nullsFirstParams_.size());
List<Boolean> nullsFirst = Lists.newArrayList();
- for (int i = 0; i < orderingExprs_.size(); ++i) {
+ for (int i = 0; i < sortExprs_.size(); ++i) {
nullsFirst.add(OrderByElement.nullsFirst(nullsFirstParams_.get(i),
isAscOrder_.get(i)));
}
@@ -120,20 +101,19 @@ public class SortInfo {
}
/**
- * Materializes the slots in sortTupleDesc_ referenced in the ordering exprs.
- * Materializes the slots referenced by the corresponding sortTupleSlotExpr after
- * applying the 'smap'.
+ * Materializes the slots in 'sortTupleDesc_' referenced in the sort exprs.
+ * Materializes the slots referenced by the corresponding materialized expr after
+ * applying the 'smap'. Valid to call after createSortTupleInfo().
*/
public void materializeRequiredSlots(Analyzer analyzer, ExprSubstitutionMap smap) {
Preconditions.checkNotNull(sortTupleDesc_);
- Preconditions.checkNotNull(sortTupleSlotExprs_);
Preconditions.checkState(sortTupleDesc_.isMaterialized());
- analyzer.materializeSlots(orderingExprs_);
+ analyzer.materializeSlots(sortExprs_);
List<SlotDescriptor> sortTupleSlotDescs = sortTupleDesc_.getSlots();
List<Expr> materializedExprs = Lists.newArrayList();
for (int i = 0; i < sortTupleSlotDescs.size(); ++i) {
if (sortTupleSlotDescs.get(i).isMaterialized()) {
- materializedExprs.add(sortTupleSlotExprs_.get(i));
+ materializedExprs.add(materializedExprs_.get(i));
}
}
List<Expr> substMaterializedExprs =
@@ -142,20 +122,22 @@ public class SortInfo {
}
/**
- * Replaces orderingExprs_ according to smap. This needs to be called to make sure that
- * the ordering exprs refer to the new tuple materialized by this sort instead of the
+ * Replaces 'sortExprs_' according to smap. This needs to be called to make sure that
+ * the sort exprs refer to the new tuple materialized by this sort instead of the
* original input.
*/
- public void substituteOrderingExprs(ExprSubstitutionMap smap, Analyzer analyzer) {
- orderingExprs_ = Expr.substituteList(orderingExprs_, smap, analyzer, false);
+ public void substituteSortExprs(ExprSubstitutionMap smap, Analyzer analyzer) {
+ sortExprs_ = Expr.substituteList(sortExprs_, smap, analyzer, false);
}
/**
- * Asserts that all ordering exprs are bound by the sort tuple.
+ * Validates internal state. Asserts that all sort exprs are bound by the sort tuple.
*/
public void checkConsistency() {
- for (Expr orderingExpr: orderingExprs_) {
- Preconditions.checkState(orderingExpr.isBound(sortTupleDesc_.getId()));
+ Preconditions.checkState(
+ materializedExprs_.size() == sortTupleDesc_.getSlots().size());
+ for (Expr sortExpr: sortExprs_) {
+ Preconditions.checkState(sortExpr.isBound(sortTupleDesc_.getId()));
}
}
@@ -163,119 +145,111 @@ public class SortInfo {
public SortInfo clone() { return new SortInfo(this); }
/**
+ * Matches SlotRef expressions that do not reference the sort tuple.
+ */
+ private class IsInputSlotRefPred implements com.google.common.base.Predicate<Expr> {
+ private final TupleId sortTid_;
+ public IsInputSlotRefPred(TupleId sortTid) {
+ sortTid_ = sortTid;
+ }
+
+ @Override
+ public boolean apply(Expr e) {
+ return e instanceof SlotRef && !e.isBound(sortTid_);
+ }
+ }
+
+ /**
* Create a tuple descriptor for the single tuple that is materialized, sorted, and
* output by the sort node. Materializes slots required by 'resultExprs' as well as
* non-deterministic and expensive order by exprs. The materialized exprs are
* substituted with slot refs into the new tuple. This simplifies the sorting logic for
- * total and top-n sorts. The substitution map is returned.
+ * total and top-n sorts.
*/
- public ExprSubstitutionMap createSortTupleInfo(
- List<Expr> resultExprs, Analyzer analyzer) {
+ public void createSortTupleInfo(List<Expr> resultExprs, Analyzer analyzer) {
+ Preconditions.checkState(sortTupleDesc_ == null);
+ Preconditions.checkState(outputSmap_.size() == 0);
+
// The descriptor for the tuples on which the sort operates.
- TupleDescriptor sortTupleDesc = analyzer.getDescTbl().createTupleDescriptor("sort");
- sortTupleDesc.setIsMaterialized(true);
- List<Expr> sortTupleExprs = Lists.newArrayList();
+ sortTupleDesc_ = analyzer.getDescTbl().createTupleDescriptor("sort");
+ sortTupleDesc_.setIsMaterialized(true);
- // substOrderBy is a mapping from exprs evaluated on the sort input that get
- // materialized into the sort tuple to their corresponding SlotRefs in the sort tuple.
// The following exprs are materialized:
- // 1. Ordering exprs that we chose to materialize
- // 2. SlotRefs against the sort input contained in the result and ordering exprs after
- // substituting the materialized ordering exprs.
-
- // Case 1:
- ExprSubstitutionMap substOrderBy =
- createMaterializedOrderExprs(sortTupleDesc, analyzer);
- sortTupleExprs.addAll(substOrderBy.getLhs());
-
- // Case 2: SlotRefs in the result and ordering exprs after substituting the
- // materialized ordering exprs. Using a LinkedHashSet prevents the slots getting
- // reordered unnecessarily.
- Set<SlotRef> sourceSlots = Sets.newLinkedHashSet();
- List<Expr> substResultExprs =
- Expr.substituteList(resultExprs, substOrderBy, analyzer, false);
- TreeNode.collect(substResultExprs, Predicates.instanceOf(SlotRef.class), sourceSlots);
- TreeNode.collect(Expr.substituteList(orderingExprs_, substOrderBy, analyzer, false),
- Predicates.instanceOf(SlotRef.class), sourceSlots);
- for (SlotRef origSlotRef: sourceSlots) {
- // Don't rematerialize slots that are already in the sort tuple.
- if (origSlotRef.getDesc().getParent().getId() != sortTupleDesc.getId()) {
- SlotDescriptor origSlotDesc = origSlotRef.getDesc();
- SlotDescriptor materializedDesc =
- analyzer.copySlotDescriptor(origSlotDesc, sortTupleDesc);
- SlotRef cloneRef = new SlotRef(materializedDesc);
- substOrderBy.put(origSlotRef, cloneRef);
- sortTupleExprs.add(origSlotRef);
- }
- }
-
- materializeTupleIsNullPredicates(
- sortTupleDesc, substResultExprs, sortTupleExprs, substOrderBy, analyzer);
+ // 1. Sort exprs that we chose to materialize
+ // 2. SlotRefs against the sort input contained in the result and sort exprs
+ // after substituting the materialized sort exprs.
+ // 3. TupleIsNullPredicates from 'resultExprs' which are not legal to evaluate after
+ // the sort because the tuples referenced by it are gone after the sort.
+
+ // Case 1: Materialize chosen sort exprs.
+ addMaterializedExprs(getMaterializedSortExprs(), analyzer);
+
+ // Case 2: Materialize required input slots. Using a LinkedHashSet prevents the
+ // slots getting reordered unnecessarily.
+ Set<SlotRef> inputSlotRefs = Sets.newLinkedHashSet();
+ IsInputSlotRefPred pred = new IsInputSlotRefPred(sortTupleDesc_.getId());
+ TreeNode.collect(Expr.substituteList(resultExprs, outputSmap_, analyzer, false),
+ pred, inputSlotRefs);
+ TreeNode.collect(Expr.substituteList(sortExprs_, outputSmap_, analyzer, false),
+ pred, inputSlotRefs);
+ addMaterializedExprs(inputSlotRefs, analyzer);
+
+ // Case 3: Materialize TupleIsNullPredicates.
+ List<Expr> tupleIsNullPreds = Lists.newArrayList();
+ TreeNode.collect(resultExprs, Predicates.instanceOf(TupleIsNullPredicate.class),
+ tupleIsNullPreds);
+ Expr.removeDuplicates(tupleIsNullPreds);
+ addMaterializedExprs(tupleIsNullPreds, analyzer);
- // The ordering exprs are evaluated against the sort tuple, so they must reflect the
+ // The sort exprs are evaluated against the sort tuple, so they must reflect the
// materialization decision above.
- substituteOrderingExprs(substOrderBy, analyzer);
-
- // Update the tuple descriptor used to materialize the input of the sort.
- setMaterializedTupleInfo(sortTupleDesc, sortTupleExprs);
-
- return substOrderBy;
+ substituteSortExprs(outputSmap_, analyzer);
+ checkConsistency();
}
/**
- * Materialize ordering exprs by creating slots for them in 'sortTupleDesc' if they:
- * - contain a non-deterministic expr
- * - contain a UDF (since we don't know if they're deterministic)
- * - are more expensive than a cost threshold
- * - don't have a cost set
- *
- * Populates 'materializedOrderingExprs_' and returns a mapping from the original
- * ordering exprs to the new SlotRefs. It is expected that this smap will be passed into
- * substituteOrderingExprs() by the caller.
+ * Materializes each of the given exprs into 'sortTupleDesc' as follows:
+ * - Adds a new slot in 'sortTupleDesc_'
+ * - Adds an entry in 'outputSmap_' mapping from the expr to a SlotRef on the new slot
+ * - Adds an entry in 'materializedExprs_'
+ * Valid to call after createSortTupleInfo().
*/
- public ExprSubstitutionMap createMaterializedOrderExprs(
- TupleDescriptor sortTupleDesc, Analyzer analyzer) {
- ExprSubstitutionMap substOrderBy = new ExprSubstitutionMap();
- for (Expr origOrderingExpr : orderingExprs_) {
- if (!origOrderingExpr.hasCost()
- || origOrderingExpr.getCost() > SORT_MATERIALIZATION_COST_THRESHOLD
- || origOrderingExpr.contains(Expr.IS_NONDETERMINISTIC_BUILTIN_FN_PREDICATE)
- || origOrderingExpr.contains(Expr.IS_UDF_PREDICATE)) {
- SlotDescriptor materializedDesc = analyzer.addSlotDescriptor(sortTupleDesc);
- materializedDesc.initFromExpr(origOrderingExpr);
- materializedDesc.setIsMaterialized(true);
- SlotRef materializedRef = new SlotRef(materializedDesc);
- substOrderBy.put(origOrderingExpr, materializedRef);
- materializedOrderingExprs_.add(origOrderingExpr);
+ public <T extends Expr> void addMaterializedExprs(Collection<T> exprs,
+ Analyzer analyzer) {
+ Preconditions.checkNotNull(sortTupleDesc_);
+ for (Expr srcExpr : exprs) {
+ SlotDescriptor dstSlotDesc;
+ if (srcExpr instanceof SlotRef) {
+ SlotDescriptor srcSlotDesc = ((SlotRef) srcExpr).getDesc();
+ dstSlotDesc = analyzer.copySlotDescriptor(srcSlotDesc, sortTupleDesc_);
+ } else {
+ dstSlotDesc = analyzer.addSlotDescriptor(sortTupleDesc_);
+ dstSlotDesc.initFromExpr(srcExpr);
}
+ dstSlotDesc.setSourceExpr(srcExpr);
+ outputSmap_.put(srcExpr.clone(), new SlotRef(dstSlotDesc));
+ materializedExprs_.add(srcExpr);
}
- return substOrderBy;
}
/**
- * Collects the unique TupleIsNullPredicates from 'exprs' and for each one:
- * - Materializes it into a new slot in 'sortTupleDesc'
- * - Adds it to 'sortSlotExprs'
- * - Adds an entry in 'substOrderBy' mapping it to a SlotRef into the new slot
+ * Returns the subset of 'sortExprs_' that should be materialized. A sort expr is
+ * is materialized if it:
+ * - contains a non-deterministic expr
+ * - contains a UDF (since we don't know if they're deterministic)
+ * - is more expensive than a cost threshold
+ * - does not have a cost set
*/
- public static void materializeTupleIsNullPredicates(TupleDescriptor sortTupleDesc,
- List<Expr> exprs, List<Expr> sortSlotExprs, ExprSubstitutionMap substOrderBy,
- Analyzer analyzer) {
- List<Expr> tupleIsNullPreds = Lists.newArrayList();
- TreeNode.collect(
- exprs, Predicates.instanceOf(TupleIsNullPredicate.class), tupleIsNullPreds);
- Expr.removeDuplicates(tupleIsNullPreds);
-
- // Materialize relevant unique TupleIsNullPredicates.
- for (Expr tupleIsNullPred: tupleIsNullPreds) {
- SlotDescriptor sortSlotDesc = analyzer.addSlotDescriptor(sortTupleDesc);
- sortSlotDesc.setType(tupleIsNullPred.getType());
- sortSlotDesc.setIsMaterialized(true);
- sortSlotDesc.setSourceExpr(tupleIsNullPred);
- sortSlotDesc.setLabel(tupleIsNullPred.toSql());
- SlotRef cloneRef = new SlotRef(sortSlotDesc);
- substOrderBy.put(tupleIsNullPred, cloneRef);
- sortSlotExprs.add(tupleIsNullPred.clone());
+ private List<Expr> getMaterializedSortExprs() {
+ List<Expr> result = Lists.newArrayList();
+ for (Expr sortExpr : sortExprs_) {
+ if (!sortExpr.hasCost()
+ || sortExpr.getCost() > SORT_MATERIALIZATION_COST_THRESHOLD
+ || sortExpr.contains(Expr.IS_NONDETERMINISTIC_BUILTIN_FN_PREDICATE)
+ || sortExpr.contains(Expr.IS_UDF_PREDICATE)) {
+ result.add(sortExpr);
+ }
}
+ return result;
}
}
http://git-wip-us.apache.org/repos/asf/impala/blob/c5e1f24e/fe/src/main/java/org/apache/impala/planner/AnalyticPlanner.java
----------------------------------------------------------------------
diff --git a/fe/src/main/java/org/apache/impala/planner/AnalyticPlanner.java b/fe/src/main/java/org/apache/impala/planner/AnalyticPlanner.java
index f504fda..90d98fd 100644
--- a/fe/src/main/java/org/apache/impala/planner/AnalyticPlanner.java
+++ b/fe/src/main/java/org/apache/impala/planner/AnalyticPlanner.java
@@ -21,9 +21,6 @@ import java.util.Collections;
import java.util.Comparator;
import java.util.List;
-import org.slf4j.Logger;
-import org.slf4j.LoggerFactory;
-
import org.apache.impala.analysis.AggregateInfoBase;
import org.apache.impala.analysis.AnalyticExpr;
import org.apache.impala.analysis.AnalyticInfo;
@@ -44,7 +41,9 @@ import org.apache.impala.analysis.TupleDescriptor;
import org.apache.impala.analysis.TupleId;
import org.apache.impala.analysis.TupleIsNullPredicate;
import org.apache.impala.common.ImpalaException;
-import org.apache.impala.thrift.TPartitionType;
+import org.slf4j.Logger;
+import org.slf4j.LoggerFactory;
+
import com.google.common.base.Preconditions;
import com.google.common.collect.Lists;
@@ -256,25 +255,23 @@ public class AnalyticPlanner {
private SortInfo createSortInfo(
PlanNode input, List<Expr> sortExprs, List<Boolean> isAsc,
List<Boolean> nullsFirst) {
- // create tuple for sort output = the entire materialized input in a single tuple
- TupleDescriptor sortTupleDesc =
- analyzer_.getDescTbl().createTupleDescriptor("sort-tuple");
- ExprSubstitutionMap sortSmap = new ExprSubstitutionMap();
- List<Expr> sortSlotExprs = Lists.newArrayList();
- sortTupleDesc.setIsMaterialized(true);
+ List<Expr> inputSlotRefs = Lists.newArrayList();
for (TupleId tid: input.getTupleIds()) {
TupleDescriptor tupleDesc = analyzer_.getTupleDesc(tid);
for (SlotDescriptor inputSlotDesc: tupleDesc.getSlots()) {
if (!inputSlotDesc.isMaterialized()) continue;
- SlotDescriptor sortSlotDesc =
- analyzer_.copySlotDescriptor(inputSlotDesc, sortTupleDesc);
- // all output slots need to be materialized
- sortSlotDesc.setIsMaterialized(true);
- sortSmap.put(new SlotRef(inputSlotDesc), new SlotRef(sortSlotDesc));
- sortSlotExprs.add(new SlotRef(inputSlotDesc));
+ inputSlotRefs.add(new SlotRef(inputSlotDesc));
}
}
+ // The decision to materialize ordering exprs should be based on exprs that are
+ // fully resolved against our input (IMPALA-5270).
+ ExprSubstitutionMap inputSmap = input.getOutputSmap();
+ List<Expr> resolvedSortExprs =
+ Expr.substituteList(sortExprs, inputSmap, analyzer_, true);
+ SortInfo sortInfo = new SortInfo(resolvedSortExprs, isAsc, nullsFirst);
+ sortInfo.createSortTupleInfo(inputSlotRefs, analyzer_);
+
// Lhs exprs to be substituted in ancestor plan nodes could have a rhs that contains
// TupleIsNullPredicates. TupleIsNullPredicates require specific tuple ids for
// evaluation. Since this sort materializes a new tuple, it's impossible to evaluate
@@ -282,31 +279,17 @@ public class AnalyticPlanner {
// To preserve the information whether an input tuple was null or not this sort node,
// we materialize those rhs TupleIsNullPredicates, which are then substituted
// by a SlotRef into the sort's tuple in ancestor nodes (IMPALA-1519).
- ExprSubstitutionMap inputSmap = input.getOutputSmap();
if (inputSmap != null) {
- List<Expr> relevantRhsExprs = Lists.newArrayList();
- for (int i = 0; i < inputSmap.size(); ++i) {
- Expr rhsExpr = inputSmap.getRhs().get(i);
+ List<Expr> tupleIsNullPreds = Lists.newArrayList();
+ for (Expr rhsExpr: inputSmap.getRhs()) {
// Ignore substitutions that are irrelevant at this plan node and its ancestors.
- if (rhsExpr.isBoundByTupleIds(input.getTupleIds())) {
- relevantRhsExprs.add(rhsExpr);
- }
+ if (!rhsExpr.isBoundByTupleIds(input.getTupleIds())) continue;
+ rhsExpr.collect(TupleIsNullPredicate.class, tupleIsNullPreds);
}
-
- SortInfo.materializeTupleIsNullPredicates(sortTupleDesc, relevantRhsExprs,
- sortSlotExprs, sortSmap, analyzer_);
- }
-
- SortInfo sortInfo = new SortInfo(sortExprs, isAsc, nullsFirst);
- ExprSubstitutionMap smap =
- sortInfo.createMaterializedOrderExprs(sortTupleDesc, analyzer_);
- sortSlotExprs.addAll(smap.getLhs());
- sortSmap = ExprSubstitutionMap.combine(sortSmap, smap);
- sortInfo.substituteOrderingExprs(sortSmap, analyzer_);
- if (LOG.isTraceEnabled()) {
- LOG.trace("sortinfo exprs: " + Expr.debugString(sortInfo.getOrderingExprs()));
+ Expr.removeDuplicates(tupleIsNullPreds);
+ sortInfo.addMaterializedExprs(tupleIsNullPreds, analyzer_);
}
- sortInfo.setMaterializedTupleInfo(sortTupleDesc, sortSlotExprs);
+ sortInfo.getSortTupleDescriptor().materializeSlots();
return sortInfo;
}
http://git-wip-us.apache.org/repos/asf/impala/blob/c5e1f24e/fe/src/main/java/org/apache/impala/planner/ExchangeNode.java
----------------------------------------------------------------------
diff --git a/fe/src/main/java/org/apache/impala/planner/ExchangeNode.java b/fe/src/main/java/org/apache/impala/planner/ExchangeNode.java
index 87d2fd2..05184f2 100644
--- a/fe/src/main/java/org/apache/impala/planner/ExchangeNode.java
+++ b/fe/src/main/java/org/apache/impala/planner/ExchangeNode.java
@@ -138,9 +138,9 @@ public class ExchangeNode extends PlanNode {
if (mergeInfo_ != null && detailLevel.ordinal() > TExplainLevel.MINIMAL.ordinal()) {
output.append(detailPrefix + "order by: ");
- for (int i = 0; i < mergeInfo_.getOrderingExprs().size(); ++i) {
+ for (int i = 0; i < mergeInfo_.getSortExprs().size(); ++i) {
if (i > 0) output.append(", ");
- output.append(mergeInfo_.getOrderingExprs().get(i).toSql() + " ");
+ output.append(mergeInfo_.getSortExprs().get(i).toSql() + " ");
output.append(mergeInfo_.getIsAscOrder().get(i) ? "ASC" : "DESC");
Boolean nullsFirstParam = mergeInfo_.getNullsFirstParams().get(i);
@@ -204,7 +204,7 @@ public class ExchangeNode extends PlanNode {
if (mergeInfo_ != null) {
TSortInfo sortInfo = new TSortInfo(
- Expr.treesToThrift(mergeInfo_.getOrderingExprs()), mergeInfo_.getIsAscOrder(),
+ Expr.treesToThrift(mergeInfo_.getSortExprs()), mergeInfo_.getIsAscOrder(),
mergeInfo_.getNullsFirst());
msg.exchange_node.setSort_info(sortInfo);
msg.exchange_node.setOffset(offset_);
http://git-wip-us.apache.org/repos/asf/impala/blob/c5e1f24e/fe/src/main/java/org/apache/impala/planner/Planner.java
----------------------------------------------------------------------
diff --git a/fe/src/main/java/org/apache/impala/planner/Planner.java b/fe/src/main/java/org/apache/impala/planner/Planner.java
index c320eb4..2b8b1c3 100644
--- a/fe/src/main/java/org/apache/impala/planner/Planner.java
+++ b/fe/src/main/java/org/apache/impala/planner/Planner.java
@@ -641,12 +641,9 @@ public class Planner {
List<Boolean> isAscOrder = Collections.nCopies(orderingExprs.size(), true);
List<Boolean> nullsFirstParams = Collections.nCopies(orderingExprs.size(), false);
SortInfo sortInfo = new SortInfo(orderingExprs, isAscOrder, nullsFirstParams);
-
- ExprSubstitutionMap smap = sortInfo.createSortTupleInfo(
- insertStmt.getResultExprs(), analyzer);
+ sortInfo.createSortTupleInfo(insertStmt.getResultExprs(), analyzer);
sortInfo.getSortTupleDescriptor().materializeSlots();
-
- insertStmt.substituteResultExprs(smap, analyzer);
+ insertStmt.substituteResultExprs(sortInfo.getOutputSmap(), analyzer);
PlanNode node = null;
if (partialSort) {
http://git-wip-us.apache.org/repos/asf/impala/blob/c5e1f24e/fe/src/main/java/org/apache/impala/planner/SortNode.java
----------------------------------------------------------------------
diff --git a/fe/src/main/java/org/apache/impala/planner/SortNode.java b/fe/src/main/java/org/apache/impala/planner/SortNode.java
index 3ca50e0..45ee763 100644
--- a/fe/src/main/java/org/apache/impala/planner/SortNode.java
+++ b/fe/src/main/java/org/apache/impala/planner/SortNode.java
@@ -19,9 +19,6 @@ package org.apache.impala.planner;
import java.util.List;
-import org.slf4j.Logger;
-import org.slf4j.LoggerFactory;
-
import org.apache.impala.analysis.Analyzer;
import org.apache.impala.analysis.Expr;
import org.apache.impala.analysis.ExprSubstitutionMap;
@@ -36,6 +33,9 @@ import org.apache.impala.thrift.TQueryOptions;
import org.apache.impala.thrift.TSortInfo;
import org.apache.impala.thrift.TSortNode;
import org.apache.impala.thrift.TSortType;
+import org.slf4j.Logger;
+import org.slf4j.LoggerFactory;
+
import com.google.common.base.Joiner;
import com.google.common.base.Objects;
import com.google.common.base.Preconditions;
@@ -72,7 +72,7 @@ public class SortNode extends PlanNode {
protected long offset_;
// The type of sort. Determines the exec node used in the BE.
- private TSortType type_;
+ private final TSortType type_;
/**
* Creates a new SortNode that implements a partial sort.
@@ -133,8 +133,7 @@ public class SortNode extends PlanNode {
// populate resolvedTupleExprs_ and outputSmap_
List<SlotDescriptor> sortTupleSlots = info_.getSortTupleDescriptor().getSlots();
- List<Expr> slotExprs = info_.getSortTupleSlotExprs();
- Preconditions.checkState(sortTupleSlots.size() == slotExprs.size());
+ List<Expr> slotExprs = info_.getMaterializedExprs();
resolvedTupleExprs_ = Lists.newArrayList();
outputSmap_ = new ExprSubstitutionMap();
for (int i = 0; i < slotExprs.size(); ++i) {
@@ -152,7 +151,7 @@ public class SortNode extends PlanNode {
// Parent nodes have have to do the same so set the composition as the outputSmap_.
outputSmap_ = ExprSubstitutionMap.compose(childSmap, outputSmap_, analyzer);
- info_.substituteOrderingExprs(outputSmap_, analyzer);
+ info_.substituteSortExprs(outputSmap_, analyzer);
info_.checkConsistency();
if (LOG.isTraceEnabled()) {
@@ -179,7 +178,7 @@ public class SortNode extends PlanNode {
}
return Objects.toStringHelper(this)
.add("type_", type_)
- .add("ordering_exprs", Expr.debugString(info_.getOrderingExprs()))
+ .add("ordering_exprs", Expr.debugString(info_.getSortExprs()))
.add("is_asc", "[" + Joiner.on(" ").join(strings) + "]")
.add("nulls_first", "[" + Joiner.on(" ").join(info_.getNullsFirst()) + "]")
.add("offset_", offset_)
@@ -190,7 +189,7 @@ public class SortNode extends PlanNode {
@Override
protected void toThrift(TPlanNode msg) {
msg.node_type = TPlanNodeType.SORT_NODE;
- TSortInfo sort_info = new TSortInfo(Expr.treesToThrift(info_.getOrderingExprs()),
+ TSortInfo sort_info = new TSortInfo(Expr.treesToThrift(info_.getSortExprs()),
info_.getIsAscOrder(), info_.getNullsFirst());
Preconditions.checkState(tupleIds_.size() == 1,
"Incorrect size for tupleIds_ in SortNode");
@@ -208,9 +207,9 @@ public class SortNode extends PlanNode {
displayName_, getNodeExplainDetail(detailLevel)));
if (detailLevel.ordinal() >= TExplainLevel.STANDARD.ordinal()) {
output.append(detailPrefix + "order by: ");
- for (int i = 0; i < info_.getOrderingExprs().size(); ++i) {
+ for (int i = 0; i < info_.getSortExprs().size(); ++i) {
if (i > 0) output.append(", ");
- output.append(info_.getOrderingExprs().get(i).toSql() + " ");
+ output.append(info_.getSortExprs().get(i).toSql() + " ");
output.append(info_.getIsAscOrder().get(i) ? "ASC" : "DESC");
Boolean nullsFirstParam = info_.getNullsFirstParams().get(i);
@@ -221,14 +220,20 @@ public class SortNode extends PlanNode {
output.append("\n");
}
- if (detailLevel.ordinal() >= TExplainLevel.EXTENDED.ordinal()
- && info_.getMaterializedOrderingExprs().size() > 0) {
- output.append(detailPrefix + "materialized: ");
- for (int i = 0; i < info_.getMaterializedOrderingExprs().size(); ++i) {
- if (i > 0) output.append(", ");
- output.append(info_.getMaterializedOrderingExprs().get(i).toSql());
+ if (detailLevel.ordinal() >= TExplainLevel.EXTENDED.ordinal()) {
+ List<Expr> nonSlotRefExprs = Lists.newArrayList();
+ for (Expr e: info_.getMaterializedExprs()) {
+ if (e instanceof SlotRef) continue;
+ nonSlotRefExprs.add(e);
+ }
+ if (!nonSlotRefExprs.isEmpty()) {
+ output.append(detailPrefix + "materialized: ");
+ for (int i = 0; i < nonSlotRefExprs.size(); ++i) {
+ if (i > 0) output.append(", ");
+ output.append(nonSlotRefExprs.get(i).toSql());
+ }
+ output.append("\n");
}
- output.append("\n");
}
return output.toString();
http://git-wip-us.apache.org/repos/asf/impala/blob/c5e1f24e/testdata/workloads/functional-planner/queries/PlannerTest/sort-expr-materialization.test
----------------------------------------------------------------------
diff --git a/testdata/workloads/functional-planner/queries/PlannerTest/sort-expr-materialization.test b/testdata/workloads/functional-planner/queries/PlannerTest/sort-expr-materialization.test
index 146524a..e6dfe72 100644
--- a/testdata/workloads/functional-planner/queries/PlannerTest/sort-expr-materialization.test
+++ b/testdata/workloads/functional-planner/queries/PlannerTest/sort-expr-materialization.test
@@ -199,3 +199,44 @@ PLAN-ROOT SINK
mem-estimate=128.00MB mem-reservation=0B
tuple-ids=0 row-size=41B cardinality=7300
====
+# IMPALA-5270: Rand() and udf inside inline view referenced by analytic function.
+select id, row_number() over (partition by u order by r) from
+ (select id, random() r, u from
+ (select id, TestFn(double_col) u from functional.alltypestiny) v1
+ ) v2
+order by id
+---- PLAN
+F00:PLAN FRAGMENT [UNPARTITIONED] hosts=1 instances=1
+| Per-Host Resources: mem-estimate=42.00MB mem-reservation=16.00MB
+PLAN-ROOT SINK
+| mem-estimate=0B mem-reservation=0B
+|
+03:SORT
+| order by: id ASC
+| mem-estimate=6.00MB mem-reservation=6.00MB spill-buffer=2.00MB
+| tuple-ids=4 row-size=12B cardinality=8
+|
+02:ANALYTIC
+| functions: row_number()
+| partition by: u
+| order by: random() ASC
+| window: ROWS BETWEEN UNBOUNDED PRECEDING AND CURRENT ROW
+| mem-estimate=4.00MB mem-reservation=4.00MB spill-buffer=2.00MB
+| tuple-ids=6,5 row-size=32B cardinality=8
+|
+01:SORT
+| order by: default.testfn(double_col) ASC NULLS FIRST, random() ASC
+| materialized: default.testfn(double_col), random()
+| mem-estimate=6.00MB mem-reservation=6.00MB spill-buffer=2.00MB
+| tuple-ids=6 row-size=24B cardinality=8
+|
+00:SCAN HDFS [functional.alltypestiny]
+ partitions=4/4 files=4 size=460B
+ stored statistics:
+ table: rows=8 size=460B
+ partitions: 4/4 rows=8
+ columns: all
+ extrapolated-rows=disabled
+ mem-estimate=32.00MB mem-reservation=0B
+ tuple-ids=0 row-size=12B cardinality=8
+====