com.bigdata.relation.accesspath

Class AccessPath<R>

java.lang.Object

com.bigdata.relation.accesspath.AccessPath<R>

All Implemented Interfaces:

IAbstractAccessPath<R>, IAccessPath<R>, IBindingSetAccessPath<R>

Direct Known Subclasses:

SPOAccessPath

public class AccessPath<R>
extends Object
implements IAccessPath<R>, IBindingSetAccessPath<R>

Abstract base class for type-specific IAccessPath implementations.

Note: Filters should be specified when the IAccessPath is constructed so that they will be evaluated on the data service rather than materializing the elements and then filtering them. This can be accomplished by adding the filter as a constraint on the predicate when specifying the access path.

Author:

Bryan Thompson

Field Summary

Fields

Modifier and Type	Field and Description
protected IFilter	accessPathFilter The filter derived from optional IPredicate.Annotations#ACCESS_PATH_FILTER.
protected int	chunkCapacity
protected int	chunkOfChunksCapacity
protected int	flags Iterator flags.
protected int	fullyBufferedReadThreshold
protected IFilter	indexLocalFilter The filter derived from optional IPredicate.Annotations#INDEX_LOCAL_FILTER.
protected IIndexManager	indexManager Access to the index, resource locator, executor service, etc.
protected IKeyOrder<R>	keyOrder Index order (the relation namespace plus the index order and the option partitionId constraint on the predicate identify the index).
protected static org.apache.log4j.Logger	log
protected static int	MAX_FULLY_BUFFERED_READ_LIMIT The maximum limit that is allowed for a fully-buffered read.
protected IIndex	ndx The index.
protected IPredicate<R>	predicate Predicate (the resource name on the predicate is the relation namespace).
protected long	timestamp Timestamp of the view.

Constructor Summary

Constructors

Constructor and Description
AccessPath(IRelation<R> relation, IIndexManager localIndexManager, IPredicate<R> predicate, IKeyOrder<R> keyOrder)

Method Summary

Methods

Modifier and Type	Method and Description
protected void	assertInitialized()
protected IChunkedOrderedIterator<R>	asynchronousIterator(Iterator<R> src) Asynchronous read using a BlockingBuffer.
ScanCostReport	estimateCost() Return an estimate of the cost of a scan on the predicate.
int	getChunkCapacity()
int	getChunkOfChunksCapacity()
byte[]	getFromKey() The key corresponding to the inclusive lower bound for the IAccessPath null if there is no lower bound.
IIndex	getIndex() The index selected for the access path.
IIndexManager	getIndexManager()
IKeyOrder<R>	getKeyOrder() The order in which the elements will be visited.
IPredicate<R>	getPredicate() The constraints on the IAccessPath.
IRelation<R>	getRelation()
long	getTimestamp()
byte[]	getToKey() The key corresponding to the exclusive upper bound for the IAccessPath -or- null if there is no upper bound.
boolean	hasFilter() true iff there is a filter for the access path (either local or remote).
AccessPath<R>	init() Required post-ctor initialization.
boolean	isEmpty() True iff the access path is empty (there are no matches for the IPredicate) This is more conclusive than #rangeCount() since you MAY have a non-zero range count when the key range is in fact empty (there may be "deleted" index entries within the key range).
boolean	isFullyBoundForKey() true iff all elements in the predicate which are required to generate the key are bound to constants.
IChunkedOrderedIterator<R>	iterator() An iterator visiting elements using the natural order of the index selected for the IPredicate.
IChunkedOrderedIterator<R>	iterator(long offset, long limit, int capacity) An iterator visiting elements using the natural order of the index selected for the IPredicate.
long	rangeCount(boolean exact) Return the maximum #of elements spanned by the IPredicate.
protected ITupleIterator<R>	rangeIterator(int capacity, int flags, IFilter filter)
long	removeAll() This implementation removes all tuples that would be visited by the access path from the backing index.
ICloseableIterator<IBindingSet[]>	solutions(BOpContext context, long limit, BaseJoinStats stats) Return an iterator which will visit the solutions drawn from the access path with a limit on the number of solutions drawn.
protected IChunkedOrderedIterator<R>	synchronousIterator(long offset, long limit, Iterator<R> src) Fully buffers all elements that would be visited by the IAccessPath iterator.
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 org.apache.log4j.Logger log

indexManager

protected final IIndexManager indexManager

Access to the index, resource locator, executor service, etc.

timestamp

protected final long timestamp

Timestamp of the view.

predicate

protected final IPredicate<R> predicate

Predicate (the resource name on the predicate is the relation namespace).

keyOrder

protected final IKeyOrder<R> keyOrder

Index order (the relation namespace plus the index order and the option partitionId constraint on the predicate identify the index).

ndx

protected final IIndex ndx

The index.

flags

protected final int flags

Iterator flags.

chunkOfChunksCapacity

protected final int chunkOfChunksCapacity

chunkCapacity

protected final int chunkCapacity

fullyBufferedReadThreshold

protected final int fullyBufferedReadThreshold

MAX_FULLY_BUFFERED_READ_LIMIT

protected static final int MAX_FULLY_BUFFERED_READ_LIMIT

The maximum limit that is allowed for a fully-buffered read. The asynchronousIterator(Iterator) will always be used above this limit. FIXME Array limits in truth maintenance code. This should probably be close to the branching factor or chunk capacity. It has been temporarily raised to a very large value in order to support truth maintenance where the code assumes access to the fully buffered result. That change needs to be examined for an impact on query performance. It is effectively forcing all access path reads to be fully buffered rather than using an asynchronous iterator pattern.

See Also:

Array limits in truth maintenance code. , Constant Field Values

indexLocalFilter

protected final IFilter indexLocalFilter

The filter derived from optional IPredicate.Annotations#INDEX_LOCAL_FILTER. If there are shared variables in the IPredicate then a SameVariableConstraint is added regardless of whether the IPredicate specified a filter or not.

accessPathFilter

protected final IFilter accessPathFilter

The filter derived from optional IPredicate.Annotations#ACCESS_PATH_FILTER.

Constructor Detail

AccessPath

public AccessPath(IRelation<R> relation,
          IIndexManager localIndexManager,
          IPredicate<R> predicate,
          IKeyOrder<R> keyOrder)

Parameters:

relation - The relation for the access path (optional). The relation is not specified when requested an IAccessPath for a specific index partition in order to avoid forcing the materialization of the IRelation.

localIndexManager - Access to the indices, resource locators, executor service, etc.

predicate - The constraints on the access path.

keyOrder - The order in which the elements would be visited for this access path.

Method Detail

hasFilter

public final boolean hasFilter()

true iff there is a filter for the access path (either local or remote).

isFullyBoundForKey

public boolean isFullyBoundForKey()

true iff all elements in the predicate which are required to generate the key are bound to constants.

getChunkCapacity

public int getChunkCapacity()

See Also:

AbstractResource.getChunkCapacity()

getChunkOfChunksCapacity

public int getChunkOfChunksCapacity()

See Also:

AbstractResource.getChunkOfChunksCapacity()

getFromKey

public final byte[] getFromKey()

The key corresponding to the inclusive lower bound for the IAccessPath null if there is no lower bound.

getToKey

public final byte[] getToKey()

The key corresponding to the exclusive upper bound for the IAccessPath -or- null if there is no upper bound.

getKeyOrder

public final IKeyOrder<R> getKeyOrder()

Description copied from interface: IAccessPath

The order in which the elements will be visited.

Specified by:

getKeyOrder in interface IAccessPath<R>

toString

public String toString()

Overrides:

toString in class Object

assertInitialized

protected final void assertInitialized()

Throws:

IllegalStateException - unless init() has been invoked.

init

public AccessPath<R> init()

Required post-ctor initialization.

Returns:

this

getRelation

public IRelation<R> getRelation()

getIndexManager

public IIndexManager getIndexManager()

getTimestamp

public long getTimestamp()

getPredicate

public IPredicate<R> getPredicate()

Description copied from interface: IAbstractAccessPath

The constraints on the IAccessPath.

Specified by:

getPredicate in interface IAbstractAccessPath<R>

getIndex

public IIndex getIndex()

Description copied from interface: IAccessPath

The index selected for the access path.

Note: The access path may incorporate additional constraints from the specified IPredicate that are not present on the IIndex returned by this method.

Specified by:

getIndex in interface IAccessPath<R>

isEmpty

public boolean isEmpty()

Description copied from interface: IAbstractAccessPath

True iff the access path is empty (there are no matches for the IPredicate) This is more conclusive than #rangeCount() since you MAY have a non-zero range count when the key range is in fact empty (there may be "deleted" index entries within the key range).

Specified by:

isEmpty in interface IAbstractAccessPath<R>

solutions

public ICloseableIterator<IBindingSet[]> solutions(BOpContext context,
                                          long limit,
                                          BaseJoinStats stats)

Return an iterator which will visit the solutions drawn from the access path with a limit on the number of solutions drawn.

Specified by:

solutions in interface IBindingSetAccessPath<R>

limit - The maximum #of solutions to visit.

stats - Some statistics are updated as solutions are visited.

Returns:

The iterator.

See Also:

(Access path should visit solutions for high level query).

iterator

public final IChunkedOrderedIterator<R> iterator()

Description copied from interface: IAccessPath

An iterator visiting elements using the natural order of the index selected for the IPredicate. This is equivalent to

 iterator(0L, 0L, 0)
 

since an offset of ZERO (0L) means no offset, a limit of ZERO (0L) means no limit and a capacity of ZERO (0) means whatever is the default capacity.

Note: Filters should be specified when the IAccessPath is constructed so that they will be evaluated on the IDataService rather than materializing the elements and then filtering then. This can be accomplished by adding the filter as an IElementFilter on the IPredicate when requesting IAccessPath.

Specified by:

iterator in interface IAccessPath<R>

Returns:

The iterator.

See Also:

IRelation.getAccessPath(IPredicate)

iterator

public final IChunkedOrderedIterator<R> iterator(long offset,
                                  long limit,
                                  int capacity)

Description copied from interface: IAccessPath

An iterator visiting elements using the natural order of the index selected for the IPredicate.

The offset and limit together describe an optional slice that will be visited by the iterator. When a slice is specified, the iterator will count off the elements accepted by the IPredicate up to the offset, but not materialize them. Elements by the IPredicate starting with the offset and up to (but not including) offset+limit will be materialized for the client. The iterator will halt processing after observing offset+limit accepted elements. Note that slices for JOINs (vs a simple IAccessPath scan) are handled by IQueryOptions for an IRule.

The meaning of "accepted" is that: (a) the elements lie in the key-range constraint implied by the IPredicate; and (b) the elements pass any optional constraints that the IPredicate imposes.

Specified by:

iterator in interface IAccessPath<R>

Parameters:

offset - The first element accepted by the iterator that it will visit (materialize for the client). The offset must be non-negative. This is ZERO (0L) to visit all accepted elements.

limit - The last element accepted by the iterator that it will visit (materialize for the client). The limit must be non-negative. This is ZERO (0L) to visit all accepted elements (the value Long.MAX_VALUE is interpreted exactly like ZERO(0L)).

capacity - The maximum capacity for the buffer used by the iterator. When ZERO(0), a default capacity will be used. When a limit is specified, the capacity will never exceed the limit.

Returns:

The iterator. FIXME The offset and limit should probably be rolled into the predicate and removed from the IAccessPath. This way they will be correctly applied when IAbstractAccessPath.isEmpty() is implemented using the IAccessPath.iterator() to determine if any elements can be visited.

Throws:

RejectedExecutionException - if the iterator is run asynchronously and the ExecutorService is shutdown or has a maximum capacity and is saturated. FIXME Support both offset and limit for asynchronous iterators. right now this will force the use of the synchronousIterator(long, long, Iterator) when the offset or limit are non-zero, but that is only permitted up to a limit of MAX_FULLY_BUFFERED_READ_LIMIT. FIXME in order to support large limits we need to verify that the asynchronous iterator can correctly handle REMOVEALL and that incremental materialization up to the [limit] will not effect the semantics for REMOVEALL or the other iterator flags (per above). (In fact, the asynchronous iterator does not support either [offset] or [limit] at this time). FIXME write unit tests for slice handling by this method and modify the SAIL integration to use it for SLICE on an IAccessPath scan. Note that there are several IAccessPath implementations and they all need to be tested with SLICE. Those tests should be located in TestSPOAccessPath. FIXME The offset and limit should probably be rolled into the predicate and removed from the IAccessPath. This way they will be correctly applied when isEmpty() is implemented using the iterator() to determine if any

synchronousIterator

protected final IChunkedOrderedIterator<R> synchronousIterator(long offset,
                                             long limit,
                                             Iterator<R> src)

Fully buffers all elements that would be visited by the IAccessPath iterator.

Parameters:

accessPath - The access path (including the triple pattern).

offset - The first element that will be materialized (non-negative).

limit - The maximum #of elements that will be materialized (must be positive, so use a range count before calling this method if there was no limit specified by the caller). FIXME pass the offset and limit into the source iterator and remove them from this method's signature. This will require a change to the IRangeQuery API and ITupleIterator impls.

asynchronousIterator

protected final IChunkedOrderedIterator<R> asynchronousIterator(Iterator<R> src)

Asynchronous read using a BlockingBuffer.

Parameters:

src - The source iterator.

Returns:

Throws:

RejectedExecutionException - if the ExecutorService is shutdown or has a maximum capacity and is saturated.

rangeCount

public final long rangeCount(boolean exact)

Description copied from interface: IAbstractAccessPath

Return the maximum #of elements spanned by the IPredicate.

Note: When there is an IFilter on the IPredicate the exact range count MUST apply that IFilter, which means that it will be required to traverse the index counting tuples which pass the IFilter. However, IFilters are ignored for the fast range count.

Specified by:

rangeCount in interface IAbstractAccessPath<R>

Parameters:

exact - When true, the result will be an exact count and may require a key-range scan. When false, the result will be an upper bound IFF delete markers are provisioned for the backing index (delete markers are required for transactions and for scale-out indices).

See Also:

IRangeQuery

rangeIterator

protected ITupleIterator<R> rangeIterator(int capacity,
                              int flags,
                              IFilter filter)

removeAll

public long removeAll()

This implementation removes all tuples that would be visited by the access path from the backing index.

Note: If you are maintaining multiple indices then you MUST override this method to remove the data from each of those indices.

Specified by:

removeAll in interface IAbstractAccessPath<R>

Returns:

The #of elements that were removed.

estimateCost

public ScanCostReport estimateCost()

Return an estimate of the cost of a scan on the predicate.

Parameters:

pred - The predicate.

Returns:

The estimated cost of a scan on that predicate.