Class RankIndexMaintainer
- java.lang.Object
-
- com.apple.foundationdb.record.provider.foundationdb.IndexMaintainer
-
- com.apple.foundationdb.record.provider.foundationdb.indexes.StandardIndexMaintainer
-
- com.apple.foundationdb.record.provider.foundationdb.indexes.RankIndexMaintainer
-
@API(MAINTAINED) public class RankIndexMaintainer extends StandardIndexMaintainer
An index maintainer for keeping aRankedSet
of record field values.A ranked-set is a persistent skip-list that efficiently implements two complementary functions:
- rank: Given a value, where would this value be in an ordered enumeration of all values in the set?
- select: Given an ordinal position in the ordered enumeration of values, what is the specific value at that position?
Any number of fields in a
RANK
index can optionally separate records into non-overlapping groups. Each group, determined by the values of those fields, has separate ranking and therefore a separate ranked-set.Physical layout: a
RANK
index maintains two subspaces in the database:- primary subspace: an ordinary B-tree index on
[group, ..., score, ...]
. - secondary subspace: a ranked-set per group, that is, with any group key as a prefix.
The overhead of the secondary subspace is one key-value pair for each value at the finest level (0) of the ranked-set skip-list, plus additional key-value pairs at coarser levels, with a probability of
1/16ⁿ
for level n.Store operations: The basic rank and select functions are exposed by the index as aggregate functions, that is, as operations on the whole record store rather than specific records.
FunctionNames.RANK_FOR_SCORE
: the rank operation; given a tuple of group keys and score values, return the ordinal position of that scoreFunctionNames.SCORE_FOR_RANK
: the select operation; given a tuple of group keys and a rank ordinal, return the score at that position or an error if out of rangeFunctionNames.SCORE_FOR_RANK_ELSE_SKIP
: similarly, given a tuple of group keys and a rank ordinal, return the score at that position, or a special value if out of range
Because the ranked-set skip-list keeps a count of entries, the index can also perform the
FunctionNames.COUNT_DISTINCT
aggregate function, and, equivalently when the index does not permit ties, that is, when the index is declared unique, the more basicFunctionNames.COUNT
aggregate function.Record operations: Given a record,
FunctionNames.RANK
record function returns the rank of that record according to the index. This is done by evaluating the same key expressions used by index maintenance against the record to determine any group keys and score values. These are then given to the ranked-set's rank function.Scan operations: The index can be used to return a range of records within a group in rank order.
IndexScanType.BY_VALUE
: The primary B-tree is used just like aIndexTypes.VALUE
index.IndexScanType.BY_RANK
: Given a range of ranks, return those records.
This is done as follows:
- Take the group keys from the common prefix of the range endpoints to determine which ranked-set to use.
- Convert each of the rank endpoints of the range into score endpoints using select.
- Add back the group prefixes to those scores.
- Return a
BY_VALUE
scan between those grouped score endpoints.
-
-
Field Summary
-
Fields inherited from class com.apple.foundationdb.record.provider.foundationdb.indexes.StandardIndexMaintainer
TOO_LARGE_VALUE_MESSAGE_LIMIT
-
Fields inherited from class com.apple.foundationdb.record.provider.foundationdb.IndexMaintainer
state
-
-
Constructor Summary
Constructors Constructor Description RankIndexMaintainer(IndexMaintainerState state)
-
Method Summary
All Methods Instance Methods Concrete Methods Modifier and Type Method Description boolean
canEvaluateAggregateFunction(IndexAggregateFunction function)
Get whether this index can be used to evaluate the given aggregate function.boolean
canEvaluateRecordFunction(IndexRecordFunction<?> function)
Returntrue
if this index be used to evaluate the given record function.CompletableFuture<Void>
deleteWhere(Transaction tr, Tuple prefix)
Clear index storage associated with the given key prefix.CompletableFuture<Tuple>
evaluateAggregateFunction(IndexAggregateFunction function, TupleRange range, IsolationLevel isolationLevel)
Evaluate an aggregate function over the given range using this index.<T,M extends Message>
CompletableFuture<T>evaluateRecordFunction(EvaluationContext context, IndexRecordFunction<T> function, FDBRecord<M> record)
Evaluate a record function on the given record.boolean
isIdempotent()
Whether updating or removing a record on this index is idempotent.protected <M extends Message>
CompletableFuture<Long>rank(EvaluationContext context, IndexRecordFunction<Long> function, FDBRecord<M> record)
<M extends Message>
CompletableFuture<Long>rank(FDBRecord<M> record)
RecordCursor<IndexEntry>
scan(IndexScanType scanType, TupleRange rankRange, byte[] continuation, ScanProperties scanProperties)
Scan entries in the index.protected <M extends Message>
CompletableFuture<Void>updateIndexKeys(FDBIndexableRecord<M> savedRecord, boolean remove, List<IndexEntry> indexEntries)
Update index according to record keys.-
Methods inherited from class com.apple.foundationdb.record.provider.foundationdb.indexes.StandardIndexMaintainer
addedRangeWithKey, addUniquenessViolation, canDeleteWhere, canDeleteWhere, checkKeyValueSizes, checkUniqueness, commonKeys, decodeValue, evaluateIndex, filteredIndexEntries, getExecutor, getGroupedCount, getGroupingCount, getTimer, indexEntryKey, makeMutable, performOperation, removeUniquenessViolationsAsync, saveIndexEntryAsKeyValue, scan, scanUniquenessViolations, skipUpdateForUnchangedKeys, trimTooLargeTuple, unpackKeyValue, unpackKeyValue, update, updateIndexKeysFunction, updateOneKeyAsync, validateEntries, validateMissingEntries, validateOrphanEntries
-
Methods inherited from class com.apple.foundationdb.record.provider.foundationdb.IndexMaintainer
getIndexSubspace, getSecondarySubspace, unsupportedAggregateFunction, unsupportedRecordFunction
-
-
-
-
Constructor Detail
-
RankIndexMaintainer
public RankIndexMaintainer(IndexMaintainerState state)
-
-
Method Detail
-
scan
@Nonnull public RecordCursor<IndexEntry> scan(@Nonnull IndexScanType scanType, @Nonnull TupleRange rankRange, @Nullable byte[] continuation, @Nonnull ScanProperties scanProperties)
Description copied from class:IndexMaintainer
Scan entries in the index.- Specified by:
scan
in classIndexMaintainer
- Parameters:
scanType
- thetype
of scan to performrankRange
- the range to scancontinuation
- any continuation from a previous scan invocationscanProperties
- skip, limit and other properties of the scan- Returns:
- a cursor over index entries in the given range
-
updateIndexKeys
protected <M extends Message> CompletableFuture<Void> updateIndexKeys(@Nonnull FDBIndexableRecord<M> savedRecord, boolean remove, @Nonnull List<IndexEntry> indexEntries)
Description copied from class:StandardIndexMaintainer
Update index according to record keys. Often this operation returns an already completed future because there is no asynchronous work to be done.- Overrides:
updateIndexKeys
in classStandardIndexMaintainer
- Type Parameters:
M
- the message type of the record- Parameters:
savedRecord
- the record being indexedremove
-true
if removing from indexindexEntries
- the result ofStandardIndexMaintainer.evaluateIndex(FDBRecord)
- Returns:
- a future completed when update is done
-
isIdempotent
public boolean isIdempotent()
Description copied from class:IndexMaintainer
Whether updating or removing a record on this index is idempotent. In principle, all index updates in the normal case are idempotent as long as the index update and the record insertion or deletion is atomic. However, certain indexes (mostly aggregate indexes) have the property that the index update on its own are not idempotent.- Overrides:
isIdempotent
in classStandardIndexMaintainer
- Returns:
- whether updating this index is idempotent
-
canEvaluateRecordFunction
public boolean canEvaluateRecordFunction(@Nonnull IndexRecordFunction<?> function)
Description copied from class:IndexMaintainer
Returntrue
if this index be used to evaluate the given record function.- Overrides:
canEvaluateRecordFunction
in classStandardIndexMaintainer
- Parameters:
function
- requested function- Returns:
true
if this index can be used to evaluate the given function
-
evaluateRecordFunction
@Nonnull public <T,M extends Message> CompletableFuture<T> evaluateRecordFunction(@Nonnull EvaluationContext context, @Nonnull IndexRecordFunction<T> function, @Nonnull FDBRecord<M> record)
Description copied from class:IndexMaintainer
Evaluate a record function on the given record.- Overrides:
evaluateRecordFunction
in classStandardIndexMaintainer
- Type Parameters:
T
- the result type of the functionM
- the message type of the record- Parameters:
context
- context for evaluationfunction
- the record function to apply to the given recordrecord
- record against which to evaluate- Returns:
- a future that completes with the result of evaluation
-
rank
public <M extends Message> CompletableFuture<Long> rank(@Nonnull FDBRecord<M> record)
-
rank
protected <M extends Message> CompletableFuture<Long> rank(@Nonnull EvaluationContext context, @Nullable IndexRecordFunction<Long> function, @Nonnull FDBRecord<M> record)
-
deleteWhere
public CompletableFuture<Void> deleteWhere(Transaction tr, @Nonnull Tuple prefix)
Description copied from class:IndexMaintainer
Clear index storage associated with the given key prefix.- Overrides:
deleteWhere
in classStandardIndexMaintainer
- Parameters:
tr
- transaction in which to access the databaseprefix
- prefix of primary key to clear- Returns:
- a future that is complete when the given prefix has been cleared from this index
-
canEvaluateAggregateFunction
public boolean canEvaluateAggregateFunction(@Nonnull IndexAggregateFunction function)
Description copied from class:IndexMaintainer
Get whether this index can be used to evaluate the given aggregate function.- Overrides:
canEvaluateAggregateFunction
in classStandardIndexMaintainer
- Parameters:
function
- the requested aggregate function- Returns:
true
if this index be used to evaluate the given aggregate function
-
evaluateAggregateFunction
@Nonnull public CompletableFuture<Tuple> evaluateAggregateFunction(@Nonnull IndexAggregateFunction function, @Nonnull TupleRange range, @Nonnull IsolationLevel isolationLevel)
Description copied from class:IndexMaintainer
Evaluate an aggregate function over the given range using this index.- Overrides:
evaluateAggregateFunction
in classStandardIndexMaintainer
- Parameters:
function
- the aggregate function to evaluaterange
- the range over which to accumulate the aggregateisolationLevel
- the isolation level at which to perform the scan- Returns:
- a future that completes with the aggregate result
-
-