Internal Jenkins has submitted this change and it was merged. Change subject: IMPALA-2805: Order conjuncts based on selectivity and cost ......................................................................
IMPALA-2805: Order conjuncts based on selectivity and cost Added costs to all Exprs, which estimate the relative cost of evaluating an expression and all of its children. Costs are calculated during analysis. For now, these costs are intended as a simple way to order expressions from cheap to expensive, not necessarily to be a precise reflection of running times. In general, expressions that deal with variable length types like strings will have higher cost than those dealing with fixed length types like numbers and booleans. Additionally, expressions with complicated subexpressions will have higher cost than simpler expressions. Also added PlanNode.orderConjunctsByCost, which takes a list of Exprs and returns a new list sorted according to an estimate of the cheapest order to evaulate the conjuncts in, based on their cost and selectivity. The conjuncts are sorted by repeatedly iterating over them and choosing the conjunct that would result in the least total estimated work were it to be applied before the remaining conjuncts. Selectivities are exponentially backed off, and Exprs without selectivity estimates are given a reasonable default. Change-Id: I02279a26fbc6308ac5eb819d78345fc010469034 Reviewed-on: http://gerrit.cloudera.org:8080/2598 Reviewed-by: Thomas Tauber-Marshall <[email protected]> Tested-by: Internal Jenkins --- M fe/src/main/java/com/cloudera/impala/analysis/ArithmeticExpr.java M fe/src/main/java/com/cloudera/impala/analysis/BetweenPredicate.java M fe/src/main/java/com/cloudera/impala/analysis/BinaryPredicate.java M fe/src/main/java/com/cloudera/impala/analysis/BoolLiteral.java M fe/src/main/java/com/cloudera/impala/analysis/CaseExpr.java M fe/src/main/java/com/cloudera/impala/analysis/CastExpr.java M fe/src/main/java/com/cloudera/impala/analysis/CompoundPredicate.java M fe/src/main/java/com/cloudera/impala/analysis/Expr.java M fe/src/main/java/com/cloudera/impala/analysis/FunctionCallExpr.java M fe/src/main/java/com/cloudera/impala/analysis/InPredicate.java M fe/src/main/java/com/cloudera/impala/analysis/IsNotEmptyPredicate.java M fe/src/main/java/com/cloudera/impala/analysis/IsNullPredicate.java M fe/src/main/java/com/cloudera/impala/analysis/LikePredicate.java M fe/src/main/java/com/cloudera/impala/analysis/NullLiteral.java M fe/src/main/java/com/cloudera/impala/analysis/NumericLiteral.java M fe/src/main/java/com/cloudera/impala/analysis/SlotRef.java M fe/src/main/java/com/cloudera/impala/analysis/StringLiteral.java M fe/src/main/java/com/cloudera/impala/analysis/TimestampArithmeticExpr.java M fe/src/main/java/com/cloudera/impala/analysis/TupleIsNullPredicate.java M fe/src/main/java/com/cloudera/impala/planner/AggregationNode.java M fe/src/main/java/com/cloudera/impala/planner/AnalyticEvalNode.java M fe/src/main/java/com/cloudera/impala/planner/DataSourceScanNode.java M fe/src/main/java/com/cloudera/impala/planner/EmptySetNode.java M fe/src/main/java/com/cloudera/impala/planner/ExchangeNode.java M fe/src/main/java/com/cloudera/impala/planner/HBaseScanNode.java M fe/src/main/java/com/cloudera/impala/planner/HashJoinNode.java M fe/src/main/java/com/cloudera/impala/planner/HdfsScanNode.java M fe/src/main/java/com/cloudera/impala/planner/JoinNode.java M fe/src/main/java/com/cloudera/impala/planner/KuduScanNode.java M fe/src/main/java/com/cloudera/impala/planner/NestedLoopJoinNode.java M fe/src/main/java/com/cloudera/impala/planner/PlanNode.java M fe/src/main/java/com/cloudera/impala/planner/SelectNode.java M fe/src/main/java/com/cloudera/impala/planner/SortNode.java M fe/src/main/java/com/cloudera/impala/planner/UnionNode.java M fe/src/main/java/com/cloudera/impala/planner/UnnestNode.java M fe/src/test/java/com/cloudera/impala/planner/PlannerTest.java M testdata/workloads/functional-planner/queries/PlannerTest/analytic-fns.test A testdata/workloads/functional-planner/queries/PlannerTest/conjunct-ordering.test M testdata/workloads/functional-planner/queries/PlannerTest/data-source-tables.test M testdata/workloads/functional-planner/queries/PlannerTest/distinct.test M testdata/workloads/functional-planner/queries/PlannerTest/hbase.test M testdata/workloads/functional-planner/queries/PlannerTest/inline-view.test M testdata/workloads/functional-planner/queries/PlannerTest/join-order.test M testdata/workloads/functional-planner/queries/PlannerTest/joins.test M testdata/workloads/functional-planner/queries/PlannerTest/kudu-selectivity.test M testdata/workloads/functional-planner/queries/PlannerTest/kudu.test M testdata/workloads/functional-planner/queries/PlannerTest/nested-collections.test M testdata/workloads/functional-planner/queries/PlannerTest/outer-joins.test M testdata/workloads/functional-planner/queries/PlannerTest/predicate-propagation.test M testdata/workloads/functional-planner/queries/PlannerTest/runtime-filter-propagation.test M testdata/workloads/functional-planner/queries/PlannerTest/subquery-rewrite.test M testdata/workloads/functional-planner/queries/PlannerTest/tpcds-all.test M testdata/workloads/functional-planner/queries/PlannerTest/tpch-all.test M testdata/workloads/functional-planner/queries/PlannerTest/tpch-nested.test M testdata/workloads/functional-planner/queries/PlannerTest/union.test A testdata/workloads/targeted-perf/queries/conjunct_ordering.test 56 files changed, 733 insertions(+), 247 deletions(-) Approvals: Internal Jenkins: Verified Thomas Tauber-Marshall: Looks good to me, approved -- To view, visit http://gerrit.cloudera.org:8080/2598 To unsubscribe, visit http://gerrit.cloudera.org:8080/settings Gerrit-MessageType: merged Gerrit-Change-Id: I02279a26fbc6308ac5eb819d78345fc010469034 Gerrit-PatchSet: 20 Gerrit-Project: Impala Gerrit-Branch: cdh5-trunk Gerrit-Owner: Thomas Tauber-Marshall <[email protected]> Gerrit-Reviewer: Alex Behm <[email protected]> Gerrit-Reviewer: Henry Robinson <[email protected]> Gerrit-Reviewer: Internal Jenkins Gerrit-Reviewer: Marcel Kornacker <[email protected]> Gerrit-Reviewer: Matthew Jacobs <[email protected]> Gerrit-Reviewer: Mostafa Mokhtar <[email protected]> Gerrit-Reviewer: Thomas Tauber-Marshall <[email protected]>
