Menu
▾
▴
[Bigdata-commit] SF.net SVN: bigdata:[7739] branches/BIGDATA_RELEASE_1_3_0
|
From: <tho...@us...> - 2014-01-06 19:10:55
|
Revision: 7739
http://bigdata.svn.sourceforge.net/bigdata/?rev=7739&view=rev
Author: thompsonbry
Date: 2014-01-06 19:10:46 +0000 (Mon, 06 Jan 2014)
Log Message:
-----------
Checkpoint on the RTO integration - See #64 (RTO).
I have reworked the AST2BOpUtility, AST2BOpJoins, and AST2BOpFilters
classes to support reuse of AST2BOpJoins#join() within the RTO and I
have verified (for one query using FILTER (?x != ?y)) that the RTO
will now generate a final query plan which includes conditional
routing operators to materialize variables for filters. However, the
sampling logic for cutoff joins has not yet been modified and will
ignore any filters that require materialization (or perhaps just die
on them). The old versus new integration point is configurable in
AST2BOpRTO so the old behavior can be trivially restored. I have also
added several static booleans into that class to allow us to gradually
enable more capabilities in the RTO integration.
The join graph test suite was not running. It is now hooked into CI.
However, there is not much in there and at least part of it might be
going away (for "fast join graphs").
The bop, AST, SPARQL evaluation test suites are all green.
Modified Paths:
--------------
branches/BIGDATA_RELEASE_1_3_0/bigdata/src/java/com/bigdata/bop/BOpIdFactory.java
branches/BIGDATA_RELEASE_1_3_0/bigdata/src/java/com/bigdata/bop/IdFactory.java
branches/BIGDATA_RELEASE_1_3_0/bigdata/src/java/com/bigdata/bop/joinGraph/PartitionedJoinGroup.java
branches/BIGDATA_RELEASE_1_3_0/bigdata/src/java/com/bigdata/bop/joinGraph/rto/JoinGraph.java
branches/BIGDATA_RELEASE_1_3_0/bigdata/src/test/com/bigdata/bop/TestAll.java
branches/BIGDATA_RELEASE_1_3_0/bigdata/src/test/com/bigdata/bop/joinGraph/rto/TestAll.java
branches/BIGDATA_RELEASE_1_3_0/bigdata/src/test/com/bigdata/bop/joinGraph/rto/TestJGraph.java
branches/BIGDATA_RELEASE_1_3_0/bigdata/src/test/com/bigdata/bop/joinGraph/rto/TestJoinGraph.java
branches/BIGDATA_RELEASE_1_3_0/bigdata-rdf/src/java/com/bigdata/rdf/sparql/ast/eval/AST2BOpContext.java
branches/BIGDATA_RELEASE_1_3_0/bigdata-rdf/src/java/com/bigdata/rdf/sparql/ast/eval/AST2BOpFilters.java
branches/BIGDATA_RELEASE_1_3_0/bigdata-rdf/src/java/com/bigdata/rdf/sparql/ast/eval/AST2BOpJoins.java
branches/BIGDATA_RELEASE_1_3_0/bigdata-rdf/src/java/com/bigdata/rdf/sparql/ast/eval/AST2BOpRTO.java
branches/BIGDATA_RELEASE_1_3_0/bigdata-rdf/src/java/com/bigdata/rdf/sparql/ast/eval/AST2BOpUtility.java
Added Paths:
-----------
branches/BIGDATA_RELEASE_1_3_0/bigdata/src/java/com/bigdata/bop/SimpleIdFactory.java
Modified: branches/BIGDATA_RELEASE_1_3_0/bigdata/src/java/com/bigdata/bop/BOpIdFactory.java
===================================================================
--- branches/BIGDATA_RELEASE_1_3_0/bigdata/src/java/com/bigdata/bop/BOpIdFactory.java 2014-01-06 17:19:27 UTC (rev 7738)
+++ branches/BIGDATA_RELEASE_1_3_0/bigdata/src/java/com/bigdata/bop/BOpIdFactory.java 2014-01-06 19:10:46 UTC (rev 7739)
@@ -1,5 +1,29 @@
+/**
+
+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
+ */
package com.bigdata.bop;
+import java.util.Iterator;
import java.util.LinkedHashSet;
/**
@@ -7,23 +31,102 @@
*/
public class BOpIdFactory implements IdFactory {
- private final LinkedHashSet<Integer> ids = new LinkedHashSet<Integer>();
-
- private int nextId = 0;
-
- public void reserve(int id) {
- ids.add(id);
- }
+ /** The set of reserved bop identifiers. */
+ private LinkedHashSet<Integer> ids;
- public int nextId() {
+ private int nextId = 0;
- while (ids.contains(nextId)) {
+ /**
+ * Reserve a bop id by adding it to a set of known identifiers that will not
+ * be issued by {@link #nextId()}.
+ *
+ * @param id
+ * The identifier.
+ */
+ public void reserve(final int id) {
+
+ synchronized (this) {
+
+ if (ids == null) {
- nextId++;
-
- }
+ // Lazily allocated.
+ ids = new LinkedHashSet<Integer>();
- return nextId++;
- }
-
+ ids.add(id);
+
+ }
+
+ }
+
+ }
+
+ @Override
+ public int nextId() {
+
+ synchronized (this) {
+
+ if (ids != null) {
+
+ while (ids.contains(nextId)) {
+
+ nextId++;
+
+ }
+
+ }
+
+ return nextId++;
+
+ }
+
+ }
+
+ /**
+ * Reserve ids used by the predicates or constraints associated with some
+ * join graph.
+ *
+ * @param preds
+ * The vertices of the join graph.
+ * @param constraints
+ * The constraints of the join graph (optional).
+ */
+ public void reserveIds(final IPredicate<?>[] preds,
+ final IConstraint[] constraints) {
+
+ if (preds == null)
+ throw new IllegalArgumentException();
+
+ final BOpIdFactory idFactory = this;
+
+ for (IPredicate<?> p : preds) {
+
+ idFactory.reserve(p.getId());
+
+ }
+
+ if (constraints != null) {
+
+ for (IConstraint c : constraints) {
+
+ final Iterator<BOp> itr = BOpUtility
+ .preOrderIteratorWithAnnotations(c);
+
+ while (itr.hasNext()) {
+
+ final BOp y = itr.next();
+
+ final Integer anId = (Integer) y
+ .getProperty(BOp.Annotations.BOP_ID);
+
+ if (anId != null)
+ idFactory.reserve(anId.intValue());
+
+ }
+
+ }
+
+ }
+
+ }
+
}
\ No newline at end of file
Modified: branches/BIGDATA_RELEASE_1_3_0/bigdata/src/java/com/bigdata/bop/IdFactory.java
===================================================================
--- branches/BIGDATA_RELEASE_1_3_0/bigdata/src/java/com/bigdata/bop/IdFactory.java 2014-01-06 17:19:27 UTC (rev 7738)
+++ branches/BIGDATA_RELEASE_1_3_0/bigdata/src/java/com/bigdata/bop/IdFactory.java 2014-01-06 19:10:46 UTC (rev 7739)
@@ -1,3 +1,26 @@
+/**
+
+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
+ */
package com.bigdata.bop;
/**
@@ -5,6 +28,9 @@
*/
public interface IdFactory {
+ /**
+ * Issue the next bop identifier.
+ */
public int nextId();
}
Added: branches/BIGDATA_RELEASE_1_3_0/bigdata/src/java/com/bigdata/bop/SimpleIdFactory.java
===================================================================
--- branches/BIGDATA_RELEASE_1_3_0/bigdata/src/java/com/bigdata/bop/SimpleIdFactory.java (rev 0)
+++ branches/BIGDATA_RELEASE_1_3_0/bigdata/src/java/com/bigdata/bop/SimpleIdFactory.java 2014-01-06 19:10:46 UTC (rev 7739)
@@ -0,0 +1,47 @@
+/**
+
+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
+*/
+package com.bigdata.bop;
+
+import java.util.concurrent.atomic.AtomicInteger;
+
+public class SimpleIdFactory implements IdFactory {
+
+ /**
+ * Note: The ids are assigned using {@link AtomicInteger#incrementAndGet()}
+ * so ONE (1) is the first id that will be assigned when we pass in ZERO (0)
+ * as the initial state of the {@link AtomicInteger}.
+ */
+ private final AtomicInteger nextId = new AtomicInteger(0);
+
+ /**
+ * {@inheritDoc}
+ */
+ @Override
+ public int nextId() {
+
+ return nextId.incrementAndGet();
+
+ }
+
+}
Modified: branches/BIGDATA_RELEASE_1_3_0/bigdata/src/java/com/bigdata/bop/joinGraph/PartitionedJoinGroup.java
===================================================================
--- branches/BIGDATA_RELEASE_1_3_0/bigdata/src/java/com/bigdata/bop/joinGraph/PartitionedJoinGroup.java 2014-01-06 17:19:27 UTC (rev 7738)
+++ branches/BIGDATA_RELEASE_1_3_0/bigdata/src/java/com/bigdata/bop/joinGraph/PartitionedJoinGroup.java 2014-01-06 19:10:46 UTC (rev 7739)
@@ -1018,24 +1018,25 @@
/*
* Reserve ids used by the join graph or its constraints.
*/
- {
- for (IPredicate<?> p : preds) {
- idFactory.reserve(p.getId());
- }
- if (constraints != null) {
- for (IConstraint c : constraints) {
- final Iterator<BOp> itr = BOpUtility
- .preOrderIteratorWithAnnotations(c);
- while (itr.hasNext()) {
- final BOp y = itr.next();
- final Integer anId = (Integer) y
- .getProperty(BOp.Annotations.BOP_ID);
- if (anId != null)
- idFactory.reserve(anId.intValue());
- }
- }
- }
- }
+ idFactory.reserveIds(preds, constraints);
+// {
+// for (IPredicate<?> p : preds) {
+// idFactory.reserve(p.getId());
+// }
+// if (constraints != null) {
+// for (IConstraint c : constraints) {
+// final Iterator<BOp> itr = BOpUtility
+// .preOrderIteratorWithAnnotations(c);
+// while (itr.hasNext()) {
+// final BOp y = itr.next();
+// final Integer anId = (Integer) y
+// .getProperty(BOp.Annotations.BOP_ID);
+// if (anId != null)
+// idFactory.reserve(anId.intValue());
+// }
+// }
+// }
+// }
// figure out which constraints are attached to which predicates.
final IConstraint[][] assignedConstraints = PartitionedJoinGroup
Modified: branches/BIGDATA_RELEASE_1_3_0/bigdata/src/java/com/bigdata/bop/joinGraph/rto/JoinGraph.java
===================================================================
--- branches/BIGDATA_RELEASE_1_3_0/bigdata/src/java/com/bigdata/bop/joinGraph/rto/JoinGraph.java 2014-01-06 17:19:27 UTC (rev 7738)
+++ branches/BIGDATA_RELEASE_1_3_0/bigdata/src/java/com/bigdata/bop/joinGraph/rto/JoinGraph.java 2014-01-06 19:10:46 UTC (rev 7739)
@@ -29,6 +29,7 @@
import java.util.LinkedHashMap;
import java.util.Map;
+import java.util.Set;
import java.util.concurrent.Callable;
import java.util.concurrent.FutureTask;
import java.util.concurrent.TimeUnit;
@@ -37,11 +38,11 @@
import com.bigdata.bop.BOp;
import com.bigdata.bop.BOpContext;
-import com.bigdata.bop.BOpIdFactory;
import com.bigdata.bop.BOpUtility;
import com.bigdata.bop.IBindingSet;
import com.bigdata.bop.IConstraint;
import com.bigdata.bop.IPredicate;
+import com.bigdata.bop.IQueryAttributes;
import com.bigdata.bop.IVariable;
import com.bigdata.bop.NV;
import com.bigdata.bop.PipelineOp;
@@ -51,7 +52,12 @@
import com.bigdata.bop.engine.AbstractRunningQuery;
import com.bigdata.bop.engine.IRunningQuery;
import com.bigdata.bop.engine.QueryEngine;
-import com.bigdata.bop.joinGraph.PartitionedJoinGroup;
+import com.bigdata.rdf.sparql.ast.IJoinNode;
+import com.bigdata.rdf.sparql.ast.JoinGroupNode;
+import com.bigdata.rdf.sparql.ast.eval.AST2BOpContext;
+import com.bigdata.rdf.sparql.ast.eval.AST2BOpRTO;
+import com.bigdata.rdf.sparql.ast.optimizers.IASTOptimizer;
+import com.bigdata.util.NT;
import com.bigdata.util.concurrent.Haltable;
import cutthecrap.utils.striterators.ICloseableIterator;
@@ -88,10 +94,11 @@
*/
public interface Annotations extends PipelineOp.Annotations {
- /**
- * The variables which are projected out of the join graph.
- */
- String SELECTED = JoinGraph.class.getName() + ".selected";
+ /**
+ * The variables to be projected out of the join graph (optional). When
+ * <code>null</code>, all variables will be projected out.
+ */
+ String SELECTED = JoinGraph.class.getName() + ".selected";
/**
* The vertices of the join graph, expressed an an {@link IPredicate}[]
@@ -136,12 +143,65 @@
String DEFAULT_SAMPLE_TYPE = SampleType.RANDOM.name();
+ /**
+ * The set of variables that are known to have already been materialized
+ * in the context in which the RTO was invoked.
+ *
+ * FIXME In order to support left-to-right evaluation fully, the
+ * {@link JGraph} needs to accept this, track it as it binds variables,
+ * and pass it through when doing cutoff joins to avoid pipeline
+ * materialization steps for variables that are already known to be
+ * materialized. Otherwise the RTO will assume that it needs to
+ * materialize everything that needs to be materialized for a FILTER and
+ * thus do too much work (which is basically the assumption of bottom-up
+ * evaluation, or if you prefer that it is executing in its own little
+ * world).
+ */
+ String DONE_SET = JoinGraph.class.getName() + ".doneSet";
+
+// /**
+// * The query hints from the dominating AST node (if any). These query
+// * hints will be passed through and made available when we compile the
+// * query plan once the RTO has decided on the join ordering. While the
+// * RTO is running, it needs to override many of the query hints for the
+// * {@link IPredicate}s, {@link PipelineJoin}s, etc. in order to ensure
+// * that the cutoff evaluation semantics are correctly applied while it
+// * is exploring the plan state space for the join graph.
+// */
+// String AST_QUERY_HINTS = JoinGraph.class.getName() + ".astQueryHints";
+
+ /**
+ * The AST {@link JoinGroupNode} for the joins and filters that we are
+ * running through the RTO (required).
+ *
+ * FIXME This should be set by an ASTRTOOptimizer. That class should
+ * rewrite the original join group, replacing some set of joins with a
+ * JoinGraphNode which implements {@link IJoinNode} and gets hooked into
+ * AST2BOpUtility#convertJoinGroup() normally rather than through
+ * expectional processing. This will simplify the code and adhere to the
+ * general {@link IASTOptimizer} pattern and avoid problems with cloning
+ * children out of the {@link JoinGroupNode} when we set it up to run
+ * the RTO. [Eventually, we will need to pass this in rather than the
+ * {@link IPredicate}[] in order to handle JOINs that are not SPs, e.g.,
+ * sub-selects, etc.]
+ */
+ String JOIN_GROUP = JoinGraph.class.getName() + ".joinGroup";
+
+ /**
+ * An {@link NT} object specifying the namespace and timestamp of the KB
+ * view against which the RTO is running. This is necessary in order to
+ * reconstruct the {@link AST2BOpContext} when it comes time to evaluate
+ * either a cutoff join involving filters that need materialization or
+ * the selected join path.
+ */
+ String NT = JoinGraph.class.getName() + ".nt";
+
}
/**
- * Query attribute names for the {@link JoinGraph}. The fully qualified name
- * of the attribute is formed by appending the attribute name to the
- * "bopId-", where <code>bopId</code> is the value returned by
+ * {@link IQueryAttributes} names for the {@link JoinGraph}. The fully
+ * qualified name of the attribute is formed by appending the attribute name
+ * to the "bopId-", where <code>bopId</code> is the value returned by
* {@link BOp#getId()}
*
* @author <a href="mailto:tho...@us...">Bryan
@@ -168,6 +228,10 @@
}
+ /*
+ * JoinGraph operator annotations.
+ */
+
/**
* @see Annotations#SELECTED
*/
@@ -223,6 +287,24 @@
}
+ /**
+ * Return the set of variables that are known to have already been
+ * materialized at the point in the overall query plan where the RTO is
+ * being executed.
+ *
+ * @see Annotations#DONE_SET
+ */
+ @SuppressWarnings("unchecked")
+ public Set<IVariable<?>> getDoneSet() {
+
+ return (Set<IVariable<?>>) getRequiredProperty(Annotations.DONE_SET);
+
+ }
+
+ /*
+ * IQueryAttributes
+ */
+
/**
* Return the computed join path.
*
@@ -301,15 +383,15 @@
super(args, anns);
- // required property.
- final IVariable<?>[] selected = (IVariable[]) getProperty(Annotations.SELECTED);
+ // optional property.
+// final IVariable<?>[] selected = (IVariable[]) getProperty(Annotations.SELECTED);
+//
+// if (selected == null)
+// throw new IllegalArgumentException(Annotations.SELECTED);
+//
+// if (selected.length == 0)
+// throw new IllegalArgumentException(Annotations.SELECTED);
- if (selected == null)
- throw new IllegalArgumentException(Annotations.SELECTED);
-
- if (selected.length == 0)
- throw new IllegalArgumentException(Annotations.SELECTED);
-
// required property.
final IPredicate<?>[] vertices = (IPredicate[]) getProperty(Annotations.VERTICES);
@@ -325,6 +407,18 @@
if (getNEdges() <= 0)
throw new IllegalArgumentException(Annotations.NEDGES);
+ /*
+ * TODO Check DONE_SET, NT, JOIN_NODES. These annotations are required
+ * for the new code path. We should check for their presence. However,
+ * the old code path is used by some unit tests which have not yet been
+ * updated and do not supply these annotations.
+ */
+// // Required.
+// getDoneSet();
+//
+// // Required.
+// getRequiredProperty(Annotations.NT);
+
if (!isController())
throw new IllegalArgumentException();
@@ -345,7 +439,6 @@
}
-
/**
* Evaluation of a {@link JoinGraph}.
*
@@ -400,11 +493,11 @@
final Map<PathIds, EdgeSample> edgeSamples = new LinkedHashMap<PathIds, EdgeSample>();
// Find the best join path.
- final Path p = g.runtimeOptimizer(context.getRunningQuery()
+ final Path path = g.runtimeOptimizer(context.getRunningQuery()
.getQueryEngine(), getLimit(), getNEdges(), edgeSamples);
// Set attribute for the join path result.
- setPath(context.getRunningQuery(), p);
+ setPath(context.getRunningQuery(), path);
// Set attribute for the join path samples.
setSamples(context.getRunningQuery(), edgeSamples);
@@ -413,20 +506,11 @@
final long elapsed_queryOptimizer = mark - begin;
- // Factory avoids reuse of bopIds assigned to the predicates.
- final BOpIdFactory idFactory = new BOpIdFactory();
-
/*
- * Generate the query from the join path.
- *
- * FIXME Update this using StaticAnalysis logic. Also, both this and
- * the JGraph need to handle triples versus named graph versus
- * default graph APs. Further, JGraph should handle filters that
- * require conditional materialization.
+ * Generate the query from the selected join path.
*/
- final PipelineOp queryOp = PartitionedJoinGroup.getQuery(idFactory,
- false/* distinct */, getSelected(), p.getPredicates(),
- getConstraints());
+ final PipelineOp queryOp = AST2BOpRTO.compileJoinGraph(context
+ .getRunningQuery().getQueryEngine(), JoinGraph.this, path);
// Set attribute for the join path samples.
setQueryPlan(context.getRunningQuery(), queryOp);
@@ -482,8 +566,9 @@
/*
* Run the query.
*
- * @todo pass in the source binding sets here and also when sampling the
- * vertices.
+ * TODO Pass in the source binding sets here and also when sampling the
+ * vertices? Otherwise it is as if we are doing bottom-up evaluation (in
+ * which case the doneSet should be empty on entry).
*/
ICloseableIterator<IBindingSet[]> subquerySolutionItr = null;
@@ -505,13 +590,9 @@
null/* mergeSolution */, null/* selectVars */,
null/* constraints */, null/* stats */);
-// System.out.println("nout=" + nout);
-
// verify no problems.
runningSubquery.get();
-// System.out.println("Future Ok");
-
} catch (Throwable t) {
if (Haltable.isTerminationByInterrupt(t)) {
Modified: branches/BIGDATA_RELEASE_1_3_0/bigdata/src/test/com/bigdata/bop/TestAll.java
===================================================================
--- branches/BIGDATA_RELEASE_1_3_0/bigdata/src/test/com/bigdata/bop/TestAll.java 2014-01-06 17:19:27 UTC (rev 7738)
+++ branches/BIGDATA_RELEASE_1_3_0/bigdata/src/test/com/bigdata/bop/TestAll.java 2014-01-06 19:10:46 UTC (rev 7739)
@@ -47,7 +47,7 @@
/**
* @param arg0
*/
- public TestAll(String arg0) {
+ public TestAll(final String arg0) {
super(arg0);
@@ -114,6 +114,9 @@
// high level query optimization and evaluation.
suite.addTest(com.bigdata.bop.controller.TestAll.suite());
+ // join graph processing (RTO, etc).
+ suite.addTest(com.bigdata.bop.joinGraph.TestAll.suite());
+
/*
* Note: This is tested later once we have gone through the core unit
* tests for the services.
Modified: branches/BIGDATA_RELEASE_1_3_0/bigdata/src/test/com/bigdata/bop/joinGraph/rto/TestAll.java
===================================================================
--- branches/BIGDATA_RELEASE_1_3_0/bigdata/src/test/com/bigdata/bop/joinGraph/rto/TestAll.java 2014-01-06 17:19:27 UTC (rev 7738)
+++ branches/BIGDATA_RELEASE_1_3_0/bigdata/src/test/com/bigdata/bop/joinGraph/rto/TestAll.java 2014-01-06 19:10:46 UTC (rev 7739)
@@ -45,7 +45,7 @@
/**
* @param arg0
*/
- public TestAll(String arg0) {
+ public TestAll(final String arg0) {
super(arg0);
@@ -64,7 +64,8 @@
suite.addTestSuite(TestJoinGraph.class);
// runtime query optimizer behavior.
- suite.addTestSuite(TestJGraph.class);
+ // FIXME This test suite is empty. Either test at the AST eval level or add tests here.
+// suite.addTestSuite(TestJGraph.class);
return suite;
Modified: branches/BIGDATA_RELEASE_1_3_0/bigdata/src/test/com/bigdata/bop/joinGraph/rto/TestJGraph.java
===================================================================
--- branches/BIGDATA_RELEASE_1_3_0/bigdata/src/test/com/bigdata/bop/joinGraph/rto/TestJGraph.java 2014-01-06 17:19:27 UTC (rev 7738)
+++ branches/BIGDATA_RELEASE_1_3_0/bigdata/src/test/com/bigdata/bop/joinGraph/rto/TestJGraph.java 2014-01-06 19:10:46 UTC (rev 7739)
@@ -60,15 +60,15 @@
/**
* @param name
*/
- public TestJGraph(String name) {
+ public TestJGraph(final String name) {
super(name);
}
- public void test_something() {
-
- fail("write tests");
-
- }
+// public void test_something() {
+//
+// fail("write tests");
+//
+// }
// /**
// * Test ability to recognize when there is a predicate without any shared
Modified: branches/BIGDATA_RELEASE_1_3_0/bigdata/src/test/com/bigdata/bop/joinGraph/rto/TestJoinGraph.java
===================================================================
--- branches/BIGDATA_RELEASE_1_3_0/bigdata/src/test/com/bigdata/bop/joinGraph/rto/TestJoinGraph.java 2014-01-06 17:19:27 UTC (rev 7738)
+++ branches/BIGDATA_RELEASE_1_3_0/bigdata/src/test/com/bigdata/bop/joinGraph/rto/TestJoinGraph.java 2014-01-06 19:10:46 UTC (rev 7739)
@@ -34,6 +34,7 @@
import com.bigdata.bop.Constant;
import com.bigdata.bop.IConstraint;
import com.bigdata.bop.IPredicate;
+import com.bigdata.bop.IVariable;
import com.bigdata.bop.NV;
import com.bigdata.bop.Var;
import com.bigdata.bop.ap.Predicate;
@@ -75,6 +76,7 @@
};
final IConstraint[] constraints = null;
final JoinGraph joinGraph = new JoinGraph(new BOp[0],//
+ new NV(JoinGraph.Annotations.SELECTED, new IVariable[]{}),//
new NV(JoinGraph.Annotations.VERTICES, vertices),//
new NV(JoinGraph.Annotations.CONTROLLER, true), //
new NV(JoinGraph.Annotations.EVALUATION_CONTEXT,
Modified: branches/BIGDATA_RELEASE_1_3_0/bigdata-rdf/src/java/com/bigdata/rdf/sparql/ast/eval/AST2BOpContext.java
===================================================================
--- branches/BIGDATA_RELEASE_1_3_0/bigdata-rdf/src/java/com/bigdata/rdf/sparql/ast/eval/AST2BOpContext.java 2014-01-06 17:19:27 UTC (rev 7738)
+++ branches/BIGDATA_RELEASE_1_3_0/bigdata-rdf/src/java/com/bigdata/rdf/sparql/ast/eval/AST2BOpContext.java 2014-01-06 19:10:46 UTC (rev 7739)
@@ -28,7 +28,6 @@
import java.util.Map;
import java.util.Properties;
import java.util.UUID;
-import java.util.concurrent.atomic.AtomicInteger;
import java.util.concurrent.atomic.AtomicReference;
import com.bigdata.bop.BOp;
@@ -38,6 +37,7 @@
import com.bigdata.bop.IdFactory;
import com.bigdata.bop.NamedSolutionSetRefUtility;
import com.bigdata.bop.PipelineOp;
+import com.bigdata.bop.SimpleIdFactory;
import com.bigdata.bop.engine.IRunningQuery;
import com.bigdata.bop.engine.QueryEngine;
import com.bigdata.bop.fed.QueryEngineFactory;
@@ -79,7 +79,7 @@
public class AST2BOpContext implements IdFactory, IEvaluationContext {
/**
- * The {@link ASTContainer}
+ * The {@link ASTContainer} and never <code>null</code>.
*/
public final ASTContainer astContainer;
@@ -88,7 +88,7 @@
*
* @see #nextId()
*/
- private final AtomicInteger idFactory;
+ private final IdFactory idFactory;
/**
* The KB instance.
@@ -368,8 +368,9 @@
/**
*
- * @param queryRoot
- * The root of the query.
+ * @param astContainer
+ * The top-level {@link ASTContainer} for the query or update
+ * request to be evaluated (required).
* @param db
* The KB instance.
*
@@ -382,26 +383,32 @@
* {@link FunctionRegistry}.
*/
public AST2BOpContext(final ASTContainer astContainer,
- final AbstractTripleStore db) {
+ final AbstractTripleStore db) {
+ this(astContainer, db, new SimpleIdFactory());
+
+ }
+
+ // Note: Exposed to AST2BOpRTO
+ AST2BOpContext(final ASTContainer astContainer,
+ final AbstractTripleStore db, final IdFactory idFactory) {
+
if (astContainer == null)
throw new IllegalArgumentException();
if (db == null)
throw new IllegalArgumentException();
+ if (idFactory == null)
+ throw new IllegalArgumentException();
+
this.astContainer = astContainer;
this.db = db;
this.optimizers = new DefaultOptimizerList();
- /*
- * Note: The ids are assigned using incrementAndGet() so ONE (1) is the
- * first id that will be assigned when we pass in ZERO (0) as the
- * initial state of the AtomicInteger.
- */
- this.idFactory = new AtomicInteger(0);
+ this.idFactory = idFactory;
this.queryEngine = QueryEngineFactory.getQueryController(db
.getIndexManager());
@@ -496,7 +503,8 @@
@Override
public int nextId() {
- return idFactory.incrementAndGet();
+ return idFactory.nextId();
+// return idFactory.incrementAndGet();
}
Modified: branches/BIGDATA_RELEASE_1_3_0/bigdata-rdf/src/java/com/bigdata/rdf/sparql/ast/eval/AST2BOpFilters.java
===================================================================
--- branches/BIGDATA_RELEASE_1_3_0/bigdata-rdf/src/java/com/bigdata/rdf/sparql/ast/eval/AST2BOpFilters.java 2014-01-06 17:19:27 UTC (rev 7738)
+++ branches/BIGDATA_RELEASE_1_3_0/bigdata-rdf/src/java/com/bigdata/rdf/sparql/ast/eval/AST2BOpFilters.java 2014-01-06 19:10:46 UTC (rev 7739)
@@ -523,10 +523,11 @@
// remove any terms already materialized
terms.removeAll(alreadyMaterialized);
- if (c instanceof INeedsMaterialization && ((INeedsMaterialization) c).getRequirement() == Requirement.ALWAYS) {
-
- // add any new terms to the list of already materialized
- alreadyMaterialized.addAll(terms);
+ if (c instanceof INeedsMaterialization
+ && ((INeedsMaterialization) c).getRequirement() == Requirement.ALWAYS) {
+
+ // add any new terms to the list of already materialized
+ alreadyMaterialized.addAll(terms);
}
Modified: branches/BIGDATA_RELEASE_1_3_0/bigdata-rdf/src/java/com/bigdata/rdf/sparql/ast/eval/AST2BOpJoins.java
===================================================================
--- branches/BIGDATA_RELEASE_1_3_0/bigdata-rdf/src/java/com/bigdata/rdf/sparql/ast/eval/AST2BOpJoins.java 2014-01-06 17:19:27 UTC (rev 7738)
+++ branches/BIGDATA_RELEASE_1_3_0/bigdata-rdf/src/java/com/bigdata/rdf/sparql/ast/eval/AST2BOpJoins.java 2014-01-06 19:10:46 UTC (rev 7739)
@@ -220,7 +220,7 @@
anns.add(new NV(Predicate.Annotations.EVALUATION_CONTEXT,
BOpEvaluationContext.SHARDED));
- pred = (Predicate) pred.setProperty(
+ pred = (Predicate<?>) pred.setProperty(
Predicate.Annotations.REMOTE_ACCESS_PATH, false);
} else {
@@ -267,7 +267,7 @@
*/
anns.add(new NV(Predicate.Annotations.EVALUATION_CONTEXT,
BOpEvaluationContext.SHARDED));
- pred = (Predicate) pred.setProperty(
+ pred = (Predicate<?>) pred.setProperty(
Predicate.Annotations.REMOTE_ACCESS_PATH, false);
} else {
anns.add(new NV(Predicate.Annotations.EVALUATION_CONTEXT,
Modified: branches/BIGDATA_RELEASE_1_3_0/bigdata-rdf/src/java/com/bigdata/rdf/sparql/ast/eval/AST2BOpRTO.java
===================================================================
--- branches/BIGDATA_RELEASE_1_3_0/bigdata-rdf/src/java/com/bigdata/rdf/sparql/ast/eval/AST2BOpRTO.java 2014-01-06 17:19:27 UTC (rev 7738)
+++ branches/BIGDATA_RELEASE_1_3_0/bigdata-rdf/src/java/com/bigdata/rdf/sparql/ast/eval/AST2BOpRTO.java 2014-01-06 19:10:46 UTC (rev 7739)
@@ -26,6 +26,8 @@
*/
package com.bigdata.rdf.sparql.ast.eval;
+import java.util.Arrays;
+import java.util.Collections;
import java.util.LinkedHashMap;
import java.util.LinkedHashSet;
import java.util.LinkedList;
@@ -36,21 +38,33 @@
import com.bigdata.bop.BOp;
import com.bigdata.bop.BOpEvaluationContext;
+import com.bigdata.bop.BOpIdFactory;
import com.bigdata.bop.IConstraint;
+import com.bigdata.bop.IPredicate;
import com.bigdata.bop.IValueExpression;
import com.bigdata.bop.IVariable;
import com.bigdata.bop.NV;
import com.bigdata.bop.PipelineOp;
import com.bigdata.bop.ap.Predicate;
import com.bigdata.bop.ap.SampleIndex.SampleType;
+import com.bigdata.bop.engine.QueryEngine;
+import com.bigdata.bop.joinGraph.PartitionedJoinGroup;
import com.bigdata.bop.joinGraph.rto.JGraph;
import com.bigdata.bop.joinGraph.rto.JoinGraph;
+import com.bigdata.bop.joinGraph.rto.Path;
+import com.bigdata.bop.solutions.ProjectionOp;
+import com.bigdata.journal.IIndexManager;
import com.bigdata.rdf.internal.IV;
import com.bigdata.rdf.internal.constraints.INeedsMaterialization;
+import com.bigdata.rdf.sparql.ast.ASTBase;
+import com.bigdata.rdf.sparql.ast.ASTContainer;
+import com.bigdata.rdf.sparql.ast.IBindingProducerNode;
import com.bigdata.rdf.sparql.ast.IGroupMemberNode;
import com.bigdata.rdf.sparql.ast.JoinGroupNode;
import com.bigdata.rdf.sparql.ast.QueryHints;
import com.bigdata.rdf.sparql.ast.StatementPatternNode;
+import com.bigdata.rdf.store.AbstractTripleStore;
+import com.bigdata.util.NT;
/**
* Integration with the Runtime Optimizer (RTO).
@@ -84,6 +98,70 @@
public class AST2BOpRTO extends AST2BOpJoins {
/**
+ * When <code>true</code>, the RTO will only accept simple joins into the
+ * join graph. Simple joins includes triples-mode joins and filters that do
+ * not have materialization requirements. Non-simple joins includes
+ * quads-mode joins and filters that have materialization contexts.
+ *
+ * TODO Eventually we can drop this. It is being used while we refactor the
+ * RTO to support more complex joins and variable materialization for
+ * filters.
+ */
+ static private final boolean onlySimpleJoins = false;
+
+ /**
+ * When <code>true</code>, the RTO will not accept OPTIONAL joins into the
+ * join graph. Optional joins can not decrease the intermediate cardinality
+ * since they can not eliminate solutions, but they can increase the
+ * intermediate cardinality by finding multiple bindings in the OPTIONAL
+ * join. Therefore, it makes sense to execute optional in an order that
+ * defers as long as possible any increase in the intermediate cardinality.
+ * This is very much the same as ordering required joins, but the OPTIONAL
+ * joins need to be handled AFTER the required joins.
+ *
+ * TODO RTO OPTIONALS: Handle optional SPs in joinGraph by ordering them in
+ * the tail so as to minimize the cost function. Once implemented, we can
+ * drop this field.
+ */
+ static private final boolean onlyRequiredJoins = true;
+
+ /**
+ * When <code>true</code>, the RTO will only accept statement patterns into
+ * the join graph. When <code>false</code>, it will attempt to handle non-SP
+ * joins, e.g., sub-query, exists, property paths, etc.
+ *
+ * TODO Eventually we can drop this.
+ */
+ static private final boolean onlySPs = true;
+
+ /**
+ * When <code>true</code>, the RTO will be applied as in we were doing
+ * bottom-up query optimization. In this case, it WILL NOT receive any
+ * solutions from the upstream operators in the pipeline when it performs
+ * its runtime sampling and it will ignore the <code>doneSet</code> for the
+ * context in which it is invoked. When run in this manner, the RTO *could*
+ * be run before the main query is executed. The only way to facilitate this
+ * at this time would be to lift out the joins on which the RTO would be run
+ * into a named subquery and then optimize that named subquery before the
+ * rest of the query.
+ * <p>
+ * When <code>false</code>, the RTO solutions from upstream operators will
+ * flow into the RTO.
+ *
+ * TODO We could still pass in exogenous solutions for bottom up evaluation.
+ * This would help constraint the RTOs exploration.
+ *
+ * TODO The RTO is not operating 100% in either an left-to-right or a
+ * bottom-up fashion, primarily because we are not passing in either
+ * exogenous bindings or meaningfully using the bindings from the upstream
+ * operator when exploring the join graph. In fact, the RTO could accept a
+ * new sample from the upstream operator in each iteration drawing from
+ * amoung those solutions which had already been materialized by the
+ * upstream operator.
+ */
+ static private final boolean bottomUp = true;
+
+ /**
* Inspect the remainder of the join group. If we can isolate a join graph
* and filters, then we will push them down into an RTO JoinGroup. Since the
* joins have already been ordered by the static optimizer, we can accept
@@ -101,117 +179,190 @@
final JoinGroupNode joinGroup, final Set<IVariable<?>> doneSet,
final AST2BOpContext ctx, final AtomicInteger start) {
- if (ctx.isQuads()) {
+ /*
+ * Snapshot of the doneSet on entry. This gets passed into the RTO.
+ */
+ final Set<IVariable<?>> doneSetIn = Collections
+ .unmodifiableSet(doneSet);
- // FIXME RTO: The RTO does not handle quads yet.
+ if (onlySimpleJoins && ctx.isQuads()) {
+
return left;
}
-
+
+ /*
+ * Consider the join group. See if it is complex enough to warrant
+ * running the RTO.
+ *
+ * TODO Can we also make a decision based on whether there is uncertain,
+ * e.g., a swing in stakes, about the cardinality estimates for the
+ * predicates in the join graph, etc.? This could give us a means to
+ * avoid using the RTO if the join graph is known to run quickly or the
+ * ordering of the joins generated by the static query optimizer is
+ * known to be good.
+ *
+ * TODO The static optimizer could simply annotation join groups for
+ * which it recognizes that it could have a bad join plan.
+ */
final int arity = joinGroup.arity();
- // The predicates for the RTO join group.
- final Set<StatementPatternNode> sps = new LinkedHashSet<StatementPatternNode>();
+ /*
+ * Create a JoinGroup just for the pieces that the RTO will handle.
+ *
+ * FIXME These joins are CLONED right now since they also exist in the
+ * caller's joinGroup. Eventually, this code should be moved into an AST
+ * rewrite and we can then destructively move the children from the
+ * original JoinGroupNode into a JoinGraphNode that will be the AST side
+ * of the RTO.
+ */
+ final JoinGroupNode rtoJoinGroup = new JoinGroupNode();
+ rtoJoinGroup.setQueryHints(joinGroup.getQueryHints());
+
+// final Set<StatementPatternNode> sps = new LinkedHashSet<StatementPatternNode>();
+ // The predicates for the join graph.
@SuppressWarnings("rawtypes")
final Set<Predicate> preds = new LinkedHashSet<Predicate>();
+ // The constraints for the join graph.
final List<IConstraint> constraints = new LinkedList<IConstraint>();
-
- // Examine the remaining joins, stopping at the first non-SP.
- for (int i = start.get(); i < arity; i++) {
-
- final IGroupMemberNode child = (IGroupMemberNode) joinGroup
- .get(i);
-
- if (child instanceof StatementPatternNode) {
- // SP
- final StatementPatternNode sp = (StatementPatternNode) child;
- final boolean optional = sp.isOptional();
- if(optional) {
+ // The #of JOINs accepted into the RTO's join group.
+ int naccepted = 0;
+ {
+ /*
+ * The [doneSet] will be modified iff we actually accept JOINs into the
+ * RTO. Therefore, we also make a temporary copy that we will use to
+ * avoid side-effects if this join group is not complex enough to run
+ * the RTO.
+ */
+ final Set<IVariable<?>> doneSetTmp = new LinkedHashSet<IVariable<?>>(
+ doneSet);
+
+ // Examine the remaining joins, stopping at the first non-SP.
+ for (int i = start.get(); i < arity; i++) {
+
+ final IGroupMemberNode child = (IGroupMemberNode) joinGroup
+ .get(i);
+
+ if (child instanceof StatementPatternNode) {
+ // SP
+ StatementPatternNode sp = (StatementPatternNode) child;
+ final boolean optional = sp.isOptional();
+ if (onlyRequiredJoins && optional) {
+ /*
+ * TODO The RTO does not order optional joins yet so we
+ * can not accept this join into the join graph.
+ */
+ break;
+ }
+
+ final List<IConstraint> attachedConstraints = getJoinConstraints(sp);
+
+ @SuppressWarnings("rawtypes")
+ final Map<IConstraint, Set<IVariable<IV>>> needsMaterialization =
+ new LinkedHashMap<IConstraint, Set<IVariable<IV>>>();
+
+ getJoinConstraints(attachedConstraints, needsMaterialization);
+
+ if (onlySimpleJoins && !needsMaterialization.isEmpty()) {
+ /*
+ * At least one variable requires (or might require)
+ * materialization. This is not currently handled by the RTO
+ * so we break out of the loop.
+ *
+ * TODO Handle materialization patterns within the RTO, in
+ * which case we need to collect up the doneSet here, but
+ * only conditionally since we might not actually execute the
+ * RTO depending on the number of SPs that we find.
+ */
+ break;
+ }
+
+ // // Add constraints to the join for that predicate.
+ // anns.add(new NV(JoinAnnotations.CONSTRAINTS, getJoinConstraints(
+ // constraints, needsMaterialization)));
+
+ // /*
+ // * Pull off annotations before we clear them from the predicate.
+ // */
+ // final Scope scope = (Scope) pred.getProperty(Annotations.SCOPE);
+ //
+ // // true iff this is a quads access path.
+ // final boolean quads = pred.getProperty(Annotations.QUADS,
+ // Annotations.DEFAULT_QUADS);
+ //
+ // // pull of the Sesame dataset before we strip the annotations.
+ // final DatasetNode dataset = (DatasetNode) pred
+ // .getProperty(Annotations.DATASET);
+
+ // Something the RTO can handle.
+ sp = (StatementPatternNode) sp.clone();// TODO Use destructive move.
+// sp.setId(ctx.nextId()); // assign id so we can reference back later.
+ rtoJoinGroup.addChild(sp); // add to group.
+ naccepted++;
/*
- * TODO Handle optional SPs in joinGraph (by ordering them
- * in the tail so as to minimize the cost function).
+ * FIXME RTO: Handle Triples vs Quads, Default vs Named
+ * Graph, and DataSet. This probably means pushing more
+ * logic down into the RTO from AST2BOpJoins.
+ * Path.cutoffJoin() will need to be call through to logic
+ * on this class that does the right thing with named graph
+ * joins, default graph joins, triples mode joins, remote AP
+ * joins, etc. This is the same code that we call through to
+ * when we take the selected join path from the RTO and
+ * compile it into a query plan to fully execute the join
+ * group.
*/
- break;
- }
-
- final List<IConstraint> attachedConstraints = getJoinConstraints(sp);
-
- @SuppressWarnings("rawtypes")
- final Map<IConstraint, Set<IVariable<IV>>> needsMaterialization =
- new LinkedHashMap<IConstraint, Set<IVariable<IV>>>();
-
- getJoinConstraints(attachedConstraints, needsMaterialization);
-
- if (!needsMaterialization.isEmpty()) {
+ final Predicate<?> pred = AST2BOpUtility.toPredicate(sp, ctx);
+ // final int joinId = ctx.nextId();
+ //
+ // // annotations for this join.
+ // final List<NV> anns = new LinkedList<NV>();
+ //
+ // anns.add(new NV(BOp.Annotations.BOP_ID, joinId));
+ preds.add(pred);
+ if (attachedConstraints != null) {
+ // RTO will figure out where to attach these constraints.
+ constraints.addAll(attachedConstraints);
+ }
+
+ } else {
+ // Non-SP.
+ if (onlySPs)
+ break;
/*
- * At least one variable requires (or might require)
- * materialization. This is not currently handled by
- * the RTO so we break out of the loop.
- *
- * TODO Handle materialization patterns within the RTO.
+ * TODO Handle non-SPs in the RTO. See convertJoinGroup()
+ * for how we handle non-SPs during normal query plan
+ * conversion. All of that would also have to be handled
+ * here for the RTO to allow in non-SPs.
*/
- break;
+ throw new UnsupportedOperationException();
}
-
-// // Add constraints to the join for that predicate.
-// anns.add(new NV(JoinAnnotations.CONSTRAINTS, getJoinConstraints(
-// constraints, needsMaterialization)));
+
+ }
-// /*
-// * Pull off annotations before we clear them from the predicate.
-// */
-// final Scope scope = (Scope) pred.getProperty(Annotations.SCOPE);
-//
-// // true iff this is a quads access path.
-// final boolean quads = pred.getProperty(Annotations.QUADS,
-// Annotations.DEFAULT_QUADS);
-//
-// // pull of the Sesame dataset before we strip the annotations.
-// final DatasetNode dataset = (DatasetNode) pred
-// .getProperty(Annotations.DATASET);
+ if (naccepted < 3) {
- // Something the RTO can handle.
- sps.add(sp);
/*
- * FIXME RTO: Handle Triples vs Quads, Default vs Named Graph, and
- * DataSet. This probably means pushing more logic down into
- * the RTO from AST2BOpJoins.
+ * There are not enough joins for the RTO.
+ *
+ * TODO For incremental query construction UIs, it would be
+ * useful to run just the RTO and to run it with even a single
+ * join. This will give us sample values as well as estimates
+ * cardinalities. If the UI has triple patterns that do not join
+ * (yet), then those should be grouped.
*/
- final Predicate<?> pred = AST2BOpUtility.toPredicate(sp, ctx);
-// final int joinId = ctx.nextId();
-//
-// // annotations for this join.
-// final List<NV> anns = new LinkedList<NV>();
-//
-// anns.add(new NV(BOp.Annotations.BOP_ID, joinId));
- preds.add(pred);
- if (attachedConstraints != null) {
- // RTO will figure out where to attach these constraints.
- constraints.addAll(attachedConstraints);
- }
+ return left;
- } else {
- // Non-SP.
- break;
}
- }
-
- if (sps.size() < 3) {
-
/*
- * There are not enough joins for the RTO.
- *
- * TODO For incremental query construction UIs, it would be useful
- * to run just the RTO and to run it with even a single join. This
- * will give us sample values as well as estimates cardinalities. If
- * the UI has triple patterns that do not join (yet), then those
- * should be grouped.
+ * Since we will run the RTO, we now record any variables that are
+ * known to be materialized in order to support the FILTERs
+ * associated with the join group that we feed into the RTO.
*/
- return left;
+ doneSet.addAll(doneSetTmp);
}
-
+
/*
* Figure out which variables are projected out of the RTO.
*
@@ -221,11 +372,15 @@
final Set<IVariable<?>> selectVars = new LinkedHashSet<IVariable<?>>();
{
- for (StatementPatternNode sp : sps) {
+ for (IGroupMemberNode child : rtoJoinGroup.getChildren()) {
+ if (!(child instanceof IBindingProducerNode))
+ continue;
+
// Note: recursive only matters for complex nodes, not SPs.
- ctx.sa.getDefinitelyProducedBindings(sp, selectVars, true/* recursive */);
-
+ ctx.sa.getDefinitelyProducedBindings(
+ (IBindingProducerNode) child, selectVars, true/* recursive */);
+
}
}
@@ -237,12 +392,16 @@
* (unless we are going to run the RTO "bottom up") and build a hash
* index. When the hash index is ready, we can execute the join group.
*/
+
final SampleType sampleType = joinGroup.getProperty(
QueryHints.RTO_SAMPLE_TYPE, QueryHints.DEFAULT_RTO_SAMPLE_TYPE);
+
final int limit = joinGroup.getProperty(QueryHints.RTO_LIMIT,
QueryHints.DEFAULT_RTO_LIMIT);
+
final int nedges = joinGroup.getProperty(QueryHints.RTO_NEDGES,
QueryHints.DEFAULT_RTO_NEDGES);
+
left = new JoinGraph(leftOrEmpty(left),//
new NV(BOp.Annotations.BOP_ID, ctx.nextId()),//
new NV(BOp.Annotations.EVALUATION_CONTEXT,
@@ -256,16 +415,262 @@
preds.toArray(new Predicate[preds.size()])),//
new NV(JoinGraph.Annotations.CONSTRAINTS, constraints
.toArray(new IConstraint[constraints.size()])),//
+ new NV(JoinGraph.Annotations.JOIN_GROUP, rtoJoinGroup),//
new NV(JoinGraph.Annotations.LIMIT, limit),//
new NV(JoinGraph.Annotations.NEDGES, nedges),//
- new NV(JoinGraph.Annotations.SAMPLE_TYPE, sampleType.name())//
+ new NV(JoinGraph.Annotations.SAMPLE_TYPE, sampleType.name()),//
+ new NV(JoinGraph.Annotations.DONE_SET, doneSetIn),//
+ new NV(JoinGraph.Annotations.NT, new NT(ctx.getNamespace(),
+ ctx.getTimestamp()))//
);
// These joins were consumed.
- start.addAndGet(sps.size());
+ start.addAndGet(naccepted);
return left;
}
-
+
+ /**
+ * Compile a join graph into a query plan.
+ *
+ * @param queryEngine
+ * The {@link QueryEngine} on which the RTO has been executing
+ * and on which the returned query plan may be executed.
+ * @param joinGraph
+ * The operator that executed the RTO.
+ * @param path
+ * The join path that was selected for full execution by the RTO
+ * based on deep sampling of the join graph.
+ *
+ * @return The query plan to fully execute that join graph.
+ */
+ public static PipelineOp compileJoinGraph(final QueryEngine queryEngine,
+ final JoinGraph joinGraph, final Path path) {
+
+ if (queryEngine == null)
+ throw new IllegalArgumentException();
+
+ if (joinGraph == null)
+ throw new IllegalArgumentException();
+
+ if (path == null)
+ throw new IllegalArgumentException();
+
+ final IVariable<?>[] selected = joinGraph.getSelected();
+
+ final IPredicate<?>[] predicates = path.getPredicates();
+
+ final IConstraint[] constraints = joinGraph.getConstraints();
+
+ if (onlySimpleJoins) {
+
+ /*
+ * This is the old code. It does not handle variable materialization
+ * for filters.
+ */
+
+ // Factory avoids reuse of bopIds assigned to the predicates.
+ final BOpIdFactory idFactory = new BOpIdFactory();
+
+ return PartitionedJoinGroup.getQuery(idFactory,
+ false/* distinct */, selected, predicates, constraints);
+
+ }
+
+ /*
+ * TODO The RTO is ignoring the doneSet so it always runs all
+ * materialization steps even if some variable is known to be
+ * materialized on entry.
+ */
+ final Set<IVariable<?>> doneSet = joinGraph.getDoneSet();
+
+ /*
+ * The AST JoinGroupNode for the joins and filters that we are running
+ * through the RTO.
+ */
+ final JoinGroupNode rtoJoinGroup = (JoinGroupNode) joinGraph
+ .getRequiredProperty(JoinGraph.Annotations.JOIN_GROUP);
+
+// // Build an index over the bopIds in that JoinGroupNode.
+// final Map<Integer, BOp> index = getIndex(rtoJoinGroup);
+
+ // Factory avoids reuse of bopIds assigned to the predicates.
+ final BOpIdFactory idFactory = new BOpIdFactory();
+
+ /*
+ * Reserve ids used by the join graph or its constraints.
+ */
+ idFactory.reserveIds(predicates, constraints);
+
+ /*
+ * Figure out which constraints are attached to which predicates.
+ *
+ * TODO Can we reconcile this code with the filter assignment code in
+ * AST2BOpFilter? If so, then we can get rid of the
+ * PartitionedJoinGroup.
+ */
+ final IConstraint[][] assignedConstraints = PartitionedJoinGroup
+ .getJoinGraphConstraints(predicates, constraints,
+ null/* knownBound */, true/* pathIsComplete */);
+
+ // Create an execution context for the query.
+ final AST2BOpContext ctx = getExecutionContext(queryEngine,
+ // Identifies the KB instance (namespace and timestamp).
+ (NT) joinGraph.getRequiredProperty(JoinGraph.Annotations.NT));
+
+ // Start with an empty plan.
+ PipelineOp left = null;
+
+ for (int i = 0; i < predicates.length; i++) {
+
+ final Predicate<?> pred = (Predicate<?>) predicates[i];
+
+ final IConstraint[] attachedJoinConstraints = assignedConstraints[i];
+
+ final boolean optional = pred.isOptional();
+
+ /*
+ * Lookup the AST node for that predicate.
+ *
+ * Note: The predicates are assigned bopIds by the RTO starting with
+ * ONE (1). Therefore we substract out ONE from the predicate's id
+ * to find its index into the join group.
+ *
+ * TODO This assumes that the join group does not contain anything
+ * other than the SPs for the predicates that we are using.,
+ *
+ * TODO HINTS: The Predicate's query hints should the hints for that
+ * specific join (aks the SP or other type of IJoinNode), not the
+ * hints for the JoinGroupNode or the JoinGraph operator. We could
+ * just pass the AST nodes themselves from the JoinGroupNode. That
+ * might make things easier, even if it make the query serialization
+ * fatter on a cluster.
+ */
+// final ASTBase astNode = (ASTBase) index.get(pred.getId());
+
+ final ASTBase astNode = (ASTBase) rtoJoinGroup.get(pred.getId() - 1);
+
+ left = join(left, //
+ pred, //
+ optional ? new LinkedHashSet<IVariable<?>>(doneSet)
+ : doneSet, //
+ attachedJoinConstraints == null ? null : Arrays
+ .asList(attachedJoinConstraints),//
+ astNode.getQueryHints(),//
+ ctx);
+
+ }
+
+ if (selected != null && selected.length != 0) {
+
+ // Drop variables that are not projected out.
+ left = applyQueryHints(new ProjectionOp(//
+ leftOrEmpty(left), //
+ new NV(ProjectionOp.Annotations.BOP_ID, idFactory.nextId()),//
+ new NV(ProjectionOp.Annotations.SELECT, selected)//
+ ), rtoJoinGroup, ctx);
+
+ }
+
+ return left;
+
+ }
+
+ /**
+ * Return an execution context that may be used to execute a cutoff join
+ * during sampling or the entire join path once it has been identified.
+ *
+ * @param queryEngine
+ * The query engine on which the RTO is executing.
+ * @param nt
+ * The namespace and timestamp of the KB view against which the
+ * RTO is running.
+ *
+ * @throws RuntimeException
+ * if there is no such KB instance.
+ */
+ private static AST2BOpContext getExecutionContext(
+ final QueryEngine queryEngine, final NT nt) {
+
+ // The index manager that can be used to resolve the KB view.
+ final IIndexManager indexManager = queryEngine.getFederation() == null ? queryEngine
+ .getIndexManager() : queryEngine.getFederation();
+
+ // Resolve the KB instance.
+ final AbstractTripleStore db = (AbstractTripleStore) indexManager
+ .getResourceLocator().locate(nt.getName(), nt.getTimestamp());
+
+ if (db == null)
+ throw new RuntimeException("No such KB? " + nt);
+
+ /*
+ * An empty container. You can not use any of the top-level SPARQL query
+ * conversion routines with this container, but it is enough for the
+ * low-level things that we need to run the RTO.
+ */
+ final ASTContainer astContainer = new ASTContainer(BOp.NOARGS,
+ BOp.NOANNS);
+
+ return...
[truncated message content] |
