You are viewing a plain text version of this content. The canonical link for it is here.
Posted to commits@jena.apache.org by an...@apache.org on 2014/04/04 19:21:18 UTC
svn commit: r1584831 - in /jena/trunk/jena-arq: ./
src/main/java/com/hp/hpl/jena/sparql/algebra/optimize/
src/test/java/com/hp/hpl/jena/sparql/algebra/optimize/
Author: andy
Date: Fri Apr 4 17:21:18 2014
New Revision: 1584831
URL: http://svn.apache.org/r1584831
Log:
JENA-671 : Place filters even at the end of (sequence)
This has knock-on consequences on the tests for FilterEquity optimization.
The optimziation is now done more deeply.
Modified:
jena/trunk/jena-arq/ReleaseNotes.txt
jena/trunk/jena-arq/src/main/java/com/hp/hpl/jena/sparql/algebra/optimize/TransformFilterPlacement.java
jena/trunk/jena-arq/src/test/java/com/hp/hpl/jena/sparql/algebra/optimize/TestTransformFilterPlacement.java
jena/trunk/jena-arq/src/test/java/com/hp/hpl/jena/sparql/algebra/optimize/TestTransformFilters.java
Modified: jena/trunk/jena-arq/ReleaseNotes.txt
URL: http://svn.apache.org/viewvc/jena/trunk/jena-arq/ReleaseNotes.txt?rev=1584831&r1=1584830&r2=1584831&view=diff
==============================================================================
--- jena/trunk/jena-arq/ReleaseNotes.txt (original)
+++ jena/trunk/jena-arq/ReleaseNotes.txt Fri Apr 4 17:21:18 2014
@@ -4,7 +4,8 @@ ChangeLog for ARQ
==== Jena 2.11.2
-+ JENA-638 : Imporve coverage of TopN optimziation
++ JENA-671 : More filter placement optimization.
++ JENA-638 : Improve coverage of TopN optimziation
+ JENA-634 : Add JSON-LD
+ JENA-518 : Add getter/setter for the error handler to ReaderRIOT.
Modified: jena/trunk/jena-arq/src/main/java/com/hp/hpl/jena/sparql/algebra/optimize/TransformFilterPlacement.java
URL: http://svn.apache.org/viewvc/jena/trunk/jena-arq/src/main/java/com/hp/hpl/jena/sparql/algebra/optimize/TransformFilterPlacement.java?rev=1584831&r1=1584830&r2=1584831&view=diff
==============================================================================
--- jena/trunk/jena-arq/src/main/java/com/hp/hpl/jena/sparql/algebra/optimize/TransformFilterPlacement.java (original)
+++ jena/trunk/jena-arq/src/main/java/com/hp/hpl/jena/sparql/algebra/optimize/TransformFilterPlacement.java Fri Apr 4 17:21:18 2014
@@ -44,11 +44,12 @@ import com.hp.hpl.jena.sparql.util.VarUt
*/
public class TransformFilterPlacement extends TransformCopy {
-
static class Placement {
final Op op ;
final ExprList unplaced ;
Placement(Op op, ExprList remaining) { this.op = op ; this.unplaced = remaining ; }
+ @Override
+ public String toString() { return ""+op+" : "+unplaced ; }
}
// Empty, immutable ExprList
@@ -178,17 +179,23 @@ public class TransformFilterPlacement ex
return wrapBGP(exprsIn, pattern) ;
}
+ public static Placement debugPlaceBGP(ExprList exprsIn, BasicPattern pattern) {
+ return placeBGP(exprsIn, pattern) ;
+ }
+
+ // See also placeQuadPattern.
+ //
+ // An improvement might be to put any filters that apply to exactly one triple
+ // directly on the triple pattern. At the moment, the filter is put over
+ // the block leading up to the triple pattern.
+
private static Placement placeBGP(ExprList exprsIn, BasicPattern pattern) {
ExprList exprs = ExprList.copy(exprsIn) ;
Set<Var> patternVarsScope = DS.set() ;
// Any filters that depend on no variables.
- Op op = null ;
+ Op op = insertAnyFilter$(exprs, patternVarsScope, null) ;
for (Triple triple : pattern) {
- // Place any filters that are now covered.
- op = insertAnyFilter$(exprs, patternVarsScope, op) ;
- // Consider this triple.
- // Get BGP that is accumulating triples.
OpBGP opBGP = getBGP(op) ;
if ( opBGP == null ) {
// Last thing was not a BGP (so it likely to be a filter)
@@ -200,10 +207,9 @@ public class TransformFilterPlacement ex
opBGP.getPattern().add(triple) ;
// Update variables in scope.
VarUtils.addVarsFromTriple(patternVarsScope, triple) ;
+ op = insertAnyFilter$(exprs, patternVarsScope, op) ;
}
- // Place any filters this whole BGP covers.
- op = insertAnyFilter$(exprs, patternVarsScope, op) ;
return result(op, exprs) ;
}
@@ -271,10 +277,9 @@ public class TransformFilterPlacement ex
// Add in the graph node of the quad block.
VarUtils.addVar(patternVarsScope, Var.alloc(graphNode)) ;
}
- Op op = null ;
+ Op op = insertAnyFilter$(exprs, patternVarsScope, null) ;
for (Triple triple : pattern) {
- op = insertAnyFilter$(exprs, patternVarsScope, op) ;
OpQuadPattern opQuad = getQuads(op) ;
if ( opQuad == null ) {
opQuad = new OpQuadPattern(graphNode, new BasicPattern()) ;
@@ -284,9 +289,8 @@ public class TransformFilterPlacement ex
opQuad.getBasicPattern().add(triple) ;
// Update variables in scope.
VarUtils.addVarsFromTriple(patternVarsScope, triple) ;
+ op = insertAnyFilter$(exprs, patternVarsScope, op) ;
}
- // Place any filters this whole quad block covers.
- op = insertAnyFilter$(exprs, patternVarsScope, op) ;
return result(op, exprs) ;
}
@@ -341,11 +345,11 @@ public class TransformFilterPlacement ex
* substituted into the right, i.e. there are no scoping issues. Assuming a
* substitution join is going to be done, filtering once as soon as the
* accumulated variables cover the filter is a good thing to do. It is
- * effectively pusing on teh left side only - the right side, by
+ * effectively pusing on the left side only - the right side, by
* substitution, will never see the variables. The variable can not be
* reintroduced (it will have been renamed away if it's the same name,
* different scope, which is a different variable with the same name in the
- * orginal query.
+ * orginal query).
*/
private Placement placeSequence(ExprList exprsIn, OpSequence opSequence) {
@@ -354,18 +358,15 @@ public class TransformFilterPlacement ex
List<Op> ops = opSequence.getElements() ;
Op op = null ;
- // No point placing on the last element as that is the same as filtering the entire expression.
for (int i = 0 ; i < ops.size() ; i++ ) {
op = insertAnyFilter$(exprs, varScope, op) ;
Op seqElt = ops.get(i) ;
- if ( i != ops.size()-1 ) {
- Placement p = transform(exprs, seqElt) ;
- if ( p != null ) {
- exprs = p.unplaced ;
- seqElt = p.op ;
- }
- varScope.addAll(fixedVars(seqElt)) ;
+ Placement p = transform(exprs, seqElt) ;
+ if ( p != null ) {
+ exprs = p.unplaced ;
+ seqElt = p.op ;
}
+ varScope.addAll(fixedVars(seqElt)) ;
op = OpSequence.create(op, seqElt) ;
}
return result(op, exprs) ;
Modified: jena/trunk/jena-arq/src/test/java/com/hp/hpl/jena/sparql/algebra/optimize/TestTransformFilterPlacement.java
URL: http://svn.apache.org/viewvc/jena/trunk/jena-arq/src/test/java/com/hp/hpl/jena/sparql/algebra/optimize/TestTransformFilterPlacement.java?rev=1584831&r1=1584830&r2=1584831&view=diff
==============================================================================
--- jena/trunk/jena-arq/src/test/java/com/hp/hpl/jena/sparql/algebra/optimize/TestTransformFilterPlacement.java (original)
+++ jena/trunk/jena-arq/src/test/java/com/hp/hpl/jena/sparql/algebra/optimize/TestTransformFilterPlacement.java Fri Apr 4 17:21:18 2014
@@ -52,7 +52,10 @@ public class TestTransformFilterPlacemen
}
@Test public void place_bgp_04() {
- test("(filter (= ?XX 1) (bgp (?s ?p ?x) (?s1 ?p1 ?XX) ))", "(filter (= ?XX 1) (bgp (?s ?p ?x) (?s1 ?p1 ?XX) ))") ;
+ test("(filter (= ?XX 1) (bgp (?s ?p ?x) (?s1 ?p1 ?XX) ))",
+ "(filter (= ?XX 1) (bgp (?s ?p ?x) (?s1 ?p1 ?XX) ))") ;
+ // and not
+ // "(sequence (bgp (?s ?p ?x)) (filter (= ?XX 1) (?s1 ?p1 ?XX)) )"
}
@Test public void place_bgp_05() {
@@ -120,9 +123,7 @@ public class TestTransformFilterPlacemen
@Test public void place_sequence_06() {
test("(filter (= ?x 123) (sequence (bgp (?s ?p ?x1) (?s ?p ?x2)) (bgp (?s ?p ?x)) ))",
- // If push filter to last element ... which is of no benefit
- //"(sequence (bgp (?s ?p ?x1) (?s ?p ?x2)) (filter (= ?x 123) (bgp (?s ?p ?x))) )") ;
- null) ;
+ "(sequence (bgp (?s ?p ?x1) (?s ?p ?x2)) (filter (= ?x 123) (bgp (?s ?p ?x))) )") ;
}
@Test public void place_sequence_07() {
@@ -262,7 +263,7 @@ public class TestTransformFilterPlacemen
@Test public void place_extend_05() {
// Filter further out than one place.
test("(filter (= ?z 1) (sequence (extend (?x1 123) (bgp (?s ?p ?x))) (bgp (?s ?p ?z))))",
- null) ;
+ "(sequence (extend (?x1 123) (bgp (?s ?p ?x))) (filter (= ?z 1) (bgp (?s ?p ?z)) ))") ;
}
@Test public void place_extend_06() {
Modified: jena/trunk/jena-arq/src/test/java/com/hp/hpl/jena/sparql/algebra/optimize/TestTransformFilters.java
URL: http://svn.apache.org/viewvc/jena/trunk/jena-arq/src/test/java/com/hp/hpl/jena/sparql/algebra/optimize/TestTransformFilters.java?rev=1584831&r1=1584830&r2=1584831&view=diff
==============================================================================
--- jena/trunk/jena-arq/src/test/java/com/hp/hpl/jena/sparql/algebra/optimize/TestTransformFilters.java (original)
+++ jena/trunk/jena-arq/src/test/java/com/hp/hpl/jena/sparql/algebra/optimize/TestTransformFilters.java Fri Apr 4 17:21:18 2014
@@ -227,8 +227,7 @@ public class TestTransformFilters extend
, " (project (?s1)"
, " (bgp (triple ?/test ?/p2 ?/o2))) )"
) ;
- // Answer if FILTER equality done only before filter placement
- // (and possibly after as well).
+ // Answer if weaker filter placement done, leaving the filter on the whole sequence.
// String ops = StrUtils.strjoinNL
// ( "(assign ((?test <http://localhost/t1>))"
// , " (sequence"
@@ -251,15 +250,27 @@ public class TestTransformFilters extend
, " ?x :p ?o2"
, "}"
) ;
+ // Answer if weaker filter placement done, leaving the filter on the whole sequence. JENA-671
+// String ops = StrUtils.strjoinNL
+// ( "(filter (= ?x <http://example/x>)"
+// , " (sequence"
+// , " (conditional"
+// , " (table unit)"
+// , " (bgp (triple ?x <http://example/q> ?o)))"
+// , " (bgp (triple ?x <http://example/p> ?o2))"
+// , " ))"
+// ) ;
+ //JENA-671
String ops = StrUtils.strjoinNL
- ( "(filter (= ?x <http://example/x>)"
- , " (sequence"
- , " (conditional"
- , " (table unit)"
- , " (bgp (triple ?x <http://example/q> ?o)))"
- , " (bgp (triple ?x <http://example/p> ?o2))"
- , " ))"
- ) ;
+ ("(sequence"
+ , " (conditional"
+ , " (table unit)"
+ , " (bgp (triple ?x <http://example/q> ?o)))"
+ , " (assign ((?x <http://example/x>))"
+ , " (bgp (triple <http://example/x> <http://example/p> ?o2)))"
+ , ")"
+ ) ;
+
TestOptimizer.check(qs, ops) ;
}
@@ -271,8 +282,8 @@ public class TestTransformFilters extend
, " ?x :p ?o2"
, "}"
) ;
- // Possible transformation:
- // Safe to transform: This (sequence) always defined ?x
+ // Transformation if ilter place not happening.
+ // Weaker placement.
String ops = StrUtils.strjoinNL
("(assign ((?x <http://example/x>))"
, " (sequence"
@@ -281,17 +292,19 @@ public class TestTransformFilters extend
, " (bgp (triple <http://example/x> <http://example/q> ?o)))"
, " (bgp (triple <http://example/x> <http://example/p> ?o2))))"
) ;
- // Currently :
- String ops1 = StrUtils.strjoinNL
- ("(filter (= ?x <http://example/x>)"
- ," (sequence"
- ," (conditional"
- ," (table unit)"
- ," (bgp (triple ?x <http://example/q> ?o)) )"
- ," (bgp (triple ?x <http://example/p> ?o2)) ))"
+ //JENA-671
+ // Note that "assign" is a filter as well
+ // so it filters the ?x fro the RHS of the conditional.
+ String ops2 = StrUtils.strjoinNL
+ ("(sequence"
+ ," (conditional"
+ ," (table unit)"
+ ," (bgp (triple ?x <http://example/q> ?o)) )"
+ ," (assign ((?x <http://example/x>))"
+ ," (bgp (triple <http://example/x> <http://example/p> ?o2)))"
+ ," )"
) ;
-
- TestOptimizer.check(qs, ops1) ;
+ TestOptimizer.check(qs, ops2) ;
}
// JENA-294 part II