Author: andy
Date: Sat Nov 16 17:48:07 2013
New Revision: 1542540
URL: http://svn.apache.org/r1542540
Log:
Better Filter Placement
Added:
jena/Scratch/AFS/Dev/src-dev/opt/TransformFilterPlacement_Rewrite.java
Removed:
jena/Scratch/AFS/Dev/src-dev/opt/TransformFilterPlacement_New.java
Modified:
jena/Scratch/AFS/Dev/src-dev/opt/OptMain.java
jena/Scratch/AFS/Dev/src-dev/opt/TestFilterPlacement.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=1542540&r1=1542539&r2=1542540&view=diff
==============================================================================
--- jena/Scratch/AFS/Dev/src-dev/opt/OptMain.java (original)
+++ jena/Scratch/AFS/Dev/src-dev/opt/OptMain.java Sat Nov 16 17:48:07 2013
@@ -18,24 +18,18 @@
package opt;
-import static opt.TransformFilterPlacement_New.insertAnyFilter ;
-
-import java.util.Collection ;
-import java.util.HashSet ;
-import java.util.Set ;
+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.* ;
-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.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.sse.SSE ;
-
public class OptMain {
public static void main(String... argv) throws Exception {
@@ -53,7 +47,7 @@ public class OptMain {
// JENA-293 : Allow the filter placement optimziation to push FILTER
though BIND.
// Filter push throughs.
- // JENA-384 : SubstitueFilterOptimize :: Interaction of optimization
(TransformFilterEquality) and initial binding
+ // JENA-384 : SubstituteFilterOptimize :: Interaction of optimization
(TransformFilterEquality) and initial binding
// Filter placement
// * Nesting
@@ -62,24 +56,63 @@ public class OptMain {
if ( false ) {
- String input = "(filter (= ?x 123) (join (bgp (?s ?p ?x)) (bgp (?s
?p ?z)) ))" ;
- Transform t_placement = new TransformFilterPlacement_New() ;
+ String input = "(filter ((= ?A 2) (= ?z 99) (= ?x 123)) (bgp (?s
?p ?x) (?s ?p ?z)) )" ;
+ Transform t_placement = new TransformFilterPlacement_Rewrite() ;
Op op1 = SSE.parseOp(input) ;
Op op2 = Transformer.transform(t_placement, op1) ;
System.out.print(op2) ;
System.out.println("------------------------");
- //System.exit(0) ;
+ 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) ;
+ Op op1 = Algebra.compile(query) ;
+ {
+ System.out.println("** OLD") ;
+ Op op2 = Algebra.optimize(op1) ;
+ 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) ;
+ 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) 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) { ?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) ;
+ }
/*
Setting
WriterLib.start(IndentedWriter out, String tag, int linePolicy)
@@ -87,84 +120,8 @@ WriterLib.finish(IndentedWriter out, Str
to use ""
*/
- System.out.println(op1) ;
-
- 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) ;
-
- 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=1542540&r1=1542539&r2=1542540&view=diff
==============================================================================
--- jena/Scratch/AFS/Dev/src-dev/opt/TestFilterPlacement.java (original)
+++ jena/Scratch/AFS/Dev/src-dev/opt/TestFilterPlacement.java Sat Nov 16
17:48:07 2013
@@ -18,6 +18,7 @@
package opt ;
+import org.apache.jena.atlas.junit.BaseTest ;
import org.apache.jena.atlas.lib.StrUtils ;
import org.junit.Assert ;
import org.junit.Test ;
@@ -27,7 +28,7 @@ import com.hp.hpl.jena.sparql.algebra.Tr
import com.hp.hpl.jena.sparql.algebra.Transformer ;
import com.hp.hpl.jena.sparql.sse.SSE ;
-public class TestFilterPlacement {
+public class TestFilterPlacement extends BaseTest { //extends
AbstractTestTransform {
@Test
public void place_filter_bgp_01() {
test("(filter (= ?x 1) (bgp ( ?s ?p ?x)))", "(filter (= ?x 1) (bgp (
?s ?p ?x)))") ;
@@ -58,7 +59,7 @@ public class TestFilterPlacement {
@Test
public void place_filter_no_match_02() {
- test("(filter (= ?x ?unbound) (bgp (?s ?p ?x)))", null) ;
+ test("(filter (= ?x ?unbound) (bgp (?s ?p ?x) (?s ?p ?x)))", null) ;
}
@Test
@@ -84,6 +85,12 @@ public class TestFilterPlacement {
"(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))
))",
+ null) ;
+ }
+
// Join : one sided push.
@Test
public void place_filter_join_01() {
@@ -106,18 +113,27 @@ public class TestFilterPlacement {
" (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 psuhed down.
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))))))") ;
-
+ " (join",
+ " (filter ((= 13 14) (< ?o 56))",
+ " (bgp (triple ?s ?p ?o)))",
+ " (filter ((= 13 14) (> ?o1 12))",
+ " (bgp (triple ?s ?p1 ?o1)))))") ;
test(x, y) ;
}
@@ -146,7 +162,7 @@ public class TestFilterPlacement {
// LeftJoin
public static void test(String input, String output) {
- Transform t_placement = new TransformFilterPlacement_New() ;
+ Transform t_placement = new TransformFilterPlacement_Rewrite() ;
Op op1 = SSE.parseOp(input) ;
Op op2 = Transformer.transform(t_placement, op1) ;
if ( output == null ) {
Added: 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=1542540&view=auto
==============================================================================
--- jena/Scratch/AFS/Dev/src-dev/opt/TransformFilterPlacement_Rewrite.java
(added)
+++ jena/Scratch/AFS/Dev/src-dev/opt/TransformFilterPlacement_Rewrite.java Sat
Nov 16 17:48:07 2013
@@ -0,0 +1,464 @@
+/*
+ * Licensed to the Apache Software Foundation (ASF) under one
+ * or more contributor license agreements. See the NOTICE file
+ * distributed with this work for additional information
+ * regarding copyright ownership. The ASF licenses this file
+ * to you under the Apache License, Version 2.0 (the
+ * "License"); you may not use this file except in compliance
+ * with the License. You may obtain a copy of the License at
+ *
+ * http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ * See the License for the specific language governing permissions and
+ * limitations under the License.
+ */
+
+/* Contains code submitted in email to jena-u...@incubator.apache.org
+ * so software grant and relicensed under the Apache Software License.
+ * placeFilterConditional
+ */
+
+package opt ;
+
+import java.util.Collection ;
+import java.util.Iterator ;
+import java.util.List ;
+import java.util.Set ;
+
+import org.apache.jena.atlas.lib.DS ;
+
+import com.hp.hpl.jena.graph.Node ;
+import com.hp.hpl.jena.graph.Triple ;
+import com.hp.hpl.jena.sparql.algebra.Op ;
+import com.hp.hpl.jena.sparql.algebra.OpVars ;
+import com.hp.hpl.jena.sparql.algebra.TransformCopy ;
+import com.hp.hpl.jena.sparql.algebra.op.* ;
+import com.hp.hpl.jena.sparql.core.BasicPattern ;
+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.util.VarUtils ;
+
+/**
+ * Rewrite an algebra expression to put filters as close to their bound
+ * variables in a BGP. Works on (filter (BGP ...) ) Could be made to work on a
+ * wider class of forms.
+ */
+
+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 ; }
+ }
+
+ private static Placement result(Op op, ExprList remaining) {
+ if ( op == null )
+ return null ;
+ return new Placement(op, remaining) ;
+ }
+
+ public static Op transform(ExprList exprs, BasicPattern bgp) {
+ Placement placement = placeFilterBGP(exprs, bgp) ;
+ Op op = ( placement == null ) ? new OpBGP(bgp) : placement.op ;
+ if ( placement != null )
+ op = buildFilter(placement.unplaced, op) ;
+ return op ;
+ }
+
+ public static Op transform(ExprList exprs, Node graphNode, BasicPattern
bgp) {
+ Placement placement = placeFilterQuadPattern(exprs, graphNode, bgp) ;
+ Op op = ( placement == null ) ? new OpQuadPattern(graphNode, bgp) :
placement.op ;
+ if ( placement != null )
+ op = buildFilter(placement.unplaced, op) ;
+ return op ;
+ }
+
+ public TransformFilterPlacement_Rewrite() {}
+
+ @Override
+ 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) ;
+ Op op = buildFilter(placement) ;
+ return op ;
+ }
+
+ // XXX Placement in / placement out?
+
+ 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 ;
+
+ if ( input instanceof OpBGP )
+ placement = placeFilterBGP(exprs, (OpBGP)input) ;
+ else if ( input instanceof OpSequence )
+ placement = placeFilterSequence(exprs, (OpSequence)input) ;
+ else if ( input instanceof OpQuadPattern )
+ placement = placeFilterQuadPattern(exprs, (OpQuadPattern)input) ;
+ else if ( input instanceof OpJoin )
+ placement = placeFilterJoin(exprs, (OpJoin)input) ;
+ else if ( input instanceof OpConditional )
+ placement = placeFilterConditional(exprs, (OpConditional)input) ;
+ else if ( input instanceof OpLeftJoin )
+ 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 ) {}
+
+ return placement ;
+ }
+
+ // == The placeFilter* modify the exprs and patternVarsScope arguments
+
+ private static Placement placeFilter(ExprList exprs, OpFilter input) {
+ // XXX NoOp
+ return result(input, exprs) ;
+ }
+
+
+ private static Placement placeFilterBGP(ExprList exprs, OpBGP x) {
+ return placeFilterBGP(exprs, x.getPattern()) ;
+ }
+
+ private static Placement placeFilterBGP(ExprList exprsIn, BasicPattern
pattern) {
+ ExprList exprs = new ExprList(exprsIn) ;
+ Set<Var> patternVarsScope = DS.set() ;
+ // Any filters that depend on no variables.
+ Op op = 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)
+ // Need to pass the results from that into the next triple.
+ opBGP = new OpBGP() ;
+ op = OpSequence.create(op, opBGP) ;
+ }
+
+ opBGP.getPattern().add(triple) ;
+ // Update variables in scope.
+ VarUtils.addVarsFromTriple(patternVarsScope, triple) ;
+ }
+
+ // Place any filters this whole BGP covers.
+ op = insertAnyFilter(exprs, patternVarsScope, op) ;
+ return result(op, exprs) ;
+ }
+
+ /** Find the current OpBGP, or return null. */
+ private static OpBGP getBGP(Op op) {
+ if ( op instanceof OpBGP )
+ return (OpBGP)op ;
+
+ if ( op instanceof OpSequence ) {
+ // Is last in OpSequence an BGP?
+ OpSequence opSeq = (OpSequence)op ;
+ List<Op> x = opSeq.getElements() ;
+ if ( x.size() > 0 ) {
+ Op opTop = x.get(x.size() - 1) ;
+ if ( opTop instanceof OpBGP )
+ return (OpBGP)opTop ;
+ // Drop through
+ }
+ }
+ // Can't find.
+ return null ;
+ }
+
+ private static Placement placeFilterQuadPattern(ExprList exprs,
OpQuadPattern pattern) {
+ return placeFilterQuadPattern(exprs, pattern.getGraphNode(),
pattern.getBasicPattern()) ;
+ }
+
+ private static Placement placeFilterQuadPattern(ExprList exprsIn, Node
graphNode, BasicPattern pattern) {
+ ExprList exprs = new ExprList(exprsIn) ;
+ Set<Var> patternVarsScope = DS.set() ;
+ // Any filters that depend on no variables.
+
+ if ( Var.isVar(graphNode) ) {
+ // Add in the graph node of the quad block.
+ VarUtils.addVar(patternVarsScope, Var.alloc(graphNode)) ;
+ }
+ Op op = null ;
+
+ for (Triple triple : pattern) {
+ op = insertAnyFilter(exprs, patternVarsScope, op) ;
+ OpQuadPattern opQuad = getQuads(op) ;
+ if ( opQuad == null ) {
+ opQuad = new OpQuadPattern(graphNode, new BasicPattern()) ;
+ op = OpSequence.create(op, opQuad) ;
+ }
+
+ opQuad.getBasicPattern().add(triple) ;
+ // Update variables in scope.
+ VarUtils.addVarsFromTriple(patternVarsScope, triple) ;
+ }
+ // Place any filters this whole quad block covers.
+ op = insertAnyFilter(exprs, patternVarsScope, op) ;
+ return result(op, exprs) ;
+ }
+
+ /** Find the current OpQuadPattern, or return null. */
+ private static OpQuadPattern getQuads(Op op) {
+ if ( op instanceof OpQuadPattern )
+ return (OpQuadPattern)op ;
+
+ if ( op instanceof OpSequence ) {
+ // Is last in OpSequence an BGP?
+ OpSequence opSeq = (OpSequence)op ;
+ List<Op> x = opSeq.getElements() ;
+ if ( x.size() > 0 ) {
+ Op opTop = x.get(x.size() - 1) ;
+ if ( opTop instanceof OpQuadPattern )
+ return (OpQuadPattern)opTop ;
+ // Drop through
+ }
+ }
+ return null ;
+ }
+
+ /*
+ * A Sequence is a number of joins where scoping means the LHS can be
+ * 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
+ * substitution, will never see the variables. The variable can not be
+ * reintroducded (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.
+ */
+
+ private static Placement placeFilterSequence(ExprList exprsIn, OpSequence
opSequence) {
+ ExprList exprs = new ExprList(exprsIn) ;
+ Set<Var> varScope = DS.set() ;
+ List<Op> ops = opSequence.getElements() ;
+
+ Op op = null ;
+
+ for (Iterator<Op> iter = ops.iterator(); iter.hasNext();) {
+ op = insertAnyFilter(exprs, varScope, op) ;
+ Op seqElt = iter.next() ;
+ // XXX Recurse
+ //seqElt = transform(exprs, varScope, seqElt) ; // varScope pass
in?
+ // Merge into sequence.
+ varScope.addAll(OpVars.mentionedVars(seqElt)) ;
+ op = OpSequence.create(op, seqElt) ;
+ }
+ 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.
+ static boolean pushRightAsWellAsLeft = true ;
+
+ private static Placement placeFilterJoin(ExprList exprs, OpJoin opJoin) {
+ 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 ( 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) ;
+ pushed = true ;
+ }
+
+ if ( !pushed )
+ unpushed.add(expr) ;
+ }
+
+ if ( pushLeft.isEmpty() && pushRight.isEmpty() )
+ return null ;
+
+ Op opLeftNew = left ;
+ if ( !pushLeft.isEmpty() ) {
+ // opLeftNew = transform(exprs, opLeftNew) ;
+ opLeftNew = OpFilter.filter(pushLeft, opLeftNew) ;
+ }
+
+ Op opRightNew = right ;
+ if ( !pushRight.isEmpty() ) {
+ // opRightNew = transform(exprs, opRightNew) ;
+ opRightNew = OpFilter.filter(pushRight, opRightNew) ;
+ }
+
+ Op op = OpJoin.create(opLeftNew, opRightNew) ;
+ return result(op, unpushed) ;
+ }
+
+ /* A conditional is left join without scoping complications.
+ */
+
+ private static Placement placeFilterConditional(ExprList exprs,
OpConditional opConditional) {
+ // Push LHS only.
+ Op left = opConditional.getLeft() ;
+ Op right = opConditional.getRight() ;
+ Placement nLeft = transform(exprs, left) ;
+ if ( nLeft == null )
+ result(null, 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.
+ Op left = opLeftJoin.getLeft() ;
+ Op right = opLeftJoin.getRight() ;
+ Placement nLeft = transform(exprs, left) ;
+ if ( nLeft == null )
+ result(null, exprs) ;
+ 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) ;
+// }
+
+ // ---- Utilities
+
+ /** For any expression now in scope, wrap the op with a filter */
+ private static Op insertAnyFilter(ExprList exprs, Set<Var>
patternVarsScope, Op op) {
+ for (Iterator<Expr> iter = exprs.iterator(); iter.hasNext();) {
+ Expr expr = iter.next() ;
+ // Cache
+ Set<Var> exprVars = expr.getVarsMentioned() ;
+ if ( patternVarsScope.containsAll(exprVars) ) {
+ if ( op == null )
+ op = OpTable.unit() ;
+ op = OpFilter.filter(expr, op) ;
+ iter.remove() ;
+ // Record expr.
+ }
+ }
+ return op ;
+ }
+
+ /** Place expressions around an Op */
+ private static Op buildFilter(Placement placement) {
+ if ( placement == null )
+ return null ;
+ return buildFilter(placement.unplaced, placement.op) ;
+ }
+
+ private static Op buildFilter(ExprList exprs, Op op) {
+ if ( exprs == null || exprs.isEmpty() )
+ return op ;
+
+ for (Iterator<Expr> iter = exprs.iterator(); iter.hasNext();) {
+ Expr expr = iter.next() ;
+ if ( op == null )
+ op = OpTable.unit() ;
+ op = OpFilter.filter(expr, op) ;
+ iter.remove() ;
+ }
+ return op ;
+ }
+}
