com.bigdata.bop.joinGraph.rto

Class JGraph

java.lang.Object

com.bigdata.bop.joinGraph.rto.JGraph

public class JGraph
extends Object

A runtime optimizer for a join graph. The JoinGraph bears some similarity to ROX (Runtime Optimizer for XQuery), but has several significant differences:

1. 1. ROX starts from the minimum cardinality edge of the minimum cardinality vertex. The JoinGraph starts with one or more low cardinality vertices.
2. 2. ROX always extends the last vertex added to a given join path. The JoinGraph extends all vertices having unexplored edges in each breadth first expansion.
3. 3. ROX is designed to interleave operator-at-once evaluation of join path segments which dominate other join path segments. The JoinGraph is designed to prune all join paths which are known to be dominated by other join paths for the same set of vertices in each round and iterates until a join path is identified which uses all vertices and has the minimum expected cumulative estimated cardinality. Join paths which survive pruning are re-sampled as necessary in order to obtain better information about edges in join paths which have a low estimated cardinality in order to address a problem with underflow of the cardinality estimates.

TODO For join graphs with a large number of vertices we may need to constrain the #of vertices which are explored in parallel. This could be done by only branching the N lowest cardinality vertices from the already connected edges. Since fewer vertices are being explored in parallel, paths are more likely to converge onto the same set of vertices at which point we can prune the dominated paths. TODO Compare the cumulative expected cardinality of a join path with the tuples read on a join path. The latter allows us to also explore alternative join strategies, such as the parallel subquery versus scan and filter decision for named graph and default graph SPARQL queries. TODO Coalescing duplicate access paths can dramatically reduce the work performed by a pipelined nested index subquery. (A hash join eliminates all duplicate access paths using a scan and filter approach.) If we will run a pipeline nested index subquery join, then should the runtime query optimizer prefer paths with duplicate access paths?

See Also:

Runtime Query Optimization, Integrate RTO into SAIL, ROX

Constructor Summary

Constructors

Constructor and Description
JGraph(JoinGraph joinGraph)

Method Summary

Methods

Modifier and Type	Method and Description
Path[]	chooseStartingPaths(int nedges, Path[] paths) Choose the starting vertices.
Path[]	expand(QueryEngine queryEngine, int limitIn, int round, Path[] a, Map<PathIds,EdgeSample> edgeSamples) Do one breadth first expansion.
int[]	getOrder(Path p) Return a permutation vector which may be used to reorder the given IPredicate[] into the evaluation order selected by the runtime query optimizer.
Vertex	getVertex(int bopId) Return the Vertex whose IPredicate is associated with the given BOp.Annotations#BOP_ID.
List<Vertex>	getVertices()
Path[]	pruneJoinPaths(Path[] a, Map<PathIds,EdgeSample> edgeSamples) Prune paths which are dominated by other paths.
protected int	resamplePaths(QueryEngine queryEngine, int limitIn, int round, Path[] a, Map<PathIds,EdgeSample> edgeSamples) Resample the initial vertices for the specified join paths and then resample the cutoff join for each given join path in path order.
Path[]	round0(QueryEngine queryEngine, int limit, int nedges) Choose up to nedges edges to be the starting point.
Path	runtimeOptimizer(QueryEngine queryEngine, Map<PathIds,EdgeSample> edgeSamples) Find a good join path in the data given the join graph.
static String	showPath(Path x, Map<PathIds,EdgeSample> edgeSamples) Show the details of a join path, including the estimated cardinality and join hit ratio for each step in the path.
static String	showTable(Path[] a) Comma delimited table showing the estimated join hit ratio, the estimated cardinality, and the set of vertices for each of the specified join paths.
static String	showTable(Path[] a, Path[] pruned) Return a comma delimited table showing the estimated join hit ratio, the estimated cardinality, and the set of vertices for each of the specified join paths.
static String	showTable(Path[] a, Path[] pruned, Map<PathIds,EdgeSample> edgeSamples) Return a comma delimited table showing the estimated join hit ratio, the estimated cardinality, and the set of vertices for each of the specified join paths.
String	toString()

Methods inherited from class java.lang.Object

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

Constructor Detail

JGraph

public JGraph(JoinGraph joinGraph)

Parameters:

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.

Throws:

IllegalArgumentException - if the joinGraph is null.

IllegalArgumentException - if the JoinGraph.getVertices() is null.

IllegalArgumentException - if the JoinGraph.getVertices() is an empty array.

IllegalArgumentException - if any element of the JoinGraph.getVertices()is null.

IllegalArgumentException - if any constraint uses a variable which is never bound by the given predicates.

IllegalArgumentException - if sampleType is null.

Method Detail

getVertices

public List<Vertex> getVertices()

toString

public String toString()

Overrides:

toString in class Object

runtimeOptimizer

public Path runtimeOptimizer(QueryEngine queryEngine,
                    Map<PathIds,EdgeSample> edgeSamples)
                      throws Exception,
                             NoSolutionsException

Find a good join path in the data given the join graph. The join path is not guaranteed to be the best join path (the search performed by the runtime optimizer is not exhaustive) but it should always be a "good" join path and may often be the "best" join path.

Parameters:

queryEngine - The query engine.

edgeSamples - A map that will be populated with the samples associated with each non-pruned join path. This map is used to associate join path segments (expressed as an ordered array of bopIds) with edge sample to avoid redundant effort.

Returns:

The join path identified by the runtime query optimizer as the best path given the join graph and the data.

Throws:

NoSolutionsException - If there are no solutions for the join graph in the data (the query does not have any results).

IllegalArgumentException - if queryEngine is null.

IllegalArgumentException - if limit is non-positive.

IllegalArgumentException - if nedges is non-positive.

Exception - TODO It is possible that this could throw a NoSolutionsException if the cutoff joins do not use a large enough sample to find a join path which produces at least one solution (except that no solutions for an optional join do not cause the total to fail, nor do no solutions for some part of a UNION). TODO We need to automatically increase the depth of search for queries where we have cardinality estimation underflows or punt to another method to decide the join order. TODO RTO: HEAP MANAGMENT : The edgeSamples map holds references to the cutoff join samples. To ensure that the map has the minimum heap footprint, it must be scanned each time we prune the set of active paths and any entry which is not a prefix of an active path should be removed. TODO RTO: MEMORY MANAGER : When an entry is cleared from this map, the corresponding allocation in the memory manager (if any) must be released. The life cycle of the map needs to be bracketed by a try/finally in order to ensure that all allocations associated with the map are released no later than when we leave the lexicon scope of that clause.

getOrder

public int[] getOrder(Path p)

Return a permutation vector which may be used to reorder the given IPredicate[] into the evaluation order selected by the runtime query optimizer.

Throws:

IllegalArgumentException - if the argument is null.

IllegalArgumentException - if the given Path does not cover all vertices in the join graph.

chooseStartingPaths

public Path[] chooseStartingPaths(int nedges,
                         Path[] paths)

Choose the starting vertices.

Parameters:

nedges - The maximum #of edges to choose.

paths - The set of possible initial paths to choose from.

Returns:

Up to nedges minimum cardinality paths.

round0

public Path[] round0(QueryEngine queryEngine,
            int limit,
            int nedges)
              throws Exception

Choose up to nedges edges to be the starting point. For each of the nedges lowest cardinality edges, the starting vertex will be the vertex with the lowest cardinality for that edge.

Note: An edge can not serve as a starting point for exploration if it uses variables (for example, in a CONSTRAINT) which are not bound by either vertex (since the variable(s) are not bound, the constraint would always fail).

Parameters:

queryEngine - The query engine.

limit - The cutoff used when sampling the vertices and when sampling the edges.

nedges - The maximum #of edges to choose. Those having the smallest expected cardinality will be chosen.

Returns:

An initial set of paths starting from at most nedges.

Throws:

Exception

resamplePaths

protected int resamplePaths(QueryEngine queryEngine,
                int limitIn,
                int round,
                Path[] a,
                Map<PathIds,EdgeSample> edgeSamples)
                     throws Exception

Resample the initial vertices for the specified join paths and then resample the cutoff join for each given join path in path order.

Parameters:

queryEngine - The query engine.

limitIn - The original limit.

round - The round number in [1:n].

a - The set of paths from the previous round. For the first round, this is formed from the initial set of edges to consider.

edgeSamples - A map used to associate join path segments (expressed as an ordered array of bopIds) with EdgeSamples to avoid redundant effort.

Returns:

The number of join paths which are experiencing cardinality estimate underflow.

Throws:

Exception

expand

public Path[] expand(QueryEngine queryEngine,
            int limitIn,
            int round,
            Path[] a,
            Map<PathIds,EdgeSample> edgeSamples)
              throws Exception

Do one breadth first expansion. In each breadth first expansion we extend each of the active join paths by one vertex for each remaining vertex which enjoys a constrained join with that join path. In the event that there are no remaining constrained joins, we will extend the join path using an unconstrained join if one exists. In all, there are three classes of joins to be considered:

1. The target predicate directly shares a variable with the source join path. Such joins are always constrained since the source predicate will have bound that variable.
2. The target predicate indirectly shares a variable with the source join path via a constraint can run for the target predicate and which shares a variable with the source join path. These joins are indirectly constrained by the shared variable in the constraint. BSBM Q5 is an example of this case.
3. Any predicates may always be join to an existing join path. However, joins which do not share variables either directly or indirectly will be full cross products. Therefore such joins are added to the join path only after all constrained joins have been consumed.

Parameters:

queryEngine - The query engine.

limitIn - The original limit.

round - The round number in [1:n].

a - The set of paths from the previous round. For the first round, this is formed from the initial set of edges to consider.

edgeSamples - A map used to associate join path segments (expressed as an ordered array of bopIds) with EdgeSamples to avoid redundant effort.

Returns:

The set of paths which survived pruning in this round.

Throws:

Exception

getVertex

public Vertex getVertex(int bopId)

Return the Vertex whose IPredicate is associated with the given BOp.Annotations#BOP_ID.

Parameters:

bopId - The bop identifier.

Returns:

The Vertex -or- null if there is no such vertex in the join graph.

pruneJoinPaths

public Path[] pruneJoinPaths(Path[] a,
                    Map<PathIds,EdgeSample> edgeSamples)

Prune paths which are dominated by other paths. Paths are extended in each round. Paths from previous rounds are always pruned. Of the new paths in each round, the following rule is applied to prune the search to just those paths which are known to dominate the other paths covering the same set of vertices:

If there is a path, [p] != [p1], where [p] is an unordered variant of [p1] (that is the vertices of p are the same as the vertices of p1), and the cumulative cost of [p] is LTE the cumulative cost of [p1], then [p] dominates (or is equivalent to) [p1] and p1 should be pruned.

Parameters:

a - A set of paths.

edgeSamples - The set of samples for path segments. Samples which are no longer in use after pruning will be cleared from the map and their materialized solution sets will be discarded.

Returns:

The set of paths with all dominated paths removed.

showTable

public static String showTable(Path[] a)

Comma delimited table showing the estimated join hit ratio, the estimated cardinality, and the set of vertices for each of the specified join paths.

Parameters:

a - An array of join paths.

Returns:

A table with that data.

showTable

public static String showTable(Path[] a,
               Path[] pruned)

Return a comma delimited table showing the estimated join hit ratio, the estimated cardinality, and the set of vertices for each of the specified join paths.

Parameters:

a - A set of paths (typically those before pruning).

pruned - The set of paths after pruning (those which were retained) (optional). When given, the paths which were pruned are marked in the table.

Returns:

A table with that data.

showTable

public static String showTable(Path[] a,
               Path[] pruned,
               Map<PathIds,EdgeSample> edgeSamples)

Return a comma delimited table showing the estimated join hit ratio, the estimated cardinality, and the set of vertices for each of the specified join paths.

Parameters:

a - A set of paths (typically those before pruning).

pruned - The set of paths after pruning (those which were retained) (optional). When given, the paths which were pruned are marked in the table.

edgeSamples - When non-null, the details will be shown (using showPath(Path, Map)) for each path that is experiencing cardinality estimate underflow (no solutions in the data).

Returns:

A table with that data.

showPath

public static String showPath(Path x,
              Map<PathIds,EdgeSample> edgeSamples)

Show the details of a join path, including the estimated cardinality and join hit ratio for each step in the path.

Parameters:

p - The join path (required).

edgeSamples - A map containing the samples utilized by the Path (required).