Menu
▾
▴
[Bigdata-commit] SF.net SVN: bigdata:[4246] branches/QUADS_QUERY_BRANCH/bigdata
|
From: <tho...@us...> - 2011-02-24 20:33:37
|
Revision: 4246
http://bigdata.svn.sourceforge.net/bigdata/?rev=4246&view=rev
Author: thompsonbry
Date: 2011-02-24 20:33:29 +0000 (Thu, 24 Feb 2011)
Log Message:
-----------
- Moved canJoin() and canJoinUsingConstraints() to PartitionedJoinGraph utility and their test suites to the com.bigdata.bop.joinGraph package.
- Modified Rule2BOpUtility in preparation for deciding constraint attachments dynamically. However, I still need to modify PartitionedJoinGroup to (a) accept a set of variables known to be bound on entry.
Modified Paths:
--------------
branches/QUADS_QUERY_BRANCH/bigdata/src/java/com/bigdata/bop/BOpUtility.java
branches/QUADS_QUERY_BRANCH/bigdata/src/java/com/bigdata/bop/joinGraph/PartitionedJoinGroup.java
branches/QUADS_QUERY_BRANCH/bigdata/src/java/com/bigdata/bop/joinGraph/rto/JGraph.java
branches/QUADS_QUERY_BRANCH/bigdata/src/test/com/bigdata/bop/joinGraph/TestAll.java
branches/QUADS_QUERY_BRANCH/bigdata/src/test/com/bigdata/bop/joinGraph/TestPartitionedJoinGroup.java
branches/QUADS_QUERY_BRANCH/bigdata/src/test/com/bigdata/bop/util/TestAll.java
branches/QUADS_QUERY_BRANCH/bigdata-sails/src/java/com/bigdata/rdf/sail/Rule2BOpUtility.java
Added Paths:
-----------
branches/QUADS_QUERY_BRANCH/bigdata/src/test/com/bigdata/bop/joinGraph/TestPartitionedJoinGroup_canJoin.java
branches/QUADS_QUERY_BRANCH/bigdata/src/test/com/bigdata/bop/joinGraph/TestPartitionedJoinGroup_canJoinUsingConstraints.java
Removed Paths:
-------------
branches/QUADS_QUERY_BRANCH/bigdata/src/test/com/bigdata/bop/util/TestBOpUtility_canJoin.java
branches/QUADS_QUERY_BRANCH/bigdata/src/test/com/bigdata/bop/util/TestBOpUtility_canJoinUsingConstraints.java
Modified: branches/QUADS_QUERY_BRANCH/bigdata/src/java/com/bigdata/bop/BOpUtility.java
===================================================================
--- branches/QUADS_QUERY_BRANCH/bigdata/src/java/com/bigdata/bop/BOpUtility.java 2011-02-24 17:49:44 UTC (rev 4245)
+++ branches/QUADS_QUERY_BRANCH/bigdata/src/java/com/bigdata/bop/BOpUtility.java 2011-02-24 20:33:29 UTC (rev 4246)
@@ -27,7 +27,6 @@
package com.bigdata.bop;
-import java.util.Arrays;
import java.util.Collections;
import java.util.Iterator;
import java.util.LinkedHashMap;
@@ -41,7 +40,6 @@
import com.bigdata.bop.BOp.Annotations;
import com.bigdata.bop.engine.BOpStats;
-import com.bigdata.bop.joinGraph.PartitionedJoinGroup;
import com.bigdata.btree.AbstractNode;
import com.bigdata.relation.accesspath.IAsynchronousIterator;
import com.bigdata.relation.accesspath.IBlockingBuffer;
@@ -60,7 +58,8 @@
*/
public class BOpUtility {
- private static final Logger log = Logger.getLogger(BOpUtility.class);
+ private static transient final Logger log = Logger
+ .getLogger(BOpUtility.class);
/**
* Pre-order recursive visitation of the operator tree (arguments only, no
@@ -1151,288 +1150,4 @@
}
- /**
- * Return <code>true</code> iff two predicates can join on the basis of at
- * least one variable which is shared directly by those predicates. Only the
- * operands of the predicates are considered.
- * <p>
- * Note: This method will only identify joins where the predicates directly
- * share at least one variable. However, joins are also possible when the
- * predicates share variables via one or more constraint(s). Use
- * {@link #canJoinUsingConstraints(IPredicate[], IPredicate, IConstraint[])}
- * to identify such joins.
- * <p>
- * Note: Any two predicates may join regardless of the presence of shared
- * variables. However, such joins will produce the full cross product of the
- * binding sets selected by each predicate. As such, they should be run last
- * and this method will not return <code>true</code> for such predicates.
- * <p>
- * Note: This method is more efficient than {@link #getSharedVars(BOp, BOp)}
- * because it does not materialize the sets of shared variables. However, it
- * only considers the operands of the {@link IPredicate}s and is thus more
- * restricted than {@link #getSharedVars(BOp, BOp)} as well.
- *
- * @param p1
- * A predicate.
- * @param p2
- * Another predicate.
- *
- * @return <code>true</code> iff the predicates share at least one variable
- * as an operand.
- *
- * @throws IllegalArgumentException
- * if the two either reference is <code>null</code>.
- */
-// * @throws IllegalArgumentException
-// * if the reference are the same.
- static public boolean canJoin(final IPredicate<?> p1, final IPredicate<?> p2) {
-
- if (p1 == null)
- throw new IllegalArgumentException();
-
- if (p2 == null)
- throw new IllegalArgumentException();
-
-// if (p1 == p2)
-// throw new IllegalArgumentException();
-
- // iterator scanning the operands of p1.
- final Iterator<IVariable<?>> itr1 = BOpUtility.getArgumentVariables(p1);
-
- while (itr1.hasNext()) {
-
- final IVariable<?> v1 = itr1.next();
-
- // iterator scanning the operands of p2.
- final Iterator<IVariable<?>> itr2 = BOpUtility
- .getArgumentVariables(p2);
-
- while (itr2.hasNext()) {
-
- final IVariable<?> v2 = itr2.next();
-
- if (v1 == v2) {
-
- if (log.isDebugEnabled())
- log.debug("Can join: sharedVar=" + v1 + ", p1=" + p1
- + ", p2=" + p2);
-
- return true;
-
- }
-
- }
-
- }
-
- if (log.isDebugEnabled())
- log.debug("No directly shared variable: p1=" + p1 + ", p2=" + p2);
-
- return false;
-
- }
-
- /**
- * Return <code>true</code> iff a predicate may be used to extend a join
- * path on the basis of at least one variable which is shared either
- * directly or via one or more constraints which may be attached to the
- * predicate when it is added to the join path. The join path is used to
- * decide which variables are known to be bound, which in turn decides which
- * constraints may be run. Unlike the case when the variable is directly
- * shared between the two predicates, a join involving a constraint requires
- * us to know which variables are already bound so we can know when the
- * constraint may be attached.
- * <p>
- * Note: Use {@link #canJoin(IPredicate, IPredicate)} instead to identify
- * joins based on a variable which is directly shared.
- * <p>
- * Note: Any two predicates may join regardless of the presence of shared
- * variables. However, such joins will produce the full cross product of the
- * binding sets selected by each predicate. As such, they should be run last
- * and this method will not return <code>true</code> for such predicates.
- *
- * @param path
- * A join path containing at least one predicate.
- * @param vertex
- * A predicate which is being considered as an extension of that
- * join path.
- * @param constraints
- * A set of zero or more constraints (optional). Constraints are
- * attached dynamically once the variables which they use are
- * bound. Hence, a constraint will always share a variable with
- * any predicate to which it is attached. If any constraints are
- * attached to the given vertex and they share a variable which
- * has already been bound by the join path, then the vertex may
- * join with the join path even if it does not directly bind that
- * variable.
- *
- * @return <code>true</code> iff the vertex can join with the join path via
- * a shared variable.
- *
- * @throws IllegalArgumentException
- * if the join path is <code>null</code>.
- * @throws IllegalArgumentException
- * if the join path is empty.
- * @throws IllegalArgumentException
- * if any element in the join path is <code>null</code>.
- * @throws IllegalArgumentException
- * if the vertex is <code>null</code>.
- * @throws IllegalArgumentException
- * if the vertex is already part of the join path.
- * @throws IllegalArgumentException
- * if any element in the optional constraints array is
- * <code>null</code>.
- */
- static public boolean canJoinUsingConstraints(final IPredicate<?>[] path,
- final IPredicate<?> vertex, final IConstraint[] constraints) {
-
- /*
- * Check arguments.
- */
- if (path == null)
- throw new IllegalArgumentException();
- if (vertex == null)
- throw new IllegalArgumentException();
- // constraints MAY be null.
- if (path.length == 0)
- throw new IllegalArgumentException();
- {
- for (IPredicate<?> p : path) {
- if (p == null)
- throw new IllegalArgumentException();
- if (vertex == p)
- throw new IllegalArgumentException();
- }
- }
-
- /*
- * Find the set of variables which are known to be bound because they
- * are referenced as operands of the predicates in the join path.
- */
- final Set<IVariable<?>> knownBound = new LinkedHashSet<IVariable<?>>();
-
- for (IPredicate<?> p : path) {
-
- final Iterator<IVariable<?>> vitr = BOpUtility
- .getArgumentVariables(p);
-
- while (vitr.hasNext()) {
-
- knownBound.add(vitr.next());
-
- }
-
- }
-
- /*
- *
- * If the given predicate directly shares a variable with any of the
- * predicates in the join path, then we can return immediately.
- */
- {
-
- final Iterator<IVariable<?>> vitr = BOpUtility
- .getArgumentVariables(vertex);
-
- while (vitr.hasNext()) {
-
- final IVariable<?> var = vitr.next();
-
- if(knownBound.contains(var)) {
-
- if (log.isDebugEnabled())
- log.debug("Can join: sharedVar=" + var + ", path="
- + Arrays.toString(path) + ", vertex=" + vertex);
-
- return true;
-
- }
-
- }
-
- }
-
- if(constraints == null) {
-
- // No opportunity for a constraint based join.
-
- if (log.isDebugEnabled())
- log.debug("No directly shared variable: path="
- + Arrays.toString(path) + ", vertex=" + vertex);
-
- return false;
-
- }
-
- /*
- * Find the set of constraints which can run with the vertex given the
- * join path.
- */
- {
-
- // Extend the new join path.
- final IPredicate<?>[] newPath = new IPredicate[path.length + 1];
-
- System.arraycopy(path/* src */, 0/* srcPos */, newPath/* dest */,
- 0/* destPos */, path.length);
-
- newPath[path.length] = vertex;
-
- /*
- * Find the constraints that will run with each vertex of the new
- * join path.
- *
- * TODO This is a forward reference to a different package, so maybe
- * move the canJoinWithConstraints() method to that package?
- */
- final IConstraint[][] constraintRunArray = PartitionedJoinGroup
- .getJoinGraphConstraints(newPath, constraints);
-
- /*
- * Consider only the constraints attached to the last vertex in the
- * new join path. All of their variables will be bound since (by
- * definition) a constraint may not run until its variables are
- * bound. If any of the constraints attached to that last share any
- * variables which were already known to be bound in the caller's
- * join path, then the vertex can join (without of necessity being
- * a full cross product join).
- */
- final IConstraint[] vertexConstraints = constraintRunArray[path.length];
-
- for (IConstraint c : vertexConstraints) {
-
- // consider all variables spanned by the constraint.
- final Iterator<IVariable<?>> vitr = BOpUtility
- .getSpannedVariables(c);
-
- while (vitr.hasNext()) {
-
- final IVariable<?> var = vitr.next();
-
- if (knownBound.contains(var)) {
-
- if (log.isDebugEnabled())
- log.debug("Can join: sharedVar=" + var + ", path="
- + Arrays.toString(path) + ", vertex="
- + vertex + ", constraint=" + c);
-
- return true;
-
- }
-
- }
-
- }
-
- }
-
- if (log.isDebugEnabled())
- log.debug("No shared variable: path=" + Arrays.toString(path)
- + ", vertex=" + vertex + ", constraints="
- + Arrays.toString(constraints));
-
- return false;
-
- }
-
}
Modified: branches/QUADS_QUERY_BRANCH/bigdata/src/java/com/bigdata/bop/joinGraph/PartitionedJoinGroup.java
===================================================================
--- branches/QUADS_QUERY_BRANCH/bigdata/src/java/com/bigdata/bop/joinGraph/PartitionedJoinGroup.java 2011-02-24 17:49:44 UTC (rev 4245)
+++ branches/QUADS_QUERY_BRANCH/bigdata/src/java/com/bigdata/bop/joinGraph/PartitionedJoinGroup.java 2011-02-24 20:33:29 UTC (rev 4246)
@@ -1,5 +1,6 @@
package com.bigdata.bop.joinGraph;
+import java.util.Arrays;
import java.util.Iterator;
import java.util.LinkedHashMap;
import java.util.LinkedHashSet;
@@ -100,6 +101,8 @@
* A map indicating which constraints are run for which predicate in the
* tail plan. The keys are the bopIds of the predicates in the tail plan.
* The values are the sets of constraints to run for that tail.
+ *
+ * @todo This assumes that the tail plan is not reordered.
*/
private final Map<Integer/* predId */, List<IConstraint>> tailPlanConstraintMap = new LinkedHashMap<Integer, List<IConstraint>>();
@@ -442,6 +445,285 @@
}
/**
+ * Return <code>true</code> iff two predicates can join on the basis of at
+ * least one variable which is shared directly by those predicates. Only the
+ * operands of the predicates are considered.
+ * <p>
+ * Note: This method will only identify joins where the predicates directly
+ * share at least one variable. However, joins are also possible when the
+ * predicates share variables via one or more constraint(s). Use
+ * {@link canJoinUsingConstraints} to identify such joins.
+ * <p>
+ * Note: Any two predicates may join regardless of the presence of shared
+ * variables. However, such joins will produce the full cross product of the
+ * binding sets selected by each predicate. As such, they should be run last
+ * and this method will not return <code>true</code> for such predicates.
+ * <p>
+ * Note: This method is more efficient than
+ * {@link BOpUtility#getSharedVars(BOp, BOp)} because it does not
+ * materialize the sets of shared variables. However, it only considers the
+ * operands of the {@link IPredicate}s and is thus more restricted than
+ * {@link BOpUtility#getSharedVars(BOp, BOp)} as well.
+ *
+ * @param p1
+ * A predicate.
+ * @param p2
+ * Another predicate.
+ *
+ * @return <code>true</code> iff the predicates share at least one variable
+ * as an operand.
+ *
+ * @throws IllegalArgumentException
+ * if the two either reference is <code>null</code>.
+ */
+ static public boolean canJoin(final IPredicate<?> p1, final IPredicate<?> p2) {
+
+ if (p1 == null)
+ throw new IllegalArgumentException();
+
+ if (p2 == null)
+ throw new IllegalArgumentException();
+
+ // iterator scanning the operands of p1.
+ final Iterator<IVariable<?>> itr1 = BOpUtility.getArgumentVariables(p1);
+
+ while (itr1.hasNext()) {
+
+ final IVariable<?> v1 = itr1.next();
+
+ // iterator scanning the operands of p2.
+ final Iterator<IVariable<?>> itr2 = BOpUtility
+ .getArgumentVariables(p2);
+
+ while (itr2.hasNext()) {
+
+ final IVariable<?> v2 = itr2.next();
+
+ if (v1 == v2) {
+
+ if (log.isDebugEnabled())
+ log.debug("Can join: sharedVar=" + v1 + ", p1=" + p1
+ + ", p2=" + p2);
+
+ return true;
+
+ }
+
+ }
+
+ }
+
+ if (log.isDebugEnabled())
+ log.debug("No directly shared variable: p1=" + p1 + ", p2=" + p2);
+
+ return false;
+
+ }
+
+ /**
+ * Return <code>true</code> iff a predicate may be used to extend a join
+ * path on the basis of at least one variable which is shared either
+ * directly or via one or more constraints which may be attached to the
+ * predicate when it is added to the join path. The join path is used to
+ * decide which variables are known to be bound, which in turn decides which
+ * constraints may be run. Unlike the case when the variable is directly
+ * shared between the two predicates, a join involving a constraint requires
+ * us to know which variables are already bound so we can know when the
+ * constraint may be attached.
+ * <p>
+ * Note: Use {@link PartitionedJoinGroup#canJoin(IPredicate, IPredicate)}
+ * instead to identify joins based on a variable which is directly shared.
+ * <p>
+ * Note: Any two predicates may join regardless of the presence of shared
+ * variables. However, such joins will produce the full cross product of the
+ * binding sets selected by each predicate. As such, they should be run last
+ * and this method will not return <code>true</code> for such predicates.
+ *
+ * @param path
+ * A join path containing at least one predicate.
+ * @param vertex
+ * A predicate which is being considered as an extension of that
+ * join path.
+ * @param constraints
+ * A set of zero or more constraints (optional). Constraints are
+ * attached dynamically once the variables which they use are
+ * bound. Hence, a constraint will always share a variable with
+ * any predicate to which it is attached. If any constraints are
+ * attached to the given vertex and they share a variable which
+ * has already been bound by the join path, then the vertex may
+ * join with the join path even if it does not directly bind that
+ * variable.
+ *
+ * @return <code>true</code> iff the vertex can join with the join path via
+ * a shared variable.
+ *
+ * @throws IllegalArgumentException
+ * if the join path is <code>null</code>.
+ * @throws IllegalArgumentException
+ * if the join path is empty.
+ * @throws IllegalArgumentException
+ * if any element in the join path is <code>null</code>.
+ * @throws IllegalArgumentException
+ * if the vertex is <code>null</code>.
+ * @throws IllegalArgumentException
+ * if the vertex is already part of the join path.
+ * @throws IllegalArgumentException
+ * if any element in the optional constraints array is
+ * <code>null</code>.
+ */
+ static public boolean canJoinUsingConstraints(final IPredicate<?>[] path,
+ final IPredicate<?> vertex, final IConstraint[] constraints) {
+
+ /*
+ * Check arguments.
+ */
+ if (path == null)
+ throw new IllegalArgumentException();
+ if (vertex == null)
+ throw new IllegalArgumentException();
+ // constraints MAY be null.
+ if (path.length == 0)
+ throw new IllegalArgumentException();
+ {
+ for (IPredicate<?> p : path) {
+ if (p == null)
+ throw new IllegalArgumentException();
+ if (vertex == p)
+ throw new IllegalArgumentException();
+ }
+ }
+
+ /*
+ * Find the set of variables which are known to be bound because they
+ * are referenced as operands of the predicates in the join path.
+ */
+ final Set<IVariable<?>> knownBound = new LinkedHashSet<IVariable<?>>();
+
+ for (IPredicate<?> p : path) {
+
+ final Iterator<IVariable<?>> vitr = BOpUtility
+ .getArgumentVariables(p);
+
+ while (vitr.hasNext()) {
+
+ knownBound.add(vitr.next());
+
+ }
+
+ }
+
+ /*
+ *
+ * If the given predicate directly shares a variable with any of the
+ * predicates in the join path, then we can return immediately.
+ */
+ {
+
+ final Iterator<IVariable<?>> vitr = BOpUtility
+ .getArgumentVariables(vertex);
+
+ while (vitr.hasNext()) {
+
+ final IVariable<?> var = vitr.next();
+
+ if (knownBound.contains(var)) {
+
+ if (log.isDebugEnabled())
+ log.debug("Can join: sharedVar=" + var + ", path="
+ + Arrays.toString(path) + ", vertex=" + vertex);
+
+ return true;
+
+ }
+
+ }
+
+ }
+
+ if (constraints == null) {
+
+ // No opportunity for a constraint based join.
+
+ if (log.isDebugEnabled())
+ log.debug("No directly shared variable: path="
+ + Arrays.toString(path) + ", vertex=" + vertex);
+
+ return false;
+
+ }
+
+ /*
+ * Find the set of constraints which can run with the vertex given the
+ * join path.
+ */
+ {
+
+ // Extend the new join path.
+ final IPredicate<?>[] newPath = new IPredicate[path.length + 1];
+
+ System.arraycopy(path/* src */, 0/* srcPos */, newPath/* dest */,
+ 0/* destPos */, path.length);
+
+ newPath[path.length] = vertex;
+
+ /*
+ * Find the constraints that will run with each vertex of the new
+ * join path.
+ *
+ * TODO This is a forward reference to a different package, so maybe
+ * move the canJoinWithConstraints() method to that package?
+ */
+ final IConstraint[][] constraintRunArray = getJoinGraphConstraints(
+ newPath, constraints);
+
+ /*
+ * Consider only the constraints attached to the last vertex in the
+ * new join path. All of their variables will be bound since (by
+ * definition) a constraint may not run until its variables are
+ * bound. If any of the constraints attached to that last share any
+ * variables which were already known to be bound in the caller's
+ * join path, then the vertex can join (without of necessity being a
+ * full cross product join).
+ */
+ final IConstraint[] vertexConstraints = constraintRunArray[path.length];
+
+ for (IConstraint c : vertexConstraints) {
+
+ // consider all variables spanned by the constraint.
+ final Iterator<IVariable<?>> vitr = BOpUtility
+ .getSpannedVariables(c);
+
+ while (vitr.hasNext()) {
+
+ final IVariable<?> var = vitr.next();
+
+ if (knownBound.contains(var)) {
+
+ if (log.isDebugEnabled())
+ log.debug("Can join: sharedVar=" + var + ", path="
+ + Arrays.toString(path) + ", vertex="
+ + vertex + ", constraint=" + c);
+
+ return true;
+
+ }
+
+ }
+
+ }
+
+ }
+
+ if (log.isDebugEnabled())
+ log.debug("No shared variable: path=" + Arrays.toString(path)
+ + ", vertex=" + vertex + ", constraints="
+ + Arrays.toString(constraints));
+
+ return false;
+
+ }
+
+ /**
* Analyze a set of {@link IPredicate}s representing "runFirst", optional
* joins, and non-optional joins which may be freely reordered together with
* a collection of {@link IConstraint}s and partition them into a join graph
@@ -450,6 +732,8 @@
* be used to formulate a complete query when combined with a desired join
* ordering.
*
+ * @param knownBound
+ * A set of variables which are known to be bound on entry.
* @param sourcePreds
* The predicates.
* @param constraints
@@ -467,6 +751,7 @@
* <code>null</code>.
*/
public PartitionedJoinGroup(//
+// final Set<IVariable<?>> knownBound,
final IPredicate<?>[] sourcePreds,//
IConstraint[] constraints) {
Modified: branches/QUADS_QUERY_BRANCH/bigdata/src/java/com/bigdata/bop/joinGraph/rto/JGraph.java
===================================================================
--- branches/QUADS_QUERY_BRANCH/bigdata/src/java/com/bigdata/bop/joinGraph/rto/JGraph.java 2011-02-24 17:49:44 UTC (rev 4245)
+++ branches/QUADS_QUERY_BRANCH/bigdata/src/java/com/bigdata/bop/joinGraph/rto/JGraph.java 2011-02-24 20:33:29 UTC (rev 4246)
@@ -47,6 +47,7 @@
import com.bigdata.bop.ap.SampleIndex.SampleType;
import com.bigdata.bop.engine.QueryEngine;
import com.bigdata.bop.joinGraph.NoSolutionsException;
+import com.bigdata.bop.joinGraph.PartitionedJoinGroup;
import com.bigdata.bop.rdf.join.DataSetJoin;
/**
@@ -894,7 +895,7 @@
continue;
}
- if (!BOpUtility.canJoinUsingConstraints(//
+ if (!PartitionedJoinGroup.canJoinUsingConstraints(//
x.getPredicates(),// path
tVertex.pred,// vertex
C// constraints
@@ -1113,7 +1114,7 @@
vp = v1;
}
- if (!BOpUtility.canJoinUsingConstraints(
+ if (!PartitionedJoinGroup.canJoinUsingConstraints(
new IPredicate[] { v.pred }, vp.pred, C)) {
/*
Modified: branches/QUADS_QUERY_BRANCH/bigdata/src/test/com/bigdata/bop/joinGraph/TestAll.java
===================================================================
--- branches/QUADS_QUERY_BRANCH/bigdata/src/test/com/bigdata/bop/joinGraph/TestAll.java 2011-02-24 17:49:44 UTC (rev 4245)
+++ branches/QUADS_QUERY_BRANCH/bigdata/src/test/com/bigdata/bop/joinGraph/TestAll.java 2011-02-24 20:33:29 UTC (rev 4246)
@@ -62,6 +62,12 @@
suite.addTestSuite(TestPartitionedJoinGroup.class);
+ // unit tests for allowing joins based on shared variables in preds.
+ suite.addTestSuite(TestPartitionedJoinGroup_canJoin.class);
+
+ // more complex logic for join paths.
+ suite.addTestSuite(TestPartitionedJoinGroup_canJoinUsingConstraints.class);
+
// static query optimizer test suite.
suite.addTest(com.bigdata.bop.joinGraph.fast.TestAll.suite());
Modified: branches/QUADS_QUERY_BRANCH/bigdata/src/test/com/bigdata/bop/joinGraph/TestPartitionedJoinGroup.java
===================================================================
--- branches/QUADS_QUERY_BRANCH/bigdata/src/test/com/bigdata/bop/joinGraph/TestPartitionedJoinGroup.java 2011-02-24 17:49:44 UTC (rev 4245)
+++ branches/QUADS_QUERY_BRANCH/bigdata/src/test/com/bigdata/bop/joinGraph/TestPartitionedJoinGroup.java 2011-02-24 20:33:29 UTC (rev 4246)
@@ -49,6 +49,11 @@
*
* @author <a href="mailto:tho...@us...">Bryan Thompson</a>
* @version $Id$
+ *
+ * FIXME Add test to ensure that constraints are run regardless as of the last
+ * join even if their variables are not known to be bound. Also, modify the
+ * constructor to accept a set of variables which are known to be bound on
+ * entry into the join group.
*/
public class TestPartitionedJoinGroup extends TestCase2 {
@@ -493,7 +498,7 @@
final int nrange = expected.length;
- java.util.Map range = new java.util.HashMap();
+ final java.util.Map range = new java.util.HashMap();
for (int j = 0; j < nrange; j++) {
@@ -513,7 +518,7 @@
}
- Object actualObject = actual.next();
+ final Object actualObject = actual.next();
if (range.remove(actualObject) == null) {
Copied: branches/QUADS_QUERY_BRANCH/bigdata/src/test/com/bigdata/bop/joinGraph/TestPartitionedJoinGroup_canJoin.java (from rev 4218, branches/QUADS_QUERY_BRANCH/bigdata/src/test/com/bigdata/bop/util/TestBOpUtility_canJoin.java)
===================================================================
--- branches/QUADS_QUERY_BRANCH/bigdata/src/test/com/bigdata/bop/joinGraph/TestPartitionedJoinGroup_canJoin.java (rev 0)
+++ branches/QUADS_QUERY_BRANCH/bigdata/src/test/com/bigdata/bop/joinGraph/TestPartitionedJoinGroup_canJoin.java 2011-02-24 20:33:29 UTC (rev 4246)
@@ -0,0 +1,153 @@
+/**
+
+Copyright (C) SYSTAP, LLC 2006-2011. All rights reserved.
+
+Contact:
+ SYSTAP, LLC
+ 4501 Tower Road
+ Greensboro, NC 27410
+ lic...@bi...
+
+This program is free software; you can redistribute it and/or modify
+it under the terms of the GNU General Public License as published by
+the Free Software Foundation; version 2 of the License.
+
+This program is distributed in the hope that it will be useful,
+but WITHOUT ANY WARRANTY; without even the implied warranty of
+MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
+GNU General Public License for more details.
+
+You should have received a copy of the GNU General Public License
+along with this program; if not, write to the Free Software
+Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA
+*/
+/*
+ * Created on Feb 20, 2011
+ */
+
+package com.bigdata.bop.joinGraph;
+
+import com.bigdata.bop.BOp;
+import com.bigdata.bop.IPredicate;
+import com.bigdata.bop.IVariable;
+import com.bigdata.bop.NV;
+import com.bigdata.bop.Var;
+import com.bigdata.bop.ap.Predicate;
+import com.bigdata.bop.joinGraph.PartitionedJoinGroup;
+
+import junit.framework.TestCase2;
+
+/**
+ * Unit tests for {@link PartitionedJoinGroup#canJoin(IPredicate, IPredicate)}
+ *
+ * @author <a href="mailto:tho...@us...">Bryan Thompson</a>
+ * @version $Id$
+ */
+public class TestPartitionedJoinGroup_canJoin extends TestCase2 {
+
+ /**
+ *
+ */
+ public TestPartitionedJoinGroup_canJoin() {
+ }
+
+ /**
+ * @param name
+ */
+ public TestPartitionedJoinGroup_canJoin(String name) {
+ super(name);
+ }
+
+
+ /**
+ * Correct rejection tests.
+ *
+ * @see BOpUtility#canJoin(IPredicate, IPredicate).
+ */
+ @SuppressWarnings("unchecked")
+ public void test_canJoin_correctRejection() {
+
+ final IVariable<?> x = Var.var("x");
+ final IVariable<?> y = Var.var("y");
+ final IVariable<?> z = Var.var("z");
+
+ final IPredicate<?> p1 = new Predicate(new BOp[]{x,y});
+ final IPredicate<?> p2 = new Predicate(new BOp[]{y,z});
+
+ // correct rejection w/ null arg.
+ try {
+ PartitionedJoinGroup.canJoin(null,p2);
+ fail("Expecting: " + IllegalArgumentException.class);
+ } catch (IllegalArgumentException ex) {
+ if (log.isInfoEnabled())
+ log.info("Ignoring expected exception: " + ex);
+ }
+
+ // correct rejection w/ null arg.
+ try {
+ PartitionedJoinGroup.canJoin(p1,null);
+ fail("Expecting: " + IllegalArgumentException.class);
+ } catch (IllegalArgumentException ex) {
+ if (log.isInfoEnabled())
+ log.info("Ignoring expected exception: " + ex);
+ }
+
+ }
+
+ /**
+ * Semantics tests focused on shared variables in the operands.
+ *
+ * @see PartitionedJoinGroup#canJoin(IPredicate, IPredicate)
+ */
+ @SuppressWarnings("unchecked")
+ public void test_canJoin() {
+
+ final IVariable<?> u = Var.var("u");
+ final IVariable<?> x = Var.var("x");
+ final IVariable<?> y = Var.var("y");
+ final IVariable<?> z = Var.var("z");
+
+ final IPredicate<?> p1 = new Predicate(new BOp[] { x, y });
+ final IPredicate<?> p2 = new Predicate(new BOp[] { y, z });
+ final IPredicate<?> p3 = new Predicate(new BOp[] { u, z });
+
+ // share y
+ assertTrue(PartitionedJoinGroup.canJoin(p1, p2));
+
+ // share z
+ assertTrue(PartitionedJoinGroup.canJoin(p2, p3));
+
+ // share z
+ assertFalse(PartitionedJoinGroup.canJoin(p1, p3));
+
+ // shares (x,y) with self.
+ assertTrue(PartitionedJoinGroup.canJoin(p1, p1));
+
+ }
+
+ /**
+ * Verify that joins are not permitted when the variables are
+ * only shared via an annotation.
+ *
+ * @see PartitionedJoinGroup#canJoin(IPredicate, IPredicate)
+ */
+ @SuppressWarnings("unchecked")
+ public void test_canJoin_annotationsAreIngored() {
+
+ final IVariable<?> x = Var.var("x");
+ final IVariable<?> y = Var.var("y");
+ final IVariable<?> z = Var.var("z");
+
+ final IPredicate<?> p1 = new Predicate(new BOp[] { x, },//
+ new NV("foo", y)//
+ );
+ final IPredicate<?> p2 = new Predicate(new BOp[] { z },//
+ new NV("foo", y)
+ );
+
+ // verify that the variables in the annotations are ignored.
+ assertFalse(PartitionedJoinGroup.canJoin(p1, p2));
+
+ }
+
+}
Copied: branches/QUADS_QUERY_BRANCH/bigdata/src/test/com/bigdata/bop/joinGraph/TestPartitionedJoinGroup_canJoinUsingConstraints.java (from rev 4233, branches/QUADS_QUERY_BRANCH/bigdata/src/test/com/bigdata/bop/util/TestBOpUtility_canJoinUsingConstraints.java)
===================================================================
--- branches/QUADS_QUERY_BRANCH/bigdata/src/test/com/bigdata/bop/joinGraph/TestPartitionedJoinGroup_canJoinUsingConstraints.java (rev 0)
+++ branches/QUADS_QUERY_BRANCH/bigdata/src/test/com/bigdata/bop/joinGraph/TestPartitionedJoinGroup_canJoinUsingConstraints.java 2011-02-24 20:33:29 UTC (rev 4246)
@@ -0,0 +1,719 @@
+/**
+
+Copyright (C) SYSTAP, LLC 2006-2011. All rights reserved.
+
+Contact:
+ SYSTAP, LLC
+ 4501 Tower Road
+ Greensboro, NC 27410
+ lic...@bi...
+
+This program is free software; you can redistribute it and/or modify
+it under the terms of the GNU General Public License as published by
+the Free Software Foundation; version 2 of the License.
+
+This program is distributed in the hope that it will be useful,
+but WITHOUT ANY WARRANTY; without even the implied warranty of
+MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
+GNU General Public License for more details.
+
+You should have received a copy of the GNU General Public License
+along with this program; if not, write to the Free Software
+Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA
+*/
+/*
+ * Created on Feb 20, 2011
+ */
+
+package com.bigdata.bop.joinGraph;
+
+import java.util.LinkedHashSet;
+import java.util.Map;
+import java.util.Random;
+import java.util.Set;
+
+import junit.framework.TestCase2;
+
+import com.bigdata.bop.BOp;
+import com.bigdata.bop.Constant;
+import com.bigdata.bop.IBindingSet;
+import com.bigdata.bop.IConstant;
+import com.bigdata.bop.IConstraint;
+import com.bigdata.bop.IPredicate;
+import com.bigdata.bop.IValueExpression;
+import com.bigdata.bop.IVariable;
+import com.bigdata.bop.ImmutableBOp;
+import com.bigdata.bop.NV;
+import com.bigdata.bop.Var;
+import com.bigdata.bop.ap.Predicate;
+import com.bigdata.bop.constraint.AND;
+import com.bigdata.bop.constraint.BooleanValueExpression;
+import com.bigdata.bop.constraint.Constraint;
+import com.bigdata.bop.joinGraph.PartitionedJoinGroup;
+import com.bigdata.bop.joinGraph.rto.JGraph;
+
+/**
+ *
+ * This test suite is built around around BSBM Q5. Each test has an existing
+ * join path and a new vertex to be added to the join path. The question is
+ * whether or not the vertex <em>can join</em> with the join path using one or
+ * more shared variable(s). This tests a method used to incrementally grow a
+ * join path when it is dynamically decided that an {@link IPredicate} may be
+ * added to the join path based on shared variables. Static analysis easily
+ * reports those joins which are allowed based on the variables directly given
+ * with two {@link IPredicate}s. The purpose of this test suite is to explore
+ * when joins (based on shared variables) become permissible through
+ * {@link IConstraint}s as the variable(s) used within those constraints become
+ * bound.
+ * <p>
+ * Note: To avoid a dependency on the RDF model layer, this just uses String
+ * constants for URIs and Literals.
+ * <h2>Analysis of BSBM Q5</h2>
+ * The following predicates all join on {@link #product}:
+ * <ul>
+ * <li>{@link #p0}</li>
+ * <li>{@link #p2}</li>
+ * <li>{@link #p4}</li>
+ * <li>{@link #p5}</li>
+ * </ul>
+ * The predicates ({@link #p3} and {@link #p5}) do not directly join with any of
+ * the other predicates (they do not directly share any variables). In general,
+ * a join without shared variables means the cross product of the sources will
+ * be materialized and such joins should be run last.
+ * <p>
+ * However, in this case there are two SPARQL FILTERs ({@link #c1} and
+ * {@link #c2}) which (a) use those variables ({@link #origProperty1} and
+ * {@link #origProperty2}); and (b) can constrain the query. This means that
+ * running the predicates without shared variables and applying the constraints
+ * before the tail of the plan can in fact lead to a more efficient join path.
+ * <p>
+ * This set of unit tests explores various join paths and verifies that the
+ * canJoin() and canJoinUsingConstraints() methods correctly recognize edges by
+ * which a join path can be extended corresponding to both static and dynamic
+ * analysis of the query.
+ *
+ * @see PartitionedJoinGroup#canJoin(IPredicate, IPredicate)
+ * @see PartitionedJoinGroup#canJoinUsingConstraints(IPredicate[], IPredicate,
+ * IConstraint[])
+ * @see JGraph
+ *
+ * @author <a href="mailto:tho...@us...">Bryan Thompson</a>
+ * @version $Id: TestBOpUtility_canJoinUsingConstraints.java 4211 2011-02-20
+ * 21:20:44Z thompsonbry $
+ *
+ * @todo These are the full plans generated by the runtime and static
+ * optimizers. One way to test canJoinXXX() is to run out these join plans
+ * and verify that they report "true" in each case. However, the critical
+ * bit to test are join plans where the predicates w/o the shared
+ * variables can be run earlier due to the FILTERs.
+ *
+ * <pre>
+ * test_bsbm_q5 : static [0] : : ids=[1, 2, 4, 6, 0, 3, 5]
+ * test_bsbm_q5 : runtime[0] : : ids=[1, 2, 0, 4, 6, 3, 5]
+ * </pre>
+ */
+//@SuppressWarnings("unchecked")
+public class TestPartitionedJoinGroup_canJoinUsingConstraints extends TestCase2 {
+
+ /**
+ *
+ */
+ public TestPartitionedJoinGroup_canJoinUsingConstraints() {
+ }
+
+ /**
+ * @param name
+ */
+ public TestPartitionedJoinGroup_canJoinUsingConstraints(String name) {
+ super(name);
+ }
+
+ /**
+ * Unit tests to verify that arguments are validated.
+ *
+ * @see PartitionedJoinGroup#canJoinUsingConstraints(IPredicate[], IPredicate,
+ * IConstraint[])
+ */
+ public void test_canJoinUsingConstraints_illegalArgument() {
+
+ final IVariable<?> x = Var.var("x");
+ final IVariable<?> y = Var.var("y");
+
+ final IPredicate<?> p1 = new Predicate(new BOp[]{x});
+
+ final IPredicate<?> p2 = new Predicate(new BOp[]{y});
+
+ // path must not be null.
+ try {
+ PartitionedJoinGroup.canJoinUsingConstraints(//
+ null, // path
+ p1,// vertex
+ new IConstraint[0]// constraints
+ );
+ fail("Expecting: " + IllegalArgumentException.class);
+ } catch (IllegalArgumentException ex) {
+ if (log.isInfoEnabled())
+ log.info("Expecting: " + IllegalArgumentException.class);
+ }
+
+ // vertex must not be null.
+ try {
+ PartitionedJoinGroup.canJoinUsingConstraints(//
+ new IPredicate[]{p1}, // path
+ null,// vertex
+ new IConstraint[0]// constraints
+ );
+ fail("Expecting: " + IllegalArgumentException.class);
+ } catch (IllegalArgumentException ex) {
+ if (log.isInfoEnabled())
+ log.info("Expecting: " + IllegalArgumentException.class);
+ }
+
+ // path may not be empty.
+ try {
+ PartitionedJoinGroup.canJoinUsingConstraints(//
+ new IPredicate[] {}, // path
+ p1,// vertex
+ new IConstraint[0]// constraints
+ );
+ fail("Expecting: " + IllegalArgumentException.class);
+ } catch (IllegalArgumentException ex) {
+ if (log.isInfoEnabled())
+ log.info("Expecting: " + IllegalArgumentException.class);
+ }
+
+ // path elements may not be null.
+ try {
+ PartitionedJoinGroup.canJoinUsingConstraints(//
+ new IPredicate[] { p2, null }, // path
+ p1,// vertex
+ new IConstraint[0]// constraints
+ );
+ fail("Expecting: " + IllegalArgumentException.class);
+ } catch (IllegalArgumentException ex) {
+ if (log.isInfoEnabled())
+ log.info("Expecting: " + IllegalArgumentException.class);
+ }
+
+ // vertex must not appear in the path.
+ try {
+ PartitionedJoinGroup.canJoinUsingConstraints(//
+ new IPredicate[] { p2, p1 }, // path
+ p1,// vertex
+ new IConstraint[0]// constraints
+ );
+ fail("Expecting: " + IllegalArgumentException.class);
+ } catch (IllegalArgumentException ex) {
+ if (log.isInfoEnabled())
+ log.info("Expecting: " + IllegalArgumentException.class);
+ }
+
+ // constraint array may not contain null elements.
+ try {
+ PartitionedJoinGroup.canJoinUsingConstraints(//
+ new IPredicate[] { p2 }, // path
+ p1,// vertex
+ new IConstraint[] { //
+ Constraint.wrap(new NEConstant(x, new Constant<Integer>(12))), //
+ null //
+ }// constraints
+ );
+ fail("Expecting: " + IllegalArgumentException.class);
+ } catch (IllegalArgumentException ex) {
+ if (log.isInfoEnabled())
+ log.info("Expecting: " + IllegalArgumentException.class);
+ }
+
+ }
+
+ // The comparison operators.
+ static private final int GT = 0, LT = 1;// , EQ = 2, GTE = 3, LTE = 4;
+
+ // The math operators.
+ static private final int PLUS = 0, MINUS = 1;
+
+ // Annotation for the comparison or math operator.
+ static private final String OP = "op";
+
+ /**
+ * A do-nothing constraint. The constraint is never evaluated. It is only
+ * used to test the logic which decides when two predicates can join based
+ * on variable(s) shared via a constraint.
+ */
+ static private final class MyCompareOp extends BooleanValueExpression {
+
+ private static final long serialVersionUID = 1L;
+
+ /**
+ * Required deep copy constructor.
+ *
+ * @param op
+ */
+ public MyCompareOp(MyCompareOp op) {
+ super(op);
+ }
+
+ /**
+ * @param args
+ * @param annotations
+ */
+ public MyCompareOp(BOp[] args, Map<String, Object> annotations) {
+ super(args, annotations);
+ }
+
+ public Boolean get(IBindingSet bindingSet) {
+ throw new UnsupportedOperationException();
+ }
+
+ }
+
+ /**
+ * A do-nothing constraint. The constraint is never evaluated. It is only
+ * used to test the logic which decides when two predicates can join based
+ * on variable(s) shared via a constraint.
+ */
+ static private final class NEConstant extends BooleanValueExpression {
+
+ private static final long serialVersionUID = 1L;
+
+ /**
+ * Required deep copy constructor.
+ *
+ * @param op
+ */
+ public NEConstant(NEConstant op) {
+ super(op);
+ }
+
+ /**
+ * @param args
+ * @param annotations
+ */
+ public NEConstant(BOp[] args, Map<String, Object> annotations) {
+ super(args, annotations);
+ }
+
+ public NEConstant(IVariable<?> var, IConstant<?> value) {
+ this(new BOp[] { var, value }, null/* annotations */);
+ }
+
+ public Boolean get(IBindingSet bindingSet) {
+ throw new UnsupportedOperationException();
+ }
+
+ }
+
+ /**
+ * A do-nothing value expression. The expression is never evaluated. It is
+ * only used to test the logic which decides when two predicates can join
+ * based on variable(s) shared via a constraint.
+ */
+ static private final class MathBOp extends ImmutableBOp implements
+ IValueExpression {
+
+ private static final long serialVersionUID = 1L;
+
+ /**
+ * Required deep copy constructor.
+ *
+ * @param op
+ */
+ public MathBOp(final MathBOp op) {
+
+ super(op);
+
+ }
+
+ /**
+ * Required shallow copy constructor.
+ *
+ * @param args
+ * The operands.
+ * @param op
+ * The operation.
+ */
+ public MathBOp(final BOp[] args, Map<String, Object> anns) {
+
+ super(args, anns);
+
+ if (args.length != 2 || args[0] == null || args[1] == null
+ || getProperty(OP) == null) {
+
+ throw new IllegalArgumentException();
+
+ }
+
+ }
+
+ /**
+ *
+ * @param left
+ * The left operand.
+ * @param right
+ * The right operand.
+ * @param op
+ * The annotation specifying the operation to be performed on
+ * those operands.
+ */
+ public MathBOp(final IValueExpression left,
+ final IValueExpression right, final int op) {
+
+ this(new BOp[] { left, right }, NV.asMap(new NV(OP, op)));
+
+ }
+
+ public Object get(IBindingSet bindingSet) {
+ throw new UnsupportedOperationException();
+ }
+ }
+
+ static private final String rdfs = "http://www.w3.org/2000/01/rdf-schema#";
+
+ static private final String bsbm = "http://www4.wiwiss.fu-berlin.de/bizer/bsbm/v01/vocabulary/";
+
+ static private final String rdfsLabel = rdfs + "label";
+
+ static private final String productFeature = bsbm + "productFeature";
+
+ static private final String productPropertyNumeric1 = "productPropertyNumeric1";
+
+ static private final String productPropertyNumeric2 = bsbm
+ + "productPropertyNumeric2";
+
+ static private final String productInstance = "http://www4.wiwiss.fu-berlin.de/bizer/bsbm/v01/instances/dataFromProducer1/Product22";
+
+ private int nextId = 0;
+
+ final IVariable<?> product = Var.var("product");
+
+ final IVariable<?> productLabel = Var.var("productLabel");
+
+ final IVariable<?> prodFeature = Var.var("prodFeature");
+
+ final IVariable<?> simProperty1 = Var.var("simProperty1");
+
+ final IVariable<?> simProperty2 = Var.var("simProperty2");
+
+ final IVariable<?> origProperty1 = Var.var("origProperty1");
+
+ final IVariable<?> origProperty2 = Var.var("origProperty2");
+
+ /** ?product rdfs:label ?productLabel . */
+ final private IPredicate<?> p0 = new Predicate(new BOp[] {//
+ product, new Constant(rdfsLabel), productLabel },//
+ new NV(BOp.Annotations.BOP_ID, nextId++)//
+ );
+
+ /** productInstance bsbm:productFeature ?prodFeature . */
+ final private IPredicate<?> p1 = new Predicate(new BOp[] { //
+ new Constant(productInstance), new Constant(productFeature),
+ prodFeature },//
+ new NV(BOp.Annotations.BOP_ID, nextId++)//
+ );
+
+ /** ?product bsbm:productFeature ?prodFeature . */
+ final private IPredicate<?> p2 = new Predicate(new BOp[] { //
+ product, new Constant(productFeature), prodFeature },//
+ new NV(BOp.Annotations.BOP_ID, nextId++)//
+ );
+
+ /** productInstance bsbm:productPropertyNumeric1 ?origProperty1 . */
+ final private IPredicate<?> p3 = new Predicate(new BOp[] { //
+ new Constant<String>(productInstance),
+ new Constant(productPropertyNumeric1), origProperty1 },//
+ new NV(BOp.Annotations.BOP_ID, nextId++)//
+ );
+
+ /** ?product bsbm:productPropertyNumeric1 ?simProperty1 . */
+ final private IPredicate<?> p4 = new Predicate(new BOp[] { //
+ product, new Constant(productPropertyNumeric1), simProperty1 },//
+ new NV(BOp.Annotations.BOP_ID, nextId++)//
+ );
+
+ /** productInstance bsbm:productPropertyNumeric2 ?origProperty2 . */
+ final private IPredicate<?> p5 = new Predicate(new BOp[] { //
+ new Constant(productInstance),
+ new Constant(productPropertyNumeric2), origProperty2 },//
+ new NV(BOp.Annotations.BOP_ID, nextId++)//
+ );
+
+ /** ?product bsbm:productPropertyNumeric2 ?simProperty2 . */
+ final private IPredicate<?> p6 = new Predicate(new BOp[] { //
+ product, new Constant(productPropertyNumeric2), simProperty2 },//
+ new NV(BOp.Annotations.BOP_ID, nextId++)//
+ );
+
+ /** The vertices of the join graph (the predicates). */
+ final IPredicate<?>[] preds = new IPredicate[] { p0, p1, p2, p3, p4, p5, p6 };
+
+ /**
+ * FILTER (productInstance != ?product)
+ */
+ final IConstraint c0 = Constraint.wrap(new NEConstant(product, new Constant<String>(
+ productInstance)));
+
+ /**
+ * FILTER (?simProperty1 < (?origProperty1 + 120) && ?simProperty1 >
+ * (?origProperty1 - 120))
+ * <p>
+ * Note: The AND in the compound filters is typically optimized out such
+ * that each of these is represented as its own IConstraint, but I have
+ * combined them for the purposes of these unit tests.
+ */
+ final IConstraint c1 = Constraint.wrap(new AND(//
+ new MyCompareOp(
+ new BOp[] {
+ simProperty1,
+ new MathBOp(origProperty1, new Constant<Integer>(
+ 120), PLUS) }, NV.asMap(new NV[] { new NV(
+ OP, LT) })), //
+ new MyCompareOp(new BOp[] {
+ simProperty1,
+ new MathBOp(origProperty1, new Constant<Integer>(120),
+ MINUS) }, NV.asMap(new NV[] { new NV(OP, GT) }))//
+ ));
+
+ /**
+ * FILTER (?simProperty2 < (?origProperty2 + 170) && ?simProperty2 >
+ * (?origProperty2 - 170))
+ * <p>
+ * Note: The AND in the compound filters is typically optimized out such
+ * that each of these is represented as its own IConstraint, but I have
+ * combined them for the purposes of these unit tests.
+ */
+ final IConstraint c2 = Constraint.wrap(new AND(//
+ new MyCompareOp(
+ new BOp[] {
+ simProperty2,
+ new MathBOp(origProperty2, new Constant<Integer>(
+ 170), PLUS) }, NV.asMap(new NV[] { new NV(
+ OP, LT) })),//
+ new MyCompareOp(new BOp[] {
+ simProperty2,
+ new MathBOp(origProperty2, new Constant<Integer>(170),
+ MINUS) }, NV.asMap(new NV[] { new NV(OP, GT) }))//
+ ));
+
+ /** The constraints on the join graph. */
+ final IConstraint[] constraints = new IConstraint[] { c0, c1, c2 };
+
+ /**
+ * Unit test for one-step joins based on the {@link #product} variable.
+ */
+ public void test_canJoinUsingConstraints_1step_productVar() {
+
+ // share ?product
+ final IPredicate<?>[] a = new IPredicate[] { p0, p2, p4, p6 };
+ for (int i = 0; i < a.length; i++) {
+ for (int j = i; j < a.length; j++) {
+ final IPredicate<?> t0 = a[i];
+ final IPredicate<?> t1 = a[j];
+ assertTrue(PartitionedJoinGroup.canJoin(t0, t1));
+ assertTrue(PartitionedJoinGroup.canJoin(t1, t0));
+ if (t0 != t1) {
+ /*
+ * Test join path extension, but not when the vertex used to
+ * extend the path is already present in the join path.
+ */
+ assertTrue(PartitionedJoinGroup.canJoinUsingConstraints(//
+ new IPredicate[] { t0 }, // path
+ t1,// vertex
+ new IConstraint[0]// constraints
+ ));
+ assertTrue(PartitionedJoinGroup.canJoinUsingConstraints(//
+ new IPredicate[] { t1 }, // path
+ t0,// vertex
+ new IConstraint[0]// constraints
+ ));
+ }
+ }
+ }
+
+ }
+
+ /**
+ * Unit test for multi-step join paths based on the {@link #product}
+ * variable.
+ */
+ public void test_canJoinUsingConstraints_multiStep_productVar() {
+
+ final Random r = new Random();
+
+ // share ?product
+ final IPredicate<?>[] a = new IPredicate[] { p0, p2, p4, p6 };
+
+ // existing path length [1:3].
+ final int existingPathLength = r.nextInt(3)+1;
+
+ // generated pre-existing path.
+ final IPredicate<?>[] path = new IPredicate[existingPathLength];
+ // vertex which will extend that path
+ final IPredicate<?> vertex;
+ {
+ // collection of predicates used so far by the path.
+ final Set<Integer> used = new LinkedHashSet<Integer>();
+ for (int i = 0; i < path.length; i++) {
+ // Locate an unused predicate.
+ int index;
+ while (true) {
+ index = r.nextInt(a.length);
+ if (!used.contains(index)) {
+ used.add(index);
+ break;
+ }
+ }
+ // add to the path.
+ path[i] = a[index];
+ }
+ // Locate an unused predicate to serve as the extension vertex.
+ {
+ // Locate an unused predicate.
+ int index;
+ while (true) {
+ index = r.nextInt(a.length);
+ if (!used.contains(index)) {
+ used.add(index);
+ break;
+ }
+ }
+ vertex = a[index];
+ }
+ }
+
+ // Verify all joins in the path are legal.
+ for (int i = 0; i < path.length - 1; i++) {
+ assertTrue(PartitionedJoinGroup.canJoin(path[i], path[i + 1]));
+ }
+
+ // Verify the extension of the path is legal.
+ assertTrue(PartitionedJoinGroup.canJoinUsingConstraints(//
+ path,//
+ vertex,//
+ new IConstraint[0]// constraints
+ ));
+
+ }
+
+ /**
+ * Unit test examines the predicates without shared variables and verifies
+ * (a) that joins are not permitted when the constraints are not considered;
+ * and (b) that joins are permitted when the constraints are considered.
+ * <p>
+ * This test is identical to {@link #test_canJoinUsingConstraints_p5_p6()()}
+ * except that it considers the ({@link #p3} x {@link #p4}) join via the
+ * {@link #c1} constraint instead.
+ */
+ public void test_canJoinUsingConstraints_p3_p4() {
+
+ /*
+ * Verify (p3,p4) join is not permitted when we do not consider the
+ * constraints (i.e., the join would be an unconstrained cross product
+ * if it were executed).
+ */
+ assertFalse(PartitionedJoinGroup.canJoin(p3, p4));
+ assertFalse(PartitionedJoinGroup.canJoin(p4, p3));
+ assertFalse(PartitionedJoinGroup.canJoinUsingConstraints(//
+ new IPredicate[] { p3 }, // path
+ p4,// vertex
+ new IConstraint[0]// constraints
+ ));
+ assertFalse(PartitionedJoinGroup.canJoinUsingConstraints(//
+ new IPredicate[] { p4 }, // path
+ p3,// vertex
+ new IConstraint[0]// constraints
+ ));
+
+ /*
+ * Verify (p3,p4) join is not permitted if we do not consider the
+ * constraint which provides the shared variables.
+ */
+ assertFalse(PartitionedJoinGroup.canJoinUsingConstraints(//
+ new IPredicate[] { p3 }, // path
+ p4,// vertex
+ new IConstraint[] { c2 }// constraints
+ ));
+ assertFalse(PartitionedJoinGroup.canJoinUsingConstraints(//
+ new IPredicate[] { p4 }, // path
+ p3,// vertex
+ new IConstraint[] { c2 }// constraints
+ ));
+
+ /*
+ * Verify (p3,p4) join is permitted if we consider the constraint which
+ * provides the shared variables.
+ */
+ assertTrue(PartitionedJoinGroup.canJoinUsingConstraints(//
+ new IPredicate[] { p3 }, // path
+ p4,// vertex
+ new IConstraint[] { c1 }// constraints
+ ));
+ assertTrue(PartitionedJoinGroup.canJoinUsingConstraints(//
+ new IPredicate[] { p4 }, // path
+ p3,// vertex
+ new IConstraint[] { c1 }// constraints
+ ));
+
+ }
+
+ /**
+ * Unit test examines the predicates without shared variables and verifies
+ * (a) that joins are not permitted when the constraints are not considered;
+ * and (b) that joins are permitted wh...
[truncated message content] |
