You are viewing a plain text version of this content. The canonical link for it is here.
Posted to commits@jena.apache.org by rv...@apache.org on 2015/07/07 11:24:16 UTC
[11/26] jena git commit: Further work on eliminating/inlining
assignments (JENA-780)
Further work on eliminating/inlining assignments (JENA-780)
- Support elimination/inlining to OpGroup and OpTopN
- Only eliminate/inline when expressions are stable
- Only inline into sort conditions if the expression is constant
- Expand test coverage
Project: http://git-wip-us.apache.org/repos/asf/jena/repo
Commit: http://git-wip-us.apache.org/repos/asf/jena/commit/bdcf8a60
Tree: http://git-wip-us.apache.org/repos/asf/jena/tree/bdcf8a60
Diff: http://git-wip-us.apache.org/repos/asf/jena/diff/bdcf8a60
Branch: refs/heads/jena2
Commit: bdcf8a6056092b04bf644607b6176afd0e834544
Parents: 57cf5dd
Author: Rob Vesse <rv...@apache.org>
Authored: Mon Jul 6 14:37:58 2015 +0100
Committer: Rob Vesse <rv...@apache.org>
Committed: Mon Jul 6 14:39:44 2015 +0100
----------------------------------------------------------------------
.../optimize/TransformEliminateAssignments.java | 193 ++++++++++++++++---
.../optimize/TransformRemoveAssignment.java | 18 ++
.../algebra/optimize/VariableUsagePopper.java | 18 ++
.../TestTransformEliminateAssignments.java | 134 ++++++++++---
4 files changed, 317 insertions(+), 46 deletions(-)
----------------------------------------------------------------------
http://git-wip-us.apache.org/repos/asf/jena/blob/bdcf8a60/jena-arq/src/main/java/com/hp/hpl/jena/sparql/algebra/optimize/TransformEliminateAssignments.java
----------------------------------------------------------------------
diff --git a/jena-arq/src/main/java/com/hp/hpl/jena/sparql/algebra/optimize/TransformEliminateAssignments.java b/jena-arq/src/main/java/com/hp/hpl/jena/sparql/algebra/optimize/TransformEliminateAssignments.java
index c9bdb7c..91dc435 100644
--- a/jena-arq/src/main/java/com/hp/hpl/jena/sparql/algebra/optimize/TransformEliminateAssignments.java
+++ b/jena-arq/src/main/java/com/hp/hpl/jena/sparql/algebra/optimize/TransformEliminateAssignments.java
@@ -44,45 +44,95 @@ import com.hp.hpl.jena.sparql.algebra.op.OpTopN;
import com.hp.hpl.jena.sparql.core.Var;
import com.hp.hpl.jena.sparql.core.VarExprList;
import com.hp.hpl.jena.sparql.expr.Expr;
+import com.hp.hpl.jena.sparql.expr.ExprAggregator;
+import com.hp.hpl.jena.sparql.expr.ExprLib;
import com.hp.hpl.jena.sparql.expr.ExprList;
+import com.hp.hpl.jena.sparql.expr.ExprTransform;
import com.hp.hpl.jena.sparql.expr.ExprTransformSubstitute;
import com.hp.hpl.jena.sparql.expr.ExprTransformer;
import com.hp.hpl.jena.sparql.expr.ExprVars;
+import com.hp.hpl.jena.sparql.expr.NodeValue;
/**
- * A transform that tries to remove unecessary assignments
+ * A transform that tries to in-line/eliminate assignments
* <p>
- * There are two classes of assignments that we can try and remove:
+ * There are two classes of assignments that we can try and in-line/eliminate:
* </p>
* <ol>
* <li>Assignments where the assigned variable is used only once in a subsequent
- * assignment</li>
- * <li>Assignments where the assigned value is never used elsewhere</li>
+ * assignment can be in-lined</li>
+ * <li>Assignments where the assigned value is never used elsewhere can be
+ * eliminated</li>
* </ol>
* <p>
* Both of these changes can only happen inside of projections as otherwise we
* have to assume that the user may need the resulting variable and thus we
- * leave the assignment alone.
+ * leave the assignment alone. Assignments to be in-lined must also be
+ * deterministic i.e. moving their placement in the query and thus the possible
+ * solutions they might operate must not change their outputs. Whether an
+ * expression is deterministic is defined by {@link ExprLib#isStable(Expr)}.
+ * </p>
+ * <p>
+ * Assignments may be in-lined in the following places:
+ * </p>
+ * <ul>
+ * <li>Filter Expressions</li>
+ * <li>Bind and Select Expressions</li>
+ * <li>Group By Expressions</li>
+ * <li>Order By Expressions if aggressive in-lining is enabled</li>
+ * </ul>
+ * <p>
+ * In the case of order by we only in-line assignments when aggressive mode is
+ * set as the realities of order by are that expressions may be recomputed
+ * multiple times and so in-lining may actually hurt performance in those cases
+ * unless the expression to be in-lined is itself a constant.
* </p>
- *
*/
public class TransformEliminateAssignments extends TransformCopy {
public static Op eliminate(Op op) {
+ return eliminate(op, false);
+ }
+
+ public static Op eliminate(Op op, boolean aggressive) {
AssignmentTracker tracker = new AssignmentTracker();
AssignmentPusher pusher = new AssignmentPusher(tracker);
AssignmentPopper popper = new AssignmentPopper(tracker);
- Transform transform = new TransformEliminateAssignments(tracker, pusher, popper);
+ Transform transform = new TransformEliminateAssignments(tracker, pusher, popper, aggressive);
return Transformer.transform(transform, op, pusher, popper);
}
- private OpVisitor before, after;
- private AssignmentTracker tracker;
+ private final OpVisitor before, after;
+ private final AssignmentTracker tracker;
+ private final boolean aggressive;
private TransformEliminateAssignments(AssignmentTracker tracker, OpVisitor before, OpVisitor after) {
+ this(tracker, before, after, false);
+ }
+
+ private TransformEliminateAssignments(AssignmentTracker tracker, OpVisitor before, OpVisitor after,
+ boolean aggressive) {
this.tracker = tracker;
this.before = before;
+ this.after = after;
+ this.aggressive = aggressive;
+ }
+
+ protected boolean canInline(Expr e) {
+ return ExprLib.isStable(e);
+ }
+
+ protected boolean shouldInline(Expr e) {
+ // Inline everything when being aggressive
+ if (this.aggressive)
+ return true;
+
+ if (e == null)
+ return false;
+
+ // If not being aggressive only inline if the expression is a constant
+ return e.isConstant() || e instanceof NodeValue;
}
protected boolean isApplicable() {
@@ -121,13 +171,12 @@ public class TransformEliminateAssignments extends TransformCopy {
// Usage count will be 2 if we can eliminate the assignment
// First usage is when it is introduced by the assignment and the
// second is when it is used now in this filter
- if (this.tracker.getUsageCount(var) == 2 && this.tracker.getAssignments().containsKey(var)) {
+ Expr e = getAssignExpr(var);
+ if (this.tracker.getUsageCount(var) == 2 && hasAssignment(var) && canInline(e)) {
// Can go back and eliminate that assignment
- subOp = Transformer.transform(
- new TransformRemoveAssignment(var, this.tracker.getAssignments().get(var)), subOp);
+ subOp = eliminateAssignment(subOp, var);
// Replace the variable usage with the expression
- exprs = ExprTransformer.transform(
- new ExprTransformSubstitute(var, this.tracker.getAssignments().get(var)), exprs);
+ exprs = ExprTransformer.transform(new ExprTransformSubstitute(var, e), exprs);
this.tracker.getAssignments().remove(var);
modified = true;
}
@@ -141,6 +190,14 @@ public class TransformEliminateAssignments extends TransformCopy {
return super.transform(opFilter, subOp);
}
+ private boolean hasAssignment(Var var) {
+ return this.tracker.getAssignments().containsKey(var);
+ }
+
+ private Expr getAssignExpr(Var var) {
+ return this.tracker.getAssignments().get(var);
+ }
+
@Override
public Op transform(OpExtend opExtend, Op subOp) {
// No point tracking assignments if not in a projection as we can't
@@ -152,6 +209,9 @@ public class TransformEliminateAssignments extends TransformCopy {
// Track the assignments for future reference
this.tracker.putAssignments(opExtend.getVarExprList());
+ // TODO Could also eliminate assignments where the value is only used in
+ // a subsequent assignment
+
// See if there are any assignments we can eliminate entirely i.e. those
// where the assigned value is never used
VarExprList assignments = processUnused(opExtend.getVarExprList());
@@ -203,11 +263,12 @@ public class TransformEliminateAssignments extends TransformCopy {
// Usage count will be 2 if we can eliminate the assignment
// First usage is when it is introduced by the assignment and the
// second is when it is used now in this filter
- if (this.tracker.getUsageCount(var) == 2 && this.tracker.getAssignments().containsKey(var)) {
+ Expr e = getAssignExpr(var);
+ if (this.tracker.getUsageCount(var) == 2 && hasAssignment(var) && canInline(e) && shouldInline(e)) {
// Can go back and eliminate that assignment
- subOp = Transformer.transform(
- new TransformRemoveAssignment(var, this.tracker.getAssignments().get(var)), subOp);
- // Replace the variable usage with the expression within the sort conditions
+ subOp = eliminateAssignment(subOp, var);
+ // Replace the variable usage with the expression within the
+ // sort conditions
conditions = processConditions(opOrder.getConditions(), conditions, var);
this.tracker.getAssignments().remove(var);
}
@@ -228,25 +289,113 @@ public class TransformEliminateAssignments extends TransformCopy {
for (SortCondition cond : inputConditions) {
Expr e = cond.getExpression();
- e = ExprTransformer.transform(new ExprTransformSubstitute(var, this.tracker.getAssignments().get(var)), e);
+ e = ExprTransformer.transform(new ExprTransformSubstitute(var, getAssignExpr(var)), e);
outputConditions.add(new SortCondition(e, cond.getDirection()));
}
-
+
return outputConditions;
}
@Override
public Op transform(OpTopN opTop, Op subOp) {
- // TODO Auto-generated method stub
+ if (!this.isApplicable())
+ return super.transform(opTop, subOp);
+
+ // See what vars are used in the sort conditions
+ Collection<Var> vars = new ArrayList<>();
+ for (SortCondition cond : opTop.getConditions()) {
+ ExprVars.varsMentioned(vars, cond.getExpression());
+ }
+
+ // Are any of these vars single usage?
+ List<SortCondition> conditions = null;
+ for (Var var : vars) {
+ // Usage count will be 2 if we can eliminate the assignment
+ // First usage is when it is introduced by the assignment and the
+ // second is when it is used now in this filter
+ Expr e = getAssignExpr(var);
+ if (this.tracker.getUsageCount(var) == 2 && hasAssignment(var) && canInline(e) && shouldInline(e)) {
+ // Can go back and eliminate that assignment
+ subOp = eliminateAssignment(subOp, var);
+ // Replace the variable usage with the expression within the
+ // sort conditions
+ conditions = processConditions(opTop.getConditions(), conditions, var);
+ this.tracker.getAssignments().remove(var);
+ }
+ }
+
+ // Create a new order if we've substituted any expressions
+ if (conditions != null) {
+ return new OpTopN(subOp, opTop.getLimit(), conditions);
+ }
+
return super.transform(opTop, subOp);
}
@Override
public Op transform(OpGroup opGroup, Op subOp) {
- // TODO Auto-generated method stub
+ if (!this.isApplicable())
+ return super.transform(opGroup, subOp);
+
+ // See what vars are used in the filter
+ Collection<Var> vars = new ArrayList<>();
+ VarExprList exprs = new VarExprList(opGroup.getGroupVars());
+ List<ExprAggregator> aggs = new ArrayList<ExprAggregator>(opGroup.getAggregators());
+ for (Expr expr : exprs.getExprs().values()) {
+ ExprVars.varsMentioned(vars, expr);
+ }
+
+ // Are any of these vars single usage?
+ boolean modified = false;
+ for (Var var : vars) {
+ // Usage count will be 2 if we can eliminate the assignment
+ // First usage is when it is introduced by the assignment and the
+ // second is when it is used now in this group by
+ Expr e = getAssignExpr(var);
+ if (this.tracker.getUsageCount(var) == 2 && hasAssignment(var) && canInline(e)) {
+ // Can go back and eliminate that assignment
+ subOp = eliminateAssignment(subOp, var);
+ // Replace the variable usage with the expression in both the
+ // expressions and the aggregators
+ ExprTransform transform = new ExprTransformSubstitute(var, e);
+ exprs = processVarExprList(exprs, transform);
+ aggs = processAggregators(aggs, transform);
+ this.tracker.getAssignments().remove(var);
+ modified = true;
+ }
+ }
+
+ // Create a new group by if we've substituted any expressions
+ if (modified) {
+ return new OpGroup(subOp, exprs, aggs);
+ }
+
return super.transform(opGroup, subOp);
}
+ private Op eliminateAssignment(Op subOp, Var var) {
+ return Transformer.transform(new TransformRemoveAssignment(var, getAssignExpr(var)), subOp);
+ }
+
+ private VarExprList processVarExprList(VarExprList exprs, ExprTransform transform) {
+ VarExprList newExprs = new VarExprList();
+ for (Var v : exprs.getVars()) {
+ Expr e = exprs.getExpr(v);
+ Expr e2 = ExprTransformer.transform(transform, e);
+ newExprs.add(v, e2);
+ }
+ return newExprs;
+ }
+
+ private List<ExprAggregator> processAggregators(List<ExprAggregator> aggs, ExprTransform transform) {
+ List<ExprAggregator> newAggs = new ArrayList<ExprAggregator>();
+ for (ExprAggregator agg : aggs) {
+ ExprAggregator e2 = (ExprAggregator) ExprTransformer.transform(transform, agg);
+ newAggs.add(e2);
+ }
+ return newAggs;
+ }
+
private static class AssignmentTracker extends VariableUsageTracker {
private Map<Var, Expr> assignments = new HashMap<>();
http://git-wip-us.apache.org/repos/asf/jena/blob/bdcf8a60/jena-arq/src/main/java/com/hp/hpl/jena/sparql/algebra/optimize/TransformRemoveAssignment.java
----------------------------------------------------------------------
diff --git a/jena-arq/src/main/java/com/hp/hpl/jena/sparql/algebra/optimize/TransformRemoveAssignment.java b/jena-arq/src/main/java/com/hp/hpl/jena/sparql/algebra/optimize/TransformRemoveAssignment.java
index dba9271..d7c08d4 100644
--- a/jena-arq/src/main/java/com/hp/hpl/jena/sparql/algebra/optimize/TransformRemoveAssignment.java
+++ b/jena-arq/src/main/java/com/hp/hpl/jena/sparql/algebra/optimize/TransformRemoveAssignment.java
@@ -1,3 +1,21 @@
+/*
+ * Licensed to the Apache Software Foundation (ASF) under one
+ * or more contributor license agreements. See the NOTICE file
+ * distributed with this work for additional information
+ * regarding copyright ownership. The ASF licenses this file
+ * to you 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 at
+ *
+ * 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 com.hp.hpl.jena.sparql.algebra.optimize;
import com.hp.hpl.jena.sparql.algebra.Op;
http://git-wip-us.apache.org/repos/asf/jena/blob/bdcf8a60/jena-arq/src/main/java/com/hp/hpl/jena/sparql/algebra/optimize/VariableUsagePopper.java
----------------------------------------------------------------------
diff --git a/jena-arq/src/main/java/com/hp/hpl/jena/sparql/algebra/optimize/VariableUsagePopper.java b/jena-arq/src/main/java/com/hp/hpl/jena/sparql/algebra/optimize/VariableUsagePopper.java
index e73bfee..73e7ec9 100644
--- a/jena-arq/src/main/java/com/hp/hpl/jena/sparql/algebra/optimize/VariableUsagePopper.java
+++ b/jena-arq/src/main/java/com/hp/hpl/jena/sparql/algebra/optimize/VariableUsagePopper.java
@@ -1,3 +1,21 @@
+/*
+ * Licensed to the Apache Software Foundation (ASF) under one
+ * or more contributor license agreements. See the NOTICE file
+ * distributed with this work for additional information
+ * regarding copyright ownership. The ASF licenses this file
+ * to you 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 at
+ *
+ * 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 com.hp.hpl.jena.sparql.algebra.optimize;
import java.util.Collection;
http://git-wip-us.apache.org/repos/asf/jena/blob/bdcf8a60/jena-arq/src/test/java/com/hp/hpl/jena/sparql/algebra/optimize/TestTransformEliminateAssignments.java
----------------------------------------------------------------------
diff --git a/jena-arq/src/test/java/com/hp/hpl/jena/sparql/algebra/optimize/TestTransformEliminateAssignments.java b/jena-arq/src/test/java/com/hp/hpl/jena/sparql/algebra/optimize/TestTransformEliminateAssignments.java
index 2f2ced9..163ce8c 100644
--- a/jena-arq/src/test/java/com/hp/hpl/jena/sparql/algebra/optimize/TestTransformEliminateAssignments.java
+++ b/jena-arq/src/test/java/com/hp/hpl/jena/sparql/algebra/optimize/TestTransformEliminateAssignments.java
@@ -32,13 +32,17 @@ import com.hp.hpl.jena.sparql.sse.SSE;
public class TestTransformEliminateAssignments {
private void test(String input, String... output) {
+ test(input, false, output);
+ }
+
+ private void test(String input, boolean aggressive, String... output) {
Op original = SSE.parseOp(input);
- test(original, output);
+ test(original, aggressive, output);
}
- private void test(Op original, String... output) {
+ private void test(Op original, boolean aggressive, String... output) {
// Transform
- Op actual = TransformEliminateAssignments.eliminate(original);
+ Op actual = TransformEliminateAssignments.eliminate(original, aggressive);
// Check results
if (output == null) {
@@ -51,17 +55,12 @@ public class TestTransformEliminateAssignments {
}
}
- @SuppressWarnings("unused")
- private void testNoChange(String input) {
- test(input, (String[]) null);
- }
-
private void testNoChange(String... input) {
test(StrUtils.strjoinNL(input), (String[]) null);
}
@Test
- public void eliminate_single_use_extend_01() {
+ public void single_use_extend_01() {
// Assigned variable used only once can substitute expression for the
// later usage of the variable
// However we must be inside a projection as otherwise the assigned
@@ -78,7 +77,7 @@ public class TestTransformEliminateAssignments {
}
@Test
- public void eliminate_single_use_extend_02() {
+ public void single_use_extend_02() {
// Assignment for ?y can be removed because it is never used
// However we must be inside a projection as otherwise the assigned
// variable would be visible and we couldn't eliminate the assignment
@@ -92,9 +91,9 @@ public class TestTransformEliminateAssignments {
" (table unit)))");
//@formatter:on
}
-
+
@Test
- public void eliminate_single_use_extend_03() {
+ public void single_use_extend_03() {
// Assigned variable used only once can substitute expression for the
// later usage of the variable
// However we must be inside a projection as otherwise the assigned
@@ -111,7 +110,92 @@ public class TestTransformEliminateAssignments {
}
@Test
- public void single_use_extend_unchanged_01() {
+ public void single_use_extend_complex_01() {
+ // Assigned variable used only once can substitute expression for the
+ // later usage of the variable
+ // BUT we won't do this by default for complex expressions where they
+ // are used in a place where they could be evaluated multiple times
+ //@formatter:off
+ testNoChange(StrUtils.strjoinNL("(project (?y)",
+ " (order (?x)",
+ " (extend (?x (contains 'foo' 'bar'))",
+ " (table unit))))"));
+ //@formatter:on
+ }
+
+ @Test
+ public void single_use_extend_complex_02() {
+ // Assigned variable used only once can substitute expression for the
+ // later usage of the variable
+ // BUT we won't do this by default for complex expressions where they
+ // are used in a place where they could be evaluated multiple times
+ // EXCEPT if we are doing aggressive in-lining
+ //@formatter:off
+ test(StrUtils.strjoinNL("(project (?y)",
+ " (order (?x)",
+ " (extend (?x (contains 'foo' 'bar'))",
+ " (table unit))))"),
+ true,
+ "(project (?y)",
+ " (order ((contains 'foo' 'bar'))",
+ " (table unit)))");
+ //@formatter:on
+ }
+
+ @Test
+ public void single_use_extend_unstable_01() {
+ // Assigned variable used only once can substitute expression for the
+ // later usage of the variable
+ // EXCEPT if the expression is unstable in which case we leave it alone
+ //@formatter:off
+ testNoChange(StrUtils.strjoinNL("(project (?y)",
+ " (filter (exprlist ?x)",
+ " (extend (?x (rand))",
+ " (table unit))))"));
+ //@formatter:on
+ }
+
+ @Test
+ public void single_use_extend_unstable_02() {
+ // Assigned variable used only once can substitute expression for the
+ // later usage of the variable
+ // EXCEPT if the expression is unstable in which case we leave it alone
+ //@formatter:off
+ testNoChange(StrUtils.strjoinNL("(project (?y)",
+ " (filter (exprlist ?x)",
+ " (extend (?x (uuid))",
+ " (table unit))))"));
+ //@formatter:on
+ }
+
+ @Test
+ public void single_use_extend_unstable_03() {
+ // Assigned variable used only once can substitute expression for the
+ // later usage of the variable
+ // EXCEPT if the expression is unstable in which case we leave it alone
+ //@formatter:off
+ testNoChange(StrUtils.strjoinNL("(project (?y)",
+ " (filter (exprlist ?x)",
+ " (extend (?x (struuid))",
+ " (table unit))))"));
+ //@formatter:on
+ }
+
+ @Test
+ public void single_use_extend_unstable_04() {
+ // Assigned variable used only once can substitute expression for the
+ // later usage of the variable
+ // EXCEPT if the expression is unstable in which case we leave it alone
+ //@formatter:off
+ testNoChange(StrUtils.strjoinNL("(project (?y)",
+ " (filter (exprlist ?x)",
+ " (extend (?x (bnode))",
+ " (table unit))))"));
+ //@formatter:on
+ }
+
+ @Test
+ public void single_use_extend_outside_projection_01() {
// Cannot eliminate as there is no projection so the assigned variable
// is visible even though in the algebra given it is used only once
//@formatter:off
@@ -122,7 +206,7 @@ public class TestTransformEliminateAssignments {
}
@Test
- public void single_use_extend_unchanged_02() {
+ public void single_use_extend_outside_projection_02() {
// Cannot eliminate as there is no projection so the assigned variable
// is visible even though in the algebra given it is used only once
//@formatter:off
@@ -133,26 +217,28 @@ public class TestTransformEliminateAssignments {
}
@Test
- public void multi_use_extend_unchanged_01() {
+ public void multi_use_extend_01() {
// As the assigned variable is used multiple times we leave the
// assignment alone
//@formatter:off
- testNoChange("(filter (> (* ?x ?x) 16)",
- " (extend (?x 3)",
- " (table unit)))");
+ testNoChange("(project (?y)",
+ " (filter (> (* ?x ?x) 16)",
+ " (extend (?x 3)",
+ " (table unit))))");
//@formatter:on
}
@Test
- public void multi_use_extend_unchanged_02() {
+ public void multi_use_extend_02() {
// Because the value of the assignment is used in multiple places we
// leave the assignment alone
//@formatter:off
- testNoChange("(filter (exprlist ?x)",
- " (join",
- " (extend (?x true)",
- " (table unit))",
- " (bgp (triple ?x ?y ?z))))");
+ testNoChange("(project (?y)",
+ " (filter (exprlist ?x)",
+ " (join",
+ " (extend (?x true)",
+ " (table unit))",
+ " (bgp (triple ?x ?y ?z)))))");
//@formatter:on
}