You are viewing a plain text version of this content. The canonical link for it is here.
Posted to commits@vxquery.apache.org by pr...@apache.org on 2013/11/01 22:24:32 UTC
svn commit: r1538066 - in
/incubator/vxquery/trunk/vxquery/vxquery-core/src/main/java/org/apache/vxquery/compiler/rewriter:
./ rules/
Author: prestonc
Date: Fri Nov 1 21:24:32 2013
New Revision: 1538066
URL: http://svn.apache.org/r1538066
Log:
All changes to the InlineVaraiablesRule are now in VXQuery only (no changes to Hyracks). Also includes a generic rule for PushMapOperatorDownThroughProductRule that works for unnest, assigning and select operator.
Added:
incubator/vxquery/trunk/vxquery/vxquery-core/src/main/java/org/apache/vxquery/compiler/rewriter/rules/InlineReferenceVariablesRule.java (with props)
incubator/vxquery/trunk/vxquery/vxquery-core/src/main/java/org/apache/vxquery/compiler/rewriter/rules/PushMapOperatorDownThroughProductRule.java (with props)
Removed:
incubator/vxquery/trunk/vxquery/vxquery-core/src/main/java/org/apache/vxquery/compiler/rewriter/rules/PushUnnestDownThroughProductRule.java
Modified:
incubator/vxquery/trunk/vxquery/vxquery-core/src/main/java/org/apache/vxquery/compiler/rewriter/RewriteRuleset.java
incubator/vxquery/trunk/vxquery/vxquery-core/src/main/java/org/apache/vxquery/compiler/rewriter/rules/InlineReferenceVariablePolicy.java
Modified: incubator/vxquery/trunk/vxquery/vxquery-core/src/main/java/org/apache/vxquery/compiler/rewriter/RewriteRuleset.java
URL: http://svn.apache.org/viewvc/incubator/vxquery/trunk/vxquery/vxquery-core/src/main/java/org/apache/vxquery/compiler/rewriter/RewriteRuleset.java?rev=1538066&r1=1538065&r2=1538066&view=diff
==============================================================================
--- incubator/vxquery/trunk/vxquery/vxquery-core/src/main/java/org/apache/vxquery/compiler/rewriter/RewriteRuleset.java (original)
+++ incubator/vxquery/trunk/vxquery/vxquery-core/src/main/java/org/apache/vxquery/compiler/rewriter/RewriteRuleset.java Fri Nov 1 21:24:32 2013
@@ -24,10 +24,10 @@ import org.apache.vxquery.compiler.rewri
import org.apache.vxquery.compiler.rewriter.rules.ConvertAssignToUnnestRule;
import org.apache.vxquery.compiler.rewriter.rules.EliminateUnnestAggregateSequencesRule;
import org.apache.vxquery.compiler.rewriter.rules.EliminateUnnestAggregateSubplanRule;
-import org.apache.vxquery.compiler.rewriter.rules.InlineReferenceVariablePolicy;
+import org.apache.vxquery.compiler.rewriter.rules.InlineReferenceVariablesRule;
import org.apache.vxquery.compiler.rewriter.rules.IntroduceCollectionRule;
import org.apache.vxquery.compiler.rewriter.rules.IntroduceTwoStepAggregateRule;
-import org.apache.vxquery.compiler.rewriter.rules.PushUnnestDownThroughProductRule;
+import org.apache.vxquery.compiler.rewriter.rules.PushMapOperatorDownThroughProductRule;
import org.apache.vxquery.compiler.rewriter.rules.RemoveUnusedSortDistinctNodesRule;
import org.apache.vxquery.compiler.rewriter.rules.RemoveUnusedTreatRule;
import org.apache.vxquery.compiler.rewriter.rules.SetCollectionDataSourceRule;
@@ -51,7 +51,6 @@ import edu.uci.ics.hyracks.algebricks.re
import edu.uci.ics.hyracks.algebricks.rewriter.rules.IntroduceGroupByCombinerRule;
import edu.uci.ics.hyracks.algebricks.rewriter.rules.IsolateHyracksOperatorsRule;
import edu.uci.ics.hyracks.algebricks.rewriter.rules.PullSelectOutOfEqJoin;
-import edu.uci.ics.hyracks.algebricks.rewriter.rules.PushAssignDownThroughProductRule;
import edu.uci.ics.hyracks.algebricks.rewriter.rules.PushLimitDownRule;
import edu.uci.ics.hyracks.algebricks.rewriter.rules.PushProjectDownRule;
import edu.uci.ics.hyracks.algebricks.rewriter.rules.PushProjectIntoDataSourceScanRule;
@@ -65,25 +64,28 @@ import edu.uci.ics.hyracks.algebricks.re
import edu.uci.ics.hyracks.algebricks.rewriter.rules.SimpleUnnestToProductRule;
public class RewriteRuleset {
+ /**
+ * Optimizations specific to XQuery.
+ */
public final static List<IAlgebraicRewriteRule> buildXQueryNormalizationRuleCollection() {
List<IAlgebraicRewriteRule> normalization = new LinkedList<IAlgebraicRewriteRule>();
normalization.add(new SetVariableIdContextRule());
-
+
// Remove unused functions.
normalization.add(new RemoveUnusedSortDistinctNodesRule());
- normalization.add(new InlineVariablesRule(new InlineReferenceVariablePolicy()));
+ normalization.add(new InlineReferenceVariablesRule());
normalization.add(new RemoveUnusedAssignAndAggregateRule());
// TODO Fix the group by operator before putting back in the rule set.
// normalization.add(new ConvertAssignSortDistinctNodesToOperatorsRule());
normalization.add(new RemoveUnusedTreatRule());
- normalization.add(new InlineVariablesRule(new InlineReferenceVariablePolicy()));
+ normalization.add(new InlineReferenceVariablesRule());
normalization.add(new RemoveUnusedAssignAndAggregateRule());
// Find assign for scalar aggregate function followed by an aggregate operator.
normalization.add(new ConsolidateAssignAggregateRule());
- normalization.add(new InlineVariablesRule(new InlineReferenceVariablePolicy()));
+ normalization.add(new InlineReferenceVariablesRule());
normalization.add(new RemoveUnusedAssignAndAggregateRule());
// Find assign for scalar aggregate function.
@@ -91,7 +93,7 @@ public class RewriteRuleset {
// Find unnest followed by aggregate in a subplan.
normalization.add(new EliminateUnnestAggregateSubplanRule());
- normalization.add(new InlineVariablesRule(new InlineReferenceVariablePolicy()));
+ normalization.add(new InlineReferenceVariablesRule());
normalization.add(new RemoveUnusedAssignAndAggregateRule());
// Remove single tuple input subplans and merge unnest aggregate operators.
@@ -110,7 +112,7 @@ public class RewriteRuleset {
normalization.add(new IntroduceTwoStepAggregateRule());
// Used to clean up any missing noops after all the subplans have been altered.
- normalization.add(new InlineVariablesRule(new InlineReferenceVariablePolicy()));
+ normalization.add(new InlineReferenceVariablesRule());
normalization.add(new RemoveUnusedAssignAndAggregateRule());
return normalization;
@@ -118,15 +120,12 @@ public class RewriteRuleset {
/**
* When a nested data sources exist, convert the plan to use the join operator.
- *
- * @return
*/
public final static List<IAlgebraicRewriteRule> buildNestedDataSourceRuleCollection() {
List<IAlgebraicRewriteRule> xquery = new LinkedList<IAlgebraicRewriteRule>();
xquery.add(new SimpleUnnestToProductRule());
- xquery.add(new PushAssignDownThroughProductRule());
- xquery.add(new PushUnnestDownThroughProductRule());
+ xquery.add(new PushMapOperatorDownThroughProductRule());
xquery.add(new PushSubplanWithAggregateDownThroughProductRule());
xquery.add(new InlineVariablesRule());
xquery.add(new PushSelectDownRule());
Modified: incubator/vxquery/trunk/vxquery/vxquery-core/src/main/java/org/apache/vxquery/compiler/rewriter/rules/InlineReferenceVariablePolicy.java
URL: http://svn.apache.org/viewvc/incubator/vxquery/trunk/vxquery/vxquery-core/src/main/java/org/apache/vxquery/compiler/rewriter/rules/InlineReferenceVariablePolicy.java?rev=1538066&r1=1538065&r2=1538066&view=diff
==============================================================================
--- incubator/vxquery/trunk/vxquery/vxquery-core/src/main/java/org/apache/vxquery/compiler/rewriter/rules/InlineReferenceVariablePolicy.java (original)
+++ incubator/vxquery/trunk/vxquery/vxquery-core/src/main/java/org/apache/vxquery/compiler/rewriter/rules/InlineReferenceVariablePolicy.java Fri Nov 1 21:24:32 2013
@@ -14,18 +14,11 @@
*/
package org.apache.vxquery.compiler.rewriter.rules;
-import java.util.ArrayList;
-import java.util.List;
-
-import org.apache.commons.lang3.mutable.Mutable;
+import org.apache.vxquery.compiler.rewriter.rules.InlineReferenceVariablesRule.IInlineReferenceVariablePolicy;
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.LogicalExpressionTag;
-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.SubplanOperator;
import edu.uci.ics.hyracks.algebricks.rewriter.rules.InlineVariablesRule;
/**
@@ -52,7 +45,7 @@ import edu.uci.ics.hyracks.algebricks.re
* such that plan__parent_new = {for each $v in plan__parent is replaced with $vr}
* </pre>
*/
-public class InlineReferenceVariablePolicy implements InlineVariablesRule.IInlineVariablePolicy {
+public class InlineReferenceVariablePolicy implements IInlineReferenceVariablePolicy {
@Override
public boolean isCandidateForInlining(ILogicalExpression expr) {
@@ -63,25 +56,6 @@ public class InlineReferenceVariablePoli
}
@Override
- public List<Mutable<ILogicalOperator>> descendIntoNextOperator(AbstractLogicalOperator op) {
- List<Mutable<ILogicalOperator>> descendOp = new ArrayList<Mutable<ILogicalOperator>>();
- // Descend into nested plans removing projects on the way.
- if (op.getOperatorTag() == LogicalOperatorTag.SUBPLAN) {
- SubplanOperator subplan = (SubplanOperator) op;
- for (ILogicalPlan nestedOpRef : subplan.getNestedPlans()) {
- for (Mutable<ILogicalOperator> rootOpRef : nestedOpRef.getRoots()) {
- descendOp.add(rootOpRef);
- }
- }
- }
- // Descend into children removing projects on the way.
- for (Mutable<ILogicalOperator> inputOpRef : op.getInputs()) {
- descendOp.add(inputOpRef);
- }
- return descendOp;
- }
-
- @Override
public boolean isCanidateInlineTarget(AbstractLogicalOperator op) {
return true;
}
Added: incubator/vxquery/trunk/vxquery/vxquery-core/src/main/java/org/apache/vxquery/compiler/rewriter/rules/InlineReferenceVariablesRule.java
URL: http://svn.apache.org/viewvc/incubator/vxquery/trunk/vxquery/vxquery-core/src/main/java/org/apache/vxquery/compiler/rewriter/rules/InlineReferenceVariablesRule.java?rev=1538066&view=auto
==============================================================================
--- incubator/vxquery/trunk/vxquery/vxquery-core/src/main/java/org/apache/vxquery/compiler/rewriter/rules/InlineReferenceVariablesRule.java (added)
+++ incubator/vxquery/trunk/vxquery/vxquery-core/src/main/java/org/apache/vxquery/compiler/rewriter/rules/InlineReferenceVariablesRule.java Fri Nov 1 21:24:32 2013
@@ -0,0 +1,143 @@
+/*
+ * 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 org.apache.vxquery.compiler.rewriter.rules;
+
+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.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.AssignOperator;
+import edu.uci.ics.hyracks.algebricks.rewriter.rules.InlineVariablesRule;
+
+/**
+ * Replaces variable reference expressions with their assigned function-call expression where applicable
+ * (some variables are generated by datasources).
+ * Inlining variables may enable other optimizations by allowing selects and assigns to be moved
+ * (e.g., a select may be pushed into a join to enable an efficient physical join operator).
+ *
+ * <pre>
+ * Preconditions/Assumptions:
+ * Assumes no projects are in the plan. Only inlines variables whose assigned expression is a function call
+ * (i.e., this rule ignores right-hand side constants and other variable references expressions
+ *
+ * Postconditions/Examples:
+ * All qualifying variables have been inlined.
+ *
+ * Example (simplified):
+ *
+ * Before plan:
+ * select <- [$$1 < $$2 + $$0]
+ * assign [$$2] <- [funcZ() + $$0]
+ * assign [$$0, $$1] <- [funcX(), funcY()]
+ *
+ * After plan:
+ * select <- [funcY() < funcZ() + funcX() + funcX()]
+ * assign [$$2] <- [funcZ() + funcX()]
+ * assign [$$0, $$1] <- [funcX(), funcY()]
+ * </pre>
+ */
+public class InlineReferenceVariablesRule extends InlineVariablesRule {
+
+ protected IInlineReferenceVariablePolicy policy;
+
+ public InlineReferenceVariablesRule() {
+ super();
+ policy = new InlineReferenceVariablePolicy();
+ }
+
+ public InlineReferenceVariablesRule(IInlineReferenceVariablePolicy policy) {
+ super();
+ this.policy = policy;
+ }
+
+ @Override
+ protected boolean performBottomUpAction(AbstractLogicalOperator op) throws AlgebricksException {
+ if (policy.isCanidateInlineTarget(op)) {
+ inlineVisitor.setOperator(op);
+ return op.acceptExpressionTransform(inlineVisitor);
+ }
+ return false;
+ }
+
+ @Override
+ protected boolean inlineVariables(Mutable<ILogicalOperator> opRef, IOptimizationContext context)
+ throws AlgebricksException {
+ AbstractLogicalOperator op = (AbstractLogicalOperator) opRef.getValue();
+
+ // Update mapping from variables to expressions during top-down traversal.
+ if (op.getOperatorTag() == LogicalOperatorTag.ASSIGN) {
+ AssignOperator assignOp = (AssignOperator) op;
+ List<LogicalVariable> vars = assignOp.getVariables();
+ List<Mutable<ILogicalExpression>> exprs = assignOp.getExpressions();
+ for (int i = 0; i < vars.size(); i++) {
+ ILogicalExpression expr = exprs.get(i).getValue();
+ if (policy.isCandidateForInlining(expr)) {
+ varAssignRhs.put(vars.get(i), exprs.get(i).getValue());
+ }
+ }
+ }
+
+ // Descend into children removing projects on the way.
+ boolean modified = false;
+ for (Mutable<ILogicalOperator> inputOpRef : op.getInputs()) {
+ // Descend into nested plans.
+ if (op.hasNestedPlans()) {
+ AbstractOperatorWithNestedPlans o2 = (AbstractOperatorWithNestedPlans) op;
+ for (ILogicalPlan p : o2.getNestedPlans()) {
+ for (Mutable<ILogicalOperator> rootOpRef : p.getRoots()) {
+ if (inlineVariables(rootOpRef, context)) {
+ modified = true;
+ }
+ }
+ }
+ }
+ // Children
+ if (inlineVariables(inputOpRef, context)) {
+ modified = true;
+ }
+ }
+
+ if (performBottomUpAction(op)) {
+ modified = true;
+ }
+
+ if (modified) {
+ context.computeAndSetTypeEnvironmentForOperator(op);
+ context.addToDontApplySet(this, op);
+ // Re-enable rules that we may have already tried. They could be applicable now after inlining.
+ context.removeFromAlreadyCompared(opRef.getValue());
+ }
+
+ return modified;
+ }
+
+ public static interface IInlineReferenceVariablePolicy {
+
+ public boolean isCandidateForInlining(ILogicalExpression expr);
+
+ public boolean isCanidateInlineTarget(AbstractLogicalOperator op);
+
+ }
+
+}
Propchange: incubator/vxquery/trunk/vxquery/vxquery-core/src/main/java/org/apache/vxquery/compiler/rewriter/rules/InlineReferenceVariablesRule.java
------------------------------------------------------------------------------
svn:eol-style = native
Added: incubator/vxquery/trunk/vxquery/vxquery-core/src/main/java/org/apache/vxquery/compiler/rewriter/rules/PushMapOperatorDownThroughProductRule.java
URL: http://svn.apache.org/viewvc/incubator/vxquery/trunk/vxquery/vxquery-core/src/main/java/org/apache/vxquery/compiler/rewriter/rules/PushMapOperatorDownThroughProductRule.java?rev=1538066&view=auto
==============================================================================
--- incubator/vxquery/trunk/vxquery/vxquery-core/src/main/java/org/apache/vxquery/compiler/rewriter/rules/PushMapOperatorDownThroughProductRule.java (added)
+++ incubator/vxquery/trunk/vxquery/vxquery-core/src/main/java/org/apache/vxquery/compiler/rewriter/rules/PushMapOperatorDownThroughProductRule.java Fri Nov 1 21:24:32 2013
@@ -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 org.apache.vxquery.compiler.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 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 (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;
+ }
+ }
+ }
+
+}
Propchange: incubator/vxquery/trunk/vxquery/vxquery-core/src/main/java/org/apache/vxquery/compiler/rewriter/rules/PushMapOperatorDownThroughProductRule.java
------------------------------------------------------------------------------
svn:eol-style = native