com.bigdata.bop.joinGraph.rto

Class Path

java.lang.Object

com.bigdata.bop.joinGraph.rto.Path

public class Path
extends Object

A join path is an ordered sequence of N vertices and represents an ordered series of N-1 joins.

During exploration, the Path is used to develop an estimate of the cost of different join paths which explore the vertices in a join graph, possibly under some set of IConstraints. The estimated cost of the join path is developed from a sample of the initial Vertex followed by the cutoff sample of each join in the join path. Join paths may be re-sampled in successive rounds at a greater sample size in order to improve the accuracy and robustness of the estimated cost for the join path.

Each join path reflects a specific history. The cutoff sample for the initial vertex can be shared across join paths since there is no prior history. This is true even when we re-sample the vertex at the start of each round. The cutoff sample for each join reflects the history of joins. It can only be shared with join paths having the same history up to that vertex. For example, the following join paths can share estimates of the vertices A, B, and C but not D or E.

 p1: {A, B, C, E, D}
 p2: {A, B, C, D, E}
 

This is because their histories diverge after the (B,C) join.

In each successive round of exploration, each join path is replaced by one or more one-step extensions of that path. The extensions are generated by considering the vertices in the join graph which are not yet in use within the join path. The join paths which spanning the same unordered set of vertices in a given round of exploration compete based on their estimated cost. The winner is the join path with the lowest estimated cost. The losers are dropped from further consideration in order to prune the search space. See JGraph which manages the expansion and competition among join paths.

When considering vertices which can extend the join path, we first select constrained joins. Only if there are no remaining constrained joins will a join path be extended by an unconstrained join. A constrained join is one which shares a variable with the existing join path. The variable may either be shared directly via the IPredicates or indirectly via an IConstraint which can be evaluated for the Vertex under consideration given the set of variables which are already known to be bound for the join path. An unconstrained join is one where there are no shared variables and always results in a full cross-product. Unconstrained joins are not chosen unless there are no available constrained joins.

Field Summary

Fields

Modifier and Type	Field and Description
long	sumEstCard The cumulative estimated cardinality of the path.
long	sumEstCost The expected cost of this join path if it were to be fully executed.
long	sumEstRead The cumulative estimated #of tuples that would be read for this path if it were to be fully executed (sum(tuplesRead*f) for each step in the path).

Constructor Summary

Constructors

Constructor and Description
Path(Vertex v0, Vertex v1, EdgeSample edgeSample) Create a path from a single edge.

Method Summary

Methods

Modifier and Type	Method and Description
Path	addEdge(QueryEngine queryEngine, JoinGraph joinGraph, int limit, Vertex vnew, IConstraint[] constraints, boolean pathIsComplete) Add an edge to a path, computing the estimated cardinality of the new path, and returning the new path.
boolean	beginsWith(int[] ids) Return true if this path begins with the given path.
boolean	beginsWith(Path p) Return true if this path begins with the given path.
boolean	contains(Vertex v) Return true iff the Path contains that Vertex.
static EdgeSample	cutoffJoin(QueryEngine queryEngine, JoinGraph joinGraph, int limit, IPredicate<?>[] path, IConstraint[] constraints, boolean pathIsComplete, SampleBase sourceSample) Cutoff join of the last vertex in the join path.
int	getNewLimit(int limitIn) Examine the path.
IPredicate<?>[]	getPathSegment(int length) Return the first N IPredicates in this Path.
IPredicate<?>[]	getPredicates() Return the IPredicates associated with the vertices of the join path in path order.
int	getVertexCount() Return the #of vertices in this join path.
int[]	getVertexIds() Return the BOp identifiers of the predicates associated with each vertex in path order.
List<Vertex>	getVertices() Return the vertices in this path (in path order).
boolean	isUnorderedVariant(Path p) Return true if this path is an unordered variant of the given path (same vertices in any order).
String	toString()

Methods inherited from class java.lang.Object

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

Field Detail

sumEstCard

public final long sumEstCard

The cumulative estimated cardinality of the path. This is zero for an empty path. For a path consisting of a single edge, this is the estimated cardinality of that edge. When creating a new path by adding an edge to an existing path, the cumulative cardinality of the new path is the cumulative cardinality of the existing path plus the estimated cardinality of the cutoff join of the new edge given the input sample of the existing path.

sumEstRead

public final long sumEstRead

The cumulative estimated #of tuples that would be read for this path if it were to be fully executed (sum(tuplesRead*f) for each step in the path).

sumEstCost

public final long sumEstCost

The expected cost of this join path if it were to be fully executed. This is a function of sumEstCard and sumEstRead. The former reflects the #of intermediate solutions generated. The latter reflects the #of tuples read from the disk. These two measures are tracked separately and then combined into the sumEstCost.

Constructor Detail

Path

public Path(Vertex v0,
    Vertex v1,
    EdgeSample edgeSample)

Create a path from a single edge.

Parameters:

v0 - The initial vertex in the path.

v1 - The 2nd vertex in the path.

edgeSample - The sample obtained from the cutoff join of (v0,v1).

Method Detail

getNewLimit

public int getNewLimit(int limitIn)

Examine the path. If there is a cardinality underflow, then boost the sampling limit. Otherwise, increase the sample by the caller's value.

Parameters:

limitIn - The default increment for the sample limit.

Returns:

The limit to use when resampling this path.

toString

public String toString()

Overrides:

toString in class Object

getVertexCount

public int getVertexCount()

Return the #of vertices in this join path.

contains

public boolean contains(Vertex v)

Return true iff the Path contains that Vertex.

Parameters:

v - The vertex

Returns:

true if the vertex is already part of the path.

isUnorderedVariant

public boolean isUnorderedVariant(Path p)

Return true if this path is an unordered variant of the given path (same vertices in any order).

Parameters:

p - Another path.

Returns:

true if this path is an unordered variant of the given path.

getVertices

public List<Vertex> getVertices()

Return the vertices in this path (in path order). For the first edge, the minimum cardinality vertex is always reported first (this is critical for producing the correct join plan). For the remaining edges in the path, the unvisited is reported.

Returns:

The vertices (in path order).

getPredicates

public IPredicate<?>[] getPredicates()

Return the IPredicates associated with the vertices of the join path in path order.

See Also:

getVertices()

getVertexIds

public int[] getVertexIds()

Return the BOp identifiers of the predicates associated with each vertex in path order.

beginsWith

public boolean beginsWith(Path p)

Return true if this path begins with the given path.

Parameters:

p - The given path.

Returns:

true if this path begins with the given path.

beginsWith

public boolean beginsWith(int[] ids)

Return true if this path begins with the given path.

Parameters:

p - The given path.

Returns:

true if this path begins with the given path.

getPathSegment

public IPredicate<?>[] getPathSegment(int length)

Return the first N IPredicates in this Path.

Parameters:

length - The length of the path segment.

Returns:

The path segment.

addEdge

public Path addEdge(QueryEngine queryEngine,
           JoinGraph joinGraph,
           int limit,
           Vertex vnew,
           IConstraint[] constraints,
           boolean pathIsComplete)
             throws Exception

Add an edge to a path, computing the estimated cardinality of the new path, and returning the new path. The cutoff join is performed using the edgeSample of this join path and the actual access path for the target vertex.

Parameters:

queryEngine -

limit -

vnew - The new vertex.

constraints - The join graph constraints (if any).

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

Returns:

The new path. The materialized sample for the new path is the sample obtained by the cutoff join for the edge added to the path.

Throws:

Exception

cutoffJoin

public static EdgeSample cutoffJoin(QueryEngine queryEngine,
                    JoinGraph joinGraph,
                    int limit,
                    IPredicate<?>[] path,
                    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.

path - 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