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 2013/11/17 19:51:29 UTC
svn commit: r1542794 - in /jena/Scratch/AFS/Dev/src-dev/opt: OptMain.java
TestFilterPlacement.java TransformFilterPlacement_Rewrite.java
Author: andy
Date: Sun Nov 17 18:51:28 2013
New Revision: 1542794
URL: http://svn.apache.org/r1542794
Log:
Better Filter Placement
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/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=1542794&r1=1542793&r2=1542794&view=diff
==============================================================================
--- jena/Scratch/AFS/Dev/src-dev/opt/OptMain.java (original)
+++ jena/Scratch/AFS/Dev/src-dev/opt/OptMain.java Sun Nov 17 18:51:28 2013
@@ -18,21 +18,44 @@
package opt;
+import static com.hp.hpl.jena.sparql.algebra.optimize.Optimize.apply ;
import org.apache.jena.atlas.lib.StrUtils ;
import com.hp.hpl.jena.query.ARQ ;
import com.hp.hpl.jena.query.Query ;
import com.hp.hpl.jena.query.QueryFactory ;
-import com.hp.hpl.jena.sparql.algebra.Algebra ;
-import com.hp.hpl.jena.sparql.algebra.Op ;
-import com.hp.hpl.jena.sparql.algebra.Transform ;
-import com.hp.hpl.jena.sparql.algebra.Transformer ;
-import com.hp.hpl.jena.sparql.algebra.optimize.TransformJoinStrategy ;
+import com.hp.hpl.jena.sparql.ARQConstants ;
+import com.hp.hpl.jena.sparql.algebra.* ;
+import com.hp.hpl.jena.sparql.algebra.op.OpLabel ;
+import com.hp.hpl.jena.sparql.algebra.optimize.* ;
+import com.hp.hpl.jena.sparql.algebra.optimize.Optimize.RewriterFactory ;
import com.hp.hpl.jena.sparql.sse.SSE ;
+import com.hp.hpl.jena.sparql.util.Context ;
public class OptMain {
public static void main(String... argv) throws Exception {
+ {
+ String DIR = "/home/afs/Jena/jena-arq/testing/ARQ/OptFilterEquality" ;
+
+ //arq.sparql.main("--engine=ref", "--query="+DIR+"/filter-equality-13.rq", "--data="+DIR+"/data-4.ttl");
+ //arq.sparql.main( "--query="+DIR+"/filter-equality-13.rq", "--data="+DIR+"/data-4.ttl");
+
+ Query q = QueryFactory.read(DIR+"/filter-equality-13.rq") ;
+ Op op1 = Algebra.compile(q) ;
+ Op op2 = Algebra.optimize(op1) ;
+ System.out.println(op2);
+ rewire() ;
+ op2 = Algebra.optimize(op1) ;
+ System.out.println(op2);
+
+
+ //arq.sparql.main( "--query="+DIR+"/filter-equality-13.rq", "--data="+DIR+"/data-4.ttl");
+
+ System.exit(0) ;
+ }
+ // Project (and other blockers?)
+
// Tests
// coverage,
// repeated application.
@@ -73,19 +96,44 @@ public class OptMain {
// Was Op.equals a good idea?
// Calculate vars for an expr once and cache : op.getVars.
- // XXX Push recursively.
+ // Push in inside a sequence?
+
+
+
+ // Checking:
+ // filter-equality-13 -- scope issue for leftjoin, conditional in a sequence.
+ // Can't push in the filer to the sequence as may yield no binding -> need fixed vars
+ // TestTranformFilters :
+ // optionalEqualitySubQuery_01 -- looks OK -- JENA-432
+ // optionalEquality_01 JENA-383 -- WRONG - Lost RHS of conditional
+ // optionalEqualityScope_01 -- WRONG -
+
+ // Double push in a sequence of conditional then BGP.
+ // JonStartegy and FilterPlacement interaction.
if ( false ) {
- String input = "(filter ((= ?A 2) (= ?z 99) (= ?x 123)) (bgp (?s ?p ?x) (?s ?p ?z)) )" ;
+ //String input = "(filter (?x 123) (sequence (conditional (table unit)
+ String input = 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))))"
+ ) ;
+
Transform t_placement = new TransformFilterPlacement_Rewrite() ;
Op op1 = SSE.parseOp(input) ;
- Op op2 = Transformer.transform(t_placement, op1) ;
+ Op op2 = op1 ;
+ op2 = Algebra.optimize(op1) ;
+ op2 = Transformer.transform(t_placement, op1) ;
+
System.out.print(op2) ;
System.out.println("------------------------");
System.exit(0) ;
}
- if ( false ) {
+ if ( true ) {
String qs1 = StrUtils.strjoinNL
("PREFIX ex: <http://example.org/test#>",
"SELECT * WHERE {",
@@ -98,17 +146,20 @@ public class OptMain {
" }",
" 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)",
- "}") ;
+
+ // Order dependency.
+ // Push LHS and RHS on a JOIN then sequence => Filter twice in sequence. No harm but ...
+
+ String qs3 = StrUtils.strjoinNL
+ ( "PREFIX : <http://example/> SELECT * {"
+ , " OPTIONAL { ?x :q ?o }"
+ , " FILTER(?x = :x)"
+ , " ?x :p ?o2"
+ , "}"
+ ) ;
+
- Query query = QueryFactory.create(qs2) ;
+ Query query = QueryFactory.create(qs3) ;
Op op1 = Algebra.compile(query) ;
System.out.println("** Input") ;
System.out.println(op1) ;
@@ -118,44 +169,145 @@ public class OptMain {
System.out.println(op2) ;
}
System.out.println("** NEW") ;
- ARQ.getContext().set(ARQ.optFilterPlacement, false);
- Transform t_placement = new TransformFilterPlacement_Rewrite() ;
- Op op2 = Algebra.optimize(op1) ;
- Op op3 = Transformer.transform(t_placement, op2) ;
- System.out.println(op3) ;
+ //Op op2 = new Rewrite2(ARQ.getContext()).rewrite(op1) ;
+ Op op2 = op1 ;
+ op2 = Transformer.transform(new TransformJoinStrategy(), op2) ;
+ op2 = placement(op2) ;
+ System.out.println(op2) ;
System.exit(0) ;
}
- // Extend test
-
- // What about covered left but partial right?
- // Push left (join),)
- // Push left (left join)
- // Other cases
+ }
+
+ static Op placement(Op op) {
+ return Transformer.transform(new TransformFilterPlacement_Rewrite(), op) ;
+ }
+
+ private static void rewire() {
+ Optimize.setFactory(new RewriterFactory2());
+ }
+
+ static class RewriterFactory2 implements RewriterFactory {
+
+ @Override
+ public Rewrite create(Context context) {
+ return new Rewrite2(context) ;
+ }
+ }
+
+ static class Rewrite2 implements Rewrite {
- if ( true ) {
- //String x = "SELECT * { {?s ?p ?o} . FILTER (13=14) FILTER(?o1 > 12) FILTER(?o < 56) FILTER(?o1+?o > 999) { ?s ?p1 ?o1 } }" ;
- String x = "SELECT * { {?s ?p ?o} . FILTER (13=14) FILTER(?o1 > 12) FILTER(?o < 56) FILTER(?o1+?o > 999) OPTIONAL { ?s ?p1 ?o1 } }" ;
- Transform t_placement = new TransformFilterPlacement_Rewrite() ;
- Transform t_join = new TransformJoinStrategy() ;
- Query query = QueryFactory.create(x) ;
- Op op1 = Algebra.compile(query) ;
- op1 = Transformer.transform(t_join, op1) ;
- System.out.println(op1) ;
- Op op2 = op1 ;
- for ( int i = 0 ; i < 3 ; i++ ) {
- op2 = Transformer.transform(t_placement, op2) ;
- System.out.println(op2) ;
+ private Context context ;
+
+ public Rewrite2(Context context) {
+ this.context = context ;
+ }
+
+ @Override
+ public Op rewrite(Op op)
+ {
+ System.out.println("Rewrite2") ;
+ Context context = ARQ.getContext() ;
+ // Record optimizer
+ if ( context.get(ARQConstants.sysOptimizer) == null )
+ context.set(ARQConstants.sysOptimizer, this) ;
+
+ if ( false )
+ {
+ // Removal of "group of one" join (AKA SPARQL "simplification")
+ // is done during algebra generation in AlgebraGenerator
+ op = apply("Simplify", new TransformSimplify(), op) ;
+ op = apply("Delabel", new TransformRemoveLabels(), op) ;
}
- /*
-Setting
-WriterLib.start(IndentedWriter out, String tag, int linePolicy)
-WriterLib.finish(IndentedWriter out, String tag)
-to use ""
- */
+
+ // ** TransformScopeRename::
+ // This is a requirement for the linearization execution that the default
+ // ARQ query engine uses where possible.
+ // This transformation must be done (e.g. by QueryEngineBase) if no other optimization is done.
+ op = TransformScopeRename.transform(op) ;
+
+ // Prepare expressions.
+ OpWalker.walk(op, new OpVisitorExprPrepare(context)) ;
+
+ // Need to allow subsystems to play with this list.
+ if ( context.isTrueOrUndef(ARQ.propertyFunctions) )
+ op = apply("Property Functions", new TransformPropertyFunction(context), op) ;
- System.exit(0) ;
+ if ( context.isTrueOrUndef(ARQ.optFilterConjunction) )
+ op = apply("filter conjunctions to ExprLists", new TransformFilterConjunction(), op) ;
+
+ if ( context.isTrueOrUndef(ARQ.optFilterExpandOneOf) )
+ op = apply("Break up IN and NOT IN", new TransformExpandOneOf(), op) ;
+
+ // Either, do filter placement and other sequence generating transformations.
+ // or improve to place in a sequence (latter is better?)
+
+ if ( context.isTrueOrUndef(ARQ.optFilterImplicitJoin) )
+ op = apply("Filter Implicit Join", new TransformFilterImplicitJoin(), op);
+
+ if ( context.isTrueOrUndef(ARQ.optImplicitLeftJoin) )
+ op = apply("Implicit Left Join", new TransformImplicitLeftJoin(), op);
+
+ if ( context.isTrueOrUndef(ARQ.optFilterEquality) )
+ {
+ //boolean termStrings = context.isDefined(ARQ.optTermStrings) ;
+ op = apply("Filter Equality", new TransformFilterEquality(), op) ;
+ }
+
+ // Can promote table empty at this point since only the implicit join optimizations
+ // are currently capable of introducing it
+ if ( context.isTrueOrUndef(ARQ.optPromoteTableEmpty) )
+ op = apply("Table Empty Promotion", new TransformPromoteTableEmpty(), op) ;
+
+ if ( context.isTrueOrUndef(ARQ.optFilterDisjunction) )
+ op = apply("Filter Disjunction", new TransformFilterDisjunction(), op) ;
+
+ // ***** After JoinStrategy (or don't push left and right in join).
+ if ( context.isTrueOrUndef(ARQ.optFilterPlacement) )
+ // *****
+ op = apply("Filter Placement", new TransformFilterPlacement_Rewrite(), op) ;
+
+
+ if ( context.isTrueOrUndef(ARQ.optTopNSorting) )
+ op = apply("TopN Sorting", new TransformTopN(), op) ;
+
+ // ORDER BY+DISTINCT optimizations
+ // We apply the one that changes evaluation order first since when it does apply it will give much
+ // better performance than just transforming DISTINCT to REDUCED
+
+ if ( context.isTrueOrUndef(ARQ.optOrderByDistinctApplication) )
+ op = apply("Apply DISTINCT prior to ORDER BY where possible", new TransformOrderByDistinctAppplication(), op);
+
+ // 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.
+ // Also done in the AlgebraGenerator so this transform step catches programmatically built op expressions
+ op = apply("Path flattening", new TransformPathFlattern(), op) ;
+
+ // Find joins/leftJoin that can be done by index joins (generally preferred as fixed memory overhead).
+ if ( context.isTrueOrUndef(ARQ.optIndexJoinStrategy) )
+ op = apply("Index Join strategy", new TransformJoinStrategy(), op) ;
+
+// // ***** After JoinStrategy (or don't push left and right in join).
+// if ( context.isTrueOrUndef(ARQ.optFilterPlacement) )
+// // *****
+// op = apply("Filter Placement", new TransformFilterPlacement_Rewrite(), op) ;
+
+ // Merge adjacent BGPs
+ if ( context.isTrueOrUndef(ARQ.optMergeBGPs) )
+ op = apply("Merge BGPs", new TransformMergeBGPs(), op) ;
+
+ // Mark
+ if ( false )
+ op = OpLabel.create("Transformed", op) ;
+ return op ;
}
+
+
}
+
}
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=1542794&r1=1542793&r2=1542794&view=diff
==============================================================================
--- jena/Scratch/AFS/Dev/src-dev/opt/TestFilterPlacement.java (original)
+++ jena/Scratch/AFS/Dev/src-dev/opt/TestFilterPlacement.java Sun Nov 17 18:51:28 2013
@@ -29,88 +29,103 @@ 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() {
+
+ // ** Filter
+
+ @Test public void place_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_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_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_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_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_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_no_match_03() {
test("(filter (= ?x ?unbound) (bgp (?s ?p ?x) (?s1 ?p1 ?XX)))", null) ;
}
- @Test public void place_filter_sequence_01() {
+ @Test public void place_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_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
+ // LHS. The RHS can't introduce ?x because it would not be a legal sequence
// if, for example, it had a BIND in it.
test("(filter (= ?x 123) (sequence (bgp (?s ?p ?x)) (bgp (?s ?p ?x)) ))",
"(sequence (filter (= ?x 123) (bgp (?s ?p ?x))) (bgp (?s ?p ?x)) )") ;
}
- @Test public void place_filter_sequence_03() {
- test("(filter (= ?z 123) (sequence (bgp (?s ?p ?x)) (bgp (?s ?p ?z)) ))",
+ @Test public void place_sequence_03() {
+ test("(filter (= ?x 123) (sequence (bgp (?s ?p ?x)) (bgp (?s ?p ?x1)) (bgp (?s ?p ?x2)) ))",
+ "(sequence (filter (= ?x 123) (bgp (?s ?p ?x))) (bgp (?s ?p ?x1)) (bgp (?s ?p ?x2)) )") ;
+ }
+
+ @Test public void place_sequence_04() {
+ test("(filter (= ?x 123) (sequence (bgp (?s ?p ?x1)) (bgp (?s ?p ?x)) (bgp (?s ?p ?x2)) ))",
+ "(sequence (bgp (?s ?p ?x1)) (filter (= ?x 123) (bgp (?s ?p ?x))) (bgp (?s ?p ?x2)) )") ;
+ }
+
+ @Test public void place_sequence_05() {
+ test("(filter (= ?x 123) (sequence (bgp (?s ?p ?x1) (?s ?p ?x)) (bgp (?s ?p ?x2)) ))",
+ "(sequence (filter (= ?x 123) (bgp (?s ?p ?x1) (?s ?p ?x))) (bgp (?s ?p ?x2)) )") ;
+ }
+
+ @Test public void place_sequence_06() {
+ test("(filter (= ?x 123) (sequence (bgp (?s ?p ?x1) (?s ?p ?x2)) (bgp (?s ?p ?x)) ))",
+ "(sequence (bgp (?s ?p ?x1) (?s ?p ?x2)) (filter (= ?x 123) (bgp (?s ?p ?x))) )") ;
+ }
+
+ @Test public void place_sequence_07() {
+ test("(filter (= ?A 123) (sequence (bgp (?s ?p ?x)) (bgp (?s ?p ?z)) ))",
+ null) ;
+ }
+
+ @Test public void place_sequence_08() {
+ test("(sequence (bgp (?s ?p ?x)) (filter (= ?z 123) (bgp (?s ?p ?z))) )",
null) ;
}
// Join : one sided push.
- @Test public void place_filter_join_01() {
+ @Test public void place_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_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_join_03() {
String x = StrUtils.strjoinNL
("(filter ((= 13 14) (> ?o1 12) (< ?o 56) (< (+ ?o ?o1) 999))",
" (join",
" (bgp (triple ?s ?p ?o))" ,
" (bgp (triple ?s ?p1 ?o1))))") ;
- // If extracting unrelated filters early ...
-// String y = StrUtils.strjoinNL
-// ("(filter (< (+ ?o ?o1) 999)",
-// " (sequence",
-// " (filter (= 13 14)",
-// " (table unit))",
-// " (join",
-// " (filter (< ?o 56)",
-// " (bgp (triple ?s ?p ?o)))",
-// " (filter (> ?o1 12)",
-// " (bgp (triple ?s ?p1 ?o1))))))") ;
-
- // Everything pushed down.
+ // Everything pushed down once.
String y = StrUtils.strjoinNL
("(filter (< (+ ?o ?o1) 999)",
" (join",
@@ -137,30 +152,54 @@ public class TestFilterPlacement extends
}
- @Test public void place_filter_conditional_01() {
- // conditional
+ @Test public void place_conditional_01() {
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() {
- // conditional
+ @Test public void place_conditional_02() {
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() {
- // conditional
+ @Test public void place_conditional_03() {
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)) )") ;
}
- // ** Sequence
-
- // ** LeftJoin
+ @Test public void place_leftjoin_01() {
+ // conditional
+ test("(filter (= ?x 123) (leftjoin (bgp (?s ?p ?x)) (bgp (?s ?p ?z)) ))",
+ "(leftjoin (filter (= ?x 123) (bgp (?s ?p ?x))) (bgp (?s ?p ?z)) )") ;
+ }
+
+ @Test public void place_leftjoin_02() {
+ // conditional
+ test("(filter (= ?z 123) (leftjoin (bgp (?s ?p ?x)) (bgp (?s ?p ?z)) ))",
+ "(filter (= ?z 123) (leftjoin (bgp (?s ?p ?x)) (bgp (?s ?p ?z)) ))") ;
+ }
+
+ @Test public void place_leftjoin_03() {
+ // conditional
+ test("(filter (= ?x 123) (leftjoin (bgp (?s ?p ?x)) (bgp (?s ?p ?x)) ))",
+ "(leftjoin (filter (= ?x 123) (bgp (?s ?p ?x))) (bgp (?s ?p ?x)) )") ;
+ }
- // ** Extend
+ @Test public void place_project_01() {
+ test("(filter (= ?x 123) (project (?x) (bgp (?s ?p ?x)) ))",
+ "(project (?x) (filter (= ?x 123) (bgp (?s ?p ?x)) ))") ;
+ }
+
+ @Test public void place_project_02() {
+ test("(filter (= ?x 123) (project (?s) (bgp (?s ?p ?x)) ))",
+ null) ;
+ }
+ @Test public void place_project_03() {
+ test("(filter (= ?x 123) (project (?x) (bgp (?s ?p ?x) (?s ?p ?z) ) ))",
+ "(project (?x) (sequence (filter (= ?x 123) (bgp (?s ?p ?x)) ) (bgp (?s ?p ?z))) )") ;
+ }
+
@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)) ))") ;
@@ -173,11 +212,35 @@ public class TestFilterPlacement extends
@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))) )") ;
+ "(extend (?x1 123) (sequence (filter ((= ?x 123) (< ?x 456)) (bgp (?s ?p ?x))) (bgp (?s ?p ?z))) )") ;
}
- // ** Assign
+ @Test public void place_assign_01() {
+ test("(filter (= ?x 123) (assign ((?z 123)) (bgp (?s ?p ?x)) ))",
+ "(assign ((?z 123)) (filter (= ?x 123) (bgp (?s ?p ?x)) ))") ;
+ }
+ @Test public void place_assign_02() { // Blocked
+ test("(filter (= ?x 123) (assign ((?x 123)) (bgp (?s ?p ?z)) ))",
+ null) ;
+ }
+
+ @Test public void place_assign_03() {
+ // Caution - OpFilter equality is sensitive to the order of expressions
+ test("(filter (= ?x 123) (assign ((?x1 123)) (filter (< ?x 456) (bgp (?s ?p ?x) (?s ?p ?z))) ))",
+ "(assign (?x1 123) (sequence (filter ((= ?x 123) (< ?x 456)) (bgp (?s ?p ?x))) (bgp (?s ?p ?z))) )") ;
+ }
+
+ @Test public void place_filter_01() {
+ test("(filter (= ?x 123) (filter (= ?y 456) (bgp (?s ?p ?x) (?s ?p ?y)) ))" ,
+ "(filter (= ?y 456) (sequence (filter (= ?x 123) (bgp (?s ?p ?x))) (bgp (?s ?p ?y)) ))" ) ;
+ }
+
+ @Test public void place_filter_02() {
+ test("(filter (= ?x 123) (filter (= ?y 456) (bgp (?s ?p ?x) (?s ?p ?y) (?s ?p ?z) )))" ,
+ "(sequence (filter (= ?y 456) (sequence (filter (= ?x 123) (bgp (?s ?p ?x))) (bgp (?s ?p ?y)))) (bgp (?s ?p ?z)))") ;
+ }
+
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/TransformFilterPlacement_Rewrite.java
URL: http://svn.apache.org/viewvc/jena/Scratch/AFS/Dev/src-dev/opt/TransformFilterPlacement_Rewrite.java?rev=1542794&r1=1542793&r2=1542794&view=diff
==============================================================================
--- jena/Scratch/AFS/Dev/src-dev/opt/TransformFilterPlacement_Rewrite.java (original)
+++ jena/Scratch/AFS/Dev/src-dev/opt/TransformFilterPlacement_Rewrite.java Sun Nov 17 18:51:28 2013
@@ -16,11 +16,6 @@
* limitations under the License.
*/
-/* Contains code submitted in email to jena-user@incubator.apache.org
- * so software grant and relicensed under the Apache Software License.
- * placeFilterConditional
- */
-
package opt ;
import java.util.Collection ;
@@ -73,7 +68,7 @@ public class TransformFilterPlacement_Re
}
public static Op transform(ExprList exprs, BasicPattern bgp) {
- Placement placement = placeFilterBGP(exprs, bgp) ;
+ Placement placement = placeBGP(exprs, bgp) ;
Op op = ( placement == null ) ? new OpBGP(bgp) : placement.op ;
if ( placement != null )
op = buildFilter(placement.unplaced, op) ;
@@ -81,7 +76,7 @@ public class TransformFilterPlacement_Re
}
public static Op transform(ExprList exprs, Node graphNode, BasicPattern bgp) {
- Placement placement = placeFilterQuadPattern(exprs, graphNode, bgp) ;
+ Placement placement = placeQuadPattern(exprs, graphNode, bgp) ;
Op op = ( placement == null ) ? new OpQuadPattern(graphNode, bgp) : placement.op ;
if ( placement != null )
op = buildFilter(placement.unplaced, op) ;
@@ -113,23 +108,30 @@ public class TransformFilterPlacement_Re
Placement placement = null ;
if ( input instanceof OpBGP )
- placement = placeFilterBGP(exprs, (OpBGP)input) ;
+ placement = placeBGP(exprs, (OpBGP)input) ;
else if ( input instanceof OpSequence )
- placement = placeFilterSequence(exprs, (OpSequence)input) ;
+ placement = placeSequence(exprs, (OpSequence)input) ;
else if ( input instanceof OpQuadPattern )
- placement = placeFilterQuadPattern(exprs, (OpQuadPattern)input) ;
+ placement = placeQuadPattern(exprs, (OpQuadPattern)input) ;
else if ( input instanceof OpJoin )
- placement = placeFilterJoin(exprs, (OpJoin)input) ;
+ placement = placeJoin(exprs, (OpJoin)input) ;
else if ( input instanceof OpConditional )
- placement = placeFilterConditional(exprs, (OpConditional)input) ;
+ placement = placeConditional(exprs, (OpConditional)input) ;
else if ( input instanceof OpLeftJoin )
- placement = placeFilterLeftJoin(exprs, (OpLeftJoin)input) ;
+ placement = placeLeftJoin(exprs, (OpLeftJoin)input) ;
else if ( input instanceof OpFilter )
placement = placeFilter(exprs, (OpFilter)input) ;
+ // These are operations where chnaging the order of operations
+ // does not in itself make a differencebut enables expressions
+ // to be pushed own down to where they might make a difference.
+ // Otherwise these would blockers.
+
else if ( input instanceof OpExtend )
placement = placeExtend(exprs, (OpExtend)input) ;
else if ( input instanceof OpAssign )
placement = placeAssign(exprs, (OpAssign)input) ;
+ else if ( input instanceof OpProject )
+ placement = placeProject(exprs, (OpProject)input) ;
return placement ;
}
@@ -138,18 +140,26 @@ public class TransformFilterPlacement_Re
return result(op, exprs) ;
}
- // == The placeFilter* modify the exprs and patternVarsScope arguments
-
+
+
private static Placement placeFilter(ExprList exprs, OpFilter input) {
- // XXX Recurse ??
- return result(input, exprs) ;
+ Placement p = transform(exprs, input.getSubOp()) ;
+ if ( p == null )
+ p = new Placement(input.getSubOp(), exprs) ;
+ // These would have already been placed (bottom up conversion)
+ // so no point in including in the transform() call above.
+ p.unplaced.addAll(input.getExprs());
+ return p ;
+// ExprList exprs2 = new ExprList(exprs) ;
+// exprs2.addAll(input.getExprs()) ;
+// return transform(exprs2, input.getSubOp()) ;
}
- private static Placement placeFilterBGP(ExprList exprs, OpBGP x) {
- return placeFilterBGP(exprs, x.getPattern()) ;
+ private static Placement placeBGP(ExprList exprs, OpBGP x) {
+ return placeBGP(exprs, x.getPattern()) ;
}
- private static Placement placeFilterBGP(ExprList exprsIn, BasicPattern pattern) {
+ private static Placement placeBGP(ExprList exprsIn, BasicPattern pattern) {
ExprList exprs = new ExprList(exprsIn) ;
Set<Var> patternVarsScope = DS.set() ;
// Any filters that depend on no variables.
@@ -198,11 +208,11 @@ public class TransformFilterPlacement_Re
return null ;
}
- private static Placement placeFilterQuadPattern(ExprList exprs, OpQuadPattern pattern) {
- return placeFilterQuadPattern(exprs, pattern.getGraphNode(), pattern.getBasicPattern()) ;
+ private static Placement placeQuadPattern(ExprList exprs, OpQuadPattern pattern) {
+ return placeQuadPattern(exprs, pattern.getGraphNode(), pattern.getBasicPattern()) ;
}
- private static Placement placeFilterQuadPattern(ExprList exprsIn, Node graphNode, BasicPattern pattern) {
+ private static Placement placeQuadPattern(ExprList exprsIn, Node graphNode, BasicPattern pattern) {
ExprList exprs = new ExprList(exprsIn) ;
Set<Var> patternVarsScope = DS.set() ;
// Any filters that depend on no variables.
@@ -261,7 +271,7 @@ public class TransformFilterPlacement_Re
* orginal query.
*/
- private static Placement placeFilterSequence(ExprList exprsIn, OpSequence opSequence) {
+ private static Placement placeSequence(ExprList exprsIn, OpSequence opSequence) {
ExprList exprs = new ExprList(exprsIn) ;
Set<Var> varScope = DS.set() ;
List<Op> ops = opSequence.getElements() ;
@@ -269,11 +279,14 @@ public class TransformFilterPlacement_Re
Op op = null ;
for (Iterator<Op> iter = ops.iterator(); iter.hasNext();) {
+ // Does not push in.
op = insertAnyFilter(exprs, varScope, op) ;
Op seqElt = iter.next() ;
- // XXX Recurse
- //seqElt = transformOp(exprs, seqElt) ;
- // Merge into sequence.
+ Placement p = transform(exprs, seqElt) ;
+ if ( p != null ) {
+ exprs = p.unplaced ;
+ seqElt = p.op ;
+ }
varScope.addAll(OpVars.mentionedVars(seqElt)) ;
op = OpSequence.create(op, seqElt) ;
}
@@ -285,7 +298,7 @@ public class TransformFilterPlacement_Re
// If this is run after join->sequence, then this is good to do.
static boolean pushRightAsWellAsLeft = true ;
- private static Placement placeFilterJoin(ExprList exprs, OpJoin opJoin) {
+ private static Placement placeJoin(ExprList exprs, OpJoin opJoin) {
Op left = opJoin.getLeft() ;
Op right = opJoin.getRight() ;
Collection<Var> leftVars = OpVars.mentionedVars(left) ;
@@ -334,27 +347,23 @@ public class TransformFilterPlacement_Re
/* A conditional is left join without scoping complications.
*/
- private static Placement placeFilterConditional(ExprList exprs, OpConditional opConditional) {
- // Push LHS only.
+ private static Placement placeConditional(ExprList exprs, OpConditional opConditional) {
Op left = opConditional.getLeft() ;
Op right = opConditional.getRight() ;
Placement nLeft = transform(exprs, left) ;
if ( nLeft == null )
- result(null, exprs) ;
- // XXX Recurse
+ return result(opConditional, exprs) ;
Op op = new OpConditional(nLeft.op, right) ;
return result(op, nLeft.unplaced) ;
}
-// private static Placement placeFilterLeftJoin(ExprList exprs, OpLeftJoin opLeftJoin) { throw new NotImplemented() ; }
-
- private static Placement placeFilterLeftJoin(ExprList exprs, OpLeftJoin opLeftJoin) {
- // Push LHS only.
+ private static Placement placeLeftJoin(ExprList exprs, OpLeftJoin opLeftJoin) {
+ // Push LHS only.
Op left = opLeftJoin.getLeft() ;
Op right = opLeftJoin.getRight() ;
Placement nLeft = transform(exprs, left) ;
if ( nLeft == null )
- result(null, exprs) ;
+ return result(opLeftJoin, exprs) ;
Op op = OpLeftJoin.create(nLeft.op, right, opLeftJoin.getExprs()) ;
return result(op, nLeft.unplaced) ;
}
@@ -368,6 +377,11 @@ public class TransformFilterPlacement_Re
return processExtendAssign(exprs, input) ;
}
+ private static Placement placeAssign(ExprList exprs, OpAssign input) {
+ return processExtendAssign(exprs, input) ;
+
+ }
+
private static Placement processExtendAssign(ExprList exprs, OpExtendAssign input) {
// Could break up the VarExprList
Collection<Var> vars1 = input.getVarExprList().getVars() ;
@@ -394,20 +408,41 @@ public class TransformFilterPlacement_Re
Placement p = transform(pushed, opSub) ;
if ( p == null ) {
- Op op1 = OpFilter.filter(exprs, opSub) ;
+ Op op1 = OpFilter.filter(pushed, 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()) ;
+ Op op2 = input.copy(op1) ;
return result(op2, unpushed) ;
}
- private static Placement placeAssign(ExprList exprs, OpAssign input) {
- return processExtendAssign(exprs, input) ;
+ private static Placement placeProject(ExprList exprs, OpProject input) {
+ Collection<Var> varsProject = input.getVars() ;
+ ExprList pushed = new ExprList() ;
+ ExprList unpushed = new ExprList() ;
+ for ( Expr expr : exprs ) {
+ Set<Var> exprVars = expr.getVarsMentioned() ;
+ if ( varsProject.containsAll(exprVars) )
+ pushed.add(expr);
+ else
+ unpushed.add(expr) ;
+ }
+ if ( pushed.isEmpty() )
+ return resultNoChange(input) ;
+ // (filter (project ...)) ===> (project (filter ...))
+ Op opSub = input.getSubOp() ;
+ Placement p = transform(pushed, opSub) ;
+ if ( p == null ) {
+ Op op1 = OpFilter.filter(pushed, opSub) ;
+ Op op2 = input.copy(op1) ;
+ return result(op2, unpushed) ;
+ }
+ Op op1 = OpFilter.filter(p.unplaced, p.op) ;
+ Op op2 = input.copy(op1) ;
+ return result(op2, unpushed) ;
}
- // ---- Utilities
/** For any expression now in scope, wrap the op with a filter */
private static Op insertAnyFilter(ExprList exprs, Set<Var> patternVarsScope, Op op) {