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 00:31:00 UTC
svn commit: r1496242 - in /jena/trunk/jena-arq/src:
main/java/com/hp/hpl/jena/sparql/algebra/optimize/
main/java/com/hp/hpl/jena/sparql/function/user/
test/java/com/hp/hpl/jena/sparql/algebra/optimize/
Author: rvesse
Date: Mon Jun 24 22:31:00 2013
New Revision: 1496242
URL: http://svn.apache.org/r1496242
Log:
Improve intelligence of the implicit left join optimization (JENA-473)
The optimizer is now capable of pulling out both sides of an && if both are implicit join conditions and it can make valid substitutions
i.e. the conditions don't overlap in such a way as to block the optimization
It is also now capable of going one level further into && when appropriate to do so
Modified:
jena/trunk/jena-arq/src/main/java/com/hp/hpl/jena/sparql/algebra/optimize/TransformImplicitLeftJoin.java
jena/trunk/jena-arq/src/main/java/com/hp/hpl/jena/sparql/function/user/UserDefinedFunctionFactory.java
jena/trunk/jena-arq/src/test/java/com/hp/hpl/jena/sparql/algebra/optimize/TestTransformFilters.java
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=1496242&r1=1496241&r2=1496242&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 Mon Jun 24 22:31:00 2013
@@ -191,9 +191,36 @@ public class TransformImplicitLeftJoin e
List<Pair<Var, Var>> exprsJoins = new ArrayList<Pair<Var, Var>>();
ExprList exprsOther = new ExprList();
for (Expr e : exprs.getList()) {
+ int others = exprsOther.size();
Pair<Var, Var> p = preprocess(left, right, e, exprsOther);
if (p != null) {
exprsJoins.add(p);
+
+ // Special case for where we've split an && in case the
+ // remaining condition is also an implicit join that we can
+ // process
+ if (others != exprsOther.size()) {
+ int possRemove = others;
+ others = exprsOther.size();
+ p = preprocess(left, right, exprsOther.get(possRemove), exprsOther);
+ if (p != null) {
+ exprsJoins.add(p);
+ // Two possibilities here:
+ // 1 - The other condition was a plain implicit join in which case the size of the expr list won't have changed
+ // 2 - The other condition was a nested && which contained an implicit join in which case the size of the expr list will have changed
+ if (others == exprsOther.size()) {
+ // Trim the additional condition off the others list
+ exprsOther = possRemove > 0 ? exprsOther.subList(0, possRemove - 1) : new ExprList();
+ } else {
+ // Have additional entry in exprOther
+ Expr extra = exprsOther.get(exprsOther.size() - 1);
+ exprsOther = possRemove > 0 ? exprsOther.subList(0, possRemove - 1) : new ExprList();
+ exprsOther.add(extra);
+
+ // NB - We don't try and handle further nesting which in principle may exist
+ }
+ }
+ }
} else {
exprsOther.add(e);
}
@@ -209,6 +236,9 @@ public class TransformImplicitLeftJoin e
ExprFunction2 eq = (ExprFunction2) e;
if (e instanceof E_LogicalAnd) {
+ // NB - We only handle a single level of nesting here
+ // There is some special case code in the calling function that can attempt to recurse one level further
+
// Is LHS of the && an implicit join?
if (eq.getArg1() instanceof E_Equals || eq.getArg1() instanceof E_SameTerm) {
Pair<Var, Var> p = preprocess(opLeft, opRight, eq.getArg1(), exprsOther);
Modified: jena/trunk/jena-arq/src/main/java/com/hp/hpl/jena/sparql/function/user/UserDefinedFunctionFactory.java
URL: http://svn.apache.org/viewvc/jena/trunk/jena-arq/src/main/java/com/hp/hpl/jena/sparql/function/user/UserDefinedFunctionFactory.java?rev=1496242&r1=1496241&r2=1496242&view=diff
==============================================================================
--- jena/trunk/jena-arq/src/main/java/com/hp/hpl/jena/sparql/function/user/UserDefinedFunctionFactory.java (original)
+++ jena/trunk/jena-arq/src/main/java/com/hp/hpl/jena/sparql/function/user/UserDefinedFunctionFactory.java Mon Jun 24 22:31:00 2013
@@ -35,40 +35,47 @@ import com.hp.hpl.jena.sparql.lang.sparq
import com.hp.hpl.jena.sparql.sse.builders.ExprBuildException;
/**
- * A function factory for managing user defined functions
+ * A function factory for managing user defined functions aka function macros.
* <p>
- * User defined functions provide a simple mechanism for a user to inject custom functions into SPARQL processing
- * without the need to write any code. These functions essentially act as aliases for another SPARQL expression
- * and serve as a means to aid users in simplifying their SPARQL queries.
+ * User defined functions provide a simple mechanism for a user to inject custom
+ * functions into SPARQL processing without the need to write any code. These
+ * functions essentially act as macros/aliases for another SPARQL expression and
+ * serve as a means to aid users in simplifying their SPARQL queries.
* </p>
* <p>
* For example we can define a <strong>square</strong> function like so:
* </p>
+ *
* <pre>
- * List<Var> args = new ArrayList<Var>(Var.alloc("x"));
- * UserDefinedFunctionFactory.getFactory().add("http://example/square", "?x * ?x", args);
+ * List<Var> args = new ArrayList<Var>(Var.alloc("x"));
+ * UserDefinedFunctionFactory.getFactory().add("http://example/square", "?x * ?x", args);
* </pre>
* <p>
* We can then use this in queries like so:
* </p>
+ *
* <pre>
* SELECT (<http://example/square>(3) AS ?ThreeSquared) { }
* </pre>
* <p>
- * Internally the call to the <strong>square</strong> function is translated into it's equivalent SPARQL expression and executed in that form.
+ * Internally the call to the <strong>square</strong> function is translated
+ * into its equivalent SPARQL expression and executed in that form.
* </p>
* <p>
- * User defined functions may rely on each other but this has some risks, therefore the default behaviour is to not preserve these dependencies
- * but rather to expand the function definitions to give the resulting expression associated with a function. Please see {@link #getPreserveDependencies()}
- * for more information on this.
+ * User defined functions may rely on each other but this has some risks,
+ * therefore the default behaviour is to not preserve these dependencies but
+ * rather to expand the function definitions to give the resulting expression
+ * associated with a function. Please see {@link #getPreserveDependencies()} for
+ * more information on this.
* </p>
*/
public class UserDefinedFunctionFactory implements FunctionFactory {
-
- private static UserDefinedFunctionFactory factory = new UserDefinedFunctionFactory();
-
+
+ private static UserDefinedFunctionFactory factory = new UserDefinedFunctionFactory();
+
/**
* Gets the static instance of the factory
+ *
* @return Function Factory
*/
public static UserDefinedFunctionFactory getFactory() {
@@ -77,121 +84,153 @@ public class UserDefinedFunctionFactory
private Map<String, UserDefinedFunctionDefinition> definitions = new HashMap<String, UserDefinedFunctionDefinition>();
private boolean preserveDependencies = false;
-
+
/**
* Private constructor prevents instantiation
*/
- private UserDefinedFunctionFactory() { }
-
+ private UserDefinedFunctionFactory() {
+ }
+
/**
- * Gets whether user defined functions may preserve dependencies on each other (default false)
+ * Gets whether user defined functions may preserve dependencies on each
+ * other (default false)
* <p>
- * When this is disabled (as it is by default) function definitions are fully expanded at registration time. So if
- * you add a function that references an existing user defined function it will be expanded to include the
- * resulting expression rather than left with a reference to another function. This protects the user from
- * depending on other functions whose definitions are later removed or changed.
+ * When this is disabled (as it is by default) function definitions are
+ * fully expanded at registration time. So if you add a function that
+ * references an existing user defined function it will be expanded to
+ * include the resulting expression rather than left with a reference to
+ * another function. This protects the user from depending on other
+ * functions whose definitions are later removed or changed.
* </p>
* <p>
- * However it may sometimes be desirable to have dependencies preserved which case this option may be
- * disabled with the corresponding {@link #setPreserveDependencies(boolean)} setter
+ * However it may sometimes be desirable to have dependencies preserved
+ * in which case this option may be disabled with the corresponding
+ * {@link #setPreserveDependencies(boolean)} setter
* </p>
+ *
* @return Whether explicit dependencies are allowed
*/
public boolean getPreserveDependencies() {
return this.preserveDependencies;
}
-
+
/**
- * Sets whether user functions may explicitly depend on each other, see {@link #getPreserveDependencies()} for explanation of this behavior
- * @param allow Whether to preserve dependencies
+ * Sets whether user functions may explicitly depend on each other, see
+ * {@link #getPreserveDependencies()} for explanation of this behavior
+ *
+ * @param allow
+ * Whether to preserve dependencies
*/
public void setPreserveDependencies(boolean allow) {
this.preserveDependencies = allow;
}
-
+
/**
* Creates a function for the given URI
- * @throws ExprBuildException Thrown if the given URI is not a known function
+ *
+ * @throws ExprBuildException
+ * Thrown if the given URI is not a known function
*/
@Override
public Function create(String uri) {
UserDefinedFunctionDefinition def = this.definitions.get(uri);
- if (def == null) throw new ExprBuildException("Function <" + uri + "> not known by this function factory");
+ if (def == null)
+ throw new ExprBuildException("Function <" + uri + "> not known by this function factory");
return def.newFunctionInstance();
}
-
+
/**
* Adds a function
- * @param uri URI
- * @param e Expression
- * @param args Arguments
+ *
+ * @param uri
+ * URI
+ * @param e
+ * Expression
+ * @param args
+ * Arguments
*/
public void add(String uri, Expr e, List<Var> args) {
if (!preserveDependencies) {
- //If not allowing dependencies expand expression fully
+ // If not allowing dependencies expand expression fully
e = ExprTransformer.transform(new ExprTransformExpand(this.definitions), e);
- }
-
+ }
+
UserDefinedFunctionDefinition def = new UserDefinedFunctionDefinition(uri, e, args);
this.definitions.put(uri, def);
FunctionRegistry.get().put(uri, this);
}
-
+
/**
* Adds a function
* <p>
- * This method will build the expression to use based on the expression string given, strings must match the SPARQL expression syntax e.g.
+ * This method will build the expression to use based on the expression
+ * string given, strings must match the SPARQL expression syntax e.g.
* </p>
+ *
* <pre>
* (?x * ?y) + 5
* </pre>
- * @param uri URI
- * @param expr Expression String (in SPARQL syntax)
- * @param args Arguments
- * @throws ParseException Thrown if the expression string is not valid syntax
+ *
+ * @param uri
+ * URI
+ * @param expr
+ * Expression String (in SPARQL syntax)
+ * @param args
+ * Arguments
+ * @throws ParseException
+ * Thrown if the expression string is not valid syntax
*/
public void add(String uri, String expr, List<Var> args) throws ParseException {
Expr e = new SPARQLParser11(new StringReader(expr)).Expression();
if (!preserveDependencies) {
- //If not allowing dependencies expand expression fully
+ // If not allowing dependencies expand expression fully
e = ExprTransformer.transform(new ExprTransformExpand(this.definitions), e);
- }
-
+ }
+
UserDefinedFunctionDefinition def = new UserDefinedFunctionDefinition(uri, e, args);
this.definitions.put(uri, def);
FunctionRegistry.get().put(uri, this);
}
-
+
/**
* Removes a function definition
- * @param uri URI
- * @throws NoSuchElementException Thrown if a function with the given URI does not exist
+ *
+ * @param uri
+ * URI
+ * @throws NoSuchElementException
+ * Thrown if a function with the given URI does not exist
*/
public void remove(String uri) {
- if (!this.definitions.containsKey(uri)) throw new NoSuchElementException("No function definition is associated with the URI <" + uri + ">");
+ if (!this.definitions.containsKey(uri))
+ throw new NoSuchElementException("No function definition is associated with the URI <" + uri + ">");
this.definitions.remove(uri);
FunctionRegistry.get().remove(uri);
}
-
+
/**
* Gets the definition of the function (if registered)
- * @param uri URI
+ *
+ * @param uri
+ * URI
* @return Function Definition if registered, null otherwise
*/
public UserDefinedFunctionDefinition get(String uri) {
- if (!this.definitions.containsKey(uri)) return null;
+ if (!this.definitions.containsKey(uri))
+ return null;
return this.definitions.get(uri);
}
-
+
/**
* Gets whether a function with the given URI has been registered
- * @param uri URI
+ *
+ * @param uri
+ * URI
* @return True if registered, false otherwise
*/
public boolean isRegistered(String uri) {
return this.definitions.containsKey(uri);
}
-
+
/**
* Clears all function definitions
*/
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=1496242&r1=1496241&r2=1496242&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 Mon Jun 24 22:31:00 2013
@@ -767,6 +767,11 @@ public class TestTransformFilters
"(leftjoin (bgp (?x ?p ?o)) (bgp (?y ?p1 ?o1)) (&& (= ?x ?y) (> ?o1 ?o2)))",
t_implicitLeftJoin,
"(leftjoin (bgp (?x ?p ?o)) (assign ((?y ?x)) (bgp (?x ?p1 ?o1))) (> ?o1 ?o2))");
+
+ test(
+ "(leftjoin (bgp (?x ?p ?o)) (bgp (?y ?p1 ?o1)) (&& (> ?o1 ?o2) (= ?x ?y)))",
+ t_implicitLeftJoin,
+ "(leftjoin (bgp (?x ?p ?o)) (assign ((?y ?x)) (bgp (?x ?p1 ?o1))) (> ?o1 ?o2))");
}
@Test public void implicitLeftJoin10()
@@ -832,6 +837,47 @@ public class TestTransformFilters
(String[])null);
}
+ @Test public void implicitLeftJoin14()
+ {
+ // The optimizer is capable of eliminating the && entirely where appropriate
+ test(
+ "(leftjoin (bgp (?x ?p ?o)) (bgp (?y ?p1 ?o1) (?y ?p2 ?z)) ((&& (= ?x ?y) (= ?x ?z))))",
+ t_implicitLeftJoin,
+ "(leftjoin (bgp (?x ?p ?o)) (assign ((?y ?x) (?z ?x)) (bgp (?x ?p1 ?o1) (?x ?p2 ?x))))");
+ }
+
+ @Test public void implicitLeftJoin15()
+ {
+ // The optimizer is capable of going one level into a nested && to find conditions to apply
+ test(
+ "(leftjoin (bgp (?x ?p ?o)) (bgp (?y ?p1 ?o1) (?y ?p2 ?z)) ((&& (&& (= ?x ?y) (> ?o1 10)) (= ?x ?z))))",
+ t_implicitLeftJoin,
+ "(leftjoin (bgp (?x ?p ?o)) (assign ((?z ?x) (?y ?x)) (bgp (?x ?p1 ?o1) (?x ?p2 ?x))) (> ?o1 10))");
+
+ test(
+ "(leftjoin (bgp (?x ?p ?o)) (bgp (?y ?p1 ?o1) (?y ?p2 ?z)) ((&& (&& (> ?o1 10) (= ?x ?y)) (= ?x ?z))))",
+ t_implicitLeftJoin,
+ "(leftjoin (bgp (?x ?p ?o)) (assign ((?z ?x) (?y ?x)) (bgp (?x ?p1 ?o1) (?x ?p2 ?x))) (> ?o1 10))");
+ }
+
+ @Test public void implicitLeftJoin16()
+ {
+ // The optimizer won't go two levels deep into && even if it does find something at the top level
+ test(
+ "(leftjoin (bgp (?x ?p ?o)) (bgp (?y ?p1 ?o1) (?y ?p2 ?z)) ((&& (&& (< ?o1 20) (&& (= ?x ?y) (> ?o1 10))) (= ?x ?z))))",
+ t_implicitLeftJoin,
+ "(leftjoin (bgp (?x ?p ?o)) (assign ((?z ?x)) (bgp (?y ?p1 ?o1) (?y ?p2 ?x))) (&& (< ?o1 20) (&& (= ?x ?y) (> ?o1 10))))");
+ }
+
+ @Test public void implicitLeftJoin17()
+ {
+ // The optimizer won't go another levels into && if it doesn't find anything in the top level
+ test(
+ "(leftjoin (bgp (?x ?p ?o)) (bgp (?y ?p1 ?o1) (?y ?p2 ?z)) ((&& (&& (= ?x ?y) (> ?o1 10)) (< ?o1 20))))",
+ t_implicitLeftJoin,
+ (String[])null);
+ }
+
@Test public void implicitLeftJoinConditional1()
{
// Can be optimized because not all assigns block linearization
@@ -840,7 +886,7 @@ public class TestTransformFilters
new TransformJoinStrategy(),
"(conditional (bgp (?x ?p ?o)) (assign ((?y ?x)) (bgp (?x ?p1 ?o1))))");
}
-
+
public static void test(String input, Transform transform, String... output)
{
Op op1 = SSE.parseOp(input) ;