com.bigdata.rdf.sparql.ast.eval

Class AST2BOpRTO

java.lang.Object

com.bigdata.rdf.sparql.ast.eval.AST2BOpBase

com.bigdata.rdf.sparql.ast.eval.AST2BOpFilters

com.bigdata.rdf.sparql.ast.eval.AST2BOpJoins

com.bigdata.rdf.sparql.ast.eval.AST2BOpRTO

Direct Known Subclasses:

AST2BOpUtility

public class AST2BOpRTO
extends AST2BOpJoins

Integration with the Runtime Optimizer (RTO).

Note: The RTO currently uses bottom-up evaluation to solve the join graph and generate a sub-query plan with an optimized join ordering. It uses left-to-right evaluation to pass pipeline solutions through the optimized subquery.

Author:

Bryan Thompson

See Also:

Runtime Query Optimization, Integrate RTO into SAIL, ROX , JoinGraph, JGraph

Nested Class Summary

Nested Classes

Modifier and Type	Class and Description
static interface	AST2BOpRTO.Annotations

Field Summary

Fields

Modifier and Type	Field and Description
static org.apache.log4j.Logger	log

Constructor Summary

Constructors

Constructor and Description
AST2BOpRTO()

Method Summary

Methods

Modifier and Type	Method and Description
static PipelineOp	compileJoinGraph(QueryEngine queryEngine, JoinGraph joinGraph, Path path) Compile a join graph into a query plan.
protected static PipelineOp	convertRTOJoinGraph(PipelineOp left, JoinGroupNode joinGroup, Set<IVariable<?>> doneSet, AST2BOpContext ctx, AtomicInteger start) Inspect the remainder of the join group.
static EdgeSample	cutoffJoin(QueryEngine queryEngine, JoinGraph joinGraph, int limit, IPredicate<?>[] predicates, IConstraint[] constraints, boolean pathIsComplete, SampleBase sourceSample) Cutoff join of the last vertex in the join path.

Methods inherited from class com.bigdata.rdf.sparql.ast.eval.AST2BOpJoins

join

Methods inherited from class com.bigdata.rdf.sparql.ast.eval.AST2BOpFilters

addChunkedMaterializationStep, addMaterializationSteps1, addMaterializationSteps2, addMaterializationSteps3, addNonConditionalMaterializationSteps, getJoinConstraints, getJoinConstraints, getJoinConstraints2

Methods inherited from class com.bigdata.rdf.sparql.ast.eval.AST2BOpBase

applyQueryHints, applyQueryHints, leftOrEmpty

Methods inherited from class java.lang.Object

clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait

Field Detail

log

public static final transient org.apache.log4j.Logger log

Constructor Detail

AST2BOpRTO

public AST2BOpRTO()

Method Detail

convertRTOJoinGraph

protected static PipelineOp convertRTOJoinGraph(PipelineOp left,
                             JoinGroupNode joinGroup,
                             Set<IVariable<?>> doneSet,
                             AST2BOpContext ctx,
                             AtomicInteger start)

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 them in sequence along with any attachable filters and (if we get at least 3 predicates) push them down into an RTO join group.

Note: Two predicates in a join group is not enough for the RTO to provide a different join ordering. Both the static optimizer and the RTO will always choose the AP with the smaller cardinality to run first. If there are only 2 predicates, then the other predicate will run second. You need at least three predicates before the RTO could provide a different answer.

compileJoinGraph

public static PipelineOp compileJoinGraph(QueryEngine queryEngine,
                          JoinGraph joinGraph,
                          Path path)

Compile a join graph into a query plan.

Parameters:

queryEngine - The QueryEngine on which the RTO has been executing and on which the returned query plan may be executed.

joinGraph - The operator that executed the RTO.

path - The join path that was selected for full execution by the RTO based on deep sampling of the join graph.

Returns:

The query plan to fully execute that join graph. FIXME RTO: Modify this to use AST2BOpUtility#convertJoinGroup(). We would have to reorder the joins in the JoinGraph.Annotations#JOIN_GROUP into the ordering specified in the Path and make sure that convertJoinGroup() did not attempt to recursively reapply the RTO. This will get rid of one of the few remaining uses of PartitionedJoinGroup.

cutoffJoin

public static EdgeSample cutoffJoin(QueryEngine queryEngine,
                    JoinGraph joinGraph,
                    int limit,
                    IPredicate<?>[] predicates,
                    IConstraint[] constraints,
                    boolean pathIsComplete,
                    SampleBase sourceSample)
                             throws Exception

Cutoff join of the last vertex in the join path.

The caller is responsible for protecting against needless re-sampling. This includes cases where a sample already exists at the desired sample limit and cases where the sample is already exact.

Parameters:

queryEngine - The query engine.

joinGraph - The pipeline operator that is executing the RTO. This defines the join graph (vertices, edges, and constraints) and also provides access to the AST and related metadata required to execute the join graph.

limit - The limit for the cutoff join.

predicates - The path segment, which must include the target vertex as the last component of the path segment.

constraints - The constraints declared for the join graph (if any). The appropriate constraints will be applied based on the variables which are known to be bound as of the cutoff join for the last vertex in the path segment.

pathIsComplete - true iff all vertices in the join graph are incorporated into this path.

sourceSample - The input sample for the cutoff join. When this is a one-step estimation of the cardinality of the edge, then this sample is taken from the VertexSample. When the edge (vSource, vTarget) extends some Path, then this is taken from the EdgeSample for that Path.

Returns:

The result of sampling that edge.

Throws:

Exception