jcamachor commented on a change in pull request #567: HIVE-21382: Group by keys
reduction optimization - keys are not reduced in query23
URL: https://github.com/apache/hive/pull/567#discussion_r265281278
##########
File path:
ql/src/java/org/apache/hadoop/hive/ql/optimizer/calcite/rules/HiveRelFieldTrimmer.java
##########
@@ -315,48 +322,128 @@ private boolean isRexLiteral(final RexNode rexNode) {
}
+ private static class TableRefFinder extends RexVisitorImpl<Void> {
+ private Set<RexTableInputRef> tableRefs = null;
+ TableRefFinder() {
+ super(true);
+ this.tableRefs = new HashSet<>();
+ }
+
+ public Set<RexTableInputRef> getTableRefs() {
+ return this.tableRefs;
+ }
+
+ @Override
+ public Void visitTableInputRef(RexTableInputRef ref) {
+ this.tableRefs.add(ref);
+ return null;
+ }
+ }
+
// Given a groupset this tries to find out if the cardinality of the
grouping columns could have changed
// because if not and it consist of keys (unique + not null OR pk), we can
safely remove rest of the columns
// if those are columns are not being used further up
private ImmutableBitSet generateGroupSetIfCardinalitySame(final Aggregate
aggregate,
final ImmutableBitSet
originalGroupSet, final ImmutableBitSet fieldsUsed) {
- Pair<RelOptTable, List<Integer>> tabToOrgCol =
HiveRelOptUtil.getColumnOriginSet(aggregate.getInput(),
-
originalGroupSet);
- if(tabToOrgCol == null) {
- return originalGroupSet;
- }
- RelOptHiveTable tbl = (RelOptHiveTable)tabToOrgCol.left;
- List<Integer> backtrackedGBList = tabToOrgCol.right;
- ImmutableBitSet backtrackedGBSet =
ImmutableBitSet.builder().addAll(backtrackedGBList).build();
- List<ImmutableBitSet> allKeys = tbl.getNonNullableKeys();
- ImmutableBitSet currentKey = null;
- for(ImmutableBitSet key:allKeys) {
- if(backtrackedGBSet.contains(key)) {
- // only if grouping sets consist of keys
- currentKey = key;
- break;
+ RexBuilder rexBuilder = aggregate.getCluster().getRexBuilder();
+ RelMetadataQuery mq = aggregate.getCluster().getMetadataQuery();
+
+ Iterator<Integer> iterator = originalGroupSet.iterator();
+ Map<Pair<RelOptTable, Integer>, Pair<List<Integer>, List<Integer>>>
mapGBKeysLineage= new HashMap<>();
+
+ Map<Pair<RelOptTable, Integer>, List<Integer>> candidateKeys = new
HashMap<>();
+
+ while(iterator.hasNext()) {
+ Integer key = iterator.next();
+ RexNode inputRef = rexBuilder.makeInputRef(aggregate.getInput(),
key.intValue());
+ Set<RexNode> exprLineage = mq.getExpressionLineage(aggregate, inputRef);
+ if(exprLineage != null && exprLineage.size() == 1){
+ RexNode expr = exprLineage.iterator().next();
+ if(expr instanceof RexTableInputRef) {
+ RexTableInputRef tblRef = (RexTableInputRef)expr;
+ Pair<RelOptTable, Integer> baseTable =
Pair.of(tblRef.getTableRef().getTable(),
tblRef.getTableRef().getEntityNumber());
+ if(mapGBKeysLineage.containsKey(baseTable)) {
+ List<Integer> baseCol = mapGBKeysLineage.get(baseTable).left;
+ baseCol.add(tblRef.getIndex());
+ List<Integer> gbKey = mapGBKeysLineage.get(baseTable).right;
+ gbKey.add(key);
+ } else {
+ List<Integer> baseCol = new ArrayList<>();
+ baseCol.add(tblRef.getIndex());
+ List<Integer> gbKey = new ArrayList<>();
+ gbKey.add(key);
+ mapGBKeysLineage.put(baseTable, Pair.of(baseCol, gbKey));
+ }
+ } else if(RexUtil.isDeterministic(expr)){
+ // even though we weren't able to backtrack this key it could still
be candidate for removal
+ // if rest of the columns contain pk/unique
+ TableRefFinder finder = new TableRefFinder();
+ expr.accept(finder);
+ Set<RexTableInputRef> tableRefs = finder.getTableRefs();
+ if(tableRefs.size() == 1) {
+ RexTableInputRef tblRef = tableRefs.iterator().next();
+ Pair<RelOptTable, Integer> baseTable =
Pair.of(tblRef.getTableRef().getTable(),
tblRef.getTableRef().getEntityNumber());
+ if(candidateKeys.containsKey(baseTable)) {
+ List<Integer> candidateGBKeys = candidateKeys.get(baseTable);
+ candidateGBKeys.add(key);
+ } else {
+ List<Integer> candidateGBKeys = new ArrayList<>();
+ candidateGBKeys.add(key);
+ candidateKeys.put(baseTable, candidateGBKeys);
+ }
+ }
+ }
}
}
- if(currentKey == null || currentKey.isEmpty()) {
- return originalGroupSet;
- }
// we want to delete all columns in original GB set except the key
ImmutableBitSet.Builder builder = ImmutableBitSet.builder();
- // we have established that this gb set contains keys and it is safe to
remove rest of the columns
- for(int i=0; i<backtrackedGBList.size(); i++) {
- Integer backtrackedCol = backtrackedGBList.get(i);
- int orgCol = originalGroupSet.nth(i);
- if(fieldsUsed.get((orgCol))
- || currentKey.get(backtrackedCol)) {
- // keep the columns which are being used or are part of keys
- builder.set(orgCol);
+ for(Map.Entry<Pair<RelOptTable, Integer>, Pair<List<Integer>,
List<Integer>>> entry:mapGBKeysLineage.entrySet()) {
+ RelOptHiveTable tbl = (RelOptHiveTable)entry.getKey().left;
+ List<Integer> backtrackedGBList = entry.getValue().left;
+ List<Integer> gbKeys = entry.getValue().right;
+
+ ImmutableBitSet backtrackedGBSet =
ImmutableBitSet.builder().addAll(backtrackedGBList).build();
+
+ List<ImmutableBitSet> allKeys = tbl.getNonNullableKeys();
+ ImmutableBitSet currentKey = null;
+ for(ImmutableBitSet key:allKeys) {
+ if(backtrackedGBSet.contains(key)) {
+ // only if grouping sets consist of keys
+ currentKey = key;
+ break;
+ }
+ }
+ if(currentKey == null || currentKey.isEmpty()) {
+ continue;
+ }
+
+ // we have established that this gb set contains keys and it is safe to
remove rest of the columns
+ for(int i=0; i<backtrackedGBList.size(); i++) {
+ Integer backtrackedCol = backtrackedGBList.get(i);
+ int orgCol = gbKeys.get(i);
+ if(!fieldsUsed.get((orgCol))
+ && !currentKey.get(backtrackedCol)) {
+ // keep the columns which are being used or are part of keys
+ builder.set(orgCol);
+ }
+ }
+ // remove candidate keys if possible
+ if(candidateKeys.containsKey(entry.getKey())) {
+ List<Integer> candiateGbKeys = candidateKeys.get(entry.getKey());
+ for(Integer keyToRemove:candiateGbKeys) {
+ if(!fieldsUsed.get(keyToRemove)) {
+ builder.set(keyToRemove);
+ }
+ }
}
}
- return builder.build();
+ ImmutableBitSet keysToRemove = builder.build();
+ return originalGroupSet.except(keysToRemove);
Review comment:
Should we assert/check/throw error if the result is the empty set?
----------------------------------------------------------------
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.
For queries about this service, please contact Infrastructure at:
us...@infra.apache.org
With regards,
Apache Git Services
