Author: andy
Date: Sun Nov 17 21:56:55 2013
New Revision: 1542842
URL: http://svn.apache.org/r1542842
Log:
Placement for union (first attempt)
Added:
jena/Scratch/AFS/Dev/src-dev/opt/VarFinder2.java
Modified:
jena/Scratch/AFS/Dev/src-dev/opt/OptMain.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=1542842&r1=1542841&r2=1542842&view=diff
==============================================================================
--- jena/Scratch/AFS/Dev/src-dev/opt/OptMain.java (original)
+++ jena/Scratch/AFS/Dev/src-dev/opt/OptMain.java Sun Nov 17 21:56:55 2013
@@ -26,91 +26,118 @@ import com.hp.hpl.jena.query.Query ;
import com.hp.hpl.jena.query.QueryFactory ;
import com.hp.hpl.jena.sparql.ARQConstants ;
import com.hp.hpl.jena.sparql.algebra.* ;
+import com.hp.hpl.jena.sparql.algebra.op.OpJoin ;
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.engine.main.JoinClassifier ;
import com.hp.hpl.jena.sparql.sse.SSE ;
import com.hp.hpl.jena.sparql.util.Context ;
public class OptMain {
+ // LeftJoin - Fixed vars only (LHS) OpVars. VarFinder.fixed(null)
+ // UNION - fixed : intersection
+ // Test - UNION
- public static void main(String... argv) throws Exception {
- {
+ // Also TransformDistinctToReduced (JENA-585)and
TransformOrderByDistincApplication
+
+ // 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 : SubstituteFilterOptimize :: Interaction of optimization
(TransformFilterEquality) and initial binding
+
+ // Was Op.equals a good idea?
+ // Calculate vars for an expr once and cache : op.getVars.
+
+ // 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.
+ // JoinStartegy and FilterPlacement interaction.
+
+ public static void main(String... argv) {
+ testFailure() ;
+ }
+
+ public static void testFailure() {
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");
+
+ arq.sparql.main(
"--query="+DIR+"/filter-equality-13.rq", "--data="+DIR+"/data-4.ttl");
+ rewire() ;
+ arq.sparql.main(
"--query="+DIR+"/filter-equality-13.rq", "--data="+DIR+"/data-4.ttl");
+ dewire() ;
+// arq.sparql.main(
"--query="+DIR+"/filter-equality-13.rq", "--data="+DIR+"/data-4.ttl");
+// System.exit(0) ;
Query q = QueryFactory.read(DIR+"/filter-equality-13.rq") ;
Op op1 = Algebra.compile(q) ;
Op op2 = Algebra.optimize(op1) ;
System.out.println(op2);
rewire() ;
+ // Pushing filter over the (conditional) is wrong
+ // Need to look for MUST be fixed variables, which is not what OpVars.
mentioned vars is.
+ // nor is VarFinder.fixed (but is that wrong?)
+
+/*
+(filter (= ?x <http://example.org/x1>)
+ (sequence
+ (conditional
+ (table unit)
+ (bgp (triple ?x <http://example.org/qq> ?o2)))
+ (bgp (triple ?x <http://example.org/p> ?o1))))
+
+Rewrite2
+(sequence
+ (filter (= ?x <http://example.org/x1>)
+ (conditional
+ (table unit)
+ (bgp (triple ?x <http://example.org/qq> ?o2))))
+ (filter (= ?x <http://example.org/x1>)
+ (bgp (triple ?x <http://example.org/p> ?o1))))
+*/
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) ;
+ }
+
+ static void varFinder() {
+ if ( false )
+ {
+ Op op = SSE.parseOp("(union (bgp (?s ?p ?o1)) (bgp (?s ?p ?o2)))")
;
+ System.out.println(op) ;
+ // ** WRONG?? Exact meaning of "defined"?
+ System.out.println(VarFinder2.fixed(op)) ;
+ System.out.println(VarFinder2.optDefined(op)) ;
+ System.exit(0) ;
}
- // Project (and other blockers?)
-
- // Tests
- // coverage,
- // repeated application.
- // BGPs directly.
- // Complex/recurse tests
-
- // Transformations are applied "bottom up"
- // - should this be top down?
- // - what happens if hits a filter? Currently, it stops.
-
- // test combined with filter equality.
-
- // What about covered left but partial right?
- // Push left (join),)
- // Push left (left join)
- // Other cases
-
- // Check order of all optimziations - equality last.
-
- // 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
-
- // JENA-293 : Allow the filter placement optimziation to push FILTER
though BIND.
- // Filter push throughs.
- // JENA-384 : SubstituteFilterOptimize :: Interaction of optimization
(TransformFilterEquality) and initial binding
-
- // Filter placement
- // * Nesting
- // * Join
- // Need to say what was pushed.
-
- // Full optimization tests
-
- // Was Op.equals a good idea?
- // Calculate vars for an expr once and cache : op.getVars.
-
- // 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.
-
+ {
+ // See alt VarFinder
+ String[] x = {
+ "(join (bgp (?s ?p ?o)) (union (bgp (?s ?p ?o)) (bgp (?s ?p
?o1))) )",
+ "(join (bgp (?s ?p ?o)) (union (bgp (?s ?p ?z)) (bgp (?s ?p1
?z))) )"
+ } ;
+
+ for (String s : x ) {
+ System.out.println("--------") ;
+ Op op = SSE.parseOp(s) ;
+ System.out.println(op) ;
+ System.out.println("fixed: "+VarFinder2.fixed(op)) ;
+ System.out.println("Opt: "+VarFinder2.optDefined(op)) ;
+ boolean nonLinear = JoinClassifier.isLinear((OpJoin)op) ;
+ System.out.println(nonLinear) ;
+ }
+ System.exit(0) ;
+ }
+ }
+
+ static void placement() {
if ( false ) {
//String input = "(filter (?x 123) (sequence (conditional (table
unit)
String input = StrUtils.strjoinNL
@@ -186,6 +213,10 @@ public class OptMain {
private static void rewire() {
Optimize.setFactory(new RewriterFactory2());
}
+
+ private static void dewire() {
+ Optimize.setFactory(Optimize.stdOptimizationFactory) ;
+ }
static class RewriterFactory2 implements RewriterFactory {
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=1542842&r1=1542841&r2=1542842&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 21:56:55 2013
@@ -121,6 +121,10 @@ public class TransformFilterPlacement_Re
placement = placeLeftJoin(exprs, (OpLeftJoin)input) ;
else if ( input instanceof OpFilter )
placement = placeFilter(exprs, (OpFilter)input) ;
+ else if ( input instanceof OpUnion )
+ placement = placeUnion(exprs, (OpUnion)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.
@@ -368,8 +372,19 @@ public class TransformFilterPlacement_Re
return result(op, nLeft.unplaced) ;
}
- private static <T> boolean disjoint(Collection<T> collection,
Collection<T> possibleElts) {
- return CollectionUtils.disjoint(collection, possibleElts) ;
+ private static Placement placeUnion(ExprList exprs, OpUnion input) {
+ // Unsubtle - push into both sides.
+ // Neater - for all unpushed put outside the union.
+ Op left = input.getLeft() ;
+ Placement pLeft = transform(exprs, left) ;
+ left = buildFilter(pLeft) ;
+
+ Op right = input.getRight() ;
+ Placement pRight = transform(exprs, right) ;
+ right = buildFilter(pRight) ;
+
+ Op op2 = OpUnion.create(left, right) ;
+ return result(op2, emptyList) ;
}
/** Try to optimize (filter (extend ...)) */
@@ -461,10 +476,16 @@ public class TransformFilterPlacement_Re
return op ;
}
+ private static <T> boolean disjoint(Collection<T> collection,
Collection<T> possibleElts) {
+ return CollectionUtils.disjoint(collection, possibleElts) ;
+ }
+
/** Place expressions around an Op */
private static Op buildFilter(Placement placement) {
if ( placement == null )
return null ;
+ if ( placement.unplaced.isEmpty() )
+ return placement.op ;
return buildFilter(placement.unplaced, placement.op) ;
}
Added: jena/Scratch/AFS/Dev/src-dev/opt/VarFinder2.java
URL:
http://svn.apache.org/viewvc/jena/Scratch/AFS/Dev/src-dev/opt/VarFinder2.java?rev=1542842&view=auto
==============================================================================
--- jena/Scratch/AFS/Dev/src-dev/opt/VarFinder2.java (added)
+++ jena/Scratch/AFS/Dev/src-dev/opt/VarFinder2.java Sun Nov 17 21:56:55 2013
@@ -0,0 +1,276 @@
+/*
+ * 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 static com.hp.hpl.jena.sparql.util.VarUtils.addVar ;
+import static com.hp.hpl.jena.sparql.util.VarUtils.addVars ;
+
+import java.util.* ;
+import java.util.Map.Entry ;
+
+import com.hp.hpl.jena.sparql.algebra.Op ;
+import com.hp.hpl.jena.sparql.algebra.OpVisitorBase ;
+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.core.VarExprList ;
+import com.hp.hpl.jena.sparql.expr.Expr ;
+import com.hp.hpl.jena.sparql.expr.ExprList ;
+
+public class VarFinder2
+{
+ // See also VarUtils and OpVars.
+ // This class is specific to the needs of the main query engine and
scoping of variables
+
+ public static Set<Var> optDefined(Op op)
+ {
+ return VarUsageVisitor.apply(op).optDefines ;
+ }
+
+ public static Set<Var> fixed(Op op)
+ {
+ return VarUsageVisitor.apply(op).defines ;
+ }
+
+ public static Set<Var> filter(Op op)
+ {
+ return VarUsageVisitor.apply(op).filterMentions ;
+ }
+
+ VarUsageVisitor varUsageVisitor ;
+
+ public VarFinder2(Op op)
+ { varUsageVisitor = VarUsageVisitor.apply(op) ; }
+
+ public Set<Var> getOpt() { return varUsageVisitor.optDefines ; }
+ public Set<Var> getFilter() { return varUsageVisitor.filterMentions ; }
+ public Set<Var> getAssign() { return varUsageVisitor.assignMentions ; }
+ public Set<Var> getFixed() { return varUsageVisitor.defines ; }
+
+ private static class VarUsageVisitor extends OpVisitorBase //implements
OpVisitor
+ {
+ static VarUsageVisitor apply(Op op)
+ {
+ VarUsageVisitor v = new VarUsageVisitor() ;
+ op.visit(v) ;
+ return v ;
+ }
+
+ Set<Var> defines = null ;
+ Set<Var> optDefines = null ;
+ Set<Var> filterMentions = null ;
+ Set<Var> assignMentions = null ;
+
+ VarUsageVisitor()
+ {
+ defines = new HashSet<Var>() ;
+ optDefines = new HashSet<Var>() ;
+ filterMentions = new HashSet<Var>() ;
+ assignMentions = new HashSet<Var>() ;
+ }
+
+ VarUsageVisitor(Set<Var> _defines, Set<Var> _optDefines, Set<Var>
_filterMentions, Set<Var> _assignMentions)
+ {
+ defines = _defines ;
+ optDefines = _optDefines ;
+ filterMentions = _filterMentions ;
+ assignMentions = _assignMentions ;
+ }
+
+ @Override
+ public void visit(OpQuadPattern quadPattern)
+ {
+ addVar(defines, quadPattern.getGraphNode()) ;
+ BasicPattern triples = quadPattern.getBasicPattern() ;
+ addVars(defines, triples) ;
+ }
+
+ @Override
+ public void visit(OpBGP opBGP)
+ {
+ BasicPattern triples = opBGP.getPattern() ;
+ addVars(defines, triples) ;
+ }
+
+ @Override
+ public void visit(OpExt opExt)
+ {
+ opExt.effectiveOp().visit(this) ;
+ }
+
+ @Override
+ public void visit(OpJoin opJoin)
+ {
+ joinAcc(opJoin.getLeft()) ;
+ joinAcc(opJoin.getRight()) ;
+ }
+
+ @Override
+ public void visit(OpSequence opSequence)
+ {
+ for ( Op op : opSequence.getElements() )
+ joinAcc(op) ;
+ }
+
+ private void joinAcc(Op op)
+ {
+ VarUsageVisitor usage = VarUsageVisitor.apply(op) ;
+
+ defines.addAll(usage.defines) ;
+ optDefines.addAll(usage.optDefines) ;
+ filterMentions.addAll(usage.filterMentions) ;
+ }
+
+ @Override
+ public void visit(OpLeftJoin opLeftJoin)
+ {
+ leftJoin(opLeftJoin.getLeft(), opLeftJoin.getRight(),
opLeftJoin.getExprs()) ;
+ }
+
+ @Override
+ public void visit(OpConditional opLeftJoin)
+ {
+ leftJoin(opLeftJoin.getLeft(), opLeftJoin.getRight(), null) ;
+ }
+
+ private void leftJoin(Op left, Op right, ExprList exprs)
+ {
+ VarUsageVisitor leftUsage = VarUsageVisitor.apply(left) ;
+ VarUsageVisitor rightUsage = VarUsageVisitor.apply(right) ;
+
+ defines.addAll(leftUsage.defines) ;
+ optDefines.addAll(leftUsage.optDefines) ;
+ filterMentions.addAll(leftUsage.filterMentions) ;
+ assignMentions.addAll(leftUsage.assignMentions) ;
+
+ optDefines.addAll(rightUsage.defines) ; // Asymmetric.
+ optDefines.addAll(rightUsage.optDefines) ;
+ filterMentions.addAll(rightUsage.filterMentions) ;
+ assignMentions.addAll(rightUsage.assignMentions) ;
+
+ // Remove any definites that are in the optionals
+ // as, overall, they are definites
+ optDefines.removeAll(leftUsage.defines) ;
+
+ // And the associated filter.
+ if ( exprs != null )
+ exprs.varsMentioned(filterMentions);
+ }
+
+ @Override
+ public void visit(OpUnion opUnion)
+ {
+ VarUsageVisitor leftUsage =
VarUsageVisitor.apply(opUnion.getLeft()) ;
+ VarUsageVisitor rightUsage =
VarUsageVisitor.apply(opUnion.getRight()) ;
+
+ // defines = intersection(left.define, right.define)
+ // Optional = optional either side and not in both sides.
+
+// Set<Var> def = SetUtils.intersection(leftUsage.defines,
rightUsage.defines) ;
+// Set<Var> opt1 = SetUtils.difference(leftUsage.defines, def) ;
+// Set<Var> opt2 = SetUtils.difference(rightUsage.defines, def) ;
+//
+//
+// defines.addAll(def) ;
+// optDefines.addAll(opt1) ;
+// optDefines.addAll(opt2) ;
+// optDefines.addAll(leftUsage.optDefines) ;
+// optDefines.addAll(rightUsage.optDefines) ;
+//
+// filterMentions.addAll(leftUsage.filterMentions) ;
+// filterMentions.addAll(rightUsage.filterMentions) ;
+// assignMentions.addAll(rightUsage.assignMentions) ;
+// assignMentions.addAll(leftUsage.assignMentions) ;
+
+ defines.addAll(leftUsage.defines) ;
+ optDefines.addAll(leftUsage.optDefines) ;
+ filterMentions.addAll(leftUsage.filterMentions) ;
+ assignMentions.addAll(leftUsage.assignMentions) ;
+
+ defines.addAll(rightUsage.defines) ;
+ optDefines.addAll(rightUsage.optDefines) ;
+ filterMentions.addAll(rightUsage.filterMentions) ;
+ assignMentions.addAll(rightUsage.assignMentions) ;
+ }
+
+ @Override
+ public void visit(OpGraph opGraph)
+ {
+ addVar(defines, opGraph.getNode()) ;
+ opGraph.getSubOp().visit(this) ;
+ }
+
+ // @Override
+ @Override
+ public void visit(OpFilter opFilter)
+ {
+ opFilter.getExprs().varsMentioned(filterMentions);
+ opFilter.getSubOp().visit(this) ;
+ }
+
+ @Override
+ public void visit(OpAssign opAssign)
+ {
+ opAssign.getSubOp().visit(this) ;
+ processVarExprList(opAssign.getVarExprList()) ;
+ }
+
+ @Override
+ public void visit(OpExtend opExtend)
+ {
+ opExtend.getSubOp().visit(this) ;
+ processVarExprList(opExtend.getVarExprList()) ;
+ }
+
+ private void processVarExprList(VarExprList varExprList)
+ {
+ Map<Var, Expr> map = varExprList.getExprs() ;
+ for ( Entry<Var, Expr> e : map.entrySet() )
+ {
+ defines.add(e.getKey()) ;
+ e.getValue().varsMentioned(assignMentions);
+ }
+ }
+
+ @Override
+ public void visit(OpProject opProject)
+ {
+ List<Var> vars = opProject.getVars() ;
+ VarUsageVisitor subUsage =
VarUsageVisitor.apply(opProject.getSubOp()) ;
+
+ subUsage.defines.retainAll(vars) ;
+ subUsage.optDefines.retainAll(vars) ;
+ subUsage.optDefines.retainAll(vars) ;
+ defines.addAll(subUsage.defines) ;
+ optDefines.addAll(subUsage.optDefines) ;
+ filterMentions.addAll(subUsage.filterMentions) ;
+ assignMentions.addAll(subUsage.assignMentions) ;
+ }
+
+ @Override
+ public void visit(OpTable opTable)
+ {
+ defines.addAll(opTable.getTable().getVars()) ;
+ }
+
+ @Override
+ public void visit(OpNull opNull)
+ { }
+ }
+}
