Author: rvesse
Date: Tue Nov 12 16:55:16 2013
New Revision: 1541139
URL: http://svn.apache.org/r1541139
Log:
Re-enable TransformDistinctToReduced making it much stricter about the kinds of
queries it will optimize.
Expands the unit tests to cover various scenarios identified in the associated
bug (JENA-587)
Modified:
jena/trunk/jena-arq/src/main/java/com/hp/hpl/jena/sparql/algebra/optimize/Optimize.java
jena/trunk/jena-arq/src/main/java/com/hp/hpl/jena/sparql/algebra/optimize/TransformDistinctToReduced.java
jena/trunk/jena-arq/src/test/java/com/hp/hpl/jena/sparql/algebra/optimize/TestOptimizer.java
Modified:
jena/trunk/jena-arq/src/main/java/com/hp/hpl/jena/sparql/algebra/optimize/Optimize.java
URL:
http://svn.apache.org/viewvc/jena/trunk/jena-arq/src/main/java/com/hp/hpl/jena/sparql/algebra/optimize/Optimize.java?rev=1541139&r1=1541138&r2=1541139&view=diff
==============================================================================
---
jena/trunk/jena-arq/src/main/java/com/hp/hpl/jena/sparql/algebra/optimize/Optimize.java
(original)
+++
jena/trunk/jena-arq/src/main/java/com/hp/hpl/jena/sparql/algebra/optimize/Optimize.java
Tue Nov 12 16:55:16 2013
@@ -201,8 +201,9 @@ public class Optimize implements Rewrite
if ( context.isTrueOrUndef(ARQ.optOrderByDistinctApplication) )
op = apply("Apply DISTINCT prior to ORDER BY where possible", new
TransformOrderByDistinctAppplication(), op);
- // JENA-587 Temporarily only used when explicitly enabled, needs
reworking to be stricter
- if ( context.isTrue(ARQ.optDistinctToReduced) )
+ // Transform some DISTINCT to REDUCED, slightly more liberal transform
that ORDER BY+DISTINCT application
+ // but doesn't improve performance as much though should keep memory
usage down
+ if ( context.isTrueOrUndef(ARQ.optDistinctToReduced) )
op = apply("Distinct replaced with reduced", new
TransformDistinctToReduced(), op) ;
// Convert paths to triple patterns.
Modified:
jena/trunk/jena-arq/src/main/java/com/hp/hpl/jena/sparql/algebra/optimize/TransformDistinctToReduced.java
URL:
http://svn.apache.org/viewvc/jena/trunk/jena-arq/src/main/java/com/hp/hpl/jena/sparql/algebra/optimize/TransformDistinctToReduced.java?rev=1541139&r1=1541138&r2=1541139&view=diff
==============================================================================
---
jena/trunk/jena-arq/src/main/java/com/hp/hpl/jena/sparql/algebra/optimize/TransformDistinctToReduced.java
(original)
+++
jena/trunk/jena-arq/src/main/java/com/hp/hpl/jena/sparql/algebra/optimize/TransformDistinctToReduced.java
Tue Nov 12 16:55:16 2013
@@ -18,12 +18,17 @@
package com.hp.hpl.jena.sparql.algebra.optimize;
+import java.util.HashSet;
+import java.util.Set;
+
+import com.hp.hpl.jena.query.SortCondition;
import com.hp.hpl.jena.sparql.algebra.Op;
import com.hp.hpl.jena.sparql.algebra.TransformCopy;
import com.hp.hpl.jena.sparql.algebra.op.OpDistinct;
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.core.Var;
/**
* <p>
@@ -33,10 +38,22 @@ import com.hp.hpl.jena.sparql.algebra.op
* in-memory to evaluate it.
* </p>
* <p>
+ * As with most optimizations this is only applied when it is safe to do so.
The
+ * criteria for being safe to do so are as follows:
+ * </p>
+ * <ul>
+ * <li>Uses both {@code ORDER BY} and {@code DISTINCT} on the same level of the
+ * query</li>
+ * <li>There is a fixed list of variables to project i.e. not {@code SELECT
*}</li>
+ * <li>{@code ORDER BY} conditions cover all the projected variables prior to
+ * the use of any other variables</li>
+ * </ul>
+ * <h3>Related Optimizations</h3>
+ * <p>
* See also {@link TransformOrderByDistinctAppplication} which is a better
- * optimization for these kinds of queries but only applies to a limited
- * range of queries. Where possible that optimization is applied in preference
- * to this one.
+ * optimization for these kinds of queries but only applies to a more limited
range
+ * of queries. Where possible that optimization is applied in preference to
this
+ * one.
* </p>
* <p>
* {@link TransformTopN} covers the case of {@code DISTINCT} plus
@@ -52,15 +69,65 @@ public class TransformDistinctToReduced
// TopN of "reduced or distinct of order" is handled.
@Override
public Op transform(OpDistinct opDistinct, Op subOp) {
- if (subOp instanceof OpOrder) {
- return OpReduced.create(subOp);
- } else if (subOp instanceof OpProject) {
- OpProject project = (OpProject) subOp;
- if (project.getSubOp() instanceof OpOrder) {
- return OpReduced.create(subOp);
+ if (subOp instanceof OpProject) {
+ OpProject opProject = (OpProject) subOp;
+ if (opProject.getSubOp() instanceof OpOrder) {
+ OpOrder opOrder = (OpOrder) opProject.getSubOp();
+ if (isSafe(opProject, opOrder)) {
+ return OpReduced.create(subOp);
+ }
}
}
return super.transform(opDistinct, subOp);
}
+ protected boolean isSafe(OpProject opProject, OpOrder opOrder) {
+ Set<Var> projectVars = new HashSet<Var>(opProject.getVars());
+ Set<Var> seenVars = new HashSet<Var>();
+
+ // For the optimization to be safe all project variables must appear in
+ // the ordering prior to any unprojected variables
+ // Ordering by expressions is fine provided they use only projected
+ // variables
+ boolean ok = true;
+ for (SortCondition cond : opOrder.getConditions()) {
+ if (!isValidSortCondition(cond, projectVars, seenVars)) {
+ ok = false;
+ break;
+ }
+
+ // As soon as we've seen all variables we know this is safe and any
+ // further sort conditions are irrelevant
+ if (seenVars.size() == projectVars.size())
+ break;
+ }
+
+ return ok;
+ }
+
+ /**
+ * Determines whether a sort condition is valid in terms of this optimizer
+ *
+ * @param cond
+ * Sort Condition
+ * @param projectVars
+ * Project Variables
+ * @return True if valid, false otherwise
+ */
+ private boolean isValidSortCondition(SortCondition cond, Set<Var>
projectVars, Set<Var> seenVars) {
+ if (cond.getExpression().isVariable()) {
+ if (projectVars.contains(cond.getExpression().asVar())) {
+ seenVars.add(cond.getExpression().asVar());
+ return true;
+ }
+ return false;
+ } else {
+ for (Var v : cond.getExpression().getVarsMentioned()) {
+ if (!projectVars.contains(v))
+ return false;
+ seenVars.add(v);
+ }
+ return true;
+ }
+ }
}
Modified:
jena/trunk/jena-arq/src/test/java/com/hp/hpl/jena/sparql/algebra/optimize/TestOptimizer.java
URL:
http://svn.apache.org/viewvc/jena/trunk/jena-arq/src/test/java/com/hp/hpl/jena/sparql/algebra/optimize/TestOptimizer.java?rev=1541139&r1=1541138&r2=1541139&view=diff
==============================================================================
---
jena/trunk/jena-arq/src/test/java/com/hp/hpl/jena/sparql/algebra/optimize/TestOptimizer.java
(original)
+++
jena/trunk/jena-arq/src/test/java/com/hp/hpl/jena/sparql/algebra/optimize/TestOptimizer.java
Tue Nov 12 16:55:16 2013
@@ -20,7 +20,6 @@ package com.hp.hpl.jena.sparql.algebra.o
import org.apache.jena.atlas.junit.BaseTest ;
import org.apache.jena.atlas.lib.StrUtils ;
-import org.junit.Ignore;
import org.junit.Test ;
import com.hp.hpl.jena.query.ARQ ;
@@ -64,7 +63,7 @@ public class TestOptimizer extends BaseT
check(queryString, opExpectedString) ;
}
- @Test public void slice_order_to_topn_03()
+ @Test public void slice_order_to_topn_03()
{
assertTrue(ARQ.isTrueOrUndef(ARQ.optTopNSorting)) ;
String queryString = "SELECT * { ?s ?p ?o } ORDER BY ?p ?o OFFSET 4242
LIMIT 10" ;
@@ -125,14 +124,13 @@ public class TestOptimizer extends BaseT
check(queryString, opExpectedString) ;
}
- @Ignore //Ignore until JENA-587 is resolved
@Test public void slice_order_to_topn_08()
{
assertTrue(ARQ.isTrueOrUndef(ARQ.optTopNSorting)) ;
String queryString = "SELECT DISTINCT * { ?s ?p ?o } ORDER BY ?p ?o
LIMIT 4242" ;
String opExpectedString =
"(slice _ 4242\n" +
- " (reduced\n" +
+ " (distinct\n" +
" (order (?p ?o)\n" +
" (bgp (triple ?s ?p ?o)))))" ;
check(queryString, opExpectedString) ;
@@ -184,13 +182,13 @@ public class TestOptimizer extends BaseT
check(queryString, opExpectedString) ;
}
- @Ignore //Ignore until JENA-587 is resolved
@Test public void distinct_to_reduced_01()
{
+ // Per JENA-587 not safe to transform if a SELECT *
assertTrue(ARQ.isTrueOrUndef(ARQ.optDistinctToReduced)) ;
String queryString = "SELECT DISTINCT * { ?s ?p ?o } ORDER BY ?p ?o"
;
String opExpectedString =
- "(reduced\n" +
+ "(distinct\n" +
" (order (?p ?o)\n" +
" (bgp (triple ?s ?p ?o))))" ;
check(queryString, opExpectedString) ;
@@ -212,9 +210,12 @@ public class TestOptimizer extends BaseT
}
}
- @Ignore //Ignore until JENA-587 is resolved
@Test public void distinct_to_reduced_03()
{
+ // Per JENA-587 this is safe to transform since all project variables
+ // appear in the ORDER BY
+ // Ordering of variables in the ORDER BY is irrelevant as long as they
appear
+ // before any non-projected variables
assertTrue(ARQ.isTrueOrUndef(ARQ.optDistinctToReduced)) ;
String queryString = "SELECT DISTINCT ?p { ?s ?p ?o } ORDER BY ?p ?o"
;
String opExpectedString =
@@ -225,6 +226,112 @@ public class TestOptimizer extends BaseT
check(queryString, opExpectedString) ;
}
+ @Test public void distinct_to_reduced_04()
+ {
+ try {
+ // Must be turned off or will apply in favour of the specific
optimization we are trying to test
+ ARQ.getContext().set(ARQ.optOrderByDistinctApplication, false);
+
+ // Per JENA-587 this is safe to transform since all project
variables
+ // appear in the ORDER BY
+ // Ordering of variables in the ORDER BY is irrelevant as long as
they appear
+ // before any non-projected variables
+ assertTrue(ARQ.isTrueOrUndef(ARQ.optDistinctToReduced)) ;
+ String queryString = "SELECT DISTINCT ?p ?o { ?s ?p ?o } ORDER BY
?p ?o" ;
+ String opExpectedString =
+ "(reduced\n" +
+ " (project (?p ?o)\n" +
+ " (order (?p ?o)\n" +
+ " (bgp (triple ?s ?p ?o)))))" ;
+ check(queryString, opExpectedString) ;
+ } finally {
+ ARQ.getContext().unset(ARQ.optOrderByDistinctApplication);
+ }
+ }
+
+ @Test public void distinct_to_reduced_05()
+ {
+ try {
+ // Must be turned off or will apply in favour of the specific
optimization we are trying to test
+ ARQ.getContext().set(ARQ.optOrderByDistinctApplication, false);
+
+ // Per JENA-587 this is safe to transform since all project
variables
+ // appear in the ORDER BY
+ // Ordering of variables in the ORDER BY is irrelevant as long as
they appear
+ // before any non-projected variables
+ assertTrue(ARQ.isTrueOrUndef(ARQ.optDistinctToReduced)) ;
+ String queryString = "SELECT DISTINCT ?p ?o { ?s ?p ?o } ORDER BY
?o ?p" ;
+ String opExpectedString =
+ "(reduced\n" +
+ " (project (?p ?o)\n" +
+ " (order (?o ?p)\n" +
+ " (bgp (triple ?s ?p ?o)))))" ;
+ check(queryString, opExpectedString) ;
+ } finally {
+ ARQ.getContext().unset(ARQ.optOrderByDistinctApplication);
+ }
+ }
+
+ @Test public void distinct_to_reduced_06()
+ {
+ // Per JENA-587 this is safe to transform since all project variables
+ // appear in the ORDER BY
+ // Ordering of variables in the ORDER BY is irrelevant as long as they
appear
+ // before any non-projected variables
+ assertTrue(ARQ.isTrueOrUndef(ARQ.optDistinctToReduced)) ;
+ String queryString = "SELECT DISTINCT ?p ?o { ?s ?p ?o } ORDER BY ?o
?p ?s" ;
+ String opExpectedString =
+ "(reduced\n" +
+ " (project (?p ?o)\n" +
+ " (order (?o ?p ?s)\n" +
+ " (bgp (triple ?s ?p ?o)))))" ;
+ check(queryString, opExpectedString) ;
+ }
+
+ @Test public void distinct_to_reduced_07()
+ {
+ // Per JENA-587 this is safe to transform since all project variables
+ // appear in the ORDER BY
+ // Ordering of variables in the ORDER BY is irrelevant as long as they
appear
+ // before any non-projected variables
+ assertTrue(ARQ.isTrueOrUndef(ARQ.optDistinctToReduced)) ;
+ String queryString = "SELECT DISTINCT ?p ?o { ?s ?p ?o } ORDER BY ?p
?o ?s" ;
+ String opExpectedString =
+ "(reduced\n" +
+ " (project (?p ?o)\n" +
+ " (order (?p ?o ?s)\n" +
+ " (bgp (triple ?s ?p ?o)))))" ;
+ check(queryString, opExpectedString) ;
+ }
+
+ @Test public void distinct_to_reduced_08()
+ {
+ // Per JENA-587 this is unsafe to transform since a non-project
variable
+ // appears before all the projected variables are seen in the ORDER BY
+ assertTrue(ARQ.isTrueOrUndef(ARQ.optDistinctToReduced)) ;
+ String queryString = "SELECT DISTINCT ?p ?o { ?s ?p ?o } ORDER BY ?s
?p ?o" ;
+ String opExpectedString =
+ "(distinct\n" +
+ " (project (?p ?o)\n" +
+ " (order (?s ?p ?o)\n" +
+ " (bgp (triple ?s ?p ?o)))))" ;
+ check(queryString, opExpectedString) ;
+ }
+
+ @Test public void distinct_to_reduced_09()
+ {
+ // Per JENA-587 this is unsafe to transform since a non-project
variable
+ // appears before all the projected variables are seen in the ORDER BY
+ assertTrue(ARQ.isTrueOrUndef(ARQ.optDistinctToReduced)) ;
+ String queryString = "SELECT DISTINCT ?p ?o { ?s ?p ?o } ORDER BY ?p
?s ?o" ;
+ String opExpectedString =
+ "(distinct\n" +
+ " (project (?p ?o)\n" +
+ " (order (?p ?s ?o)\n" +
+ " (bgp (triple ?s ?p ?o)))))" ;
+ check(queryString, opExpectedString) ;
+ }
+
@Test public void distinct_order_by_application_01()
{
assertTrue(ARQ.isTrueOrUndef(ARQ.optOrderByDistinctApplication)) ;
@@ -256,15 +363,14 @@ public class TestOptimizer extends BaseT
}
}
- @Ignore //Ignore until JENA-587 is resolved
@Test public void distinct_order_by_application_03()
{
// Evaluation reordering optimization doesn't apply if it's a SELECT *
- // However the DISTINCT to REDUCED transformation still applies
+ // Also per JENA-587 DISTINCT -> REDUCED transformation cannot apply
either
assertTrue(ARQ.isTrueOrUndef(ARQ.optOrderByDistinctApplication)) ;
String queryString = "SELECT DISTINCT * { ?s ?p ?o } ORDER BY ?p";
String opExpectedString =
- " (reduced\n" +
+ " (distinct\n" +
" (order (?p)\n" +
" (bgp (triple ?s ?p ?o))))" ;
check(queryString, opExpectedString) ;
@@ -298,18 +404,17 @@ public class TestOptimizer extends BaseT
check(queryString, opExpectedString) ;
}
- @Ignore //Ignore until JENA-587 is resolved
@Test public void distinct_order_by_application_06()
{
// The optimization can apply when order conditions are not simple
variables
// provided every variable used in an expression appears in the
project list
// In this case it should not apply because the condition used a
variable that
// does not appear in the project list
- // However the DISTINCT to REDUCED optimization does apply
+ // Per JENA-587 the DISTINCT to REDUCED optimization also does not
apply
assertTrue(ARQ.isTrueOrUndef(ARQ.optOrderByDistinctApplication)) ;
String queryString = "SELECT DISTINCT ?p { ?s ?p ?o } ORDER BY
LCASE(CONCAT(?s, ?p))";
String opExpectedString =
- " (reduced\n" +
+ " (distinct\n" +
" (project (?p)\n" +
" (order ((lcase (concat ?s ?p)))\n" +
" (bgp (triple ?s ?p ?o)))))" ;
