Author: andy
Date: Mon Nov 11 22:37:03 2013
New Revision: 1540871
URL: http://svn.apache.org/r1540871
Log:
Tidy/reorganize scratch area.
Added:
jena/Scratch/AFS/Dev/src-dev/opt/
jena/Scratch/AFS/Dev/src-dev/opt/Jena383_BadPlanOptionals.java
- copied, changed from r1523030,
jena/Scratch/AFS/Dev/src-dev/dev/Jena383_BadPlanOptionals.java
jena/Scratch/AFS/Dev/src-dev/opt/Jena384_SubstitueFilterOptimize.java
- copied, changed from r1523030,
jena/Scratch/AFS/Dev/src-dev/dev/Jena384_SubstitueFilterOptimize.java
jena/Scratch/AFS/Dev/src-dev/opt/JenaNNN_FilterEquality.java
- copied, changed from r1523030,
jena/Scratch/AFS/Dev/src-dev/dev/JenaNNN_FilterEquality.java
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
- copied, changed from r1523030,
jena/Scratch/AFS/Dev/src-dev/dev/TransformFilterEquality2.java
jena/Scratch/AFS/Dev/src-dev/opt/TransformFilterPlacement_New.java
Removed:
jena/Scratch/AFS/Dev/src-dev/dev/Jena383_BadPlanOptionals.java
jena/Scratch/AFS/Dev/src-dev/dev/Jena384_SubstitueFilterOptimize.java
jena/Scratch/AFS/Dev/src-dev/dev/JenaNNN_FilterEquality.java
jena/Scratch/AFS/Dev/src-dev/dev/TransformFilterEquality2.java
jena/Scratch/AFS/Dev/src-dev/reports/
jena/Scratch/AFS/Dev/src/main/java/algebra2/
Modified:
jena/Scratch/AFS/Dev/src-dev/dev/TestModelCreation.java
Modified: jena/Scratch/AFS/Dev/src-dev/dev/TestModelCreation.java
URL:
http://svn.apache.org/viewvc/jena/Scratch/AFS/Dev/src-dev/dev/TestModelCreation.java?rev=1540871&r1=1540870&r2=1540871&view=diff
==============================================================================
--- jena/Scratch/AFS/Dev/src-dev/dev/TestModelCreation.java (original)
+++ jena/Scratch/AFS/Dev/src-dev/dev/TestModelCreation.java Mon Nov 11 22:37:03
2013
@@ -18,9 +18,8 @@
package dev;
-import java.util.HashMap ;
-import java.util.Map ;
-
+import com.hp.hpl.jena.rdf.model.Model ;
+import com.hp.hpl.jena.rdf.model.ModelFactory ;
import com.hp.hpl.jena.sparql.util.Timer ;
public class TestModelCreation
@@ -34,8 +33,8 @@ public class TestModelCreation
t.startTimer() ;
for ( int i = 0 ; i < N; i++ )
{
- //Model m = ModelFactory.createDefaultModel() ;
- Map<Object, Object> m = new HashMap<Object, Object>() ;
+ Model m = ModelFactory.createDefaultModel() ;
+ //Map<Object, Object> m = new HashMap<Object, Object>() ;
objects[i%100] = m ;
}
long millis = t.endTimer() ;
Copied: jena/Scratch/AFS/Dev/src-dev/opt/Jena383_BadPlanOptionals.java (from
r1523030, jena/Scratch/AFS/Dev/src-dev/dev/Jena383_BadPlanOptionals.java)
URL:
http://svn.apache.org/viewvc/jena/Scratch/AFS/Dev/src-dev/opt/Jena383_BadPlanOptionals.java?p2=jena/Scratch/AFS/Dev/src-dev/opt/Jena383_BadPlanOptionals.java&p1=jena/Scratch/AFS/Dev/src-dev/dev/Jena383_BadPlanOptionals.java&r1=1523030&r2=1540871&rev=1540871&view=diff
==============================================================================
--- jena/Scratch/AFS/Dev/src-dev/dev/Jena383_BadPlanOptionals.java (original)
+++ jena/Scratch/AFS/Dev/src-dev/opt/Jena383_BadPlanOptionals.java Mon Nov 11
22:37:03 2013
@@ -16,7 +16,7 @@
* limitations under the License.
*/
-package dev;
+package opt;
import org.apache.jena.atlas.lib.StrUtils ;
Copied: jena/Scratch/AFS/Dev/src-dev/opt/Jena384_SubstitueFilterOptimize.java
(from r1523030,
jena/Scratch/AFS/Dev/src-dev/dev/Jena384_SubstitueFilterOptimize.java)
URL:
http://svn.apache.org/viewvc/jena/Scratch/AFS/Dev/src-dev/opt/Jena384_SubstitueFilterOptimize.java?p2=jena/Scratch/AFS/Dev/src-dev/opt/Jena384_SubstitueFilterOptimize.java&p1=jena/Scratch/AFS/Dev/src-dev/dev/Jena384_SubstitueFilterOptimize.java&r1=1523030&r2=1540871&rev=1540871&view=diff
==============================================================================
--- jena/Scratch/AFS/Dev/src-dev/dev/Jena384_SubstitueFilterOptimize.java
(original)
+++ jena/Scratch/AFS/Dev/src-dev/opt/Jena384_SubstitueFilterOptimize.java Mon
Nov 11 22:37:03 2013
@@ -16,7 +16,7 @@
* limitations under the License.
*/
-package dev;
+package opt;
import com.hp.hpl.jena.query.* ;
import com.hp.hpl.jena.rdf.model.ModelFactory ;
Copied: jena/Scratch/AFS/Dev/src-dev/opt/JenaNNN_FilterEquality.java (from
r1523030, jena/Scratch/AFS/Dev/src-dev/dev/JenaNNN_FilterEquality.java)
URL:
http://svn.apache.org/viewvc/jena/Scratch/AFS/Dev/src-dev/opt/JenaNNN_FilterEquality.java?p2=jena/Scratch/AFS/Dev/src-dev/opt/JenaNNN_FilterEquality.java&p1=jena/Scratch/AFS/Dev/src-dev/dev/JenaNNN_FilterEquality.java&r1=1523030&r2=1540871&rev=1540871&view=diff
==============================================================================
--- jena/Scratch/AFS/Dev/src-dev/dev/JenaNNN_FilterEquality.java (original)
+++ jena/Scratch/AFS/Dev/src-dev/opt/JenaNNN_FilterEquality.java Mon Nov 11
22:37:03 2013
@@ -16,7 +16,7 @@
* limitations under the License.
*/
-package dev;
+package opt;
import org.apache.jena.atlas.lib.StrUtils ;
import org.junit.Assert ;
@@ -36,12 +36,7 @@ import com.hp.hpl.jena.sparql.sse.SSE ;
public class JenaNNN_FilterEquality
{
- // remove assignment from projection?
- // No need! It's going to be a no-op!
-
- // [DONE] JENA-432 : Filter optimization messes up when a nested select is
present in the same block
// JENA-383 : The query optimizer generates a suboptimal query plan in
case of nested optionals followed by a filter
- // [DONE] JENA-294 : TransformFilterEquality does not handle starting
OPTIONAL well
// Unrelated
// JENA-293 : Allow the filter placement optimziation to push FILTER
though BIND.
Added: 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=1540871&view=auto
==============================================================================
--- jena/Scratch/AFS/Dev/src-dev/opt/OptMain.java (added)
+++ jena/Scratch/AFS/Dev/src-dev/opt/OptMain.java Mon Nov 11 22:37:03 2013
@@ -0,0 +1,74 @@
+/**
+ * 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.
+ */
+
+package opt;
+
+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.sse.SSE ;
+
+public class OptMain {
+
+ public static void main(String... argv) throws Exception {
+ // Cominations e.g. placement then equality
+
+
+ // JENA-383 : The query optimizer generates a suboptimal query plan in
case of nested optionals followed by a filter
+
+ // 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
+
+ // Filter placement
+ // * Nesting
+ // * Join
+ // Need to say what was pushed.
+
+
+ if ( true ) {
+ 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) ;
+ Op op2 = Transformer.transform(t_placement, op1) ;
+ System.out.print(op2) ;
+ System.out.println("------------------------");
+ //System.exit(0) ;
+ }
+
+ if ( true ) {
+ String x = "SELECT * { ?s ?p ?o . FILTER (13=14) FILTER(?o1 > 12)
FILTER(?o < 56) OPTIONAL { ?s ?p1 ?o1 } }" ;
+ Query query = QueryFactory.create(x) ;
+ Op op1 = Algebra.compile(query) ;
+ System.out.println(op1) ;
+
+ // && 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) ;
+ }
+ }
+}
Added: 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=1540871&view=auto
==============================================================================
--- jena/Scratch/AFS/Dev/src-dev/opt/TestFilterPlacement.java (added)
+++ jena/Scratch/AFS/Dev/src-dev/opt/TestFilterPlacement.java Mon Nov 11
22:37:03 2013
@@ -0,0 +1,137 @@
+/**
+ * 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.
+ */
+
+package opt ;
+
+import org.junit.Assert ;
+import org.junit.Test ;
+
+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.sse.SSE ;
+
+public class TestFilterPlacement {
+ @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("(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("(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("(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() {
+ // Unbound
+ test("(filter (= ?x ?unbound) (bgp (?s ?p ?x)))", null) ;
+ }
+
+ @Test
+ public void place_filter_no_match_02() {
+ test("(filter (= ?x ?unbound) (bgp (?s ?p ?x)))", null) ;
+ }
+
+ @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("(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() {
+ // 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.
+ 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))
)") ;
+ }
+
+ // Join : one sided push.
+ @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
+ @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_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() {
+ // 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() {
+ // 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
+
+ public static void test(String input, String output) {
+ Transform t_placement = new TransformFilterPlacement_New() ;
+ Op op1 = SSE.parseOp(input) ;
+ Op op2 = Transformer.transform(t_placement, op1) ;
+ if ( output == null ) {
+ // No transformation.
+ Assert.assertEquals(op1, op2) ;
+ return ;
+ }
+
+ Op op3 = SSE.parseOp(output) ;
+ Assert.assertEquals(op3, op2) ;
+ }
+
+}
Copied: jena/Scratch/AFS/Dev/src-dev/opt/TransformFilterEquality2.java (from
r1523030, jena/Scratch/AFS/Dev/src-dev/dev/TransformFilterEquality2.java)
URL:
http://svn.apache.org/viewvc/jena/Scratch/AFS/Dev/src-dev/opt/TransformFilterEquality2.java?p2=jena/Scratch/AFS/Dev/src-dev/opt/TransformFilterEquality2.java&p1=jena/Scratch/AFS/Dev/src-dev/dev/TransformFilterEquality2.java&r1=1523030&r2=1540871&rev=1540871&view=diff
==============================================================================
--- jena/Scratch/AFS/Dev/src-dev/dev/TransformFilterEquality2.java (original)
+++ jena/Scratch/AFS/Dev/src-dev/opt/TransformFilterEquality2.java Mon Nov 11
22:37:03 2013
@@ -16,7 +16,7 @@
* limitations under the License.
*/
-package dev;
+package opt;
import static org.apache.jena.atlas.lib.CollectionUtils.disjoint ;
Added: 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=1540871&view=auto
==============================================================================
--- jena/Scratch/AFS/Dev/src-dev/opt/TransformFilterPlacement_New.java (added)
+++ jena/Scratch/AFS/Dev/src-dev/opt/TransformFilterPlacement_New.java Mon Nov
11 22:37:03 2013
@@ -0,0 +1,364 @@
+/*
+ * 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 [email protected]
+ * so software grant and relicensed under the Apache Software License.
+ * transformFilterConditional
+ */
+
+package opt;
+
+import java.util.HashSet ;
+import java.util.Iterator ;
+import java.util.List ;
+import java.util.Set ;
+
+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_New extends TransformCopy
+{
+ static boolean doFilterPlacement = true ;
+
+ public static Op transform(ExprList exprs, BasicPattern bgp)
+ {
+ if ( ! doFilterPlacement )
+ return OpFilter.filter(exprs, new OpBGP(bgp)) ;
+ // Mutated
+ ExprList exprs2 = new ExprList(exprs) ;
+ Op op = transformFilterBGP(exprs2, new HashSet<Var>(), bgp) ;
+ // Remaining filters? e.g. ones mentioning var s not used anywhere.
+ op = buildFilter(exprs2, op) ;
+ return op ;
+ }
+
+ public static Op transform(ExprList exprs, Node graphNode, BasicPattern
bgp)
+ {
+ if ( ! doFilterPlacement )
+ return OpFilter.filter(exprs, new OpQuadPattern(graphNode, bgp)) ;
+ // Mutated
+ ExprList exprs2 = new ExprList(exprs) ;
+ Op op = transformFilterQuadPattern(exprs2, new HashSet<Var>(),
graphNode, bgp);
+ op = buildFilter(exprs2, op) ;
+ return op ;
+ }
+
+ public TransformFilterPlacement_New()
+ { }
+
+ @Override
+ public Op transform(OpFilter opFilter, Op x)
+ {
+ if ( ! doFilterPlacement )
+ return super.transform(opFilter, x) ;
+
+ // Destructive use of exprs - copy it.
+ ExprList exprs = new ExprList(opFilter.getExprs()) ;
+ Set<Var> varsScope = new HashSet<Var>() ;
+
+ Op op = transform(exprs, varsScope, x) ;
+ if ( op == x )
+ // Didn't do anything.
+ return super.transform(opFilter, x) ;
+
+ // Remaining exprs
+ op = buildFilter(exprs, op) ;
+ return op ;
+ }
+
+ 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.
+ // Dispatch by visitor??
+ Op opOutput = null ;
+
+ if ( input instanceof OpBGP )
+ opOutput = transformFilterBGP(exprs, varsScope, (OpBGP)input) ;
+ else if ( input instanceof OpSequence )
+ opOutput = transformFilterSequence(exprs, varsScope,
(OpSequence)input) ;
+ else if ( input instanceof OpQuadPattern )
+ opOutput = transformFilterQuadPattern(exprs, varsScope,
(OpQuadPattern)input) ;
+ else if ( input instanceof OpSequence )
+ opOutput = transformFilterSequence(exprs, varsScope,
(OpSequence)input) ;
+ else if ( input instanceof OpJoin )
+ opOutput = transformFilterJoin(exprs, varsScope, (OpJoin)input) ;
+ else if ( input instanceof OpConditional )
+ opOutput = transformFilterConditional(exprs, varsScope,
(OpConditional)input) ;
+ else if ( input instanceof OpLeftJoin )
+ opOutput = transformFilterLeftJoin(exprs, varsScope,
(OpLeftJoin)input) ;
+ else {
+ OpVars.visibleVars(input, varsScope) ;
+ return input ;
+ }
+
+ if ( opInitial != null )
+ opOutput = OpSequence.create(opInitial, opOutput) ;
+ return opOutput ;
+ }
+
+ // == The transformFilter* modify the exprs and patternVarsScope arguments
+
+ private static Op transformFilterBGP(ExprList exprs, Set<Var>
patternVarsScope, OpBGP x)
+ {
+ return transformFilterBGP(exprs, patternVarsScope, x.getPattern()) ;
+ }
+
+ // Mutates exprs
+ private static Op transformFilterBGP(ExprList exprs, Set<Var>
patternVarsScope, BasicPattern pattern)
+ {
+ // Any filters that depend on no variables.
+ Op op = insertAnyFilter(exprs, patternVarsScope, null) ;
+
+ for ( Triple triple : pattern )
+ {
+ 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.
+ // Which is a join and sequence is a special case of join
+ // which always evaluates by passing results of the early
+ // part into the next element of the sequence.
+
+ opBGP = new OpBGP() ;
+ op = OpSequence.create(op, opBGP) ;
+ }
+
+ opBGP.getPattern().add(triple) ;
+ // Update variables in scope.
+ VarUtils.addVarsFromTriple(patternVarsScope, triple) ;
+
+ // Attempt to place any filters
+ op = insertAnyFilter(exprs, patternVarsScope, op) ;
+ }
+ // Leave any remaining filter expressions - don't wrap up any as
something else may take them.
+ return op ;
+ }
+
+ /** 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 Op transformFilterQuadPattern(ExprList exprs, Set<Var>
patternVarsScope, OpQuadPattern pattern)
+ {
+ return transformFilterQuadPattern(exprs, patternVarsScope,
pattern.getGraphNode(), pattern.getBasicPattern()) ;
+ }
+
+ private static Op transformFilterQuadPattern(ExprList exprs, Set<Var>
patternVarsScope, Node graphNode, BasicPattern pattern)
+ {
+ // Any filters that depend on no variables.
+ Op op = insertAnyFilter(exprs, patternVarsScope, null) ;
+ if ( Var.isVar(graphNode) )
+ {
+ // Add in the graph node of the quad block.
+ // It's picked up after the first triple is processed.
+ VarUtils.addVar(patternVarsScope, Var.alloc(graphNode)) ;
+ }
+
+ for ( Triple triple : pattern )
+ {
+ 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) ;
+
+ // Attempt to place any filters
+ op = insertAnyFilter(exprs, patternVarsScope, op) ;
+ }
+
+
+ return op ;
+ }
+
+ /** 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
+ }
+ }
+ // Can't find.
+ return null ;
+ }
+
+ private static Op transformFilterSequence(ExprList exprs, Set<Var>
varScope, OpSequence opSequence)
+ {
+ List<Op> ops = opSequence.getElements() ;
+
+ // Any filters that depend on no variables.
+ Op op = insertAnyFilter(exprs, varScope, null) ;
+
+ for ( Iterator<Op> iter = ops.iterator() ; iter.hasNext() ; )
+ {
+ Op seqElt = iter.next() ;
+ // Process the sequence element. This may insert filters
(sequence or BGP)
+ // Only need inserting once because sequence implies legal for a
substituion join
+ // so later ops can't introduce a variable with a value outside
the filter.
+ seqElt = transform(exprs, varScope, seqElt) ;
+ // Merge into sequence.
+ op = OpSequence.create(op, seqElt) ;
+ // Place any filters now ready.
+ op = insertAnyFilter(exprs, varScope, op) ;
+ }
+ return op ;
+ }
+
+ private static Op transformFilterJoin(ExprList exprs, Set<Var> varScope,
OpJoin opJoin)
+ {
+ // Any filters that depend on no variables.
+ Op opInitial = insertAnyFilter(exprs, varScope, null) ;
+
+ // Check: Can push down either side or both. Both is better.
+
+ // WROnG: code removes
+
+ // Be careful about exprs.
+ // accumulate scope.
+
+ ExprList exprs1 = new ExprList(exprs) ;
+ ExprList exprs2 = new ExprList(exprs) ;
+
+ Op opLeft = transform(exprs, varScope, opJoin.getLeft());
+ Op opRight = transform(exprs, varScope, opJoin.getRight());
+
+ // WRONG
+ exprs.getList().clear() ;
+ //exprs.getList().addAll(exprs1.getList()) ;
+
+
+ Op op = OpJoin.create(opLeft, opRight) ;
+ return OpSequence.create(opInitial, op) ;
+ }
+
+ // Modularize.
+ private static Op transformFilterConditional(ExprList exprs, Set<Var>
varScope, OpConditional opConditional)
+ {
+ // Any filters that depend on no variables.
+ Op opInitial = insertAnyFilter(exprs, varScope, null) ;
+ Op left = opConditional.getLeft();
+ left = transform(exprs, varScope, left);
+ Op right = opConditional.getRight();
+ Op op = new OpConditional(left, right);
+ op = insertAnyFilter(exprs, varScope, op);
+ return OpSequence.create(opInitial, op) ;
+ }
+
+ // Modularize.
+ 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) ;
+ }
+
+ // ---- 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(ExprList exprs, Op op)
+ {
+ if ( 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 ;
+ }
+}
