Menu
▾
▴
[Bigdata-commit] SF.net SVN: bigdata:[4211] branches/QUADS_QUERY_BRANCH/bigdata/src
|
From: <tho...@us...> - 2011-02-20 21:20:51
|
Revision: 4211
http://bigdata.svn.sourceforge.net/bigdata/?rev=4211&view=rev
Author: thompsonbry
Date: 2011-02-20 21:20:44 +0000 (Sun, 20 Feb 2011)
Log Message:
-----------
Working on unit tests for getSharedVars(), canJoin(), and now canJoinWithConstraints().
Modified Paths:
--------------
branches/QUADS_QUERY_BRANCH/bigdata/src/java/com/bigdata/bop/BOpUtility.java
branches/QUADS_QUERY_BRANCH/bigdata/src/test/com/bigdata/bop/TestAll.java
branches/QUADS_QUERY_BRANCH/bigdata/src/test/com/bigdata/bop/TestBOpUtility.java
Added Paths:
-----------
branches/QUADS_QUERY_BRANCH/bigdata/src/test/com/bigdata/bop/TestBOpUtility_canJoin.java
branches/QUADS_QUERY_BRANCH/bigdata/src/test/com/bigdata/bop/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-20 13:50:40 UTC (rev 4210)
+++ branches/QUADS_QUERY_BRANCH/bigdata/src/java/com/bigdata/bop/BOpUtility.java 2011-02-20 21:20:44 UTC (rev 4211)
@@ -27,6 +27,7 @@
package com.bigdata.bop;
+import java.util.Arrays;
import java.util.Collections;
import java.util.Iterator;
import java.util.LinkedHashMap;
@@ -39,6 +40,7 @@
import org.apache.log4j.Logger;
import com.bigdata.bop.BOp.Annotations;
+import com.bigdata.bop.controller.PartitionedJoinGroup;
import com.bigdata.bop.engine.BOpStats;
import com.bigdata.btree.AbstractNode;
import com.bigdata.relation.accesspath.IAsynchronousIterator;
@@ -1010,41 +1012,41 @@
}
- /**
- * Inject (or replace) an {@link Integer} "rowId" column. This does not have
- * a side-effect on the source {@link IBindingSet}s.
- *
- * @param var
- * The name of the column.
- * @param start
- * The starting value for the identifier.
- * @param in
- * The source {@link IBindingSet}s.
- *
- * @return The modified {@link IBindingSet}s.
- */
- public static IBindingSet[] injectRowIdColumn(final IVariable var,
- final int start, final IBindingSet[] in) {
+// /**
+// * Inject (or replace) an {@link Integer} "rowId" column. This does not have
+// * a side-effect on the source {@link IBindingSet}s.
+// *
+// * @param var
+// * The name of the column.
+// * @param start
+// * The starting value for the identifier.
+// * @param in
+// * The source {@link IBindingSet}s.
+// *
+// * @return The modified {@link IBindingSet}s.
+// */
+// public static IBindingSet[] injectRowIdColumn(final IVariable<?> var,
+// final int start, final IBindingSet[] in) {
+//
+// if (in == null)
+// throw new IllegalArgumentException();
+//
+// final IBindingSet[] out = new IBindingSet[in.length];
+//
+// for (int i = 0; i < out.length; i++) {
+//
+// final IBindingSet bset = in[i].clone();
+//
+// bset.set(var, new Constant<Integer>(Integer.valueOf(start + i)));
+//
+// out[i] = bset;
+//
+// }
+//
+// return out;
+//
+// }
- if (in == null)
- throw new IllegalArgumentException();
-
- final IBindingSet[] out = new IBindingSet[in.length];
-
- for (int i = 0; i < out.length; i++) {
-
- final IBindingSet bset = in[i].clone();
-
- bset.set(var, new Constant<Integer>(Integer.valueOf(start + i)));
-
- out[i] = bset;
-
- }
-
- return out;
-
- }
-
/**
* Return an ordered array of the bopIds associated with an ordered array of
* predicates (aka a join path).
@@ -1077,29 +1079,20 @@
}
/**
- * Return the variable references shared by tw operators. All variables
- * spanned by either {@link BOp} are considered.
+ * Return the variable references shared by two operators. All variables
+ * spanned by either {@link BOp} are considered, regardless of whether they
+ * appear as operands or within annotations.
*
* @param p
* An operator.
* @param c
* Another operator.
*
- * @param p
- * A predicate.
+ * @return The variable(s) in common. This may be an empty set, but it is
+ * never <code>null</code>.
*
- * @param c
- * A constraint.
- *
- * @return The variables in common -or- <code>null</code> iff there are no
- * variables in common.
- *
* @throws IllegalArgumentException
* if the two either reference is <code>null</code>.
- * @throws IllegalArgumentException
- * if the reference are the same.
- *
- * @todo unit tests.
*/
public static Set<IVariable<?>> getSharedVars(final BOp p, final BOp c) {
@@ -1109,8 +1102,12 @@
if (c == null)
throw new IllegalArgumentException();
- if (p == c)
- throw new IllegalArgumentException();
+ /*
+ * Note: This is allowed since both arguments might be the same variable
+ * or constant.
+ */
+// if (p == c)
+// throw new IllegalArgumentException();
// The set of variables which are shared.
final Set<IVariable<?>> sharedVars = new LinkedHashSet<IVariable<?>>();
@@ -1154,4 +1151,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(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.
+ */
+ 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/test/com/bigdata/bop/TestAll.java
===================================================================
--- branches/QUADS_QUERY_BRANCH/bigdata/src/test/com/bigdata/bop/TestAll.java 2011-02-20 13:50:40 UTC (rev 4210)
+++ branches/QUADS_QUERY_BRANCH/bigdata/src/test/com/bigdata/bop/TestAll.java 2011-02-20 21:20:44 UTC (rev 4211)
@@ -73,6 +73,12 @@
// counting variables, etc.
suite.addTestSuite(TestBOpUtility.class);
+ // unit tests for allowing joins based on shared variables in preds.
+ suite.addTestSuite(TestBOpUtility_canJoin.class);
+
+ // more complex logic for join paths.
+ suite.addTestSuite(TestBOpUtility_canJoinUsingConstraints.class);
+
// constraint operators (EQ, NE, etc).
suite.addTest(com.bigdata.bop.constraint.TestAll.suite());
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 2011-02-20 13:50:40 UTC (rev 4210)
+++ branches/QUADS_QUERY_BRANCH/bigdata/src/test/com/bigdata/bop/TestBOpUtility.java 2011-02-20 21:20:44 UTC (rev 4211)
@@ -29,11 +29,13 @@
import java.util.Iterator;
import java.util.Map;
+import java.util.Set;
import java.util.concurrent.FutureTask;
import junit.framework.TestCase2;
-import junit.framework.TestCase2;
+import com.bigdata.bop.ap.Predicate;
+import com.bigdata.bop.constraint.BOpConstraint;
/**
* Unit tests for {@link BOpUtility}.
@@ -296,7 +298,7 @@
// .annotationOpPreOrderIterator(op2);
// while (itr.hasNext()) {
// final BOp t = itr.next();
-// System.out.println(i + " : " + t);// @todo uncomment
+//// System.out.println(i + " : " + t);
//// assertTrue("index=" + i + ", expected=" + expected[i] + ", actual="
//// + t, expected[i].equals(t));
// i++;
@@ -828,5 +830,199 @@
}
}
+
+ /**
+ * Unit test for correct rejection of illegal arguments.
+ *
+ * @see BOpUtility#getSharedVars(BOp, BOp)
+ */
+ public void test_getSharedVariables_correctRejection() {
+
+ // correct rejection w/ null arg.
+ try {
+ BOpUtility.getSharedVars(Var.var("x"), null);
+ fail("Expecting: " + IllegalArgumentException.class);
+ } catch (IllegalArgumentException ex) {
+ if (log.isInfoEnabled())
+ log.info("Ignoring expected exception: " + ex);
+ }
+
+ // correct rejection w/ null arg.
+ try {
+ BOpUtility.getSharedVars(null, Var.var("x"));
+ fail("Expecting: " + IllegalArgumentException.class);
+ } catch (IllegalArgumentException ex) {
+ if (log.isInfoEnabled())
+ log.info("Ignoring expected exception: " + ex);
+ }
+
+ }
+
+ /**
+ * Unit test for correct identification of cases in which there are no
+ * shared variables.
+ *
+ * @see BOpUtility#getSharedVars(BOp, BOp)
+ */
+ @SuppressWarnings("unchecked")
+ public void test_getSharedVariables_nothingShared() {
+
+ // nothing shared.
+ assertTrue(BOpUtility.getSharedVars(Var.var("x"), Var.var("y"))
+ .isEmpty());
+
+ // nothing shared.
+ assertTrue(BOpUtility.getSharedVars(Var.var("x"),
+ new Constant<String>("x")).isEmpty());
+
+ // nothing shared.
+ assertTrue(BOpUtility.getSharedVars(//
+ Var.var("x"),//
+ new Predicate(new BOp[] { Var.var("y"), Var.var("z") },//
+ (Map) null/* annotations */)//
+ ).isEmpty());
+
+ // nothing shared.
+ assertTrue(BOpUtility.getSharedVars(//
+ Var.var("x"),//
+ new Predicate(new BOp[] { Var.var("y"), Var.var("z") },//
+ new NV("name", "value")//
+ )).isEmpty());
+
+ }
+
+ /**
+ * Unit test for correct identification of cases in which there are shared
+ * variables.
+ *
+ * @see BOpUtility#getSharedVars(BOp, BOp)
+ */
+ @SuppressWarnings("unchecked")
+ public void test_getSharedVariables_somethingShared() {
+
+ // two variables
+ assertSameVariables(//
+ new IVariable[] { Var.var("x") }, //
+ BOpUtility.getSharedVars(//
+ Var.var("x"), //
+ Var.var("x")//
+ ));
+
+ // variable and expression.
+ assertSameVariables(//
+ new IVariable[] { Var.var("x") }, //
+ BOpUtility.getSharedVars(//
+ Var.var("x"), //
+ new BOpBase(//
+ new BOp[] { new Constant<String>("x"),
+ Var.var("x") },//
+ null// annotations
+ )//
+ ));
+
+ // expression and variable.
+ assertSameVariables(//
+ new IVariable[] { Var.var("x") }, //
+ BOpUtility.getSharedVars(//
+ new BOpBase(//
+ new BOp[] { new Constant<String>("x"),
+ Var.var("x") },//
+ null// annotations
+ ),//
+ Var.var("x") //
+ ));
+
+ // variable and predicate w/o annotations.
+ assertSameVariables(//
+ new IVariable[] { Var.var("x") }, //
+ BOpUtility.getSharedVars(//
+ Var.var("x"),//
+ new Predicate(new BOp[] { Var.var("y"), Var.var("x") },//
+ (Map) null/* annotations */)//
+ ));
+
+ // predicate w/o annotations and variable.
+ assertSameVariables(//
+ new IVariable[] { Var.var("x") }, //
+ BOpUtility.getSharedVars(//
+ new Predicate(new BOp[] { Var.var("y"), Var.var("x") },//
+ (Map) null/* annotations */),//
+ Var.var("x")//
+ ));
+
+ // variable and predicate w/ annotations (w/o var).
+ assertSameVariables(//
+ new IVariable[] { Var.var("x") }, //
+ BOpUtility.getSharedVars(//
+ Var.var("x"),//
+ new Predicate(new BOp[] { Var.var("x"), Var.var("z") },//
+ new NV("name", "value")//
+ )));
+
+ // variable and predicate w/ annotations (w/ same var).
+ assertSameVariables(//
+ new IVariable[] { Var.var("x") }, //
+ BOpUtility.getSharedVars(//
+ Var.var("x"),//
+ new Predicate(new BOp[] { Var.var("y"), Var.var("z") },//
+ new NV("name", Var.var("x"))//
+ )));
+
+ // variable and predicate w/ annotations (w/ another var).
+ assertSameVariables(//
+ new IVariable[] { /*Var.var("x")*/ }, //
+ BOpUtility.getSharedVars(//
+ Var.var("x"),//
+ new Predicate(new BOp[] { Var.var("y"), Var.var("z") },//
+ new NV("name", Var.var("z"))//
+ )));
+
+ // two predicates
+ assertSameVariables(//
+ new IVariable[] { Var.var("y"), Var.var("z") }, //
+ BOpUtility.getSharedVars(//
+ new Predicate(new BOp[] { Var.var("y"), Var.var("z") },//
+ new NV("name", Var.var("z"))//
+ ), //
+ new Predicate(new BOp[] { Var.var("y"), Var.var("z") },//
+ new NV("name", Var.var("x"))//
+ )//
+ ));
+
+ // two predicates
+ assertSameVariables(//
+ new IVariable[] { Var.var("x"), Var.var("y"), Var.var("z") }, //
+ BOpUtility.getSharedVars(//
+ new Predicate(new BOp[] { Var.var("y"), Var.var("x") },//
+ new NV("name", Var.var("z"))//
+ ), //
+ new Predicate(new BOp[] { Var.var("y"), Var.var("z") },//
+ new NV("name", Var.var("x"))//
+ )//
+ ));
+
+ }
+ /**
+ * Test helper.
+ * @param expected The expected variables in any order.
+ * @param actual A set of variables actually reported.
+ */
+ private static void assertSameVariables(final IVariable<?>[] expected,
+ final Set<IVariable<?>> actual) {
+
+ for(IVariable<?> var : expected) {
+
+ if(!actual.contains(var)) {
+
+ fail("Expecting: "+var);
+
+ }
+
+ }
+
+ assertEquals("size", expected.length, actual.size());
+
+ }
+
}
Added: branches/QUADS_QUERY_BRANCH/bigdata/src/test/com/bigdata/bop/TestBOpUtility_canJoin.java
===================================================================
--- branches/QUADS_QUERY_BRANCH/bigdata/src/test/com/bigdata/bop/TestBOpUtility_canJoin.java (rev 0)
+++ branches/QUADS_QUERY_BRANCH/bigdata/src/test/com/bigdata/bop/TestBOpUtility_canJoin.java 2011-02-20 21:20:44 UTC (rev 4211)
@@ -0,0 +1,147 @@
+/**
+
+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;
+
+import com.bigdata.bop.ap.Predicate;
+
+import junit.framework.TestCase2;
+
+/**
+ * Unit tests for {@link BOpUtility#canJoin(IPredicate, IPredicate)}
+ *
+ * @author <a href="mailto:tho...@us...">Bryan Thompson</a>
+ * @version $Id$
+ */
+public class TestBOpUtility_canJoin extends TestCase2 {
+
+ /**
+ *
+ */
+ public TestBOpUtility_canJoin() {
+ }
+
+ /**
+ * @param name
+ */
+ public TestBOpUtility_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 {
+ BOpUtility.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 {
+ BOpUtility.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 BOpUtility#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(BOpUtility.canJoin(p1, p2));
+
+ // share z
+ assertTrue(BOpUtility.canJoin(p2, p3));
+
+ // share z
+ assertFalse(BOpUtility.canJoin(p1, p3));
+
+ // shares (x,y) with self.
+ assertTrue(BOpUtility.canJoin(p1, p1));
+
+ }
+
+ /**
+ * Verify that joins are not permitted when the variables are
+ * only shared via an annotation.
+ *
+ * @see BOpUtility#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(BOpUtility.canJoin(p1, p2));
+
+ }
+
+}
Property changes on: branches/QUADS_QUERY_BRANCH/bigdata/src/test/com/bigdata/bop/TestBOpUtility_canJoin.java
___________________________________________________________________
Added: svn:keywords
+ Id Date Revision Author HeadURL
Added: branches/QUADS_QUERY_BRANCH/bigdata/src/test/com/bigdata/bop/TestBOpUtility_canJoinUsingConstraints.java
===================================================================
--- branches/QUADS_QUERY_BRANCH/bigdata/src/test/com/bigdata/bop/TestBOpUtility_canJoinUsingConstraints.java (rev 0)
+++ branches/QUADS_QUERY_BRANCH/bigdata/src/test/com/bigdata/bop/TestBOpUtility_canJoinUsingConstraints.java 2011-02-20 21:20:44 UTC (rev 4211)
@@ -0,0 +1,494 @@
+/**
+
+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;
+
+import java.util.Map;
+
+import junit.framework.TestCase2;
+
+import com.bigdata.bop.ap.Predicate;
+import com.bigdata.bop.constraint.AND;
+import com.bigdata.bop.constraint.BOpConstraint;
+import com.bigdata.bop.controller.JoinGraph.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.
+ *
+ * @see BOpUtility#canJoin(IPredicate, IPredicate)
+ * @see BOpUtility#canJoinUsingConstraints(IPredicate[], IPredicate,
+ * IConstraint[])
+ * @see JGraph
+ *
+ * @author <a href="mailto:tho...@us...">Bryan Thompson</a>
+ * @version $Id$
+ */
+//@SuppressWarnings("unchecked")
+public class TestBOpUtility_canJoinUsingConstraints extends TestCase2 {
+
+ /**
+ *
+ */
+ public TestBOpUtility_canJoinUsingConstraints() {
+ }
+
+ /**
+ * @param name
+ */
+ public TestBOpUtility_canJoinUsingConstraints(String name) {
+ super(name);
+ }
+
+ /**
+ * Unit tests to verify that arguments are validated.
+ *
+ * @see BOpUtility#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 {
+ BOpUtility.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 {
+ BOpUtility.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 {
+ BOpUtility.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 {
+ BOpUtility.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 {
+ BOpUtility.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 {
+ BOpUtility.canJoinUsingConstraints(//
+ new IPredicate[] { p2 }, // path
+ p1,// vertex
+ new IConstraint[] { //
+ 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 BOpConstraint {
+
+ 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 accept(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 BOpConstraint {
+
+ 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 accept(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 = 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 = 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 = 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 };
+
+ /**
+ * path=[p0], vertex=p2, constraints=[].
+ */
+ public void test_canJoinUsingConstraints_01() {
+
+ // share ?product
+ assertTrue(BOpUtility.canJoin(p0, p2));
+ assertTrue(BOpUtility.canJoinUsingConstraints(//
+ new IPredicate[] { p0 }, // path
+ p2,// vertex
+ new IConstraint[0]// constraints
+ ));
+
+ }
+
+ /**
+ * path=[p0], vertex=p2, constraints=[].
+ *
+ * @todo Test w/o any constraints or with all constraints. Testing with only
+ * some of the constraints does not add much here (we probably do not
+ * need to have [c0] defined for this set of unit tests).
+ *
+ * @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>
+ */
+ public void test_canJoinUsingConstraints_02() {
+
+ // share ?product
+ assertTrue(BOpUtility.canJoin(p0, p2));
+ assertTrue(BOpUtility.canJoinUsingConstraints(//
+ new IPredicate[] { p0 }, // path
+ p2,// vertex
+ new IConstraint[0]// constraints
+ ));
+
+ }
+
+}
Property changes on: branches/QUADS_QUERY_BRANCH/bigdata/src/test/com/bigdata/bop/TestBOpUtility_canJoinUsingConstraints.java
___________________________________________________________________
Added: svn:keywords
+ Id Date Revision Author HeadURL
This was sent by the SourceForge.net collaborative development platform, the world's largest Open Source development site.
|
