Abstracting algebricks rules out of AsterixDB.
Change-Id: I80789e3827b4224b92b0b9d7247919f862f6f939
Reviewed-on: https://asterix-gerrit.ics.uci.edu/352
Tested-by: Jenkins <jenkins@fulliautomatix.ics.uci.edu>
Reviewed-by: Steven Jacobs <sjaco002@ucr.edu>
diff --git a/algebricks/algebricks-rewriter/src/main/java/edu/uci/ics/hyracks/algebricks/rewriter/rules/ExtractFunctionsFromJoinConditionRule.java b/algebricks/algebricks-rewriter/src/main/java/edu/uci/ics/hyracks/algebricks/rewriter/rules/ExtractFunctionsFromJoinConditionRule.java
new file mode 100644
index 0000000..8f8e62b
--- /dev/null
+++ b/algebricks/algebricks-rewriter/src/main/java/edu/uci/ics/hyracks/algebricks/rewriter/rules/ExtractFunctionsFromJoinConditionRule.java
@@ -0,0 +1,155 @@
+/*
+ * 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.base.LogicalVariable;
+import edu.uci.ics.hyracks.algebricks.core.algebra.expressions.AbstractFunctionCallExpression;
+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.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;
+
+/**
+ * Factors out function expressions from each comparison function or similarity function in join condition by
+ * assigning them to a variables, and replacing the function expressions with references to those variables.
+ * Examples:
+ * Plan with function expressions in comparison or similarity condition of join expression.
+ * Generates one assign operator per extracted function expression.
+ *
+ * <pre>
+ * Before plan:
+ *
+ * join ( eq( funcX($$1), funcX($$2) ) )
+ *
+ * After plan:
+ *
+ * join (eq($$3,$$4))
+ * assign [$$4] <- [funcY($$2)]
+ * assign [$$3] <- [funcX($$1)]
+ * </pre>
+ */
+public class ExtractFunctionsFromJoinConditionRule 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
+ && op.getOperatorTag() != LogicalOperatorTag.LEFTOUTERJOIN) {
+ return false;
+ }
+ AbstractBinaryJoinOperator joinOp = (AbstractBinaryJoinOperator) op;
+ ILogicalExpression expr = joinOp.getCondition().getValue();
+
+ return assignFunctionExpressions(joinOp, expr, context);
+
+ }
+
+ private boolean assignFunctionExpressions(AbstractLogicalOperator joinOp, ILogicalExpression expr,
+ IOptimizationContext context) throws AlgebricksException {
+ if (expr.getExpressionTag() != LogicalExpressionTag.FUNCTION_CALL) {
+ return false;
+ }
+ AbstractFunctionCallExpression fexp = (AbstractFunctionCallExpression) expr;
+ FunctionIdentifier fi = fexp.getFunctionIdentifier();
+
+ boolean modified = false;
+ if (fi.equals(AlgebricksBuiltinFunctions.AND) || fi.equals(AlgebricksBuiltinFunctions.OR)
+ || processArgumentsToFunction(fi)) {
+ for (Mutable<ILogicalExpression> a : fexp.getArguments()) {
+ if (assignFunctionExpressions(joinOp, a.getValue(), context)) {
+ modified = true;
+ }
+ }
+ return modified;
+ } else if (AlgebricksBuiltinFunctions.isComparisonFunction(fi) || isComparisonFunction(fi)) {
+ for (Mutable<ILogicalExpression> exprRef : fexp.getArguments()) {
+ if (exprRef.getValue().getExpressionTag() == LogicalExpressionTag.FUNCTION_CALL) {
+ LogicalVariable newVar = context.newVar();
+ AssignOperator newAssign = new AssignOperator(newVar, new MutableObject<ILogicalExpression>(exprRef
+ .getValue().cloneExpression()));
+ newAssign.setExecutionMode(joinOp.getExecutionMode());
+
+ // Place assign below joinOp.
+ List<LogicalVariable> used = new ArrayList<LogicalVariable>();
+ VariableUtilities.getUsedVariables(newAssign, used);
+
+ Mutable<ILogicalOperator> leftBranchRef = joinOp.getInputs().get(0);
+ ILogicalOperator leftBranch = leftBranchRef.getValue();
+ List<LogicalVariable> leftBranchVariables = new ArrayList<LogicalVariable>();
+ VariableUtilities.getLiveVariables(leftBranch, leftBranchVariables);
+ if (leftBranchVariables.containsAll(used)) {
+ // place assign on left branch
+ newAssign.getInputs().add(new MutableObject<ILogicalOperator>(leftBranch));
+ leftBranchRef.setValue(newAssign);
+ modified = true;
+ } else {
+ Mutable<ILogicalOperator> rightBranchRef = joinOp.getInputs().get(1);
+ ILogicalOperator rightBranch = rightBranchRef.getValue();
+ List<LogicalVariable> rightBranchVariables = new ArrayList<LogicalVariable>();
+ VariableUtilities.getLiveVariables(rightBranch, rightBranchVariables);
+ if (rightBranchVariables.containsAll(used)) {
+ // place assign on right branch
+ newAssign.getInputs().add(new MutableObject<ILogicalOperator>(rightBranch));
+ rightBranchRef.setValue(newAssign);
+ modified = true;
+ }
+ }
+
+ if (modified) {
+ // Replace original expr with variable reference.
+ exprRef.setValue(new VariableReferenceExpression(newVar));
+ context.computeAndSetTypeEnvironmentForOperator(newAssign);
+ context.computeAndSetTypeEnvironmentForOperator(joinOp);
+ }
+ }
+ }
+ return modified;
+ } else {
+ return false;
+ }
+ }
+
+ protected boolean processArgumentsToFunction(FunctionIdentifier fi) {
+ return false;
+ }
+
+ protected boolean isComparisonFunction(FunctionIdentifier fi) {
+ return false;
+ }
+
+}
diff --git a/algebricks/algebricks-rewriter/src/main/java/edu/uci/ics/hyracks/algebricks/rewriter/rules/IntroduceGroupByForSubplanRule.java b/algebricks/algebricks-rewriter/src/main/java/edu/uci/ics/hyracks/algebricks/rewriter/rules/IntroduceGroupByForSubplanRule.java
index ab7835d..a6d9ab0 100644
--- a/algebricks/algebricks-rewriter/src/main/java/edu/uci/ics/hyracks/algebricks/rewriter/rules/IntroduceGroupByForSubplanRule.java
+++ b/algebricks/algebricks-rewriter/src/main/java/edu/uci/ics/hyracks/algebricks/rewriter/rules/IntroduceGroupByForSubplanRule.java
@@ -3,9 +3,9 @@
* 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.
@@ -60,6 +60,45 @@
import edu.uci.ics.hyracks.algebricks.core.rewriter.base.IAlgebraicRewriteRule;
import edu.uci.ics.hyracks.algebricks.rewriter.util.PhysicalOptimizationsUtil;
+/**
+ * The rule searches for SUBPLAN operator with a optional PROJECT operator and
+ * an AGGREGATE followed by a join operator.
+ *
+ * <pre>
+ * Before
+ *
+ * plan__parent
+ * SUBPLAN {
+ * PROJECT?
+ * AGGREGATE
+ * plan__nested_A
+ * INNER_JOIN | LEFT_OUTER_JOIN ($condition, $left, $right)
+ * plan__nested_B
+ * }
+ * plan__child
+ *
+ * where $condition does not equal a constant true.
+ *
+ * After (This is a general application of the rule, specifics may vary based on the query plan.)
+ *
+ * plan__parent
+ * GROUP_BY {
+ * PROJECT?
+ * AGGREGATE
+ * plan__nested_A
+ * SELECT( algebricks:not( is_null( $right ) ) )
+ * NESTED_TUPLE_SOURCE
+ * }
+ * SUBPLAN {
+ * INNER_JOIN | LEFT_OUTER_JOIN ($condition, $left, $right)
+ * plan__nested_B
+ * }
+ * plan__child
+ * </pre>
+ *
+ * @author prestonc
+ */
+
public class IntroduceGroupByForSubplanRule implements IAlgebraicRewriteRule {
@Override
diff --git a/algebricks/algebricks-rewriter/src/main/java/edu/uci/ics/hyracks/algebricks/rewriter/rules/MoveFreeVariableOperatorOutOfSubplanRule.java b/algebricks/algebricks-rewriter/src/main/java/edu/uci/ics/hyracks/algebricks/rewriter/rules/MoveFreeVariableOperatorOutOfSubplanRule.java
index b01f320..5867abd 100644
--- a/algebricks/algebricks-rewriter/src/main/java/edu/uci/ics/hyracks/algebricks/rewriter/rules/MoveFreeVariableOperatorOutOfSubplanRule.java
+++ b/algebricks/algebricks-rewriter/src/main/java/edu/uci/ics/hyracks/algebricks/rewriter/rules/MoveFreeVariableOperatorOutOfSubplanRule.java
@@ -1,11 +1,11 @@
/*
- * Copyright 2009-2014 by The Regents of the University of California
+ * 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.
@@ -30,19 +30,43 @@
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.OperatorPropertiesUtil;
+import edu.uci.ics.hyracks.algebricks.rewriter.rules.AbstractDecorrelationRule;
+/**
+ * The rule searches for operators that can be moved outside the subplan.
+ *
+ * <pre>
+ * Before
+ *
+ * %PARENT_PLAN
+ * SUBPLAN{
+ * %NESTED_OPERATORS_B+
+ * ASSIGN || %SUBPLAN
+ * %NESTED_OPERATORS_A*
+ * NESTEDTUPLESOURCE
+ * }
+ * %CHILD_PLAN
+ *
+ * where
+ * %SUBPLAN has one nested plan with a root AGGREGATE operator.
+ *
+ * After
+ *
+ * %PARENT_PLAN
+ * SUBPLAN{
+ * %NESTED_OPERATORS_B+
+ * %NESTED_OPERATORS_A*
+ * NESTEDTUPLESOURCE
+ * }
+ * ASSIGN || %SUBPLAN
+ * %CHILD_PLAN
+ * </pre>
+ */
public class MoveFreeVariableOperatorOutOfSubplanRule extends AbstractDecorrelationRule {
@Override
public boolean rewritePost(Mutable<ILogicalOperator> opRef, IOptimizationContext context)
throws AlgebricksException {
- /*
- * This rule looks for an assign within a subplan that uses only
- * variables from outside of the subplan
- *
- * It moves this assign outside of the subplan
- *
- */
AbstractLogicalOperator op0 = (AbstractLogicalOperator) opRef.getValue();
if (op0.getOperatorTag() != LogicalOperatorTag.SUBPLAN) {
return false;
@@ -90,11 +114,38 @@
//Get its used variables
Set<LogicalVariable> used = new HashSet<LogicalVariable>();
- VariableUtilities.getUsedVariables(op2, used);
- //not movable if the operator is not an assign
+ //not movable if the operator is not an assign or subplan
//Might be helpful in the future for other operations in the future
- if (op2.getOperatorTag() != LogicalOperatorTag.ASSIGN) {
+ if (movableOperator(op2.getOperatorTag())) {
+ if (op2.getOperatorTag() == LogicalOperatorTag.ASSIGN) {
+ VariableUtilities.getUsedVariables(op2, used);
+ } else if (op2.getOperatorTag() == LogicalOperatorTag.SUBPLAN) {
+ // Nested plan must have an aggregate root.
+ ListIterator<ILogicalPlan> subplansIter = ((SubplanOperator) op2).getNestedPlans().listIterator();
+ ILogicalPlan plan = null;
+ while (subplansIter.hasNext()) {
+ plan = subplansIter.next();
+ }
+ if (plan == null) {
+ return false;
+ }
+ if (plan.getRoots().size() != 1) {
+ return false;
+ }
+ ILogicalOperator op3 = plan.getRoots().get(0).getValue();
+ if (op3.getOperatorTag() != LogicalOperatorTag.AGGREGATE) {
+ return false;
+ }
+ // Used variables do not include ones created in the subplan.
+ VariableUtilities.getUsedVariables(op2, used);
+ Set<LogicalVariable> subplanProducedAndDown = new HashSet<LogicalVariable>();
+ VariableUtilities.getProducedVariablesInDescendantsAndSelf(op3, subplanProducedAndDown);
+ used.removeAll(subplanProducedAndDown);
+ } else {
+ notApplicable = true;
+ }
+ } else {
notApplicable = true;
}
@@ -126,4 +177,7 @@
return false;
}
-}
+ protected boolean movableOperator(LogicalOperatorTag operatorTag) {
+ return (operatorTag == LogicalOperatorTag.ASSIGN || operatorTag == LogicalOperatorTag.SUBPLAN);
+ }
+}
\ No newline at end of file