public class Path extends Object
vertices
and
represents an ordered series of N1 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 IConstraint
s.
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 resampled 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 resample 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 onestep 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 IPredicate
s 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 crossproduct. Unconstrained joins are
not chosen unless there are no available constrained joins.
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 and Description 

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

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)

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
IPredicate s in this Path . 
IPredicate<?>[] 
getPredicates()
Return the
IPredicate s 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() 
public final long sumEstCard
public final long sumEstRead
public final long sumEstCost
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
.public Path(Vertex v0, Vertex v1, EdgeSample edgeSample)
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).public int getNewLimit(int limitIn)
limitIn
 The default increment for the sample limit.public int getVertexCount()
public boolean contains(Vertex v)
v
 The vertexpublic boolean isUnorderedVariant(Path p)
true
if this path is an unordered variant of the
given path (same vertices in any order).p
 Another path.true
if this path is an unordered variant of the
given path.public List<Vertex> getVertices()
public IPredicate<?>[] getPredicates()
IPredicate
s associated with the vertices of the
join path in path order.getVertices()
public int[] getVertexIds()
BOp
identifiers of the predicates associated with
each vertex in path order.public boolean beginsWith(Path p)
true
if this path begins with the given path.p
 The given path.true
if this path begins with the given path.public boolean beginsWith(int[] ids)
true
if this path begins with the given path.p
 The given path.true
if this path begins with the given path.public IPredicate<?>[] getPathSegment(int length)
IPredicate
s in this Path
.length
 The length of the path segment.public Path addEdge(QueryEngine queryEngine, JoinGraph joinGraph, int limit, Vertex vnew, IConstraint[] constraints, boolean pathIsComplete) throws Exception
edgeSample
of this join path and the actual access path
for the target vertex.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.Exception
public static EdgeSample cutoffJoin(QueryEngine queryEngine, JoinGraph joinGraph, int limit, IPredicate<?>[] path, IConstraint[] constraints, boolean pathIsComplete, SampleBase sourceSample) throws Exception
The caller is responsible for protecting against needless resampling. This includes cases where a sample already exists at the desired sample limit and cases where the sample is already exact.
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 onestep
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
.Exception
Copyright © 2006–2016 SYSTAP, LLC DBA Blazegraph. All rights reserved.