Menu
▾
▴
[Bigdata-commit] SF.net SVN: bigdata:[4039] branches/QUADS_QUERY_BRANCH/bigdata/src
|
From: <tho...@us...> - 2010-12-21 23:07:15
|
Revision: 4039
http://bigdata.svn.sourceforge.net/bigdata/?rev=4039&view=rev
Author: thompsonbry
Date: 2010-12-21 23:07:08 +0000 (Tue, 21 Dec 2010)
Log Message:
-----------
Modified the QueryEngine (in RunningQuery) to support push/pop of binding sets when transitioning into or out of a conditional join group. I've updated the first of the unit tests developed by MikeP to show how to annotate the query plan in order to trigger the conditional binding mechanisms. It is clear that the conditional binding is working (solutions where the 3rd join fail discard the results from the 2nd join), but the query plan is overgenerating.
Modified Paths:
--------------
branches/QUADS_QUERY_BRANCH/bigdata/src/java/com/bigdata/bop/BOpContext.java
branches/QUADS_QUERY_BRANCH/bigdata/src/java/com/bigdata/bop/BOpUtility.java
branches/QUADS_QUERY_BRANCH/bigdata/src/java/com/bigdata/bop/PipelineOp.java
branches/QUADS_QUERY_BRANCH/bigdata/src/java/com/bigdata/bop/engine/RunningQuery.java
branches/QUADS_QUERY_BRANCH/bigdata/src/java/com/bigdata/bop/join/PipelineJoin.java
branches/QUADS_QUERY_BRANCH/bigdata/src/test/com/bigdata/bop/TestBOpUtility.java
branches/QUADS_QUERY_BRANCH/bigdata/src/test/com/bigdata/bop/engine/TestQueryEngineOptionalJoins.java
Added Paths:
-----------
branches/QUADS_QUERY_BRANCH/bigdata/src/java/com/bigdata/bop/BadConditionalGroupIdTypeException.java
Modified: branches/QUADS_QUERY_BRANCH/bigdata/src/java/com/bigdata/bop/BOpContext.java
===================================================================
--- branches/QUADS_QUERY_BRANCH/bigdata/src/java/com/bigdata/bop/BOpContext.java 2010-12-21 22:21:54 UTC (rev 4038)
+++ branches/QUADS_QUERY_BRANCH/bigdata/src/java/com/bigdata/bop/BOpContext.java 2010-12-21 23:07:08 UTC (rev 4039)
@@ -131,6 +131,7 @@
* join group.
*
* @see PipelineOp.Annotations#ALT_SINK_REF
+ * @see PipelineOp.Annotations#ALT_SINK_GROUP
*/
public final IBlockingBuffer<E[]> getSink2() {
return sink2;
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 2010-12-21 22:21:54 UTC (rev 4038)
+++ branches/QUADS_QUERY_BRANCH/bigdata/src/java/com/bigdata/bop/BOpUtility.java 2010-12-21 23:07:08 UTC (rev 4039)
@@ -426,6 +426,57 @@
}
/**
+ * Lookup the first operator in the specified conditional binding group and
+ * return its bopId.
+ *
+ * @param query
+ * The query plan.
+ * @param groupId
+ * The identifier for the desired conditional binding group.
+ *
+ * @return The bopId of the first operator in that conditional binding group
+ * -or- <code>null</code> if the specified conditional binding group
+ * does not exist in the query plan.
+ *
+ * @throws IllegalArgumentException
+ * if either argument is <code>null</code>.
+ *
+ * @see PipelineOp.Annotations#CONDITIONAL_GROUP
+ * @see PipelineOp.Annotations#ALT_SINK_GROUP
+ */
+ static public Integer getFirstBOpIdForConditionalGroup(final BOp query,
+ final Integer groupId) {
+ if (query == null)
+ throw new IllegalArgumentException();
+ if (groupId == null)
+ throw new IllegalArgumentException();
+ final Iterator<BOp> itr = postOrderIterator(query);
+ while (itr.hasNext()) {
+ final BOp t = itr.next();
+ final Object x = t.getProperty(PipelineOp.Annotations.CONDITIONAL_GROUP);
+ if (x != null) {
+ if (!(x instanceof Integer)) {
+ throw new BadConditionalGroupIdTypeException(
+ "Must be Integer, not: " + x.getClass() + ": "
+ + PipelineOp.Annotations.CONDITIONAL_GROUP);
+ }
+ final Integer id = (Integer) t
+ .getProperty(PipelineOp.Annotations.CONDITIONAL_GROUP);
+ if(id.equals(groupId)) {
+ /*
+ * Return the BOpId associated with the first operator in
+ * the pre-order traversal of the query plan which has the
+ * specified groupId.
+ */
+ return t.getId();
+ }
+ }
+ }
+ // No such groupId in the query plan.
+ return null;
+ }
+
+ /**
* Return the parent of the operator in the operator tree (this does not
* search the annotations, just the children).
* <p>
Added: branches/QUADS_QUERY_BRANCH/bigdata/src/java/com/bigdata/bop/BadConditionalGroupIdTypeException.java
===================================================================
--- branches/QUADS_QUERY_BRANCH/bigdata/src/java/com/bigdata/bop/BadConditionalGroupIdTypeException.java (rev 0)
+++ branches/QUADS_QUERY_BRANCH/bigdata/src/java/com/bigdata/bop/BadConditionalGroupIdTypeException.java 2010-12-21 23:07:08 UTC (rev 4039)
@@ -0,0 +1,22 @@
+package com.bigdata.bop;
+
+/**
+ * Exception thrown when a {@link PipelineOp.Annotations#CONDITIONAL_GROUP} is
+ * not an {@link Integer}.
+ *
+ * @author <a href="mailto:tho...@us...">Bryan Thompson</a>
+ * @version $Id: BadBOpIdTypeException.java 3466 2010-08-27 14:28:04Z
+ * thompsonbry $
+ */
+public class BadConditionalGroupIdTypeException extends RuntimeException {
+
+ /**
+ * @param msg
+ */
+ public BadConditionalGroupIdTypeException(String msg) {
+ super(msg);
+ }
+
+ private static final long serialVersionUID = 1L;
+
+}
Property changes on: branches/QUADS_QUERY_BRANCH/bigdata/src/java/com/bigdata/bop/BadConditionalGroupIdTypeException.java
___________________________________________________________________
Added: svn:keywords
+ Id Date Revision Author HeadURL
Modified: branches/QUADS_QUERY_BRANCH/bigdata/src/java/com/bigdata/bop/PipelineOp.java
===================================================================
--- branches/QUADS_QUERY_BRANCH/bigdata/src/java/com/bigdata/bop/PipelineOp.java 2010-12-21 22:21:54 UTC (rev 4038)
+++ branches/QUADS_QUERY_BRANCH/bigdata/src/java/com/bigdata/bop/PipelineOp.java 2010-12-21 23:07:08 UTC (rev 4039)
@@ -33,10 +33,18 @@
import com.bigdata.bop.engine.BOpStats;
import com.bigdata.bop.engine.QueryEngine;
+import com.bigdata.bop.solutions.SliceOp;
/**
* Abstract base class for pipeline operators where the data moving along the
* pipeline is chunks of {@link IBindingSet}s.
+ * <p>
+ * The top-level of a query plan is composed of a required
+ * {@link Annotations#JOIN_GRAPH}s followed by a mixture of optional joins and
+ * {@link Annotations#CONDITIONAL_GROUP}s. A
+ * {@link Annotations#CONDITIONAL_GROUP} will have at least one required join
+ * (in a {@link Annotations#JOIN_GRAPH}) followed by zero or more optional
+ * joins.
*
* @author <a href="mailto:tho...@us...">Bryan Thompson</a>
* @version $Id$
@@ -61,6 +69,8 @@
* The value of the annotation is the {@link BOp.Annotations#BOP_ID} of
* the ancestor in the operator tree which serves as the alternative
* sink for binding sets (default is no alternative sink).
+ *
+ * @see #ALT_SINK_GROUP
*/
String ALT_SINK_REF = PipelineOp.class.getName()
+ ".altSinkRef";
@@ -82,46 +92,73 @@
boolean DEFAULT_SHARED_STATE = false;
- /**
- * Annotation used to mark the set of non-optional joins which may be
- * input to either the static or runtime query optimizer. Joins within a
- * join graph may be freely reordered by the query optimizer in order to
- * minimize the amount of work required to compute the solutions.
- * <p>
- * Note: Optional joins MAY NOT appear within the a join graph. Optional
- * joins SHOULD be evaluated as part of the "tail plan" following the
- * join graph, but before operations such as SORT, DISTINCT, etc.
- *
- * @todo We should be able to automatically apply the static or runtime
- * query optimizers to an operator tree using this annotation to
- * identify the join graphs.
- */
+ /**
+ * Annotation used to mark a set of (non-optional) joins which may be
+ * freely reordered by the query optimizer in order to minimize the
+ * amount of work required to compute the solutions.
+ * <p>
+ * Note: Optional joins MAY NOT appear within a join graph. Optional
+ * joins SHOULD be evaluated as part of the "tail plan" following the
+ * join graph, but before operations such as SORT, DISTINCT, etc. When
+ * the query plan includes {@link #CONDITIONAL_GROUP}s, those groups
+ * include a leading {@link #JOIN_GRAPH} (required joins) followed by
+ * zero or more optional joins.
+ */
String JOIN_GRAPH = PipelineOp.class.getName() + ".joinGraph";
- /**
- * Annotation marks a high level join group, which may include optional
- * joins. Join groups are marked in order to decide the re-entry point
- * in the query plan when a join within an optional join group fails.
- * Also, the top-level join group is not marked -- only nested join
- * groups are marked. This is used by the decision rule to handle do
- * {@link IBindingSet#push()} when entering a
- * <p>
- * This is different from a {@link #JOIN_GRAPH} primarily in that the
- * latter may not include optional joins.
- */
- String JOIN_GROUP = PipelineOp.class.getName() + ".joinGroup";
+ /**
+ * Annotation used to mark a set of operators belonging to a conditional
+ * binding group. Bindings within with the group will be discarded if
+ * any required operator in the group fails. For example, if a binding
+ * set exits via the alternative sink for a required join then any
+ * conditional bindings within the group will be discarded.
+ * <p>
+ * Together with {@link #ALT_SINK_GROUP}, the {@link #CONDITIONAL_GROUP}
+ * annotation provides the information necessary in order to decide the
+ * re-entry point in the query plan when a join within an conditional
+ * binding group fails.
+ * <p>
+ * The {@link #CONDITIONAL_GROUP} annotation controls the
+ * {@link IBindingSet#push()} and {@link IBindingSet#pop(boolean)} of
+ * individual solutions as they propagate through the pipeline. When a
+ * pipeline starts, the {@link IBindingSet} stack contains only the top
+ * level symbol table (i.e., name/value bindings). When an intermediate
+ * solution enters a {@link PipelineOp} marked as belonging to a
+ * {@link #CONDITIONAL_GROUP}, a new symbol table is
+ * {@link IBindingSet#push() pushed} onto the stack for that solution.
+ * If the solution leaves the optional join group via the default sink,
+ * then the symbol table is "saved" when it is
+ * {@link IBindingSet#pop(boolean) popped} off of the stack. If the
+ * solution leaves the join group via the alternative sink, then the
+ * symbol table is discarded when it is {@link IBindingSet#pop(boolean)
+ * popped} off of the stack. This provides for conditional binding of
+ * variables within the operators of the group.
+ * <p>
+ * The value of the {@link #CONDITIONAL_GROUP} is an {@link Integer}
+ * which uniquely identifies the group within the query.
+ */
+ String CONDITIONAL_GROUP = PipelineOp.class.getName() + ".conditionalGroup";
- /**
- * Annotation is used to designate the target when a join within an
- * optional join group fails. The value of this annotation must be the
- * {@link #JOIN_GROUP} identifier corresponding to the next join group
- * in the query plan. The target join group identifier is specified
- * (rather than the bopId of the target join) since the joins in the
- * target join group may be reordered by the query optimizer. The entry
- * point for solutions redirected to the {@link #ALT_SINK_GROUP} is
- * therefore the first operator in the target {@link #JOIN_GROUP}. This
- * decouples the routing decisions from the join ordering decisions.
- */
+ /**
+ * Annotation used to designate the target when a required operator
+ * within an {@link #CONDITIONAL_GROUP} fails. The value of this
+ * annotation must be the {@link #CONDITIONAL_GROUP} identifier
+ * corresponding to the next conditional binding group in the query
+ * plan. If there is no such group, then the {@link #ALT_SINK_REF}
+ * should be used instead to specify the target operator in the
+ * pipeline, e.g., a {@link SliceOp}.
+ * <p>
+ * The target {@link #CONDITIONAL_GROUP} is specified (rather than the
+ * bopId of the target join) since the non-optional joins in the target
+ * {@link #CONDITIONAL_GROUP} be reordered by the query optimizer. The
+ * entry point for solutions redirected to the {@link #ALT_SINK_GROUP}
+ * is therefore the first operator in the target
+ * {@link #CONDITIONAL_GROUP}. This decouples the routing decisions from
+ * the join ordering decisions.
+ *
+ * @see #CONDITIONAL_GROUP
+ * @see #ALT_SINK_REF
+ */
String ALT_SINK_GROUP = PipelineOp.class.getName() + ".altSinkGroup";
}
Modified: branches/QUADS_QUERY_BRANCH/bigdata/src/java/com/bigdata/bop/engine/RunningQuery.java
===================================================================
--- branches/QUADS_QUERY_BRANCH/bigdata/src/java/com/bigdata/bop/engine/RunningQuery.java 2010-12-21 22:21:54 UTC (rev 4038)
+++ branches/QUADS_QUERY_BRANCH/bigdata/src/java/com/bigdata/bop/engine/RunningQuery.java 2010-12-21 23:07:08 UTC (rev 4039)
@@ -41,7 +41,6 @@
import java.util.concurrent.FutureTask;
import java.util.concurrent.LinkedBlockingQueue;
import java.util.concurrent.RejectedExecutionException;
-import java.util.concurrent.Semaphore;
import java.util.concurrent.TimeUnit;
import java.util.concurrent.TimeoutException;
import java.util.concurrent.atomic.AtomicBoolean;
@@ -1568,8 +1567,9 @@
/**
* The index of the operator which is the alternative sink for outputs
* generated by this evaluation. This is <code>null</code> unless the
- * operator explicitly specifies an alternative sink using
- * {@link PipelineOp.Annotations#ALT_SINK_REF}.
+ * operator explicitly specifies an alternative sink using either
+ * {@link PipelineOp.Annotations#ALT_SINK_REF} or
+ * {@link PipelineOp.Annotations#ALT_SINK_GROUP}.
*/
private final Integer altSinkId;
@@ -1674,9 +1674,30 @@
*/
sinkId = BOpUtility.getEffectiveDefaultSink(bop, p);
- // altSink (null when not specified).
- altSinkId = (Integer) op
- .getProperty(PipelineOp.Annotations.ALT_SINK_REF);
+ {
+ // altSink (null when not specified).
+ final Integer altSinkId = (Integer) op
+ .getProperty(PipelineOp.Annotations.ALT_SINK_REF);
+ final Integer altSinkGroup = (Integer) op
+ .getProperty(PipelineOp.Annotations.ALT_SINK_GROUP);
+ if (altSinkId != null && altSinkGroup != null)
+ throw new RuntimeException(
+ "Annotations are mutually exclusive: "
+ + PipelineOp.Annotations.ALT_SINK_REF
+ + " and "
+ + PipelineOp.Annotations.ALT_SINK_GROUP);
+ if (altSinkGroup != null) {
+ /*
+ * Lookup the first pipeline op in the conditional binding
+ * group and use its bopId as the altSinkId.
+ */
+ this.altSinkId = BOpUtility.getFirstBOpIdForConditionalGroup(
+ query, altSinkGroup);
+ } else {
+ // MAY be null.
+ this.altSinkId = altSinkId;
+ }
+ }
if (altSinkId != null && !bopIndex.containsKey(altSinkId))
throw new NoSuchBOpException(altSinkId);
@@ -1714,13 +1735,39 @@
}
assert stats != null;
- sink = (p == null ? queryBuffer : newBuffer(op, sinkId,
- sinkMessagesOut, stats));
+ // The groupId (if any) for this operator.
+ final Integer fromGroupId = (Integer) op
+ .getProperty(PipelineOp.Annotations.CONDITIONAL_GROUP);
- altSink = altSinkId == null ? null
- : altSinkId.equals(sinkId) ? sink : newBuffer(op,
- altSinkId, altSinkMessagesOut, stats);
+ if (p == null) {
+ sink = queryBuffer;
+ } else {
+ final BOp targetOp = bopIndex.get(sinkId);
+ final Integer toGroupId = (Integer) targetOp
+ .getProperty(PipelineOp.Annotations.CONDITIONAL_GROUP);
+ sink = newBuffer(op, sinkId, new SinkTransitionMetadata(
+ fromGroupId, toGroupId, true/* isSink */),
+ sinkMessagesOut, stats);
+ }
+ if (altSinkId == null) {
+ altSink = null;
+ // } else if(altSinkId.equals(sinkId)){
+ /*
+ * @todo Note: The optimization when altSink:=sink is now only
+ * possible when the groupId is not changing during the
+ * transition.
+ */
+ // altSink = sink;
+ } else {
+ final BOp targetOp = bopIndex.get(altSinkId);
+ final Integer toGroupId = (Integer) targetOp
+ .getProperty(PipelineOp.Annotations.CONDITIONAL_GROUP);
+ altSink = newBuffer(op, altSinkId, new SinkTransitionMetadata(
+ fromGroupId, toGroupId, false/* isSink */),
+ altSinkMessagesOut, stats);
+ }
+
// context : @todo pass in IChunkMessage or IChunkAccessor
context = new BOpContext<IBindingSet>(RunningQuery.this,
partitionId, stats, src, sink, altSink);
@@ -1748,7 +1795,9 @@
* target that sink.
*/
private IBlockingBuffer<IBindingSet[]> newBuffer(final PipelineOp op,
- final int sinkId, final AtomicInteger sinkMessagesOut, final BOpStats stats) {
+ final int sinkId,
+ final SinkTransitionMetadata sinkTransitionMetadata,
+ final AtomicInteger sinkMessagesOut, final BOpStats stats) {
// final MultiplexBlockingBuffer<IBindingSet[]> factory = inputBufferMap == null ? null
// : inputBufferMap.get(sinkId);
@@ -1774,7 +1823,8 @@
// BufferAnnotations.chunkTimeoutUnit);
return new HandleChunkBuffer(RunningQuery.this, bopId, sinkId, op
- .getChunkCapacity(), sinkMessagesOut, stats);
+ .getChunkCapacity(), sinkTransitionMetadata, sinkMessagesOut,
+ stats);
}
@@ -1814,7 +1864,115 @@
} // call()
} // class ChunkTask
+
+ /**
+ * In order to setup the push/pop of the sink and altSink we need to specify
+ * certain metadata about the source groupId, the target groupId, and
+ * whether the transition is via the sink or the altSink. The groupId for
+ * the source and target operators MAY be null, in which case the operator
+ * is understood to be outside of any conditional binding group.
+ * <p>
+ * The action to be taken when the binding set is written to the sink or the
+ * altSink is determined by a simple decision matrix.
+ *
+ * <pre>
+ * | toGroup
+ * fromGroup + null + newGroup + sameGroup
+ * null | NOP | Push | n/a
+ * group | Pop | Pop+Push | NOP
+ * </pre>
+ *
+ * The value of the [boolean:save] flag for pop is decided based on whether
+ * the transition is via the default sink (save:=true) or the altSink
+ * (save:=false).
+ *
+ * @see PipelineOp.Annotations#CONDITIONAL_GROUP
+ */
+ private static class SinkTransitionMetadata {
+
+ private final Integer fromGroupId;
+ private final Integer toGroupId;
+ private final boolean isSink;
+
+ public String toString() {
+
+ return getClass().getSimpleName() + "{from=" + fromGroupId + ",to="
+ + toGroupId + ",isSink=" + isSink + "}";
+
+ }
+
+ public SinkTransitionMetadata(final Integer fromGroupId,
+ final Integer toGroupId, final boolean isSink) {
+
+ this.fromGroupId = fromGroupId;
+
+ this.toGroupId = toGroupId;
+
+ this.isSink = isSink;
+
+ }
+
+ /**
+ * Apply the appropriate action(s) to the binding set.
+ *
+ * @param bset
+ * The binding set.
+ */
+ public void handleBindingSet(final IBindingSet bset) {
+ if (fromGroupId == null) {
+ if (toGroupId == null)
+ return;
+ // Transition from no group to some group.
+ bset.push();
+ return;
+ } else {
+ if (toGroupId == null)
+ // Transition from a group to no group.
+ bset.pop(isSink/* save */);
+ else if (toGroupId.equals(fromGroupId)) {
+ // NOP (transition to the same group)
+ } else {
+ // Transition to a different group.
+ bset.pop(isSink/* save */);
+ bset.push();
+ }
+ }
+ }
+
+ }
+// /**
+// * Type safe enumeration for after action on a generated binding set used to
+// * manage exit from a conditional binding group via the defaultSink and the
+// * altSink.
+// *
+// * @author <a href="mailto:tho...@us...">Bryan
+// * Thompson</a>
+// */
+// static private enum AfterActionEnum {
+// /**
+// * NOP
+// */
+// None,
+// /**
+// * Use {@link IBindingSet#pop(boolean)} to discard the symbol table on
+// * the top of the stack.
+// */
+// Discard,
+// /**
+// * Use {@link IBindingSet#pop(boolean)} to save the symbol table on the
+// * top of the stack.
+// */
+// Save,
+// /**
+// * Use {@link IBindingSet#push()} to push a symbol table on the top of
+// * the stack. Bindings made against that symbol table will be
+// * conditional until they are either {@link #Discard discarded} or
+// * {@link #Save saved}.
+// */
+// Push;
+// }
+
/**
* Class traps {@link #add(IBindingSet[])} to handle the IBindingSet[]
* chunks as they are generated by the running operator task, invoking
@@ -1841,6 +1999,8 @@
*/
private final int chunkCapacity;
+ private final SinkTransitionMetadata sinkTransitionMetadata;
+
private final AtomicInteger sinkMessagesOut;
private final BOpStats stats;
@@ -1869,11 +2029,13 @@
*/
public HandleChunkBuffer(final RunningQuery q, final int bopId,
final int sinkId, final int chunkCapacity,
+ final SinkTransitionMetadata sinkTransitionMetadata,
final AtomicInteger sinkMessagesOut, final BOpStats stats) {
this.q = q;
this.bopId = bopId;
this.sinkId = sinkId;
this.chunkCapacity = chunkCapacity;
+ this.sinkTransitionMetadata = sinkTransitionMetadata;
this.sinkMessagesOut = sinkMessagesOut;
this.stats = stats;
}
@@ -1892,6 +2054,10 @@
if(!open)
throw new BufferClosedException();
+ for (IBindingSet bset : e) {
+ sinkTransitionMetadata.handleBindingSet(bset);
+ }
+
// if (chunkCapacity != 0 && e.length < (chunkCapacity >> 1)) {
// /*
// * The caller's array is significantly smaller than the target
Modified: branches/QUADS_QUERY_BRANCH/bigdata/src/java/com/bigdata/bop/join/PipelineJoin.java
===================================================================
--- branches/QUADS_QUERY_BRANCH/bigdata/src/java/com/bigdata/bop/join/PipelineJoin.java 2010-12-21 22:21:54 UTC (rev 4038)
+++ branches/QUADS_QUERY_BRANCH/bigdata/src/java/com/bigdata/bop/join/PipelineJoin.java 2010-12-21 23:07:08 UTC (rev 4039)
@@ -137,7 +137,8 @@
/**
* Marks the join as "optional" in the SPARQL sense. Binding sets which
* fail the join will be routed to the alternative sink as specified by
- * {@link PipelineOp.Annotations#ALT_SINK_REF}.
+ * either {@link PipelineOp.Annotations#ALT_SINK_REF} or
+ * {@link PipelineOp.Annotations#ALT_SINK_GROUP}.
*
* @see #DEFAULT_OPTIONAL
*/
Modified: branches/QUADS_QUERY_BRANCH/bigdata/src/test/com/bigdata/bop/TestBOpUtility.java
===================================================================
--- branches/QUADS_QUERY_BRANCH/bigdata/src/test/com/bigdata/bop/TestBOpUtility.java 2010-12-21 22:21:54 UTC (rev 4038)
+++ branches/QUADS_QUERY_BRANCH/bigdata/src/test/com/bigdata/bop/TestBOpUtility.java 2010-12-21 23:07:08 UTC (rev 4039)
@@ -31,6 +31,14 @@
import java.util.Map;
import java.util.concurrent.FutureTask;
+import com.bigdata.bop.IPredicate.Annotations;
+import com.bigdata.bop.ap.E;
+import com.bigdata.bop.ap.Predicate;
+import com.bigdata.bop.bset.StartOp;
+import com.bigdata.bop.join.PipelineJoin;
+import com.bigdata.bop.solutions.SliceOp;
+import com.bigdata.journal.ITx;
+
import junit.framework.TestCase2;
/**
@@ -579,6 +587,120 @@
}
/**
+ * A conditional join group:
+ *
+ * <pre>
+ * (a b)
+ * optional {
+ * (b c)
+ * (c d)
+ * }
+ * </pre>
+ *
+ * where the groupId for the optional join group is ONE (1). The test should
+ * locate the first {@link PipelineJoin} in that join group, which is the
+ * one reading on the <code>(b c)</code> access path.
+ */
+ public void test_getFirstBOpIdForConditionalGroup() {
+
+ final String namespace = "kb";
+
+ final int startId = 1; //
+ final int joinId1 = 2; // : base join group.
+ final int predId1 = 3; // (a b)
+ final int joinId2 = 4; // : joinGroup1
+ final int predId2 = 5; // (b c)
+ final int joinId3 = 6; // : joinGroup1
+ final int predId3 = 7; // (c d)
+ final int sliceId = 8; //
+
+ final IVariable<?> a = Var.var("a");
+ final IVariable<?> b = Var.var("b");
+ final IVariable<?> c = Var.var("c");
+ final IVariable<?> d = Var.var("d");
+
+ final Integer joinGroup1 = Integer.valueOf(1);
+
+ final PipelineOp startOp = new StartOp(new BOp[] {},
+ NV.asMap(new NV[] {//
+ new NV(Predicate.Annotations.BOP_ID, startId),//
+ new NV(SliceOp.Annotations.EVALUATION_CONTEXT,
+ BOpEvaluationContext.CONTROLLER),//
+ }));
+
+ final Predicate<?> pred1Op = new Predicate<E>(
+ new IVariableOrConstant[] { a, b }, NV
+ .asMap(new NV[] {//
+ new NV(Predicate.Annotations.RELATION_NAME,
+ new String[] { namespace }),//
+ new NV(Predicate.Annotations.BOP_ID, predId1),//
+ new NV(Annotations.TIMESTAMP, ITx.READ_COMMITTED),//
+ }));
+
+ final Predicate<?> pred2Op = new Predicate<E>(
+ new IVariableOrConstant[] { b, c }, NV
+ .asMap(new NV[] {//
+ new NV(Predicate.Annotations.RELATION_NAME,
+ new String[] { namespace }),//
+ new NV(Predicate.Annotations.BOP_ID, predId2),//
+ new NV(Annotations.TIMESTAMP, ITx.READ_COMMITTED),//
+ }));
+
+ final Predicate<?> pred3Op = new Predicate<E>(
+ new IVariableOrConstant[] { c, d }, NV
+ .asMap(new NV[] {//
+ new NV(Predicate.Annotations.RELATION_NAME,
+ new String[] { namespace }),//
+ new NV(Predicate.Annotations.BOP_ID, predId3),//
+ new NV(Annotations.TIMESTAMP, ITx.READ_COMMITTED),//
+ }));
+
+ final PipelineOp join1Op = new PipelineJoin<E>(//
+ new BOp[]{startOp},//
+ new NV(Predicate.Annotations.BOP_ID, joinId1),//
+ new NV(PipelineJoin.Annotations.PREDICATE,pred1Op));
+
+ final PipelineOp join2Op = new PipelineJoin<E>(//
+ new BOp[] { join1Op },//
+ new NV(Predicate.Annotations.BOP_ID, joinId2),//
+ new NV(PipelineOp.Annotations.CONDITIONAL_GROUP, joinGroup1),//
+ new NV(PipelineJoin.Annotations.PREDICATE, pred2Op),//
+ // join is optional.
+ new NV(PipelineJoin.Annotations.OPTIONAL, true),//
+ // optional target is the same as the default target.
+ new NV(PipelineOp.Annotations.ALT_SINK_REF, sliceId));
+
+ final PipelineOp join3Op = new PipelineJoin<E>(//
+ new BOp[] { join2Op },//
+ new NV(Predicate.Annotations.BOP_ID, joinId3),//
+ new NV(PipelineOp.Annotations.CONDITIONAL_GROUP, joinGroup1),//
+ new NV(PipelineJoin.Annotations.PREDICATE, pred3Op),//
+ // join is optional.
+ new NV(PipelineJoin.Annotations.OPTIONAL, true),//
+ // optional target is the same as the default target.
+ new NV(PipelineOp.Annotations.ALT_SINK_REF, sliceId));
+
+ final PipelineOp sliceOp = new SliceOp(//
+ new BOp[]{join3Op},
+ NV.asMap(new NV[] {//
+ new NV(BOp.Annotations.BOP_ID, sliceId),//
+ new NV(BOp.Annotations.EVALUATION_CONTEXT,
+ BOpEvaluationContext.CONTROLLER),//
+ }));
+
+ final PipelineOp query = sliceOp;
+
+ // verify found.
+ assertEquals(Integer.valueOf(joinId2), BOpUtility
+ .getFirstBOpIdForConditionalGroup(query, joinGroup1));
+
+ // verify not-found.
+ assertEquals(null, BOpUtility.getFirstBOpIdForConditionalGroup(query,
+ Integer.valueOf(2)/* groupId */));
+
+ }
+
+ /**
* Unit test for {@link BOpUtility#getParent(BOp, BOp)}.
*/
public void test_getParent() {
Modified: branches/QUADS_QUERY_BRANCH/bigdata/src/test/com/bigdata/bop/engine/TestQueryEngineOptionalJoins.java
===================================================================
--- branches/QUADS_QUERY_BRANCH/bigdata/src/test/com/bigdata/bop/engine/TestQueryEngineOptionalJoins.java 2010-12-21 22:21:54 UTC (rev 4038)
+++ branches/QUADS_QUERY_BRANCH/bigdata/src/test/com/bigdata/bop/engine/TestQueryEngineOptionalJoins.java 2010-12-21 23:07:08 UTC (rev 4039)
@@ -28,6 +28,8 @@
package com.bigdata.bop.engine;
import java.util.Iterator;
+import java.util.LinkedList;
+import java.util.List;
import java.util.Map;
import java.util.Properties;
import java.util.UUID;
@@ -218,39 +220,46 @@
/**
* Unit test for optional join group. Three joins are used and target a
- * {@link SliceOp}. The 2nd and 3rd joins are an optional join group.
- * Intermediate results which do not succeed on the optional join are
+ * {@link SliceOp}. The 2nd and 3rd joins are an optional join group.
+ * Intermediate results which do not succeed on the optional join are
* forwarded to the {@link SliceOp} which is the target specified by the
* {@link PipelineOp.Annotations#ALT_SINK_REF}.
*
* The optional join group takes the form:
+ *
+ * <pre>
* (a b)
* optional {
* (b c)
* (c d)
* }
- *
- * The (a b) tail will match everything in the knowledge base. The join
- * group takes us two hops out from ?b. There should be four solutions
- * that succeed the optional join group:
+ * </pre>
*
+ * The (a b) tail will match everything in the knowledge base. The join
+ * group takes us two hops out from ?b. There should be four solutions that
+ * succeed the optional join group:
+ *
+ * <pre>
* (paul mary brad fred)
* (paul mary brad leon)
* (john mary brad fred)
* (john mary brad leon)
+ * </pre>
*
* and five more that don't succeed the optional join group:
*
+ * <pre>
* (paul brad) *
* (john brad) *
* (mary brad) *
* (brad fred)
* (brad leon)
+ * </pre>
*
- * In this cases marked with a *, ?c will become temporarily bound to fred
- * and leon (since brad knows fred and leon), but the (c d) tail will fail
- * since fred and leon don't know anyone else. At this point, the ?c binding
- * must be removed from the solution.
+ * In this cases marked with a <code>*</code>, ?c will become temporarily
+ * bound to fred and leon (since brad knows fred and leon), but the (c d)
+ * tail will fail since fred and leon don't know anyone else. At this point,
+ * the ?c binding must be removed from the solution.
*/
public void test_query_join2_optionals() throws Exception {
@@ -267,6 +276,8 @@
final IVariable<?> b = Var.var("b");
final IVariable<?> c = Var.var("c");
final IVariable<?> d = Var.var("d");
+
+ final Object joinGroup1 = Integer.valueOf(1);
final PipelineOp startOp = new StartOp(new BOp[] {},
NV.asMap(new NV[] {//
@@ -309,7 +320,8 @@
final PipelineOp join2Op = new PipelineJoin<E>(//
new BOp[] { join1Op },//
- new NV(Predicate.Annotations.BOP_ID, joinId2),//
+ new NV(Predicate.Annotations.BOP_ID, joinId2),//
+ new NV(PipelineOp.Annotations.CONDITIONAL_GROUP, joinGroup1),//
new NV(PipelineJoin.Annotations.PREDICATE, pred2Op),//
// join is optional.
new NV(PipelineJoin.Annotations.OPTIONAL, true),//
@@ -319,6 +331,7 @@
final PipelineOp join3Op = new PipelineJoin<E>(//
new BOp[] { join2Op },//
new NV(Predicate.Annotations.BOP_ID, joinId3),//
+ new NV(PipelineOp.Annotations.CONDITIONAL_GROUP, joinGroup1),//
new NV(PipelineJoin.Annotations.PREDICATE, pred3Op),//
// join is optional.
new NV(PipelineJoin.Annotations.OPTIONAL, true),//
@@ -415,6 +428,11 @@
)
};
+ /*
+ * junit.framework.AssertionFailedError: Iterator will deliver too
+ * many objects: reminder(3)=[{ a=John, b=Brad }, { a=Mary, b=Brad
+ * }, { a=Paul, b=Brad }].
+ */
assertSameSolutionsAnyOrder(expected,
new Dechunkerator<IBindingSet>(runningQuery.iterator()));
@@ -434,45 +452,54 @@
}
/**
- * Unit test for optional join group with a filter. Three joins are used
- * and target a {@link SliceOp}. The 2nd and 3rd joins are an optional join
- * group. Intermediate results which do not succeed on the optional join are
+ * Unit test for optional join group with a filter. Three joins are used and
+ * target a {@link SliceOp}. The 2nd and 3rd joins are an optional join
+ * group. Intermediate results which do not succeed on the optional join are
* forwarded to the {@link SliceOp} which is the target specified by the
- * {@link PipelineOp.Annotations#ALT_SINK_REF}. The optional join group
+ * {@link PipelineOp.Annotations#ALT_SINK_REF}. The optional join group
* contains a filter.
+ * <p>
+ * The optional join group takes the form:
*
- * The optional join group takes the form:
+ * <pre>
* (a b)
* optional {
* (b c)
* (c d)
* filter(d != Leon)
* }
- *
- * The (a b) tail will match everything in the knowledge base. The join
- * group takes us two hops out from ?b. There should be two solutions
- * that succeed the optional join group:
+ * </pre>
*
+ * The (a b) tail will match everything in the knowledge base. The join
+ * group takes us two hops out from ?b. There should be two solutions that
+ * succeed the optional join group:
+ *
+ * <pre>
* (paul mary brad fred)
* (john mary brad fred)
+ * </pre>
*
* and five more that don't succeed the optional join group:
*
+ * <pre>
* (paul brad) *
* (john brad) *
* (mary brad) *
* (brad fred)
* (brad leon)
+ * </pre>
*
- * In this cases marked with a *, ?c will become temporarily bound to fred
- * and leon (since brad knows fred and leon), but the (c d) tail will fail
- * since fred and leon don't know anyone else. At this point, the ?c binding
- * must be removed from the solution.
- *
+ * In this cases marked with a <code>*</code>, ?c will become temporarily
+ * bound to fred and leon (since brad knows fred and leon), but the (c d)
+ * tail will fail since fred and leon don't know anyone else. At this point,
+ * the ?c binding must be removed from the solution.
+ * <p>
* The filter (d != Leon) will prune the two solutions:
*
+ * <pre>
* (paul mary brad leon)
* (john mary brad leon)
+ * </pre>
*
* since ?d is bound to Leon in those cases.
*/
@@ -647,43 +674,50 @@
}
/**
- * Unit test for optional join group with a filter on a variable outside
- * the optional join group. Three joins are used and target a
- * {@link SliceOp}. The 2nd and 3rd joins are an optional join
- * group. Intermediate results which do not succeed on the optional join are
- * forwarded to the {@link SliceOp} which is the target specified by the
- * {@link PipelineOp.Annotations#ALT_SINK_REF}. The optional join group
+ * Unit test for optional join group with a filter on a variable outside the
+ * optional join group. Three joins are used and target a {@link SliceOp}.
+ * The 2nd and 3rd joins are an optional join group. Intermediate results
+ * which do not succeed on the optional join are forwarded to the
+ * {@link SliceOp} which is the target specified by the
+ * {@link PipelineOp.Annotations#ALT_SINK_REF}. The optional join group
* contains a filter that uses a variable outside the optional join group.
+ * <P>
+ * The query takes the form:
*
- * The query takes the form:
+ * <pre>
* (a b)
* optional {
* (b c)
* (c d)
* filter(a != Paul)
* }
- *
- * The (a b) tail will match everything in the knowledge base. The join
- * group takes us two hops out from ?b. There should be two solutions
- * that succeed the optional join group:
+ * </pre>
*
+ * The (a b) tail will match everything in the knowledge base. The join
+ * group takes us two hops out from ?b. There should be two solutions that
+ * succeed the optional join group:
+ *
+ * <pre>
* (john mary brad fred)
* (john mary brad leon)
+ * </pre>
*
* and six more that don't succeed the optional join group:
- *
+ *
+ * <pre>
* (paul mary) *
* (paul brad) *
* (john brad)
* (mary brad)
* (brad fred)
* (brad leon)
+ * </pre>
*
- * In this cases marked with a *, ?a is bound to Paul even though there is
- * a filter that specifically prohibits a = Paul. This is because the filter
- * is inside the optional join group, which means that solutions can still
- * include a = Paul, but the optional join group should not run in that
- * case.
+ * In this cases marked with a <code>*</code>, ?a is bound to Paul even
+ * though there is a filter that specifically prohibits a = Paul. This is
+ * because the filter is inside the optional join group, which means that
+ * solutions can still include a = Paul, but the optional join group should
+ * not run in that case.
*/
public void test_query_optionals_filter2() throws Exception {
@@ -1006,8 +1040,15 @@
if (actual.hasNext()) {
- fail("Iterator will deliver too many objects.");
+ final List<T> remainder = new LinkedList<T>();
+
+ while(actual.hasNext()) {
+ remainder.add(actual.next());
+ }
+ fail("Iterator will deliver too many objects: reminder("
+ + remainder.size() + ")=" + remainder);
+
}
} finally {
This was sent by the SourceForge.net collaborative development platform, the world's largest Open Source development site.
|
