Author: andy
Date: Sat Nov 16 23:36:45 2013
New Revision: 1542613
URL: http://svn.apache.org/r1542613
Log:
Recursively push filter expressions down.
Modified:
jena/Scratch/AFS/Dev/src-dev/opt/OptMain.java
jena/Scratch/AFS/Dev/src-dev/opt/TestFilterPlacement.java
jena/Scratch/AFS/Dev/src-dev/opt/TransformFilterEquality2.java
jena/Scratch/AFS/Dev/src-dev/opt/TransformFilterPlacement_Rewrite.java
Modified: jena/Scratch/AFS/Dev/src-dev/opt/OptMain.java
URL:
http://svn.apache.org/viewvc/jena/Scratch/AFS/Dev/src-dev/opt/OptMain.java?rev=1542613&r1=1542612&r2=1542613&view=diff
==============================================================================
--- jena/Scratch/AFS/Dev/src-dev/opt/OptMain.java (original)
+++ jena/Scratch/AFS/Dev/src-dev/opt/OptMain.java Sat Nov 16 23:36:45 2013
@@ -33,11 +33,25 @@ import com.hp.hpl.jena.sparql.sse.SSE ;
public class OptMain {
public static void main(String... argv) throws Exception {
+ // Tests
+ // coverage,
+ // repeated application.
+ // BGPs directly.
+ // Complex/recurse tests
+
+ // Transformations are applied "bottom up"
+ // - should this be top down?
+ // - what happens if hits a filter? Currently, it stops.
+
+ // test combined with filter equality.
+
// What about covered left but partial right?
// Push left (join),)
// Push left (left join)
// Other cases
+ // Check order of all optimziations - equality last.
+
// Also TransformDistinctToReduced (JENA-585)and
TransformOrderByDistincApplication
// Combinations e.g. placement then equality
@@ -54,6 +68,12 @@ public class OptMain {
// * Join
// Need to say what was pushed.
+ // Full optimization tests
+
+ // Was Op.equals a good idea?
+ // Calculate vars for an expr once and cache : op.getVars.
+
+ // XXX Push recursively.
if ( false ) {
String input = "(filter ((= ?A 2) (= ?z 99) (= ?x 123)) (bgp (?s
?p ?x) (?s ?p ?z)) )" ;
@@ -65,21 +85,33 @@ public class OptMain {
System.exit(0) ;
}
- if (true) {
- String qs = StrUtils.strjoinNL(
- "PREFIX ex: <http://example.org/test#>",
- "SELECT * WHERE {",
- " ?var ex:p1 ?x. ",
- " OPTIONAL {",
- " ?x ex:p2 ?y.",
- " OPTIONAL {",
- " ?y ex:p3 ?z",
- " }",
- " }",
- " FILTER (?var = ex:i)",
- "}") ;
- Query query = QueryFactory.create(qs) ;
+ if ( false ) {
+ String qs1 = StrUtils.strjoinNL
+ ("PREFIX ex: <http://example.org/test#>",
+ "SELECT * WHERE {",
+ " ?var ex:p1 ?x. ",
+ " OPTIONAL {",
+ " ?x ex:p2 ?y.",
+ " OPTIONAL {",
+ " ?y ex:p3 ?z",
+ " }",
+ " }",
+ " FILTER (?var = ex:i)",
+ "}") ;
+ String qs2 = StrUtils.strjoinNL
+ ("PREFIX ex: <http://example.org/test#>",
+ "SELECT * WHERE {",
+ " ?s ?p ?o .",
+ " ?s ?q ?w ",
+ " BIND ( ?o+1 as ?z)" ,
+ " FILTER (?o != 57)",
+ " FILTER (?z != 57)",
+ "}") ;
+
+ Query query = QueryFactory.create(qs2) ;
Op op1 = Algebra.compile(query) ;
+ System.out.println("** Input") ;
+ System.out.println(op1) ;
{
System.out.println("** OLD") ;
Op op2 = Algebra.optimize(op1) ;
@@ -94,6 +126,8 @@ public class OptMain {
System.exit(0) ;
}
+ // Extend test
+
// What about covered left but partial right?
// Push left (join),)
// Push left (left join)
Modified: jena/Scratch/AFS/Dev/src-dev/opt/TestFilterPlacement.java
URL:
http://svn.apache.org/viewvc/jena/Scratch/AFS/Dev/src-dev/opt/TestFilterPlacement.java?rev=1542613&r1=1542612&r2=1542613&view=diff
==============================================================================
--- jena/Scratch/AFS/Dev/src-dev/opt/TestFilterPlacement.java (original)
+++ jena/Scratch/AFS/Dev/src-dev/opt/TestFilterPlacement.java Sat Nov 16
23:36:45 2013
@@ -29,55 +29,43 @@ import com.hp.hpl.jena.sparql.algebra.Tr
import com.hp.hpl.jena.sparql.sse.SSE ;
public class TestFilterPlacement extends BaseTest { //extends
AbstractTestTransform {
- @Test
- public void place_filter_bgp_01() {
+ @Test public void place_filter_bgp_01() {
test("(filter (= ?x 1) (bgp ( ?s ?p ?x)))", "(filter (= ?x 1) (bgp (
?s ?p ?x)))") ;
}
- @Test
- public void place_filter_bgp_02() {
+ @Test public void place_filter_bgp_02() {
test("(filter (= ?x 1) (bgp (?s ?p ?x) (?s1 ?p1 ?x1) ))",
"(sequence (filter (= ?x 1) (bgp ( ?s ?p ?x))) (bgp (?s1 ?p1
?x1)))") ;
}
- @Test
- public void place_filter_bgp_03() {
+ @Test public void place_filter_bgp_03() {
test("(filter (= ?x 1) (bgp (?s ?p ?x) (?s1 ?p1 ?x) ))",
"(sequence (filter (= ?x 1) (bgp ( ?s ?p ?x))) (bgp (?s1 ?p1
?x)))") ;
}
- @Test
- public void place_filter_bgp_04() {
+ @Test public void place_filter_bgp_04() {
test("(filter (= ?XX 1) (bgp (?s ?p ?x) (?s1 ?p1 ?XX) ))", "(filter (=
?XX 1) (bgp (?s ?p ?x) (?s1 ?p1 ?XX) ))") ;
}
- @Test
- public void place_filter_no_match_01() {
+ @Test public void place_filter_no_match_01() {
// Unbound
test("(filter (= ?x ?unbound) (bgp (?s ?p ?x)))", null) ;
}
- @Test
- public void place_filter_no_match_02() {
+ @Test public void place_filter_no_match_02() {
test("(filter (= ?x ?unbound) (bgp (?s ?p ?x) (?s ?p ?x)))", null) ;
}
- @Test
- public void place_filter_no_match_03() {
+ @Test public void place_filter_no_match_03() {
test("(filter (= ?x ?unbound) (bgp (?s ?p ?x) (?s1 ?p1 ?XX)))", null) ;
}
- // Sequence
-
- @Test
- public void place_filter_sequence_01() {
+ @Test public void place_filter_sequence_01() {
test("(filter (= ?x 123) (sequence (bgp (?s ?p ?x)) (bgp (?s ?p ?z))
))",
"(sequence (filter (= ?x 123) (bgp (?s ?p ?x))) (bgp (?s ?p ?z))
)") ;
-
}
- @Test
- public void place_filter_sequence_02() {
+ @Test public void place_filter_sequence_02() {
// Given the sequence flows left into right, only need to filter in the
// LHS. The RHS can't introduce ?x because it woudl not be a legal
sequence
// if, for example, it had a BIND in it.
@@ -85,29 +73,25 @@ public class TestFilterPlacement extends
"(sequence (filter (= ?x 123) (bgp (?s ?p ?x))) (bgp (?s ?p ?x))
)") ;
}
- @Test
- public void place_filter_sequence_03() {
+ @Test public void place_filter_sequence_03() {
test("(filter (= ?z 123) (sequence (bgp (?s ?p ?x)) (bgp (?s ?p ?z))
))",
null) ;
}
// Join : one sided push.
- @Test
- public void place_filter_join_01() {
+ @Test public void place_filter_join_01() {
test("(filter (= ?x 123) (join (bgp (?s ?p ?x)) (bgp (?s ?p ?z)) ))",
"(join (filter (= ?x 123) (bgp (?s ?p ?x))) (bgp (?s ?p ?z)) )") ;
}
// Join : two side push
- @Test
- public void place_filter_join_02() {
+ @Test public void place_filter_join_02() {
test("(filter (= ?x 123) (join (bgp (?s ?p ?x)) (bgp (?s ?p ?x)) ))",
"(join (filter (= ?x 123) (bgp (?s ?p ?x))) (filter (= ?x 123)
(bgp (?s ?p ?x))) )") ;
}
- @Test
- public void place_filter_join_03() {
+ @Test public void place_filter_join_03() {
String x = StrUtils.strjoinNL
("(filter ((= 13 14) (> ?o1 12) (< ?o 56) (< (+ ?o ?o1) 999))",
" (join",
@@ -126,7 +110,7 @@ public class TestFilterPlacement extends
// " (filter (> ?o1 12)",
// " (bgp (triple ?s ?p1 ?o1))))))") ;
- // Everything psuhed down.
+ // Everything pushed down.
String y = StrUtils.strjoinNL
("(filter (< (+ ?o ?o1) 999)",
" (join",
@@ -134,33 +118,66 @@ public class TestFilterPlacement extends
" (bgp (triple ?s ?p ?o)))",
" (filter ((= 13 14) (> ?o1 12))",
" (bgp (triple ?s ?p1 ?o1)))))") ;
- test(x, y) ;
+ // Recursive push in - causes (= 13 14) to go into BGP
+ String y1 = StrUtils.strjoinNL
+ ("(filter (< (+ ?o ?o1) 999)",
+ " (join",
+ " (filter (< ?o 56)",
+ " (sequence",
+ " (filter (= 13 14)",
+ " (table unit))",
+ " (bgp (triple ?s ?p ?o))))",
+ " (filter (> ?o1 12)",
+ " (sequence",
+ " (filter (= 13 14)",
+ " (table unit))",
+ " (bgp (triple ?s ?p1 ?o1))))",
+ " ))") ;
+ test(x, y1) ;
}
- @Test
- public void place_filter_conditional_01() {
+ @Test public void place_filter_conditional_01() {
// conditional
test("(filter (= ?x 123) (conditional (bgp (?s ?p ?x)) (bgp (?s ?p
?z)) ))",
"(conditional (filter (= ?x 123) (bgp (?s ?p ?x))) (bgp (?s ?p
?z)) )") ;
}
- @Test
- public void place_filter_conditional_02() {
+ @Test public void place_filter_conditional_02() {
// conditional
test("(filter (= ?z 123) (conditional (bgp (?s ?p ?x)) (bgp (?s ?p
?z)) ))",
"(filter (= ?z 123) (conditional (bgp (?s ?p ?x)) (bgp (?s ?p
?z)) ))") ;
}
- @Test
- public void place_filter_conditional_03() {
+ @Test public void place_filter_conditional_03() {
// conditional
test("(filter (= ?x 123) (conditional (bgp (?s ?p ?x)) (bgp (?s ?p
?x)) ))",
"(conditional (filter (= ?x 123) (bgp (?s ?p ?x))) (bgp (?s ?p
?x)) )") ;
}
- // LeftJoin
+ // ** Sequence
+
+ // ** LeftJoin
+
+ // ** Extend
+
+ @Test public void place_extend_01() {
+ test("(filter (= ?x 123) (extend ((?z 123)) (bgp (?s ?p ?x)) ))",
+ "(extend ((?z 123)) (filter (= ?x 123) (bgp (?s ?p ?x)) ))") ;
+ }
+
+ @Test public void place_extend_02() { // Blocked
+ test("(filter (= ?x 123) (extend ((?x 123)) (bgp (?s ?p ?z)) ))",
+ null) ;
+ }
+
+ @Test public void place_extend_03() {
+ test("(filter (= ?x 123) (extend ((?x1 123)) (filter (< ?x 456) (bgp
(?s ?p ?x) (?s ?p ?z))) ))",
+ "(extend (?x1 123) (sequence (filter ((< ?x 456) (= ?x 123)) (bgp
(?s ?p ?x))) (bgp (?s ?p ?z))) )") ;
+ }
+ // ** Assign
+
public static void test(String input, String output) {
Transform t_placement = new TransformFilterPlacement_Rewrite() ;
Op op1 = SSE.parseOp(input) ;
Modified: jena/Scratch/AFS/Dev/src-dev/opt/TransformFilterEquality2.java
URL:
http://svn.apache.org/viewvc/jena/Scratch/AFS/Dev/src-dev/opt/TransformFilterEquality2.java?rev=1542613&r1=1542612&r2=1542613&view=diff
==============================================================================
--- jena/Scratch/AFS/Dev/src-dev/opt/TransformFilterEquality2.java (original)
+++ jena/Scratch/AFS/Dev/src-dev/opt/TransformFilterEquality2.java Sat Nov 16
23:36:45 2013
@@ -41,7 +41,7 @@ import com.hp.hpl.jena.sparql.expr.* ;
public class TransformFilterEquality2 extends TransformCopy
{
// The approach taken for { OPTIONAL{} OPTIONAL{} } is more general ...
and better?
- // Still need to be careful of double-nested OPTIONALS as intermedates of
a different
+ // Still need to be careful of double-nested OPTIONALS as intermediates of
a different
// value can block overall results so don't mask immediately.
public TransformFilterEquality2()
{ }
Modified: jena/Scratch/AFS/Dev/src-dev/opt/TransformFilterPlacement_Rewrite.java
URL:
http://svn.apache.org/viewvc/jena/Scratch/AFS/Dev/src-dev/opt/TransformFilterPlacement_Rewrite.java?rev=1542613&r1=1542612&r2=1542613&view=diff
==============================================================================
--- jena/Scratch/AFS/Dev/src-dev/opt/TransformFilterPlacement_Rewrite.java
(original)
+++ jena/Scratch/AFS/Dev/src-dev/opt/TransformFilterPlacement_Rewrite.java Sat
Nov 16 23:36:45 2013
@@ -28,6 +28,7 @@ import java.util.Iterator ;
import java.util.List ;
import java.util.Set ;
+import org.apache.jena.atlas.lib.CollectionUtils ;
import org.apache.jena.atlas.lib.DS ;
import com.hp.hpl.jena.graph.Node ;
@@ -49,30 +50,28 @@ import com.hp.hpl.jena.sparql.util.VarUt
*/
public class TransformFilterPlacement_Rewrite extends TransformCopy {
- // Tests
- // coverage,
- // repeated application.
- // BGPs directly.
-
- // Transformations are applied "bottom up"
- // - should this be top down?
- // - what happens if hits a filter? Currently, it stops.
-
- // Was Op.equals a good idea?
- // Calculate vars for an expr once and cache
-
static class Placement {
final Op op ;
final ExprList unplaced ;
Placement(Op op, ExprList remaining) { this.op = op ; this.unplaced =
remaining ; }
}
+ static final ExprList emptyList = new ExprList() ;
+ static final Placement noChangePlacement = null ; //new Placement(null,
null) ;
+
private static Placement result(Op op, ExprList remaining) {
if ( op == null )
return null ;
return new Placement(op, remaining) ;
}
+ private static Placement resultNoChange(Op original) {
+ return noChangePlacement ;
+ }
+ private static boolean isNoChange(Placement placement) {
+ return placement == noChangePlacement ;
+ }
+
public static Op transform(ExprList exprs, BasicPattern bgp) {
Placement placement = placeFilterBGP(exprs, bgp) ;
Op op = ( placement == null ) ? new OpBGP(bgp) : placement.op ;
@@ -95,7 +94,6 @@ public class TransformFilterPlacement_Re
public Op transform(OpFilter opFilter, Op x) {
ExprList exprs = opFilter.getExprs() ;
Placement placement = transform(exprs, x) ;
-
if ( placement == null || placement.op == x )
// Didn't do anything.
return super.transform(opFilter, x) ;
@@ -103,11 +101,14 @@ public class TransformFilterPlacement_Re
return op ;
}
- // XXX Placement in / placement out?
-
+ // Recurse
+ private static Op transformOp(ExprList exprs, Op x) {
+ Placement placement = transform(exprs, x) ;
+ Op op = buildFilter(placement) ;
+ return op ;
+ }
+
private static Placement transform(ExprList exprs, Op input) {
- // OpAssign/OpExtend could be done if the assignment and exprs are
- // independent.
// Dispatch by visitor??
Placement placement = null ;
@@ -125,21 +126,25 @@ public class TransformFilterPlacement_Re
placement = placeFilterLeftJoin(exprs, (OpLeftJoin)input) ;
else if ( input instanceof OpFilter )
placement = placeFilter(exprs, (OpFilter)input) ;
-
-// else if ( input instanceof OpExtend ) {}
-// else if ( input instanceof OpAssign ) {}
-
+ else if ( input instanceof OpExtend )
+ placement = placeExtend(exprs, (OpExtend)input) ;
+ else if ( input instanceof OpAssign )
+ placement = placeAssign(exprs, (OpAssign)input) ;
+
return placement ;
}
+
+ private static Placement x_placeNoOp(ExprList exprs, Op op) {
+ return result(op, exprs) ;
+ }
// == The placeFilter* modify the exprs and patternVarsScope arguments
private static Placement placeFilter(ExprList exprs, OpFilter input) {
- // XXX NoOp
+ // XXX Recurse ??
return result(input, exprs) ;
}
-
private static Placement placeFilterBGP(ExprList exprs, OpBGP x) {
return placeFilterBGP(exprs, x.getPattern()) ;
}
@@ -267,7 +272,7 @@ public class TransformFilterPlacement_Re
op = insertAnyFilter(exprs, varScope, op) ;
Op seqElt = iter.next() ;
// XXX Recurse
- //seqElt = transform(exprs, varScope, seqElt) ; // varScope pass
in?
+ //seqElt = transformOp(exprs, seqElt) ;
// Merge into sequence.
varScope.addAll(OpVars.mentionedVars(seqElt)) ;
op = OpSequence.create(op, seqElt) ;
@@ -275,9 +280,6 @@ public class TransformFilterPlacement_Re
return result(op, exprs) ;
}
- // XXX Comments
-
- // XXX Push recursively.
// Whether to push a covered filter into the RHS even if pushed into the
LHS.
// If this is run after join->sequence, then this is good to do.
@@ -304,7 +306,6 @@ public class TransformFilterPlacement_Re
if ( pushed && ! pushRightAsWellAsLeft )
continue ;
// If left only, make this "else if" of left test, remove
"continue"
- // XXX Tests for this
if ( rightVars.containsAll(vars) ) {
// Push right
pushRight.add(expr) ;
@@ -319,16 +320,12 @@ public class TransformFilterPlacement_Re
return null ;
Op opLeftNew = left ;
- if ( !pushLeft.isEmpty() ) {
- // opLeftNew = transform(exprs, opLeftNew) ;
- opLeftNew = OpFilter.filter(pushLeft, opLeftNew) ;
- }
+ if ( !pushLeft.isEmpty() )
+ opLeftNew = transformOp(pushLeft, opLeftNew) ;
Op opRightNew = right ;
- if ( !pushRight.isEmpty() ) {
- // opRightNew = transform(exprs, opRightNew) ;
- opRightNew = OpFilter.filter(pushRight, opRightNew) ;
- }
+ if ( !pushRight.isEmpty() )
+ opRightNew = transformOp(pushRight, opRightNew) ;
Op op = OpJoin.create(opLeftNew, opRightNew) ;
return result(op, unpushed) ;
@@ -344,6 +341,7 @@ public class TransformFilterPlacement_Re
Placement nLeft = transform(exprs, left) ;
if ( nLeft == null )
result(null, exprs) ;
+ // XXX Recurse
Op op = new OpConditional(nLeft.op, right) ;
return result(op, nLeft.unplaced) ;
}
@@ -360,68 +358,55 @@ public class TransformFilterPlacement_Re
Op op = OpLeftJoin.create(nLeft.op, right, opLeftJoin.getExprs()) ;
return result(op, nLeft.unplaced) ;
}
-// // Any filters that depend on no variables.
-// Op opInitial = insertAnyFilter(exprs, varScope, null) ;
-//
-// if ( opInitial == opLeftJoin )
-// opInitial = null ;
-//
-// // ?? Anything magic for the filters in the LeftJoin itself?
-// ExprList leftJoinExpr = opLeftJoin.getExprs() ;
-//
-// Op left = opLeftJoin.getLeft() ;
-// Op right = opLeftJoin.getRight() ;
-// Collection<Var> leftVars = OpVars.mentionedVars(left) ;
-// Collection<Var> rightVars = OpVars.mentionedVars(right) ;
-// ExprList unpushed = new ExprList() ;
-// ExprList pushLeft = new ExprList() ;
-// ExprList pushRight = new ExprList() ; // Unused
-//
-// for (Expr expr : exprs) {
-// Set<Var> vars = expr.getVarsMentioned() ;
-// boolean pushed = false ;
-//
-// if ( leftVars.containsAll(vars)
-// // && disjoint(rightVars, vars)
-// ) {
-// // If not disjoint can push in, put also retain it.
-// // if ( rightVars.containsAny()
-// // && right does not mention.
-//
-// pushLeft.add(expr) ;
-// pushed = true ;
-// }
-// // Right?????
-//
-// if ( !pushed )
-// unpushed.add(expr) ;
-// }
-//
-// if ( pushLeft.isEmpty() && pushRight.isEmpty() )
-// return opLeftJoin ;
-//
-// Op opLeftNew = left ;
-// if ( !pushLeft.isEmpty() )
-// opLeftNew = OpFilter.filter(pushLeft, opLeftNew) ;
-//
-// Op opRightNew = right ;
-// if ( !pushRight.isEmpty() )
-// opRightNew = OpFilter.filter(pushRight, opRightNew) ;
-//
-// // HACK
-// exprs.getList().clear() ;
-// exprs.getList().addAll(unpushed.getList()) ;
-//
-// Op op = OpLeftJoin.create(opLeftNew, opRightNew, (ExprList)null) ;
-// if ( opInitial != null )
-// op = OpSequence.create(opInitial, op) ;
-// return op ;
-// }
-//
-// private static <T> boolean disjoint(Collection<T> collection,
Collection<T> possibleElts) {
-// return CollectionUtils.disjoint(collection, possibleElts) ;
-// }
+
+ private static <T> boolean disjoint(Collection<T> collection,
Collection<T> possibleElts) {
+ return CollectionUtils.disjoint(collection, possibleElts) ;
+ }
+ /** Try to optimize (filter (extend ...)) */
+ private static Placement placeExtend(ExprList exprs, OpExtend input) {
+ return processExtendAssign(exprs, input) ;
+ }
+
+ private static Placement processExtendAssign(ExprList exprs,
OpExtendAssign input) {
+ // Could break up the VarExprList
+ Collection<Var> vars1 = input.getVarExprList().getVars() ;
+ ExprList pushed = new ExprList() ;
+ ExprList unpushed = new ExprList() ;
+
+ for ( Expr expr : exprs ) {
+ Set<Var> exprVars = expr.getVarsMentioned() ;
+ if ( disjoint(vars1, exprVars) )
+ pushed.add(expr);
+ else
+ unpushed.add(expr) ;
+ }
+
+ if ( pushed.isEmpty() )
+ return resultNoChange(input) ;
+
+ // (filter ... (extend ... ))
+ // ===>
+ // (extend ... (filter ... ))
+ Op opSub = input.getSubOp() ;
+
+ // And try down the expressions
+ Placement p = transform(pushed, opSub) ;
+
+ if ( p == null ) {
+ Op op1 = OpFilter.filter(exprs, opSub) ;
+ Op op2 = input.copy(op1) ; //, input.getVarExprList()) ;
//OpExtend.extend(op1, input.getVarExprList()) ;
+ return result(op2, unpushed) ;
+ }
+ Op op1 = OpFilter.filter(p.unplaced, p.op) ;
+ Op op2 = OpExtend.extend(op1, input.getVarExprList()) ;
+ return result(op2, unpushed) ;
+ }
+
+ private static Placement placeAssign(ExprList exprs, OpAssign input) {
+ return processExtendAssign(exprs, input) ;
+
+ }
// ---- Utilities
/** For any expression now in scope, wrap the op with a filter */
