You are viewing a plain text version of this content. The canonical link for it is here.
Posted to commits@asterixdb.apache.org by im...@apache.org on 2015/08/25 18:41:23 UTC
[10/51] [partial] incubator-asterixdb-hyracks git commit: Change
folder structure for Java repackage
http://git-wip-us.apache.org/repos/asf/incubator-asterixdb-hyracks/blob/9939b48e/algebricks/algebricks-rewriter/src/main/java/edu/uci/ics/hyracks/algebricks/rewriter/util/JoinUtils.java
----------------------------------------------------------------------
diff --git a/algebricks/algebricks-rewriter/src/main/java/edu/uci/ics/hyracks/algebricks/rewriter/util/JoinUtils.java b/algebricks/algebricks-rewriter/src/main/java/edu/uci/ics/hyracks/algebricks/rewriter/util/JoinUtils.java
deleted file mode 100644
index 0881b50..0000000
--- a/algebricks/algebricks-rewriter/src/main/java/edu/uci/ics/hyracks/algebricks/rewriter/util/JoinUtils.java
+++ /dev/null
@@ -1,210 +0,0 @@
-/*
- * 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.util;
-
-import java.util.ArrayList;
-import java.util.Collection;
-import java.util.LinkedList;
-import java.util.List;
-
-import org.apache.commons.lang3.mutable.Mutable;
-
-import edu.uci.ics.hyracks.algebricks.common.exceptions.AlgebricksException;
-import edu.uci.ics.hyracks.algebricks.core.algebra.base.ILogicalExpression;
-import edu.uci.ics.hyracks.algebricks.core.algebra.base.ILogicalOperator;
-import edu.uci.ics.hyracks.algebricks.core.algebra.base.IOptimizationContext;
-import edu.uci.ics.hyracks.algebricks.core.algebra.base.LogicalExpressionTag;
-import edu.uci.ics.hyracks.algebricks.core.algebra.base.LogicalVariable;
-import edu.uci.ics.hyracks.algebricks.core.algebra.expressions.AbstractFunctionCallExpression;
-import edu.uci.ics.hyracks.algebricks.core.algebra.expressions.BroadcastExpressionAnnotation;
-import edu.uci.ics.hyracks.algebricks.core.algebra.expressions.BroadcastExpressionAnnotation.BroadcastSide;
-import edu.uci.ics.hyracks.algebricks.core.algebra.expressions.IExpressionAnnotation;
-import edu.uci.ics.hyracks.algebricks.core.algebra.expressions.VariableReferenceExpression;
-import edu.uci.ics.hyracks.algebricks.core.algebra.functions.AlgebricksBuiltinFunctions;
-import edu.uci.ics.hyracks.algebricks.core.algebra.functions.AlgebricksBuiltinFunctions.ComparisonKind;
-import edu.uci.ics.hyracks.algebricks.core.algebra.functions.FunctionIdentifier;
-import edu.uci.ics.hyracks.algebricks.core.algebra.operators.logical.AbstractBinaryJoinOperator;
-import edu.uci.ics.hyracks.algebricks.core.algebra.operators.logical.visitors.LogicalPropertiesVisitor;
-import edu.uci.ics.hyracks.algebricks.core.algebra.operators.physical.AbstractJoinPOperator.JoinPartitioningType;
-import edu.uci.ics.hyracks.algebricks.core.algebra.operators.physical.HybridHashJoinPOperator;
-import edu.uci.ics.hyracks.algebricks.core.algebra.operators.physical.InMemoryHashJoinPOperator;
-import edu.uci.ics.hyracks.algebricks.core.algebra.operators.physical.NLJoinPOperator;
-import edu.uci.ics.hyracks.algebricks.core.algebra.properties.ILogicalPropertiesVector;
-import edu.uci.ics.hyracks.algebricks.core.config.AlgebricksConfig;
-
-public class JoinUtils {
-
- public static void setJoinAlgorithmAndExchangeAlgo(AbstractBinaryJoinOperator op, IOptimizationContext context)
- throws AlgebricksException {
- List<LogicalVariable> sideLeft = new LinkedList<LogicalVariable>();
- List<LogicalVariable> sideRight = new LinkedList<LogicalVariable>();
- List<LogicalVariable> varsLeft = op.getInputs().get(0).getValue().getSchema();
- List<LogicalVariable> varsRight = op.getInputs().get(1).getValue().getSchema();
- if (isHashJoinCondition(op.getCondition().getValue(), varsLeft, varsRight, sideLeft, sideRight)) {
- BroadcastSide side = getBroadcastJoinSide(op.getCondition().getValue(), varsLeft, varsRight);
- if (side == null) {
- setHashJoinOp(op, JoinPartitioningType.PAIRWISE, sideLeft, sideRight, context);
- } else {
- switch (side) {
- case RIGHT:
- setHashJoinOp(op, JoinPartitioningType.BROADCAST, sideLeft, sideRight, context);
- break;
- case LEFT:
- Mutable<ILogicalOperator> opRef0 = op.getInputs().get(0);
- Mutable<ILogicalOperator> opRef1 = op.getInputs().get(1);
- ILogicalOperator tmp = opRef0.getValue();
- opRef0.setValue(opRef1.getValue());
- opRef1.setValue(tmp);
- setHashJoinOp(op, JoinPartitioningType.BROADCAST, sideRight, sideLeft, context);
- break;
- default:
- setHashJoinOp(op, JoinPartitioningType.PAIRWISE, sideLeft, sideRight, context);
- }
- }
- } else {
- setNLJoinOp(op, context);
- }
- }
-
- private static void setNLJoinOp(AbstractBinaryJoinOperator op, IOptimizationContext context) {
- op.setPhysicalOperator(new NLJoinPOperator(op.getJoinKind(), JoinPartitioningType.BROADCAST, context
- .getPhysicalOptimizationConfig().getMaxRecordsPerFrame()));
- }
-
- private static void setHashJoinOp(AbstractBinaryJoinOperator op, JoinPartitioningType partitioningType,
- List<LogicalVariable> sideLeft, List<LogicalVariable> sideRight, IOptimizationContext context)
- throws AlgebricksException {
- op.setPhysicalOperator(new HybridHashJoinPOperator(op.getJoinKind(), partitioningType, sideLeft, sideRight,
- context.getPhysicalOptimizationConfig().getMaxFramesHybridHash(), context
- .getPhysicalOptimizationConfig().getMaxFramesLeftInputHybridHash(), context
- .getPhysicalOptimizationConfig().getMaxRecordsPerFrame(), context
- .getPhysicalOptimizationConfig().getFudgeFactor()));
- if (partitioningType == JoinPartitioningType.BROADCAST) {
- hybridToInMemHashJoin(op, context);
- }
- // op.setPhysicalOperator(new
- // InMemoryHashJoinPOperator(op.getJoinKind(), partitioningType,
- // sideLeft, sideRight,
- // 1024 * 512));
- }
-
- private static void hybridToInMemHashJoin(AbstractBinaryJoinOperator op, IOptimizationContext context)
- throws AlgebricksException {
- ILogicalOperator opBuild = op.getInputs().get(1).getValue();
- LogicalPropertiesVisitor.computeLogicalPropertiesDFS(opBuild, context);
- ILogicalPropertiesVector v = context.getLogicalPropertiesVector(opBuild);
- AlgebricksConfig.ALGEBRICKS_LOGGER.fine("// HybridHashJoin inner branch -- Logical properties for " + opBuild
- + ": " + v + "\n");
- if (v != null) {
- int size2 = v.getMaxOutputFrames();
- HybridHashJoinPOperator hhj = (HybridHashJoinPOperator) op.getPhysicalOperator();
- if (size2 > 0 && size2 * hhj.getFudgeFactor() <= hhj.getMemSizeInFrames()) {
- AlgebricksConfig.ALGEBRICKS_LOGGER.fine("// HybridHashJoin inner branch " + opBuild
- + " fits in memory\n");
- // maintains the local properties on the probe side
- op.setPhysicalOperator(new InMemoryHashJoinPOperator(hhj.getKind(), hhj.getPartitioningType(), hhj
- .getKeysLeftBranch(), hhj.getKeysRightBranch(), v.getNumberOfTuples() * 2));
- }
- }
-
- }
-
- private static boolean isHashJoinCondition(ILogicalExpression e, Collection<LogicalVariable> inLeftAll,
- Collection<LogicalVariable> inRightAll, Collection<LogicalVariable> outLeftFields,
- Collection<LogicalVariable> outRightFields) {
- switch (e.getExpressionTag()) {
- case FUNCTION_CALL: {
- AbstractFunctionCallExpression fexp = (AbstractFunctionCallExpression) e;
- FunctionIdentifier fi = fexp.getFunctionIdentifier();
- if (fi.equals(AlgebricksBuiltinFunctions.AND)) {
- for (Mutable<ILogicalExpression> a : fexp.getArguments()) {
- if (!isHashJoinCondition(a.getValue(), inLeftAll, inRightAll, outLeftFields,
- outRightFields)) {
- return false;
- }
- }
- return true;
- } else {
- ComparisonKind ck = AlgebricksBuiltinFunctions.getComparisonType(fi);
- if (ck != ComparisonKind.EQ) {
- return false;
- }
- ILogicalExpression opLeft = fexp.getArguments().get(0).getValue();
- ILogicalExpression opRight = fexp.getArguments().get(1).getValue();
- if (opLeft.getExpressionTag() != LogicalExpressionTag.VARIABLE
- || opRight.getExpressionTag() != LogicalExpressionTag.VARIABLE) {
- return false;
- }
- LogicalVariable var1 = ((VariableReferenceExpression) opLeft).getVariableReference();
- if (inLeftAll.contains(var1) && !outLeftFields.contains(var1)) {
- outLeftFields.add(var1);
- } else if (inRightAll.contains(var1) && !outRightFields.contains(var1)) {
- outRightFields.add(var1);
- } else {
- return false;
- }
- LogicalVariable var2 = ((VariableReferenceExpression) opRight).getVariableReference();
- if (inLeftAll.contains(var2) && !outLeftFields.contains(var2)) {
- outLeftFields.add(var2);
- } else if (inRightAll.contains(var2) && !outRightFields.contains(var2)) {
- outRightFields.add(var2);
- } else {
- return false;
- }
- return true;
- }
- }
- default: {
- return false;
- }
- }
- }
-
- private static BroadcastSide getBroadcastJoinSide(ILogicalExpression e, List<LogicalVariable> varsLeft,
- List<LogicalVariable> varsRight) {
- if (e.getExpressionTag() != LogicalExpressionTag.FUNCTION_CALL) {
- return null;
- }
- AbstractFunctionCallExpression fexp = (AbstractFunctionCallExpression) e;
- IExpressionAnnotation ann = fexp.getAnnotations().get(BroadcastExpressionAnnotation.BROADCAST_ANNOTATION_KEY);
- if (ann == null) {
- return null;
- }
- BroadcastSide side = (BroadcastSide) ann.getObject();
- if (side == null) {
- return null;
- }
- int i;
- switch (side) {
- case LEFT:
- i = 0;
- break;
- case RIGHT:
- i = 1;
- break;
- default:
- return null;
- }
- ArrayList<LogicalVariable> vars = new ArrayList<LogicalVariable>();
- fexp.getArguments().get(i).getValue().getUsedVariables(vars);
- if (varsLeft.containsAll(vars)) {
- return BroadcastSide.LEFT;
- } else if (varsRight.containsAll(vars)) {
- return BroadcastSide.RIGHT;
- } else {
- return null;
- }
- }
-}
http://git-wip-us.apache.org/repos/asf/incubator-asterixdb-hyracks/blob/9939b48e/algebricks/algebricks-rewriter/src/main/java/edu/uci/ics/hyracks/algebricks/rewriter/util/PhysicalOptimizationsUtil.java
----------------------------------------------------------------------
diff --git a/algebricks/algebricks-rewriter/src/main/java/edu/uci/ics/hyracks/algebricks/rewriter/util/PhysicalOptimizationsUtil.java b/algebricks/algebricks-rewriter/src/main/java/edu/uci/ics/hyracks/algebricks/rewriter/util/PhysicalOptimizationsUtil.java
deleted file mode 100644
index ecacc05..0000000
--- a/algebricks/algebricks-rewriter/src/main/java/edu/uci/ics/hyracks/algebricks/rewriter/util/PhysicalOptimizationsUtil.java
+++ /dev/null
@@ -1,71 +0,0 @@
-/*
- * 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.util;
-
-import java.util.HashSet;
-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.core.algebra.base.ILogicalOperator;
-import edu.uci.ics.hyracks.algebricks.core.algebra.base.ILogicalPlan;
-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.operators.logical.AbstractLogicalOperator;
-import edu.uci.ics.hyracks.algebricks.core.algebra.operators.logical.AbstractOperatorWithNestedPlans;
-import edu.uci.ics.hyracks.algebricks.core.algebra.operators.logical.NestedTupleSourceOperator;
-import edu.uci.ics.hyracks.algebricks.core.algebra.operators.logical.visitors.FDsAndEquivClassesVisitor;
-import edu.uci.ics.hyracks.algebricks.core.config.AlgebricksConfig;
-
-public class PhysicalOptimizationsUtil {
-
- public static void computeFDsAndEquivalenceClasses(AbstractLogicalOperator op, IOptimizationContext ctx)
- throws AlgebricksException {
- FDsAndEquivClassesVisitor visitor = new FDsAndEquivClassesVisitor();
- Set<ILogicalOperator> visitSet = new HashSet<ILogicalOperator>();
- computeFDsAndEqClassesWithVisitorRec(op, ctx, visitor, visitSet);
- }
-
- private static void computeFDsAndEqClassesWithVisitorRec(AbstractLogicalOperator op, IOptimizationContext ctx,
- FDsAndEquivClassesVisitor visitor, Set<ILogicalOperator> visitSet) throws AlgebricksException {
- visitSet.add(op);
- for (Mutable<ILogicalOperator> i : op.getInputs()) {
- computeFDsAndEqClassesWithVisitorRec((AbstractLogicalOperator) i.getValue(), ctx, visitor, visitSet);
- }
- if (op.hasNestedPlans()) {
- for (ILogicalPlan p : ((AbstractOperatorWithNestedPlans) op).getNestedPlans()) {
- for (Mutable<ILogicalOperator> r : p.getRoots()) {
- AbstractLogicalOperator rootOp = (AbstractLogicalOperator) r.getValue();
- computeFDsAndEqClassesWithVisitorRec(rootOp, ctx, visitor, visitSet);
- }
- }
- }
- if (op.getOperatorTag() == LogicalOperatorTag.NESTEDTUPLESOURCE) {
- NestedTupleSourceOperator nts = (NestedTupleSourceOperator) op;
- ILogicalOperator source = nts.getDataSourceReference().getValue().getInputs().get(0).getValue();
- if (!visitSet.contains(source)) {
- computeFDsAndEqClassesWithVisitorRec((AbstractLogicalOperator) source, ctx, visitor, visitSet);
- }
- }
- op.accept(visitor, ctx);
- if (AlgebricksConfig.DEBUG) {
- AlgebricksConfig.ALGEBRICKS_LOGGER.fine("--> op. type = " + op.getOperatorTag() + "\n"
- + " equiv. classes = " + ctx.getEquivalenceClassMap(op) + "\n" + " FDs = "
- + ctx.getFDList(op) + "\n");
- }
- }
-
-}
http://git-wip-us.apache.org/repos/asf/incubator-asterixdb-hyracks/blob/9939b48e/algebricks/algebricks-rewriter/src/main/java/org/apache/hyracks/algebricks/rewriter/rules/AbstractDecorrelationRule.java
----------------------------------------------------------------------
diff --git a/algebricks/algebricks-rewriter/src/main/java/org/apache/hyracks/algebricks/rewriter/rules/AbstractDecorrelationRule.java b/algebricks/algebricks-rewriter/src/main/java/org/apache/hyracks/algebricks/rewriter/rules/AbstractDecorrelationRule.java
new file mode 100644
index 0000000..f897791
--- /dev/null
+++ b/algebricks/algebricks-rewriter/src/main/java/org/apache/hyracks/algebricks/rewriter/rules/AbstractDecorrelationRule.java
@@ -0,0 +1,104 @@
+/*
+ * 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.Collection;
+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.Pair;
+import edu.uci.ics.hyracks.algebricks.core.algebra.base.ILogicalExpression;
+import edu.uci.ics.hyracks.algebricks.core.algebra.base.ILogicalOperator;
+import edu.uci.ics.hyracks.algebricks.core.algebra.base.ILogicalPlan;
+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.expressions.VariableReferenceExpression;
+import edu.uci.ics.hyracks.algebricks.core.algebra.operators.logical.AbstractLogicalOperator;
+import edu.uci.ics.hyracks.algebricks.core.algebra.operators.logical.GroupByOperator;
+import edu.uci.ics.hyracks.algebricks.core.algebra.properties.FunctionalDependency;
+import edu.uci.ics.hyracks.algebricks.core.algebra.util.OperatorManipulationUtil;
+import edu.uci.ics.hyracks.algebricks.core.rewriter.base.IAlgebraicRewriteRule;
+import edu.uci.ics.hyracks.algebricks.rewriter.util.PhysicalOptimizationsUtil;
+
+public abstract class AbstractDecorrelationRule implements IAlgebraicRewriteRule {
+
+ @Override
+ public boolean rewritePre(Mutable<ILogicalOperator> opRef, IOptimizationContext context) {
+ return false;
+ }
+
+ protected boolean descOrSelfIsScanOrJoin(AbstractLogicalOperator op2) {
+ LogicalOperatorTag t = op2.getOperatorTag();
+ if (isScanOrJoin(t)) {
+ return true;
+ }
+ if (op2.getInputs().size() != 1) {
+ return false;
+ }
+ AbstractLogicalOperator alo = (AbstractLogicalOperator) op2.getInputs().get(0).getValue();
+ if (descOrSelfIsScanOrJoin(alo)) {
+ return true;
+ }
+ return false;
+ }
+
+ protected boolean isScanOrJoin(LogicalOperatorTag t) {
+ if (t == LogicalOperatorTag.DATASOURCESCAN || t == LogicalOperatorTag.INNERJOIN
+ || t == LogicalOperatorTag.UNNEST || t == LogicalOperatorTag.UNNEST_MAP
+ || t == LogicalOperatorTag.LEFTOUTERJOIN) {
+ return true;
+ }
+ return false;
+ }
+
+ protected Set<LogicalVariable> computeGbyVarsUsingPksOnly(Set<LogicalVariable> varSet, AbstractLogicalOperator op,
+ IOptimizationContext context) throws AlgebricksException {
+ PhysicalOptimizationsUtil.computeFDsAndEquivalenceClasses(op, context);
+ List<FunctionalDependency> fdList = context.getFDList(op);
+ if (fdList == null) {
+ return null;
+ }
+ // check if any of the FDs is a key
+ for (FunctionalDependency fd : fdList) {
+ if (fd.getTail().containsAll(varSet)) {
+ return new HashSet<LogicalVariable>(fd.getHead());
+ }
+ }
+ return null;
+ }
+
+ protected void buildVarExprList(Collection<LogicalVariable> vars, IOptimizationContext context, GroupByOperator g,
+ List<Pair<LogicalVariable, Mutable<ILogicalExpression>>> outVeList) throws AlgebricksException {
+ for (LogicalVariable ov : vars) {
+ LogicalVariable newVar = context.newVar();
+ ILogicalExpression varExpr = new VariableReferenceExpression(newVar);
+ outVeList.add(new Pair<LogicalVariable, Mutable<ILogicalExpression>>(ov,
+ new MutableObject<ILogicalExpression>(varExpr)));
+ for (ILogicalPlan p : g.getNestedPlans()) {
+ for (Mutable<ILogicalOperator> r : p.getRoots()) {
+ OperatorManipulationUtil.substituteVarRec((AbstractLogicalOperator) r.getValue(), ov, newVar, true,
+ context);
+ }
+ }
+ }
+ }
+
+}
http://git-wip-us.apache.org/repos/asf/incubator-asterixdb-hyracks/blob/9939b48e/algebricks/algebricks-rewriter/src/main/java/org/apache/hyracks/algebricks/rewriter/rules/AbstractExtractExprRule.java
----------------------------------------------------------------------
diff --git a/algebricks/algebricks-rewriter/src/main/java/org/apache/hyracks/algebricks/rewriter/rules/AbstractExtractExprRule.java b/algebricks/algebricks-rewriter/src/main/java/org/apache/hyracks/algebricks/rewriter/rules/AbstractExtractExprRule.java
new file mode 100644
index 0000000..882db41
--- /dev/null
+++ b/algebricks/algebricks-rewriter/src/main/java/org/apache/hyracks/algebricks/rewriter/rules/AbstractExtractExprRule.java
@@ -0,0 +1,44 @@
+/*
+ * 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 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.core.algebra.base.ILogicalExpression;
+import edu.uci.ics.hyracks.algebricks.core.algebra.base.ILogicalOperator;
+import edu.uci.ics.hyracks.algebricks.core.algebra.base.IOptimizationContext;
+import edu.uci.ics.hyracks.algebricks.core.algebra.base.LogicalExpressionTag;
+import edu.uci.ics.hyracks.algebricks.core.algebra.base.LogicalVariable;
+import edu.uci.ics.hyracks.algebricks.core.algebra.operators.logical.AssignOperator;
+import edu.uci.ics.hyracks.algebricks.core.rewriter.base.IAlgebraicRewriteRule;
+
+public abstract class AbstractExtractExprRule implements IAlgebraicRewriteRule {
+
+ protected LogicalVariable extractExprIntoAssignOpRef(ILogicalExpression gExpr, Mutable<ILogicalOperator> opRef2,
+ IOptimizationContext context) throws AlgebricksException {
+ LogicalVariable v = context.newVar();
+ AssignOperator a = new AssignOperator(v, new MutableObject<ILogicalExpression>(gExpr));
+ a.getInputs().add(new MutableObject<ILogicalOperator>(opRef2.getValue()));
+ opRef2.setValue(a);
+ if (gExpr.getExpressionTag() == LogicalExpressionTag.CONSTANT) {
+ context.addNotToBeInlinedVar(v);
+ }
+ context.computeAndSetTypeEnvironmentForOperator(a);
+ return v;
+ }
+
+}
http://git-wip-us.apache.org/repos/asf/incubator-asterixdb-hyracks/blob/9939b48e/algebricks/algebricks-rewriter/src/main/java/org/apache/hyracks/algebricks/rewriter/rules/AbstractIntroduceCombinerRule.java
----------------------------------------------------------------------
diff --git a/algebricks/algebricks-rewriter/src/main/java/org/apache/hyracks/algebricks/rewriter/rules/AbstractIntroduceCombinerRule.java b/algebricks/algebricks-rewriter/src/main/java/org/apache/hyracks/algebricks/rewriter/rules/AbstractIntroduceCombinerRule.java
new file mode 100644
index 0000000..67b2d0c
--- /dev/null
+++ b/algebricks/algebricks-rewriter/src/main/java/org/apache/hyracks/algebricks/rewriter/rules/AbstractIntroduceCombinerRule.java
@@ -0,0 +1,158 @@
+/*
+ * 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.HashMap;
+import java.util.List;
+import java.util.Map;
+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.Pair;
+import edu.uci.ics.hyracks.algebricks.core.algebra.base.ILogicalExpression;
+import edu.uci.ics.hyracks.algebricks.core.algebra.base.ILogicalOperator;
+import edu.uci.ics.hyracks.algebricks.core.algebra.base.IOptimizationContext;
+import edu.uci.ics.hyracks.algebricks.core.algebra.base.LogicalVariable;
+import edu.uci.ics.hyracks.algebricks.core.algebra.expressions.AbstractFunctionCallExpression;
+import edu.uci.ics.hyracks.algebricks.core.algebra.expressions.AggregateFunctionCallExpression;
+import edu.uci.ics.hyracks.algebricks.core.algebra.expressions.VariableReferenceExpression;
+import edu.uci.ics.hyracks.algebricks.core.algebra.functions.IFunctionInfo;
+import edu.uci.ics.hyracks.algebricks.core.algebra.operators.logical.AbstractLogicalOperator.ExecutionMode;
+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.rewriter.base.IAlgebraicRewriteRule;
+
+public abstract class AbstractIntroduceCombinerRule implements IAlgebraicRewriteRule {
+
+ @Override
+ public boolean rewritePre(Mutable<ILogicalOperator> opRef, IOptimizationContext context) {
+ return false;
+ }
+
+ /**
+ * Replace the original aggregate functions with their corresponding global aggregate function.
+ */
+ protected void replaceOriginalAggFuncs(Set<SimilarAggregatesInfo> toReplaceSet) {
+ for (SimilarAggregatesInfo sai : toReplaceSet) {
+ for (AggregateExprInfo aei : sai.simAggs) {
+ AbstractFunctionCallExpression afce = (AbstractFunctionCallExpression) aei.aggExprRef.getValue();
+ afce.setFunctionInfo(aei.newFunInfo);
+ afce.getArguments().clear();
+ afce.getArguments().add(new MutableObject<ILogicalExpression>(sai.stepOneResult));
+ }
+ }
+ }
+
+ protected Pair<Boolean, Mutable<ILogicalOperator>> tryToPushAgg(AggregateOperator initAgg,
+ GroupByOperator newGbyOp, Set<SimilarAggregatesInfo> toReplaceSet, IOptimizationContext context)
+ throws AlgebricksException {
+
+ ArrayList<LogicalVariable> pushedVars = new ArrayList<LogicalVariable>();
+ ArrayList<Mutable<ILogicalExpression>> pushedExprs = new ArrayList<Mutable<ILogicalExpression>>();
+
+ List<LogicalVariable> initVars = initAgg.getVariables();
+ List<Mutable<ILogicalExpression>> initExprs = initAgg.getExpressions();
+ int numExprs = initVars.size();
+
+ // First make sure that all agg funcs are two step, otherwise we cannot use local aggs.
+ for (int i = 0; i < numExprs; i++) {
+ AggregateFunctionCallExpression aggFun = (AggregateFunctionCallExpression) initExprs.get(i).getValue();
+ if (!aggFun.isTwoStep()) {
+ return new Pair<Boolean, Mutable<ILogicalOperator>>(false, null);
+ }
+ }
+
+ boolean haveAggToReplace = false;
+ for (int i = 0; i < numExprs; i++) {
+ Mutable<ILogicalExpression> expRef = initExprs.get(i);
+ AggregateFunctionCallExpression aggFun = (AggregateFunctionCallExpression) expRef.getValue();
+ IFunctionInfo fi1 = aggFun.getStepOneAggregate();
+ // Clone the aggregate's args.
+ List<Mutable<ILogicalExpression>> newArgs = new ArrayList<Mutable<ILogicalExpression>>(aggFun
+ .getArguments().size());
+ for (Mutable<ILogicalExpression> er : aggFun.getArguments()) {
+ newArgs.add(new MutableObject<ILogicalExpression>(er.getValue().cloneExpression()));
+ }
+ IFunctionInfo fi2 = aggFun.getStepTwoAggregate();
+
+ SimilarAggregatesInfo inf = new SimilarAggregatesInfo();
+ LogicalVariable newAggVar = context.newVar();
+ pushedVars.add(newAggVar);
+ inf.stepOneResult = new VariableReferenceExpression(newAggVar);
+ inf.simAggs = new ArrayList<AggregateExprInfo>();
+ toReplaceSet.add(inf);
+ AggregateFunctionCallExpression aggLocal = new AggregateFunctionCallExpression(fi1, false, newArgs);
+ pushedExprs.add(new MutableObject<ILogicalExpression>(aggLocal));
+ AggregateExprInfo aei = new AggregateExprInfo();
+ aei.aggExprRef = expRef;
+ aei.newFunInfo = fi2;
+ inf.simAggs.add(aei);
+ haveAggToReplace = true;
+ }
+
+ if (!pushedVars.isEmpty()) {
+ AggregateOperator pushedAgg = new AggregateOperator(pushedVars, pushedExprs);
+ pushedAgg.setExecutionMode(ExecutionMode.LOCAL);
+ // If newGbyOp is null, then we optimizing an aggregate without group by.
+ if (newGbyOp != null) {
+ // Cut and paste nested input pipelines of initAgg to pushedAgg's input
+ Mutable<ILogicalOperator> inputRef = initAgg.getInputs().get(0);
+ Mutable<ILogicalOperator> bottomRef = inputRef;
+ while (bottomRef.getValue().getInputs().size() > 0) {
+ bottomRef = bottomRef.getValue().getInputs().get(0);
+ }
+ ILogicalOperator oldNts = bottomRef.getValue();
+ initAgg.getInputs().clear();
+ initAgg.getInputs().add(new MutableObject<ILogicalOperator>(oldNts));
+
+ // Hook up the nested aggregate op with the outer group by.
+ NestedTupleSourceOperator nts = new NestedTupleSourceOperator(new MutableObject<ILogicalOperator>(
+ newGbyOp));
+ nts.setExecutionMode(ExecutionMode.LOCAL);
+ bottomRef.setValue(nts);
+ pushedAgg.getInputs().add(inputRef);
+ } else {
+ // The local aggregate operator is fed by the input of the original aggregate operator.
+ pushedAgg.getInputs().add(new MutableObject<ILogicalOperator>(initAgg.getInputs().get(0).getValue()));
+ // Reintroduce assign op for the global agg partitioning var.
+ initAgg.getInputs().get(0).setValue(pushedAgg);
+ pushedAgg.setGlobal(false);
+ context.computeAndSetTypeEnvironmentForOperator(pushedAgg);
+ }
+ return new Pair<Boolean, Mutable<ILogicalOperator>>(true, new MutableObject<ILogicalOperator>(pushedAgg));
+ } else {
+ return new Pair<Boolean, Mutable<ILogicalOperator>>(haveAggToReplace, null);
+ }
+ }
+
+ protected class SimilarAggregatesInfo {
+ ILogicalExpression stepOneResult;
+ List<AggregateExprInfo> simAggs;
+ }
+
+ protected class AggregateExprInfo {
+ Mutable<ILogicalExpression> aggExprRef;
+ IFunctionInfo newFunInfo;
+ }
+
+ protected class BookkeepingInfo {
+ Map<GroupByOperator, List<LogicalVariable>> modifyGbyMap = new HashMap<GroupByOperator, List<LogicalVariable>>();
+ }
+}
http://git-wip-us.apache.org/repos/asf/incubator-asterixdb-hyracks/blob/9939b48e/algebricks/algebricks-rewriter/src/main/java/org/apache/hyracks/algebricks/rewriter/rules/AbstractIntroduceGroupByCombinerRule.java
----------------------------------------------------------------------
diff --git a/algebricks/algebricks-rewriter/src/main/java/org/apache/hyracks/algebricks/rewriter/rules/AbstractIntroduceGroupByCombinerRule.java b/algebricks/algebricks-rewriter/src/main/java/org/apache/hyracks/algebricks/rewriter/rules/AbstractIntroduceGroupByCombinerRule.java
new file mode 100644
index 0000000..b60c80d
--- /dev/null
+++ b/algebricks/algebricks-rewriter/src/main/java/org/apache/hyracks/algebricks/rewriter/rules/AbstractIntroduceGroupByCombinerRule.java
@@ -0,0 +1,340 @@
+/*
+ * 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.Iterator;
+import java.util.LinkedList;
+import java.util.List;
+import java.util.Map;
+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;
+import edu.uci.ics.hyracks.algebricks.common.utils.Pair;
+import edu.uci.ics.hyracks.algebricks.core.algebra.base.ILogicalExpression;
+import edu.uci.ics.hyracks.algebricks.core.algebra.base.ILogicalOperator;
+import edu.uci.ics.hyracks.algebricks.core.algebra.base.ILogicalPlan;
+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.base.OperatorAnnotations;
+import edu.uci.ics.hyracks.algebricks.core.algebra.expressions.VariableReferenceExpression;
+import edu.uci.ics.hyracks.algebricks.core.algebra.operators.logical.AbstractLogicalOperator;
+import edu.uci.ics.hyracks.algebricks.core.algebra.operators.logical.AbstractLogicalOperator.ExecutionMode;
+import edu.uci.ics.hyracks.algebricks.core.algebra.operators.logical.AbstractOperatorWithNestedPlans;
+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.visitors.IsomorphismUtilities;
+import edu.uci.ics.hyracks.algebricks.core.algebra.operators.logical.visitors.VariableUtilities;
+import edu.uci.ics.hyracks.algebricks.core.algebra.plan.ALogicalPlanImpl;
+import edu.uci.ics.hyracks.algebricks.core.algebra.util.OperatorPropertiesUtil;
+
+public abstract class AbstractIntroduceGroupByCombinerRule extends AbstractIntroduceCombinerRule {
+
+ @Override
+ public boolean rewritePost(Mutable<ILogicalOperator> opRef, IOptimizationContext context)
+ throws AlgebricksException {
+ AbstractLogicalOperator op = (AbstractLogicalOperator) opRef.getValue();
+ if (context.checkIfInDontApplySet(this, op)) {
+ return false;
+ }
+ if (op.getOperatorTag() != LogicalOperatorTag.GROUP) {
+ return false;
+ }
+ GroupByOperator gbyOp = (GroupByOperator) op;
+ if (gbyOp.getExecutionMode() != ExecutionMode.PARTITIONED) {
+ return false;
+ }
+
+ BookkeepingInfo bi = new BookkeepingInfo();
+ GroupByOperator newGbyOp = opToPush(gbyOp, bi, context);
+ if (newGbyOp == null) {
+ return false;
+ }
+
+ Set<LogicalVariable> newGbyLiveVars = new ListSet<LogicalVariable>();
+ VariableUtilities.getLiveVariables(newGbyOp, newGbyLiveVars);
+ for (Pair<LogicalVariable, Mutable<ILogicalExpression>> p : gbyOp.getDecorList()) {
+ List<LogicalVariable> usedDecorVars = new ArrayList<LogicalVariable>();
+ // p.second.getValue() should always return a VariableReferenceExpression, hence
+ // usedDecorVars should always contain only one variable.
+ p.second.getValue().getUsedVariables(usedDecorVars);
+ if (!newGbyLiveVars.contains(usedDecorVars.get(0))) {
+ // Let the left-hand side of gbyOp's decoration expressions populated through the combiner group-by without
+ // any intermediate assignment.
+ newGbyOp.addDecorExpression(null, p.second.getValue());
+ }
+ }
+ newGbyOp.setExecutionMode(ExecutionMode.LOCAL);
+ Object v = gbyOp.getAnnotations().get(OperatorAnnotations.USE_HASH_GROUP_BY);
+ newGbyOp.getAnnotations().put(OperatorAnnotations.USE_HASH_GROUP_BY, v);
+
+ Object v2 = gbyOp.getAnnotations().get(OperatorAnnotations.USE_EXTERNAL_GROUP_BY);
+ newGbyOp.getAnnotations().put(OperatorAnnotations.USE_EXTERNAL_GROUP_BY, v2);
+
+ List<LogicalVariable> propagatedVars = new LinkedList<LogicalVariable>();
+ VariableUtilities.getProducedVariables(newGbyOp, propagatedVars);
+
+ Set<LogicalVariable> freeVars = new HashSet<LogicalVariable>();
+ OperatorPropertiesUtil.getFreeVariablesInSubplans(gbyOp, freeVars);
+
+ for (LogicalVariable var : freeVars) {
+ if (!propagatedVars.contains(var)) {
+ LogicalVariable newDecorVar = context.newVar();
+ newGbyOp.addDecorExpression(newDecorVar, new VariableReferenceExpression(var));
+ VariableUtilities.substituteVariables(gbyOp.getNestedPlans().get(0).getRoots().get(0).getValue(), var,
+ newDecorVar, context);
+ }
+ }
+
+ Mutable<ILogicalOperator> opRef3 = gbyOp.getInputs().get(0);
+ opRef3.setValue(newGbyOp);
+ typeGby(newGbyOp, context);
+ typeGby(gbyOp, context);
+ context.addToDontApplySet(this, op);
+ return true;
+ }
+
+ private void typeGby(AbstractOperatorWithNestedPlans op, IOptimizationContext context) throws AlgebricksException {
+ for (ILogicalPlan p : op.getNestedPlans()) {
+ OperatorPropertiesUtil.typePlan(p, context);
+ }
+ context.computeAndSetTypeEnvironmentForOperator(op);
+ }
+
+ private GroupByOperator opToPush(GroupByOperator gbyOp, BookkeepingInfo bi, IOptimizationContext context)
+ throws AlgebricksException {
+ // Hook up input to new group-by.
+ Mutable<ILogicalOperator> opRef3 = gbyOp.getInputs().get(0);
+ ILogicalOperator op3 = opRef3.getValue();
+ GroupByOperator newGbyOp = new GroupByOperator();
+ newGbyOp.getInputs().add(new MutableObject<ILogicalOperator>(op3));
+ // Copy annotations.
+ Map<String, Object> annotations = newGbyOp.getAnnotations();
+ annotations.putAll(gbyOp.getAnnotations());
+
+ List<LogicalVariable> gbyVars = gbyOp.getGbyVarList();
+ for (ILogicalPlan p : gbyOp.getNestedPlans()) {
+ Pair<Boolean, ILogicalPlan> bip = tryToPushSubplan(p, gbyOp, newGbyOp, bi, gbyVars, context);
+ if (!bip.first) {
+ // For now, if we cannot push everything, give up.
+ return null;
+ }
+ ILogicalPlan pushedSubplan = bip.second;
+ if (pushedSubplan != null) {
+ newGbyOp.getNestedPlans().add(pushedSubplan);
+ }
+ }
+
+ ArrayList<LogicalVariable> newOpGbyList = new ArrayList<LogicalVariable>();
+ ArrayList<LogicalVariable> replGbyList = new ArrayList<LogicalVariable>();
+ // Find maximal sequence of variable.
+ for (Map.Entry<GroupByOperator, List<LogicalVariable>> e : bi.modifyGbyMap.entrySet()) {
+ List<LogicalVariable> varList = e.getValue();
+ boolean see1 = true;
+ int sz1 = newOpGbyList.size();
+ int i = 0;
+ for (LogicalVariable v : varList) {
+ if (see1) {
+ if (i < sz1) {
+ LogicalVariable v2 = newOpGbyList.get(i);
+ if (v != v2) {
+ // cannot linearize
+ return null;
+ }
+ } else {
+ see1 = false;
+ newOpGbyList.add(v);
+ replGbyList.add(context.newVar());
+ }
+ i++;
+ } else {
+ newOpGbyList.add(v);
+ replGbyList.add(context.newVar());
+ }
+ }
+ }
+ // set the vars in the new op
+ int n = newOpGbyList.size();
+ for (int i = 0; i < n; i++) {
+ newGbyOp.addGbyExpression(replGbyList.get(i), new VariableReferenceExpression(newOpGbyList.get(i)));
+ VariableUtilities.substituteVariables(gbyOp, newOpGbyList.get(i), replGbyList.get(i), false, context);
+ }
+ return newGbyOp;
+ }
+
+ private Pair<Boolean, ILogicalPlan> tryToPushSubplan(ILogicalPlan nestedPlan, GroupByOperator oldGbyOp,
+ GroupByOperator newGbyOp, BookkeepingInfo bi, List<LogicalVariable> gbyVars, IOptimizationContext context)
+ throws AlgebricksException {
+ List<Mutable<ILogicalOperator>> pushedRoots = new ArrayList<Mutable<ILogicalOperator>>();
+ Set<SimilarAggregatesInfo> toReplaceSet = new HashSet<SimilarAggregatesInfo>();
+ for (Mutable<ILogicalOperator> r : nestedPlan.getRoots()) {
+ if (!tryToPushRoot(r, oldGbyOp, newGbyOp, bi, gbyVars, context, pushedRoots, toReplaceSet)) {
+ // For now, if we cannot push everything, give up.
+ return new Pair<Boolean, ILogicalPlan>(false, null);
+ }
+ }
+ if (pushedRoots.isEmpty()) {
+ return new Pair<Boolean, ILogicalPlan>(true, null);
+ } else {
+ // Replaces the aggregation expressions in the original group-by op with new ones.
+ ILogicalPlan newPlan = new ALogicalPlanImpl(pushedRoots);
+ ILogicalPlan plan = fingIdenticalPlan(newGbyOp, newPlan);
+ replaceOriginalAggFuncs(toReplaceSet);
+ if (plan == null) {
+ return new Pair<Boolean, ILogicalPlan>(true, newPlan);
+ } else {
+ // Does not add a nested subplan to newGbyOp if there already exists an isomorphic plan.
+ Set<LogicalVariable> originalVars = new ListSet<LogicalVariable>();
+ Set<LogicalVariable> newVars = new ListSet<LogicalVariable>();
+ for (Mutable<ILogicalOperator> rootRef : pushedRoots) {
+ VariableUtilities.getProducedVariables(rootRef.getValue(), originalVars);
+ }
+ for (Mutable<ILogicalOperator> rootRef : plan.getRoots()) {
+ VariableUtilities.getProducedVariables(rootRef.getValue(), newVars);
+ }
+
+ // Replaces variable exprs referring to the variables produced by newPlan by
+ // those produced by plan.
+ Iterator<LogicalVariable> originalVarIter = originalVars.iterator();
+ Iterator<LogicalVariable> newVarIter = newVars.iterator();
+ while (originalVarIter.hasNext()) {
+ LogicalVariable originalVar = originalVarIter.next();
+ LogicalVariable newVar = newVarIter.next();
+ for (SimilarAggregatesInfo sai : toReplaceSet) {
+ for (AggregateExprInfo aei : sai.simAggs) {
+ ILogicalExpression afce = aei.aggExprRef.getValue();
+ afce.substituteVar(originalVar, newVar);
+ }
+ }
+ }
+ return new Pair<Boolean, ILogicalPlan>(true, null);
+ }
+ }
+ }
+
+ private ILogicalPlan fingIdenticalPlan(GroupByOperator newGbyOp, ILogicalPlan plan) throws AlgebricksException {
+ for (ILogicalPlan nestedPlan : newGbyOp.getNestedPlans()) {
+ if (IsomorphismUtilities.isOperatorIsomorphicPlan(plan, nestedPlan)) {
+ return nestedPlan;
+ }
+ }
+ return null;
+ }
+
+ private boolean tryToPushRoot(Mutable<ILogicalOperator> root, GroupByOperator oldGbyOp, GroupByOperator newGbyOp,
+ BookkeepingInfo bi, List<LogicalVariable> gbyVars, IOptimizationContext context,
+ List<Mutable<ILogicalOperator>> toPushAccumulate, Set<SimilarAggregatesInfo> toReplaceSet)
+ throws AlgebricksException {
+ AbstractLogicalOperator op1 = (AbstractLogicalOperator) root.getValue();
+ if (op1.getOperatorTag() != LogicalOperatorTag.AGGREGATE) {
+ return false;
+ }
+ AbstractLogicalOperator op2 = (AbstractLogicalOperator) op1.getInputs().get(0).getValue();
+ // Finds nested group-by if any.
+ AbstractLogicalOperator op3 = op2;
+ while (op3.getOperatorTag() != LogicalOperatorTag.GROUP && op3.getInputs().size() == 1) {
+ op3 = (AbstractLogicalOperator) op3.getInputs().get(0).getValue();
+ }
+
+ if (op3.getOperatorTag() != LogicalOperatorTag.GROUP) {
+ AggregateOperator initAgg = (AggregateOperator) op1;
+ Pair<Boolean, Mutable<ILogicalOperator>> pOpRef = tryToPushAgg(initAgg, newGbyOp, toReplaceSet, context);
+ if (!pOpRef.first) {
+ return false;
+ }
+ Mutable<ILogicalOperator> opRef = pOpRef.second;
+ if (opRef != null) {
+ toPushAccumulate.add(opRef);
+ }
+ bi.modifyGbyMap.put(oldGbyOp, gbyVars);
+ return true;
+ } else {
+ GroupByOperator nestedGby = (GroupByOperator) op3;
+ List<LogicalVariable> gbyVars2 = nestedGby.getGbyVarList();
+ List<LogicalVariable> concatGbyVars = new ArrayList<LogicalVariable>(gbyVars);
+ concatGbyVars.addAll(gbyVars2);
+ for (ILogicalPlan p : nestedGby.getNestedPlans()) {
+ for (Mutable<ILogicalOperator> r2 : p.getRoots()) {
+ if (!tryToPushRoot(r2, nestedGby, newGbyOp, bi, concatGbyVars, context, toPushAccumulate,
+ toReplaceSet)) {
+ return false;
+ }
+ }
+ }
+
+ /***
+ * Push the nested pipeline which provides the input to the nested group operator into newGbyOp (the combined gby op).
+ * The change is to fix asterixdb issue 782.
+ */
+ Mutable<ILogicalOperator> nestedGbyInputRef = nestedGby.getInputs().get(0);
+ Mutable<ILogicalOperator> startOfPipelineRef = nestedGbyInputRef;
+ if (startOfPipelineRef.getValue().getOperatorTag() == LogicalOperatorTag.NESTEDTUPLESOURCE) {
+ return true;
+ }
+
+ // move down the nested pipeline to find the start of the pipeline right upon the nested-tuple-source
+ boolean hasIsNullFunction = OperatorPropertiesUtil.isNullTest((AbstractLogicalOperator) startOfPipelineRef
+ .getValue());
+ while (startOfPipelineRef.getValue().getInputs().get(0).getValue().getOperatorTag() != LogicalOperatorTag.NESTEDTUPLESOURCE) {
+ startOfPipelineRef = startOfPipelineRef.getValue().getInputs().get(0);
+ hasIsNullFunction = OperatorPropertiesUtil.isNullTest((AbstractLogicalOperator) startOfPipelineRef
+ .getValue());
+ }
+ //keep the old nested-tuple-source
+ Mutable<ILogicalOperator> oldNts = startOfPipelineRef.getValue().getInputs().get(0);
+
+ //move down the nested op in the new gby operator
+ Mutable<ILogicalOperator> newGbyNestedOpRef = toPushAccumulate.get(0);
+ while (newGbyNestedOpRef.getValue().getInputs().get(0).getValue().getOperatorTag() != LogicalOperatorTag.NESTEDTUPLESOURCE) {
+ newGbyNestedOpRef = newGbyNestedOpRef.getValue().getInputs().get(0);
+ }
+
+ //insert the pipeline before nested gby into the new (combiner) gby's nested plan on top of the nested-tuple-source
+ startOfPipelineRef.getValue().getInputs().set(0, newGbyNestedOpRef.getValue().getInputs().get(0));
+ newGbyNestedOpRef.getValue().getInputs().set(0, nestedGbyInputRef);
+
+ //in the old gby operator, remove the nested pipeline since it is already pushed to the combiner gby
+ nestedGby.getInputs().set(0, oldNts);
+ List<LogicalVariable> aggProducedVars = new ArrayList<LogicalVariable>();
+ VariableUtilities.getProducedVariables(toPushAccumulate.get(0).getValue(), aggProducedVars);
+
+ if (hasIsNullFunction && aggProducedVars.size() != 0) {
+ // if the old nested pipeline contains a not-null-check, we need to convert it to a not-system-null-check in the non-local gby
+ processNullTest(context, nestedGby, aggProducedVars);
+ }
+
+ return true;
+ }
+ }
+
+ /**
+ * Deal with the case where the nested plan in the combiner gby operator has a null-test before invoking aggregation functions.
+ *
+ * @param context
+ * The optimization context.
+ * @param nestedGby
+ * The nested gby operator in the global gby operator's subplan.
+ * @param firstAggVar
+ * The first aggregation variable produced by the combiner gby.
+ */
+ protected abstract void processNullTest(IOptimizationContext context, GroupByOperator nestedGby,
+ List<LogicalVariable> aggregateVarsProducedByCombiner);
+}
\ No newline at end of file
http://git-wip-us.apache.org/repos/asf/incubator-asterixdb-hyracks/blob/9939b48e/algebricks/algebricks-rewriter/src/main/java/org/apache/hyracks/algebricks/rewriter/rules/BreakSelectIntoConjunctsRule.java
----------------------------------------------------------------------
diff --git a/algebricks/algebricks-rewriter/src/main/java/org/apache/hyracks/algebricks/rewriter/rules/BreakSelectIntoConjunctsRule.java b/algebricks/algebricks-rewriter/src/main/java/org/apache/hyracks/algebricks/rewriter/rules/BreakSelectIntoConjunctsRule.java
new file mode 100644
index 0000000..53ca903
--- /dev/null
+++ b/algebricks/algebricks-rewriter/src/main/java/org/apache/hyracks/algebricks/rewriter/rules/BreakSelectIntoConjunctsRule.java
@@ -0,0 +1,82 @@
+/*
+ * 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.List;
+
+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.core.algebra.base.ILogicalExpression;
+import edu.uci.ics.hyracks.algebricks.core.algebra.base.ILogicalOperator;
+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.operators.logical.AbstractLogicalOperator;
+import edu.uci.ics.hyracks.algebricks.core.algebra.operators.logical.SelectOperator;
+import edu.uci.ics.hyracks.algebricks.core.rewriter.base.IAlgebraicRewriteRule;
+
+public class BreakSelectIntoConjunctsRule implements IAlgebraicRewriteRule {
+
+ private List<Mutable<ILogicalExpression>> conjs = new ArrayList<Mutable<ILogicalExpression>>();
+
+ @Override
+ public boolean rewritePost(Mutable<ILogicalOperator> opRef, IOptimizationContext context) {
+ return false;
+ }
+
+ @Override
+ public boolean rewritePre(Mutable<ILogicalOperator> opRef, IOptimizationContext context) throws AlgebricksException {
+ AbstractLogicalOperator op = (AbstractLogicalOperator) opRef.getValue();
+ if (op.getOperatorTag() != LogicalOperatorTag.SELECT) {
+ return false;
+ }
+ SelectOperator select = (SelectOperator) op;
+
+ ILogicalExpression cond = select.getCondition().getValue();
+
+ conjs.clear();
+ if (!cond.splitIntoConjuncts(conjs)) {
+ return false;
+ }
+
+ Mutable<ILogicalOperator> childOfSelect = select.getInputs().get(0);
+ boolean fst = true;
+ ILogicalOperator botOp = select;
+ ILogicalExpression firstExpr = null;
+ for (Mutable<ILogicalExpression> eRef : conjs) {
+ ILogicalExpression e = eRef.getValue();
+ if (fst) {
+ fst = false;
+ firstExpr = e;
+ } else {
+ SelectOperator newSelect = new SelectOperator(new MutableObject<ILogicalExpression>(e),
+ select.getRetainNull(), select.getNullPlaceholderVariable());
+ List<Mutable<ILogicalOperator>> botInpList = botOp.getInputs();
+ botInpList.clear();
+ botInpList.add(new MutableObject<ILogicalOperator>(newSelect));
+ context.computeAndSetTypeEnvironmentForOperator(botOp);
+ botOp = newSelect;
+ }
+ }
+ botOp.getInputs().add(childOfSelect);
+ select.getCondition().setValue(firstExpr);
+ context.computeAndSetTypeEnvironmentForOperator(botOp);
+ context.computeAndSetTypeEnvironmentForOperator(select);
+
+ return true;
+ }
+}
http://git-wip-us.apache.org/repos/asf/incubator-asterixdb-hyracks/blob/9939b48e/algebricks/algebricks-rewriter/src/main/java/org/apache/hyracks/algebricks/rewriter/rules/ComplexJoinInferenceRule.java
----------------------------------------------------------------------
diff --git a/algebricks/algebricks-rewriter/src/main/java/org/apache/hyracks/algebricks/rewriter/rules/ComplexJoinInferenceRule.java b/algebricks/algebricks-rewriter/src/main/java/org/apache/hyracks/algebricks/rewriter/rules/ComplexJoinInferenceRule.java
new file mode 100644
index 0000000..73fd966
--- /dev/null
+++ b/algebricks/algebricks-rewriter/src/main/java/org/apache/hyracks/algebricks/rewriter/rules/ComplexJoinInferenceRule.java
@@ -0,0 +1,138 @@
+/*
+ * 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.HashSet;
+
+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.core.algebra.base.ILogicalExpression;
+import edu.uci.ics.hyracks.algebricks.core.algebra.base.ILogicalOperator;
+import edu.uci.ics.hyracks.algebricks.core.algebra.base.ILogicalPlan;
+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.expressions.ConstantExpression;
+import edu.uci.ics.hyracks.algebricks.core.algebra.operators.logical.AbstractBinaryJoinOperator;
+import edu.uci.ics.hyracks.algebricks.core.algebra.operators.logical.AbstractLogicalOperator;
+import edu.uci.ics.hyracks.algebricks.core.algebra.operators.logical.AbstractScanOperator;
+import edu.uci.ics.hyracks.algebricks.core.algebra.operators.logical.InnerJoinOperator;
+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.algebra.util.OperatorPropertiesUtil;
+import edu.uci.ics.hyracks.algebricks.core.rewriter.base.IAlgebraicRewriteRule;
+
+public class ComplexJoinInferenceRule implements IAlgebraicRewriteRule {
+
+ @Override
+ public boolean rewritePost(Mutable<ILogicalOperator> opRef, IOptimizationContext context)
+ throws AlgebricksException {
+ ILogicalOperator op = opRef.getValue();
+ if (!(op instanceof AbstractScanOperator)) {
+ return false;
+ }
+
+ Mutable<ILogicalOperator> opRef2 = op.getInputs().get(0);
+ AbstractLogicalOperator op2 = (AbstractLogicalOperator) opRef2.getValue();
+ if (op2.getOperatorTag() != LogicalOperatorTag.SUBPLAN) {
+ return false;
+ }
+ SubplanOperator subplan = (SubplanOperator) op2;
+
+ Mutable<ILogicalOperator> opRef3 = subplan.getInputs().get(0);
+ AbstractLogicalOperator op3 = (AbstractLogicalOperator) opRef3.getValue();
+
+ if (op3.getOperatorTag() == LogicalOperatorTag.EMPTYTUPLESOURCE
+ || op3.getOperatorTag() == LogicalOperatorTag.NESTEDTUPLESOURCE) {
+ return false;
+ }
+
+ if (subplanHasFreeVariables(subplan)) {
+ return false;
+ }
+
+ HashSet<LogicalVariable> varsUsedInUnnest = new HashSet<LogicalVariable>();
+ VariableUtilities.getUsedVariables(op, varsUsedInUnnest);
+
+ HashSet<LogicalVariable> producedInSubplan = new HashSet<LogicalVariable>();
+ VariableUtilities.getProducedVariables(subplan, producedInSubplan);
+
+ if (!producedInSubplan.containsAll(varsUsedInUnnest)) {
+ return false;
+ }
+
+ ntsToEtsInSubplan(subplan, context);
+ cleanupJoins(subplan);
+ InnerJoinOperator join = new InnerJoinOperator(new MutableObject<ILogicalExpression>(ConstantExpression.TRUE));
+ join.getInputs().add(opRef3);
+ opRef2.setValue(OperatorManipulationUtil.eliminateSingleSubplanOverEts(subplan));
+ join.getInputs().add(new MutableObject<ILogicalOperator>(op));
+ opRef.setValue(join);
+ context.computeAndSetTypeEnvironmentForOperator(join);
+ return true;
+ }
+
+ @Override
+ public boolean rewritePre(Mutable<ILogicalOperator> opRef, IOptimizationContext context) {
+ return false;
+ }
+
+ private static void cleanupJoins(SubplanOperator s) {
+ for (ILogicalPlan p : s.getNestedPlans()) {
+ for (Mutable<ILogicalOperator> r : p.getRoots()) {
+ cleanupJoins(r);
+ }
+ }
+ }
+
+ /** clean up joins that have one input branch that is empty tuple source */
+ private static void cleanupJoins(Mutable<ILogicalOperator> opRef) {
+ if (opRef.getValue() instanceof AbstractBinaryJoinOperator) {
+ for (Mutable<ILogicalOperator> inputRef : opRef.getValue().getInputs()) {
+ if (inputRef.getValue().getOperatorTag() == LogicalOperatorTag.EMPTYTUPLESOURCE) {
+ opRef.getValue().getInputs().remove(inputRef);
+ opRef.setValue(opRef.getValue().getInputs().get(0).getValue());
+ break;
+ }
+ }
+ }
+ for (Mutable<ILogicalOperator> inputRef : opRef.getValue().getInputs()) {
+ cleanupJoins(inputRef);
+ }
+ }
+
+ private static void ntsToEtsInSubplan(SubplanOperator s, IOptimizationContext context) throws AlgebricksException {
+ for (ILogicalPlan p : s.getNestedPlans()) {
+ for (Mutable<ILogicalOperator> r : p.getRoots()) {
+ OperatorManipulationUtil.ntsToEts(r, context);
+ }
+ }
+ }
+
+ private static boolean subplanHasFreeVariables(SubplanOperator s) throws AlgebricksException {
+ for (ILogicalPlan p : s.getNestedPlans()) {
+ for (Mutable<ILogicalOperator> r : p.getRoots()) {
+ if (OperatorPropertiesUtil.hasFreeVariablesInSelfOrDesc((AbstractLogicalOperator) r.getValue())) {
+ return true;
+ }
+ }
+ }
+ return false;
+ }
+
+}
http://git-wip-us.apache.org/repos/asf/incubator-asterixdb-hyracks/blob/9939b48e/algebricks/algebricks-rewriter/src/main/java/org/apache/hyracks/algebricks/rewriter/rules/ComplexUnnestToProductRule.java
----------------------------------------------------------------------
diff --git a/algebricks/algebricks-rewriter/src/main/java/org/apache/hyracks/algebricks/rewriter/rules/ComplexUnnestToProductRule.java b/algebricks/algebricks-rewriter/src/main/java/org/apache/hyracks/algebricks/rewriter/rules/ComplexUnnestToProductRule.java
new file mode 100644
index 0000000..910a8f9
--- /dev/null
+++ b/algebricks/algebricks-rewriter/src/main/java/org/apache/hyracks/algebricks/rewriter/rules/ComplexUnnestToProductRule.java
@@ -0,0 +1,314 @@
+/*
+ * 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 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.core.algebra.base.ILogicalExpression;
+import edu.uci.ics.hyracks.algebricks.core.algebra.base.ILogicalOperator;
+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.expressions.ConstantExpression;
+import edu.uci.ics.hyracks.algebricks.core.algebra.operators.logical.AbstractLogicalOperator;
+import edu.uci.ics.hyracks.algebricks.core.algebra.operators.logical.AbstractOperatorWithNestedPlans;
+import edu.uci.ics.hyracks.algebricks.core.algebra.operators.logical.EmptyTupleSourceOperator;
+import edu.uci.ics.hyracks.algebricks.core.algebra.operators.logical.InnerJoinOperator;
+import edu.uci.ics.hyracks.algebricks.core.algebra.operators.logical.visitors.VariableUtilities;
+import edu.uci.ics.hyracks.algebricks.core.rewriter.base.IAlgebraicRewriteRule;
+
+/**
+ * Complex rewrite rule for producing joins from unnests.
+ * This rule is limited to creating left-deep trees.
+ */
+public class ComplexUnnestToProductRule implements IAlgebraicRewriteRule {
+
+ @Override
+ public boolean rewritePre(Mutable<ILogicalOperator> opRef, IOptimizationContext context) {
+ return false;
+ }
+
+ @Override
+ public boolean rewritePost(Mutable<ILogicalOperator> opRef, IOptimizationContext context)
+ throws AlgebricksException {
+ AbstractLogicalOperator op = (AbstractLogicalOperator) opRef.getValue();
+ if (op.getOperatorTag() != LogicalOperatorTag.DATASOURCESCAN
+ && op.getOperatorTag() != LogicalOperatorTag.UNNEST) {
+ return false;
+ }
+
+ //stop rewriting if the operators originates from a nested tuple source
+ if (insideSubplan(opRef)) {
+ return false;
+ }
+
+ // We may pull selects above the join we create in order to eliminate possible dependencies between
+ // the outer and inner input plans of the join.
+ List<ILogicalOperator> topSelects = new ArrayList<ILogicalOperator>();
+
+ // Keep track of the operators and used variables participating in the inner input plan.
+ HashSet<LogicalVariable> innerUsedVars = new HashSet<LogicalVariable>();
+ List<ILogicalOperator> innerOps = new ArrayList<ILogicalOperator>();
+ HashSet<LogicalVariable> outerUsedVars = new HashSet<LogicalVariable>();
+ List<ILogicalOperator> outerOps = new ArrayList<ILogicalOperator>();
+ innerOps.add(op);
+ VariableUtilities.getUsedVariables(op, innerUsedVars);
+
+ Mutable<ILogicalOperator> opRef2 = op.getInputs().get(0);
+ AbstractLogicalOperator op2 = (AbstractLogicalOperator) opRef2.getValue();
+
+ // Find an unnest or join and partition the plan between the first unnest and that operator into independent parts.
+ if (!findPlanPartition(op2, innerUsedVars, outerUsedVars, innerOps, outerOps, topSelects, false)) {
+ // We could not find an unnest or join.
+ return false;
+ }
+ // The last operator must be an unnest or join.
+ AbstractLogicalOperator unnestOrJoin = (AbstractLogicalOperator) outerOps.get(outerOps.size() - 1);
+
+ ILogicalOperator outerRoot = null;
+ ILogicalOperator innerRoot = null;
+ EmptyTupleSourceOperator ets = new EmptyTupleSourceOperator();
+ // If we found a join, simply use it as the outer root.
+ if (unnestOrJoin.getOperatorTag() != LogicalOperatorTag.INNERJOIN
+ && unnestOrJoin.getOperatorTag() != LogicalOperatorTag.LEFTOUTERJOIN) {
+ // We've found a second unnest. First, sanity check that the unnest does not produce any vars that are used by the plan above (until the first unnest).
+ List<LogicalVariable> producedVars = new ArrayList<LogicalVariable>();
+ VariableUtilities.getProducedVariables(unnestOrJoin, producedVars);
+ for (LogicalVariable producedVar : producedVars) {
+ if (innerUsedVars.contains(producedVar)) {
+ return false;
+ }
+ }
+ // Continue finding a partitioning of the plan such that the inner and outer partitions are independent, in order to feed a join.
+ // Now, we look below the second unnest or join.
+ VariableUtilities.getUsedVariables(unnestOrJoin, outerUsedVars);
+ AbstractLogicalOperator unnestChild = (AbstractLogicalOperator) unnestOrJoin.getInputs().get(0).getValue();
+ if (!findPlanPartition(unnestChild, innerUsedVars, outerUsedVars, innerOps, outerOps, topSelects, true)) {
+ // We could not find a suitable partitioning.
+ return false;
+ }
+ }
+ innerRoot = buildOperatorChain(innerOps, ets, context);
+ context.computeAndSetTypeEnvironmentForOperator(innerRoot);
+ outerRoot = buildOperatorChain(outerOps, null, context);
+ context.computeAndSetTypeEnvironmentForOperator(outerRoot);
+
+ InnerJoinOperator product = new InnerJoinOperator(
+ new MutableObject<ILogicalExpression>(ConstantExpression.TRUE));
+ // Outer branch.
+ product.getInputs().add(new MutableObject<ILogicalOperator>(outerRoot));
+ // Inner branch.
+ product.getInputs().add(new MutableObject<ILogicalOperator>(innerRoot));
+ context.computeAndSetTypeEnvironmentForOperator(product);
+ // Put the selects on top of the join.
+ ILogicalOperator topOp = product;
+ if (!topSelects.isEmpty()) {
+ topOp = buildOperatorChain(topSelects, product, context);
+ }
+ // Plug the selects + product in the plan.
+ opRef.setValue(topOp);
+ context.computeAndSetTypeEnvironmentForOperator(topOp);
+ return true;
+ }
+
+ private ILogicalOperator buildOperatorChain(List<ILogicalOperator> ops, ILogicalOperator bottomOp,
+ IOptimizationContext context) throws AlgebricksException {
+ ILogicalOperator root = ops.get(0);
+ ILogicalOperator prevOp = root;
+ for (int i = 1; i < ops.size(); i++) {
+ ILogicalOperator inputOp = ops.get(i);
+ prevOp.getInputs().clear();
+ prevOp.getInputs().add(new MutableObject<ILogicalOperator>(inputOp));
+ prevOp = inputOp;
+ }
+ if (bottomOp != null) {
+ context.computeAndSetTypeEnvironmentForOperator(bottomOp);
+ prevOp.getInputs().clear();
+ prevOp.getInputs().add(new MutableObject<ILogicalOperator>(bottomOp));
+ }
+ return root;
+ }
+
+ private boolean findPlanPartition(AbstractLogicalOperator op, HashSet<LogicalVariable> innerUsedVars,
+ HashSet<LogicalVariable> outerUsedVars, List<ILogicalOperator> innerOps, List<ILogicalOperator> outerOps,
+ List<ILogicalOperator> topSelects, boolean belowSecondUnnest) throws AlgebricksException {
+ if (belowSecondUnnest && innerUsedVars.isEmpty()) {
+ // Trivially joinable.
+ return true;
+ }
+ if (!belowSecondUnnest) {
+ // Bail on the following operators.
+ switch (op.getOperatorTag()) {
+ case AGGREGATE:
+ case SUBPLAN:
+ case GROUP:
+ case UNNEST_MAP:
+ return false;
+ }
+ }
+ switch (op.getOperatorTag()) {
+ case UNNEST:
+ case DATASOURCESCAN: {
+ // We may have reached this state by descending through a subplan.
+ outerOps.add(op);
+ return true;
+ }
+ case INNERJOIN:
+ case LEFTOUTERJOIN: {
+ // Make sure that no variables that are live under this join are needed by the inner.
+ List<LogicalVariable> liveVars = new ArrayList<LogicalVariable>();
+ VariableUtilities.getLiveVariables(op, liveVars);
+ for (LogicalVariable liveVar : liveVars) {
+ if (innerUsedVars.contains(liveVar)) {
+ return false;
+ }
+ }
+ outerOps.add(op);
+ return true;
+ }
+ case SELECT: {
+ // Remember this select to pulling it above the join.
+ if (innerUsedVars.isEmpty()) {
+ outerOps.add(op);
+ } else {
+ topSelects.add(op);
+ }
+ break;
+ }
+ case PROJECT: {
+ // Throw away projects from the plan since we are pulling selects up.
+ break;
+ }
+ case EMPTYTUPLESOURCE:
+ case NESTEDTUPLESOURCE: {
+ if (belowSecondUnnest) {
+ // We have successfully partitioned the plan into independent parts to be plugged into the join.
+ return true;
+ } else {
+ // We could not find a second unnest or a join.
+ return false;
+ }
+ }
+ default: {
+ // The inner is trivially independent.
+ if (!belowSecondUnnest && innerUsedVars.isEmpty()) {
+ outerOps.add(op);
+ break;
+ }
+
+ // Examine produced vars to determine which partition uses them.
+ List<LogicalVariable> producedVars = new ArrayList<LogicalVariable>();
+ VariableUtilities.getProducedVariables(op, producedVars);
+ int outerMatches = 0;
+ int innerMatches = 0;
+ for (LogicalVariable producedVar : producedVars) {
+ if (outerUsedVars.contains(producedVar)) {
+ outerMatches++;
+ }
+ if (innerUsedVars.contains(producedVar)) {
+ innerMatches++;
+ }
+ }
+
+ HashSet<LogicalVariable> targetUsedVars = null;
+ if (outerMatches == producedVars.size() && !producedVars.isEmpty()) {
+ // All produced vars used by outer partition.
+ outerOps.add(op);
+ targetUsedVars = outerUsedVars;
+ }
+ if (innerMatches == producedVars.size() && !producedVars.isEmpty()) {
+ // All produced vars used by inner partition.
+ innerOps.add(op);
+ targetUsedVars = innerUsedVars;
+ }
+ if (innerMatches == 0 && outerMatches == 0) {
+ // Op produces variables that are not used in the part of the plan we've seen (or it doesn't produce any vars).
+ // Try to figure out where it belongs by analyzing the used variables.
+ List<LogicalVariable> usedVars = new ArrayList<LogicalVariable>();
+ VariableUtilities.getUsedVariables(op, usedVars);
+ for (LogicalVariable usedVar : usedVars) {
+ boolean canBreak = false;
+ if (outerUsedVars.contains(usedVar)) {
+ outerOps.add(op);
+ targetUsedVars = outerUsedVars;
+ canBreak = true;
+ }
+ if (innerUsedVars.contains(usedVar)) {
+ innerOps.add(op);
+ targetUsedVars = innerUsedVars;
+ canBreak = true;
+ }
+ if (canBreak) {
+ break;
+ }
+ }
+ // TODO: For now we bail here, but we could remember such ops and determine their target partition at a later point.
+ if (targetUsedVars == null) {
+ return false;
+ }
+ } else if (innerMatches != 0 && outerMatches != 0) {
+ // The current operator produces variables that are used by both partitions, so the inner and outer are not independent and, therefore, we cannot create a join.
+ // TODO: We may still be able to split the operator to create a viable partitioning.
+ return false;
+ }
+ // Update used variables of partition that op belongs to.
+ if (op.hasNestedPlans() && op.getOperatorTag() != LogicalOperatorTag.SUBPLAN) {
+ AbstractOperatorWithNestedPlans opWithNestedPlans = (AbstractOperatorWithNestedPlans) op;
+ opWithNestedPlans.getUsedVariablesExceptNestedPlans(targetUsedVars);
+ } else {
+ VariableUtilities.getUsedVariables(op, targetUsedVars);
+ }
+ break;
+ }
+ }
+ if (!op.hasInputs()) {
+ if (!belowSecondUnnest) {
+ // We could not find a second unnest or a join.
+ return false;
+ } else {
+ // We have successfully partitioned the plan into independent parts to be plugged into the join.
+ return true;
+ }
+ }
+ return findPlanPartition((AbstractLogicalOperator) op.getInputs().get(0).getValue(), innerUsedVars,
+ outerUsedVars, innerOps, outerOps, topSelects, belowSecondUnnest);
+ }
+
+ /**
+ * check whether the operator is inside a sub-plan
+ *
+ * @param nestedRootRef
+ * @return true-if it is; false otherwise.
+ */
+ private boolean insideSubplan(Mutable<ILogicalOperator> nestedRootRef) {
+ AbstractLogicalOperator nestedRoot = (AbstractLogicalOperator) nestedRootRef.getValue();
+ if (nestedRoot.getOperatorTag() == LogicalOperatorTag.NESTEDTUPLESOURCE) {
+ return true;
+ }
+ List<Mutable<ILogicalOperator>> inputs = nestedRoot.getInputs();
+ for (Mutable<ILogicalOperator> input : inputs) {
+ if (insideSubplan(input)) {
+ return true;
+ }
+ }
+ return false;
+ }
+}
http://git-wip-us.apache.org/repos/asf/incubator-asterixdb-hyracks/blob/9939b48e/algebricks/algebricks-rewriter/src/main/java/org/apache/hyracks/algebricks/rewriter/rules/ConsolidateAssignsRule.java
----------------------------------------------------------------------
diff --git a/algebricks/algebricks-rewriter/src/main/java/org/apache/hyracks/algebricks/rewriter/rules/ConsolidateAssignsRule.java b/algebricks/algebricks-rewriter/src/main/java/org/apache/hyracks/algebricks/rewriter/rules/ConsolidateAssignsRule.java
new file mode 100644
index 0000000..4da332c
--- /dev/null
+++ b/algebricks/algebricks-rewriter/src/main/java/org/apache/hyracks/algebricks/rewriter/rules/ConsolidateAssignsRule.java
@@ -0,0 +1,73 @@
+/*
+ * 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.HashSet;
+import java.util.List;
+
+import org.apache.commons.lang3.mutable.Mutable;
+
+import edu.uci.ics.hyracks.algebricks.common.exceptions.AlgebricksException;
+import edu.uci.ics.hyracks.algebricks.core.algebra.base.ILogicalOperator;
+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.AssignOperator;
+import edu.uci.ics.hyracks.algebricks.core.algebra.operators.logical.visitors.VariableUtilities;
+import edu.uci.ics.hyracks.algebricks.core.rewriter.base.IAlgebraicRewriteRule;
+
+public class ConsolidateAssignsRule implements IAlgebraicRewriteRule {
+
+ @Override
+ public boolean rewritePre(Mutable<ILogicalOperator> opRef, IOptimizationContext context) {
+ return false;
+ }
+
+ @Override
+ public boolean rewritePost(Mutable<ILogicalOperator> opRef, IOptimizationContext context)
+ throws AlgebricksException {
+ AbstractLogicalOperator op = (AbstractLogicalOperator) opRef.getValue();
+ if (op.getOperatorTag() != LogicalOperatorTag.ASSIGN) {
+ return false;
+ }
+ AssignOperator assign1 = (AssignOperator) op;
+
+ AbstractLogicalOperator op2 = (AbstractLogicalOperator) assign1.getInputs().get(0).getValue();
+ if (op2.getOperatorTag() != LogicalOperatorTag.ASSIGN) {
+ return false;
+ }
+ AssignOperator assign2 = (AssignOperator) op2;
+
+ HashSet<LogicalVariable> used1 = new HashSet<LogicalVariable>();
+ VariableUtilities.getUsedVariables(assign1, used1);
+ for (LogicalVariable v2 : assign2.getVariables()) {
+ if (used1.contains(v2)) {
+ return false;
+ }
+ }
+
+ assign1.getVariables().addAll(assign2.getVariables());
+ assign1.getExpressions().addAll(assign2.getExpressions());
+
+ Mutable<ILogicalOperator> botOpRef = assign2.getInputs().get(0);
+ List<Mutable<ILogicalOperator>> asgnInpList = assign1.getInputs();
+ asgnInpList.clear();
+ asgnInpList.add(botOpRef);
+ context.computeAndSetTypeEnvironmentForOperator(assign1);
+ return true;
+ }
+
+}
http://git-wip-us.apache.org/repos/asf/incubator-asterixdb-hyracks/blob/9939b48e/algebricks/algebricks-rewriter/src/main/java/org/apache/hyracks/algebricks/rewriter/rules/ConsolidateSelectsRule.java
----------------------------------------------------------------------
diff --git a/algebricks/algebricks-rewriter/src/main/java/org/apache/hyracks/algebricks/rewriter/rules/ConsolidateSelectsRule.java b/algebricks/algebricks-rewriter/src/main/java/org/apache/hyracks/algebricks/rewriter/rules/ConsolidateSelectsRule.java
new file mode 100644
index 0000000..e57bd3c
--- /dev/null
+++ b/algebricks/algebricks-rewriter/src/main/java/org/apache/hyracks/algebricks/rewriter/rules/ConsolidateSelectsRule.java
@@ -0,0 +1,109 @@
+/*
+ * 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 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.core.algebra.base.ILogicalExpression;
+import edu.uci.ics.hyracks.algebricks.core.algebra.base.ILogicalOperator;
+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.expressions.AbstractFunctionCallExpression;
+import edu.uci.ics.hyracks.algebricks.core.algebra.expressions.ScalarFunctionCallExpression;
+import edu.uci.ics.hyracks.algebricks.core.algebra.functions.AlgebricksBuiltinFunctions;
+import edu.uci.ics.hyracks.algebricks.core.algebra.functions.IFunctionInfo;
+import edu.uci.ics.hyracks.algebricks.core.algebra.operators.logical.AbstractLogicalOperator;
+import edu.uci.ics.hyracks.algebricks.core.algebra.operators.logical.SelectOperator;
+import edu.uci.ics.hyracks.algebricks.core.rewriter.base.IAlgebraicRewriteRule;
+
+/**
+ * Matches the following operator pattern:
+ * (select) <-- ((assign)* <-- (select)*)+
+ *
+ * Consolidates the selects to:
+ * (select) <-- (assign)*
+ *
+ */
+public class ConsolidateSelectsRule implements IAlgebraicRewriteRule {
+
+ @Override
+ public boolean rewritePost(Mutable<ILogicalOperator> opRef, IOptimizationContext context) {
+ return false;
+ }
+
+ @Override
+ public boolean rewritePre(Mutable<ILogicalOperator> opRef, IOptimizationContext context) throws AlgebricksException {
+ AbstractLogicalOperator op = (AbstractLogicalOperator) opRef.getValue();
+ if (op.getOperatorTag() != LogicalOperatorTag.SELECT) {
+ return false;
+ }
+ SelectOperator firstSelect = (SelectOperator) op;
+
+ IFunctionInfo andFn = context.getMetadataProvider().lookupFunction(AlgebricksBuiltinFunctions.AND);
+ // New conjuncts for consolidated select.
+ AbstractFunctionCallExpression conj = null;
+ AbstractLogicalOperator topMostOp = null;
+ AbstractLogicalOperator selectParent = null;
+ AbstractLogicalOperator nextSelect = firstSelect;
+ do {
+ // Skip through assigns.
+ do {
+ selectParent = nextSelect;
+ nextSelect = (AbstractLogicalOperator) selectParent.getInputs().get(0).getValue();
+ } while (nextSelect.getOperatorTag() == LogicalOperatorTag.ASSIGN);
+ // Stop if the child op is not a select.
+ if (nextSelect.getOperatorTag() != LogicalOperatorTag.SELECT) {
+ break;
+ }
+ // Remember the top-most op that we are not removing.
+ topMostOp = selectParent;
+
+ // Initialize the new conjuncts, if necessary.
+ if (conj == null) {
+ conj = new ScalarFunctionCallExpression(andFn);
+ // Add the first select's condition.
+ conj.getArguments().add(new MutableObject<ILogicalExpression>(firstSelect.getCondition().getValue()));
+ }
+
+ // Consolidate all following selects.
+ do {
+ // Add the condition nextSelect to the new list of conjuncts.
+ conj.getArguments().add(((SelectOperator) nextSelect).getCondition());
+ selectParent = nextSelect;
+ nextSelect = (AbstractLogicalOperator) nextSelect.getInputs().get(0).getValue();
+ } while (nextSelect.getOperatorTag() == LogicalOperatorTag.SELECT);
+
+ // Hook up the input of the top-most remaining op if necessary.
+ if (topMostOp.getOperatorTag() == LogicalOperatorTag.ASSIGN || topMostOp == firstSelect) {
+ topMostOp.getInputs().set(0, selectParent.getInputs().get(0));
+ }
+
+ // Prepare for next iteration.
+ nextSelect = selectParent;
+ } while (true);
+
+ // Did we consolidate any selects?
+ if (conj == null) {
+ return false;
+ }
+
+ // Set the new conjuncts.
+ firstSelect.getCondition().setValue(conj);
+ context.computeAndSetTypeEnvironmentForOperator(firstSelect);
+ return true;
+ }
+}