com.bigdata.rdf.sparql.ast.optimizers

Class StaticOptimizer

java.lang.Object

com.bigdata.rdf.sparql.ast.optimizers.StaticOptimizer

public final class StaticOptimizer
extends Object

This is the old static optimizer code, taken directly from DefaultEvaluationPlan2, but lined up with the AST API instead of the Rule and IPredicate API.

Constructor Summary

Constructors

Constructor and Description
StaticOptimizer(StaticOptimizer parent, List<IReorderableNode> nodes)

Method Summary

Methods

Modifier and Type	Method and Description
long	cardinality(int tailIndex) Return the cardinality of a particular tail, which is the range count if not optional and infinite if optional.
protected long	computeJoinCardinality(com.bigdata.rdf.sparql.ast.optimizers.StaticOptimizer.IJoinDimension d1, com.bigdata.rdf.sparql.ast.optimizers.StaticOptimizer.IJoinDimension d2) This is the secret sauce.
long	getCardinality()
protected int	getNextTailThatSharesVarsWithAncestry() Get the next tail (unused, non-optional) that shares a var with the ancestry.
int[]	getOrder()
protected Set<String>	getVars(int tail) Get the named variables for a given tail.
protected boolean	hasSharedVars(com.bigdata.rdf.sparql.ast.optimizers.StaticOptimizer.IJoinDimension d1, com.bigdata.rdf.sparql.ast.optimizers.StaticOptimizer.IJoinDimension d2) Look for shared variables.
protected boolean	hasUnsharedVars(com.bigdata.rdf.sparql.ast.optimizers.StaticOptimizer.IJoinDimension d1, com.bigdata.rdf.sparql.ast.optimizers.StaticOptimizer.IJoinDimension d2) Look for unshared variables.
long	rangeCount(int tailIndex) Return the range count for the predicate, ignoring any bindings.
protected boolean	sharesVarsWithAncestry(int tail) Check to see if the specified tail shares any variables with the ancestry.
String	toString()

Methods inherited from class java.lang.Object

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

Constructor Detail

StaticOptimizer

public StaticOptimizer(StaticOptimizer parent,
               List<IReorderableNode> nodes)

Method Detail

getOrder

public int[] getOrder()

rangeCount

public long rangeCount(int tailIndex)

Return the range count for the predicate, ignoring any bindings. The range count for the tail predicate is cached the first time it is requested and returned from the cache thereafter. The range counts are requested using the "non-exact" range count query, so the range counts are actually the upper bound. However, if the upper bound is ZERO (0) then the range count really is ZERO (0).

Parameters:

tailIndex - The index of the predicate in the tail of the rule.

Returns:

The range count for that tail predicate.

cardinality

public long cardinality(int tailIndex)

Return the cardinality of a particular tail, which is the range count if not optional and infinite if optional.

toString

public String toString()

Overrides:

toString in class Object

computeJoinCardinality

protected long computeJoinCardinality(com.bigdata.rdf.sparql.ast.optimizers.StaticOptimizer.IJoinDimension d1,
                          com.bigdata.rdf.sparql.ast.optimizers.StaticOptimizer.IJoinDimension d2)

This is the secret sauce. There are three possibilities for computing the join cardinality, which we are defining as the upper-bound for solutions for a particular join. First, if there are no shared variables then the cardinality will just be the simple product of the cardinality of each join dimension. If there are shared variables but no unshared variables, then the cardinality will be the minimum cardinality from the join dimensions. If there are shared variables but also some unshared variables, then the join cardinality will be the maximum cardinality from each join dimension.

TODO: Any join involving an optional will have infinite cardinality, so that optionals get placed at the end.

Parameters:

d1 - the first join dimension

d2 - the second join dimension

Returns:

the join cardinality

getVars

protected Set<String> getVars(int tail)

Get the named variables for a given tail. Is there a better way to do this?

Parameters:

tail - the tail

Returns:

the named variables

hasSharedVars

protected boolean hasSharedVars(com.bigdata.rdf.sparql.ast.optimizers.StaticOptimizer.IJoinDimension d1,
                    com.bigdata.rdf.sparql.ast.optimizers.StaticOptimizer.IJoinDimension d2)

Look for shared variables.

Parameters:

d1 - the first join dimension

d2 - the second join dimension

Returns:

true if there are shared variables, false otherwise

sharesVarsWithAncestry

protected boolean sharesVarsWithAncestry(int tail)

Check to see if the specified tail shares any variables with the ancestry.

getNextTailThatSharesVarsWithAncestry

protected int getNextTailThatSharesVarsWithAncestry()

Get the next tail (unused, non-optional) that shares a var with the ancestry. If there are many, choose the one with the lowest cardinality. Return -1 if none are found.

hasUnsharedVars

protected boolean hasUnsharedVars(com.bigdata.rdf.sparql.ast.optimizers.StaticOptimizer.IJoinDimension d1,
                      com.bigdata.rdf.sparql.ast.optimizers.StaticOptimizer.IJoinDimension d2)

Look for unshared variables.

Parameters:

d1 - the first join dimension

d2 - the second join dimension

Returns:

true if there are unshared variables, false otherwise

getCardinality

public long getCardinality()