Menu
▾
▴
[Bigdata-commit] SF.net SVN: bigdata:[4152] branches/QUADS_QUERY_BRANCH/bigdata
|
From: <tho...@us...> - 2011-01-21 00:17:25
|
Revision: 4152
http://bigdata.svn.sourceforge.net/bigdata/?rev=4152&view=rev
Author: thompsonbry
Date: 2011-01-21 00:17:18 +0000 (Fri, 21 Jan 2011)
Log Message:
-----------
Added method to return an int[] of the ids for predicates to BOpUtility.
Added method to return the set of constraints attached to the last join in a join path to PartitionedJoinGroup and (a few) unit tests for that method.
Modified BOpBase#toString() to write out everything if an operand is an IValueExpression for better printing of bops.
Modified the QUADS mode SAIL proxy test suites to invoke the TestNestedOptionals and TestNestedUnions test suites.
Modified Paths:
--------------
branches/QUADS_QUERY_BRANCH/bigdata/src/java/com/bigdata/bop/BOpBase.java
branches/QUADS_QUERY_BRANCH/bigdata/src/java/com/bigdata/bop/BOpUtility.java
branches/QUADS_QUERY_BRANCH/bigdata/src/java/com/bigdata/bop/controller/PartitionedJoinGroup.java
branches/QUADS_QUERY_BRANCH/bigdata/src/test/com/bigdata/bop/controller/TestPartitionedJoinGroup.java
branches/QUADS_QUERY_BRANCH/bigdata/src/test/com/bigdata/bop/join/TestPipelineJoin.java
branches/QUADS_QUERY_BRANCH/bigdata-sails/src/test/com/bigdata/rdf/sail/TestBigdataSailEmbeddedFederationWithQuads.java
branches/QUADS_QUERY_BRANCH/bigdata-sails/src/test/com/bigdata/rdf/sail/TestBigdataSailWithQuads.java
branches/QUADS_QUERY_BRANCH/bigdata-sails/src/test/com/bigdata/rdf/sail/TestBigdataSailWithQuadsWithoutInlining.java
branches/QUADS_QUERY_BRANCH/bigdata-sails/src/test/com/bigdata/rdf/sail/TestNestedOptionals.java
branches/QUADS_QUERY_BRANCH/bigdata-sails/src/test/com/bigdata/rdf/sail/TestNestedUnions.java
Modified: branches/QUADS_QUERY_BRANCH/bigdata/src/java/com/bigdata/bop/BOpBase.java
===================================================================
--- branches/QUADS_QUERY_BRANCH/bigdata/src/java/com/bigdata/bop/BOpBase.java 2011-01-20 23:25:24 UTC (rev 4151)
+++ branches/QUADS_QUERY_BRANCH/bigdata/src/java/com/bigdata/bop/BOpBase.java 2011-01-21 00:17:18 UTC (rev 4152)
@@ -566,10 +566,14 @@
for (BOp t : args) {
if (nwritten > 0)
sb.append(',');
- sb.append(t.getClass().getSimpleName());
- final Integer tid = (Integer) t.getProperty(Annotations.BOP_ID);
- if (tid != null) {
- sb.append("[" + tid + "]");
+ if(t instanceof IValueExpression<?>) {
+ sb.append(t.toString());
+ } else {
+ sb.append(t.getClass().getSimpleName());
+ final Integer tid = (Integer) t.getProperty(Annotations.BOP_ID);
+ if (tid != null) {
+ sb.append("[" + tid + "]");
+ }
}
nwritten++;
}
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-01-20 23:25:24 UTC (rev 4151)
+++ branches/QUADS_QUERY_BRANCH/bigdata/src/java/com/bigdata/bop/BOpUtility.java 2011-01-21 00:17:18 UTC (rev 4152)
@@ -1022,6 +1022,37 @@
return out;
}
-
+
+ /**
+ * Return an ordered array of the bopIds associated with an ordered array of
+ * predicates (aka a join path).
+ *
+ * @param path
+ * A join path.
+ *
+ * @return The ordered array of predicates for that join path.
+ *
+ * @throws IllegalArgumentException
+ * if the argument is <code>null</code>.
+ * @throws IllegalArgumentException
+ * if any element of the argument is <code>null</code>.
+ * @throws IllegalStateException
+ * if any {@link IPredicate} does not have a defined bopId as
+ * reported by {@link BOp#getId()}.
+ */
+ public static int[] getPredIds(final IPredicate<?>[] path) {
+
+ final int[] b = new int[path.length];
+
+ for (int i = 0; i < path.length; i++) {
+
+ b[i] = path[i].getId();
+
+ }
+
+ return b;
+
+ }
+
}
Modified: branches/QUADS_QUERY_BRANCH/bigdata/src/java/com/bigdata/bop/controller/PartitionedJoinGroup.java
===================================================================
--- branches/QUADS_QUERY_BRANCH/bigdata/src/java/com/bigdata/bop/controller/PartitionedJoinGroup.java 2011-01-20 23:25:24 UTC (rev 4151)
+++ branches/QUADS_QUERY_BRANCH/bigdata/src/java/com/bigdata/bop/controller/PartitionedJoinGroup.java 2011-01-21 00:17:18 UTC (rev 4152)
@@ -8,6 +8,8 @@
import java.util.Map;
import java.util.Set;
+import org.apache.log4j.Logger;
+
import com.bigdata.bop.BOpUtility;
import com.bigdata.bop.IConstraint;
import com.bigdata.bop.IPredicate;
@@ -65,6 +67,9 @@
*/
public class PartitionedJoinGroup {
+ private static final transient Logger log = Logger
+ .getLogger(PartitionedJoinGroup.class);
+
/**
* The set of variables bound by the non-optional predicates.
*/
@@ -139,6 +144,206 @@
}
/**
+ * Return the set of constraints which should be attached to the last join
+ * in the given the join path. All joins in the join path must be
+ * non-optional joins (that is, part of either the head plan or the join
+ * graph).
+ * <p>
+ * The rule followed by this method is that each constraint will be attached
+ * to the first non-optional join at which all of its variables are known to
+ * be bound. It is assumed that constraints are attached to each join in the
+ * join path by a consistent logic, e.g., as dictated by this method.
+ *
+ * @param joinPath
+ * An ordered array of predicate identifiers representing a
+ * specific sequence of non-optional joins.
+ *
+ * @return The constraints which should be attached to the last join in the
+ * join path.
+ *
+ * @throws IllegalArgumentException
+ * if the join path is <code>null</code>.
+ * @throws IllegalArgumentException
+ * if the join path is empty.
+ * @throws IllegalArgumentException
+ * if any element of the join path is <code>null</code>.
+ * @throws IllegalArgumentException
+ * if any predicate specified in the join path is not known to
+ * this class.
+ * @throws IllegalArgumentException
+ * if any predicate specified in the join path is optional.
+ *
+ * FIXME implement and unit tests.
+ *
+ * @todo Implement (or refactor) the logic to decide which variables need to
+ * be propagated and which can be dropped. This decision logic will
+ * need to be available to the runtime query optimizer.
+ *
+ * @todo This does not pay attention to the head plan. If there can be
+ * constraints on the head plan then either this should be modified
+ * such that it can decide where they attach or we need to have a
+ * method which does the same thing for the head plan.
+ */
+ public IConstraint[] getJoinGraphConstraints(final int[] pathIds) {
+
+ /*
+ * Verify arguments and resolve bopIds to predicates.
+ */
+ if (pathIds == null)
+ throw new IllegalArgumentException();
+
+ final IPredicate<?>[] path = new IPredicate[pathIds.length];
+
+ for (int i = 0; i < pathIds.length; i++) {
+
+ final int id = pathIds[i];
+
+ IPredicate<?> p = null;
+
+ for (IPredicate<?> tmp : joinGraph) {
+
+ if (tmp.getId() == id) {
+
+ p = tmp;
+
+ break;
+
+ }
+
+ }
+
+ if (p == null)
+ throw new IllegalArgumentException("Not found: id=" + id);
+
+ if (p.isOptional())
+ throw new AssertionError(
+ "Not expecting an optional predicate: " + p);
+
+ path[i] = p;
+
+ }
+
+ /*
+ * For each predicate in the path in the given order, figure out which
+ * constraint(s) would attach to that predicate based on which variables
+ * first become bound with that predicate. For the last predicate in the
+ * given join path, we return that set of constraints.
+ */
+
+ // the set of variables which are bound.
+ final Set<IVariable<?>> boundVars = new LinkedHashSet<IVariable<?>>();
+
+ // the set of constraints which have been consumed.
+ final Set<IConstraint> used = new LinkedHashSet<IConstraint>();
+
+ // the set of constraints for the last predicate in the join path.
+ final List<IConstraint> ret = new LinkedList<IConstraint>();
+
+ for(int i = 0; i<path.length; i++) {
+
+ // true iff this is the last join in the path.
+ final boolean lastJoin = i == path.length - 1;
+
+ // a predicate in the path.
+ final IPredicate<?> p = path[i];
+
+ {
+ /*
+ * Visit the variables used by the predicate (and bound by it
+ * since it is not an optional predicate) and add them into the
+ * total set of variables which are bound at this point in the
+ * join path.
+ */
+ final Iterator<IVariable<?>> vitr = BOpUtility
+ .getArgumentVariables(p);
+
+ while (vitr.hasNext()) {
+
+ final IVariable<?> var = vitr.next();
+
+ boundVars.add(var);
+
+ }
+ }
+
+ // consider each constraint.
+ for(IConstraint c : joinGraphConstraints) {
+
+ if (used.contains(c)) {
+ /*
+ * Skip constraints which were already assigned to
+ * predicates before this one in the join path.
+ */
+ continue;
+ }
+
+ /*
+ * true iff all variables used by this constraint are bound at
+ * this point in the join path.
+ */
+ boolean allVarsBound = true;
+
+ // visit the variables used by this constraint.
+ final Iterator<IVariable<?>> vitr = BOpUtility
+ .getSpannedVariables(c);
+
+ while (vitr.hasNext()) {
+
+ final IVariable<?> var = vitr.next();
+
+ if(!boundVars.contains(var)) {
+
+ allVarsBound = false;
+
+ break;
+
+ }
+
+ }
+
+ if (allVarsBound) {
+
+ /*
+ * All variables have become bound for this constraint, so
+ * add it to the set of "used" constraints.
+ */
+
+ used.add(c);
+
+// if (log.isDebugEnabled()) {
+// log.debug
+// }
+ System.err.println("Constraint attached at index " + i + " of "
+ + path.length + ", bopId=" + p.getId()
+ + ", constraint=" + c);
+
+ if (lastJoin) {
+
+ /*
+ * If we are on the last join in the join path, then
+ * this constraint is one of the ones that we will
+ * return.
+ */
+
+ ret.add(c);
+
+ }
+
+ } // if(allVarsBound)
+
+ } // next constraint
+
+ } // next predicate in the join path.
+
+ /*
+ * Return the set of constraints to be applied as of the last predicate
+ * in the join path.
+ */
+ return ret.toArray(new IConstraint[ret.size()]);
+
+ }
+
+ /**
* The {@link IPredicate}s representing optional joins. Any
* {@link IConstraint}s having variable(s) NOT bound by the required joins
* will already have been attached to the last {@link IPredicate} in the
Modified: branches/QUADS_QUERY_BRANCH/bigdata/src/test/com/bigdata/bop/controller/TestPartitionedJoinGroup.java
===================================================================
--- branches/QUADS_QUERY_BRANCH/bigdata/src/test/com/bigdata/bop/controller/TestPartitionedJoinGroup.java 2011-01-20 23:25:24 UTC (rev 4151)
+++ branches/QUADS_QUERY_BRANCH/bigdata/src/test/com/bigdata/bop/controller/TestPartitionedJoinGroup.java 2011-01-21 00:17:18 UTC (rev 4152)
@@ -231,6 +231,40 @@
assertSameIteratorAnyOrder("joinGraphConstraints", constraints,
Arrays.asList(fixture.getJoinGraphConstraints()).iterator());
+ /*
+ * Verify the placement of each constraint for a variety of join
+ * paths.
+ */
+ {
+// final int[] pathIds = BOpUtility.getPredIds(new IPredicate[] {
+// p0, p1, p2, p3, p4, p5 });
+// final IConstraint[] actual = fixture
+// .getJoinGraphConstraints(pathIds);
+// System.out.println(Arrays.toString(actual));
+
+ // c1 is applied when x is bound. x is bound by p0.
+ assertEquals(new IConstraint[] { c1 }, fixture
+ .getJoinGraphConstraints(new int[] { p1.getId(),
+ p0.getId() }));
+
+ /*
+ * c1 is applied when x is bound. x is bound by p0. p0 is the
+ * last predicate in this join path, so c1 is attached to p0.
+ */
+ assertEquals(new IConstraint[] { c1 }, fixture
+ .getJoinGraphConstraints(new int[] { p0.getId()}));
+
+ /*
+ * c2 is applied when y is bound. y is bound by p1. p1 is the
+ * last predicate in this join path, p1 is the last predicate in
+ * this join path so c2 is attached to p1.
+ */
+ assertEquals(new IConstraint[] { c2 }, fixture
+ .getJoinGraphConstraints(new int[] { p0.getId(),
+ p1.getId() }));
+
+ }
+
// there is no tail plan.
assertEquals("tailPlan", new IPredicate[] {}, fixture.getTailPlan());
Modified: branches/QUADS_QUERY_BRANCH/bigdata/src/test/com/bigdata/bop/join/TestPipelineJoin.java
===================================================================
--- branches/QUADS_QUERY_BRANCH/bigdata/src/test/com/bigdata/bop/join/TestPipelineJoin.java 2011-01-20 23:25:24 UTC (rev 4151)
+++ branches/QUADS_QUERY_BRANCH/bigdata/src/test/com/bigdata/bop/join/TestPipelineJoin.java 2011-01-21 00:17:18 UTC (rev 4152)
@@ -68,10 +68,23 @@
/**
* Unit tests for the {@link PipelineJoin} operator.
* <p>
- * Note: The operators to map binding sets over shards are tested independently.
+ * Note: The logic to map binding sets over shards is tested independently.
*
* @author <a href="mailto:tho...@us...">Bryan Thompson</a>
* @version $Id$
+ *
+ * FIXME This test suite does not fully test the FILTER semantics for
+ * SPARQL joins. In particular, (a) optional join solutions are counted
+ * as successful <em>before</em> the FILTER is applied; and (b) if no
+ * optional join solutions exist (before filtering) for a given source
+ * binding set, then the FILTER is applied to the source binding set to
+ * decide whether or not the source solutions should be passed along.
+ * That is, the behavior is the same in both cases as if the FILTER as
+ * applied after the optional join. However, in fact, we apply it as
+ * part of the join operator in order to keep things simpler for the
+ * runtime query optimizer, which needs to be able to perform cutoff
+ * joins and which also needs to be able to reorder the predicates,
+ * creating the appropriate join operators as it does so.
*/
public class TestPipelineJoin extends TestCase2 {
Modified: branches/QUADS_QUERY_BRANCH/bigdata-sails/src/test/com/bigdata/rdf/sail/TestBigdataSailEmbeddedFederationWithQuads.java
===================================================================
--- branches/QUADS_QUERY_BRANCH/bigdata-sails/src/test/com/bigdata/rdf/sail/TestBigdataSailEmbeddedFederationWithQuads.java 2011-01-20 23:25:24 UTC (rev 4151)
+++ branches/QUADS_QUERY_BRANCH/bigdata-sails/src/test/com/bigdata/rdf/sail/TestBigdataSailEmbeddedFederationWithQuads.java 2011-01-21 00:17:18 UTC (rev 4152)
@@ -97,6 +97,10 @@
// test suite for optionals handling (left joins).
suite.addTestSuite(TestOptionals.class);
+ suite.addTestSuite(TestNestedOptionals.class);
+
+ suite.addTestSuite(TestNestedUnions.class);
+
// test of the search magic predicate
suite.addTestSuite(TestSearchQuery.class);
Modified: branches/QUADS_QUERY_BRANCH/bigdata-sails/src/test/com/bigdata/rdf/sail/TestBigdataSailWithQuads.java
===================================================================
--- branches/QUADS_QUERY_BRANCH/bigdata-sails/src/test/com/bigdata/rdf/sail/TestBigdataSailWithQuads.java 2011-01-20 23:25:24 UTC (rev 4151)
+++ branches/QUADS_QUERY_BRANCH/bigdata-sails/src/test/com/bigdata/rdf/sail/TestBigdataSailWithQuads.java 2011-01-21 00:17:18 UTC (rev 4152)
@@ -79,6 +79,10 @@
// test suite for optionals handling (left joins).
suite.addTestSuite(TestOptionals.class);
+ suite.addTestSuite(TestNestedOptionals.class);
+
+ suite.addTestSuite(TestNestedUnions.class);
+
// test of the search magic predicate
suite.addTestSuite(TestSearchQuery.class);
Modified: branches/QUADS_QUERY_BRANCH/bigdata-sails/src/test/com/bigdata/rdf/sail/TestBigdataSailWithQuadsWithoutInlining.java
===================================================================
--- branches/QUADS_QUERY_BRANCH/bigdata-sails/src/test/com/bigdata/rdf/sail/TestBigdataSailWithQuadsWithoutInlining.java 2011-01-20 23:25:24 UTC (rev 4151)
+++ branches/QUADS_QUERY_BRANCH/bigdata-sails/src/test/com/bigdata/rdf/sail/TestBigdataSailWithQuadsWithoutInlining.java 2011-01-21 00:17:18 UTC (rev 4152)
@@ -81,6 +81,10 @@
// test suite for optionals handling (left joins).
suite.addTestSuite(TestOptionals.class);
+ suite.addTestSuite(TestNestedOptionals.class);
+
+ suite.addTestSuite(TestNestedUnions.class);
+
// test of the search magic predicate
suite.addTestSuite(TestSearchQuery.class);
Modified: branches/QUADS_QUERY_BRANCH/bigdata-sails/src/test/com/bigdata/rdf/sail/TestNestedOptionals.java
===================================================================
--- branches/QUADS_QUERY_BRANCH/bigdata-sails/src/test/com/bigdata/rdf/sail/TestNestedOptionals.java 2011-01-20 23:25:24 UTC (rev 4151)
+++ branches/QUADS_QUERY_BRANCH/bigdata-sails/src/test/com/bigdata/rdf/sail/TestNestedOptionals.java 2011-01-21 00:17:18 UTC (rev 4152)
@@ -69,7 +69,7 @@
* @author <a href="mailto:mrp...@us...">Mike Personick</a>
* @version $Id$
*/
-public class TestNestedOptionals extends ProxyBigdataSailTestCase {
+public class TestNestedOptionals extends QuadsTestCase {
/*
* TODO
Modified: branches/QUADS_QUERY_BRANCH/bigdata-sails/src/test/com/bigdata/rdf/sail/TestNestedUnions.java
===================================================================
--- branches/QUADS_QUERY_BRANCH/bigdata-sails/src/test/com/bigdata/rdf/sail/TestNestedUnions.java 2011-01-20 23:25:24 UTC (rev 4151)
+++ branches/QUADS_QUERY_BRANCH/bigdata-sails/src/test/com/bigdata/rdf/sail/TestNestedUnions.java 2011-01-21 00:17:18 UTC (rev 4152)
@@ -69,7 +69,7 @@
* @author <a href="mailto:mrp...@us...">Mike Personick</a>
* @version $Id$
*/
-public class TestNestedUnions extends ProxyBigdataSailTestCase {
+public class TestNestedUnions extends QuadsTestCase {
/*
* TODO
This was sent by the SourceForge.net collaborative development platform, the world's largest Open Source development site.
|
