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/06 16:49:13 UTC
[2/3] jena git commit: Improve assignment inlining (JENA-780)
Improve assignment inlining (JENA-780)
Fixes a bug in how assignments were eliminated/inlined from usages in
extend and generally improves how we cope with extend such that we can
inline expressions where they are defined in the same extend as they are
used.
Project: http://git-wip-us.apache.org/repos/asf/jena/repo
Commit: http://git-wip-us.apache.org/repos/asf/jena/commit/985b995b
Tree: http://git-wip-us.apache.org/repos/asf/jena/tree/985b995b
Diff: http://git-wip-us.apache.org/repos/asf/jena/diff/985b995b
Branch: refs/heads/eliminate-assignments
Commit: 985b995be1f21c7ee0627a00326866b27babfd03
Parents: bdcf8a6
Author: Rob Vesse <rv...@apache.org>
Authored: Mon Jul 6 15:29:22 2015 +0100
Committer: Rob Vesse <rv...@apache.org>
Committed: Mon Jul 6 15:29:22 2015 +0100
----------------------------------------------------------------------
.../optimize/TransformEliminateAssignments.java | 73 ++++++---
.../TestTransformEliminateAssignments.java | 160 ++++++++++++++++---
2 files changed, 193 insertions(+), 40 deletions(-)
----------------------------------------------------------------------
http://git-wip-us.apache.org/repos/asf/jena/blob/985b995b/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 91dc435..4d59fc3 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
@@ -120,17 +120,19 @@ public class TransformEliminateAssignments extends TransformCopy {
}
protected boolean canInline(Expr e) {
+ if (e == null)
+ return false;
return ExprLib.isStable(e);
}
protected boolean shouldInline(Expr e) {
+ if (e == null)
+ return false;
+
// 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;
}
@@ -214,13 +216,47 @@ public class TransformEliminateAssignments extends TransformCopy {
// 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());
- if (assignments == null)
- return super.transform(opExtend, subOp);
+ VarExprList unusedAssignments = processUnused(opExtend.getVarExprList());
+ VarExprList newAssignments = new VarExprList();
+ for (Var assignVar : opExtend.getVarExprList().getVars()) {
+ // If unused eliminate
+ if (unusedAssignments != null && unusedAssignments.contains(assignVar))
+ continue;
+
+ Expr currExpr = opExtend.getVarExprList().getExpr(assignVar);
+
+ // See what vars are used in the current expression
+ Collection<Var> vars = new ArrayList<>();
+ ExprVars.varsMentioned(vars, currExpr);
+
+ 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 used in another assignment
+ 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 within
+ // expression
+ currExpr = ExprTransformer.transform(new ExprTransformSubstitute(var, e), currExpr);
+ this.tracker.getAssignments().remove(var);
+
+ // If the assignment to be eliminated was introduced by the
+ // extend we are processing need to remove it from the
+ // VarExprList we are currently building
+ if (newAssignments.contains(var) && newAssignments.getExpr(var).equals(e)) {
+ newAssignments.getVars().remove(var);
+ newAssignments.getExprs().remove(var);
+ }
+ }
+ }
+ newAssignments.add(assignVar, currExpr);
+ }
- // Can eliminate some assignments entirely
- if (assignments.size() > 0) {
- return OpExtend.extend(subOp, assignments);
+ // May be able to eliminate the extend entirely in some cases
+ if (newAssignments.size() > 0) {
+ return OpExtend.extend(subOp, newAssignments);
} else {
return subOp;
}
@@ -230,20 +266,17 @@ public class TransformEliminateAssignments extends TransformCopy {
if (CollectionUtils.disjoint(assignments.getVars(), this.tracker.getAssignments().keySet()))
return null;
- VarExprList modified = new VarExprList();
+ VarExprList singleUse = new VarExprList();
for (Var var : assignments.getVars()) {
- // If an assignment is used more than once then it must be preserved
- // for now
- if (this.tracker.getUsageCount(var) > 1)
- modified.add(var, assignments.getExpr(var));
+ if (this.tracker.getUsageCount(var) == 1)
+ singleUse.add(var, assignments.getExpr(var));
}
-
- // If all assignments are used more than once then there are no changes
- // and we return null
- if (modified.size() == assignments.size())
+
+ // If nothing is single use
+ if (singleUse.size() == 0)
return null;
- return modified;
+ return singleUse;
}
@Override
@@ -262,7 +295,7 @@ public class TransformEliminateAssignments extends TransformCopy {
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
+ // second is when it is used now in this order expression
Expr e = getAssignExpr(var);
if (this.tracker.getUsageCount(var) == 2 && hasAssignment(var) && canInline(e) && shouldInline(e)) {
// Can go back and eliminate that assignment
http://git-wip-us.apache.org/repos/asf/jena/blob/985b995b/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 163ce8c..cd0904b 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
@@ -56,11 +56,48 @@ public class TestTransformEliminateAssignments {
}
private void testNoChange(String... input) {
- test(StrUtils.strjoinNL(input), (String[]) null);
+ testNoChange(false, input);
+ }
+
+ private void testNoChangeAggressive(String... input) {
+ testNoChange(true, input);
+ }
+
+ private void testNoChange(boolean aggressive, String... input) {
+ test(StrUtils.strjoinNL(input), aggressive, (String[]) null);
+ }
+
+ @Test
+ public void unused_01() {
+ // Assignments never used can be eliminated
+ // However we must be inside a projection as otherwise the assigned
+ // variable would be visible and we couldn't eliminate the assignment
+ //@formatter:off
+ test(StrUtils.strjoinNL("(project (?y)",
+ " (extend (?x true)",
+ " (table unit)))"),
+ "(project (?y)",
+ " (table unit))");
+ //@formatter:on
+ }
+
+ @Test
+ public void unused_02() {
+ // Assignments never used can be eliminated
+ // However we must be inside a projection as otherwise the assigned
+ // variable would be visible and we couldn't eliminate the assignment
+ //@formatter:off
+ test(StrUtils.strjoinNL("(project (?y)",
+ " (extend ((?x true) (?y false))",
+ " (table unit)))"),
+ "(project (?y)",
+ " (extend (?y false)",
+ " (table unit)))");
+ //@formatter:on
}
@Test
- public void single_use_extend_01() {
+ public void filter_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
@@ -77,8 +114,9 @@ public class TestTransformEliminateAssignments {
}
@Test
- public void single_use_extend_02() {
+ public void filter_02() {
// Assignment for ?y can be removed because it is never used
+ // Assignment for ?x can be in-lined
// However we must be inside a projection as otherwise the assigned
// variable would be visible and we couldn't eliminate the assignment
//@formatter:off
@@ -93,7 +131,23 @@ public class TestTransformEliminateAssignments {
}
@Test
- public void single_use_extend_03() {
+ public void 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
+ // variable would be visible and we couldn't eliminate the assignment
+ //@formatter:off
+ test(StrUtils.strjoinNL("(project (?y)",
+ " (extend ((?x true) (?y ?x))",
+ " (table unit)))"),
+ "(project (?y)",
+ " (extend (?y true)",
+ " (table unit)))");
+ //@formatter:on
+ }
+
+ @Test
+ public void orderby_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
@@ -110,7 +164,7 @@ public class TestTransformEliminateAssignments {
}
@Test
- public void single_use_extend_complex_01() {
+ public void orderby_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
@@ -124,7 +178,7 @@ public class TestTransformEliminateAssignments {
}
@Test
- public void single_use_extend_complex_02() {
+ public void orderby_03() {
// 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
@@ -141,9 +195,9 @@ public class TestTransformEliminateAssignments {
" (table unit)))");
//@formatter:on
}
-
+
@Test
- public void single_use_extend_unstable_01() {
+ public void filter_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
@@ -154,9 +208,9 @@ public class TestTransformEliminateAssignments {
" (table unit))))"));
//@formatter:on
}
-
+
@Test
- public void single_use_extend_unstable_02() {
+ public void filter_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
@@ -167,9 +221,9 @@ public class TestTransformEliminateAssignments {
" (table unit))))"));
//@formatter:on
}
-
+
@Test
- public void single_use_extend_unstable_03() {
+ public void filter_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
@@ -180,9 +234,9 @@ public class TestTransformEliminateAssignments {
" (table unit))))"));
//@formatter:on
}
-
+
@Test
- public void single_use_extend_unstable_04() {
+ public void filter_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
@@ -195,7 +249,59 @@ public class TestTransformEliminateAssignments {
}
@Test
- public void single_use_extend_outside_projection_01() {
+ public void orderby_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
+ testNoChangeAggressive(StrUtils.strjoinNL("(project (?y)",
+ " (order (?x)",
+ " (extend (?x (rand))",
+ " (table unit))))"));
+ //@formatter:on
+ }
+
+ @Test
+ public void orderby_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
+ testNoChangeAggressive(StrUtils.strjoinNL("(project (?y)",
+ " (order (?x)",
+ " (extend (?x (uuid))",
+ " (table unit))))"));
+ //@formatter:on
+ }
+
+ @Test
+ public void orderby_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
+ testNoChangeAggressive(StrUtils.strjoinNL("(project (?y)",
+ " (order (?x)",
+ " (extend (?x (struuid))",
+ " (table unit))))"));
+ //@formatter:on
+ }
+
+ @Test
+ public void orderby_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
+ testNoChangeAggressive(StrUtils.strjoinNL("(project (?y)",
+ " (order (?x)",
+ " (extend (?x (bnode))",
+ " (table unit))))"));
+ //@formatter:on
+ }
+
+ @Test
+ public void ineligible_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
@@ -206,7 +312,7 @@ public class TestTransformEliminateAssignments {
}
@Test
- public void single_use_extend_outside_projection_02() {
+ public void ineligible_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
@@ -217,7 +323,7 @@ public class TestTransformEliminateAssignments {
}
@Test
- public void multi_use_extend_01() {
+ public void ineligible_03() {
// As the assigned variable is used multiple times we leave the
// assignment alone
//@formatter:off
@@ -229,7 +335,7 @@ public class TestTransformEliminateAssignments {
}
@Test
- public void multi_use_extend_02() {
+ public void ineligible_04() {
// Because the value of the assignment is used in multiple places we
// leave the assignment alone
//@formatter:off
@@ -243,7 +349,21 @@ public class TestTransformEliminateAssignments {
}
@Test
- public void scoped_use_extend_01() {
+ public void scope_01() {
+ // If the assignment is out of scope by the time it is used in the outer
+ // scope then we can't substitute it out there
+ // In this test the outer ?x is technically different from the inner ?x
+ // anyway because of the projection
+ //@formatter:off
+ testNoChange(StrUtils.strjoinNL("(filter (exprlist ?x)",
+ " (project (?x ?y)",
+ " (extend (?x true)",
+ " (table unit))))"));
+ //@formatter:on
+ }
+
+ @Test
+ public void scope_02() {
// If the assignment is out of scope by the time it is used in the outer
// scope then we can't substitute it out there
// However if the scoping means the value is never used we can instead
@@ -260,7 +380,7 @@ public class TestTransformEliminateAssignments {
}
@Test
- public void scoped_use_extend_02() {
+ public void scope_03() {
// If the assignment is out of scope by the time it is used in the outer
// scope then we can't substitute it out there
// However in this case we can substitute it in the inner scope