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 2012/08/21 18:10:00 UTC
svn commit: r1375639 - in /jena/trunk/jena-arq: ./
src/main/java/com/hp/hpl/jena/sparql/algebra/optimize/
src/test/java/com/hp/hpl/jena/sparql/algebra/
Author: andy
Date: Tue Aug 21 16:09:59 2012
New Revision: 1375639
URL: http://svn.apache.org/viewvc?rev=1375639&view=rev
Log:
Improved optimization of { OPTIONAL{} OPTIONAL{} FILTER(equality) }
Removed:
jena/trunk/jena-arq/src/test/java/com/hp/hpl/jena/sparql/algebra/TestFilterTransform.java
Modified:
jena/trunk/jena-arq/ReleaseNotes.txt
jena/trunk/jena-arq/src/main/java/com/hp/hpl/jena/sparql/algebra/optimize/TransformFilterEquality.java
jena/trunk/jena-arq/src/test/java/com/hp/hpl/jena/sparql/algebra/TS_Algebra.java
Modified: jena/trunk/jena-arq/ReleaseNotes.txt
URL: http://svn.apache.org/viewvc/jena/trunk/jena-arq/ReleaseNotes.txt?rev=1375639&r1=1375638&r2=1375639&view=diff
==============================================================================
--- jena/trunk/jena-arq/ReleaseNotes.txt (original)
+++ jena/trunk/jena-arq/ReleaseNotes.txt Tue Aug 21 16:09:59 2012
@@ -4,6 +4,10 @@ ChangeLog for ARQ
==== ARQ 2.9.4
++ Implement WG decision on BIND - use original semantics.
++ improved optimization of sequeneces of OPTIONALs where the grouois only OPTIONAL and an equality filter (JENA-294)
++ Add URIs for all XQuery/Xpath F&O functions for duration accessors. (JENA-302)
++ Add URIs for all XQuery/Xpath F&O functions where there are SPARQl functions (JENA-303)
==== ARQ 2.9.3
Modified: jena/trunk/jena-arq/src/main/java/com/hp/hpl/jena/sparql/algebra/optimize/TransformFilterEquality.java
URL: http://svn.apache.org/viewvc/jena/trunk/jena-arq/src/main/java/com/hp/hpl/jena/sparql/algebra/optimize/TransformFilterEquality.java?rev=1375639&r1=1375638&r2=1375639&view=diff
==============================================================================
--- jena/trunk/jena-arq/src/main/java/com/hp/hpl/jena/sparql/algebra/optimize/TransformFilterEquality.java (original)
+++ jena/trunk/jena-arq/src/main/java/com/hp/hpl/jena/sparql/algebra/optimize/TransformFilterEquality.java Tue Aug 21 16:09:59 2012
@@ -26,7 +26,6 @@ import java.util.Set ;
import org.openjena.atlas.lib.Pair ;
import com.hp.hpl.jena.query.ARQ ;
-import com.hp.hpl.jena.sparql.ARQNotImplemented ;
import com.hp.hpl.jena.sparql.algebra.Op ;
import com.hp.hpl.jena.sparql.algebra.OpVars ;
import com.hp.hpl.jena.sparql.algebra.TransformCopy ;
@@ -37,6 +36,9 @@ import com.hp.hpl.jena.sparql.expr.* ;
public class TransformFilterEquality extends TransformCopy
{
+ // The approach taken for { OPTIONAL{} OPTIONAL{} } is more general ... and better?
+ // Still need to be careful of double-nested OPTIONALS as intermedates of a different
+ // value can block overall results so don't mask immediately.
public TransformFilterEquality()
{ }
@@ -67,17 +69,23 @@ public class TransformFilterEquality ext
// hence elimate all rows. Return the empty table.
if ( testSpecialCaseUnused(subOp, equalities, remaining))
- {
return OpTable.empty() ;
- }
// Special case: the deep left op of a OpConditional/OpLeftJoin is unit table.
- // Given the there is an equality filter, if the right does not match,
- // the empty row will be rejected by the filter.
- // So the bottom is in fact a normal join;
- // and a form like "(join unit P)" is equal to P.
+ // This is
+ // { OPTIONAL{P1} OPTIONAL{P2} ... FILTER(?x = :x) }
if ( testSpecialCase1(subOp, equalities, remaining))
- op = processSpecialCase1(op, equalities) ;
+ {
+ // Find backbone of ops
+ List<Op> ops = extractOptionals(subOp) ;
+ ops = processSpecialCase1(ops, equalities) ;
+ // Put back together
+ op = rebuild((Op2)subOp, ops) ;
+ // Put all filters - either we optimized, or we left alone.
+ // Either way, the complete set of filter expressions.
+ op = OpFilter.filter(exprs, op) ;
+ return op ;
+ }
// ---- Transform
@@ -86,7 +94,7 @@ public class TransformFilterEquality ext
for ( Pair<Var, NodeValue> equalityTest : equalities )
op = processFilterWorker(op, equalityTest.getLeft(), equalityTest.getRight()) ;
- // ---- Place any filter expressions around the processed sub op.
+ // ---- Place any filter expressions around the processed sub op.
if ( remaining.size() > 0 )
op = OpFilter.filter(remaining, op) ;
return op ;
@@ -220,7 +228,8 @@ public class TransformFilterEquality ext
return false ;
}
- // -- Special cases
+ // -- A special case
+
private static boolean testSpecialCaseUnused(Op op, List<Pair<Var, NodeValue>> equalities, ExprList remaining)
{
// If the op does not contain the var at all, for some equality
@@ -234,20 +243,70 @@ public class TransformFilterEquality ext
}
return false ;
}
-
- // If a sequence of OPTIONALS, and nothing prior to the first, we end up with
- // a unit table on the left side of deepest leftjoin/conditional.
+ // If a sequence of OPTIONALS, and nothing prior to the first, we end up with
+ // a unit table on the left sid of a next of LeftJoin/conditionals.
+
private static boolean testSpecialCase1(Op op, List<Pair<Var, NodeValue>> equalities , ExprList remaining )
{
- return false ;
+ while ( op instanceof OpConditional || op instanceof OpLeftJoin )
+ {
+ Op2 opleftjoin2 = (Op2)op ;
+ op = opleftjoin2.getLeft() ;
+ }
+ return isUnitTable(op) ;
+ }
+
+ private static List<Op> extractOptionals(Op op)
+ {
+ List<Op> chain = new ArrayList<Op>() ;
+ while ( op instanceof OpConditional || op instanceof OpLeftJoin )
+ {
+ Op2 opleftjoin2 = (Op2)op ;
+ chain.add(opleftjoin2.getRight()) ;
+ op = opleftjoin2.getLeft() ;
+ }
+ return chain ;
}
- private static Op processSpecialCase1(Op op, List<Pair<Var, NodeValue>> equalities)
+ private static List<Op> processSpecialCase1(List<Op> ops, List<Pair<Var, NodeValue>> equalities)
{
- throw new ARQNotImplemented() ;
+ List<Op> ops2 = new ArrayList<Op>() ;
+ Collection<Var> vars = varsMentionedInEqualityFilters(equalities) ;
+
+ for ( Op op : ops )
+ {
+ Op op2 = op ;
+ if ( safeToTransform(vars, op) )
+ {
+ for ( Pair<Var, NodeValue> p : equalities )
+ op2 = processFilterWorker(op, p.getLeft(), p.getRight()) ;
+ }
+ ops2.add(op2) ;
+ }
+ return ops2 ;
}
+ private static Op rebuild(Op2 subOp, List<Op> ops)
+ {
+ Op chain = OpTable.unit() ;
+ for ( Op op : ops )
+ {
+ chain = subOp.copy(chain, op) ;
+ }
+ return chain ;
+ }
+
+ private static boolean isUnitTable(Op op)
+ {
+ if (op instanceof OpTable )
+ {
+ if ( ((OpTable)op).isJoinIdentity() )
+ return true;
+ }
+ return false ;
+ }
+
// ---- Transformation
private static Op processFilterWorker(Op op, Var var, NodeValue constant)
Modified: jena/trunk/jena-arq/src/test/java/com/hp/hpl/jena/sparql/algebra/TS_Algebra.java
URL: http://svn.apache.org/viewvc/jena/trunk/jena-arq/src/test/java/com/hp/hpl/jena/sparql/algebra/TS_Algebra.java?rev=1375639&r1=1375638&r2=1375639&view=diff
==============================================================================
--- jena/trunk/jena-arq/src/test/java/com/hp/hpl/jena/sparql/algebra/TS_Algebra.java (original)
+++ jena/trunk/jena-arq/src/test/java/com/hp/hpl/jena/sparql/algebra/TS_Algebra.java Tue Aug 21 16:09:59 2012
@@ -19,6 +19,7 @@
package com.hp.hpl.jena.sparql.algebra;
+import com.hp.hpl.jena.sparql.algebra.optimize.TestFilterTransform ;
import com.hp.hpl.jena.sparql.algebra.optimize.TestOptimizer ;
import com.hp.hpl.jena.sparql.algebra.optimize.TestTransformMergeBGPs ;
import com.hp.hpl.jena.sparql.algebra.optimize.TestVarRename ;