com.bigdata.btree

Interface IRangeQuery

All Known Subinterfaces:

IClientIndex, IIndex, ILocalBTreeView, IMetadataIndex, IScaleOutClientIndex

All Known Implementing Classes:

AbstractBTree, AbstractCommitTimeIndex, AbstractScaleOutClientIndexView, AbstractScaleOutClientIndexView2, BTree, CacheOnceMetadataIndex, CachingMetadataIndex, ClientIndexView, ClientIndexViewRefactor, CommitRecordIndex, CommitTimeIndex, CounterSetBTree, DelegateBTree, DelegateIndex, EventReceiver.EventBTree, FusedView, IndexSegment, IndexSegmentIndex, IsolatedFusedView, JournalIndex, MetadataIndex, MetadataIndexView, Name2Addr, NoCacheMetadataIndexView, ReadCommittedView, ReadOnlyIndex, TestMROWTransactions.MyBTree, TestRestartSafe.MyBTree, TxId2CommitTimeIndex, UnisolatedReadWriteIndex

public interface IRangeQuery

Interface for range count and range query operations.

Note: There are implementations of this interface for both local indices and for distributed scale-out indices.

Version:

$Id$

Author:

Bryan Thompson

Field Summary

Fields

Modifier and Type	Field and Description
static int	ALL Shorthand for [KEYS, VALS, DELETED].
static int	CURSOR Flag specifies that the base iterator will support the full ITupleCursor API, including traversal with concurrent modification, bi-directional tuple navigation and random seeks within the key range.
static int	DEFAULT The flags that should be used by default [KEYS, VALS] in contexts where the flags are not explicitly specified by the application such as rangeIterator(byte[], byte[]).
static int	DELETED Flag specifies that deleted index entries for a key are visited by the iterator (by default the iterator will hide deleted index entries).
static int	FIXED_LENGTH_SUCCESSOR There are two ways in which the successor of an unsigned byte[] key may be computed.
static int	KEYS Flag specifies that keys in the key range will be returned.
static int	NONE Flag specifies no data (the #of scanned index entries matching the optional filter will still be reported).
static int	PARALLEL Flag indicates that the iterator may process multiple index partitions in parallel.
static int	READONLY Flag specifies that the iterator, including any ITupleFilters, will not write on the index.
static int	REMOVEALL Flag specifies that entries visited by the iterator in the key range will be removed from the index.
static int	REVERSE Flag specifies that the entries will be visited using a reverse scan.
static int	VALS Flag specifies that values in the key range will be returned.

Method Summary

Methods

Modifier and Type	Method and Description
long	rangeCount() Return the #of tuples in the index.
long	rangeCount(byte[] fromKey, byte[] toKey) Return the #of tuples in a half-open key range.
long	rangeCountExact(byte[] fromKey, byte[] toKey) Return the exact #of tuples in a half-open key range.
long	rangeCountExactWithDeleted(byte[] fromKey, byte[] toKey) Return the exact #of tuples in a half-open key range, including any deleted tuples.
ITupleIterator	rangeIterator() Visits all tuples in key order.
ITupleIterator	rangeIterator(byte[] fromKey, byte[] toKey) Return an iterator that visits the entries in a half-open key range.
ITupleIterator	rangeIterator(byte[] fromKey, byte[] toKey, int capacity, int flags, IFilter filterCtor) Designated variant (the one that gets overridden) for an iterator that visits the entries in a half-open key range.

Field Detail

NONE

static final int NONE

Flag specifies no data (the #of scanned index entries matching the optional filter will still be reported).

See Also:

Constant Field Values

KEYS

static final int KEYS

Flag specifies that keys in the key range will be returned. The keys are guaranteed to be made available via ITupleIterator#getKey() only when this flag is given.

See Also:

Constant Field Values

VALS

static final int VALS

Flag specifies that values in the key range will be returned. The values are guaranteed to be made available via ITupleIterator.next() and ITupleIterator#getValue() only when this flag is given.

See Also:

Constant Field Values

DELETED

static final int DELETED

Flag specifies that deleted index entries for a key are visited by the iterator (by default the iterator will hide deleted index entries).

See Also:

Constant Field Values

DEFAULT

static final int DEFAULT

The flags that should be used by default [KEYS, VALS] in contexts where the flags are not explicitly specified by the application such as rangeIterator(byte[], byte[]).

See Also:

Constant Field Values

ALL

static final int ALL

Shorthand for [KEYS, VALS, DELETED].

See Also:

Constant Field Values

READONLY

static final int READONLY

Flag specifies that the iterator, including any ITupleFilters, will not write on the index. Various optimizations may be applied when this flag is present. (Read only can be inferred if CURSOR flag is NOT specified AND there are NO ITupleFilters).

See Also:

Constant Field Values

REMOVEALL

static final int REMOVEALL

Flag specifies that entries visited by the iterator in the key range will be removed from the index. This flag may be combined with KEYS or VALS in order to return the keys and/or values for the deleted entries. When a IFilter is specified, the filter stack will be applied first and then REMOVEALL will cause a TupleRemover to be layered on top. You can achieve other stacked iterator semantics using IFilter, including causing ITuples to be removed at a different layer in the stack. Note however, that removal for a local BTree will require that the TupleRemover is stacked directly over an ITupleCursor.

Note: This semantics of this flag require that the entries are atomically removed within the isolation level of the operation. In particular, if the iterator is running against an IDataService using an unisolated view then the entries MUST be buffered and removed as the ResultSet is populated.

Note: The BigdataFileSystem.deleteHead(String, int) relies on this atomic guarantee.

See Also:

Constant Field Values

CURSOR

static final int CURSOR

Flag specifies that the base iterator will support the full ITupleCursor API, including traversal with concurrent modification, bi-directional tuple navigation and random seeks within the key range. There are several pragmatic reasons why you would or would not specify this flag.

1. The original Striterator construction for the BTree is faster than the newer AbstractBTreeTupleCursor. It is used by default when this flag is NOT specified and the iterator is running across a BTree. (The IndexSegment.IndexSegmentTupleCursor is used for IndexSegments regardless of the value of this flag since it exploits the double-linked leaves of the IndexSegment and is therefore MORE efficient than the Striterator based construct.)
2. This flag enables traversal with concurrent modification (i.e., Iterator.remove()) when used with a local BTree. Scale-out iterators always support traversal with concurrent modification since they heavily buffer the iterator with ResultSets.

See Also:

Constant Field Values

REVERSE

static final int REVERSE

Flag specifies that the entries will be visited using a reverse scan. The first tuple to be visited will be the tuple having the largest key strictly less than the optional upper bound for the key range. The iterator will then visit the previous tuple(s) until it has visited the tuple having the smallest key greater than or equal to the optional lower bound for the key range.

This flag may be used to realize a number of interesting constructions, including atomic operations on the tail of a queue and obtaining the last key in the key range.

See Also:

Constant Field Values

FIXED_LENGTH_SUCCESSOR

static final int FIXED_LENGTH_SUCCESSOR

There are two ways in which the successor of an unsigned byte[] key may be computed. The default is to append an unsigned zero byte to the key. This forms the next possible key for the natural unsigned byte[] sort order.

The other choice is to treat the unsigned byte[] as a fixed length bit string and to add ONE (1) with rollover. This works in some special circumstances, primarily because you are actually seeking to skip over all keys that have a given key as their prefix and continue the iterator at the next possible prefix having the same length.

Note: This option is applied by AbstractChunkedTupleIterator, which is responsible for issuing continuation queries.

See Also:

Constant Field Values

PARALLEL

static final int PARALLEL

Flag indicates that the iterator may process multiple index partitions in parallel. While tuples are visited in each index partition in the natural ordering, this flag breaks the total ordering guarantee of the iterator if multiple index partitions are visited as tuples from each index partition will be visited concurrently and appear in an interleaved ordering. To maintain efficiency, the tuples are interleaved in chunks so processing which benefits from order effects can exploit the within chunk ordering of the tuples. The semantics of this flag are realized by the IClientIndex implementation. This flag has no effect on an ILocalBTreeView and is not passed through to the IDataService.

See Also:

Constant Field Values

Method Detail

rangeCount

long rangeCount()

Return the #of tuples in the index.

Note: If the index supports deletion markers then the range count will be an upper bound and may double count tuples which have been overwritten, including the special case where the overwrite is a delete.

Returns:

The #of tuples in the index.

See Also:

ISimpleIndexAccess.rangeCount()

rangeCount

long rangeCount(byte[] fromKey,
              byte[] toKey)

Return the #of tuples in a half-open key range. The fromKey and toKey need not exist in the B+Tree.

Note: If the index supports deletion markers then the range count will be an upper bound and may double count tuples which have been overwritten, including the special case where the overwrite is a delete.

Parameters:

fromKey - The lowest key that will be counted (inclusive). When null there is no lower bound.

toKey - The first key that will not be counted (exclusive). When null there is no upper bound.

Returns:

The #of tuples in the half-open key range.

rangeCountExact

long rangeCountExact(byte[] fromKey,
                   byte[] toKey)

Return the exact #of tuples in a half-open key range. The fromKey and toKey need not exist in the B+Tree.

Note: If the index supports deletion markers then this operation will require a key-range scan.

Parameters:

fromKey - The lowest key that will be counted (inclusive). When null there is no lower bound.

toKey - The first key that will not be counted (exclusive). When null there is no upper bound.

Returns:

The exact #of tuples in the half-open key range.

rangeCountExactWithDeleted

long rangeCountExactWithDeleted(byte[] fromKey,
                              byte[] toKey)

Return the exact #of tuples in a half-open key range, including any deleted tuples. The fromKey and toKey need not exist in the B+Tree.

When the view is just an AbstractBTree the result is the same as for rangeCount(byte[], byte[]), which already reports all tuples regardless of whether or not they are deleted.

When the index is a view with multiple sources, this operation requires a key-range scan where both deleted and undeleted tuples are visited.

Parameters:

fromKey - The lowest key that will be counted (inclusive). When null there is no lower bound.

toKey - The first key that will not be counted (exclusive). When null there is no upper bound.

Returns:

The exact #of deleted and undeleted tuples in the half-open key range.

See Also:

rangeCountExact(byte[], byte[])

rangeIterator

ITupleIterator rangeIterator()

Visits all tuples in key order. This is identical to

 rangeIterator(null, null)
 

Returns:

An iterator that will visit all entries in key order.

rangeIterator

ITupleIterator rangeIterator(byte[] fromKey,
                           byte[] toKey)

Return an iterator that visits the entries in a half-open key range. When toKey EQ fromKey nothing will be visited. It is an error if toKey LT fromKey.

Parameters:

fromKey - The first key that will be visited (inclusive lower bound). When null there is no lower bound.

toKey - The first key that will NOT be visited (exclusive upper bound). When null there is no upper bound.

Throws:

RuntimeException - if fromKey is non-null and orders LT the inclusive lower bound for an index partition.

RuntimeException - if toKey is non-null and orders GTE the exclusive upper bound for an index partition.

See Also:

SuccessorUtil, which may be used to compute the successor of a value before encoding it as a component of a key., BytesUtil#successor(byte[]), which may be used to compute the successor of an encoded key., EntryFilter, which may be used to filter the entries visited by the iterator.

rangeIterator

ITupleIterator rangeIterator(byte[] fromKey,
                           byte[] toKey,
                           int capacity,
                           int flags,
                           IFilter filterCtor)

Designated variant (the one that gets overridden) for an iterator that visits the entries in a half-open key range. When toKey EQ fromKey nothing will be visited. It is an error if toKey LT fromKey.

Parameters:

fromKey - The first key that will be visited (inclusive lower bound). When null there is no lower bound.

toKey - The first key that will NOT be visited (exclusive upper bound). When null there is no upper bound.

capacity - The #of entries to buffer at a time. This is a hint and MAY be zero (0) to use an implementation specific default capacity. A non-zero value may be used if you know that you want at most N results or if you want to override the default #of results to be buffered before sending them across a network interface. (Note that you can control the default value using IBigdataClient.Options#DEFAULT_CLIENT_RANGE_QUERY_CAPACITY).

flags - A bitwise OR of KEYS, VALS, etc.

filterCtor - An optional object used to construct a stacked iterator. When CURSOR is specified in flags, the base iterator will implement ITupleCursor and the first filter in the stack can safely cast the source iterator to an ITupleCursor. If the outermost filter in the stack does not implement ITupleIterator, then it will be wrapped an ITupleIterator.

See Also:

SuccessorUtil, which may be used to compute the successor of a value before encoding it as a component of a key., BytesUtil#successor(byte[]), which may be used to compute the successor of an encoded key., IFilterConstructor, which may be used to construct an iterator stack performing filtering or other operations.