rubenada commented on code in PR #6963:
URL: https://github.com/apache/hive/pull/6963#discussion_r4587489632


##########
ql/src/java/org/apache/hadoop/hive/ql/optimizer/PartialGroupByJoinTransposeOptimizer.java:
##########
@@ -0,0 +1,994 @@
+/*
+ * Licensed to the Apache Software Foundation (ASF) under one
+ * or more contributor license agreements.  See the NOTICE file
+ * distributed with this work for additional information
+ * regarding copyright ownership.  The ASF licenses this file
+ * to you under the Apache License, Version 2.0 (the
+ * "License"); you may not use this file except in compliance
+ * with the License.  You may obtain a copy of the License at
+ *
+ *     http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing,
+ * software distributed under the License is distributed on an
+ * "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY
+ * KIND, either express or implied.  See the License for the
+ * specific language governing permissions and limitations
+ * under the License.
+ */
+package org.apache.hadoop.hive.ql.optimizer;
+
+import java.util.ArrayDeque;
+import java.util.ArrayList;
+import java.util.Arrays;
+import java.util.Deque;
+import java.util.HashMap;
+import java.util.HashSet;
+import java.util.LinkedHashMap;
+import java.util.LinkedHashSet;
+import java.util.List;
+import java.util.Map;
+import java.util.Set;
+import java.util.Stack;
+import java.util.function.Function;
+import java.util.stream.Collectors;
+
+import org.apache.hadoop.hive.common.type.HiveDecimal;
+import org.apache.hadoop.hive.conf.HiveConf;
+import org.apache.hadoop.hive.ql.exec.ColumnInfo;
+import org.apache.hadoop.hive.ql.exec.FilterOperator;
+import org.apache.hadoop.hive.ql.exec.FunctionRegistry;
+import org.apache.hadoop.hive.ql.exec.GroupByOperator;
+import org.apache.hadoop.hive.ql.exec.JoinOperator;
+import org.apache.hadoop.hive.ql.exec.Operator;
+import org.apache.hadoop.hive.ql.exec.OperatorFactory;
+import org.apache.hadoop.hive.ql.exec.OperatorUtils;
+import org.apache.hadoop.hive.ql.exec.ReduceSinkOperator;
+import org.apache.hadoop.hive.ql.exec.RowSchema;
+import org.apache.hadoop.hive.ql.exec.SelectOperator;
+import org.apache.hadoop.hive.ql.exec.Utilities;
+import org.apache.hadoop.hive.ql.lib.DefaultGraphWalker;
+import org.apache.hadoop.hive.ql.lib.DefaultRuleDispatcher;
+import org.apache.hadoop.hive.ql.lib.Node;
+import org.apache.hadoop.hive.ql.lib.NodeProcessorCtx;
+import org.apache.hadoop.hive.ql.lib.RuleRegExp;
+import org.apache.hadoop.hive.ql.lib.SemanticDispatcher;
+import org.apache.hadoop.hive.ql.lib.SemanticGraphWalker;
+import org.apache.hadoop.hive.ql.lib.SemanticNodeProcessor;
+import org.apache.hadoop.hive.ql.lib.SemanticRule;
+import org.apache.hadoop.hive.ql.parse.ParseContext;
+import org.apache.hadoop.hive.ql.parse.SemanticAnalyzer;
+import org.apache.hadoop.hive.ql.parse.SemanticAnalyzer.GenericUDAFInfo;
+import org.apache.hadoop.hive.ql.parse.SemanticException;
+import org.apache.hadoop.hive.ql.parse.type.ExprNodeTypeCheck;
+import org.apache.hadoop.hive.ql.plan.AggregationDesc;
+import org.apache.hadoop.hive.ql.plan.ColStatistics;
+import org.apache.hadoop.hive.ql.plan.ExprNodeColumnDesc;
+import org.apache.hadoop.hive.ql.plan.ExprNodeConstantDesc;
+import org.apache.hadoop.hive.ql.plan.ExprNodeDesc;
+import org.apache.hadoop.hive.ql.plan.ExprNodeDescUtils;
+import org.apache.hadoop.hive.ql.plan.ExprNodeDynamicListDesc;
+import org.apache.hadoop.hive.ql.plan.ExprNodeFieldDesc;
+import org.apache.hadoop.hive.ql.plan.ExprNodeGenericFuncDesc;
+import org.apache.hadoop.hive.ql.plan.GroupByDesc;
+import org.apache.hadoop.hive.ql.plan.JoinCondDesc;
+import org.apache.hadoop.hive.ql.plan.JoinDesc;
+import org.apache.hadoop.hive.ql.plan.PlanUtils;
+import org.apache.hadoop.hive.ql.plan.ReduceSinkDesc;
+import org.apache.hadoop.hive.ql.plan.SelectDesc;
+import org.apache.hadoop.hive.ql.plan.Statistics;
+import org.apache.hadoop.hive.ql.stats.StatsUtils;
+import org.apache.hadoop.hive.ql.udf.generic.GenericUDAFEvaluator;
+import org.apache.hadoop.hive.ql.udf.generic.GenericUDF;
+import org.apache.hadoop.hive.ql.udf.generic.GenericUDFIf;
+import org.apache.hadoop.hive.ql.udf.generic.GenericUDFOPMinus;
+import org.apache.hadoop.hive.ql.udf.generic.GenericUDFOPMultiply;
+import org.apache.hadoop.hive.ql.udf.generic.GenericUDFOPPlus;
+import org.apache.hadoop.hive.ql.udf.generic.GenericUDFWhen;
+import org.apache.hadoop.hive.serde2.typeinfo.PrimitiveTypeInfo;
+import org.apache.hadoop.hive.serde2.typeinfo.TypeInfo;
+import org.slf4j.Logger;
+import org.slf4j.LoggerFactory;
+
+/**
+ * Pushes a map-side (hash) GROUP BY below an inner join, to the join input 
that holds every aggregation
+ * argument. The pushed GROUP BY runs in {@link GroupByDesc.Mode#PARTIAL_HASH} 
mode in the vertex of that input,
+ * before its existing shuffle (or map join). The matched GROUP BY stays above 
the join with the same mode and
+ * output, but its aggregations merge the partial results ({@code PARTIAL2}) 
instead of iterating over rows. The
+ * reduce-side GROUP BY that computes the final aggregate is unchanged.
+ * <pre>
+ *   TS - SEL - RS \
+ *                  JOIN - SEL - GBY(hash) - RS - GBY(mergepartial)
+ *   TS - SEL - RS /
+ *
+ *   =>
+ *
+ *   TS - SEL - GBY(partialhash) - RS \
+ *                                     JOIN - GBY(hash) - RS - 
GBY(mergepartial)
+ *   TS - SEL ------------------ RS /
+ * </pre>
+ * <p>Criteria must meet
+ * <ul>
+ *   <li>The join is a common join when this optimization applied (a {@link 
JoinOperator}, every input a ReduceSink).
+ *   The {@link JoinOperator} must be Inner Join. If the {@link JoinOperator} 
is an n-way join all entry in the
+ *   condition map has to be Inner Join.
+ *   <li>the GROUP BY<ul>
+ *     <li>is over the join through Select operators only;</li>
+ *     <li>it has keys,</li>
+ *     <li>no grouping sets</li>
+ *     <li>no distinct aggregation,</li>
+ *     <li>only SUM, $SUM0, COUNT, MIN and MAX aggregations: their partial 
result is a plain
+ *         value, merged by SUM (counts) or the function itself</li></ul>
+ *   </li>
+ *   <li>every aggregate key is deterministic and references one join input at 
most</li>
+ *   <li>every aggregation argument (examples over {@code store_sales JOIN 
date_dim})
+ *   <ul>
+ *     <li>is deterministic and references one join input at most. For 
example, in {@code sum(ss_sales_price)} the
+ *     argument references store_sales: the input the GROUP BY is pushed 
to.</li>
+ *     <li>or it is an {@code IF(condition, value, else)} whose condition 
references one join input and whose value
+ *     the other. For example, in {@code sum(if(d_day_name = 'Sunday', 
ss_sales_price, null))}:
+ *     <ul>
+ *       <li>the condition is {@code d_day_name = 'Sunday'}, it references 
date_dim;</li>
+ *       <li>the value is {@code ss_sales_price}, it references store_sales: 
the input the GROUP BY is pushed to;</li>
+ *       <li>the else is {@code null}.</li>
+ *     </ul>
+ *     The value is aggregated below the join, {@code sum(ss_sales_price)}, 
and the condition is applied to the
+ *     partial result above the join: {@code sum(if(d_day_name = 'Sunday', 
partial, null))};</li>
+ *     <li>or it is a {@code CASE WHEN condition THEN value [ELSE else] END} 
with the same condition and value as
+ *     the IF; a missing ELSE is NULL. For example,
+ *     {@code sum(case when d_day_name = 'Sunday' then ss_sales_price else 0 
end)} is aggregated below the join as
+ *     {@code sum(ss_sales_price)}, and above the join as {@code 
sum(if(d_day_name = 'Sunday', partial, 0))}.</li>
+ *   </ul>
+ *   Splitting an IF or CASE is exact because every row of a pushed group has 
the same join key, so it joins the
+ *   same rows of the other input: for each of those rows, the condition is 
true or false for the whole group. The
+ *   value is aggregated over the rows whose condition is false too, so it 
must not fail on them: it is built from
+ *   columns, constants, +, -, * and casts only. The else is NULL, or 0 for a 
SUM;</li>
+ *   <li>every aggregation argument (the value, for a split IF or CASE) 
references the same join input, and the
+ *   GROUP BY is pushed to it; otherwise the push is skipped.<br>
+ *   Example: {@code sum(ss_sales_price), max(d_moy)} over {@code store_sales 
JOIN date_dim} is not pushed.<br>
+ *   An argument without columns does not choose an input; if no argument has 
columns, the GROUP BY is pushed to
+ *   the larger input.<br>
+ *   Example: {@code count(*)}, {@code count(1)};</li>
+ *   <li>the pushed aggregate's keys are going to be the original keys 
available on that input plus
+ *   the join keys from that side and its columns used by residual join 
filters (non-equijoin filters)</li>
+ *   <li>the push is skipped when the join expands its input by more than
+ *   {@code hive.optimize.partial.aggr.join.transpose.max.join.expansion}, 
when the pushed keys outnumber the
+ *   original keys and the columns of the IF conditions or are empty, or when 
a pushed key has an NDV of more than
+ *   {@code hive.optimize.partial.aggr.join.transpose.max.key.ndv.ratio} x 
input rows </li>
+ *   <li>missing statistics also skip it. Required:
+ *   <ul>
+ *     <li>the row count of the join;</li>
+ *     <li>the row count of the join input the aggregate is pushed to;</li>
+ *     <li>the column statistics of every pushed key column (both join and 
aggregate);</li>
+ *     <li>the row counts of every join input, when no aggregation argument 
has columns (e.g. every aggregation is
+ *     {@code count(*)} or {@code count(1)}).</li>
+ *   </ul>
+ *   </li>
+ *   <li>the push is also skipped when the join reduces the pushed input by 
more than
+ *   {@code hive.optimize.partial.aggr.join.transpose.max.join.reduction}: 
Hive has no dynamic filters for a map
+ *   join, so the pushed GROUP BY would process every row the join 
discards.</li>
+ * </ul>
+ *
+ * <p>When a pushed GROUP BY is matched again it can be moved further down a 
chain of joins. It is not kept above the
+ * join it moves below: a Select projecting its keys and the partial results 
replaces it.
+ *
+ * <p>The TezCompiler annotates the statistics, which the gates above read, 
right before this optimization.
+ * This optimization runs before the top n key optimization: a Top N Key 
operator pushed down to the join output
+ * would sit between the join and the GROUP BY. It runs before the dynamic 
partition pruning: its semijoin branches
+ * would hang off the join inputs and the joins,
+ * so the GROUP BY could not move below them, and built afterwards they read 
from the pushed GROUP BY. The
+ * synthetic join predicates of residual join filters that read the values of 
a pushed join input are moved to the
+ * pushed GROUP BY output.
+ */
+public class PartialGroupByJoinTransposeOptimizer extends Transform {
+
+  private static final Logger LOG = 
LoggerFactory.getLogger(PartialGroupByJoinTransposeOptimizer.class);
+
+  private static final Set<String> SUPPORTED_UDAFS = Set.of("sum", "$sum0", 
"count", "min", "max");
+
+  // inputOf results other than a join input tag
+  private static final int NO_INPUT = -1;
+  private static final int INVALID = -2;
+
+  private HiveConf conf;
+  private float minReduction;
+  private float maxJoinReduction;
+  private float maxJoinExpansion;
+  private float maxKeyNdvRatio;
+  // the value lists of synthetic join predicates from residual join filters: 
their target is an expression over
+  // the input of the join input they read from
+  private final List<ExprNodeDynamicListDesc> residualDynamicLists = new 
ArrayList<>();
+
+  @Override
+  public ParseContext transform(ParseContext pctx) throws SemanticException {
+    conf = pctx.getConf();
+    minReduction = HiveConf.getFloatVar(conf, 
HiveConf.ConfVars.PARTIAL_AGGR_JOIN_TRANSPOSE_MIN_REDUCTION);
+    maxJoinReduction = HiveConf.getFloatVar(conf, 
HiveConf.ConfVars.PARTIAL_AGGR_JOIN_TRANSPOSE_MAX_JOIN_REDUCTION);
+    maxJoinExpansion = HiveConf.getFloatVar(conf, 
HiveConf.ConfVars.PARTIAL_AGGR_JOIN_TRANSPOSE_MAX_JOIN_EXPANSION);
+    maxKeyNdvRatio = HiveConf.getFloatVar(conf, 
HiveConf.ConfVars.PARTIAL_AGGR_JOIN_TRANSPOSE_MAX_KEY_NDV_RATIO);
+    String JOIN = JoinOperator.getOperatorName() + "%";
+    String SEL = SelectOperator.getOperatorName() + "%";
+    String GBY = GroupByOperator.getOperatorName() + "%";
+
+    Map<SemanticRule, SemanticNodeProcessor> opRules = Map.of(
+        new RuleRegExp("R1", JOIN + "(" + SEL + ")*" + GBY), new 
CandidateCollector());
+
+    // only collect the candidates during the walk and push them afterwards: 
pushing changes the operators around the
+    // join, which the walker may still visit
+    CandidateCtx ctx = new CandidateCtx();
+    SemanticDispatcher semanticDispatcher = new DefaultRuleDispatcher(null, 
opRules, ctx);
+    SemanticGraphWalker graphWalker = new 
DefaultGraphWalker(semanticDispatcher);
+    List<Node> topNodes = new ArrayList<>(pctx.getTopOps().values());
+    graphWalker.startWalking(topNodes, null);
+    if (ctx.candidates.isEmpty()) {
+      return pctx;
+    }
+
+    List<Operator<?>> topOps = new ArrayList<>(pctx.getTopOps().values());
+    for (FilterOperator filter : OperatorUtils.findOperators(topOps, 
FilterOperator.class)) {
+      collectResidualDynamicLists(filter.getConf().getPredicate(), 
residualDynamicLists);
+    }
+
+    Deque<GroupByOperator> candidates = new ArrayDeque<>(ctx.candidates);
+    while (!candidates.isEmpty()) {
+      GroupByOperator pushed = push(candidates.poll());
+      if (pushed != null) {
+        // it may move further down a chain of joins
+        candidates.add(pushed);
+      }
+    }
+    return pctx;
+  }
+
+  private static class CandidateCtx implements NodeProcessorCtx {
+    private final Set<GroupByOperator> candidates = new LinkedHashSet<>();
+  }
+
+  private static class CandidateCollector implements SemanticNodeProcessor {
+    @Override
+    public Object process(Node nd, Stack<Node> stack, NodeProcessorCtx 
procCtx, Object... nodeOutputs) {
+      ((CandidateCtx) procCtx).candidates.add((GroupByOperator) nd);
+      return null;
+    }
+  }
+
+  private static void collectResidualDynamicLists(ExprNodeDesc expr, 
List<ExprNodeDynamicListDesc> lists) {
+    if (expr instanceof ExprNodeDynamicListDesc) {
+      if (((ExprNodeDynamicListDesc) expr).getTarget() != null) {
+        lists.add((ExprNodeDynamicListDesc) expr);
+      }
+    } else if (expr != null && expr.getChildren() != null) {
+      for (ExprNodeDesc child : expr.getChildren()) {
+        collectResidualDynamicLists(child, lists);
+      }
+    }
+  }
+
+  /**
+   * Pushes the GROUP BY below the join it is over, if every criterion is met.
+   *
+   * @return the pushed GROUP BY, or null if the plan is unchanged
+   */
+  private GroupByOperator push(GroupByOperator gby) throws SemanticException {
+    GroupByDesc gbyDesc = gby.getConf();
+    if (gby.getNumParent() != 1 || !gbyDesc.getMode().isHash() || 
gbyDesc.isGroupingSetsPresent()
+        || gbyDesc.getBucketGroup() || gbyDesc.isDistinct() || 
gbyDesc.getKeys().isEmpty()) {
+      return null;
+    }
+    List<AggregationDesc> aggs = gbyDesc.getAggregators();
+    for (AggregationDesc agg : aggs) {
+      if (agg.getDistinct() || agg.getMode() != 
GenericUDAFEvaluator.Mode.PARTIAL1
+          || 
!SUPPORTED_UDAFS.contains(agg.getGenericUDAFName().toLowerCase())) {
+        return null;
+      }
+    }
+
+    // the operator directly over the join: the lowest Select or the GROUP BY 
itself
+    Operator<?> joinChild = gby;
+    Operator<?> parent = gby.getParentOperators().getFirst();
+    while (parent instanceof SelectOperator) {
+      if (parent.getNumChild() != 1 || parent.getNumParent() != 1) {
+        return null;
+      }
+      joinChild = parent;
+      parent = parent.getParentOperators().getFirst();
+    }
+    if (!(parent instanceof JoinOperator join) || parent.getNumChild() != 1) {
+      return null;
+    }
+    JoinDesc joinDesc = join.getConf();
+    if (joinDesc.getHandleSkewJoin()) {
+      return null;
+    }
+    for (JoinCondDesc cond : joinDesc.getConds()) {
+      if (cond.getType() != JoinDesc.INNER_JOIN) {
+        return null;
+      }
+    }
+    ReduceSinkOperator[] rsByTag = new ReduceSinkOperator[join.getNumParent()];
+    for (Operator<?> joinParent : join.getParentOperators()) {
+      if (!(joinParent instanceof ReduceSinkOperator reduceSinkOperator) || 
joinParent.getNumParent() != 1
+          || joinParent.getNumChild() != 1) {
+        return null;
+      }
+      int tag = reduceSinkOperator.getConf().getTag();
+      if (tag < 0 || tag >= rsByTag.length || rsByTag[tag] != null) {
+        return null;
+      }
+      rsByTag[tag] = reduceSinkOperator;
+    }
+    Map<String, Byte> reversedExprs = joinDesc.getReversedExprs();
+    if (reversedExprs == null || join.getColumnExprMap() == null) {
+      return null;
+    }
+    for (String name : joinDesc.getOutputColumnNames()) {
+      if (reversedExprs.get(name) == null || 
join.getSchema().getColumnInfo(name) == null) {
+        return null;
+      }
+    }
+
+    // the GBY keys and aggregation arguments, backtracked through the Selects 
to the join output, and the join
+    // input each one references
+    List<ExprNodeDesc> keys = ExprNodeDescUtils.backtrack(gbyDesc.getKeys(), 
gby, joinChild);
+    int[] keyInputs = new int[keys.size()];
+    for (int i = 0; i < keys.size(); i++) {
+      keyInputs[i] = inputOf(keys.get(i), reversedExprs);
+      if (keyInputs[i] == INVALID) {
+        return null;
+      }
+    }
+    List<List<ExprNodeDesc>> params = new ArrayList<>();
+    List<CaseSplit> splits = new ArrayList<>();
+    Set<String> conditionCols = new HashSet<>();
+    int side = NO_INPUT;
+    for (AggregationDesc agg : aggs) {
+      List<ExprNodeDesc> aggParams = 
ExprNodeDescUtils.backtrack(agg.getParameters(), gby, joinChild);
+      CaseSplit split = null;
+      if (aggParams.size() == 1 && inputOf(aggParams.getFirst(), 
reversedExprs) == INVALID) {
+        // the value is aggregated below the join, on the input other than the 
condition's
+        split = splitCase(agg, aggParams.getFirst(), reversedExprs);
+        if (split == null) {
+          return null;
+        }
+        conditionCols.addAll(split.conditionCols);
+        aggParams = new ArrayList<>(Arrays.asList(split.value));
+      }
+      splits.add(split);
+      for (ExprNodeDesc param : aggParams) {
+        int input = inputOf(param, reversedExprs);
+        if (input == INVALID) {
+          return null;
+        }
+        // the arguments of all the aggregations must be on the same join 
input, the one the GBY is pushed to
+        if (input != NO_INPUT && side != NO_INPUT && input != side) {
+          return null;
+        }
+        if (input != NO_INPUT) {
+          side = input;
+        }
+      }
+      params.add(aggParams);
+    }
+    if (side == NO_INPUT) {
+      side = largestInput(rsByTag);
+      if (side == NO_INPUT) {
+        return null;
+      }
+    }
+    // The join's filter predicates (not its residual filter predicates) on 
the input the GROUP BY would be pushed to
+    // are evaluated on each row of that input, but it would send partial 
results instead of rows. Bail out. Inner
+    // joins have such predicates only when the CBO return path 
(hive.cbo.returnpath.hiveop) is on.
+    if (joinDesc.getFilters() != null && joinDesc.getFilters().get((byte) 
side) != null
+        && !joinDesc.getFilters().get((byte) side).isEmpty()) {
+      return null;
+    }
+    ReduceSinkOperator rs = rsByTag[side];
+    ReduceSinkDesc rsDesc = rs.getConf();
+    Operator<?> sideRsParent = rs.getParentOperators().getFirst();
+
+    // pushed keys over the input of the join input: the original keys of the 
input, its join keys and its
+    // columns used by residual filters
+    List<ExprNodeDesc> pushedKeys = new ArrayList<>();
+    int[] keyToPushed = new int[keys.size()];
+    for (int i = 0; i < keys.size(); i++) {
+      keyToPushed[i] = -1;
+      if (keyInputs[i] == side) {
+        ExprNodeDesc key = ExprNodeDescUtils.backtrack(keys.get(i), joinChild, 
rs);
+        if (key == null) {
+          return null;
+        }
+        keyToPushed[i] = addUnique(pushedKeys, key);
+      }
+    }
+    List<ExprNodeDesc> rsKeyCols = rsDesc.getKeyCols();
+    int[] rsKeyToPushed = new int[rsKeyCols.size()];
+    for (int k = 0; k < rsKeyCols.size(); k++) {
+      rsKeyToPushed[k] = addUnique(pushedKeys, rsKeyCols.get(k));
+    }
+    List<ExprNodeDesc> residualFilters = joinDesc.getResidualFilterExprs();
+    Map<String, Integer> filterColToPushed = new HashMap<>();
+    if (residualFilters != null) {
+      for (ExprNodeDesc filter : residualFilters) {
+        List<ExprNodeColumnDesc> cols = columnsOf(filter);
+        if (cols == null) {
+          return null;
+        }
+        for (ExprNodeColumnDesc col : cols) {
+          Byte tag = reversedExprs.get(col.getColumn());
+          if (tag == null) {
+            return null;
+          }
+          if (tag == side && !filterColToPushed.containsKey(col.getColumn())) {
+            ExprNodeDesc key = ExprNodeDescUtils.backtrack(col, joinChild, rs);
+            if (key == null) {
+              return null;
+            }
+            filterColToPushed.put(col.getColumn(), addUnique(pushedKeys, key));
+          }
+        }
+      }
+    }
+    // The push is skipped when the pushed keys (the original keys on this 
input, its
+    // join keys and its columns used by residual filters) are empty or 
outnumber the keys of the original GROUP BY
+    // plus the columns of the split IF conditions.

Review Comment:
   why? is this a perf-wise heuristic?



-- 
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.

To unsubscribe, e-mail: [email protected]

For queries about this service, please contact Infrastructure at:
[email protected]


---------------------------------------------------------------------
To unsubscribe, e-mail: [email protected]
For additional commands, e-mail: [email protected]

Reply via email to