RFC: Index percentile

[locker]

Status: Completed
Author: @locker

Reviewers

• Reviewer: @Totktonada
• Reviewer: @unera
• Reviewer: @nshy
• CTO: @sergos

Tickets

• Optimize select with offset option #8204
• Efficient way to find approximate median in data range #11111

Pull requests

• Introduce index:quantile() #11226

Change log

• 2025-02-25: Initial version
• 2025-02-26: Raise an error if the quantile value is 0 or 1.
• 2025-02-28: Describe the vinyl implementation in more details.
• 2025-02-28: Raise an error if the target range can't possibly store any tuples.
• 2025-02-28: Add an example on how partial keys work.
• 2025-02-28: Mention that nil return value means that the range is too small for splitting.
• 2025-03-04: Mention that we can implement the new method for memcs in future
• 2025-03-04: Mention that the new functions won't work well in vinyl for the time-series workload.
• 2025-03-05: Minor changes in function argument names.

Summary

In the scope of this RFC document a new index API method for finding an arbitrary percentile (the median, in particular) in a key interval is proposed. The method can be used for splitting data ranges for load balancing in a range-based sharding approach.

Context

To implement range-based sharding, we need an efficient way to find a median in an indexed key interval so that we can split it for load balancing. Note, we can't just take the average key value because (a) data in the range can be distributed unevenly and (b) computing the average may be technically difficult to implement (consider a compound key with string, uuid, date-time parts, for example).

With the recent improvements of index:count() and index:select() with offset, we can now efficiently find the median (or any other percentile) of an interval in a memtx tree index, as demonstrated by the following code snippet.

-- Example of finding the median in an indexed key interval using
-- index:count() and index:select() with offset.

local function median(index, begin_key, end_key)
    local count = index:count(begin_key, {iterator = 'ge'}) -
                  index:count(end_key,   {iterator = 'ge'})
    return unpack(index:select(begin_key, {
        iterator = 'ge', offset = count / 2, limit = 1,
    }))
end

box.schema.space.create('test')
box.space.test:create_index('primary')
for i = 1, 100 do
    box.space.test:insert{i * i}
end

print(median(box.space.test, 10, 1000)) -- prints [324]

Unfortunately, this approach is unacceptable in case of vinyl because it would require linear scanning of the target range, which has a prohibitive cost. Optimizing index:count() and index:select() with offset from O(N) to O(logN), like we did in memtx, is technically difficult if not unfeasible because vinyl stores data in layers, which have to be merged in order to serve a query. Instead we're planning to introduce a new index API method, which would find a percentile with a reasonable error.

Proposed solution

Synopsis

We propose to introduce the new index method index:quantile(). The method will take up to three arguments:

• level: quantile level; must be a number in range (0, 1); mandatory argument.
• begin_key: beginning of the target key range; optional, assumed to be the empty key if unset.
• end_key: end of the target key range; optional, assumed to be the empty key if unset.

See the "Range definition" section for details on how the range boundary keys are defined.

The function will return the quantile point, i.e. the max key such that the percentage of tuples in the target range which are less than the key doesn't exceed the quantile level * 100%. Note that the function will return a key (given as a Lua table), not a tuple. There's no guarantee that the corresponding tuple exists in the range, see the "Engine differences" section, but the key is guaranteed to be full (have all indexed parts) and belong in the specified range.

Note

We called the new method "quantile", not "percentile", because it seems to be more convenient to pass a fractional value between 0 and 1 rather than a percentage between 0 and 100 (see the explanation of the difference between a quantile and a percentile).

Example usage

-- Example of using the new method index:quantile() for finding
-- the median in an indexed key range.

box.schema.space.create('test')
box.space.test:create_index('primary')
for i = 1, 100 do
    box.space.test:insert{i * i}
end

index:quantile(0.5, 10, 1000) -- prints [324]

Range definition

The range boundary keys (begin_key and end_key) passed to index:quantile() will be specified the same way as in index:select(). A boundary key won't have to be full (have all indexed parts) - it may be partial. The target data set will be defined as an intersection of the following queries:

index:select(begin_key, {iterator = 'ge'})
index:select(end_key, {iterator = 'lt'})

Thus for full keys, the interval would be defined as starting from begin_key inclusive and ending at end_key exclusive, which is a common way to define an interval. To understand how a range is defined if a boundary key is partial, we need to recall how index:select() works in Tarantool. In Tarantool a partial key is assumed to be equal to any full key if it has the same defined parts. For example, {10} equals both {10, 1} and {10, 2} so a range starting at {10} and ending at {15} for two-part integer keys would include {10, 1}, {10, 2}, {12, 1}, {14, 2}, but not {15, 1}. The empty key {} is special: when used with the lt iterator, it is treated as le. So passing the empty key {} for both range boundaries will return the quantile point in the whole space.

Corner cases

The function will raise an error if any of the following conditions is true:

• The requested quantile level is less than or equal to 0 or greater than or equal to 1.
• The range is empty, i.e. there's no tuple that can possibly meet the search criteria from the "Range definition" section.

The function will return nil if there's no tuple in the target range. It may also return nil if it can't find the quantile point for implementation-specific reasons (for example, if the specified range is less than a page in case of vinyl). If the function is used for splitting a range, nil means that the target range is too small for splitting.

Engine differences

The implementation and guarantees of the new method will be engine-dependent:

• In memtx the function will be implemented using index:count() and index:select() with offset. This means that it will return a quantile point without an error and have the O(logN) complexity where N is the number of tuples stored in the index. The function will be available for the tree index only.
• In vinyl the function will basically return the quantile point of the last (deepest) data storage layer, which should be a good enough approximation. The complexity of the function will depend on the configured page and range sizes, but it will never exceed O(logN).

Initially, other engines won't support the new index method. In future, we may implement it for memcs, which like memtx stores data ordered by key.

Vinyl implementation

Vinyl stores data in layers, where the last (deepest) layer is the base while more recent layers store incremental updates. Within a layer, contiguous non-intersecting data chunks are stored in runs while each run consists of pages. The page index of each run is stored in memory so that we can quickly find the first page matching given search criteria. To look up a tuple within a page, we have to read it from disk because the row index of each page is stored on disk.

The new method will look up the quantile point in the last (deepest) data storage layer, which should be a good enough approximation, because the last layer is the largest one and should reflect the data distribution of the whole index in most common usage scenarios. If there's no disk layers, we will use the same internal functions to look up the quantile point in the in-memory BPS-tree that are used internally in memtx.

To find the quantile point in a disk layer, we will perform the following steps:

1. Count the number of data pages in the last layer that fall in the target range. This can be done quickly thanks to the page index. We just need to find the indexes of the first and the last pages, then subtract one from another.
2. Pick the quoantile-point page assuming each page stores roughly the same number of tuples.
3. Return the starting key of the page, which is stored in memory.

Notes:

• The procedure doesn't read disk, i.e. it doesn't yield.
• If the target range is so small that there's no page that starts within it, the function will return nil even if there are tuples in the range because otherwise it'd have to yield, which we'd like to avoid.
• Since the data stored in the last layer may be completely deleted in more recent layers, there's no upper boundary for the error, i.e. the function will give adequate results only if there are no massive deletions or insertions.
• In particular, the function may give inadequate results for the time-series workload, when newer tuples have greater keys, although this should be somewhat alleviated by the fact that vinyl divides data into ranges. We could optimize this case by considering newer data layers in case they don't intersect with the deepest one, but this is postponed until we get to vinyl: make sure range splits don't break time-series use case #1917.