Yet more fixes and test cases for assignment inlining (JENA-780) - Don't inline out of DISTINCT/REDUCED - Ensure we don't break projections when editing out inlined assignments that were projected - Ensure that editing projections only edits the outermost projection
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 d36f036..ee2b91d 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
@@ -37,6 +37,7 @@ import com.hp.hpl.jena.sparql.algebra.Transform; import com.hp.hpl.jena.sparql.algebra.TransformCopy; import com.hp.hpl.jena.sparql.algebra.Transformer; +import com.hp.hpl.jena.sparql.algebra.op.OpDistinct; import com.hp.hpl.jena.sparql.algebra.op.OpExt; import com.hp.hpl.jena.sparql.algebra.op.OpExtend; import com.hp.hpl.jena.sparql.algebra.op.OpFilter; @@ -46,6 +47,7 @@ import com.hp.hpl.jena.sparql.algebra.op.OpMinus; import com.hp.hpl.jena.sparql.algebra.op.OpOrder; import com.hp.hpl.jena.sparql.algebra.op.OpProject; +import com.hp.hpl.jena.sparql.algebra.op.OpReduced; import com.hp.hpl.jena.sparql.algebra.op.OpTopN; import com.hp.hpl.jena.sparql.algebra.op.OpUnion; import com.hp.hpl.jena.sparql.core.Var; @@ -71,10 +73,11 @@ * </p> * <ol> * <li>Assignments where the assigned variable is used only once in a subsequent - * assignment can be in-lined</li> + * expression can be in-lined</li> * <li>Assignments where the assigned value is never used elsewhere can be * eliminated</li> * </ol> + * <h3>Eligibility for In-lining</h3> * <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 @@ -84,19 +87,45 @@ * expression is deterministic is defined by {@link ExprLib#isStable(Expr)}. * </p> * <p> + * In-lining must also respect variable scope, it is possible with a nested + * query to have an assignment in-lined out through a projection that projects + * it provided that the projection is appropriately modified. + * </p> + * <p> + * There are also various other conditions on assignments that might be eligible + * for in-lining: + * </p> + * <ul> + * <li>They cannot occur inside a n-ary operator (e.g. join, {@code UNION}, + * {@code OPTIONAL} etc.) because then in-lining would change semantics because + * an expression that previously was only valid for part of the query might + * become valid for a larger part of the query</li> + * <li>They cannot be in-lined into an {@code EXISTS} or {@code NOT EXISTS} in a + * filter</li> + * <li>They cannot be in-lined out of a {@code DISTINCT} or {@code REDUCED} + * because the assignment would be relevant for the purposes of distinctness</li> + * </ul> + * <p> + * Please see <a + * href="https://issues.apache.org/jira/browse/JENA-780">JENA-780</a> for more + * information on this. + * </p> + * <h3>In-lining Application</h3> + * <p> * Assignments may be in-lined in the following places: * </p> * <ul> - * <li>Filter Expressions</li> - * <li>Bind and Select Expressions</li> - * <li>Order By Expressions if aggressive in-lining is enabled or the assigned - * expression is a constant</li> + * <li>{@code FILTER} Expressions</li> + * <li>{@code BIND} and Project Expressions</li> + * <li>{@code ORDER BY} Expressions if aggressive in-lining is enabled or the + * assigned expression is a constant</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. + * In the case of {@code ORDER BY} we only in-line assignments when aggressive + * mode is set unless the assignment is a constant value. This is because during + * order by evaluation 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 { @@ -567,6 +596,20 @@ unsafe(); } + @Override + public void visit(OpDistinct opDistinct) { + // Inlining out through the distinct might change the results of the + // distinct + unsafe(); + } + + @Override + public void visit(OpReduced opReduced) { + // Inlining out through the reduced might change the results of the + // reduced + unsafe(); + } + private void unsafe() { // Throw out any assignments because if they would be eligible their // values can't be bound in every branch of the union and thus
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 da56116..ceddcff 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
@@ -18,6 +18,7 @@ package com.hp.hpl.jena.sparql.algebra.optimize; +import java.util.ArrayList; import java.util.List; import com.hp.hpl.jena.sparql.algebra.Op; @@ -39,6 +40,7 @@ private Var var; private Expr expr; private boolean topmostOnly = true; + private boolean aboveExtend = false; public TransformRemoveAssignment(Var var, Expr expr, boolean topmostOnly) { this.var = var; @@ -88,6 +90,9 @@ modified.add(v, orig.getExpr(v)); } } + if (modified.size() > 0 && modified.size() == orig.size()) + return null; + return modified; } @@ -96,6 +101,8 @@ VarExprList assignments = processAssignments(opExtend); if (assignments == null) return super.transform(opExtend, subOp); + + this.aboveExtend = true; // Rewrite appropriately if (this.topmostOnly) { @@ -114,14 +121,23 @@ return subOp; } } + } public Op transform(OpProject opProject, Op subOp) { if (!opProject.getVars().contains(this.var)) return super.transform(opProject, subOp); - List<Var> newVars = opProject.getVars(); + List<Var> newVars = new ArrayList<Var>(opProject.getVars()); newVars.remove(this.var); - return new OpProject(subOp, newVars); + if (this.topmostOnly) { + if (this.aboveExtend) { + return new OpProject(subOp, newVars); + } else { + return opProject; + } + } else { + return new OpProject(subOp, newVars); + } } }
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 52c6cf3..e8e97be 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
@@ -478,6 +478,30 @@ } @Test + public void ineligible_12() { + // Can't inline through a distinct + //@formatter:off + testNoChange("(project (?y)", + " (filter (exprlist ?x)", + " (distinct", + " (extend (?x true)", + " (bgp (triple ?s ?p ?o))))))"); + //@formatter:on + } + + @Test + public void ineligible_13() { + // Can't inline through a reduced + //@formatter:off + testNoChange("(project (?y)", + " (filter (exprlist ?x)", + " (reduced", + " (extend (?x true)", + " (bgp (triple ?s ?p ?o))))))"); + //@formatter:on + } + + @Test public void exists_01() { // We can't inline into an EXISTS since the assignment isn't projected // out anyway and its an n-ary operator so would change semantics @@ -587,6 +611,18 @@ } @Test + public void through_project_04() { + // Can't inline because the value is projected out + //@formatter:off + testNoChange("(project (?y)", + " (project (?x ?y)", + " (filter (exprlist ?x)", + " (extend (?x true)", + " (bgp (triple ?y <urn:pred> <urn:obj>))))))"); + //@formatter:on + } + + @Test public void no_merge_01() { // We should not merge extends //@formatter:off @@ -646,4 +682,62 @@ " (table unit))))"); //@formatter:on } + + @Test + public void scope_04() { + // Only the topmost assignment should be inlined since any deeper + // assignments are technically different variables + //@formatter:off + test(StrUtils.strjoinNL("(project (?y)", + " (filter (exprlist ?x)", + " (extend (?x true)", + " (project (?z)", + " (filter (exprlist (|| ?x (! ?x)))", + " (extend (?x false)", + " (table unit)))))))"), + "(project (?y)", + " (filter (exprlist true)", + " (project (?z)", + " (filter (exprlist (|| ?x (! ?x)))", + " (extend (?x false)", + " (table unit))))))"); + //@formatter:on + } + + @Test + public void scope_05() { + // Technically invalid query but validates that the inner projection of + // ?x blocks later in-lining + //@formatter:off + testNoChange("(project (?y)", + " (filter (exprlist ?x)", + " (extend (?x true)", + " (project (?x)", + " (filter (exprlist (|| ?x (! ?x)))", + " (extend (?x false)", + " (table unit)))))))"); + //@formatter:off + } + + @Test + public void scope_06() { + // In-lining in the outer scope should not change the inner scope + //@formatter:off + test(StrUtils.strjoinNL("(project (?y)", + " (filter (exprlist ?x)", + " (extend (?x true)", + " (project (?z)", + " (project (?x)", + " (filter (exprlist (|| ?x (! ?x)))", + " (extend (?x false)", + " (table unit))))))))"), + "(project (?y)", + " (filter (exprlist true)", + " (project (?z)", + " (project (?x)", + " (filter (exprlist (|| ?x (! ?x)))", + " (extend (?x false)", + " (table unit)))))))"); + //@formatter:off + } }