You are viewing a plain text version of this content. The canonical link for it is here.
Posted to commits@jena.apache.org by rv...@apache.org on 2013/06/25 21:46:52 UTC
svn commit: r1496611 - in /jena/trunk/jena-arq: ./
src/main/java/com/hp/hpl/jena/sparql/algebra/optimize/
src/test/java/com/hp/hpl/jena/sparql/algebra/optimize/
Author: rvesse
Date: Tue Jun 25 19:46:51 2013
New Revision: 1496611
URL: http://svn.apache.org/r1496611
Log:
Some code cleanup and TODO comments, update Release Notes (JENA-473)
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/main/java/com/hp/hpl/jena/sparql/algebra/optimize/TransformFilterImplicitJoin.java
jena/trunk/jena-arq/src/main/java/com/hp/hpl/jena/sparql/algebra/optimize/TransformImplicitLeftJoin.java
jena/trunk/jena-arq/src/test/java/com/hp/hpl/jena/sparql/algebra/optimize/TestTransformFilters.java
Modified: jena/trunk/jena-arq/ReleaseNotes.txt
URL: http://svn.apache.org/viewvc/jena/trunk/jena-arq/ReleaseNotes.txt?rev=1496611&r1=1496610&r2=1496611&view=diff
==============================================================================
--- jena/trunk/jena-arq/ReleaseNotes.txt (original)
+++ jena/trunk/jena-arq/ReleaseNotes.txt Tue Jun 25 19:46:51 2013
@@ -5,6 +5,9 @@ ChangeLog for ARQ
==== Jena 2.10.2
+ JENA-470 : Enable optimization of mixtures of disjunctions with equality and other expressions.
++ JENA-473 : Enable implicit join optimizations
++ JENA-475 : HTTP Authentication for SPARQL Updates was not properly supported
++ JENA-471 : Fix regression in generated quad form of algebra for some queries
==== Jena 2.10.1
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=1496611&r1=1496610&r2=1496611&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 Jun 25 19:46:51 2013
@@ -18,264 +18,282 @@
package com.hp.hpl.jena.sparql.algebra.optimize;
-import static org.apache.jena.atlas.lib.CollectionUtils.disjoint ;
+import static org.apache.jena.atlas.lib.CollectionUtils.disjoint;
-import java.util.ArrayList ;
-import java.util.Collection ;
+import java.util.ArrayList;
+import java.util.Collection;
import java.util.HashSet;
-import java.util.List ;
-import java.util.Set ;
+import java.util.List;
+import java.util.Set;
-import org.apache.jena.atlas.lib.Pair ;
+import org.apache.jena.atlas.lib.Pair;
-import com.hp.hpl.jena.query.ARQ ;
-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.Substitute ;
-import com.hp.hpl.jena.sparql.core.Var ;
-import com.hp.hpl.jena.sparql.core.VarExprList ;
-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 intermediates of a different
+import com.hp.hpl.jena.query.ARQ;
+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.Substitute;
+import com.hp.hpl.jena.sparql.core.Var;
+import com.hp.hpl.jena.sparql.core.VarExprList;
+import com.hp.hpl.jena.sparql.expr.*;
+
+/**
+ * A transform that aims to optimize queries where there is an equality
+ * constraint on a variable to speed up evaluation e.g
+ *
+ * <pre>
+ * SELECT *
+ * WHERE
+ * {
+ * ?s ?p ?o .
+ * FILTER(?s = <http://subject>)
+ * }
+ * </pre>
+ *
+ * Would transform to the following:
+ *
+ * <pre>
+ * SELECT *
+ * WHERE
+ * {
+ * <http://subject> ?p ?o .
+ * BIND(<http://subject> AS ?s)
+ * }
+ * </pre>
+ *
+ * <h3>Applicability</h3>
+ * <p>
+ * This optimizer is conservative in that it only makes the optimization where
+ * the equality constraint is against a non-literal as otherwise substituting
+ * the value changes the query semantics because it switches from value equality
+ * to the more restrictive term equality. The optimization is safe for
+ * non-literals because for those value and term equality are equivalent (in
+ * fact value equality is defined to be term equality).
+ * </p>
+ * <p>
+ * There are also various nested algebra structures that can make the
+ * optimization unsafe and so it does not take place if any of those situations
+ * is detected.
+ * </p>
+ */
+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 intermediates of a
+ // different
// value can block overall results so don't mask immediately.
- public TransformFilterEquality()
- { }
-
+ public TransformFilterEquality() {
+ }
+
@Override
- public Op transform(OpFilter opFilter, Op subOp)
- {
- Op op = apply(opFilter.getExprs(), subOp) ;
- if ( op == null )
- return super.transform(opFilter, subOp) ;
- return op ;
- }
-
- private static Op apply(ExprList exprs, Op subOp)
- {
+ public Op transform(OpFilter opFilter, Op subOp) {
+ Op op = apply(opFilter.getExprs(), subOp);
+ if (op == null)
+ return super.transform(opFilter, subOp);
+ return op;
+ }
+
+ private static Op apply(ExprList exprs, Op subOp) {
// ---- Find and extract any equality filters.
- Pair<List<Pair<Var, NodeValue>>, ExprList> p = preprocessFilterEquality(exprs) ;
- if ( p == null || p.getLeft().size() == 0 )
- return null ;
-
- List<Pair<Var, NodeValue>> equalities = p.getLeft() ;
- Collection<Var> varsMentioned = varsMentionedInEqualityFilters(equalities) ;
- ExprList remaining = p.getRight() ;
-
- // If any of the conditions overlap the optimization is unsafe
+ Pair<List<Pair<Var, NodeValue>>, ExprList> p = preprocessFilterEquality(exprs);
+ if (p == null || p.getLeft().size() == 0)
+ return null;
+
+ List<Pair<Var, NodeValue>> equalities = p.getLeft();
+ Collection<Var> varsMentioned = varsMentionedInEqualityFilters(equalities);
+ ExprList remaining = p.getRight();
+
+ // If any of the conditions overlap the optimization is unsafe
// (the query is also likely incorrect but that isn't our problem)
+
+ // TODO There is actually a special case here, if the equality
+ // constraints are conflicting then we can special case to table empty.
+ // At the very least we should check for the case where an equality
+ // condition is duplicated
if (varsMentioned.size() < equalities.size())
return null;
-
+
// ---- Check if the subOp is the right shape to transform.
- Op op = subOp ;
-
+ Op op = subOp;
+
// Special case : deduce that the filter will always "eval unbound"
- // hence eliminate 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.
- // This is
- // { OPTIONAL{P1} OPTIONAL{P2} ... FILTER(?x = :x) }
- if ( testSpecialCase1(subOp, equalities, remaining))
- {
+ // hence eliminate 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.
+ // This is
+ // { OPTIONAL{P1} OPTIONAL{P2} ... FILTER(?x = :x) }
+ if (testSpecialCase1(subOp, equalities, remaining)) {
// Find backbone of ops
- List<Op> ops = extractOptionals(subOp) ;
- ops = processSpecialCase1(ops, equalities) ;
+ List<Op> ops = extractOptionals(subOp);
+ ops = processSpecialCase1(ops, equalities);
// Put back together
- op = rebuild((Op2)subOp, ops) ;
+ 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 ;
+ op = OpFilter.filter(exprs, op);
+ return op;
}
-
+
// ---- Transform
- if ( ! safeToTransform(varsMentioned, op) )
- return null ;
- for ( Pair<Var, NodeValue> equalityTest : equalities )
- op = processFilterWorker(op, equalityTest.getLeft(), equalityTest.getRight()) ;
-
- // ---- Place any filter expressions around the processed sub op.
- if ( remaining.size() > 0 )
- op = OpFilter.filter(remaining, op) ;
- return op ;
- }
-
- // --- find and extract
- private static Pair<List<Pair<Var, NodeValue>>, ExprList> preprocessFilterEquality(ExprList exprs)
- {
- List<Pair<Var, NodeValue>> exprsFilterEquality = new ArrayList<Pair<Var, NodeValue>>() ;
- ExprList exprsOther = new ExprList() ;
- for ( Expr e : exprs.getList() )
- {
- Pair<Var, NodeValue> p = preprocess(e) ;
- if ( p != null )
- exprsFilterEquality.add(p) ;
+ if (!safeToTransform(varsMentioned, op))
+ return null;
+ for (Pair<Var, NodeValue> equalityTest : equalities)
+ op = processFilterWorker(op, equalityTest.getLeft(), equalityTest.getRight());
+
+ // ---- Place any filter expressions around the processed sub op.
+ if (remaining.size() > 0)
+ op = OpFilter.filter(remaining, op);
+ return op;
+ }
+
+ // --- find and extract
+ private static Pair<List<Pair<Var, NodeValue>>, ExprList> preprocessFilterEquality(ExprList exprs) {
+ List<Pair<Var, NodeValue>> exprsFilterEquality = new ArrayList<Pair<Var, NodeValue>>();
+ ExprList exprsOther = new ExprList();
+ for (Expr e : exprs.getList()) {
+ Pair<Var, NodeValue> p = preprocess(e);
+ if (p != null)
+ exprsFilterEquality.add(p);
else
- exprsOther.add(e) ;
+ exprsOther.add(e);
}
- if ( exprsFilterEquality.size() == 0 )
- return null ;
- return Pair.create(exprsFilterEquality, exprsOther) ;
- }
-
- private static Pair<Var, NodeValue> preprocess(Expr e)
- {
- if ( !(e instanceof E_Equals) && !(e instanceof E_SameTerm) )
- return null ;
-
- ExprFunction2 eq = (ExprFunction2)e ;
- Expr left = eq.getArg1() ;
- Expr right = eq.getArg2() ;
-
- Var var = null ;
- NodeValue constant = null ;
-
- if ( left.isVariable() && right.isConstant() )
- {
- var = left.asVar() ;
- constant = right.getConstant() ;
- }
- else if ( right.isVariable() && left.isConstant() )
- {
- var = right.asVar() ;
- constant = left.getConstant() ;
- }
-
- if ( var == null || constant == null )
- return null ;
-
- // Corner case: sameTerm is false for string/plain literal,
- // but true in the graph for graph matching.
- if (e instanceof E_SameTerm)
- {
- if ( ! ARQ.isStrictMode() && constant.isString() )
- return null ;
- }
-
- // Final check for "=" where a FILTER = can do value matching when the graph does not.
- if ( e instanceof E_Equals )
- {
+ if (exprsFilterEquality.size() == 0)
+ return null;
+ return Pair.create(exprsFilterEquality, exprsOther);
+ }
+
+ private static Pair<Var, NodeValue> preprocess(Expr e) {
+ if (!(e instanceof E_Equals) && !(e instanceof E_SameTerm))
+ return null;
+
+ ExprFunction2 eq = (ExprFunction2) e;
+ Expr left = eq.getArg1();
+ Expr right = eq.getArg2();
+
+ Var var = null;
+ NodeValue constant = null;
+
+ if (left.isVariable() && right.isConstant()) {
+ var = left.asVar();
+ constant = right.getConstant();
+ } else if (right.isVariable() && left.isConstant()) {
+ var = right.asVar();
+ constant = left.getConstant();
+ }
+
+ if (var == null || constant == null)
+ return null;
+
+ // Corner case: sameTerm is false for string/plain literal,
+ // but true in the graph for graph matching.
+ if (e instanceof E_SameTerm) {
+ if (!ARQ.isStrictMode() && constant.isString())
+ return null;
+ }
+
+ // Final check for "=" where a FILTER = can do value matching when the
+ // graph does not.
+ if (e instanceof E_Equals) {
// Value based?
- if ( ! ARQ.isStrictMode() && constant.isLiteral() )
- return null ;
+ if (!ARQ.isStrictMode() && constant.isLiteral())
+ return null;
}
-
- return Pair.create(var, constant) ;
+
+ return Pair.create(var, constant);
}
- private static Collection<Var> varsMentionedInEqualityFilters(List<Pair<Var, NodeValue>> equalities)
- {
- Set<Var> vars = new HashSet<Var>() ;
- for ( Pair<Var, NodeValue> p : equalities )
- vars.add(p.getLeft()) ;
- return vars ;
+ private static Collection<Var> varsMentionedInEqualityFilters(List<Pair<Var, NodeValue>> equalities) {
+ Set<Var> vars = new HashSet<Var>();
+ for (Pair<Var, NodeValue> p : equalities)
+ vars.add(p.getLeft());
+ return vars;
}
- private static boolean safeToTransform(Collection<Var> varsEquality, Op op)
- {
+ private static boolean safeToTransform(Collection<Var> varsEquality, Op op) {
// Structure as a visitor?
- if ( op instanceof OpBGP || op instanceof OpQuadPattern )
- return true ;
-
- if ( op instanceof OpFilter )
- {
- OpFilter opf = (OpFilter)op ;
+ if (op instanceof OpBGP || op instanceof OpQuadPattern)
+ return true;
+
+ if (op instanceof OpFilter) {
+ OpFilter opf = (OpFilter) op;
// Expressions are always safe transform by substitution.
-// Collection<Var> fvars = opf.getExprs().getVarsMentioned() ;
-// if ( ! disjoint(fvars, varsEquality) )
-// return false ;
- return safeToTransform(varsEquality, opf.getSubOp()) ;
- }
-
- // This will be applied also in sub-calls of the Transform but queries
- // are very rarely so deep that it matters.
- if ( op instanceof OpSequence )
- {
- OpN opN = (OpN)op ;
- for ( Op subOp : opN.getElements() )
- {
- if ( ! safeToTransform(varsEquality, subOp) )
- return false ;
+ return safeToTransform(varsEquality, opf.getSubOp());
+ }
+
+ // This will be applied also in sub-calls of the Transform but queries
+ // are very rarely so deep that it matters.
+ if (op instanceof OpSequence) {
+ OpN opN = (OpN) op;
+ for (Op subOp : opN.getElements()) {
+ if (!safeToTransform(varsEquality, subOp))
+ return false;
}
- return true ;
+ return true;
}
-
- if ( op instanceof OpJoin || op instanceof OpUnion)
- {
- Op2 op2 = (Op2)op ;
- return safeToTransform(varsEquality, op2.getLeft()) && safeToTransform(varsEquality, op2.getRight()) ;
- }
-
- // Not safe unless filter variables are mentioned on the LHS.
- if ( op instanceof OpConditional || op instanceof OpLeftJoin )
- {
- Op2 opleftjoin = (Op2)op ;
-
- if ( ! safeToTransform(varsEquality, opleftjoin.getLeft()) ||
- ! safeToTransform(varsEquality, opleftjoin.getRight()) )
- return false ;
-
+
+ if (op instanceof OpJoin || op instanceof OpUnion) {
+ Op2 op2 = (Op2) op;
+ return safeToTransform(varsEquality, op2.getLeft()) && safeToTransform(varsEquality, op2.getRight());
+ }
+
+ // Not safe unless filter variables are mentioned on the LHS.
+ if (op instanceof OpConditional || op instanceof OpLeftJoin) {
+ Op2 opleftjoin = (Op2) op;
+
+ if (!safeToTransform(varsEquality, opleftjoin.getLeft()) || !safeToTransform(varsEquality, opleftjoin.getRight()))
+ return false;
+
// Not only must the left and right be safe to transform,
- // but the equality variable must be known to be always set.
+ // but the equality variable must be known to be always set.
// If the varsLeft are disjoint from assigned vars,
// we may be able to push assign down right
// (this generalises the unit table case specialcase1)
// Needs more investigation.
-
- Op opLeft = opleftjoin.getLeft() ;
- Set<Var> varsLeft = OpVars.visibleVars(opLeft) ;
- if ( varsLeft.containsAll(varsEquality) )
- return true ;
- return false ;
- }
-
- if ( op instanceof OpGraph )
- {
- OpGraph opg = (OpGraph)op ;
- return safeToTransform(varsEquality, opg.getSubOp()) ;
- }
-
- // Subquery - assume scope rewriting has already been applied.
- if ( op instanceof OpModifier )
- {
+
+ Op opLeft = opleftjoin.getLeft();
+ Set<Var> varsLeft = OpVars.visibleVars(opLeft);
+ if (varsLeft.containsAll(varsEquality))
+ return true;
+ return false;
+ }
+
+ if (op instanceof OpGraph) {
+ OpGraph opg = (OpGraph) op;
+ return safeToTransform(varsEquality, opg.getSubOp());
+ }
+
+ // Subquery - assume scope rewriting has already been applied.
+ if (op instanceof OpModifier) {
// ORDER BY?
- OpModifier opMod = (OpModifier)op ;
- if ( opMod instanceof OpProject )
- {
- OpProject opProject = (OpProject)op ;
- // Writing "SELECT ?var" for "?var" -> a value would need AS-ification.
- for ( Var v : opProject.getVars() )
- {
- if ( varsEquality.contains(v) )
- return false ;
+ OpModifier opMod = (OpModifier) op;
+ if (opMod instanceof OpProject) {
+ OpProject opProject = (OpProject) op;
+ // Writing "SELECT ?var" for "?var" -> a value would need
+ // AS-ification.
+ for (Var v : opProject.getVars()) {
+ if (varsEquality.contains(v))
+ return false;
}
}
- return safeToTransform(varsEquality, opMod.getSubOp()) ;
+ return safeToTransform(varsEquality, opMod.getSubOp());
+ }
+
+ if (op instanceof OpGroup) {
+ OpGroup opGroup = (OpGroup) op;
+ VarExprList varExprList = opGroup.getGroupVars();
+ return safeToTransform(varsEquality, varExprList) && safeToTransform(varsEquality, opGroup.getSubOp());
}
-
- if ( op instanceof OpGroup )
- {
- OpGroup opGroup = (OpGroup)op ;
- VarExprList varExprList = opGroup.getGroupVars() ;
- return safeToTransform(varsEquality, varExprList) &&
- safeToTransform(varsEquality, opGroup.getSubOp()) ;
- }
-
- if ( op instanceof OpTable )
- {
- OpTable opTable = (OpTable)op ;
- if ( opTable.isJoinIdentity() )
- return true ;
+
+ if (op instanceof OpTable) {
+ OpTable opTable = (OpTable) op;
+ if (opTable.isJoinIdentity())
+ return true;
}
// Op1 - OpGroup
@@ -284,114 +302,97 @@ public class TransformFilterEquality ext
// Op1 - OpFilter - done.
// Op1 - OpLabel - easy
// Op1 - OpService - no.
-
- return false ;
+
+ return false;
}
-
- private static boolean safeToTransform(Collection<Var> varsEquality, VarExprList varsExprList)
- {
+
+ private static boolean safeToTransform(Collection<Var> varsEquality, VarExprList varsExprList) {
// If the named variable is used, unsafe to rewrite.
- return disjoint(varsExprList.getVars(), varsEquality) ;
+ return disjoint(varsExprList.getVars(), varsEquality);
}
-
+
// -- A special case
- private static boolean testSpecialCaseUnused(Op op, List<Pair<Var, NodeValue>> equalities, ExprList remaining)
- {
+ 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
// then the filter expression will be "eval unbound" i.e. false.
// We can return empty table.
- Set<Var> patternVars = OpVars.visibleVars(op) ;
- for ( Pair<Var, NodeValue> p : equalities )
- {
- if ( ! patternVars.contains(p.getLeft()))
- return true ;
- }
- return false ;
- }
-
- // 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 )
- {
- 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 List<Op> processSpecialCase1(List<Op> ops, List<Pair<Var, NodeValue>> equalities)
- {
- 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()) ;
+ Set<Var> patternVars = OpVars.visibleVars(op);
+ for (Pair<Var, NodeValue> p : equalities) {
+ if (!patternVars.contains(p.getLeft()))
+ return true;
+ }
+ 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 a next of LeftJoin/conditionals.
+
+ private static boolean testSpecialCase1(Op op, List<Pair<Var, NodeValue>> equalities, ExprList remaining) {
+ 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 List<Op> processSpecialCase1(List<Op> ops, List<Pair<Var, NodeValue>> equalities) {
+ 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) ;
+ ops2.add(op2);
}
- return ops2 ;
+ return ops2;
}
- private static Op rebuild(Op2 subOp, List<Op> ops)
- {
- Op chain = OpTable.unit() ;
- for ( Op op : ops )
- {
- chain = subOp.copy(chain, op) ;
+ private static Op rebuild(Op2 subOp, List<Op> ops) {
+ Op chain = OpTable.unit();
+ for (Op op : ops) {
+ chain = subOp.copy(chain, op);
}
- return chain ;
+ return chain;
}
-
- private static boolean isUnitTable(Op op)
- {
- if (op instanceof OpTable )
- {
- if ( ((OpTable)op).isJoinIdentity() )
- return true;
+
+ private static boolean isUnitTable(Op op) {
+ if (op instanceof OpTable) {
+ if (((OpTable) op).isJoinIdentity())
+ return true;
}
- return false ;
+ return false;
}
-
+
// ---- Transformation
-
- private static Op processFilterWorker(Op op, Var var, NodeValue constant)
- {
- return subst(op, var, constant) ;
- }
-
- private static Op subst(Op subOp , Var var, NodeValue nv)
- {
- Op op = Substitute.substitute(subOp, var, nv.asNode()) ;
- return OpAssign.assign(op, var, nv) ;
+
+ private static Op processFilterWorker(Op op, Var var, NodeValue constant) {
+ return subst(op, var, constant);
}
-
+
+ private static Op subst(Op subOp, Var var, NodeValue nv) {
+ Op op = Substitute.substitute(subOp, var, nv.asNode());
+ return OpAssign.assign(op, var, nv);
+ }
+
// Helper for TransformFilterDisjunction.
-
+
/** Apply the FilterEquality transform or return null if no change */
- static Op processFilter(Expr e, Op subOp)
- {
- return apply(new ExprList(e), subOp) ;
+ static Op processFilter(Expr e, Op subOp) {
+ return apply(new ExprList(e), subOp);
}
}
Modified: jena/trunk/jena-arq/src/main/java/com/hp/hpl/jena/sparql/algebra/optimize/TransformFilterImplicitJoin.java
URL: http://svn.apache.org/viewvc/jena/trunk/jena-arq/src/main/java/com/hp/hpl/jena/sparql/algebra/optimize/TransformFilterImplicitJoin.java?rev=1496611&r1=1496610&r2=1496611&view=diff
==============================================================================
--- jena/trunk/jena-arq/src/main/java/com/hp/hpl/jena/sparql/algebra/optimize/TransformFilterImplicitJoin.java (original)
+++ jena/trunk/jena-arq/src/main/java/com/hp/hpl/jena/sparql/algebra/optimize/TransformFilterImplicitJoin.java Tue Jun 25 19:46:51 2013
@@ -112,7 +112,7 @@ public class TransformFilterImplicitJoin
// Not possible to optimize if multiple overlapping implicit joins
// We can test this simply by checking that the number of vars in
// varsMentioned is double the number of detected implicit joins
-
+
// TODO In principal this may be safe provided we carefully apply the
// substitutions in the correct order, this is left as a future
// enhancement to this optimizer
@@ -146,8 +146,11 @@ public class TransformFilterImplicitJoin
if (!safeToTransform(joins, varsMentioned, op))
return null;
- for (Pair<Var, Var> implicitJoin : joins)
+ for (Pair<Var, Var> implicitJoin : joins) {
+ // TODO Where there are multiple conditions it may be necessary to
+ // apply the substitutions more intelligently
op = processFilterWorker(op, implicitJoin.getLeft(), implicitJoin.getRight());
+ }
// ---- Place any filter expressions around the processed sub op.
if (remaining.size() > 0)
@@ -173,6 +176,8 @@ public class TransformFilterImplicitJoin
}
private static Pair<Var, Var> preprocess(Op subOp, Expr e) {
+ // TODO Should also handle the case of && as TransformImplicitLeftJoin
+ // is already capable of doing
if (!(e instanceof E_Equals) && !(e instanceof E_SameTerm))
return null;
Modified: jena/trunk/jena-arq/src/main/java/com/hp/hpl/jena/sparql/algebra/optimize/TransformImplicitLeftJoin.java
URL: http://svn.apache.org/viewvc/jena/trunk/jena-arq/src/main/java/com/hp/hpl/jena/sparql/algebra/optimize/TransformImplicitLeftJoin.java?rev=1496611&r1=1496610&r2=1496611&view=diff
==============================================================================
--- jena/trunk/jena-arq/src/main/java/com/hp/hpl/jena/sparql/algebra/optimize/TransformImplicitLeftJoin.java (original)
+++ jena/trunk/jena-arq/src/main/java/com/hp/hpl/jena/sparql/algebra/optimize/TransformImplicitLeftJoin.java Tue Jun 25 19:46:51 2013
@@ -133,6 +133,12 @@ public class TransformImplicitLeftJoin e
// semantics of the Left Join
Collection<Var> lhsVars = OpVars.visibleVars(left);
Collection<Var> rhsVars = OpVars.visibleVars(right);
+
+ // TODO A better approach here would be to build a dependency graph of
+ // the implicit joins and use that to inform the order in which they
+ // should be carried out or even to remove some entirely where
+ // transitivity and commutativity
+
for (Pair<Var, Var> implicitJoin : joins) {
// Which variable do we want to substitute out?
// We don't need to deal with the case of neither variable being on
Modified: jena/trunk/jena-arq/src/test/java/com/hp/hpl/jena/sparql/algebra/optimize/TestTransformFilters.java
URL: http://svn.apache.org/viewvc/jena/trunk/jena-arq/src/test/java/com/hp/hpl/jena/sparql/algebra/optimize/TestTransformFilters.java?rev=1496611&r1=1496610&r2=1496611&view=diff
==============================================================================
--- jena/trunk/jena-arq/src/test/java/com/hp/hpl/jena/sparql/algebra/optimize/TestTransformFilters.java (original)
+++ jena/trunk/jena-arq/src/test/java/com/hp/hpl/jena/sparql/algebra/optimize/TestTransformFilters.java Tue Jun 25 19:46:51 2013
@@ -213,6 +213,7 @@ public class TestTransformFilters
}
@Test public void equality17() {
+ // Conflicting constraints should result in no optimization
test("(filter ((= ?x <http://constant1>) (= ?x <http://constant2>)) (join (bgp (?x <http://p1> ?o1)) (bgp (?x <http://p2> ?o2))))",
t_equality,
(String[])null);
@@ -970,7 +971,7 @@ public class TestTransformFilters
t_implicitLeftJoin,
"(leftjoin (table unit) (assign ((?x ?y)) (bgp (?y ?p ?o)(?y <http://pred> ?y))))");
- // Swapping the order of the equality expression should make no difference
+ // Swapping the order of the equality will make a difference in this case
test(
"(leftjoin (table unit) (bgp (?x ?p ?o)(?x <http://pred> ?y)) ((= ?y ?x)))",
t_implicitLeftJoin,