com.bigdata.bop.joinGraph.fast

Class DefaultEvaluationPlan2

java.lang.Object

com.bigdata.bop.joinGraph.fast.DefaultEvaluationPlan2

All Implemented Interfaces:

IEvaluationPlan

public class DefaultEvaluationPlan2
extends Object
implements IEvaluationPlan

The evaluation order is determined by analysis of the propagation of bindings. The most selective predicate is chosen first (having the fewest unbound variables with ties broken by a range count on the data) and "fake" bindings are propagated to the other predicates in the tail. This process is repeated until all variables are bound and an evaluation order has been determined.

Version:

$Id$

Author:

Bryan Thompson

Field Summary

Fields

Modifier and Type	Field and Description
protected static boolean	DEBUG
protected static boolean	INFO
protected static org.apache.log4j.Logger	log

Constructor Summary

Constructors

Constructor and Description
DefaultEvaluationPlan2(IJoinNexus joinNexus, IRule rule) Computes an evaluation plan for the rule.
DefaultEvaluationPlan2(IRangeCountFactory rangeCountFactory, IRule rule) Computes an evaluation plan for the rule.

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.bop.joinGraph.fast.DefaultEvaluationPlan2.IJoinDimension d1, com.bigdata.bop.joinGraph.fast.DefaultEvaluationPlan2.IJoinDimension d2) This is the secret sauce.
int[]	getOrder() Return the evaluation order.
protected Set<String>	getVars(int tail) Get the named variables for a given tail.
protected boolean	hasSharedVars(com.bigdata.bop.joinGraph.fast.DefaultEvaluationPlan2.IJoinDimension d1, com.bigdata.bop.joinGraph.fast.DefaultEvaluationPlan2.IJoinDimension d2) Look for shared variables.
protected boolean	hasUnsharedVars(com.bigdata.bop.joinGraph.fast.DefaultEvaluationPlan2.IJoinDimension d1, com.bigdata.bop.joinGraph.fast.DefaultEvaluationPlan2.IJoinDimension d2) Look for unshared variables.
boolean	isEmpty() true iff the IRule was proven to be empty based on range counts or other data.
long	rangeCount(int tailIndex) Return the range count for the predicate, ignoring any bindings.
String	toString()

Methods inherited from class java.lang.Object

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

Field Detail

log

protected static final transient org.apache.log4j.Logger log

DEBUG

protected static final transient boolean DEBUG

INFO

protected static final transient boolean INFO

Constructor Detail

DefaultEvaluationPlan2

public DefaultEvaluationPlan2(IJoinNexus joinNexus,
                      IRule rule)

Computes an evaluation plan for the rule.

Parameters:

joinNexus - The join nexus.

rule - The rule.

DefaultEvaluationPlan2

public DefaultEvaluationPlan2(IRangeCountFactory rangeCountFactory,
                      IRule rule)

Computes an evaluation plan for the rule.

Parameters:

rangeCountFactory - The range count factory.

rule - The rule.

Method Detail

getOrder

public int[] getOrder()

Description copied from interface: IEvaluationPlan

Return the evaluation order.

Specified by:

getOrder in interface IEvaluationPlan

Returns:

The evaluation order. This is an array of indices into the predicates in the tail of the rule. Each tail predicate must be used exactly once. The elements in this array are the order in which each tail predicate will be evaluated. The index into the array is the index of the tail predicate whose evaluation order you want. So [2,0,1] says that the predicates will be evaluated in the order tail[2], then tail[0], then tail[1].

isEmpty

public boolean isEmpty()

Description copied from interface: IEvaluationPlan

true iff the IRule was proven to be empty based on range counts or other data.

Specified by:

isEmpty in interface IEvaluationPlan

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).

Specified by:

rangeCount in interface IEvaluationPlan

Parameters:

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

Returns:

The range count for that tail predicate.

See Also:

IRangeCountFactory

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.bop.joinGraph.fast.DefaultEvaluationPlan2.IJoinDimension d1,
                          com.bigdata.bop.joinGraph.fast.DefaultEvaluationPlan2.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 sum 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.

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.bop.joinGraph.fast.DefaultEvaluationPlan2.IJoinDimension d1,
                    com.bigdata.bop.joinGraph.fast.DefaultEvaluationPlan2.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

hasUnsharedVars

protected boolean hasUnsharedVars(com.bigdata.bop.joinGraph.fast.DefaultEvaluationPlan2.IJoinDimension d1,
                      com.bigdata.bop.joinGraph.fast.DefaultEvaluationPlan2.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