com.bigdata.bop

Class BOpUtility

java.lang.Object

com.bigdata.bop.BOpUtility

public class BOpUtility
extends Object

Operator utility class.

Version:

$Id$

Author:

Bryan Thompson

Field Summary

Fields

Modifier and Type	Field and Description
static IBindingSet[]	EMPTY_CHUNK An empty IBindingSet[].

Constructor Summary

Constructors

Constructor and Description
BOpUtility()

Method Summary

Methods

Modifier and Type	Method and Description
static Iterator<BOp>	annotationOpIterator(BOp op) Visit all annotations which are BOps (non-recursive).
static ICloseableIterator<IBindingSet[]>	asIterator(IBindingSet[] bindingSets) Wrap the solutions with an ICloseableIterator.
static IConstraint[]	concat(IConstraint[] a, IConstraint[] b) Combine two arrays of constraints.
static long	copy(Iterator<IBindingSet[]> source, IBlockingBuffer<IBindingSet[]> sink, IBlockingBuffer<IBindingSet[]> sink2, IBindingSet mergeSolution, IVariable<?>[] selectVars, IConstraint[] constraints, BOpStats stats) Copy binding sets from the source to the sink(s).
static int	countVarOccurrencesOutsideProjections(BOp op, IVariable inputVar) Counts the number of occurrences of a BOp inside another BOp.
static <T extends BOp> T	deepCopy(T op) Deep copy.
static int	getArgumentVariableCount(BOp op) The #of arguments to this operation which are variables.
static Iterator<IVariable<?>>	getArgumentVariables(BOp op) Return the variables from the operator's arguments.
static Integer	getEffectiveDefaultSink(BOp bop, BOp p) Return the effective default sink.
static Integer[]	getEvaluationOrder(BOp op) Return a list containing the evaluation order for the pipeline.
static Map<Integer,BOp>	getIndex(BOp op) Return an index from the BOp.Annotations.BOP_ID to the BOp for each spanned PipelineOp.
static <C> C	getOnly(BOp op, Class<C> class1) Return the sole instance of the specified class.
static BOp	getParent(BOp root, BOp op) Return the parent of the operator in the operator tree (this does not search the annotations, just the children).
static BOp	getPipelineStart(BOp op) Return the left-deep child of the operator.
static int[]	getPredIds(IPredicate<?>[] path) Return an ordered array of the bopIds associated with an ordered array of predicates (aka a join path).
static Set<IVariable<?>>	getSharedVars(BOp p, BOp c) Return the variable references shared by two operators.
static Iterator<IVariable<?>>	getSpannedVariables(BOp op) Return the distinct variables recursively using a pre-order traversal present whether in the operator tree or on annotations attached to operators.
static boolean	isConsistent(IConstraint[] constraints, IBindingSet bindingSet) Check constraints.
static PipelineOp	makeAggregateDistinct(PipelineOp subQuery) Return a copy of the subquery in which each IAggregate function is a distinct instance.
static Iterator<BOp>	postOrderIterator(BOp op) Post-order recursive visitation of the operator tree (arguments only, no annotations).
static Iterator<BOp>	postOrderIteratorWithAnnotations(BOp op) Recursive post-order traversal of the operator tree with visitation of all operator annotations.
static Iterator<BOp>	preOrderIterator(BOp op) Pre-order recursive visitation of the operator tree (arguments only, no annotations).
static Iterator<BOp>	preOrderIteratorWithAnnotations(BOp op) Recursive pre-order traversal of the operator tree with visitation of all operator annotations.
static IBindingSet[]	toArray(Iterator<IBindingSet[]> itr, BOpStats stats) Combine chunks drawn from an iterator into a single chunk.
static IVariable[]	toArray(Iterator<IVariable<?>> it) Return an array containing the IVariables visited by the iterator.
static <C> List<C>	toList(BOp op, Class<C> clas) Return a list containing references to all nodes of the given type (recursive, including annotations).
static <T> List<T>	toList(Iterator<T> it) Return an List containing the IVariables visited by the iterator.
static String	toString(BOp bop) Pretty print a bop.
static String	toString2(BOp bop)
static <C> Iterator<C>	visitAll(BOp op, Class<C> clas) Return an iterator visiting references to all nodes of the given type (recursive, including annotations).

Methods inherited from class java.lang.Object

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

Field Detail

EMPTY_CHUNK

public static final IBindingSet[] EMPTY_CHUNK

An empty IBindingSet[].

Constructor Detail

BOpUtility

public BOpUtility()

Method Detail

preOrderIterator

public static Iterator<BOp> preOrderIterator(BOp op)

Pre-order recursive visitation of the operator tree (arguments only, no annotations).

postOrderIterator

public static Iterator<BOp> postOrderIterator(BOp op)

Post-order recursive visitation of the operator tree (arguments only, no annotations).

annotationOpIterator

public static Iterator<BOp> annotationOpIterator(BOp op)

Visit all annotations which are BOps (non-recursive).

Parameters:

op - An operator.

Returns:

An iterator which visits the BOp annotations in an arbitrary order.

preOrderIteratorWithAnnotations

public static Iterator<BOp> preOrderIteratorWithAnnotations(BOp op)

Recursive pre-order traversal of the operator tree with visitation of all operator annotations. The annotations for an operator are visited before its children are visited. Only annotations whose values are BOps are visited. Annotation BOps are also recursively visited with the pre-order traversal.

Parameters:

op - An operator.

Returns:

The iterator.

postOrderIteratorWithAnnotations

public static Iterator<BOp> postOrderIteratorWithAnnotations(BOp op)

Recursive post-order traversal of the operator tree with visitation of all operator annotations. The annotations for an operator are visited before its children are visited. Only annotations whose values are BOps are visited. Annotation BOps are also recursively visited with the pre-order traversal.

Parameters:

op - An operator.

Returns:

The iterator.

See Also:

BOpUtility.postOrderIteratorWithAnnotations() is has wrong visitation order.

getSpannedVariables

public static Iterator<IVariable<?>> getSpannedVariables(BOp op)

Return the distinct variables recursively using a pre-order traversal present whether in the operator tree or on annotations attached to operators.

Note: This will find variables within subqueries as well, which may not be what is intended.

See Also:

StaticAnalysis#getSpannedVariables(BOp, Set), which will only report the variables which are actually visible (variables not projected from subqueries are not reported).

toList

public static <T> List<T> toList(Iterator<T> it)

Return an List containing the IVariables visited by the iterator.

Parameters:

it - The iterator.

toArray

public static IVariable[] toArray(Iterator<IVariable<?>> it)

Return an array containing the IVariables visited by the iterator.

Parameters:

it - The iterator.

toList

public static <C> List<C> toList(BOp op,
                 Class<C> clas)

Return a list containing references to all nodes of the given type (recursive, including annotations).

Note: This may be used to work around concurrent modification errors since the returned list is structurally independent of the original operator tree.

Parameters:

op - The root of the operator tree.

clas - The type of the node to be extracted.

Returns:

A list containing those references.

See Also:

visitAll(BOp, Class)

getOnly

public static <C> C getOnly(BOp op,
            Class<C> class1)

Return the sole instance of the specified class.

Parameters:

op - The root of the traversal.

class1 - The class to look for.

Returns:

The sole instance of that class.

Throws:

NoSuchElementException - if there is no such instance.

RuntimeException - if there is more than one such instance.

visitAll

public static <C> Iterator<C> visitAll(BOp op,
                       Class<C> clas)

Return an iterator visiting references to all nodes of the given type (recursive, including annotations).

Parameters:

op - The root of the operator tree.

clas - The type of the node to be extracted.

Returns:

A iterator visiting those references.

See Also:

toList(BOp, Class)

getArgumentVariables

public static Iterator<IVariable<?>> getArgumentVariables(BOp op)

Return the variables from the operator's arguments.

Parameters:

op - The operator.

Returns:

An iterator visiting its IVariable arguments.

getArgumentVariableCount

public static int getArgumentVariableCount(BOp op)

The #of arguments to this operation which are variables. This method does not report on variables in child nodes nor on variables in attached IConstraint, etc.

getIndex

public static Map<Integer,BOp> getIndex(BOp op)

Return an index from the BOp.Annotations.BOP_ID to the BOp for each spanned PipelineOp. BOps without identifiers are not indexed. It is an error a non-PipelineOp is encountered.

BOps should form directed acyclic graphs, but this is not strictly enforced. The recursive traversal iterators declared by this class do not protect against loops in the operator tree. However, getIndex(BOp) detects and report loops based on duplicate BOp.Annotations.BOP_IDs -or- duplicate BOp references.

Parameters:

op - A BOp.

Returns:

The index, which is immutable and thread-safe.

Throws:

DuplicateBOpIdException - if there are two or more BOps having the same BOp.Annotations.BOP_ID.

BadBOpIdTypeException - if the BOp.Annotations.BOP_ID is not an Integer.

NoBOpIdException - if a PipelineOp does not have a BOp.Annotations.BOP_ID.

NotPipelineOpException - if op or any of its arguments visited during recursive traversal are not a PipelineOp.

getParent

public static BOp getParent(BOp root,
            BOp op)

Return the parent of the operator in the operator tree (this does not search the annotations, just the children).

Note that Var is a singleton pattern for each distinct variable node, so there can be multiple parents for a Var.

Parameters:

root - The root of the operator tree (or at least a known ancestor of the operator).

op - The operator.

Returns:

The parent -or- null if op is not found in the operator tree.

Throws:

IllegalArgumentException - if either argument is null.

getPipelineStart

public static BOp getPipelineStart(BOp op)

Return the left-deep child of the operator.

Note: This does not protect against loops in the operator tree.

Parameters:

op - The operator.

Returns:

The child where pipeline evaluation should begin.

Throws:

IllegalArgumentException - if the argument is null.

getEffectiveDefaultSink

public static Integer getEffectiveDefaultSink(BOp bop,
                              BOp p)

Return the effective default sink.

Parameters:

bop - The operator.

p - The parent of that operator, if any.

getEvaluationOrder

public static Integer[] getEvaluationOrder(BOp op)

Return a list containing the evaluation order for the pipeline. Only the child operands are visited. Operators in subqueries are not visited since they will be assigned BOpStats objects when they are run as a subquery. The evaluation order is given by the depth-first left-deep traversal of the query.

toArray

public static IBindingSet[] toArray(Iterator<IBindingSet[]> itr,
                    BOpStats stats)

Combine chunks drawn from an iterator into a single chunk. This is useful when materializing intermediate results for an all-at-once operator.

Parameters:

itr - The iterator

stats - BOpStats.chunksIn and BOpStats.unitsIn are updated.

Returns:

A single chunk containing all of the chunks visited by the iterator.

asIterator

public static ICloseableIterator<IBindingSet[]> asIterator(IBindingSet[] bindingSets)

Wrap the solutions with an ICloseableIterator.

Parameters:

bindingSets - The solutions.

Returns:

The ICloseableIterator.

toString

public static String toString(BOp bop)

Pretty print a bop.

Parameters:

bop - The bop.

Returns:

The formatted representation.

toString2

public static String toString2(BOp bop)

isConsistent

public static boolean isConsistent(IConstraint[] constraints,
                   IBindingSet bindingSet)

Check constraints.

Parameters:

constraints -

bindingSet -

Returns:

true iff the constraints are satisfied.

copy

public static long copy(Iterator<IBindingSet[]> source,
        IBlockingBuffer<IBindingSet[]> sink,
        IBlockingBuffer<IBindingSet[]> sink2,
        IBindingSet mergeSolution,
        IVariable<?>[] selectVars,
        IConstraint[] constraints,
        BOpStats stats)

Copy binding sets from the source to the sink(s).

Note: You MUST use IBlockingBuffer.flush() to flush the sink(s) in order for the last chunk in the sink(s) to be pushed to the downstream operator for that sink. However, do NOT use flush() if the operator evaluation fails since you do not want to push outputs from a failed operator to downstream operators.

Parameters:

source - The source.

sink - The sink (required).

sink2 - Another sink (optional).

mergeSolution - A solution to be merged in with each solution copied from the source (optional). When given, the selectVars will be applied first to prune the copied solutions to just the selected variables and any additional bindings will then be added from the mergeSolution. This supports the lexical scoping on variables within a subquery when that subquery is being pipelined.

selectVars - The variables to be retained (optional). When not specified, all variables will be retained.

constraints - Binding sets which fail these constraints will NOT be copied (optional).

stats - The BOpStats.chunksIn and BOpStats.unitsIn will be updated during the copy (optional).

Returns:

The #of binding sets copied.

getPredIds

public static int[] getPredIds(IPredicate<?>[] path)

Return an ordered array of the bopIds associated with an ordered array of predicates (aka a join path).

Parameters:

path - A join path.

Returns:

The ordered array of predicates for that join path.

Throws:

IllegalArgumentException - if the argument is null.

IllegalArgumentException - if any element of the argument is null.

IllegalStateException - if any IPredicate does not have a defined bopId as reported by BOp.getId().

getSharedVars

public static Set<IVariable<?>> getSharedVars(BOp p,
                              BOp c)

Return the variable references shared by two operators. All variables spanned by either BOp are considered, regardless of whether they appear as operands or within annotations.

Parameters:

p - An operator.

c - Another operator.

Returns:

The variable(s) in common. This may be an empty set, but it is never null.

Throws:

IllegalArgumentException - if the two either reference is null.

makeAggregateDistinct

public static PipelineOp makeAggregateDistinct(PipelineOp subQuery)

Return a copy of the subquery in which each IAggregate function is a distinct instance. This prevents inappropriate sharing of state across invocations of the subquery.

Parameters:

subQuery -

Returns:

deepCopy

public static <T extends BOp> T deepCopy(T op)

Deep copy. All bops will be distinct instances having the same data for their arguments and their annotations. Annotations which are bops are also deep copied.

concat

public static IConstraint[] concat(IConstraint[] a,
                   IConstraint[] b)

Combine two arrays of constraints. Either may be null or empty. If both were null or empty, then a null will be returned.

Parameters:

a - One set of constraints.

b - Another set of constraints.

Returns:

The combined constraints.

countVarOccurrencesOutsideProjections

public static int countVarOccurrencesOutsideProjections(BOp op,
                                        IVariable inputVar)

Counts the number of occurrences of a BOp inside another BOp.

Parameters:

op - the BOp to scan for occurrences of inner

inner - the nested BOp we're looking for

Returns:

the number of occurrences