Menu
▾
▴
[Bigdata-commit] SF.net SVN: bigdata:[3998] branches/QUADS_QUERY_BRANCH/bigdata
|
From: <mrp...@us...> - 2010-12-07 22:32:03
|
Revision: 3998
http://bigdata.svn.sourceforge.net/bigdata/?rev=3998&view=rev
Author: mrpersonick
Date: 2010-12-07 22:31:55 +0000 (Tue, 07 Dec 2010)
Log Message:
-----------
adding test for optional join groups
Modified Paths:
--------------
branches/QUADS_QUERY_BRANCH/bigdata-sails/src/test/com/bigdata/rdf/sail/TestNestedOptionals.java
Added Paths:
-----------
branches/QUADS_QUERY_BRANCH/bigdata/src/test/com/bigdata/bop/engine/TestQueryEngineOptionalJoins.java
Added: 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 (rev 0)
+++ branches/QUADS_QUERY_BRANCH/bigdata/src/test/com/bigdata/bop/engine/TestQueryEngineOptionalJoins.java 2010-12-07 22:31:55 UTC (rev 3998)
@@ -0,0 +1,980 @@
+/**
+
+Copyright (C) SYSTAP, LLC 2006-2010. 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 Aug 23, 2010
+ */
+
+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;
+import java.util.concurrent.CancellationException;
+import java.util.concurrent.ExecutionException;
+import java.util.concurrent.Executor;
+import java.util.concurrent.FutureTask;
+import java.util.concurrent.TimeUnit;
+import java.util.concurrent.TimeoutException;
+import java.util.concurrent.atomic.AtomicInteger;
+
+import junit.framework.TestCase2;
+
+import com.bigdata.bop.BOp;
+import com.bigdata.bop.BOpEvaluationContext;
+import com.bigdata.bop.Constant;
+import com.bigdata.bop.IBindingSet;
+import com.bigdata.bop.IConstant;
+import com.bigdata.bop.IConstraint;
+import com.bigdata.bop.IVariable;
+import com.bigdata.bop.IVariableOrConstant;
+import com.bigdata.bop.NV;
+import com.bigdata.bop.PipelineOp;
+import com.bigdata.bop.Var;
+import com.bigdata.bop.IPredicate.Annotations;
+import com.bigdata.bop.ap.E;
+import com.bigdata.bop.ap.Predicate;
+import com.bigdata.bop.ap.R;
+import com.bigdata.bop.bindingSet.ArrayBindingSet;
+import com.bigdata.bop.bindingSet.HashBindingSet;
+import com.bigdata.bop.bset.ConditionalRoutingOp;
+import com.bigdata.bop.bset.StartOp;
+import com.bigdata.bop.constraint.EQ;
+import com.bigdata.bop.constraint.EQConstant;
+import com.bigdata.bop.constraint.NEConstant;
+import com.bigdata.bop.fed.TestFederatedQueryEngine;
+import com.bigdata.bop.join.PipelineJoin;
+import com.bigdata.bop.solutions.SliceOp;
+import com.bigdata.bop.solutions.SliceOp.SliceStats;
+import com.bigdata.io.DirectBufferPoolAllocator.IAllocationContext;
+import com.bigdata.journal.BufferMode;
+import com.bigdata.journal.ITx;
+import com.bigdata.journal.Journal;
+import com.bigdata.relation.accesspath.IAsynchronousIterator;
+import com.bigdata.relation.accesspath.ThickAsynchronousIterator;
+import com.bigdata.striterator.ChunkedArrayIterator;
+import com.bigdata.striterator.Dechunkerator;
+import com.bigdata.striterator.ICloseableIterator;
+import com.bigdata.util.InnerCause;
+import com.bigdata.util.concurrent.LatchedExecutor;
+import com.ibm.icu.impl.ByteBuffer;
+
+/**
+ * Test suite for the {@link QueryEngine} against a local database instance.
+ * <p>
+ * Note: The {@link BOp}s are unit tested separately. This test suite is focused
+ * on interactions when {@link BOp}s are chained together in a query, such as a
+ * sequence of pipeline joins, a slice applied to a query, etc.
+ *
+ * <pre>
+ * -Dlog4j.configuration=bigdata/src/resources/logging/log4j.properties
+ * </pre>
+ *
+ * @author <a href="mailto:tho...@us...">Bryan Thompson</a>
+ * @version $Id: TestQueryEngine.java 3950 2010-11-17 02:14:08Z thompsonbry $
+ *
+ * @see TestFederatedQueryEngine
+ *
+ * @todo write a unit and stress tests for deadlines.
+ */
+public class TestQueryEngineOptionalJoins extends TestCase2 {
+
+ /**
+ *
+ */
+ public TestQueryEngineOptionalJoins() {
+ }
+
+ /**
+ * @param name
+ */
+ public TestQueryEngineOptionalJoins(String name) {
+ super(name);
+ }
+
+ @Override
+ public Properties getProperties() {
+
+ final Properties p = new Properties(super.getProperties());
+
+ p.setProperty(Journal.Options.BUFFER_MODE, BufferMode.Transient
+ .toString());
+
+ return p;
+
+ }
+
+ static private final String namespace = "ns";
+ Journal jnl;
+ QueryEngine queryEngine;
+
+ public void setUp() throws Exception {
+
+ jnl = new Journal(getProperties());
+
+ loadData(jnl);
+
+ queryEngine = new QueryEngine(jnl);
+
+ queryEngine.init();
+
+ }
+
+ /**
+ * Create and populate relation in the {@link #namespace}.
+ */
+ private void loadData(final Journal store) {
+
+ // create the relation.
+ final R rel = new R(store, namespace, ITx.UNISOLATED, new Properties());
+ rel.create();
+
+ // data to insert (in key order for convenience).
+ final E[] a = {//
+ new E("Paul", "Mary"),// [0]
+ new E("Paul", "Brad"),// [1]
+
+ new E("John", "Mary"),// [0]
+ new E("John", "Brad"),// [1]
+
+ new E("Mary", "Brad"),// [1]
+
+ new E("Brad", "Fred"),// [1]
+ new E("Brad", "Leon"),// [1]
+ };
+
+ // insert data (the records are not pre-sorted).
+ rel.insert(new ChunkedArrayIterator<E>(a.length, a, null/* keyOrder */));
+
+ // Do commit since not scale-out.
+ store.commit();
+
+ }
+
+ public void tearDown() throws Exception {
+
+ if (queryEngine != null) {
+ queryEngine.shutdownNow();
+ queryEngine = null;
+ }
+
+ if (jnl != null) {
+ jnl.destroy();
+ jnl = null;
+ }
+
+ }
+
+ /**
+ * Return an {@link IAsynchronousIterator} that will read a single,
+ * empty {@link IBindingSet}.
+ *
+ * @param bindingSet
+ * the binding set.
+ */
+ protected ThickAsynchronousIterator<IBindingSet[]> newBindingSetIterator(
+ final IBindingSet bindingSet) {
+
+ return new ThickAsynchronousIterator<IBindingSet[]>(
+ new IBindingSet[][] { new IBindingSet[] { bindingSet } });
+
+ }
+
+ /**
+ * Return an {@link IAsynchronousIterator} that will read a single, chunk
+ * containing all of the specified {@link IBindingSet}s.
+ *
+ * @param bindingSets
+ * the binding sets.
+ */
+ protected ThickAsynchronousIterator<IBindingSet[]> newBindingSetIterator(
+ final IBindingSet[] bindingSets) {
+
+ return new ThickAsynchronousIterator<IBindingSet[]>(
+ new IBindingSet[][] { bindingSets });
+
+ }
+
+ /**
+ * Return an {@link IAsynchronousIterator} that will read a single, chunk
+ * containing all of the specified {@link IBindingSet}s.
+ *
+ * @param bindingSetChunks
+ * the chunks of binding sets.
+ */
+ protected ThickAsynchronousIterator<IBindingSet[]> newBindingSetIterator(
+ final IBindingSet[][] bindingSetChunks) {
+
+ return new ThickAsynchronousIterator<IBindingSet[]>(bindingSetChunks);
+
+ }
+
+ /**
+ * 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
+ * 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:
+ * (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:
+ *
+ * (paul mary brad fred)
+ * (paul mary brad leon)
+ * (john mary brad fred)
+ * (john mary brad leon)
+ *
+ * and five more that don't succeed the optional join group:
+ *
+ * (paul brad) *
+ * (john brad) *
+ * (mary brad) *
+ * (brad fred)
+ * (brad leon)
+ *
+ * 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.
+ */
+ public void test_query_join2_optionals() throws Exception {
+
+ final int startId = 1;
+ final int joinId1 = 2;
+ final int predId1 = 3;
+ final int joinId2 = 4;
+ final int predId2 = 5;
+ final int joinId3 = 6;
+ final int predId3 = 7;
+ 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 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(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(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;
+
+ // start the query.
+ final UUID queryId = UUID.randomUUID();
+ final IChunkMessage<IBindingSet> initialChunkMessage;
+ {
+
+ final IBindingSet initialBindings = new HashBindingSet();
+
+// initialBindings.set(Var.var("x"), new Constant<String>("Mary"));
+
+ initialChunkMessage = new LocalChunkMessage<IBindingSet>(queryEngine,
+ queryId, startId,//
+ -1, // partitionId
+ newBindingSetIterator(initialBindings));
+ }
+ final RunningQuery runningQuery = queryEngine.eval(queryId, query,
+ initialChunkMessage);
+
+ // verify solutions.
+ {
+
+ // the expected solutions.
+ final IBindingSet[] expected = new IBindingSet[] {//
+ // four solutions where the optional join succeeds.
+ new ArrayBindingSet(//
+ new IVariable[] { a, b, c, d },//
+ new IConstant[] { new Constant<String>("Paul"),
+ new Constant<String>("Mary"),
+ new Constant<String>("Brad"),
+ new Constant<String>("Fred") }//
+ ),
+ new ArrayBindingSet(//
+ new IVariable[] { a, b, c, d },//
+ new IConstant[] { new Constant<String>("Paul"),
+ new Constant<String>("Mary"),
+ new Constant<String>("Brad"),
+ new Constant<String>("Leon") }//
+ ),
+ new ArrayBindingSet(//
+ new IVariable[] { a, b, c, d },//
+ new IConstant[] { new Constant<String>("John"),
+ new Constant<String>("Mary"),
+ new Constant<String>("Brad"),
+ new Constant<String>("Fred") }//
+ ),
+ new ArrayBindingSet(//
+ new IVariable[] { a, b, c, d },//
+ new IConstant[] { new Constant<String>("John"),
+ new Constant<String>("Mary"),
+ new Constant<String>("Brad"),
+ new Constant<String>("Leon") }//
+ ),
+ // plus anything we read from the first access path which did not
+ // pass the optional join
+ new ArrayBindingSet(//
+ new IVariable[] { a, b },//
+ new IConstant[] { new Constant<String>("Paul"),
+ new Constant<String>("Brad") }//
+ ),
+ new ArrayBindingSet(//
+ new IVariable[] { a, b },//
+ new IConstant[] { new Constant<String>("John"),
+ new Constant<String>("Brad") }//
+ ),
+ new ArrayBindingSet(//
+ new IVariable[] { a, b },//
+ new IConstant[] { new Constant<String>("Mary"),
+ new Constant<String>("Brad") }//
+ ),
+ new ArrayBindingSet(//
+ new IVariable[] { a, b },//
+ new IConstant[] { new Constant<String>("Brad"),
+ new Constant<String>("Fred") }//
+ ),
+ new ArrayBindingSet(//
+ new IVariable[] { a, b },//
+ new IConstant[] { new Constant<String>("Brad"),
+ new Constant<String>("Leon") }//
+ )
+ };
+
+ assertSameSolutionsAnyOrder(expected,
+ new Dechunkerator<IBindingSet>(runningQuery.iterator()));
+
+ }
+
+ // Wait until the query is done.
+ runningQuery.get();
+ final Map<Integer, BOpStats> statsMap = runningQuery.getStats();
+ {
+ // validate the stats map.
+ assertNotNull(statsMap);
+ assertEquals(5, statsMap.size());
+ if (log.isInfoEnabled())
+ log.info(statsMap.toString());
+ }
+
+ }
+
+ /**
+ * 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
+ * contains a filter.
+ *
+ * The optional join group takes the form:
+ * (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:
+ *
+ * (paul mary brad fred)
+ * (john mary brad fred)
+ *
+ * and five more that don't succeed the optional join group:
+ *
+ * (paul brad) *
+ * (john brad) *
+ * (mary brad) *
+ * (brad fred)
+ * (brad leon)
+ *
+ * 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.
+ *
+ * The filter (d != Leon) will prune the two solutions:
+ *
+ * (paul mary brad leon)
+ * (john mary brad leon)
+ *
+ * since ?d is bound to Leon in those cases.
+ */
+ public void test_query_optionals_filter() throws Exception {
+
+ final int startId = 1;
+ final int joinId1 = 2;
+ final int predId1 = 3;
+ final int joinId2 = 4;
+ final int predId2 = 5;
+ final int joinId3 = 6;
+ final int predId3 = 7;
+ 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 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(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(PipelineJoin.Annotations.PREDICATE, pred3Op),//
+ // constraint d != Leon
+ new NV(PipelineJoin.Annotations.CONSTRAINTS,
+ new IConstraint[] { new NEConstant(d, new Constant<String>("Leon")) }),
+ // 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;
+
+ // start the query.
+ final UUID queryId = UUID.randomUUID();
+ final IChunkMessage<IBindingSet> initialChunkMessage;
+ {
+
+ final IBindingSet initialBindings = new HashBindingSet();
+
+// initialBindings.set(Var.var("x"), new Constant<String>("Mary"));
+
+ initialChunkMessage = new LocalChunkMessage<IBindingSet>(queryEngine,
+ queryId, startId,//
+ -1, // partitionId
+ newBindingSetIterator(initialBindings));
+ }
+ final RunningQuery runningQuery = queryEngine.eval(queryId, query,
+ initialChunkMessage);
+
+ // verify solutions.
+ {
+
+ // the expected solutions.
+ final IBindingSet[] expected = new IBindingSet[] {//
+ // two solutions where the optional join succeeds.
+ new ArrayBindingSet(//
+ new IVariable[] { a, b, c, d },//
+ new IConstant[] { new Constant<String>("Paul"),
+ new Constant<String>("Mary"),
+ new Constant<String>("Brad"),
+ new Constant<String>("Fred") }//
+ ),
+ new ArrayBindingSet(//
+ new IVariable[] { a, b, c, d },//
+ new IConstant[] { new Constant<String>("John"),
+ new Constant<String>("Mary"),
+ new Constant<String>("Brad"),
+ new Constant<String>("Fred") }//
+ ),
+ // plus anything we read from the first access path which did not
+ // pass the optional join
+ new ArrayBindingSet(//
+ new IVariable[] { a, b },//
+ new IConstant[] { new Constant<String>("Paul"),
+ new Constant<String>("Brad") }//
+ ),
+ new ArrayBindingSet(//
+ new IVariable[] { a, b },//
+ new IConstant[] { new Constant<String>("John"),
+ new Constant<String>("Brad") }//
+ ),
+ new ArrayBindingSet(//
+ new IVariable[] { a, b },//
+ new IConstant[] { new Constant<String>("Mary"),
+ new Constant<String>("Brad") }//
+ ),
+ new ArrayBindingSet(//
+ new IVariable[] { a, b },//
+ new IConstant[] { new Constant<String>("Brad"),
+ new Constant<String>("Fred") }//
+ ),
+ new ArrayBindingSet(//
+ new IVariable[] { a, b },//
+ new IConstant[] { new Constant<String>("Brad"),
+ new Constant<String>("Leon") }//
+ )
+ };
+
+ assertSameSolutionsAnyOrder(expected,
+ new Dechunkerator<IBindingSet>(runningQuery.iterator()));
+
+ }
+
+ // Wait until the query is done.
+ runningQuery.get();
+ final Map<Integer, BOpStats> statsMap = runningQuery.getStats();
+ {
+ // validate the stats map.
+ assertNotNull(statsMap);
+ assertEquals(5, statsMap.size());
+ if (log.isInfoEnabled())
+ log.info(statsMap.toString());
+ }
+
+ }
+
+ /**
+ * 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.
+ *
+ * The query takes the form:
+ * (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:
+ *
+ * (john mary brad fred)
+ * (john mary brad leon)
+ *
+ * and six more that don't succeed the optional join group:
+ *
+ * (paul mary) *
+ * (paul brad) *
+ * (john brad)
+ * (mary brad)
+ * (brad fred)
+ * (brad leon)
+ *
+ * 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.
+ */
+ public void test_query_optionals_filter2() throws Exception {
+
+ final int startId = 1;
+ final int joinId1 = 2;
+ final int predId1 = 3;
+ final int joinId2 = 4;
+ final int predId2 = 5;
+ final int joinId3 = 6;
+ final int predId3 = 7;
+ 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");
+
+ /*
+ * Not quite sure how to write this one. I think it probably goes
+ * something like this:
+ *
+ * 1. startOp
+ * 2. join1Op(a b)
+ * 3. conditionalRoutingOp( if a = Paul then goto sliceOp )
+ * 4. join2Op(b c)
+ * 5. join3Op(c d)
+ * 6. sliceOp
+ */
+
+ 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 PipelineOp sliceOp = new SliceOp(//
+ new BOp[]{startOp},
+ NV.asMap(new NV[] {//
+ new NV(BOp.Annotations.BOP_ID, sliceId),//
+ new NV(BOp.Annotations.EVALUATION_CONTEXT,
+ BOpEvaluationContext.CONTROLLER),//
+ }));
+
+ final PipelineOp query = sliceOp;
+
+ // start the query.
+ final UUID queryId = UUID.randomUUID();
+ final IChunkMessage<IBindingSet> initialChunkMessage;
+ {
+
+ final IBindingSet initialBindings = new HashBindingSet();
+
+// initialBindings.set(Var.var("x"), new Constant<String>("Mary"));
+
+ initialChunkMessage = new LocalChunkMessage<IBindingSet>(queryEngine,
+ queryId, startId,//
+ -1, // partitionId
+ newBindingSetIterator(initialBindings));
+ }
+ final RunningQuery runningQuery = queryEngine.eval(queryId, query,
+ initialChunkMessage);
+
+ // verify solutions.
+ {
+
+ // the expected solutions.
+ final IBindingSet[] expected = new IBindingSet[] {//
+ // two solutions where the optional join succeeds.
+ new ArrayBindingSet(//
+ new IVariable[] { a, b, c, d },//
+ new IConstant[] { new Constant<String>("John"),
+ new Constant<String>("Mary"),
+ new Constant<String>("Brad"),
+ new Constant<String>("John") }//
+ ),
+ new ArrayBindingSet(//
+ new IVariable[] { a, b, c, d },//
+ new IConstant[] { new Constant<String>("John"),
+ new Constant<String>("Mary"),
+ new Constant<String>("Brad"),
+ new Constant<String>("Fred") }//
+ ),
+ // plus anything we read from the first access path which did not
+ // pass the optional join
+ new ArrayBindingSet(//
+ new IVariable[] { a, b },//
+ new IConstant[] { new Constant<String>("Paul"),
+ new Constant<String>("Mary") }//
+ ),
+ new ArrayBindingSet(//
+ new IVariable[] { a, b },//
+ new IConstant[] { new Constant<String>("Paul"),
+ new Constant<String>("Brad") }//
+ ),
+ new ArrayBindingSet(//
+ new IVariable[] { a, b },//
+ new IConstant[] { new Constant<String>("John"),
+ new Constant<String>("Brad") }//
+ ),
+ new ArrayBindingSet(//
+ new IVariable[] { a, b },//
+ new IConstant[] { new Constant<String>("Mary"),
+ new Constant<String>("Brad") }//
+ ),
+ new ArrayBindingSet(//
+ new IVariable[] { a, b },//
+ new IConstant[] { new Constant<String>("Brad"),
+ new Constant<String>("Fred") }//
+ ),
+ new ArrayBindingSet(//
+ new IVariable[] { a, b },//
+ new IConstant[] { new Constant<String>("Brad"),
+ new Constant<String>("Leon") }//
+ )
+ };
+
+ assertSameSolutionsAnyOrder(expected,
+ new Dechunkerator<IBindingSet>(runningQuery.iterator()));
+
+ }
+
+ // Wait until the query is done.
+ runningQuery.get();
+ final Map<Integer, BOpStats> statsMap = runningQuery.getStats();
+ {
+ // validate the stats map.
+ assertNotNull(statsMap);
+ assertEquals(6, statsMap.size());
+ if (log.isInfoEnabled())
+ log.info(statsMap.toString());
+ }
+
+ }
+
+ /**
+ * Verify the expected solutions.
+ *
+ * @param expected
+ * @param itr
+ */
+ static public void assertSameSolutions(final IBindingSet[] expected,
+ final IAsynchronousIterator<IBindingSet[]> itr) {
+ try {
+ int n = 0;
+ while (itr.hasNext()) {
+ final IBindingSet[] e = itr.next();
+ if (log.isInfoEnabled())
+ log.info(n + " : chunkSize=" + e.length);
+ for (int i = 0; i < e.length; i++) {
+ if (log.isInfoEnabled())
+ log.info(n + " : " + e[i]);
+ if (n >= expected.length) {
+ fail("Willing to deliver too many solutions: n=" + n
+ + " : " + e[i]);
+ }
+ if (!expected[n].equals(e[i])) {
+ fail("n=" + n + ", expected=" + expected[n]
+ + ", actual=" + e[i]);
+ }
+ n++;
+ }
+ }
+ assertEquals("Wrong number of solutions", expected.length, n);
+ } finally {
+ itr.close();
+ }
+ }
+
+ /**
+ * Verifies that the iterator visits the specified objects in some arbitrary
+ * ordering and that the iterator is exhausted once all expected objects
+ * have been visited. The implementation uses a selection without
+ * replacement "pattern".
+ * <p>
+ * Note: If the objects being visited do not correctly implement hashCode()
+ * and equals() then this can fail even if the desired objects would be
+ * visited. When this happens, fix the implementation classes.
+ */
+ static public <T> void assertSameSolutionsAnyOrder(final T[] expected,
+ final Iterator<T> actual) {
+
+ assertSameSolutionsAnyOrder("", expected, actual);
+
+ }
+
+ /**
+ * Verifies that the iterator visits the specified objects in some arbitrary
+ * ordering and that the iterator is exhausted once all expected objects
+ * have been visited. The implementation uses a selection without
+ * replacement "pattern".
+ * <p>
+ * Note: If the objects being visited do not correctly implement hashCode()
+ * and equals() then this can fail even if the desired objects would be
+ * visited. When this happens, fix the implementation classes.
+ */
+ static public <T> void assertSameSolutionsAnyOrder(final String msg,
+ final T[] expected, final Iterator<T> actual) {
+
+ try {
+
+ /*
+ * Populate a map that we will use to realize the match and
+ * selection without replacement logic. The map uses counters to
+ * handle duplicate keys. This makes it possible to write tests in
+ * which two or more binding sets which are "equal" appear.
+ */
+
+ final int nrange = expected.length;
+
+ final java.util.Map<T, AtomicInteger> range = new java.util.LinkedHashMap<T, AtomicInteger>();
+
+ for (int j = 0; j < nrange; j++) {
+
+ AtomicInteger count = range.get(expected[j]);
+
+ if (count == null) {
+
+ count = new AtomicInteger();
+
+ }
+
+ range.put(expected[j], count);
+
+ count.incrementAndGet();
+
+ }
+
+ // Do selection without replacement for the objects visited by
+ // iterator.
+
+ for (int j = 0; j < nrange; j++) {
+
+ if (!actual.hasNext()) {
+
+ fail(msg
+ + ": Iterator exhausted while expecting more object(s)"
+ + ": index=" + j);
+
+ }
+
+ final T actualObject = actual.next();
+
+ if (log.isInfoEnabled())
+ log.info("visting: " + actualObject);
+
+ AtomicInteger counter = range.get(actualObject);
+
+ if (counter == null || counter.get() == 0) {
+
+ fail("Object not expected" + ": index=" + j + ", object="
+ + actualObject);
+
+ }
+
+ counter.decrementAndGet();
+
+ }
+
+ if (actual.hasNext()) {
+
+ fail("Iterator will deliver too many objects.");
+
+ }
+
+ } finally {
+
+ if (actual instanceof ICloseableIterator<?>) {
+
+ ((ICloseableIterator<T>) actual).close();
+
+ }
+
+ }
+
+ }
+
+}
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 2010-12-06 22:09:42 UTC (rev 3997)
+++ branches/QUADS_QUERY_BRANCH/bigdata-sails/src/test/com/bigdata/rdf/sail/TestNestedOptionals.java 2010-12-07 22:31:55 UTC (rev 3998)
@@ -26,11 +26,11 @@
package com.bigdata.rdf.sail;
-import java.util.Arrays;
import java.util.Collection;
import java.util.LinkedList;
import java.util.List;
import java.util.Properties;
+
import org.apache.log4j.Logger;
import org.openrdf.model.Literal;
import org.openrdf.model.URI;
@@ -49,6 +49,13 @@
import org.openrdf.query.algebra.TupleExpr;
import org.openrdf.query.algebra.ValueExpr;
import org.openrdf.query.algebra.Var;
+import org.openrdf.repository.Repository;
+import org.openrdf.repository.RepositoryConnection;
+import org.openrdf.repository.sail.SailRepository;
+import org.openrdf.repository.sail.SailTupleQuery;
+import org.openrdf.sail.Sail;
+import org.openrdf.sail.memory.MemoryStore;
+
import com.bigdata.rdf.axioms.NoAxioms;
import com.bigdata.rdf.store.BD;
import com.bigdata.rdf.vocab.NoVocabulary;
@@ -92,9 +99,160 @@
public TestNestedOptionals(String arg0) {
super(arg0);
}
+
+ public void testNestedOptionals() throws Exception {
+
+ final Sail sail = new MemoryStore();
+ sail.initialize();
+ final Repository repo = new SailRepository(sail);
+ final RepositoryConnection cxn = repo.getConnection();
+ cxn.setAutoCommit(false);
+
+ try {
+
+ final ValueFactory vf = sail.getValueFactory();
- public void testNestedOptionals1() throws Exception {
+ /*
+ * Create some terms.
+ */
+ final URI john = vf.createURI(BD.NAMESPACE + "john");
+ final URI mary = vf.createURI(BD.NAMESPACE + "mary");
+ final URI leon = vf.createURI(BD.NAMESPACE + "leon");
+ final URI paul = vf.createURI(BD.NAMESPACE + "paul");
+ final URI brad = vf.createURI(BD.NAMESPACE + "brad");
+ final URI fred = vf.createURI(BD.NAMESPACE + "fred");
+ final URI knows = vf.createURI(BD.NAMESPACE + "knows");
+ /*
+ * Create some statements.
+ */
+ cxn.add(paul, knows, mary);
+ cxn.add(paul, knows, brad);
+
+ cxn.add(john, knows, mary);
+ cxn.add(john, knows, brad);
+
+ cxn.add(mary, knows, brad);
+ cxn.add(brad, knows, fred);
+ cxn.add(brad, knows, leon);
+
+ /*
+ * Note: The either flush() or commit() is required to flush the
+ * statement buffers to the database before executing any operations
+ * that go around the sail.
+ */
+ cxn.commit();
+
+ {
+
+ String query =
+ "prefix bd: <"+BD.NAMESPACE+"> " +
+ "select * " +
+ "where { " +
+ " ?a bd:knows ?b . " +
+ " OPTIONAL { " +
+ " ?b bd:knows ?c . " +
+ " ?c bd:knows ?d . " +
+ " } " +
+ "}";
+
+ final SailTupleQuery tupleQuery = (SailTupleQuery)
+ cxn.prepareTupleQuery(QueryLanguage.SPARQL, query);
+ tupleQuery.setIncludeInferred(false /* includeInferred */);
+
+ if (INFO) {
+ log.info(query);
+ final TupleQueryResult result = tupleQuery.evaluate();
+ while (result.hasNext()) {
+ log.info(result.next());
+ }
+ }
+
+ final Collection<BindingSet> answer = new LinkedList<BindingSet>();
+ answer.add(createBindingSet());
+
+ // result = tupleQuery.evaluate();
+ // compare(result, answer);
+
+ }
+
+ {
+
+ String query =
+ "prefix bd: <"+BD.NAMESPACE+"> " +
+ "select * " +
+ "where { " +
+ " ?a bd:knows ?b . " +
+ " OPTIONAL { " +
+ " ?b bd:knows ?c . " +
+ " ?c bd:knows ?d . " +
+ " filter(?a != bd:paul) " +
+ " } " +
+ "}";
+
+ final SailTupleQuery tupleQuery = (SailTupleQuery)
+ cxn.prepareTupleQuery(QueryLanguage.SPARQL, query);
+ tupleQuery.setIncludeInferred(false /* includeInferred */);
+
+ if (INFO) {
+ log.info(query);
+ final TupleQueryResult result = tupleQuery.evaluate();
+ while (result.hasNext()) {
+ log.info(result.next());
+ }
+ }
+
+ final Collection<BindingSet> answer = new LinkedList<BindingSet>();
+ answer.add(createBindingSet());
+
+ // result = tupleQuery.evaluate();
+ // compare(result, answer);
+
+ }
+
+ {
+
+ String query =
+ "prefix bd: <"+BD.NAMESPACE+"> " +
+ "select * " +
+ "where { " +
+ " ?a bd:knows ?b . " +
+ " OPTIONAL { " +
+ " ?b bd:knows ?c . " +
+ " ?c bd:knows ?d . " +
+ " filter(?d != bd:leon) " +
+ " } " +
+ "}";
+
+ final SailTupleQuery tupleQuery = (SailTupleQuery)
+ cxn.prepareTupleQuery(QueryLanguage.SPARQL, query);
+ tupleQuery.setIncludeInferred(false /* includeInferred */);
+
+ if (INFO) {
+ log.info(query);
+ final TupleQueryResult result = tupleQuery.evaluate();
+ while (result.hasNext()) {
+ log.info(result.next());
+ }
+ }
+
+ final Collection<BindingSet> answer = new LinkedList<BindingSet>();
+ answer.add(createBindingSet());
+
+ // result = tupleQuery.evaluate();
+ // compare(result, answer);
+
+ }
+
+ } finally {
+ cxn.close();
+ sail.shutDown();
+ }
+
+ }
+
+ private void __testNestedOptionals1() throws Exception {
+
final BigdataSail sail = getSail();
sail.initialize();
final BigdataSailRepository repo = new BigdataSailRepository(sail);
@@ -197,7 +355,7 @@
}
- public void testNestedOptionals2() throws Exception {
+ private void __testNestedOptionals2() throws Exception {
final BigdataSail sail = getSail();
sail.initialize();
This was sent by the SourceForge.net collaborative development platform, the world's largest Open Source development site.
|
