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:19 UTC
[06/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/org/apache/hyracks/algebricks/rewriter/rules/PullSelectOutOfEqJoin.java
----------------------------------------------------------------------
diff --git a/algebricks/algebricks-rewriter/src/main/java/org/apache/hyracks/algebricks/rewriter/rules/PullSelectOutOfEqJoin.java b/algebricks/algebricks-rewriter/src/main/java/org/apache/hyracks/algebricks/rewriter/rules/PullSelectOutOfEqJoin.java
new file mode 100644
index 0000000..b268e77
--- /dev/null
+++ b/algebricks/algebricks-rewriter/src/main/java/org/apache/hyracks/algebricks/rewriter/rules/PullSelectOutOfEqJoin.java
@@ -0,0 +1,114 @@
+/*
+ * 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.LogicalExpressionTag;
+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.FunctionIdentifier;
+import edu.uci.ics.hyracks.algebricks.core.algebra.functions.IFunctionInfo;
+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.SelectOperator;
+import edu.uci.ics.hyracks.algebricks.core.rewriter.base.IAlgebraicRewriteRule;
+
+public class PullSelectOutOfEqJoin implements IAlgebraicRewriteRule {
+
+ @Override
+ public boolean rewritePre(Mutable<ILogicalOperator> opRef, IOptimizationContext context) throws AlgebricksException {
+ return false;
+ }
+
+ @Override
+ public boolean rewritePost(Mutable<ILogicalOperator> opRef, IOptimizationContext context)
+ throws AlgebricksException {
+ AbstractLogicalOperator op = (AbstractLogicalOperator) opRef.getValue();
+
+ if (op.getOperatorTag() != LogicalOperatorTag.INNERJOIN) {
+ return false;
+ }
+ AbstractBinaryJoinOperator join = (AbstractBinaryJoinOperator) op;
+
+ ILogicalExpression expr = join.getCondition().getValue();
+ if (expr.getExpressionTag() != LogicalExpressionTag.FUNCTION_CALL) {
+ return false;
+ }
+ AbstractFunctionCallExpression fexp = (AbstractFunctionCallExpression) expr;
+ FunctionIdentifier fi = fexp.getFunctionIdentifier();
+ if (!fi.equals(AlgebricksBuiltinFunctions.AND)) {
+ return false;
+ }
+ List<Mutable<ILogicalExpression>> eqVarVarComps = new ArrayList<Mutable<ILogicalExpression>>();
+ List<Mutable<ILogicalExpression>> otherPredicates = new ArrayList<Mutable<ILogicalExpression>>();
+ for (Mutable<ILogicalExpression> arg : fexp.getArguments()) {
+ if (isEqVarVar(arg.getValue())) {
+ eqVarVarComps.add(arg);
+ } else {
+ otherPredicates.add(arg);
+ }
+ }
+ if (eqVarVarComps.isEmpty() || otherPredicates.isEmpty()) {
+ return false;
+ }
+ // pull up
+ ILogicalExpression pulledCond = makeCondition(otherPredicates, context);
+ SelectOperator select = new SelectOperator(new MutableObject<ILogicalExpression>(pulledCond), false, null);
+ ILogicalExpression newJoinCond = makeCondition(eqVarVarComps, context);
+ join.getCondition().setValue(newJoinCond);
+ select.getInputs().add(new MutableObject<ILogicalOperator>(join));
+ opRef.setValue(select);
+ context.computeAndSetTypeEnvironmentForOperator(select);
+ return true;
+ }
+
+ private ILogicalExpression makeCondition(List<Mutable<ILogicalExpression>> predList, IOptimizationContext context) {
+ if (predList.size() > 1) {
+ IFunctionInfo finfo = context.getMetadataProvider().lookupFunction(AlgebricksBuiltinFunctions.AND);
+ return new ScalarFunctionCallExpression(finfo, predList);
+ } else {
+ return predList.get(0).getValue();
+ }
+ }
+
+ private boolean isEqVarVar(ILogicalExpression expr) {
+ if (expr.getExpressionTag() != LogicalExpressionTag.FUNCTION_CALL) {
+ return false;
+ }
+ AbstractFunctionCallExpression f = (AbstractFunctionCallExpression) expr;
+ if (!f.getFunctionIdentifier().equals(AlgebricksBuiltinFunctions.EQ)) {
+ return false;
+ }
+ ILogicalExpression e1 = f.getArguments().get(0).getValue();
+ if (e1.getExpressionTag() != LogicalExpressionTag.VARIABLE) {
+ return false;
+ } else {
+ ILogicalExpression e2 = f.getArguments().get(1).getValue();
+ return e2.getExpressionTag() == LogicalExpressionTag.VARIABLE;
+ }
+ }
+
+}
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/PushAssignBelowUnionAllRule.java
----------------------------------------------------------------------
diff --git a/algebricks/algebricks-rewriter/src/main/java/org/apache/hyracks/algebricks/rewriter/rules/PushAssignBelowUnionAllRule.java b/algebricks/algebricks-rewriter/src/main/java/org/apache/hyracks/algebricks/rewriter/rules/PushAssignBelowUnionAllRule.java
new file mode 100644
index 0000000..418ee36
--- /dev/null
+++ b/algebricks/algebricks-rewriter/src/main/java/org/apache/hyracks/algebricks/rewriter/rules/PushAssignBelowUnionAllRule.java
@@ -0,0 +1,165 @@
+/*
+ * 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.Triple;
+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.operators.logical.AbstractLogicalOperator;
+import edu.uci.ics.hyracks.algebricks.core.algebra.operators.logical.AssignOperator;
+import edu.uci.ics.hyracks.algebricks.core.algebra.operators.logical.UnionAllOperator;
+import edu.uci.ics.hyracks.algebricks.core.algebra.operators.logical.visitors.VariableUtilities;
+import edu.uci.ics.hyracks.algebricks.core.rewriter.base.IAlgebraicRewriteRule;
+
+/**
+ * Pushes an AssignOperator below a UnionAll operator by creating an new AssignOperator below each of
+ * the UnionAllOperator's branches with appropriate variable replacements.
+ * This rule can help to enable other rules that are difficult to fire across a UnionAllOperator,
+ * for example, eliminating common sub-expressions.
+ * Example:
+ * Before plan:
+ * ...
+ * assign [$$20, $$21] <- [funcA($$3), funcB($$6)]
+ * union ($$1, $$2, $$3) ($$4, $$5, $$6)
+ * union_branch_0
+ * ...
+ * union_branch_1
+ * ...
+ * After plan:
+ * ...
+ * union ($$1, $$2, $$3) ($$4, $$5, $$6) ($$22, $$24, $$20) ($$23, $$25, $$21)
+ * assign [$$22, $$23] <- [funcA($$1), funcB($$4)]
+ * union_branch_0
+ * ...
+ * assign [$$24, $$25] <- [funcA($$2), funcB($$5)]
+ * union_branch_1
+ * ...
+ */
+public class PushAssignBelowUnionAllRule implements IAlgebraicRewriteRule {
+
+ @Override
+ public boolean rewritePre(Mutable<ILogicalOperator> opRef, IOptimizationContext context) throws AlgebricksException {
+ return false;
+ }
+
+ @Override
+ public boolean rewritePost(Mutable<ILogicalOperator> opRef, IOptimizationContext context)
+ throws AlgebricksException {
+ AbstractLogicalOperator op = (AbstractLogicalOperator) opRef.getValue();
+ if (!op.hasInputs()) {
+ return false;
+ }
+
+ boolean modified = false;
+ for (int i = 0; i < op.getInputs().size(); i++) {
+ AbstractLogicalOperator childOp = (AbstractLogicalOperator) op.getInputs().get(i).getValue();
+ if (childOp.getOperatorTag() != LogicalOperatorTag.ASSIGN) {
+ continue;
+ }
+ AssignOperator assignOp = (AssignOperator) childOp;
+ for (Mutable<ILogicalExpression> expr : assignOp.getExpressions()) {
+ if (!expr.getValue().isFunctional()) {
+ return false;
+ }
+ }
+
+ AbstractLogicalOperator childOfChildOp = (AbstractLogicalOperator) assignOp.getInputs().get(0).getValue();
+ if (childOfChildOp.getOperatorTag() != LogicalOperatorTag.UNIONALL) {
+ continue;
+ }
+ UnionAllOperator unionOp = (UnionAllOperator) childOfChildOp;
+
+ Set<LogicalVariable> assignUsedVars = new HashSet<LogicalVariable>();
+ VariableUtilities.getUsedVariables(assignOp, assignUsedVars);
+
+ List<LogicalVariable> assignVars = assignOp.getVariables();
+
+ AssignOperator[] newAssignOps = new AssignOperator[2];
+ for (int j = 0; j < unionOp.getInputs().size(); j++) {
+ newAssignOps[j] = createAssignBelowUnionAllBranch(unionOp, j, assignOp, assignUsedVars, context);
+ }
+ // Add original assign variables to the union variable mappings.
+ for (int j = 0; j < assignVars.size(); j++) {
+ LogicalVariable first = newAssignOps[0].getVariables().get(j);
+ LogicalVariable second = newAssignOps[1].getVariables().get(j);
+ Triple<LogicalVariable, LogicalVariable, LogicalVariable> varMapping = new Triple<LogicalVariable, LogicalVariable, LogicalVariable>(
+ first, second, assignVars.get(j));
+ unionOp.getVariableMappings().add(varMapping);
+ }
+ context.computeAndSetTypeEnvironmentForOperator(unionOp);
+
+ // Remove original assign operator.
+ op.getInputs().set(i, assignOp.getInputs().get(0));
+ context.computeAndSetTypeEnvironmentForOperator(op);
+ modified = true;
+ }
+
+ return modified;
+ }
+
+ private AssignOperator createAssignBelowUnionAllBranch(UnionAllOperator unionOp, int inputIndex,
+ AssignOperator originalAssignOp, Set<LogicalVariable> assignUsedVars, IOptimizationContext context)
+ throws AlgebricksException {
+ AssignOperator newAssignOp = cloneAssignOperator(originalAssignOp, context);
+ newAssignOp.getInputs()
+ .add(new MutableObject<ILogicalOperator>(unionOp.getInputs().get(inputIndex).getValue()));
+ context.computeAndSetTypeEnvironmentForOperator(newAssignOp);
+ unionOp.getInputs().get(inputIndex).setValue(newAssignOp);
+ int numVarMappings = unionOp.getVariableMappings().size();
+ for (int i = 0; i < numVarMappings; i++) {
+ Triple<LogicalVariable, LogicalVariable, LogicalVariable> varMapping = unionOp.getVariableMappings().get(i);
+ if (assignUsedVars.contains(varMapping.third)) {
+ LogicalVariable replacementVar;
+ if (inputIndex == 0) {
+ replacementVar = varMapping.first;
+ } else {
+ replacementVar = varMapping.second;
+ }
+ VariableUtilities.substituteVariables(newAssignOp, varMapping.third, replacementVar, context);
+ }
+ }
+ return newAssignOp;
+ }
+
+ /**
+ * Clones the given assign operator changing the returned variables to be new ones.
+ * Also, leaves the inputs of the clone clear.
+ */
+ private AssignOperator cloneAssignOperator(AssignOperator assignOp, IOptimizationContext context) {
+ List<LogicalVariable> vars = new ArrayList<LogicalVariable>();
+ List<Mutable<ILogicalExpression>> exprs = new ArrayList<Mutable<ILogicalExpression>>();
+ int numVars = assignOp.getVariables().size();
+ for (int i = 0; i < numVars; i++) {
+ vars.add(context.newVar());
+ exprs.add(new MutableObject<ILogicalExpression>(assignOp.getExpressions().get(i).getValue()
+ .cloneExpression()));
+ }
+ AssignOperator assignCloneOp = new AssignOperator(vars, exprs);
+ assignCloneOp.setExecutionMode(assignOp.getExecutionMode());
+ return assignCloneOp;
+ }
+}
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/PushAssignDownThroughProductRule.java
----------------------------------------------------------------------
diff --git a/algebricks/algebricks-rewriter/src/main/java/org/apache/hyracks/algebricks/rewriter/rules/PushAssignDownThroughProductRule.java b/algebricks/algebricks-rewriter/src/main/java/org/apache/hyracks/algebricks/rewriter/rules/PushAssignDownThroughProductRule.java
new file mode 100644
index 0000000..d8523f6
--- /dev/null
+++ b/algebricks/algebricks-rewriter/src/main/java/org/apache/hyracks/algebricks/rewriter/rules/PushAssignDownThroughProductRule.java
@@ -0,0 +1,87 @@
+/*
+ * 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 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.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.visitors.VariableUtilities;
+import edu.uci.ics.hyracks.algebricks.core.rewriter.base.IAlgebraicRewriteRule;
+
+public class PushAssignDownThroughProductRule implements IAlgebraicRewriteRule {
+
+ @Override
+ public boolean rewritePre(Mutable<ILogicalOperator> opRef, IOptimizationContext context) throws AlgebricksException {
+ return false;
+ }
+
+ @Override
+ public boolean rewritePost(Mutable<ILogicalOperator> opRef, IOptimizationContext context)
+ throws AlgebricksException {
+ AbstractLogicalOperator op1 = (AbstractLogicalOperator) opRef.getValue();
+ if (op1.getOperatorTag() != LogicalOperatorTag.ASSIGN) {
+ return false;
+ }
+ Mutable<ILogicalOperator> op2Ref = op1.getInputs().get(0);
+ AbstractLogicalOperator op2 = (AbstractLogicalOperator) op2Ref.getValue();
+ if (op2.getOperatorTag() != LogicalOperatorTag.INNERJOIN) {
+ return false;
+ }
+ AbstractBinaryJoinOperator join = (AbstractBinaryJoinOperator) op2;
+ if (join.getCondition().getValue() != ConstantExpression.TRUE) {
+ return false;
+ }
+
+ List<LogicalVariable> used = new ArrayList<LogicalVariable>();
+ VariableUtilities.getUsedVariables(op1, used);
+
+ Mutable<ILogicalOperator> b0Ref = op2.getInputs().get(0);
+ ILogicalOperator b0 = b0Ref.getValue();
+ List<LogicalVariable> b0Scm = new ArrayList<LogicalVariable>();
+ VariableUtilities.getLiveVariables(b0, b0Scm);
+ if (b0Scm.containsAll(used)) {
+ // push assign on left branch
+ op2Ref.setValue(b0);
+ b0Ref.setValue(op1);
+ opRef.setValue(op2);
+ return true;
+ } else {
+ Mutable<ILogicalOperator> b1Ref = op2.getInputs().get(1);
+ ILogicalOperator b1 = b1Ref.getValue();
+ List<LogicalVariable> b1Scm = new ArrayList<LogicalVariable>();
+ VariableUtilities.getLiveVariables(b1, b1Scm);
+ if (b1Scm.containsAll(used)) {
+ // push assign on right branch
+ op2Ref.setValue(b1);
+ b1Ref.setValue(op1);
+ opRef.setValue(op2);
+ return true;
+ } else {
+ 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/PushFunctionsBelowJoin.java
----------------------------------------------------------------------
diff --git a/algebricks/algebricks-rewriter/src/main/java/org/apache/hyracks/algebricks/rewriter/rules/PushFunctionsBelowJoin.java b/algebricks/algebricks-rewriter/src/main/java/org/apache/hyracks/algebricks/rewriter/rules/PushFunctionsBelowJoin.java
new file mode 100644
index 0000000..0d24618
--- /dev/null
+++ b/algebricks/algebricks-rewriter/src/main/java/org/apache/hyracks/algebricks/rewriter/rules/PushFunctionsBelowJoin.java
@@ -0,0 +1,208 @@
+/*
+ * 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.Iterator;
+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.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.LogicalOperatorTag;
+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.AbstractLogicalExpression;
+import edu.uci.ics.hyracks.algebricks.core.algebra.expressions.VariableReferenceExpression;
+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.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;
+
+/**
+ * Pushes function-call expressions below a join if possible.
+ * Assigns the result of such function-calls expressions to new variables, and replaces the original
+ * expression with a corresponding variable reference expression.
+ * This rule can help reduce the cost of computing expensive functions by pushing them below
+ * a join (which may blow up the cardinality).
+ * Also, this rule may help to enable other rules such as common subexpression elimination, again to reduce
+ * the number of calls to expensive functions.
+ *
+ * Example: (we are pushing pushMeFunc)
+ *
+ * Before plan:
+ * assign [$$10] <- [funcA(funcB(pushMeFunc($$3, $$4)))]
+ * join (some condition)
+ * join_branch_0 where $$3 and $$4 are not live
+ * ...
+ * join_branch_1 where $$3 and $$4 are live
+ * ...
+ *
+ * After plan:
+ * assign [$$10] <- [funcA(funcB($$11))]
+ * join (some condition)
+ * join_branch_0 where $$3 and $$4 are not live
+ * ...
+ * join_branch_1 where $$3 and $$4 are live
+ * assign[$$11] <- [pushMeFunc($$3, $$4)]
+ * ...
+ */
+public class PushFunctionsBelowJoin implements IAlgebraicRewriteRule {
+
+ private final Set<FunctionIdentifier> toPushFuncIdents;
+ private final List<Mutable<ILogicalExpression>> funcExprs = new ArrayList<Mutable<ILogicalExpression>>();
+ private final List<LogicalVariable> usedVars = new ArrayList<LogicalVariable>();
+ private final List<LogicalVariable> liveVars = new ArrayList<LogicalVariable>();
+
+ public PushFunctionsBelowJoin(Set<FunctionIdentifier> toPushFuncIdents) {
+ this.toPushFuncIdents = toPushFuncIdents;
+ }
+
+ @Override
+ public boolean rewritePre(Mutable<ILogicalOperator> opRef, IOptimizationContext context) throws AlgebricksException {
+ 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 assignOp = (AssignOperator) op;
+
+ // Find a join operator below this assign.
+ Mutable<ILogicalOperator> joinOpRef = findJoinOp(assignOp.getInputs().get(0));
+ if (joinOpRef == null) {
+ return false;
+ }
+ AbstractBinaryJoinOperator joinOp = (AbstractBinaryJoinOperator) joinOpRef.getValue();
+
+ // Check if the assign uses a function that we wish to push below the join if possible.
+ funcExprs.clear();
+ gatherFunctionCalls(assignOp, funcExprs);
+ if (funcExprs.isEmpty()) {
+ return false;
+ }
+
+ // Try to push the functions down the input branches of the join.
+ boolean modified = false;
+ if (pushDownFunctions(joinOp, 0, funcExprs, context)) {
+ modified = true;
+ }
+ if (pushDownFunctions(joinOp, 1, funcExprs, context)) {
+ modified = true;
+ }
+ if (modified) {
+ context.computeAndSetTypeEnvironmentForOperator(joinOp);
+ }
+ return modified;
+ }
+
+ private Mutable<ILogicalOperator> findJoinOp(Mutable<ILogicalOperator> opRef) {
+ AbstractLogicalOperator op = (AbstractLogicalOperator) opRef.getValue();
+ switch (op.getOperatorTag()) {
+ case INNERJOIN:
+ case LEFTOUTERJOIN: {
+ return opRef;
+ }
+ // Bail on these operators.
+ case GROUP:
+ case AGGREGATE:
+ case DISTINCT:
+ case UNNEST_MAP: {
+ return null;
+ }
+ // Traverse children.
+ default: {
+ for (Mutable<ILogicalOperator> childOpRef : op.getInputs()) {
+ return findJoinOp(childOpRef);
+ }
+ }
+ }
+ return null;
+ }
+
+ private void gatherFunctionCalls(AssignOperator assignOp, List<Mutable<ILogicalExpression>> funcExprs) {
+ for (Mutable<ILogicalExpression> exprRef : assignOp.getExpressions()) {
+ gatherFunctionCalls(exprRef, funcExprs);
+ }
+ }
+
+ private void gatherFunctionCalls(Mutable<ILogicalExpression> exprRef, List<Mutable<ILogicalExpression>> funcExprs) {
+ AbstractLogicalExpression expr = (AbstractLogicalExpression) exprRef.getValue();
+ if (expr.getExpressionTag() != LogicalExpressionTag.FUNCTION_CALL) {
+ return;
+ }
+ // Check whether the function is a function we want to push.
+ AbstractFunctionCallExpression funcExpr = (AbstractFunctionCallExpression) expr;
+ if (toPushFuncIdents.contains(funcExpr.getFunctionIdentifier())) {
+ funcExprs.add(exprRef);
+ }
+ // Traverse arguments.
+ for (Mutable<ILogicalExpression> funcArg : funcExpr.getArguments()) {
+ gatherFunctionCalls(funcArg, funcExprs);
+ }
+ }
+
+ private boolean pushDownFunctions(AbstractBinaryJoinOperator joinOp, int inputIndex,
+ List<Mutable<ILogicalExpression>> funcExprs, IOptimizationContext context) throws AlgebricksException {
+ ILogicalOperator joinInputOp = joinOp.getInputs().get(inputIndex).getValue();
+ liveVars.clear();
+ VariableUtilities.getLiveVariables(joinInputOp, liveVars);
+ Iterator<Mutable<ILogicalExpression>> funcIter = funcExprs.iterator();
+ List<LogicalVariable> assignVars = null;
+ List<Mutable<ILogicalExpression>> assignExprs = null;
+ while (funcIter.hasNext()) {
+ Mutable<ILogicalExpression> funcExprRef = funcIter.next();
+ ILogicalExpression funcExpr = funcExprRef.getValue();
+ usedVars.clear();
+ funcExpr.getUsedVariables(usedVars);
+ // Check if we can push the function down this branch.
+ if (liveVars.containsAll(usedVars)) {
+ if (assignVars == null) {
+ assignVars = new ArrayList<LogicalVariable>();
+ assignExprs = new ArrayList<Mutable<ILogicalExpression>>();
+ }
+ // Replace the original expression with a variable reference expression.
+ LogicalVariable replacementVar = context.newVar();
+ assignVars.add(replacementVar);
+ assignExprs.add(new MutableObject<ILogicalExpression>(funcExpr));
+ funcExprRef.setValue(new VariableReferenceExpression(replacementVar));
+ funcIter.remove();
+ }
+ }
+ // Create new assign operator below the join if any functions can be pushed.
+ if (assignVars != null) {
+ AssignOperator newAssign = new AssignOperator(assignVars, assignExprs);
+ newAssign.getInputs().add(new MutableObject<ILogicalOperator>(joinInputOp));
+ newAssign.setExecutionMode(joinOp.getExecutionMode());
+ joinOp.getInputs().get(inputIndex).setValue(newAssign);
+ context.computeAndSetTypeEnvironmentForOperator(newAssign);
+ 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/PushGroupByIntoSortRule.java
----------------------------------------------------------------------
diff --git a/algebricks/algebricks-rewriter/src/main/java/org/apache/hyracks/algebricks/rewriter/rules/PushGroupByIntoSortRule.java b/algebricks/algebricks-rewriter/src/main/java/org/apache/hyracks/algebricks/rewriter/rules/PushGroupByIntoSortRule.java
new file mode 100644
index 0000000..56b2a8e
--- /dev/null
+++ b/algebricks/algebricks-rewriter/src/main/java/org/apache/hyracks/algebricks/rewriter/rules/PushGroupByIntoSortRule.java
@@ -0,0 +1,150 @@
+/*
+ * 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.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.PhysicalOperatorTag;
+import edu.uci.ics.hyracks.algebricks.core.algebra.expressions.IMergeAggregationExpressionFactory;
+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.physical.AbstractStableSortPOperator;
+import edu.uci.ics.hyracks.algebricks.core.algebra.operators.physical.SortGroupByPOperator;
+import edu.uci.ics.hyracks.algebricks.core.rewriter.base.IAlgebraicRewriteRule;
+
+/**
+ * @author yingyib
+ * merge externalsort+preclustered-gby into sort-gby
+ */
+public class PushGroupByIntoSortRule implements IAlgebraicRewriteRule {
+
+ @Override
+ public boolean rewritePre(Mutable<ILogicalOperator> opRef, IOptimizationContext context) throws AlgebricksException {
+ return false;
+ }
+
+ @Override
+ public boolean rewritePost(Mutable<ILogicalOperator> opRef, IOptimizationContext context)
+ throws AlgebricksException {
+ ILogicalOperator op1 = opRef.getValue();
+ if (op1 == null) {
+ return false;
+ }
+ boolean changed = false;
+ for (Mutable<ILogicalOperator> childRef : op1.getInputs()) {
+ AbstractLogicalOperator op = (AbstractLogicalOperator) childRef.getValue();
+ if (op.getOperatorTag() == LogicalOperatorTag.GROUP) {
+ PhysicalOperatorTag opTag = op.getPhysicalOperator().getOperatorTag();
+ GroupByOperator groupByOperator = (GroupByOperator) op;
+ if (opTag == PhysicalOperatorTag.PRE_CLUSTERED_GROUP_BY) {
+ Mutable<ILogicalOperator> op2Ref = op.getInputs().get(0).getValue().getInputs().get(0);
+ AbstractLogicalOperator op2 = (AbstractLogicalOperator) op2Ref.getValue();
+ if (op2.getPhysicalOperator().getOperatorTag() == PhysicalOperatorTag.STABLE_SORT) {
+ AbstractStableSortPOperator sortPhysicalOperator = (AbstractStableSortPOperator) op2
+ .getPhysicalOperator();
+ if (groupByOperator.getNestedPlans().size() != 1) {
+ //Sort group-by currently works only for one nested plan with one root containing
+ //an aggregate and a nested-tuple-source.
+ continue;
+ }
+ ILogicalPlan p0 = groupByOperator.getNestedPlans().get(0);
+ if (p0.getRoots().size() != 1) {
+ //Sort group-by currently works only for one nested plan with one root containing
+ //an aggregate and a nested-tuple-source.
+ continue;
+ }
+
+ Mutable<ILogicalOperator> r0 = p0.getRoots().get(0);
+ AbstractLogicalOperator r0Logical = (AbstractLogicalOperator) r0.getValue();
+ if (r0Logical.getOperatorTag() != LogicalOperatorTag.AGGREGATE) {
+ //we only rewrite aggregation function; do nothing for running aggregates
+ continue;
+ }
+ AggregateOperator aggOp = (AggregateOperator) r0.getValue();
+ AbstractLogicalOperator aggInputOp = (AbstractLogicalOperator) aggOp.getInputs().get(0)
+ .getValue();
+ if (aggInputOp.getOperatorTag() != LogicalOperatorTag.NESTEDTUPLESOURCE) {
+ continue;
+ }
+
+ boolean hasIntermediateAggregate = generateMergeAggregationExpressions(groupByOperator, context);
+ if (!hasIntermediateAggregate) {
+ continue;
+ }
+
+ //replace preclustered gby with sort gby
+ op.setPhysicalOperator(new SortGroupByPOperator(groupByOperator.getGroupByList(), context
+ .getPhysicalOptimizationConfig().getMaxFramesExternalGroupBy(), sortPhysicalOperator
+ .getSortColumns()));
+
+ // remove the stable sort operator
+ op.getInputs().clear();
+ op.getInputs().addAll(op2.getInputs());
+ changed = true;
+ }
+ }
+ continue;
+ } else {
+ continue;
+ }
+ }
+ return changed;
+ }
+
+ private boolean generateMergeAggregationExpressions(GroupByOperator gby, IOptimizationContext context)
+ throws AlgebricksException {
+ if (gby.getNestedPlans().size() != 1) {
+ throw new AlgebricksException(
+ "External/sort group-by currently works only for one nested plan with one root containing"
+ + "an aggregate and a nested-tuple-source.");
+ }
+ ILogicalPlan p0 = gby.getNestedPlans().get(0);
+ if (p0.getRoots().size() != 1) {
+ throw new AlgebricksException(
+ "External/sort group-by currently works only for one nested plan with one root containing"
+ + "an aggregate and a nested-tuple-source.");
+ }
+ IMergeAggregationExpressionFactory mergeAggregationExpressionFactory = context
+ .getMergeAggregationExpressionFactory();
+ Mutable<ILogicalOperator> r0 = p0.getRoots().get(0);
+ AggregateOperator aggOp = (AggregateOperator) r0.getValue();
+ List<Mutable<ILogicalExpression>> aggFuncRefs = aggOp.getExpressions();
+ List<LogicalVariable> originalAggVars = aggOp.getVariables();
+ int n = aggOp.getExpressions().size();
+ List<Mutable<ILogicalExpression>> mergeExpressionRefs = new ArrayList<Mutable<ILogicalExpression>>();
+ for (int i = 0; i < n; i++) {
+ ILogicalExpression mergeExpr = mergeAggregationExpressionFactory.createMergeAggregation(
+ originalAggVars.get(i), aggFuncRefs.get(i).getValue(), context);
+ if (mergeExpr == null) {
+ return false;
+ }
+ mergeExpressionRefs.add(new MutableObject<ILogicalExpression>(mergeExpr));
+ }
+ aggOp.setMergeExpressions(mergeExpressionRefs);
+ 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/PushMapOperatorDownThroughProductRule.java
----------------------------------------------------------------------
diff --git a/algebricks/algebricks-rewriter/src/main/java/org/apache/hyracks/algebricks/rewriter/rules/PushMapOperatorDownThroughProductRule.java b/algebricks/algebricks-rewriter/src/main/java/org/apache/hyracks/algebricks/rewriter/rules/PushMapOperatorDownThroughProductRule.java
new file mode 100644
index 0000000..16a71a4
--- /dev/null
+++ b/algebricks/algebricks-rewriter/src/main/java/org/apache/hyracks/algebricks/rewriter/rules/PushMapOperatorDownThroughProductRule.java
@@ -0,0 +1,87 @@
+/*
+ * 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 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.AbstractBinaryJoinOperator;
+import edu.uci.ics.hyracks.algebricks.core.algebra.operators.logical.AbstractLogicalOperator;
+import edu.uci.ics.hyracks.algebricks.core.algebra.operators.logical.visitors.VariableUtilities;
+import edu.uci.ics.hyracks.algebricks.core.algebra.util.OperatorPropertiesUtil;
+import edu.uci.ics.hyracks.algebricks.core.rewriter.base.IAlgebraicRewriteRule;
+
+public class PushMapOperatorDownThroughProductRule implements IAlgebraicRewriteRule {
+
+ @Override
+ public boolean rewritePre(Mutable<ILogicalOperator> opRef, IOptimizationContext context) throws AlgebricksException {
+ return false;
+ }
+
+ @Override
+ public boolean rewritePost(Mutable<ILogicalOperator> opRef, IOptimizationContext context)
+ throws AlgebricksException {
+ AbstractLogicalOperator op1 = (AbstractLogicalOperator) opRef.getValue();
+ if (!op1.isMap()) {
+ return false;
+ }
+ Mutable<ILogicalOperator> op2Ref = op1.getInputs().get(0);
+ AbstractLogicalOperator op2 = (AbstractLogicalOperator) op2Ref.getValue();
+ if (op2.getOperatorTag() != LogicalOperatorTag.INNERJOIN) {
+ return false;
+ }
+ AbstractBinaryJoinOperator join = (AbstractBinaryJoinOperator) op2;
+ if (!OperatorPropertiesUtil.isAlwaysTrueCond(join.getCondition().getValue())) {
+ return false;
+ }
+
+ List<LogicalVariable> used = new ArrayList<LogicalVariable>();
+ VariableUtilities.getUsedVariables(op1, used);
+
+ Mutable<ILogicalOperator> b0Ref = op2.getInputs().get(0);
+ ILogicalOperator b0 = b0Ref.getValue();
+ List<LogicalVariable> b0Scm = new ArrayList<LogicalVariable>();
+ VariableUtilities.getLiveVariables(b0, b0Scm);
+ if (b0Scm.containsAll(used)) {
+ // push operator on left branch
+ op2Ref.setValue(b0);
+ b0Ref.setValue(op1);
+ opRef.setValue(op2);
+ return true;
+ } else {
+ Mutable<ILogicalOperator> b1Ref = op2.getInputs().get(1);
+ ILogicalOperator b1 = b1Ref.getValue();
+ List<LogicalVariable> b1Scm = new ArrayList<LogicalVariable>();
+ VariableUtilities.getLiveVariables(b1, b1Scm);
+ if (b1Scm.containsAll(used)) {
+ // push operator on right branch
+ op2Ref.setValue(b1);
+ b1Ref.setValue(op1);
+ opRef.setValue(op2);
+ return true;
+ } else {
+ 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/PushNestedOrderByUnderPreSortedGroupByRule.java
----------------------------------------------------------------------
diff --git a/algebricks/algebricks-rewriter/src/main/java/org/apache/hyracks/algebricks/rewriter/rules/PushNestedOrderByUnderPreSortedGroupByRule.java b/algebricks/algebricks-rewriter/src/main/java/org/apache/hyracks/algebricks/rewriter/rules/PushNestedOrderByUnderPreSortedGroupByRule.java
new file mode 100644
index 0000000..476096d
--- /dev/null
+++ b/algebricks/algebricks-rewriter/src/main/java/org/apache/hyracks/algebricks/rewriter/rules/PushNestedOrderByUnderPreSortedGroupByRule.java
@@ -0,0 +1,119 @@
+/*
+ * 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.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.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.PhysicalOperatorTag;
+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.operators.logical.OrderOperator;
+import edu.uci.ics.hyracks.algebricks.core.algebra.operators.logical.OrderOperator.IOrder;
+import edu.uci.ics.hyracks.algebricks.core.algebra.operators.logical.visitors.VariableUtilities;
+import edu.uci.ics.hyracks.algebricks.core.algebra.operators.physical.AbstractPhysicalOperator;
+import edu.uci.ics.hyracks.algebricks.core.algebra.operators.physical.StableSortPOperator;
+import edu.uci.ics.hyracks.algebricks.core.algebra.util.OperatorPropertiesUtil;
+import edu.uci.ics.hyracks.algebricks.core.rewriter.base.IAlgebraicRewriteRule;
+
+public class PushNestedOrderByUnderPreSortedGroupByRule implements IAlgebraicRewriteRule {
+
+ @Override
+ public boolean rewritePre(Mutable<ILogicalOperator> opRef, IOptimizationContext context) throws AlgebricksException {
+ return false;
+ }
+
+ @Override
+ public boolean rewritePost(Mutable<ILogicalOperator> opRef, IOptimizationContext context)
+ throws AlgebricksException {
+ AbstractLogicalOperator op = (AbstractLogicalOperator) opRef.getValue();
+ if (op.getOperatorTag() != LogicalOperatorTag.GROUP) {
+ return false;
+ }
+ if (op.getPhysicalOperator() == null) {
+ return false;
+ }
+ AbstractPhysicalOperator pOp = (AbstractPhysicalOperator) op.getPhysicalOperator();
+ if (pOp.getOperatorTag() != PhysicalOperatorTag.PRE_CLUSTERED_GROUP_BY) {
+ return false;
+ }
+ GroupByOperator gby = (GroupByOperator) op;
+ ILogicalPlan plan = gby.getNestedPlans().get(0);
+ AbstractLogicalOperator op1 = (AbstractLogicalOperator) plan.getRoots().get(0).getValue();
+ if (op1.getOperatorTag() != LogicalOperatorTag.AGGREGATE) {
+ return false;
+ }
+ Mutable<ILogicalOperator> opRef2 = op1.getInputs().get(0);
+ AbstractLogicalOperator op2 = (AbstractLogicalOperator) opRef2.getValue();
+ if (op2.getOperatorTag() != LogicalOperatorTag.ORDER) {
+ return false;
+ }
+ OrderOperator order1 = (OrderOperator) op2;
+ if (!isIndependentFromChildren(order1)) {
+ return false;
+ }
+ AbstractPhysicalOperator pOrder1 = (AbstractPhysicalOperator) op2.getPhysicalOperator();
+ if (pOrder1.getOperatorTag() != PhysicalOperatorTag.STABLE_SORT
+ && pOrder1.getOperatorTag() != PhysicalOperatorTag.IN_MEMORY_STABLE_SORT) {
+ return false;
+ }
+ // StableSortPOperator sort1 = (StableSortPOperator) pOrder1;
+ AbstractLogicalOperator op3 = (AbstractLogicalOperator) op.getInputs().get(0).getValue();
+ if (op3.getOperatorTag() != LogicalOperatorTag.ORDER) {
+ return false;
+ }
+ AbstractPhysicalOperator pOp3 = (AbstractPhysicalOperator) op3.getPhysicalOperator();
+ if (pOp3.getOperatorTag() != PhysicalOperatorTag.STABLE_SORT) {
+ return false;
+ }
+ OrderOperator order2 = (OrderOperator) op3;
+ StableSortPOperator sort2 = (StableSortPOperator) pOp3;
+ // int n1 = sort1.getSortColumns().length;
+ // int n2 = sort2.getSortColumns().length;
+ // OrderColumn[] sortColumns = new OrderColumn[n2 + n1];
+ // System.arraycopy(sort2.getSortColumns(), 0, sortColumns, 0, n2);
+ // int k = 0;
+ for (Pair<IOrder, Mutable<ILogicalExpression>> oe : order1.getOrderExpressions()) {
+ order2.getOrderExpressions().add(oe);
+ // sortColumns[n2 + k] = sort1.getSortColumns()[k];
+ // ++k;
+ }
+ // sort2.setSortColumns(sortColumns);
+ sort2.computeDeliveredProperties(order2, null);
+ // remove order1
+ ILogicalOperator underOrder1 = order1.getInputs().get(0).getValue();
+ opRef2.setValue(underOrder1);
+ return true;
+ }
+
+ private boolean isIndependentFromChildren(OrderOperator order1) throws AlgebricksException {
+ Set<LogicalVariable> free = new HashSet<LogicalVariable>();
+ OperatorPropertiesUtil.getFreeVariablesInSelfOrDesc(order1, free);
+ Set<LogicalVariable> usedInOrder = new HashSet<LogicalVariable>();
+ VariableUtilities.getUsedVariables(order1, usedInOrder);
+ return free.containsAll(usedInOrder);
+ }
+
+}
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/PushProjectDownRule.java
----------------------------------------------------------------------
diff --git a/algebricks/algebricks-rewriter/src/main/java/org/apache/hyracks/algebricks/rewriter/rules/PushProjectDownRule.java b/algebricks/algebricks-rewriter/src/main/java/org/apache/hyracks/algebricks/rewriter/rules/PushProjectDownRule.java
new file mode 100644
index 0000000..b8ff247
--- /dev/null
+++ b/algebricks/algebricks-rewriter/src/main/java/org/apache/hyracks/algebricks/rewriter/rules/PushProjectDownRule.java
@@ -0,0 +1,219 @@
+/*
+ * 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.Collection;
+import java.util.HashSet;
+import java.util.LinkedList;
+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.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.operators.logical.AbstractLogicalOperator;
+import edu.uci.ics.hyracks.algebricks.core.algebra.operators.logical.AbstractOperatorWithNestedPlans;
+import edu.uci.ics.hyracks.algebricks.core.algebra.operators.logical.GroupByOperator;
+import edu.uci.ics.hyracks.algebricks.core.algebra.operators.logical.ProjectOperator;
+import edu.uci.ics.hyracks.algebricks.core.algebra.operators.logical.visitors.VariableUtilities;
+import edu.uci.ics.hyracks.algebricks.core.rewriter.base.IAlgebraicRewriteRule;
+
+/**
+ * Pushes projections through its input operator, provided that operator does
+ * not produce the projected variables.
+ *
+ * @author Nicola
+ */
+public class PushProjectDownRule 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.PROJECT) {
+ return false;
+ }
+ ProjectOperator pi = (ProjectOperator) op;
+ Mutable<ILogicalOperator> opRef2 = pi.getInputs().get(0);
+
+ HashSet<LogicalVariable> toPush = new HashSet<LogicalVariable>();
+ toPush.addAll(pi.getVariables());
+
+ Pair<Boolean, Boolean> p = pushThroughOp(toPush, opRef2, op, context);
+ boolean smthWasPushed = p.first;
+ if (p.second) { // the original projection is redundant
+ opRef.setValue(op.getInputs().get(0).getValue());
+ smthWasPushed = true;
+ }
+
+ return smthWasPushed;
+ }
+
+ private static Pair<Boolean, Boolean> pushThroughOp(HashSet<LogicalVariable> toPush,
+ Mutable<ILogicalOperator> opRef2, ILogicalOperator initialOp, IOptimizationContext context)
+ throws AlgebricksException {
+ List<LogicalVariable> initProjectList = new ArrayList<LogicalVariable>(toPush);
+ AbstractLogicalOperator op2 = (AbstractLogicalOperator) opRef2.getValue();
+ do {
+ if (op2.getOperatorTag() == LogicalOperatorTag.EMPTYTUPLESOURCE
+ || op2.getOperatorTag() == LogicalOperatorTag.NESTEDTUPLESOURCE
+ || op2.getOperatorTag() == LogicalOperatorTag.PROJECT
+ || op2.getOperatorTag() == LogicalOperatorTag.REPLICATE
+ || op2.getOperatorTag() == LogicalOperatorTag.UNIONALL) {
+ return new Pair<Boolean, Boolean>(false, false);
+ }
+ if (!op2.isMap()) {
+ break;
+ }
+ LinkedList<LogicalVariable> usedVars = new LinkedList<LogicalVariable>();
+ VariableUtilities.getUsedVariables(op2, usedVars);
+ toPush.addAll(usedVars);
+ LinkedList<LogicalVariable> producedVars = new LinkedList<LogicalVariable>();
+ VariableUtilities.getProducedVariables(op2, producedVars);
+ toPush.removeAll(producedVars);
+ // we assume pipelineable ops. have only one input
+ opRef2 = op2.getInputs().get(0);
+ op2 = (AbstractLogicalOperator) opRef2.getValue();
+ } while (true);
+
+ LinkedList<LogicalVariable> produced2 = new LinkedList<LogicalVariable>();
+ VariableUtilities.getProducedVariables(op2, produced2);
+ LinkedList<LogicalVariable> used2 = new LinkedList<LogicalVariable>();
+ VariableUtilities.getUsedVariables(op2, used2);
+
+ boolean canCommuteProjection = initProjectList.containsAll(toPush) && initProjectList.containsAll(produced2)
+ && initProjectList.containsAll(used2);
+ // if true, we can get rid of the initial projection
+
+ // get rid of useless decor vars.
+ if (!canCommuteProjection && op2.getOperatorTag() == LogicalOperatorTag.GROUP) {
+ boolean gbyChanged = false;
+ GroupByOperator gby = (GroupByOperator) op2;
+ List<Pair<LogicalVariable, Mutable<ILogicalExpression>>> newDecorList = new ArrayList<Pair<LogicalVariable, Mutable<ILogicalExpression>>>();
+ for (Pair<LogicalVariable, Mutable<ILogicalExpression>> p : gby.getDecorList()) {
+ LogicalVariable decorVar = GroupByOperator.getDecorVariable(p);
+ if (!toPush.contains(decorVar)) {
+ used2.remove(decorVar);
+ gbyChanged = true;
+ } else {
+ newDecorList.add(p);
+ }
+ }
+ gby.getDecorList().clear();
+ gby.getDecorList().addAll(newDecorList);
+ if (gbyChanged) {
+ context.computeAndSetTypeEnvironmentForOperator(gby);
+ }
+ }
+ used2.clear();
+ VariableUtilities.getUsedVariables(op2, used2);
+
+ toPush.addAll(used2); // remember that toPush is a Set
+ toPush.removeAll(produced2);
+
+ if (toPush.isEmpty()) {
+ return new Pair<Boolean, Boolean>(false, false);
+ }
+
+ boolean smthWasPushed = false;
+ for (Mutable<ILogicalOperator> c : op2.getInputs()) {
+ if (pushNeededProjections(toPush, c, context, initialOp)) {
+ smthWasPushed = true;
+ }
+ }
+ if (op2.hasNestedPlans()) {
+ AbstractOperatorWithNestedPlans n = (AbstractOperatorWithNestedPlans) op2;
+ for (ILogicalPlan p : n.getNestedPlans()) {
+ for (Mutable<ILogicalOperator> r : p.getRoots()) {
+ if (pushNeededProjections(toPush, r, context, initialOp)) {
+ smthWasPushed = true;
+ }
+ }
+ }
+ }
+ return new Pair<Boolean, Boolean>(smthWasPushed, canCommuteProjection);
+ }
+
+ // It does not try to push above another Projection.
+ private static boolean pushNeededProjections(HashSet<LogicalVariable> toPush, Mutable<ILogicalOperator> opRef,
+ IOptimizationContext context, ILogicalOperator initialOp) throws AlgebricksException {
+ HashSet<LogicalVariable> allP = new HashSet<LogicalVariable>();
+ AbstractLogicalOperator op = (AbstractLogicalOperator) opRef.getValue();
+ VariableUtilities.getLiveVariables(op, allP);
+
+ HashSet<LogicalVariable> toProject = new HashSet<LogicalVariable>();
+ for (LogicalVariable v : toPush) {
+ if (allP.contains(v)) {
+ toProject.add(v);
+ }
+ }
+ if (toProject.equals(allP)) {
+ // projection would be redundant, since we would project everything
+ // but we can try with the children
+ boolean push = false;
+ if (pushThroughOp(toProject, opRef, initialOp, context).first) {
+ push = true;
+ }
+ return push;
+ } else {
+ return pushAllProjectionsOnTopOf(toProject, opRef, context, initialOp);
+ }
+ }
+
+ // It does not try to push above another Projection.
+ private static boolean pushAllProjectionsOnTopOf(Collection<LogicalVariable> toPush,
+ Mutable<ILogicalOperator> opRef, IOptimizationContext context, ILogicalOperator initialOp)
+ throws AlgebricksException {
+ if (toPush.isEmpty()) {
+ return false;
+ }
+ AbstractLogicalOperator op = (AbstractLogicalOperator) opRef.getValue();
+
+ if (context.checkAndAddToAlreadyCompared(initialOp, op)) {
+ return false;
+ }
+
+ switch (op.getOperatorTag()) {
+ case EXCHANGE: {
+ opRef = opRef.getValue().getInputs().get(0);
+ op = (AbstractLogicalOperator) opRef.getValue();
+ break;
+ }
+ case PROJECT: {
+ return false;
+ }
+ }
+
+ ProjectOperator pi2 = new ProjectOperator(new ArrayList<LogicalVariable>(toPush));
+ pi2.getInputs().add(new MutableObject<ILogicalOperator>(op));
+ opRef.setValue(pi2);
+ pi2.setExecutionMode(op.getExecutionMode());
+ context.computeAndSetTypeEnvironmentForOperator(pi2);
+ 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/PushProjectIntoDataSourceScanRule.java
----------------------------------------------------------------------
diff --git a/algebricks/algebricks-rewriter/src/main/java/org/apache/hyracks/algebricks/rewriter/rules/PushProjectIntoDataSourceScanRule.java b/algebricks/algebricks-rewriter/src/main/java/org/apache/hyracks/algebricks/rewriter/rules/PushProjectIntoDataSourceScanRule.java
new file mode 100644
index 0000000..b17d50f
--- /dev/null
+++ b/algebricks/algebricks-rewriter/src/main/java/org/apache/hyracks/algebricks/rewriter/rules/PushProjectIntoDataSourceScanRule.java
@@ -0,0 +1,60 @@
+/*
+ * 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 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.operators.logical.AbstractLogicalOperator;
+import edu.uci.ics.hyracks.algebricks.core.algebra.operators.logical.DataSourceScanOperator;
+import edu.uci.ics.hyracks.algebricks.core.algebra.operators.logical.ProjectOperator;
+import edu.uci.ics.hyracks.algebricks.core.rewriter.base.IAlgebraicRewriteRule;
+
+public class PushProjectIntoDataSourceScanRule implements IAlgebraicRewriteRule {
+
+ @Override
+ public boolean rewritePre(Mutable<ILogicalOperator> opRef, IOptimizationContext context) throws AlgebricksException {
+ return false;
+ }
+
+ @Override
+ public boolean rewritePost(Mutable<ILogicalOperator> opRef, IOptimizationContext context)
+ throws AlgebricksException {
+ AbstractLogicalOperator op = (AbstractLogicalOperator) opRef.getValue();
+ if (op.getInputs().size() <= 0)
+ return false;
+ AbstractLogicalOperator project = (AbstractLogicalOperator) op.getInputs().get(0).getValue();
+ if (project.getOperatorTag() != LogicalOperatorTag.PROJECT)
+ return false;
+ AbstractLogicalOperator exchange = (AbstractLogicalOperator) project.getInputs().get(0).getValue();
+ if (exchange.getOperatorTag() != LogicalOperatorTag.EXCHANGE)
+ return false;
+ AbstractLogicalOperator inputOp = (AbstractLogicalOperator) exchange.getInputs().get(0).getValue();
+ if (inputOp.getOperatorTag() != LogicalOperatorTag.DATASOURCESCAN)
+ return false;
+ DataSourceScanOperator scanOp = (DataSourceScanOperator) inputOp;
+ ProjectOperator projectOp = (ProjectOperator) project;
+ scanOp.addProjectVariables(projectOp.getVariables());
+ if (op.getOperatorTag() != LogicalOperatorTag.EXCHANGE) {
+ op.getInputs().set(0, project.getInputs().get(0));
+ } else {
+ op.getInputs().set(0, exchange.getInputs().get(0));
+ }
+ 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/PushSelectDownRule.java
----------------------------------------------------------------------
diff --git a/algebricks/algebricks-rewriter/src/main/java/org/apache/hyracks/algebricks/rewriter/rules/PushSelectDownRule.java b/algebricks/algebricks-rewriter/src/main/java/org/apache/hyracks/algebricks/rewriter/rules/PushSelectDownRule.java
new file mode 100644
index 0000000..cc65996
--- /dev/null
+++ b/algebricks/algebricks-rewriter/src/main/java/org/apache/hyracks/algebricks/rewriter/rules/PushSelectDownRule.java
@@ -0,0 +1,98 @@
+/*
+ * 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.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.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.SelectOperator;
+import edu.uci.ics.hyracks.algebricks.core.algebra.operators.logical.visitors.VariableUtilities;
+import edu.uci.ics.hyracks.algebricks.core.algebra.util.OperatorPropertiesUtil;
+import edu.uci.ics.hyracks.algebricks.core.rewriter.base.IAlgebraicRewriteRule;
+
+public class PushSelectDownRule 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;
+ }
+
+ Mutable<ILogicalOperator> opRef2 = op.getInputs().get(0);
+ AbstractLogicalOperator op2 = (AbstractLogicalOperator) opRef2.getValue();
+
+ if (context.checkAndAddToAlreadyCompared(op, op2)) {
+ return false;
+ }
+
+ LogicalOperatorTag tag2 = op2.getOperatorTag();
+
+ if (tag2 == LogicalOperatorTag.INNERJOIN || tag2 == LogicalOperatorTag.LEFTOUTERJOIN
+ || tag2 == LogicalOperatorTag.REPLICATE) {
+ return false;
+ } else { // not a join
+ boolean res = propagateSelectionRec(opRef, opRef2);
+ if (res) {
+ OperatorPropertiesUtil.typeOpRec(opRef, context);
+ }
+ return res;
+ }
+ }
+
+ private static boolean propagateSelectionRec(Mutable<ILogicalOperator> sigmaRef, Mutable<ILogicalOperator> opRef2)
+ throws AlgebricksException {
+ AbstractLogicalOperator op2 = (AbstractLogicalOperator) opRef2.getValue();
+ if (op2.getInputs().size() != 1 || op2.getOperatorTag() == LogicalOperatorTag.DATASOURCESCAN) {
+ return false;
+ }
+
+ SelectOperator sigma = (SelectOperator) sigmaRef.getValue();
+ LinkedList<LogicalVariable> usedInSigma = new LinkedList<LogicalVariable>();
+ sigma.getCondition().getValue().getUsedVariables(usedInSigma);
+
+ LinkedList<LogicalVariable> produced2 = new LinkedList<LogicalVariable>();
+ VariableUtilities.getProducedVariables(op2, produced2);
+ if (OperatorPropertiesUtil.disjoint(produced2, usedInSigma)) {
+ // just swap
+ opRef2.setValue(sigma);
+ sigmaRef.setValue(op2);
+ List<Mutable<ILogicalOperator>> sigmaInpList = sigma.getInputs();
+ sigmaInpList.clear();
+ sigmaInpList.addAll(op2.getInputs());
+ List<Mutable<ILogicalOperator>> op2InpList = op2.getInputs();
+ op2InpList.clear();
+ op2InpList.add(opRef2);
+ propagateSelectionRec(opRef2, sigma.getInputs().get(0));
+ 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/PushSelectIntoJoinRule.java
----------------------------------------------------------------------
diff --git a/algebricks/algebricks-rewriter/src/main/java/org/apache/hyracks/algebricks/rewriter/rules/PushSelectIntoJoinRule.java b/algebricks/algebricks-rewriter/src/main/java/org/apache/hyracks/algebricks/rewriter/rules/PushSelectIntoJoinRule.java
new file mode 100644
index 0000000..e29299c
--- /dev/null
+++ b/algebricks/algebricks-rewriter/src/main/java/org/apache/hyracks/algebricks/rewriter/rules/PushSelectIntoJoinRule.java
@@ -0,0 +1,309 @@
+/*
+ * 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.Collection;
+import java.util.HashSet;
+import java.util.Iterator;
+import java.util.LinkedList;
+import java.util.List;
+import java.util.ListIterator;
+
+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.LogicalOperatorTag;
+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.ScalarFunctionCallExpression;
+import edu.uci.ics.hyracks.algebricks.core.algebra.functions.AlgebricksBuiltinFunctions;
+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.InnerJoinOperator;
+import edu.uci.ics.hyracks.algebricks.core.algebra.operators.logical.SelectOperator;
+import edu.uci.ics.hyracks.algebricks.core.algebra.operators.logical.visitors.VariableUtilities;
+import edu.uci.ics.hyracks.algebricks.core.algebra.util.OperatorPropertiesUtil;
+import edu.uci.ics.hyracks.algebricks.core.rewriter.base.IAlgebraicRewriteRule;
+
+public class PushSelectIntoJoinRule implements IAlgebraicRewriteRule {
+
+ @Override
+ public boolean rewritePre(Mutable<ILogicalOperator> opRef, IOptimizationContext context) {
+ return false;
+ }
+
+ @Override
+ public boolean rewritePost(Mutable<ILogicalOperator> opRef, IOptimizationContext context)
+ throws AlgebricksException {
+ Collection<LogicalVariable> joinLiveVarsLeft = new HashSet<LogicalVariable>();
+ Collection<LogicalVariable> joinLiveVarsRight = new HashSet<LogicalVariable>();
+ Collection<LogicalVariable> liveInOpsToPushLeft = new HashSet<LogicalVariable>();
+ Collection<LogicalVariable> liveInOpsToPushRight = new HashSet<LogicalVariable>();
+
+ List<ILogicalOperator> pushedOnLeft = new ArrayList<ILogicalOperator>();
+ List<ILogicalOperator> pushedOnRight = new ArrayList<ILogicalOperator>();
+ LinkedList<ILogicalOperator> notPushedStack = new LinkedList<ILogicalOperator>();
+ Collection<LogicalVariable> usedVars = new HashSet<LogicalVariable>();
+ Collection<LogicalVariable> producedVars = new HashSet<LogicalVariable>();
+
+ AbstractLogicalOperator op = (AbstractLogicalOperator) opRef.getValue();
+ if (op.getOperatorTag() != LogicalOperatorTag.SELECT) {
+ return false;
+ }
+ SelectOperator select = (SelectOperator) op;
+ Mutable<ILogicalOperator> opRef2 = op.getInputs().get(0);
+ AbstractLogicalOperator son = (AbstractLogicalOperator) opRef2.getValue();
+ AbstractLogicalOperator op2 = son;
+ boolean needToPushOps = false;
+ while (son.isMap()) {
+ needToPushOps = true;
+ Mutable<ILogicalOperator> opRefLink = son.getInputs().get(0);
+ son = (AbstractLogicalOperator) opRefLink.getValue();
+ }
+
+ if (son.getOperatorTag() != LogicalOperatorTag.INNERJOIN
+ && son.getOperatorTag() != LogicalOperatorTag.LEFTOUTERJOIN) {
+ return false;
+ }
+ boolean isLoj = son.getOperatorTag() == LogicalOperatorTag.LEFTOUTERJOIN;
+ AbstractBinaryJoinOperator join = (AbstractBinaryJoinOperator) son;
+
+ Mutable<ILogicalOperator> joinBranchLeftRef = join.getInputs().get(0);
+ Mutable<ILogicalOperator> joinBranchRightRef = join.getInputs().get(1);
+
+ if (needToPushOps) {
+ ILogicalOperator joinBranchLeft = joinBranchLeftRef.getValue();
+ ILogicalOperator joinBranchRight = joinBranchRightRef.getValue();
+ VariableUtilities.getLiveVariables(joinBranchLeft, joinLiveVarsLeft);
+ VariableUtilities.getLiveVariables(joinBranchRight, joinLiveVarsRight);
+ Mutable<ILogicalOperator> opIterRef = opRef2;
+ ILogicalOperator opIter = op2;
+ while (opIter != join) {
+ LogicalOperatorTag tag = ((AbstractLogicalOperator) opIter).getOperatorTag();
+ if (tag == LogicalOperatorTag.PROJECT) {
+ notPushedStack.addFirst(opIter);
+ } else {
+ VariableUtilities.getUsedVariables(opIter, usedVars);
+ VariableUtilities.getProducedVariables(opIter, producedVars);
+ if (joinLiveVarsLeft.containsAll(usedVars)) {
+ pushedOnLeft.add(opIter);
+ liveInOpsToPushLeft.addAll(producedVars);
+ } else if (joinLiveVarsRight.containsAll(usedVars)) {
+ pushedOnRight.add(opIter);
+ liveInOpsToPushRight.addAll(producedVars);
+ } else {
+ return false;
+ }
+ }
+ opIterRef = opIter.getInputs().get(0);
+ opIter = opIterRef.getValue();
+ }
+ if (isLoj && pushedOnLeft.isEmpty()) {
+ return false;
+ }
+ }
+
+ boolean intersectsAllBranches = true;
+ boolean[] intersectsBranch = new boolean[join.getInputs().size()];
+ LinkedList<LogicalVariable> selectVars = new LinkedList<LogicalVariable>();
+ select.getCondition().getValue().getUsedVariables(selectVars);
+ int i = 0;
+ for (Mutable<ILogicalOperator> branch : join.getInputs()) {
+ LinkedList<LogicalVariable> branchVars = new LinkedList<LogicalVariable>();
+ VariableUtilities.getLiveVariables(branch.getValue(), branchVars);
+ if (i == 0) {
+ branchVars.addAll(liveInOpsToPushLeft);
+ } else {
+ branchVars.addAll(liveInOpsToPushRight);
+ }
+ if (OperatorPropertiesUtil.disjoint(selectVars, branchVars)) {
+ intersectsAllBranches = false;
+ } else {
+ intersectsBranch[i] = true;
+ }
+ i++;
+ }
+ if (!intersectsBranch[0] && !intersectsBranch[1]) {
+ return false;
+ }
+ if (needToPushOps) {
+ pushOps(pushedOnLeft, joinBranchLeftRef, context);
+ pushOps(pushedOnRight, joinBranchRightRef, context);
+ }
+ if (intersectsAllBranches) {
+ addCondToJoin(select, join, context);
+ } else { // push down
+ Iterator<Mutable<ILogicalOperator>> branchIter = join.getInputs().iterator();
+ ILogicalExpression selectCondition = select.getCondition().getValue();
+ boolean lojToInner = false;
+ for (int j = 0; j < intersectsBranch.length; j++) {
+ Mutable<ILogicalOperator> branch = branchIter.next();
+ boolean inter = intersectsBranch[j];
+ if (inter) {
+ if (j > 0 && isLoj) {
+ // if a left outer join, if the select condition is not-null filtering,
+ // we rewrite left outer join
+ // to inner join for this case.
+ if (containsNotNullFiltering(selectCondition)) {
+ lojToInner = true;
+ }
+ }
+ if ((j > 0 && isLoj) && containsNullFiltering(selectCondition)) {
+ // Select is-null($$var) cannot be pushed in the right branch of a LOJ;
+ notPushedStack.addFirst(select);
+ } else {
+ // Conditions for the left branch can always be pushed.
+ // Other conditions can be pushed to the right branch of a LOJ.
+ copySelectToBranch(select, branch, context);
+ }
+ }
+ }
+ if (lojToInner) {
+ // Rewrites left outer join to inner join.
+ InnerJoinOperator innerJoin = new InnerJoinOperator(join.getCondition());
+ innerJoin.getInputs().addAll(join.getInputs());
+ join = innerJoin;
+ context.computeAndSetTypeEnvironmentForOperator(join);
+ }
+ }
+ ILogicalOperator top = join;
+ for (ILogicalOperator npOp : notPushedStack) {
+ List<Mutable<ILogicalOperator>> npInpList = npOp.getInputs();
+ npInpList.clear();
+ npInpList.add(new MutableObject<ILogicalOperator>(top));
+ context.computeAndSetTypeEnvironmentForOperator(npOp);
+ top = npOp;
+ }
+ opRef.setValue(top);
+ return true;
+
+ }
+
+ private void pushOps(List<ILogicalOperator> opList, Mutable<ILogicalOperator> joinBranch,
+ IOptimizationContext context) throws AlgebricksException {
+ ILogicalOperator topOp = joinBranch.getValue();
+ ListIterator<ILogicalOperator> iter = opList.listIterator(opList.size());
+ while (iter.hasPrevious()) {
+ ILogicalOperator op = iter.previous();
+ List<Mutable<ILogicalOperator>> opInpList = op.getInputs();
+ opInpList.clear();
+ opInpList.add(new MutableObject<ILogicalOperator>(topOp));
+ topOp = op;
+ context.computeAndSetTypeEnvironmentForOperator(op);
+ }
+ joinBranch.setValue(topOp);
+ }
+
+ private static void addCondToJoin(SelectOperator select, AbstractBinaryJoinOperator join,
+ IOptimizationContext context) {
+ ILogicalExpression cond = join.getCondition().getValue();
+ if (OperatorPropertiesUtil.isAlwaysTrueCond(cond)) { // the join was a product
+ join.getCondition().setValue(select.getCondition().getValue());
+ } else {
+ boolean bAddedToConj = false;
+ if (cond.getExpressionTag() == LogicalExpressionTag.FUNCTION_CALL) {
+ AbstractFunctionCallExpression fcond = (AbstractFunctionCallExpression) cond;
+ if (fcond.getFunctionIdentifier().equals(AlgebricksBuiltinFunctions.AND)) {
+ AbstractFunctionCallExpression newCond = new ScalarFunctionCallExpression(context
+ .getMetadataProvider().lookupFunction(AlgebricksBuiltinFunctions.AND));
+ newCond.getArguments().add(select.getCondition());
+ newCond.getArguments().addAll(fcond.getArguments());
+ join.getCondition().setValue(newCond);
+ bAddedToConj = true;
+ }
+ }
+ if (!bAddedToConj) {
+ AbstractFunctionCallExpression newCond = new ScalarFunctionCallExpression(context.getMetadataProvider()
+ .lookupFunction(AlgebricksBuiltinFunctions.AND), select.getCondition(),
+ new MutableObject<ILogicalExpression>(join.getCondition().getValue()));
+ join.getCondition().setValue(newCond);
+ }
+ }
+ }
+
+ private static void copySelectToBranch(SelectOperator select, Mutable<ILogicalOperator> branch,
+ IOptimizationContext context) throws AlgebricksException {
+ ILogicalOperator newSelect = new SelectOperator(select.getCondition(), select.getRetainNull(),
+ select.getNullPlaceholderVariable());
+ Mutable<ILogicalOperator> newRef = new MutableObject<ILogicalOperator>(branch.getValue());
+ newSelect.getInputs().add(newRef);
+ branch.setValue(newSelect);
+ context.computeAndSetTypeEnvironmentForOperator(newSelect);
+ }
+
+ /**
+ * Whether the expression contains a not-null filtering
+ *
+ * @param expr
+ * @return true if the expression contains a not-null filtering function call; false otherwise.
+ */
+ private boolean containsNotNullFiltering(ILogicalExpression expr) {
+ if (expr.getExpressionTag() != LogicalExpressionTag.FUNCTION_CALL) {
+ return false;
+ }
+ ScalarFunctionCallExpression func = (ScalarFunctionCallExpression) expr;
+ if (func.getFunctionIdentifier() == AlgebricksBuiltinFunctions.AND) {
+ for (Mutable<ILogicalExpression> argumentRef : func.getArguments()) {
+ if (containsNotNullFiltering(argumentRef.getValue())) {
+ return true;
+ }
+ }
+ return false;
+ }
+ if (func.getFunctionIdentifier() != AlgebricksBuiltinFunctions.NOT) {
+ return false;
+ }
+ ILogicalExpression arg = func.getArguments().get(0).getValue();
+ if (arg.getExpressionTag() != LogicalExpressionTag.FUNCTION_CALL) {
+ return false;
+ }
+ ScalarFunctionCallExpression func2 = (ScalarFunctionCallExpression) arg;
+ if (func2.getFunctionIdentifier() != AlgebricksBuiltinFunctions.IS_NULL) {
+ return false;
+ }
+ return true;
+ }
+
+ /**
+ * Whether the expression contains a null filtering
+ *
+ * @param expr
+ * @return true if the expression contains a null filtering function call; false otherwise.
+ */
+ private boolean containsNullFiltering(ILogicalExpression expr) {
+ if (expr.getExpressionTag() != LogicalExpressionTag.FUNCTION_CALL) {
+ return false;
+ }
+ ScalarFunctionCallExpression func = (ScalarFunctionCallExpression) expr;
+ if (func.getFunctionIdentifier() == AlgebricksBuiltinFunctions.AND) {
+ for (Mutable<ILogicalExpression> argumentRef : func.getArguments()) {
+ if (containsNullFiltering(argumentRef.getValue())) {
+ return true;
+ }
+ }
+ return false;
+ }
+ if (func.getFunctionIdentifier() != AlgebricksBuiltinFunctions.IS_NULL) {
+ return false;
+ }
+ return true;
+ }
+}
\ No newline at end of file