Author: andy
Date: Thu Nov 14 16:51:06 2013
New Revision: 1541973
URL: http://svn.apache.org/r1541973
Log:
Filter placement experiments.
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_New.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=1541973&r1=1541972&r2=1541973&view=diff
==============================================================================
--- jena/Scratch/AFS/Dev/src-dev/opt/OptMain.java (original)
+++ jena/Scratch/AFS/Dev/src-dev/opt/OptMain.java Thu Nov 14 16:51:06 2013
@@ -18,19 +18,35 @@
package opt;
+import static opt.TransformFilterPlacement_New.insertAnyFilter ;
+
+import java.util.Collection ;
+import java.util.HashSet ;
+import java.util.Set ;
+
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.TransformFilterConjunction ;
+import com.hp.hpl.jena.sparql.algebra.* ;
+import com.hp.hpl.jena.sparql.algebra.op.OpFilter ;
+import com.hp.hpl.jena.sparql.algebra.op.OpJoin ;
+import com.hp.hpl.jena.sparql.algebra.op.OpSequence ;
+import com.hp.hpl.jena.sparql.core.Var ;
+import com.hp.hpl.jena.sparql.expr.Expr ;
+import com.hp.hpl.jena.sparql.expr.ExprList ;
import com.hp.hpl.jena.sparql.sse.SSE ;
+
public class OptMain {
public static void main(String... argv) throws Exception {
- // Cominations e.g. placement then equality
+ // What about covered left but partial right?
+ // Push left (join),)
+ // Push left (left join)
+ // Other cases
+
+ // Also TransformDistinctToReduced (JENA-585)and
TransformOrderByDistincApplication
+
+ // Combinations e.g. placement then equality
// JENA-383 : The query optimizer generates a suboptimal query plan in
case of nested optionals followed by a filter
@@ -45,7 +61,7 @@ public class OptMain {
// Need to say what was pushed.
- if ( true ) {
+ if ( false ) {
String input = "(filter (= ?x 123) (join (bgp (?s ?p ?x)) (bgp (?s
?p ?z)) ))" ;
Transform t_placement = new TransformFilterPlacement_New() ;
Op op1 = SSE.parseOp(input) ;
@@ -55,20 +71,100 @@ public class OptMain {
//System.exit(0) ;
}
+ // What about covered left but partial right?
+ // Push left (join),)
+ // Push left (left join)
+ // Other cases
+
if ( true ) {
- String x = "SELECT * { ?s ?p ?o . FILTER (13=14) FILTER(?o1 > 12)
FILTER(?o < 56) OPTIONAL { ?s ?p1 ?o1 } }" ;
+ String x = "SELECT * { {?s ?p ?o} . FILTER (13=14) FILTER(?o1 >
12) FILTER(?o < 56) FILTER(?o1+?o > 999) { ?s ?p1 ?o1 } }" ;
Query query = QueryFactory.create(x) ;
Op op1 = Algebra.compile(query) ;
+ /*
+Setting
+WriterLib.start(IndentedWriter out, String tag, int linePolicy)
+WriterLib.finish(IndentedWriter out, String tag)
+to use ""
+ */
+
System.out.println(op1) ;
- // && to list
- Op op2 = Transformer.transform(new TransformFilterConjunction(),
op1) ;
- //Op op2 = Algebra.optimize(op1) ;
- //System.out.println(op2) ;
+ ExprList exprs = ((OpFilter)op1).getExprs() ;
+ OpJoin opJoin = (OpJoin)((OpFilter)op1).getSubOp() ;
+
+ Set<Var> scope = new HashSet<Var>() ;
+ Op op = transformFilterJoin(exprs, scope, opJoin) ;
+ if ( ! exprs.isEmpty() )
+ op = OpFilter.filter(exprs, op) ;
- Op op3 = Transformer.transform(new TransformFilterPlacement_New(),
op2) ;
- System.out.println(op3) ;
+ System.out.println(op) ;
+
+// // && to list
+// Op op2 = Transformer.transform(new TransformFilterConjunction(),
op1) ;
+// //Op op2 = Algebra.optimize(op1) ;
+// //System.out.println(op2) ;
+//
+// Op op3 = Transformer.transform(new
TransformFilterPlacement_New(), op2) ;
+// System.out.println(op3) ;
System.exit(0) ;
}
}
+
+ private static Op transformFilterJoin(ExprList exprs, Set<Var> varScope,
OpJoin opJoin)
+ {
+
+ // Any filters that depend on no variables.
+ Op opInitial = insertAnyFilter(exprs, varScope, null) ;
+ if ( opInitial == opJoin )
+ opInitial = null ;
+
+ Op left = opJoin.getLeft() ;
+ Op right = opJoin.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() ;
+
+
+ for ( Expr expr : exprs ) {
+ Set<Var> vars = expr.getVarsMentioned() ;
+ boolean pushed = false ;
+
+ if ( leftVars.containsAll(vars) ) {
+ pushLeft.add(expr) ;
+ pushed = true ;
+ }
+ // If left only, make this "else if"
+
+ if ( rightVars.containsAll(vars) ) {
+ // Push right
+ pushRight.add(expr) ;
+ pushed = true ;
+ }
+
+ if ( ! pushed )
+ unpushed.add(expr);
+ }
+
+ if ( pushLeft.isEmpty() && pushRight.isEmpty() )
+ return opJoin ;
+
+ 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 = OpJoin.create(opLeftNew, opRightNew) ;
+ if ( opInitial != null )
+ op = OpSequence.create(opInitial, 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=1541973&r1=1541972&r2=1541973&view=diff
==============================================================================
--- jena/Scratch/AFS/Dev/src-dev/opt/TestFilterPlacement.java (original)
+++ jena/Scratch/AFS/Dev/src-dev/opt/TestFilterPlacement.java Thu Nov 14
16:51:06 2013
@@ -18,6 +18,7 @@
package opt ;
+import org.apache.jena.atlas.lib.StrUtils ;
import org.junit.Assert ;
import org.junit.Test ;
@@ -90,13 +91,37 @@ public class TestFilterPlacement {
"(join (filter (= ?x 123) (bgp (?s ?p ?x))) (bgp (?s ?p ?z)) )") ;
}
- // Join
+ // Join : two side push
@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() {
+ 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))))") ;
+
+ 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))))))") ;
+
+ test(x, y) ;
+ }
+
+
@Test
public void place_filter_conditional_01() {
// conditional
Modified: jena/Scratch/AFS/Dev/src-dev/opt/TransformFilterPlacement_New.java
URL:
http://svn.apache.org/viewvc/jena/Scratch/AFS/Dev/src-dev/opt/TransformFilterPlacement_New.java?rev=1541973&r1=1541972&r2=1541973&view=diff
==============================================================================
--- jena/Scratch/AFS/Dev/src-dev/opt/TransformFilterPlacement_New.java
(original)
+++ jena/Scratch/AFS/Dev/src-dev/opt/TransformFilterPlacement_New.java Thu Nov
14 16:51:06 2013
@@ -23,10 +23,9 @@
package opt;
-import java.util.HashSet ;
-import java.util.Iterator ;
-import java.util.List ;
-import java.util.Set ;
+import java.util.* ;
+
+import org.apache.jena.atlas.lib.CollectionUtils ;
import com.hp.hpl.jena.graph.Node ;
import com.hp.hpl.jena.graph.Triple ;
@@ -95,7 +94,7 @@ public class TransformFilterPlacement_Ne
return op ;
}
- private static Op transform(ExprList exprs, Set<Var> varsScope, Op input)
+ /*private*/ static Op transform(ExprList exprs, Set<Var> varsScope, Op
input)
{
Op opInitial = insertAnyFilter(exprs, varsScope, null) ;
// OpAssign/OpExtend could be done if the assignment and exprs are
independent.
@@ -272,31 +271,62 @@ public class TransformFilterPlacement_Ne
private static Op transformFilterJoin(ExprList exprs, Set<Var> varScope,
OpJoin opJoin)
{
+
// Any filters that depend on no variables.
Op opInitial = insertAnyFilter(exprs, varScope, null) ;
+ if ( opInitial == opJoin )
+ opInitial = null ;
- // Check: Can push down either side or both. Both is better.
-
- // WROnG: code removes
-
- // Be careful about exprs.
- // accumulate scope.
+ Op left = opJoin.getLeft() ;
+ Op right = opJoin.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() ;
+
+ for ( Expr expr : exprs ) {
+ Set<Var> vars = expr.getVarsMentioned() ;
+ boolean pushed = false ;
+
+ if ( leftVars.containsAll(vars) ) {
+ pushLeft.add(expr) ;
+ pushed = true ;
+ }
+ // If left only, make this "else if"
+
+ if ( rightVars.containsAll(vars) ) {
+ // Push right
+ pushRight.add(expr) ;
+ pushed = true ;
+ }
+
+ if ( ! pushed )
+ unpushed.add(expr);
+ }
- ExprList exprs1 = new ExprList(exprs) ;
- ExprList exprs2 = new ExprList(exprs) ;
+ if ( pushLeft.isEmpty() && pushRight.isEmpty() )
+ return opJoin ;
- Op opLeft = transform(exprs, varScope, opJoin.getLeft());
- Op opRight = transform(exprs, varScope, opJoin.getRight());
+ Op opLeftNew = left ;
+ if ( ! pushLeft.isEmpty() )
+ opLeftNew = OpFilter.filter(pushLeft, opLeftNew) ;
+
+ Op opRightNew = right ;
+ if ( ! pushRight.isEmpty() )
+ opRightNew = OpFilter.filter(pushRight, opRightNew) ;
- // WRONG
+ // HACK
exprs.getList().clear() ;
- //exprs.getList().addAll(exprs1.getList()) ;
+ exprs.getList().addAll(unpushed.getList()) ;
-
- Op op = OpJoin.create(opLeft, opRight) ;
- return OpSequence.create(opInitial, op) ;
+ Op op = OpJoin.create(opLeftNew, opRightNew) ;
+ if ( opInitial != null )
+ op = OpSequence.create(opInitial, op) ;
+ return op ;
}
+
// Modularize.
private static Op transformFilterConditional(ExprList exprs, Set<Var>
varScope, OpConditional opConditional)
{
@@ -308,25 +338,78 @@ public class TransformFilterPlacement_Ne
Op op = new OpConditional(left, right);
op = insertAnyFilter(exprs, varScope, op);
return OpSequence.create(opInitial, op) ;
- }
+ }
- // Modularize.
+ // Much in common with Join.
private static Op transformFilterLeftJoin(ExprList exprs, Set<Var>
varScope, OpLeftJoin opLeftJoin)
{
// Any filters that depend on no variables.
Op opInitial = insertAnyFilter(exprs, varScope, null) ;
- Op left = opLeftJoin.getLeft();
- left = transform(exprs, varScope, left);
- Op right = opLeftJoin.getRight();
- Op op = OpLeftJoin.create(left, right, opLeftJoin.getExprs());
- op = insertAnyFilter(exprs, varScope, op);
- return OpSequence.create(opInitial, op) ;
- }
+
+ 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() ;
+
+ 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 = OpJoin.create(opLeftNew, opRightNew) ;
+ 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) ;
+ }
// ---- Utilities
/** For any expression now in scope, wrap the op with a filter */
- private static Op insertAnyFilter(ExprList exprs, Set<Var>
patternVarsScope, Op op)
+ /*private*/ static Op insertAnyFilter(ExprList exprs, Set<Var>
patternVarsScope, Op op)
{
for ( Iterator<Expr> iter = exprs.iterator() ; iter.hasNext() ; )
{
