Menu
▾
▴
[Bigdata-commit] SF.net SVN: bigdata:[4130] branches/QUADS_QUERY_BRANCH/bigdata
|
From: <tho...@us...> - 2011-01-19 18:34:52
|
Revision: 4130
http://bigdata.svn.sourceforge.net/bigdata/?rev=4130&view=rev
Author: thompsonbry
Date: 2011-01-19 18:34:43 +0000 (Wed, 19 Jan 2011)
Log Message:
-----------
- Got rid of PipelineJoin.Annotations.OPTIONAL and just test
IPredicate.isOptional() instead of propagating the annotation to the
join.
- Moved CONSTRAINTS back to the PipelineJoin.
- Changed the namespaces of some annotations (IPredicate mainly).
- Modified the various runtime query optimizer test suites to run against small data sets bundled within SVN by default.
- Added the "bar" data set from MRoy and the data generator for that data set.
- Working on a PartitionedJoinGroup utility class which will break down a set of predicates and constraints into a join graph, head plan, and tail plan.
Modified Paths:
--------------
branches/QUADS_QUERY_BRANCH/bigdata/src/java/com/bigdata/bop/BOp.java
branches/QUADS_QUERY_BRANCH/bigdata/src/java/com/bigdata/bop/BOpBase.java
branches/QUADS_QUERY_BRANCH/bigdata/src/java/com/bigdata/bop/IPredicate.java
branches/QUADS_QUERY_BRANCH/bigdata/src/java/com/bigdata/bop/PipelineOp.java
branches/QUADS_QUERY_BRANCH/bigdata/src/java/com/bigdata/bop/ap/Predicate.java
branches/QUADS_QUERY_BRANCH/bigdata/src/java/com/bigdata/bop/controller/JoinGraph.java
branches/QUADS_QUERY_BRANCH/bigdata/src/java/com/bigdata/bop/join/PipelineJoin.java
branches/QUADS_QUERY_BRANCH/bigdata/src/test/com/bigdata/bop/controller/TestAll.java
branches/QUADS_QUERY_BRANCH/bigdata/src/test/com/bigdata/bop/controller/TestJoinGraph.java
branches/QUADS_QUERY_BRANCH/bigdata/src/test/com/bigdata/bop/controller/TestSubqueryOp.java
branches/QUADS_QUERY_BRANCH/bigdata/src/test/com/bigdata/bop/engine/TestQueryEngine.java
branches/QUADS_QUERY_BRANCH/bigdata/src/test/com/bigdata/bop/fed/TestFederatedQueryEngine.java
branches/QUADS_QUERY_BRANCH/bigdata/src/test/com/bigdata/bop/join/TestPipelineJoin.java
branches/QUADS_QUERY_BRANCH/bigdata-rdf/src/test/com/bigdata/bop/rdf/joinGraph/TestJoinGraphOnBSBMData.java
branches/QUADS_QUERY_BRANCH/bigdata-rdf/src/test/com/bigdata/bop/rdf/joinGraph/TestJoinGraphOnBarData.java
branches/QUADS_QUERY_BRANCH/bigdata-rdf/src/test/com/bigdata/bop/rdf/joinGraph/TestJoinGraphOnLubm.java
branches/QUADS_QUERY_BRANCH/bigdata-sails/src/java/com/bigdata/rdf/sail/BigdataEvaluationStrategyImpl.java
branches/QUADS_QUERY_BRANCH/bigdata-sails/src/java/com/bigdata/rdf/sail/Rule2BOpUtility.java
Added Paths:
-----------
branches/QUADS_QUERY_BRANCH/bigdata/src/java/com/bigdata/bop/controller/PartitionedJoinGroup.java
branches/QUADS_QUERY_BRANCH/bigdata/src/test/com/bigdata/bop/controller/TestJGraph.java
branches/QUADS_QUERY_BRANCH/bigdata/src/test/com/bigdata/bop/controller/TestPartitionedJoinGroup.java
branches/QUADS_QUERY_BRANCH/bigdata-rdf/src/resources/data/barData/
branches/QUADS_QUERY_BRANCH/bigdata-rdf/src/resources/data/barData/barData.trig.gz
branches/QUADS_QUERY_BRANCH/bigdata-rdf/src/test/com/bigdata/bop/rdf/joinGraph/AbstractJoinGraphTestCase.java
branches/QUADS_QUERY_BRANCH/bigdata-rdf/src/test/com/bigdata/bop/rdf/joinGraph/GenerateBarData.java
branches/QUADS_QUERY_BRANCH/bigdata-rdf/src/test/com/bigdata/bop/rdf/joinGraph/TestJoinGraphWithRDF.java
Modified: branches/QUADS_QUERY_BRANCH/bigdata/src/java/com/bigdata/bop/BOp.java
===================================================================
--- branches/QUADS_QUERY_BRANCH/bigdata/src/java/com/bigdata/bop/BOp.java 2011-01-19 18:22:38 UTC (rev 4129)
+++ branches/QUADS_QUERY_BRANCH/bigdata/src/java/com/bigdata/bop/BOp.java 2011-01-19 18:34:43 UTC (rev 4130)
@@ -31,8 +31,6 @@
import java.util.List;
import java.util.Map;
-import com.bigdata.bop.IPredicate.Annotations;
-
import cutthecrap.utils.striterators.IPropertySet;
/**
@@ -182,6 +180,13 @@
*/
BOpEvaluationContext getEvaluationContext();
+ /**
+ * Return <code>true</code> iff this operator is a controller.
+ *
+ * @see Annotations#CONTROLLER
+ */
+ boolean isController();
+
// /**
// * Return <code>true</code> iff this operator is an access path which writes
// * on the database.
@@ -248,6 +253,8 @@
/**
* This annotation determines where an operator will be evaluated
* (default {@value #DEFAULT_EVALUATION_CONTEXT}).
+ *
+ * @see BOpEvaluationContext
*/
String EVALUATION_CONTEXT = BOp.class.getName() + ".evaluationContext";
@@ -260,6 +267,8 @@
* arguments. Thus control operators mark a boundary in pipelined
* evaluation. Some examples of control operators include UNION, STEPS,
* and STAR (aka transitive closure).
+ *
+ * @see BOp#isController()
*/
String CONTROLLER = BOp.class.getName()+".controller";
Modified: branches/QUADS_QUERY_BRANCH/bigdata/src/java/com/bigdata/bop/BOpBase.java
===================================================================
--- branches/QUADS_QUERY_BRANCH/bigdata/src/java/com/bigdata/bop/BOpBase.java 2011-01-19 18:22:38 UTC (rev 4129)
+++ branches/QUADS_QUERY_BRANCH/bigdata/src/java/com/bigdata/bop/BOpBase.java 2011-01-19 18:34:43 UTC (rev 4130)
@@ -424,6 +424,12 @@
}
+ public boolean isController() {
+
+ return getProperty(Annotations.CONTROLLER, false);
+
+ }
+
/**
* Set an annotation.
* <p>
Modified: branches/QUADS_QUERY_BRANCH/bigdata/src/java/com/bigdata/bop/IPredicate.java
===================================================================
--- branches/QUADS_QUERY_BRANCH/bigdata/src/java/com/bigdata/bop/IPredicate.java 2011-01-19 18:22:38 UTC (rev 4129)
+++ branches/QUADS_QUERY_BRANCH/bigdata/src/java/com/bigdata/bop/IPredicate.java 2011-01-19 18:34:43 UTC (rev 4130)
@@ -34,7 +34,6 @@
import com.bigdata.bop.ap.filter.BOpFilterBase;
import com.bigdata.bop.ap.filter.BOpTupleFilter;
import com.bigdata.bop.ap.filter.DistinctFilter;
-import com.bigdata.bop.join.PipelineJoin;
import com.bigdata.btree.IRangeQuery;
import com.bigdata.btree.ITuple;
import com.bigdata.btree.ITupleCursor;
@@ -85,7 +84,7 @@
* @see https://sourceforge.net/apps/trac/bigdata/ticket/180 (Migrate
* the RDFS inference and truth maintenance logic to BOPs)
*/
- String RELATION_NAME = "relationName";
+ String RELATION_NAME = IPredicate.class.getName() + ".relationName";
// /**
// * The {@link IKeyOrder} which will be used to read on the relation.
@@ -98,15 +97,9 @@
// String KEY_ORDER = "keyOrder";
/**
- * <code>true</code> iff the predicate is optional (the right operand of
- * a left join).
- *
- * @deprecated This flag is being moved to the join operator (or should
- * it stay with the predicate so we can work with join
- * graphs more easily, but note that join graphs never
- * contain optional joins).
+ * <code>true</code> iff the predicate has SPARQL optional semantics.
*/
- String OPTIONAL = "optional";
+ String OPTIONAL = IPredicate.class.getName() + ".optional";
// /**
// * Constraints on the elements read from the relation.
@@ -146,7 +139,7 @@
*
* @see IRangeQuery#rangeIterator(byte[], byte[], int, int, IFilter)
*/
- String INDEX_LOCAL_FILTER = "indexLocalFilter";
+ String INDEX_LOCAL_FILTER = IPredicate.class.getName() + ".indexLocalFilter";
/**
* An optional {@link BOpFilterBase} to be applied to the elements of
@@ -163,7 +156,7 @@
* one another. You can chain {@link FilterBase} filters together as
* well.
*/
- String ACCESS_PATH_FILTER = "accessPathFilter";
+ String ACCESS_PATH_FILTER = IPredicate.class.getName() + ".accessPathFilter";
/**
* Access path expander pattern. This allows you to wrap or replace the
@@ -192,13 +185,13 @@
*
* @see IAccessPathExpander
*/
- String ACCESS_PATH_EXPANDER = "accessPathExpander";
+ String ACCESS_PATH_EXPANDER = IPredicate.class.getName() + ".accessPathExpander";
/**
* The partition identifier -or- <code>-1</code> if the predicate does
* not address a specific shard.
*/
- String PARTITION_ID = "partitionId";
+ String PARTITION_ID = IPredicate.class.getName() + ".partitionId";
int DEFAULT_PARTITION_ID = -1;
@@ -240,7 +233,7 @@
*
* @see BOpEvaluationContext
*/
- String REMOTE_ACCESS_PATH = "remoteAccessPath";
+ String REMOTE_ACCESS_PATH = IPredicate.class.getName() + ".remoteAccessPath";
boolean DEFAULT_REMOTE_ACCESS_PATH = true;
@@ -307,9 +300,9 @@
* Operators which read or write on the database must declare the
* {@link Annotations#TIMESTAMP} associated with that operation.
*
- * @see Annotations#TIMESTAMP
+ * @see #TIMESTAMP
*/
- String MUTATION = BOp.class.getName() + ".mutation";
+ String MUTATION = IPredicate.class.getName() + ".mutation";
boolean DEFAULT_MUTATION = false;
@@ -317,17 +310,15 @@
* The timestamp (or transaction identifier) used by this operator if it
* reads or writes on the database (no default).
*
- * @see com.bigdata.bop.IPredicate.Annotations#MUTATION
- *
- * @todo Move to {@link IPredicate}?
+ * @see #MUTATION
*/
- String TIMESTAMP = BOp.class.getName() + ".timestamp";
+ String TIMESTAMP = IPredicate.class.getName() + ".timestamp";
- /**
- * An optional {@link IConstraint}[] which places restrictions on the
- * legal patterns in the variable bindings.
- */
- String CONSTRAINTS = PipelineJoin.class.getName() + ".constraints";
+// /**
+// * An optional {@link IConstraint}[] which places restrictions on the
+// * legal patterns in the variable bindings.
+// */
+// String CONSTRAINTS = PipelineJoin.class.getName() + ".constraints";
}
@@ -404,14 +395,9 @@
* For mutation, some {@link IRelation}s may require that all variables
* appearing in the head are bound. This and similar constraints can be
* enforced using {@link IConstraint}s on the {@link IRule}.
- * <p>
- * More control over the behavior of optionals may be gained through the use
- * of an {@link IAccessPathExpander} pattern.
*
* @return <code>true</code> iff this predicate is optional when evaluating
* a JOIN.
- *
- * @deprecated By {@link PipelineJoin.Annotations#OPTIONAL}
*/
public boolean isOptional();
@@ -441,21 +427,21 @@
// */
// public IElementFilter<E> getConstraint();
- /**
- * Return the optional {@link IConstraint}[] to be applied by a join which
- * evaluates this {@link IPredicate}.
- * <p>
- * Note: The {@link Annotations#CONSTRAINTS} are annotated on the
- * {@link IPredicate} rather than the join operators so they may be used
- * with join graphs, which are expressed solely as an unordered set of
- * {@link IPredicate}s. Using join graphs, we are able to do nifty things
- * such as runtime query optimization which would not be possible if the
- * annotations were decorating the joins since we would be unable to
- * dynamically generate the join operators with the necessary annotations.
- *
- * @see Annotations#CONSTRAINTS
- */
- public IConstraint[] constraints();
+// /**
+// * Return the optional {@link IConstraint}[] to be applied by a join which
+// * evaluates this {@link IPredicate}.
+// * <p>
+// * Note: The {@link Annotations#CONSTRAINTS} are annotated on the
+// * {@link IPredicate} rather than the join operators so they may be used
+// * with join graphs, which are expressed solely as an unordered set of
+// * {@link IPredicate}s. Using join graphs, we are able to do nifty things
+// * such as runtime query optimization which would not be possible if the
+// * annotations were decorating the joins since we would be unable to
+// * dynamically generate the join operators with the necessary annotations.
+// *
+// * @see Annotations#CONSTRAINTS
+// */
+// public IConstraint[] constraints();
/**
* Return the optional filter to be evaluated local to the index.
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 2011-01-19 18:22:38 UTC (rev 4129)
+++ branches/QUADS_QUERY_BRANCH/bigdata/src/java/com/bigdata/bop/PipelineOp.java 2011-01-19 18:34:43 UTC (rev 4130)
@@ -91,19 +91,19 @@
boolean DEFAULT_SHARED_STATE = false;
- /**
- * 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 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 used to mark a set of operators belonging to a conditional
Modified: branches/QUADS_QUERY_BRANCH/bigdata/src/java/com/bigdata/bop/ap/Predicate.java
===================================================================
--- branches/QUADS_QUERY_BRANCH/bigdata/src/java/com/bigdata/bop/ap/Predicate.java 2011-01-19 18:22:38 UTC (rev 4129)
+++ branches/QUADS_QUERY_BRANCH/bigdata/src/java/com/bigdata/bop/ap/Predicate.java 2011-01-19 18:34:43 UTC (rev 4130)
@@ -245,12 +245,12 @@
//
// }
- public IConstraint[] constraints() {
+// public IConstraint[] constraints() {
+//
+// return getProperty(IPredicate.Annotations.CONSTRAINTS, null/* defaultValue */);
+//
+// }
- return getProperty(IPredicate.Annotations.CONSTRAINTS, null/* defaultValue */);
-
- }
-
final public IFilter getIndexLocalFilter() {
return (IFilter) getProperty(Annotations.INDEX_LOCAL_FILTER);
Modified: branches/QUADS_QUERY_BRANCH/bigdata/src/java/com/bigdata/bop/controller/JoinGraph.java
===================================================================
--- branches/QUADS_QUERY_BRANCH/bigdata/src/java/com/bigdata/bop/controller/JoinGraph.java 2011-01-19 18:22:38 UTC (rev 4129)
+++ branches/QUADS_QUERY_BRANCH/bigdata/src/java/com/bigdata/bop/controller/JoinGraph.java 2011-01-19 18:34:43 UTC (rev 4130)
@@ -47,13 +47,13 @@
import org.apache.log4j.Logger;
import com.bigdata.bop.BOp;
-import com.bigdata.bop.BOpBase;
import com.bigdata.bop.BOpContext;
import com.bigdata.bop.BOpContextBase;
import com.bigdata.bop.BOpEvaluationContext;
import com.bigdata.bop.BOpIdFactory;
import com.bigdata.bop.BOpUtility;
import com.bigdata.bop.IBindingSet;
+import com.bigdata.bop.IConstraint;
import com.bigdata.bop.IElement;
import com.bigdata.bop.IPredicate;
import com.bigdata.bop.IVariable;
@@ -80,10 +80,10 @@
* A join graph with annotations for estimated cardinality and other details in
* support of runtime query optimization. A join graph is a collection of
* relations and joins which connect those relations. This boils down to a
- * collection of {@link IPredicate}s (selects on relations) and shared variables
- * (which identify joins). Operators other than standard joins (including
- * optional joins, sort, order by, etc.) must be handled downstream from the
- * join graph in a "tail plan".
+ * collection of {@link IPredicate}s (selects on relations), shared variables
+ * (which identify joins), and {@link IConstraint}s (which limit solutions).
+ * Operators other than standard joins (including optional joins, sort, order
+ * by, etc.) must be handled downstream from the join graph in a "tail plan".
*
* @see http://arxiv.org/PS_cache/arxiv/pdf/0810/0810.4809v1.pdf, XQuery Join
* Graph Isolation.
@@ -197,10 +197,10 @@
* approach should be able to handle queries without perfect / covering
* automatically. Then experiment with carrying fewer statement indices
* for quads.
- *
+ *
* @todo Unit test when there are no solutions to the query. In this case there
* will be no paths identified by the optimizer and the final path length
- * becomes zero.
+ * becomes zero.
*/
public class JoinGraph extends PipelineOp {
@@ -214,17 +214,24 @@
*/
public interface Annotations extends PipelineOp.Annotations {
- /**
- * The vertices of the join graph expressed an an {@link IPredicate}[].
- */
- String VERTICES = JoinGraph.class.getName() + ".vertices";
+ /**
+ * The vertices of the join graph, expressed an an {@link IPredicate}[]
+ * (required).
+ */
+ String VERTICES = JoinGraph.class.getName() + ".vertices";
- /**
- * The initial limit for cutoff sampling (default
- * {@value #DEFAULT_LIMIT}).
- */
- String LIMIT = JoinGraph.class.getName() + ".limit";
+ /**
+ * The constraints on the join graph, expressed an an
+ * {@link IConstraint}[] (optional, defaults to no constraints).
+ */
+ String CONSTRAINTS = JoinGraph.class.getName() + ".constraints";
+ /**
+ * The initial limit for cutoff sampling (default
+ * {@value #DEFAULT_LIMIT}).
+ */
+ String LIMIT = JoinGraph.class.getName() + ".limit";
+
int DEFAULT_LIMIT = 100;
/**
@@ -240,12 +247,21 @@
/**
* @see Annotations#VERTICES
*/
- public IPredicate[] getVertices() {
+ public IPredicate<?>[] getVertices() {
return (IPredicate[]) getRequiredProperty(Annotations.VERTICES);
}
+ /**
+ * @see Annotations#CONSTRAINTS
+ */
+ public IConstraint[] getConstraints() {
+
+ return (IConstraint[]) getProperty(Annotations.CONSTRAINTS, null/* none */);
+
+ }
+
/**
* @see Annotations#LIMIT
*/
@@ -264,25 +280,42 @@
}
- public JoinGraph(final NV... anns) {
+ public JoinGraph(final BOp[] args, final NV... anns) {
- this(BOpBase.NOARGS, NV.asMap(anns));
+ this(args, NV.asMap(anns));
}
- public JoinGraph(final BOp[] args, final Map<String, Object> anns) {
+ public JoinGraph(final BOp[] args, final Map<String, Object> anns) {
- super(args, anns);
+ super(args, anns);
- switch (getEvaluationContext()) {
- case CONTROLLER:
- break;
- default:
- throw new UnsupportedOperationException(
- Annotations.EVALUATION_CONTEXT + "="
- + getEvaluationContext());
- }
+ // required property.
+ final IPredicate<?>[] vertices = (IPredicate[]) getProperty(Annotations.VERTICES);
+ if (vertices == null)
+ throw new IllegalArgumentException(Annotations.VERTICES);
+
+ if (vertices.length == 0)
+ throw new IllegalArgumentException(Annotations.VERTICES);
+
+ if (getLimit() <= 0)
+ throw new IllegalArgumentException(Annotations.LIMIT);
+
+ if (getNEdges() <= 0)
+ throw new IllegalArgumentException(Annotations.NEDGES);
+
+ if (!isController())
+ throw new IllegalArgumentException();
+
+ switch (getEvaluationContext()) {
+ case CONTROLLER:
+ break;
+ default:
+ throw new IllegalArgumentException(Annotations.EVALUATION_CONTEXT
+ + "=" + getEvaluationContext());
+ }
+
}
public FutureTask<Void> eval(final BOpContext<IBindingSet> context) {
@@ -383,7 +416,7 @@
/**
* The most recently taken sample of the {@link Vertex}.
*/
- VertexSample sample = null;
+ transient VertexSample sample = null;
Vertex(final IPredicate<?> pred) {
@@ -768,7 +801,7 @@
* the cutoff sample of a join path having this edge except for the
* degenerate case where the edge is the first edge in the join path.
*/
- public EdgeSample sample = null;
+ transient EdgeSample sample = null;
public Edge(final Vertex v1, final Vertex v2,
final Set<IVariable<?>> shared) {
@@ -1560,6 +1593,10 @@
* FIXME CONSTRAINT ORDERING : It is illegal to add a vertex to the
* path if any variable appearing in its CONSTRAINTS would not be
* bound.
+ *
+ * FIXME CONSTRAINT ORDERING : Rather than constraints imposing an
+ * ordering on joins, constraints need to be attached dynamically to
+ * the first join for which their variables are known to be bound.
*/
final EdgeSample edgeSample = e.estimateCardinality(queryEngine,
@@ -1787,7 +1824,31 @@
return sb.toString();
}
- public JGraph(final IPredicate[] v) {
+ /**
+ *
+ * @param v
+ * The vertices of the join graph. These are
+ * {@link IPredicate}s associated with required joins.
+ * @param constraints
+ * The constraints of the join graph (optional). Since all
+ * joins in the join graph are required, constraints are
+ * dynamically attached to the first join in which all of
+ * their variables are bound.
+ *
+ * @throws IllegalArgumentException
+ * if the vertices is <code>null</code>.
+ * @throws IllegalArgumentException
+ * if the vertices is an empty array.
+ * @throws IllegalArgumentException
+ * if any element of the vertices is <code>null</code>.
+ * @throws IllegalArgumentException
+ * if any constraint uses a variable which is never bound by
+ * the given predicates.
+ *
+ * @todo unit test for a constraint using a variable which is never
+ * bound.
+ */
+ public JGraph(final IPredicate[] v, final IConstraint[] constraints) {
if (v == null)
throw new IllegalArgumentException();
@@ -1797,8 +1858,11 @@
V = new Vertex[v.length];
- for (int i = 0; i < v.length; i++) {
+ for (int i = 0; i < v.length; i++) {
+ if (v[i] == null)
+ throw new IllegalArgumentException();
+
V[i] = new Vertex(v[i]);
}
@@ -1833,9 +1897,12 @@
// The set of identified edges for vertices which share vars.
final List<Edge> tmp = new LinkedList<Edge>();
-
+
+ // The set of vertices which share variables.
+ final Set<Vertex> sharedEdgeVertices = new LinkedHashSet<Vertex>();
+
// The set of vertices which do not share variables.
- final List<Vertex> unshared = new LinkedList<Vertex>();
+ final List<Vertex> unsharedEdgeVertices = new LinkedList<Vertex>();
for (int i = 0; i < v.length; i++) {
@@ -1865,31 +1932,44 @@
* or not the join path would bind the variable(s)
* appearing in the CONSTRAINT.
*/
+
+ if (log.isDebugEnabled())
+ log.debug("vertices shared variable(s): vars="
+ + shared + ", v1=" + p1 + ", v2=" + p2);
+
tmp.add(new Edge(V[i], V[j], shared));
+ sharedEdgeVertices.add(V[i]);
+
+ sharedEdgeVertices.add(V[j]);
+
nmatched++;
}
}
- if (nmatched == 0) {
+ if (nmatched == 0 && !sharedEdgeVertices.contains(V[i])) {
/*
* The source vertex does not share any variables.
*/
-
- unshared.add(V[i]);
+ log
+ .warn("Vertex does not share any variables: "
+ + V[i]);
+
+ unsharedEdgeVertices.add(V[i]);
+
}
}
E = tmp.toArray(new Edge[0]);
- this.unshared = unshared.toArray(new Vertex[0]);
+ this.unshared = unsharedEdgeVertices.toArray(new Vertex[0]);
- if(!unshared.isEmpty()) {
+ if(!unsharedEdgeVertices.isEmpty()) {
/*
* FIXME This needs to be supported. We should explore and
@@ -1902,8 +1982,9 @@
* the evaluation).
*/
- throw new UnsupportedOperationException(
- "Some predicates do not share any variables with other predicates.");
+ throw new UnsupportedOperationException(
+ "Some predicates do not share any variables with other predicates: unshared="
+ + unsharedEdgeVertices);
}
@@ -2794,7 +2875,7 @@
private final BOpContext<IBindingSet> context;
- private final JGraph g;
+// private final JGraph g;
private int limit;
@@ -2813,22 +2894,20 @@
// The initial number of edges (1 step paths) to explore.
nedges = getNEdges();
- if (limit <= 0)
- throw new IllegalArgumentException();
+// if (limit <= 0)
+// throw new IllegalArgumentException();
+//
+// if (nedges <= 0)
+// throw new IllegalArgumentException();
- if (nedges <= 0)
- throw new IllegalArgumentException();
+// g = new JGraph(getVertices(), getConstraints());
- final IPredicate[] v = getVertices();
-
- g = new JGraph(v);
-
}
public Void call() throws Exception {
// Create the join graph.
- final JGraph g = new JGraph(getVertices());
+ final JGraph g = new JGraph(getVertices(), getConstraints());
// Find the best join path.
final Path p = g.runtimeOptimizer(context.getRunningQuery()
@@ -2839,7 +2918,7 @@
// Generate the query from the join path.
final PipelineOp queryOp = JoinGraph.getQuery(idFactory, p
- .getPredicates());
+ .getPredicates(), getConstraints());
// Run the query, blocking until it is done.
JoinGraph.runSubquery(context, queryOp);
@@ -2850,27 +2929,27 @@
} // class JoinGraphTask
- /**
- * Places vertices into order by the {@link BOp#getId()} associated with
- * their {@link IPredicate}.
- */
- private static class BOpIdComparator implements Comparator<Vertex> {
+// /**
+// * Places vertices into order by the {@link BOp#getId()} associated with
+// * their {@link IPredicate}.
+// */
+// private static class BOpIdComparator implements Comparator<Vertex> {
+//
+// private static final transient Comparator<Vertex> INSTANCE = new BOpIdComparator();
+//
+//// @Override
+// public int compare(final Vertex o1, final Vertex o2) {
+// final int id1 = o1.pred.getId();
+// final int id2 = o2.pred.getId();
+// if (id1 < id2)
+// return -1;
+// if (id2 > id1)
+// return 1;
+// return 0;
+// }
+//
+// }
- private static final transient Comparator<Vertex> INSTANCE = new BOpIdComparator();
-
-// @Override
- public int compare(final Vertex o1, final Vertex o2) {
- final int id1 = o1.pred.getId();
- final int id2 = o2.pred.getId();
- if (id1 < id2)
- return -1;
- if (id2 > id1)
- return 1;
- return 0;
- }
-
- }
-
/**
* Places edges into order by ascending estimated cardinality. Edges which
* are not weighted are ordered to the end.
@@ -2915,18 +2994,27 @@
* we are not yet handling anything except standard joins in the runtime
* optimizer.
*/
-
- /**
- * Generate a query plan from an ordered collection of predicates.
- *
- * @param p
- * The join path.
- *
- * @return The query plan.
- */
- static public PipelineOp getQuery(final BOpIdFactory idFactory,
- final IPredicate[] preds) {
+ /**
+ * Generate a query plan from an ordered collection of predicates.
+ *
+ * @param p
+ * The join path.
+ *
+ * @return The query plan.
+ *
+ * FIXME Verify that constraints are attached correctly to the
+ * returned query.
+ */
+ static public PipelineOp getQuery(final BOpIdFactory idFactory,
+ final IPredicate[] preds, final IConstraint[] constraints) {
+
+ if (constraints != null && constraints.length != 0) {
+ // FIXME Constraints must be attached to joins.
+ throw new UnsupportedOperationException(
+ "Constraints must be attached to joins!");
+ }
+
final PipelineJoin[] joins = new PipelineJoin[preds.length];
// final PipelineOp startOp = new StartOp(new BOp[] {},
@@ -3191,7 +3279,7 @@
return sharedVars;
}
-
+
/**
* Exception thrown when the join graph does not have any solutions in the
* data (running the query does not produce any results).
Added: branches/QUADS_QUERY_BRANCH/bigdata/src/java/com/bigdata/bop/controller/PartitionedJoinGroup.java
===================================================================
--- branches/QUADS_QUERY_BRANCH/bigdata/src/java/com/bigdata/bop/controller/PartitionedJoinGroup.java (rev 0)
+++ branches/QUADS_QUERY_BRANCH/bigdata/src/java/com/bigdata/bop/controller/PartitionedJoinGroup.java 2011-01-19 18:34:43 UTC (rev 4130)
@@ -0,0 +1,360 @@
+package com.bigdata.bop.controller;
+
+import java.util.Iterator;
+import java.util.LinkedHashMap;
+import java.util.LinkedHashSet;
+import java.util.LinkedList;
+import java.util.List;
+import java.util.Map;
+import java.util.Set;
+
+import com.bigdata.bop.BOpUtility;
+import com.bigdata.bop.IConstraint;
+import com.bigdata.bop.IPredicate;
+import com.bigdata.bop.IVariable;
+import com.bigdata.bop.controller.JoinGraph.NoSolutionsException;
+
+/**
+ * Class accepts a join group and partitions it into a join graph and a tail
+ * plan.
+ * <p>
+ * A join group consists of an ordered collection of {@link IPredicate}s and an
+ * unordered collection of {@link IConstraint}s. {@link IPredicate} representing
+ * non-optional joins are extracted into a {@link JoinGraph} along with any
+ * {@link IConstraint}s whose variables are guaranteed to be bound by the
+ * implied joins.
+ * <p>
+ * The remainder of the {@link IPredicate}s and {@link IConstraint}s form a
+ * "tail plan". {@link IConstraint}s in the tail plan are attached to the last
+ * {@link IPredicate} at which their variable(s) MIGHT have become bound.
+ *
+ * @author <a href="mailto:tho...@us...">Bryan Thompson</a>
+ *
+ * @todo However, how do we manage when there are things like conditional
+ * routing operators?
+ *
+ * @todo The order of the {@link IPredicate}s in the tail plan is currently
+ * unchanged from their given order (optional joins without constraints
+ * can not reduce the selectivity of the query). However, it could be
+ * worthwhile to run optionals with constraints before those without
+ * constraints since the constraints can reduce the selectivity of the
+ * query. If we do this, then we need to reorder the optionals based on
+ * the partial order imposed what variables they MIGHT bind (which are not
+ * bound by the join graph).
+ *
+ * @todo Things like LET can also bind variables. So can a subquery. Analysis of
+ * those will tell us whether the variable will definitely or
+ * conditionally become bound (I am assuming that a LET can conditionally
+ * leave a variable unbound).
+ *
+ * @todo runFirst flag on the expander (for free text search). this should be an
+ * annotation. this can be a headPlan. [There can be constraints which are
+ * evaluated against the head plan. They need to get attached to the joins
+ * generated for the head plan. MikeP writes: There is a free text search
+ * access path that replaces the actual access path for the predicate,
+ * which is meaningless in an of itself because the P is magical.]
+ *
+ * @todo inline APs and get rid of DataSetJoin. Rewrite NG and DG first.
+ *
+ * @todo write a method which returns the set of constraints which should be run
+ * for the last predicate in a given join path (a join path is just an
+ * ordered array of predicates).
+ */
+public class PartitionedJoinGroup {
+
+// private final IPredicate<?>[] headPlan;
+//
+// private final IConstraint[] headPlanConstraints;
+
+ private final IPredicate<?>[] joinGraphPredicates;
+
+ private final IConstraint[] joinGraphConstraints;
+
+ private final IPredicate<?>[] tailPlan;
+
+// private final IConstraint[] tailPlanConstraints;
+
+
+ /**
+ * The {@link IPredicate}s in the join graph (required joins).
+ */
+ public IPredicate<?>[] getJoinGraphPredicates() {
+ return joinGraphPredicates;
+ }
+
+ /**
+ * The {@link IConstraint}s to be applied to the {@link IPredicate}s in the
+ * join graph. Each {@link IConstraint} should be applied as soon as all of
+ * its variable(s) are known to be bound. The constraints are not attached
+ * to the {@link IPredicate}s in the join graph because the evaluation order
+ * of those {@link IPredicate}s is not yet known (it will be determined by a
+ * query optimizer when it decides on an evaluation order for those joins).
+ */
+ public IConstraint[] getJoinGraphConstraints() {
+ return joinGraphConstraints;
+ }
+
+ /**
+ * The {@link IPredicate}s representing optional joins. Any
+ * {@link IConstraint}s having variable(s) NOT bound by the required joins
+ * will already have been attached to the last {@link IPredicate} in the
+ * tail plan in which their variable(S) MIGHT have been bound.
+ */
+ public IPredicate<?>[] getTailPlan() {
+ return tailPlan;
+ }
+
+// private PartitionedJoinGroup(//
+// final IPredicate<?>[] headPlan,//
+// final IConstraint[] headPlanConstraints,//
+// final IPredicate<?>[] joinGraphPredicates,//
+// final IConstraint[] joinGraphConstraints,//
+// final IPredicate<?>[] tailPlan,//
+// final IConstraint[] tailPlanConstraints//
+// ) {
+// this.headPlan = headPlan;
+// this.headPlanConstraints = headPlanConstraints;
+// this.joinGraphPredicates = joinGraphPredicates;
+// this.joinGraphConstraints = joinGraphConstraints;
+// this.tailPlan = tailPlan;
+// this.tailPlanConstraints = tailPlanConstraints;
+// }
+
+ /**
+ * Analyze a set of {@link IPredicate}s representing optional and
+ * non-optional joins and a collection of {@link IConstraint}s, partitioning
+ * them into a join graph and a tail plan.
+ *
+ * @param sourcePreds
+ * The predicates.
+ * @param constraints
+ * The constraints.
+ *
+ * @return A data structure representing both the join graph and the tail
+ * plan.
+ *
+ * @throws IllegalArgumentException
+ * if the source predicates array is <code>null</code>.
+ * @throws IllegalArgumentException
+ * if the source predicates array is empty.
+ * @throws IllegalArgumentException
+ * if any element of the source predicates array is
+ * <code>null</code>.
+ */
+ public PartitionedJoinGroup(//
+ final IPredicate<?>[] sourcePreds,//
+ IConstraint[] constraints) {
+
+ if (sourcePreds == null)
+ throw new IllegalArgumentException();
+ if (sourcePreds.length == 0)
+ throw new IllegalArgumentException();
+
+ if (constraints == null) {
+ // replace with an empty array.
+ constraints = new IConstraint[0];
+ }
+
+ /*
+ * An unordered list of constraints which do not involve ANY variables.
+ * These constraints should be run first, before the join graph.
+ *
+ * @todo add to the class instance fields.
+ */
+ final List<IConstraint> runFirstConstraints = new LinkedList<IConstraint>();
+
+// final List<IPredicate<?>> headPlan = new LinkedList<IPredicate<?>>();
+//
+// final List<IConstraint> headPlanConstraints = new LinkedList<IConstraint>();
+
+ /*
+ * The non-optional predicates.
+ */
+ final List<IPredicate<?>> joinGraphPredicates = new LinkedList<IPredicate<?>>();
+
+ /*
+ * The set of variables bound by the non-optional predicates.
+ */
+ final Set<IVariable<?>> joinGraphVars = new LinkedHashSet<IVariable<?>>();
+
+ /*
+ * An unordered list of those constraints whose variables are known to
+ * be bound by the non-optional predicates.
+ */
+ final List<IConstraint> joinGraphConstraints = new LinkedList<IConstraint>();
+
+ /*
+ * The predicates representing the optional joins.
+ */
+ final List<IPredicate<?>> tailPlan = new LinkedList<IPredicate<?>>();
+
+ /*
+ * An unordered list of those constraints containing at least one
+ * variable known to NOT be bound by the non-optional predicates.
+ */
+ final List<IConstraint> tailPlanConstraints = new LinkedList<IConstraint>();
+
+ /*
+ * Map indicating which constraints are run for which predicate in the
+ * tail plan. The keys are the bopIds of the predicates in the tail
+ * plan. The values are the sets of constraints to run for that tail.
+ */
+ final Map<Integer/* predId */, List<IConstraint>> tailPlanConstraintMap = new LinkedHashMap<Integer, List<IConstraint>>();
+
+ /*
+ * First identify the predicates which correspond to non-optional joins.
+ * All other pipeline operators are inserted into the tail plan in the
+ * order in which they are given.
+ */
+ for (IPredicate<?> p : sourcePreds) {
+ if (p == null)
+ throw new IllegalArgumentException();
+ if (!p.isOptional()) {
+ // non-optional predicate.
+ joinGraphPredicates.add(p);
+ // variables which will be bound by the join graph.
+ final Iterator<IVariable<?>> vitr = BOpUtility
+ .getArgumentVariables(p);
+ while (vitr.hasNext()) {
+ joinGraphVars.add(vitr.next());
+ }
+ } else {
+ // an optional predicate
+ tailPlan.add(p);
+ }
+ }
+
+ /*
+ * Now break the constraints into two groups - those whose variables are
+ * bound by the predicates in the join graph (required joins) and those
+ * having at least one variable bound by an optional join.
+ */
+ for (IConstraint c : constraints) {
+ boolean allFound = true;
+ final Iterator<IVariable<?>> vitr = BOpUtility
+ .getSpannedVariables(c);
+ if (!vitr.hasNext()) {
+ /*
+ * This is a constraint which does not involve any variable so
+ * we should evaluate it as soon as possible. I.e., before the
+ * join graph.
+ */
+ runFirstConstraints.add(c);
+ continue;
+ }
+ while (vitr.hasNext()) {
+ final IVariable<?> var = vitr.next();
+ if (!joinGraphVars.contains(var)) {
+ /*
+ * This constraint will be evaluated against the tail plan.
+ */
+ allFound = false;
+ tailPlanConstraints.add(c);
+ break;
+ }
+ }
+ if (allFound) {
+ /*
+ * This constraint will be evaluated by the join graph for the
+ * first join in in which all of the variables used by the
+ * constraint are known to be bound.
+ */
+ joinGraphConstraints.add(c);
+ }
+ }
+
+ /*
+ * If a variable is not bound by a required predicate, then we attach
+ * any constraint using that variable to the last optional predicate in
+ * which that variable MIGHT become bound.
+ */
+ {
+ /*
+ * Populate a map from each variable not bound in the join graph to
+ * the last index in the tail plan at which it MIGHT become bound.
+ */
+ final Map<IVariable<?>, Integer/* lastIndexOf */> lastIndexOf = new LinkedHashMap<IVariable<?>, Integer>();
+ int indexOf = 0;
+ for (IPredicate<?> p : tailPlan) {
+ final Iterator<IVariable<?>> vitr = BOpUtility
+ .getArgumentVariables(p);
+ while (vitr.hasNext()) {
+ final IVariable<?> var = vitr.next();
+ lastIndexOf.put(var, Integer.valueOf(indexOf));
+ }
+ indexOf++;
+ }
+ /*
+ * For each constraint using at least one variable NOT bound by the
+ * join graph, find the maximum value of lastIndexOf for the
+ * variable(s) in that constraint. That is the index of the operator
+ * in the tail plan to which the constraint should be attached.
+ */
+ for (IConstraint c : tailPlanConstraints) {
+ final Iterator<IVariable<?>> vitr = BOpUtility
+ .getSpannedVariables(c);
+ Integer maxLastIndexOf = null;
+ while (vitr.hasNext()) {
+ final IVariable<?> var = vitr.next();
+ if (joinGraphVars.contains(var)) {
+ // This variable is bound by the join graph.
+ continue;
+ }
+ final Integer tmp = lastIndexOf.get(var);
+ if (tmp == null) {
+ // This variable is never bound by the query.
+ throw new NoSolutionsException(
+ "Variable is never bound: " + var);
+ }
+ if (maxLastIndexOf == null
+ || tmp.intValue() > maxLastIndexOf.intValue()) {
+ maxLastIndexOf = tmp;
+ }
+ } // next variable.
+ if (maxLastIndexOf == null) {
+ // A logic error.
+ throw new AssertionError("maxLastIndexOf is undefined: "
+ + c);
+ }
+ /*
+ * Add the constraint to the last predicate at which any of its
+ * variables MIGHT have become bound.
+ */
+ {
+ /*
+ * The bopId for the predicate in the tail plan for which,
+ * when that predicate is evaluated, we will run this
+ * constraint.
+ */
+ final int predId = tailPlan.get(maxLastIndexOf).getId();
+ /*
+ * The constraint(s) (if any) already associated with that
+ * predicate.
+ */
+ List<IConstraint> tmp = tailPlanConstraintMap.get(predId);
+ if (tmp == null) {
+ tmp = new LinkedList<IConstraint>();
+ tailPlanConstraintMap.put(predId, tmp);
+ }
+ tmp.add(c);
+ }
+ } // next tail plan constraint.
+
+ }
+
+ /*
+ * Assign to instance fields.
+ */
+ // @todo headPlan
+// this.headPlan = null;
+// this.headPlanConstraints = null;
+ this.joinGraphPredicates = joinGraphPredicates
+ .toArray(new IPredicate[joinGraphPredicates.size()]);
+ this.joinGraphConstraints = joinGraphConstraints
+ .toArray(new IConstraint[joinGraphConstraints.size()]);
+ this.tailPlan = tailPlan.toArray(new IPredicate[tailPlan.size()]);
+ // @todo tailPlanConstraintMap
+
+ }
+
+}
Property changes on: branches/QUADS_QUERY_BRANCH/bigdata/src/java/com/bigdata/bop/controller/PartitionedJoinGroup.java
___________________________________________________________________
Added: svn:keywords
+ Id Date Revision Author HeadURL
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 2011-01-19 18:22:38 UTC (rev 4129)
+++ branches/QUADS_QUERY_BRANCH/bigdata/src/java/com/bigdata/bop/join/PipelineJoin.java 2011-01-19 18:34:43 UTC (rev 4130)
@@ -129,18 +129,27 @@
*/
String SELECT = PipelineJoin.class.getName() + ".select";
- /**
- * 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
- * either {@link PipelineOp.Annotations#ALT_SINK_REF} or
- * {@link PipelineOp.Annotations#ALT_SINK_GROUP}.
- *
- * @see #DEFAULT_OPTIONAL
- */
- String OPTIONAL = PipelineJoin.class.getName() + ".optional";
+// /**
+// * 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
+// * either {@link PipelineOp.Annotations#ALT_SINK_REF} or
+// * {@link PipelineOp.Annotations#ALT_SINK_GROUP}.
+// *
+// * @see #DEFAULT_OPTIONAL
+// *
+// * @deprecated We should just inspect
+// * {@link IPredicate.Annotations#OPTIONAL}.
+// */
+// String OPTIONAL = PipelineJoin.class.getName() + ".optional";
+//
+// boolean DEFAULT_OPTIONAL = false;
- boolean DEFAULT_OPTIONAL = false;
-
+ /**
+ * An {@link IConstraint}[] which places restrictions on the legal
+ * patterns in the variable bindings (optional).
+ */
+ String CONSTRAINTS = PipelineJoin.class.getName() + ".constraints";
+
/**
* The maximum parallelism with which the pipeline will consume the
* source {@link IBindingSet}[] chunk.
@@ -435,16 +444,30 @@
}
- /**
- * @see Annotations#OPTIONAL
- */
+ /**
+ * Return the value of {@link IPredicate#isOptional()} for the
+ * {@link IPredicate} associated with this join.
+ *
+ * @see IPredicate.Annotations#OPTIONAL
+ */
public boolean isOptional() {
- return getProperty(Annotations.OPTIONAL, Annotations.DEFAULT_OPTIONAL);
+// return getProperty(Annotations.OPTIONAL, Annotations.DEFAULT_OPTIONAL);
+ return getPredicate().isOptional();
}
/**
+ *
+ * @see Annotations#CONSTRAINTS
+ */
+ public IConstraint[] constraints() {
+
+ return getProperty(Annotations.CONSTRAINTS, null/* defaultValue */);
+
+ }
+
+ /**
* @see Annotations#MAX_PARALLEL
*/
public int getMaxParallel() {
@@ -642,7 +665,7 @@
this.joinOp = joinOp;
this.predicate = joinOp.getPredicate();
- this.constraints = predicate.constraints();
+ this.constraints = joinOp.constraints();
this.maxParallel = joinOp.getMaxParallel();
if (maxParallel < 0)
throw new IllegalArgumentException(Annotations.MAX_PARALLEL
Modified: branches/QUADS_QUERY_BRANCH/bigdata/src/test/com/bigdata/bop/controller/TestAll.java
===================================================================
--- branches/QUADS_QUERY_BRANCH/bigdata/src/test/com/bigdata/bop/controller/TestAll.java 2011-01-19 18:22:38 UTC (rev 4129)
+++ branches/QUADS_QUERY_BRANCH/bigdata/src/test/com/bigdata/bop/controller/TestAll.java 2011-01-19 18:34:43 UTC (rev 4130)
@@ -75,6 +75,12 @@
suite.addTestSuite(TestSubqueryOp.class);
+ suite.addTestSuite(TestPartitionedJoinGroup.class);
+
+ suite.addTestSuite(TestJoinGraph.class);
+
+ suite.addTestSuite(TestJGraph.class);
+
// @todo test STAR (transitive closure).
// suite.addTestSuite(TestStar.class);
Added: branches/QUADS_QUERY_BRANCH/bigdata/src/test/com/bigdata/bop/controller/TestJGraph.java
===================================================================
--- branches/QUADS_QUERY_BRANCH/bigdata/src/test/com/bigdata/bop/controller/TestJGraph.java (rev 0)
+++ branches/QUADS_QUERY_BRANCH/bigdata/src/test/com/bigdata/bop/controller/TestJGraph.java 2011-01-19 18:34:43 UTC (rev 4130)
@@ -0,0 +1,254 @@
+/**
+
+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 Jan 18, 2011
+ */
+
+package com.bigdata.bop.controller;
+
+import com.bigdata.bop.controller.JoinGraph.JGraph;
+
+import junit.framework.TestCase2;
+
+/**
+ * Test suite for {@link JGraph}, which is the core implementation of the
+ * runtime query optimizer logic.
+ *
+ * @author <a href="mailto:tho...@us...">Bryan Thompson</a>
+ * @version $Id$
+ *
+ * @todo There are some operations which depend on equality or hash code
+ * behavior for vertices and perhaps edges so those things should also be
+ * tested.
+ */
+public class TestJGraph extends TestCase2 {
+
+ /**
+ *
+ */
+ public TestJGraph() {
+ }
+
+ /**
+ * @param name
+ */
+ public TestJGraph(String name) {
+ super(name);
+ }
+
+ public void test_something() {
+
+ fail("write tests");
+
+ }
+
+// /**
+// * Test ability to identify shared variables appearing either as predicate
+// * operands or as part of CONSTRAINTS or FILTERS.
+// */
+// public void test_getSharedVariables() {
+// fail("write test");
+// }
+//
+// /**
+// * Test ability to recognize when there is a predicate without any shared
+// * variables.
+// */
+// public void test_noSharedVariables() {
+// fail("write test");
+// }
+//
+// public void test_getMinimumCardinalityEdge() {
+// fail("write test");
+// }
+//
+// public void test_moreEdgesToExecute() {
+// fail("write test");
+// }
+//
+// // @todo also getEdgeCount()
+// public void test_getEdges() {
+// fail("write test");
+// }
+//
+// public void test_getSelectedJoinPath() {
+// fail("write test");
+// }
+//
+// public void test_getBestAlternativeJoinPath() {
+// fail("write test");
+// }
+//
+// public void test_getVertex() {
+// fail("write test");
+// }
+//
+// // getEdge(v1,v2)
+// public void test_getEdge() {
+// fail("write test");
+// }
+//
+// // test ability to obtain a Path which extends another path.
+// public void test_Path_addEdge() {
+// fail("write test");
+// }
+
+// @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;
+//
+// R rel;
+//
+// public void setUp() throws Exception {
+//
+// jnl = new Journal(getProperties());
+//
+// }
+//
+// /**
+// * Create and populate relation in the {@link #namespace}.
+// *
+// * @return The #of distinct entries.
+// */
+// private int loadData(final int scale) {
+//
+// final String[] names = new String[] { "John", "Mary", "Saul", "Paul",
+// "Leon", "Jane", "Mike", "Mark", "Jill", "Jake", "Alex", "Lucy" };
+//
+// final Random rnd = new Random();
+//
+// // #of distinct instances of each name.
+// final int populationSize = Math.max(10, (int) Math.ceil(scale / 10.));
+//
+// // #of trailing zeros for each name.
+// final int nzeros = 1 + (int) Math.ceil(Math.log10(populationSize));
+//
+//// System.out.println("scale=" + scale + ", populationSize="
+//// + populationSize + ", nzeros=" + nzeros);
+//
+// final NumberFormat fmt = NumberFormat.getIntegerInstance();
+// fmt.setMinimumIntegerDigits(nzeros);
+// fmt.setMaximumIntegerDigits(nzeros);
+// fmt.setGroupingUsed(false);
+//
+// // create the relation.
+// final R rel = new R(jnl, namespace, ITx.UNISOLATED, new Properties());
+// rel.create();
+//
+// // data to insert.
+// final E[] a = new E[scale];
+//
+// for (int i = 0; i < scale; i++) {
+//
+// final String n1 = names[rnd.nextInt(names.length)]
+// + fmt.format(rnd.nextInt(populationSize));
+//
+// final String n2 = names[rnd.nextInt(names.length)]
+// + fmt.format(rnd.nextInt(populationSize));
+//
+//// System.err.println("i=" + i + ", n1=" + n1 + ", n2=" + n2);
+//
+// a[i] = new E(n1, n2);
+//
+// }
+//
+// // sort before insert for efficiency.
+// Arrays.sort(a,R.primaryKeyOrder.getComparator());
+//
+// // insert data (the records are not pre-sorted).
+// final long ninserts = rel.insert(new ChunkedArrayIterator<E>(a.length, a, null/* keyOrder */));
+//
+// // Do commit since not scale-out.
+// jnl.commit();
+//
+// // should exist as of the last commit point.
+// this.rel = (R) jnl.getResourceLocator().locate(namespace,
+// ITx.READ_COMMITTED);
+//
+// assertNotNull(rel);
+//
+// return (int) ninserts;
+//
+// }
+//
+// public void tearDown() throws Exception {
+//
+// if (jnl != null) {
+// jnl.destroy();
+// jnl = null;
+// }
+//
+// // clear reference.
+// rel = null;
+//
+// }
+
+// public void test_something() {
+
+//// final int scale = 10000;
+////
+//// final int nrecords = loadData(scale);
+//
+// final IVariable<?> x = Var.var("x");
+//
+// final IVariable<?> y = Var.var("y");
+//
+// final IPredicate<E> p1 = new Predicate<E>(new BOp[] { x, y },
+// new NV(IPredicate.Annotations.RELATION_NAME,
+// new String[] { namespace }),//
+// new NV(IPredicate.Annotations.TIMESTAMP, ITx.READ_COMMITTED)//
+// );
+//
+// final IPredicate<E> p2 = new Predicate<E>(new BOp[] { x, y },
+// new NV(IPredicate.Annotations.RELATION_NAME,
+// new String[] { namespace }),//
+// new NV(IPredicate.Annotations.TIMESTAMP, ITx.READ_COMMITTED)//
+// );
+//
+// final IPredicate<E> p3 = new Predicate<E>(new BOp[] { x, y },
+// new NV(IPredicate.Annotations.RELATION_NAME,
+// new String[] { namespace }),//
+// new NV(IPredicate.Annotations.TIMESTAMP, ITx.READ_COMMITTED)//
+// );
+//
+// new JoinGraph(//
+// new NV(BOp.Annotations.BOP_ID, 1),//
+// new NV(JoinGraph.Annotations.VERTICES,new IPredicate[]{}),//
+// new NV(JoinGraph.Annotations.SAMPLE_SIZE, 100)//
+// );
+//}
+
+}
Property changes on: branches/QUADS_QUERY_BRANCH/bigdata/src/test/com/bigdata/bop/controller/TestJGraph.java
___________________________________________________________________
Added: svn:keywords
+ Id Date Revision Author HeadURL
Modified: branches/QUADS_QUERY_BRANCH/bigdata/src/test/com/bigdata/bop/controller/TestJoinGraph.java
===================================================================
--- branches/QUADS_QUERY_BRANCH/bigdata/src/test/com/bigdata/bop/controller/TestJoinGraph.java 2011-01-19 18:22:38 UTC (rev 4129)
+++ branches/QUADS_QUERY_BRANCH/bigdata/src/test/com/bigdata/bop/controller/TestJoinGraph.java 2011-01-19 18:34:43 UTC (rev 4130)
@@ -29,11 +29,24 @@
import junit.framework.TestCase2;
+import com.bigdata.bop.BOp;
+import com.bigdata.bop.BOpEvaluationContext;
+import com.bigdata.bop.Constant;
+import com.bigdata.bop.IConstraint;
+import com.bigdata.bop.IPredicate;
+import com.bigdata.bop.NV;
+import com.bigdata.bop.Var;
+import com.bigdata.bop.ap.Predicate;
+import com.bigdata.bop.constraint.NEConstant;
+
/**
- * Unit tests for runtime query optimization using {@link JoinGraph}.
+ * Unit tests for the {@link JoinGraph} operator.
*
* @author <a href="mailto:tho...@us...">Bryan Thompson</a>
* @version $Id$
+ *
+ * @todo Test evaluation of the operator as well. A lot of the guts of that are
+ * tested by {@link TestJGraph}.
*/
public class TestJoinGraph extends TestCase2 {
@@ -50,193 +63,224 @@
super(name);
}
- /*
- * Among other things, there are some operations which depend on equality or
- * hash code behavior for vertices and perhaps edges so those things should
- * also be tested.
- */
-
- public void test_getMinimumCardinalityEdge() {
- fail("write test");
- }
+ public void test_ctor() {
- public void test_moreEdgesToExecute() {
- fail("write test");
- }
+ // correct acceptance.
+ {
+ final IPredicate[] vertices = new IPredicate[] {
+ new Predicate(new BOp[]{Var.var("x"),Var.var("y")}),//
+ new Predicate(new BOp[]{Var.var("y"),Var.var("z")}),//
+ };
+ final IConstraint[] constraints = null;
+ final JoinGraph joinGraph = new JoinGraph(new BOp[0],//
+ new NV(JoinGraph.Annotations.VERTICES, vertices),//
+ new NV(JoinGraph.Annotations.CONTROLLER, true), //
+ new NV(JoinGraph.Annotations.EVALUATION_CONTEXT,
+ BOpEvaluationContext.CONTROLLER)//
+ );
+ assertEquals("vertices", vertices, joinGraph.getVertices());
+ assertEquals("cons...
[truncated message content] |
