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/03/15 20:43:44 UTC
svn commit: r1577924 - in /jena/trunk/jena-arq/src:
main/java/com/hp/hpl/jena/sparql/algebra/op/
main/java/com/hp/hpl/jena/sparql/algebra/optimize/
test/java/com/hp/hpl/jena/sparql/algebra/optimize/
Author: andy
Date: Sat Mar 15 19:43:43 2014
New Revision: 1577924
URL: http://svn.apache.org/r1577924
Log:
Proper fix for JENA-652 : consider each expression separately
Modified:
jena/trunk/jena-arq/src/main/java/com/hp/hpl/jena/sparql/algebra/op/OpFilter.java
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
Modified: jena/trunk/jena-arq/src/main/java/com/hp/hpl/jena/sparql/algebra/op/OpFilter.java
URL: http://svn.apache.org/viewvc/jena/trunk/jena-arq/src/main/java/com/hp/hpl/jena/sparql/algebra/op/OpFilter.java?rev=1577924&r1=1577923&r2=1577924&view=diff
==============================================================================
--- jena/trunk/jena-arq/src/main/java/com/hp/hpl/jena/sparql/algebra/op/OpFilter.java (original)
+++ jena/trunk/jena-arq/src/main/java/com/hp/hpl/jena/sparql/algebra/op/OpFilter.java Sat Mar 15 19:43:43 2014
@@ -30,6 +30,7 @@ public class OpFilter extends Op1
{
protected ExprList expressions ;
+ /** Add expression - mutates an existing filter */
public static Op filter(Expr expr, Op op)
{
OpFilter f = filter(op) ;
@@ -45,6 +46,7 @@ public class OpFilter extends Op1
return new OpFilter(op) ;
}
+ /** Add expressions - mutates an existing filter */
public static Op filter(ExprList exprs, Op op)
{
if ( exprs.isEmpty() )
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=1577924&r1=1577923&r2=1577924&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 Sat Mar 15 19:43:43 2014
@@ -18,10 +18,7 @@
package com.hp.hpl.jena.sparql.algebra.optimize ;
-import java.util.Collection ;
-import java.util.Iterator ;
-import java.util.List ;
-import java.util.Set ;
+import java.util.* ;
import org.apache.jena.atlas.lib.CollectionUtils ;
import org.apache.jena.atlas.lib.DS ;
@@ -54,7 +51,10 @@ public class TransformFilterPlacement ex
Placement(Op op, ExprList remaining) { this.op = op ; this.unplaced = remaining ; }
}
- static final ExprList emptyList = new ExprList() ;
+ // Empty, immutable ExprList
+ static final ExprList emptyList = ExprList.emptyList ;
+
+ // No placement performed
static final Placement noChangePlacement = null ; //new Placement(null, null) ;
private static Placement result(Op op, ExprList remaining) {
@@ -107,7 +107,8 @@ public class TransformFilterPlacement ex
return op ;
}
- private Op transformOp(ExprList exprs, Op x) {
+ /** Transform and always at least wrap the op with the exprs */
+ private Op transformOpAlways(ExprList exprs, Op x) {
Placement placement = transform(exprs, x) ;
if ( placement == null )
return buildFilter(exprs, x) ;
@@ -146,20 +147,23 @@ public class TransformFilterPlacement ex
placement = placeAssign(exprs, (OpAssign)input) ;
else if ( input instanceof OpProject )
placement = placeProject(exprs, (OpProject)input) ;
+ else if ( input instanceof OpTable )
+ placement = placeTable(exprs, (OpTable)input) ;
return placement ;
}
private Placement placeFilter(ExprList exprs, OpFilter input) {
- // Thrown the filter expressions into the
- if ( exprs.size() != 0 ) {
- exprs = ExprList.copy(exprs) ;
- exprs.addAll(input.getExprs());
- } else
- exprs = input.getExprs() ;
-
- Placement p = transform(exprs, input.getSubOp()) ;
- return p ;
+ if ( exprs.size() == 0 )
+ // Unpack the filter,
+ return transform(input.getExprs(), input.getSubOp()) ;
+
+ // Thrown the filter expressions into the general list to be placed.
+ // Add to keep the application order (original filter then additional exprs)
+ // Not important, but nice.
+ ExprList exprs2 = ExprList.copy(input.getExprs()) ;
+ exprs2.addAll(exprs);
+ return transform(exprs2, input.getSubOp()) ;
}
private Placement placeOrWrapBGP(ExprList exprs, OpBGP x) {
@@ -182,7 +186,7 @@ public class TransformFilterPlacement ex
for (Triple triple : pattern) {
// Place any filters that are now covered.
- op = insertAnyFilter(exprs, patternVarsScope, op) ;
+ op = insertAnyFilter$(exprs, patternVarsScope, op) ;
// Consider this triple.
// Get BGP that is accumulating triples.
OpBGP opBGP = getBGP(op) ;
@@ -199,7 +203,7 @@ public class TransformFilterPlacement ex
}
// Place any filters this whole BGP covers.
- op = insertAnyFilter(exprs, patternVarsScope, op) ;
+ op = insertAnyFilter$(exprs, patternVarsScope, op) ;
return result(op, exprs) ;
}
@@ -270,7 +274,7 @@ public class TransformFilterPlacement ex
Op op = null ;
for (Triple triple : pattern) {
- op = insertAnyFilter(exprs, patternVarsScope, op) ;
+ op = insertAnyFilter$(exprs, patternVarsScope, op) ;
OpQuadPattern opQuad = getQuads(op) ;
if ( opQuad == null ) {
opQuad = new OpQuadPattern(graphNode, new BasicPattern()) ;
@@ -282,7 +286,7 @@ public class TransformFilterPlacement ex
VarUtils.addVarsFromTriple(patternVarsScope, triple) ;
}
// Place any filters this whole quad block covers.
- op = insertAnyFilter(exprs, patternVarsScope, op) ;
+ op = insertAnyFilter$(exprs, patternVarsScope, op) ;
return result(op, exprs) ;
}
@@ -352,7 +356,7 @@ public class TransformFilterPlacement ex
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 = insertAnyFilter$(exprs, varScope, op) ;
Op seqElt = ops.get(i) ;
if ( i != ops.size()-1 ) {
Placement p = transform(exprs, seqElt) ;
@@ -407,11 +411,11 @@ public class TransformFilterPlacement ex
Op opLeftNew = left ;
if ( !pushLeft.isEmpty() )
- opLeftNew = transformOp(pushLeft, opLeftNew) ;
+ opLeftNew = transformOpAlways(pushLeft, opLeftNew) ;
Op opRightNew = right ;
if ( !pushRight.isEmpty() )
- opRightNew = transformOp(pushRight, opRightNew) ;
+ opRightNew = transformOpAlways(pushRight, opRightNew) ;
Op op = OpJoin.create(opLeftNew, opRightNew) ;
return result(op, unpushed) ;
@@ -441,25 +445,82 @@ public class TransformFilterPlacement ex
}
private Placement placeUnion(ExprList exprs, OpUnion input) {
- // Push into both sides.
+ if ( false )
+ // Safely but inefficiently do nothing.
+ return null ; //new Placement(input, exprs) ;
+
+ if ( false ) {
+ // Push into both sides.
+ Op left = input.getLeft() ;
+ Placement pLeft = transform(exprs, left) ;
+
+ Op right = input.getRight() ;
+ Placement pRight = transform(exprs, right) ;
+
+ // JENA-652 Temporary fix
+ if ( pLeft != null && ! pLeft.unplaced.isEmpty() )
+ return noChangePlacement ;
+ if ( pRight != null && ! pRight.unplaced.isEmpty() )
+ return noChangePlacement ;
+
+ // Old, buggy if not guarded by the above.
+ left = transformOpAlways(exprs, left) ;
+ right = transformOpAlways(exprs, right) ;
+
+ Op op2 = OpUnion.create(left, right) ;
+ return result(op2, emptyList) ;
+ }
+
Op left = input.getLeft() ;
Placement pLeft = transform(exprs, left) ;
Op right = input.getRight() ;
Placement pRight = transform(exprs, right) ;
- // JENA-652 Temporary fix
- if ( pLeft != null && ! pLeft.unplaced.isEmpty() )
- return null ;
- if ( pRight != null && ! pRight.unplaced.isEmpty() )
- return null ;
-
- // Old code.
- left = transformOp(exprs, left) ;
- right = transformOp(exprs, right) ;
+ // If it's placed in neitehr arm it should be passed back out for placement.
+ //
+ // If it's done in both arms, then expression can be left pushed in
+ // and not passed back out for placement.
+
+ // If it is done in one arm and not the other, then it can be left pushed
+ // in but needs to be redone for the other arm as if it were no placed at all.
+
+ // A filter applied twice is safe.
+ // Placement = null => nothing done => unplaced.
+
+ ExprList exprs2 = null ;
- Op op2 = OpUnion.create(left, right) ;
- return result(op2, emptyList) ;
+ for ( Expr expr : exprs ) {
+ boolean unplacedLeft = ( pLeft == null || pLeft.unplaced.getList().contains(expr) ) ;
+ boolean unplacedRight = ( pRight == null || pRight.unplaced.getList().contains(expr) ) ;
+
+// if ( unplacedLeft && unplacedRight ) {
+// System.out.println("Unplaced: "+expr) ;
+// } else if ( unplacedLeft ) {
+// System.out.println("Unplaced(L): "+expr) ;
+// } else if ( unplacedRight ) {
+// System.out.println("Unplaced(R): "+expr) ;
+// } else
+// System.out.println("Placed(L+R): "+expr) ;
+
+ boolean placed = !unplacedLeft && !unplacedRight ;
+ if ( placed )
+ // Went into both arms - expression has been handled completely.
+ continue ;
+
+ if ( exprs2 == null )
+ exprs2 = new ExprList() ;
+ exprs2.add(expr) ;
+ }
+
+
+ Op newLeft = (pLeft == null ) ? left : pLeft.op ;
+ Op newRight = (pRight == null ) ? right : pRight.op ;
+ if ( exprs2 == null )
+ exprs2 = emptyList ;
+
+ Op op2 = OpUnion.create(newLeft, newRight) ;
+ return result(op2, exprs2) ;
}
/** Try to optimize (filter (extend ...)) */
@@ -538,6 +599,12 @@ public class TransformFilterPlacement ex
return result(op2, unpushed) ;
}
+ private Placement placeTable(ExprList exprs, OpTable input) {
+ exprs = ExprList.copy(exprs) ;
+ Op op = insertAnyFilter$(exprs, input.getTable().getVars(), input) ;
+ return result(op, exprs) ;
+ }
+
private Set<Var> fixedVars(Op op) {
return OpVars.fixedVars(op) ;
}
@@ -548,7 +615,7 @@ public class TransformFilterPlacement ex
* that is placed.
*/
- private static Op insertAnyFilter(ExprList unplacedExprs, Set<Var> patternVarsScope, Op op) {
+ private static Op insertAnyFilter$(ExprList unplacedExprs, Collection<Var> patternVarsScope, Op op) {
for (Iterator<Expr> iter = unplacedExprs.iterator(); iter.hasNext();) {
Expr expr = iter.next() ;
// Cache
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=1577924&r1=1577923&r2=1577924&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 Sat Mar 15 19:43:43 2014
@@ -256,7 +256,7 @@ public class TestTransformFilterPlacemen
@Test public void place_extend_04() {
test("(filter (= ?x 123) (extend ((?x1 123)) (filter (< ?x 456) (bgp (?s ?p ?x) (?s ?p ?z))) ))",
- "(extend (?x1 123) (sequence (filter ((= ?x 123) (< ?x 456)) (bgp (?s ?p ?x))) (bgp (?s ?p ?z))) )") ;
+ "(extend (?x1 123) (sequence (filter ((< ?x 456) (= ?x 123)) (bgp (?s ?p ?x))) (bgp (?s ?p ?z))) )") ;
}
@Test public void place_extend_05() {
@@ -289,7 +289,7 @@ public class TestTransformFilterPlacemen
@Test public void place_assign_04() {
// 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))) )") ;
+ "(assign (?x1 123) (sequence (filter ((< ?x 456) (= ?x 123)) (bgp (?s ?p ?x))) (bgp (?s ?p ?z))) )") ;
}
@Test public void place_assign_05() {
@@ -319,6 +319,8 @@ public class TestTransformFilterPlacemen
"(sequence (filter (= ?y 456) (sequence (filter (= ?x 123) (bgp (?s ?p ?x))) (bgp (?s ?p ?y)))) (bgp (?s ?p ?z)))") ;
}
+ // XXX Table tests.
+
@Test public void place_union_01() {
test("(filter (= ?x 123) (union (bgp (?s ?p ?x) (?s ?p ?y)) (bgp (?s ?p ?z) (?s1 ?p1 ?x)) ))",
"(union (sequence (filter (= ?x 123) (bgp (?s ?p ?x))) (bgp (?s ?p ?y))) "+
@@ -326,23 +328,86 @@ public class TestTransformFilterPlacemen
}
@Test public void place_union_02() {
- test("(filter 1 (union (bgp (triple ?s ?p ?o)) (filter 0 (table unit))) )",
- "(union (sequence (filter 1 (table unit)) (bgp (triple ?s ?p ?o))) (filter (exprlist 0 1) (table unit)))");
+ String in = StrUtils.strjoinNL
+ ("(filter 1"
+ ," (union"
+ , " (bgp (triple ?s ?p ?o))"
+ ," (filter 0 (table unit))"
+ ,"))"
+ ) ;
+ String out = StrUtils.strjoinNL
+ ("(union"
+ ," (sequence"
+ ," (filter 1 (table unit))"
+ , " (bgp (triple ?s ?p ?o)))"
+ ," (filter (exprlist 0 1) (table unit))"
+ ,")"
+ );
+ test(in, out) ;
}
@Test public void place_union_02a() {
- testNoBGP("(filter 1 (union (bgp (triple ?s ?p ?o)) (filter 0 (table unit))) )",
- "(union (filter 1 (bgp (triple ?s ?p ?o))) (filter (exprlist 0 1) (table unit)))");
+ String in = StrUtils.strjoinNL
+ ("(filter 1"
+ ," (union"
+ , " (bgp (triple ?s ?p ?o))"
+ ," (filter 0 (table unit))"
+ ,"))"
+ ) ;
+ String out = StrUtils.strjoinNL
+ ("(union"
+ ," (filter 1 (bgp (triple ?s ?p ?o)))"
+ ," (filter (exprlist 0 1) (table unit))"
+ ,")"
+ );
+ testNoBGP(in, out) ;
}
@Test public void place_union_03() {
- test("(slice _ 1 (project (?s ?p ?o) (filter 1 (union (bgp (?s ?p ?o)) (filter 0 (table unit))))))",
- "(slice _ 1 (project (?s ?p ?o) (union (sequence (filter 1 (table unit)) (bgp (?s ?p ?o))) (filter (exprlist 0 1) (table unit)))))");
+ String in = StrUtils.strjoinNL
+ ("(slice _ 1"
+ ," (project (?s ?p ?o)"
+ ," (filter 1"
+ ," (union"
+ ," (bgp (?s ?p ?o))"
+ ," (filter 0 (table unit))"
+ ," ))"
+ ,"))"
+ ) ;
+ String out = StrUtils.strjoinNL
+ ("(slice _ 1"
+ ," (project (?s ?p ?o)"
+ ," (union"
+ ," (sequence"
+ ," (filter 1 (table unit))"
+ ," (bgp (?s ?p ?o)))"
+ ," (filter (exprlist 0 1)"
+ ," (table unit))"
+ , ")"
+ ,"))");
+ test(in, out) ;
}
@Test public void place_union_03a() {
- testNoBGP("(slice _ 1 (project (?s ?p ?o) (filter 1 (union (bgp (?s ?p ?o)) (filter 0 (table unit))))))",
- "(slice _ 1 (project (?s ?p ?o) (union (filter 1 (bgp (?s ?p ?o))) (filter (exprlist 0 1) (table unit)))))");
+ String in = StrUtils.strjoinNL
+ ("(slice _ 1"
+ ," (project (?s ?p ?o)"
+ ," (filter 1"
+ ," (union"
+ ," (bgp (?s ?p ?o))"
+ ," (filter 0 (table unit))"
+ ," ))"
+ ,"))"
+ ) ;
+ String out = StrUtils.strjoinNL
+ ("(slice _ 1"
+ ," (project (?s ?p ?o)"
+ ," (union"
+ ," (filter 1 (bgp (?s ?p ?o)))"
+ ," (filter (exprlist 0 1) (table unit))"
+ , ")"
+ ,"))");
+ testNoBGP(in, out) ;
}
// Union - push outer filters into each arm.
@@ -384,7 +449,7 @@ public class TestTransformFilterPlacemen
testNoBGP ( in, out ) ;
}
- // Urelated filter
+ // Unrelated filter
@Test public void place_union_05() {
String in = StrUtils.strjoinNL
("(filter (= ?x 1)"
@@ -394,11 +459,60 @@ public class TestTransformFilterPlacemen
,"))"
) ;
String out = in ;
- test ( in, out ) ;
+ test( in, out ) ;
}
- // Reverse arms.
+ // Unrelated filter
+ @Test public void place_union_05a() {
+ String in = StrUtils.strjoinNL
+ ("(filter (= ?x 1)"
+ ," (union"
+ ," (bgp (triple ?s ?p ?o))"
+ ," (bgp (triple ?s ?p ?o))"
+ ,"))"
+ ) ;
+ String out = in ;
+ testNoBGP( in, out ) ;
+ }
+ // Filter in one arm but not the other.
+ // Push and also leave to be placed again.
+ @Test public void place_union_06() {
+ String in = StrUtils.strjoinNL
+ ("(filter (= ?x 1)"
+ ," (union"
+ ," (bgp (triple ?s ?p ?o))"
+ ," (bgp (triple ?s ?p ?x))"
+ ,"))"
+ ) ;
+ String out = StrUtils.strjoinNL
+ ("(filter (= ?x 1)"
+ ," (union"
+ ," (bgp (triple ?s ?p ?o))"
+ ," (filter (= ?x 1) (bgp (triple ?s ?p ?x)))"
+ ,"))"
+ ) ;
+ test( in, out ) ;
+ }
+
+ // Filter in one arm but not the other
+ @Test public void place_union_07() {
+ String in = StrUtils.strjoinNL
+ ("(filter (= ?x 1)"
+ ," (union"
+ ," (bgp (triple ?s ?p ?x))"
+ ," (bgp (triple ?s ?p ?o))"
+ ,"))"
+ ) ;
+ String out = StrUtils.strjoinNL
+ ("(filter (= ?x 1)"
+ ," (union"
+ ," (filter (= ?x 1) (bgp (triple ?s ?p ?x)))"
+ ," (bgp (triple ?s ?p ?o))"
+ ,"))"
+ ) ;
+ test( in, out ) ;
+ }
public static void test(String input, String output) {
test$(input, output, true) ;