com.bigdata.rdf.sparql.ast

Class JoinSetUtil

java.lang.Object

com.bigdata.rdf.sparql.ast.JoinSetUtil

public class JoinSetUtil
extends Object

Utility class for join analysis. TODO Surely we can do some bit math which would be slimmer and faster than managing the IVariable sets?

Version:

$Id$

Author:

Bryan Thompson

Nested Class Summary

Nested Classes

Modifier and Type	Class and Description
static class	JoinSetUtil.VertexJoinSet A collection of vertices and the join variables they bind.

Field Summary

Fields

Modifier and Type	Field and Description
int[][]	canJoin Diagonal matrix for the required joins.
int[]	directJoinCount The #of direct joins found for each vertex (summed across canJoin matrix.
Set<JoinSetUtil.VertexJoinSet>	directJoinSets The distinct sets of vertices which are composed solely of (the transitive closure of) joins on directly shared variables.
Set<IVariable<?>>	eventuallyBoundVars The set of variables which are bound by the time the last required join is done.
GraphPatternGroup<IGroupMemberNode>	group The group.
Set<FilterNode>	joinFilters The FILTERS that will be attached to the required joins for this group.
Set<IVariable<?>>	knownBound The variables known to be bound on entry to the group.
Set<FilterNode>	postFilters The FILTERS that can not be run until the end of the join group.
Set<FilterNode>	preFilters The FILTERS that can be run on entry to the group (and which should be lifted into the parent).
int	requiredJoinCount The #of required joins in the group (the requiredJoins length).
IJoinNode[]	requiredJoins An array of the vertices for the required joins in the group.
Set<IVariable<?>>[]	vars The set of variables which are bound be each of the vertices for the required joins.

Constructor Summary

Constructors

Constructor and Description
JoinSetUtil(StaticAnalysis sa, Set<IVariable<?>> knownBound, GraphPatternGroup<IGroupMemberNode> group)

Method Summary

Methods inherited from class java.lang.Object

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

Field Detail

group

public final GraphPatternGroup<IGroupMemberNode> group

The group.

knownBound

public final Set<IVariable<?>> knownBound

The variables known to be bound on entry to the group.

eventuallyBoundVars

public final Set<IVariable<?>> eventuallyBoundVars

The set of variables which are bound by the time the last required join is done. This includes the knownBound variables plus any variables for any required join.

requiredJoins

public final IJoinNode[] requiredJoins

An array of the vertices for the required joins in the group. The indices into the array are the order in which the required joins were encountered in the group.

requiredJoinCount

public final int requiredJoinCount

The #of required joins in the group (the requiredJoins length).

preFilters

public final Set<FilterNode> preFilters

The FILTERS that can be run on entry to the group (and which should be lifted into the parent).

joinFilters

public final Set<FilterNode> joinFilters

The FILTERS that will be attached to the required joins for this group.

postFilters

public final Set<FilterNode> postFilters

The FILTERS that can not be run until the end of the join group.

vars

public final Set<IVariable<?>>[] vars

The set of variables which are bound be each of the vertices for the required joins. The indices into the array are the order in which the requried joins were encountered in the group.

canJoin

public final int[][] canJoin

Diagonal matrix for the required joins. A cells having a positive value gives the #of directly shared variables. This will be ZERO (0) if there is no direct join. Only the upper diagonal of the matrix is populated.

directJoinCount

public final int[] directJoinCount

The #of direct joins found for each vertex (summed across canJoin matrix.

directJoinSets

public final Set<JoinSetUtil.VertexJoinSet> directJoinSets

The distinct sets of vertices which are composed solely of (the transitive closure of) joins on directly shared variables. For example

 p(x,y) X p(y,z) x p(z,t)
 

Would form a direct join set each join will share a variable directly. Even though there are some vertices which do not share variables directly, they can be joined directly once other joins have been processed. For example p(z,t) can be joined once we have p(y,z).

The number of such direct join sets varies with the query. If all vertices fit into one direct join set, then the query can be pipelined efficiently. If there is more than one such set then we need to look further to see if we can identify joins on indirectly shared variables (shared through a FILTER) which can be used to piece these join sets together. If not, there is an unconstrained cross product in the query.

Constructor Detail

JoinSetUtil

public JoinSetUtil(StaticAnalysis sa,
           Set<IVariable<?>> knownBound,
           GraphPatternGroup<IGroupMemberNode> group)

Parameters:

sa -

knownBound - Any variables known to be bound on entry to the group.

group - The group.