asterixdb-commits mailing list archives

Site index · List index
Message view « Date » · « Thread »
Top « Date » · « Thread »
From ima...@apache.org
Subject [61/85] [abbrv] incubator-asterixdb-hyracks git commit: Changes in this CL include: 1. fix asterixdb issue 810, 2. allow group-by logical operator to work with multiple nested plans.
Date Fri, 24 Apr 2015 18:46:28 GMT
http://git-wip-us.apache.org/repos/asf/incubator-asterixdb-hyracks/blob/8f33513f/algebricks/algebricks-rewriter/src/main/java/edu/uci/ics/hyracks/algebricks/rewriter/rules/PushSubplanIntoGroupByRule.java
----------------------------------------------------------------------
diff --git a/algebricks/algebricks-rewriter/src/main/java/edu/uci/ics/hyracks/algebricks/rewriter/rules/PushSubplanIntoGroupByRule.java
b/algebricks/algebricks-rewriter/src/main/java/edu/uci/ics/hyracks/algebricks/rewriter/rules/PushSubplanIntoGroupByRule.java
index 4dfede0..1eef9f8 100644
--- a/algebricks/algebricks-rewriter/src/main/java/edu/uci/ics/hyracks/algebricks/rewriter/rules/PushSubplanIntoGroupByRule.java
+++ b/algebricks/algebricks-rewriter/src/main/java/edu/uci/ics/hyracks/algebricks/rewriter/rules/PushSubplanIntoGroupByRule.java
@@ -1,25 +1,40 @@
 /*
+
  * Copyright 2009-2013 by The Regents of the University of California
+
  * Licensed 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 from
+
  * 
+
  *     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 edu.uci.ics.hyracks.algebricks.rewriter.rules;
 
 import java.util.ArrayList;
+import java.util.HashSet;
 import java.util.List;
 import java.util.Set;
 
 import org.apache.commons.lang3.mutable.Mutable;
+import org.apache.commons.lang3.mutable.MutableObject;
 
 import edu.uci.ics.hyracks.algebricks.common.exceptions.AlgebricksException;
 import edu.uci.ics.hyracks.algebricks.common.utils.ListSet;
@@ -29,92 +44,168 @@ import edu.uci.ics.hyracks.algebricks.core.algebra.base.IOptimizationContext;
 import edu.uci.ics.hyracks.algebricks.core.algebra.base.LogicalOperatorTag;
 import edu.uci.ics.hyracks.algebricks.core.algebra.base.LogicalVariable;
 import edu.uci.ics.hyracks.algebricks.core.algebra.operators.logical.AbstractLogicalOperator;
+import edu.uci.ics.hyracks.algebricks.core.algebra.operators.logical.AggregateOperator;
 import edu.uci.ics.hyracks.algebricks.core.algebra.operators.logical.GroupByOperator;
+import edu.uci.ics.hyracks.algebricks.core.algebra.operators.logical.NestedTupleSourceOperator;
 import edu.uci.ics.hyracks.algebricks.core.algebra.operators.logical.SubplanOperator;
 import edu.uci.ics.hyracks.algebricks.core.algebra.operators.logical.visitors.VariableUtilities;
+import edu.uci.ics.hyracks.algebricks.core.algebra.util.OperatorManipulationUtil;
 import edu.uci.ics.hyracks.algebricks.core.rewriter.base.IAlgebraicRewriteRule;
 
 /**
- * This rule pushes a subplan on top of a group-by into the
+ * This rule pushes an array of subplans on top of a group-by into the
  * nested plan of the group-by.
  * 
  * @author yingyib
  */
+
 public class PushSubplanIntoGroupByRule implements IAlgebraicRewriteRule {
+    /** Stores used variables above the current operator. */
+    private final Set<LogicalVariable> usedVarsSoFar = new HashSet<LogicalVariable>();
 
     @Override
-    public boolean rewritePre(Mutable<ILogicalOperator> opRef, IOptimizationContext
context) throws AlgebricksException {
+    public boolean rewritePost(Mutable<ILogicalOperator> opRef, IOptimizationContext
context)
+            throws AlgebricksException {
         return false;
     }
 
     @Override
-    public boolean rewritePost(Mutable<ILogicalOperator> opRef, IOptimizationContext
context)
-            throws AlgebricksException {
+    public boolean rewritePre(Mutable<ILogicalOperator> opRef, IOptimizationContext
context) throws AlgebricksException {
         ILogicalOperator parentOperator = opRef.getValue();
+        if (context.checkIfInDontApplySet(this, parentOperator)) {
+            return false;
+        }
+        context.addToDontApplySet(this, parentOperator);
+        VariableUtilities.getUsedVariables(parentOperator, usedVarsSoFar);
         if (parentOperator.getInputs().size() <= 0) {
             return false;
         }
         boolean changed = false;
+        GroupByOperator gby = null;
         for (Mutable<ILogicalOperator> ref : parentOperator.getInputs()) {
             AbstractLogicalOperator op = (AbstractLogicalOperator) ref.getValue();
             /** Only processes subplan operator. */
+            List<SubplanOperator> subplans = new ArrayList<SubplanOperator>();
             if (op.getOperatorTag() == LogicalOperatorTag.SUBPLAN) {
-                AbstractLogicalOperator child = (AbstractLogicalOperator) op.getInputs().get(0).getValue();
-                /** Only processes the case a group-by operator is the input of the subplan
operator. */
-                if (child.getOperatorTag() == LogicalOperatorTag.GROUP) {
-                    SubplanOperator subplan = (SubplanOperator) op;
-                    GroupByOperator gby = (GroupByOperator) child;
-                    List<ILogicalPlan> subplanNestedPlans = subplan.getNestedPlans();
-                    List<ILogicalPlan> gbyNestedPlans = gby.getNestedPlans();
-                    List<ILogicalPlan> subplanNestedPlansToRemove = new ArrayList<ILogicalPlan>();
-                    for (ILogicalPlan subplanNestedPlan : subplanNestedPlans) {
-                        List<Mutable<ILogicalOperator>> rootOpRefs = subplanNestedPlan.getRoots();
-                        List<Mutable<ILogicalOperator>> rootOpRefsToRemove =
new ArrayList<Mutable<ILogicalOperator>>();
-                        for (Mutable<ILogicalOperator> rootOpRef : rootOpRefs) {
-                            /** Gets free variables in the root operator of a nested plan
and its descent. */
-                            Set<LogicalVariable> freeVars = new ListSet<LogicalVariable>();
-                            VariableUtilities.getUsedVariablesInDescendantsAndSelf(rootOpRef.getValue(),
freeVars);
-                            Set<LogicalVariable> producedVars = new ListSet<LogicalVariable>();
-                            VariableUtilities.getProducedVariablesInDescendantsAndSelf(rootOpRef.getValue(),
-                                    producedVars);
-                            freeVars.removeAll(producedVars);
-
-                            /**
-                             * Checks whether the above freeVars are all contained in live
variables
-                             * of one nested plan inside the group-by operator.
-                             * If yes, then the subplan can be pushed into the nested plan
of the group-by.
-                             */
-                            for (ILogicalPlan gbyNestedPlan : gbyNestedPlans) {
-                                List<Mutable<ILogicalOperator>> gbyRootOpRefs
= gbyNestedPlan.getRoots();
-                                for (Mutable<ILogicalOperator> gbyRootOpRef : gbyRootOpRefs)
{
-                                    Set<LogicalVariable> liveVars = new ListSet<LogicalVariable>();
-                                    VariableUtilities.getLiveVariables(gbyRootOpRef.getValue(),
liveVars);
-                                    if (liveVars.containsAll(freeVars)) {
-                                        /** Does the actual push. */
-                                        Mutable<ILogicalOperator> ntsRef = downToNts(rootOpRef);
-                                        ntsRef.setValue(gbyRootOpRef.getValue());
-                                        gbyRootOpRef.setValue(rootOpRef.getValue());
-                                        rootOpRefsToRemove.add(rootOpRef);
-                                        changed = true;
+                while (op.getOperatorTag() == LogicalOperatorTag.SUBPLAN) {
+                    SubplanOperator currentSubplan = (SubplanOperator) op;
+                    subplans.add(currentSubplan);
+                    op = (AbstractLogicalOperator) op.getInputs().get(0).getValue();
+                }
+                /** Only processes the case a group-by operator is the input of the subplan
operators. */
+                if (op.getOperatorTag() == LogicalOperatorTag.GROUP) {
+                    gby = (GroupByOperator) op;
+                    List<ILogicalPlan> newGbyNestedPlans = new ArrayList<ILogicalPlan>();
+                    for (SubplanOperator subplan : subplans) {
+                        List<ILogicalPlan> subplanNestedPlans = subplan.getNestedPlans();
+                        List<ILogicalPlan> gbyNestedPlans = gby.getNestedPlans();
+                        List<ILogicalPlan> subplanNestedPlansToRemove = new ArrayList<ILogicalPlan>();
+                        for (ILogicalPlan subplanNestedPlan : subplanNestedPlans) {
+                            List<Mutable<ILogicalOperator>> rootOpRefs = subplanNestedPlan.getRoots();
+                            List<Mutable<ILogicalOperator>> rootOpRefsToRemove
= new ArrayList<Mutable<ILogicalOperator>>();
+                            for (Mutable<ILogicalOperator> rootOpRef : rootOpRefs)
{
+                                /** Gets free variables in the root operator of a nested
plan and its descent. */
+                                Set<LogicalVariable> freeVars = new ListSet<LogicalVariable>();
+                                VariableUtilities.getUsedVariablesInDescendantsAndSelf(rootOpRef.getValue(),
freeVars);
+                                Set<LogicalVariable> producedVars = new ListSet<LogicalVariable>();
+                                VariableUtilities.getProducedVariablesInDescendantsAndSelf(rootOpRef.getValue(),
+                                        producedVars);
+                                freeVars.removeAll(producedVars);
+                                /** * Checks whether the above freeVars are all contained
in live variables * of one nested plan inside the group-by operator. * If yes, then the subplan
can be pushed into the nested plan of the group-by. */
+                                for (ILogicalPlan gbyNestedPlanOriginal : gbyNestedPlans)
{
+                                    // add a subplan in the original gby
+                                    if (!newGbyNestedPlans.contains(gbyNestedPlanOriginal))
{
+                                        newGbyNestedPlans.add(gbyNestedPlanOriginal);
+                                    }
+
+                                    // add a pushed subplan
+                                    ILogicalPlan gbyNestedPlan = OperatorManipulationUtil.deepCopy(
+                                            gbyNestedPlanOriginal, context);
+                                    List<Mutable<ILogicalOperator>> gbyRootOpRefs
= gbyNestedPlan.getRoots();
+                                    for (int rootIndex = 0; rootIndex < gbyRootOpRefs.size();
rootIndex++) {
+                                        //set the nts for a original subplan
+                                        Mutable<ILogicalOperator> originalGbyRootOpRef
= gbyNestedPlanOriginal
+                                                .getRoots().get(rootIndex);
+                                        Mutable<ILogicalOperator> originalGbyNtsRef
= downToNts(originalGbyRootOpRef);
+                                        NestedTupleSourceOperator originalNts = (NestedTupleSourceOperator)
originalGbyNtsRef
+                                                .getValue();
+                                        originalNts.setDataSourceReference(new MutableObject<ILogicalOperator>(gby));
+
+                                        //push a new subplan if possible
+                                        Mutable<ILogicalOperator> gbyRootOpRef = gbyRootOpRefs.get(rootIndex);
+                                        Set<LogicalVariable> liveVars = new ListSet<LogicalVariable>();
+                                        VariableUtilities.getLiveVariables(gbyRootOpRef.getValue(),
liveVars);
+                                        if (liveVars.containsAll(freeVars)) {
+                                            /** Does the actual push. */
+                                            Mutable<ILogicalOperator> ntsRef = downToNts(rootOpRef);
+                                            ntsRef.setValue(gbyRootOpRef.getValue());
+                                            // Removes unused vars.
+                                            AggregateOperator aggOp = (AggregateOperator)
gbyRootOpRef.getValue();
+                                            for (int varIndex = aggOp.getVariables().size()
- 1; varIndex >= 0; varIndex--) {
+                                                if (!freeVars.contains(aggOp.getVariables().get(varIndex)))
{
+                                                    aggOp.getVariables().remove(varIndex);
+                                                    aggOp.getExpressions().remove(varIndex);
+                                                }
+                                            }
+
+                                            gbyRootOpRef.setValue(rootOpRef.getValue());
+                                            rootOpRefsToRemove.add(rootOpRef);
+
+                                            // Sets the nts for a new pushed plan.
+                                            Mutable<ILogicalOperator> oldGbyNtsRef
= downToNts(gbyRootOpRef);
+                                            NestedTupleSourceOperator nts = (NestedTupleSourceOperator)
oldGbyNtsRef
+                                                    .getValue();
+                                            nts.setDataSourceReference(new MutableObject<ILogicalOperator>(gby));
+
+                                            newGbyNestedPlans.add(gbyNestedPlan);
+                                            changed = true;
+                                            continue;
+                                        }
                                     }
                                 }
                             }
+                            rootOpRefs.removeAll(rootOpRefsToRemove);
+                            if (rootOpRefs.size() == 0) {
+                                subplanNestedPlansToRemove.add(subplanNestedPlan);
+                            }
                         }
-                        rootOpRefs.removeAll(rootOpRefsToRemove);
-                        if (rootOpRefs.size() == 0) {
-                            subplanNestedPlansToRemove.add(subplanNestedPlan);
-                        }
+                        subplanNestedPlans.removeAll(subplanNestedPlansToRemove);
                     }
-                    subplanNestedPlans.removeAll(subplanNestedPlansToRemove);
-                    if (subplanNestedPlans.size() == 0) {
+                    if (changed) {
                         ref.setValue(gby);
+                        gby.getNestedPlans().clear();
+                        gby.getNestedPlans().addAll(newGbyNestedPlans);
                     }
                 }
             }
         }
+        if (changed) {
+            cleanup(gby);
+        }
         return changed;
     }
 
+    /**
+     * Removes unused aggregation variables (and expressions)
+     * 
+     * @param gby
+     * @throws AlgebricksException
+     */
+    private void cleanup(GroupByOperator gby) throws AlgebricksException {
+        for (ILogicalPlan nestedPlan : gby.getNestedPlans()) {
+            for (Mutable<ILogicalOperator> rootRef : nestedPlan.getRoots()) {
+                AggregateOperator aggOp = (AggregateOperator) rootRef.getValue();
+                for (int varIndex = aggOp.getVariables().size() - 1; varIndex >= 0; varIndex--)
{
+                    if (!usedVarsSoFar.contains(aggOp.getVariables().get(varIndex))) {
+                        aggOp.getVariables().remove(varIndex);
+                        aggOp.getExpressions().remove(varIndex);
+                    }
+                }
+            }
+
+        }
+    }
+
     private Mutable<ILogicalOperator> downToNts(Mutable<ILogicalOperator> opRef)
{
         Mutable<ILogicalOperator> currentOpRef = opRef;
         while (currentOpRef.getValue().getInputs().size() > 0) {
@@ -122,4 +213,5 @@ public class PushSubplanIntoGroupByRule implements IAlgebraicRewriteRule
{
         }
         return currentOpRef;
     }
-}
+
+}
\ No newline at end of file

http://git-wip-us.apache.org/repos/asf/incubator-asterixdb-hyracks/blob/8f33513f/algebricks/algebricks-rewriter/src/main/java/edu/uci/ics/hyracks/algebricks/rewriter/rules/RemoveUnusedAssignAndAggregateRule.java
----------------------------------------------------------------------
diff --git a/algebricks/algebricks-rewriter/src/main/java/edu/uci/ics/hyracks/algebricks/rewriter/rules/RemoveUnusedAssignAndAggregateRule.java
b/algebricks/algebricks-rewriter/src/main/java/edu/uci/ics/hyracks/algebricks/rewriter/rules/RemoveUnusedAssignAndAggregateRule.java
index 6e0d55c..de4fbfb 100644
--- a/algebricks/algebricks-rewriter/src/main/java/edu/uci/ics/hyracks/algebricks/rewriter/rules/RemoveUnusedAssignAndAggregateRule.java
+++ b/algebricks/algebricks-rewriter/src/main/java/edu/uci/ics/hyracks/algebricks/rewriter/rules/RemoveUnusedAssignAndAggregateRule.java
@@ -14,6 +14,7 @@
  */
 package edu.uci.ics.hyracks.algebricks.rewriter.rules;
 
+import java.util.ArrayList;
 import java.util.HashSet;
 import java.util.Iterator;
 import java.util.LinkedList;
@@ -23,6 +24,7 @@ import java.util.Set;
 import org.apache.commons.lang3.mutable.Mutable;
 
 import edu.uci.ics.hyracks.algebricks.common.exceptions.AlgebricksException;
+import edu.uci.ics.hyracks.algebricks.common.utils.ListSet;
 import edu.uci.ics.hyracks.algebricks.common.utils.Triple;
 import edu.uci.ics.hyracks.algebricks.core.algebra.base.ILogicalExpression;
 import edu.uci.ics.hyracks.algebricks.core.algebra.base.ILogicalOperator;
@@ -87,6 +89,26 @@ public class RemoveUnusedAssignAndAggregateRule implements IAlgebraicRewriteRule
                     removeUnusedAssigns(r, toRemove, context);
                 }
             }
+
+            // Removes redundant nested plans that produces nothing
+            for (int i = opWithNest.getNestedPlans().size() - 1; i >= 0; i--) {
+                ILogicalPlan nestedPlan = opWithNest.getNestedPlans().get(i);
+                List<Mutable<ILogicalOperator>> rootsToBeRemoved = new ArrayList<Mutable<ILogicalOperator>>();
+                for (Mutable<ILogicalOperator> r : nestedPlan.getRoots()) {
+                    ILogicalOperator topOp = r.getValue();
+                    Set<LogicalVariable> producedVars = new ListSet<LogicalVariable>();
+                    VariableUtilities.getProducedVariablesInDescendantsAndSelf(topOp, producedVars);
+                    if (producedVars.size() == 0) {
+                        rootsToBeRemoved.add(r);
+                    }
+                }
+                // Makes sure the operator should have at least ONE nested plan even it is
empty 
+                // (because a lot of places uses this assumption,  TODO(yingyib): clean them
up).
+                if (nestedPlan.getRoots().size() == rootsToBeRemoved.size() && opWithNest.getNestedPlans().size()
> 1) {
+                    nestedPlan.getRoots().removeAll(rootsToBeRemoved);
+                    opWithNest.getNestedPlans().remove(nestedPlan);
+                }
+            }
         }
     }
 


Mime
View raw message