tarantool / tarantool / 13768461042

88%

Build Type

push

github

Committed by locker

Commit Message

vinyl: implement index quantile method

We find the quantile key assuming that all keys are stored at the
deepest disk layer while newer layers contain incremental updates.
First, we walk over all index ranges overlapping with the target range
and estimate the number of tuples in them. Then we compute the offset of
the quantile key and walk over the index ranges again to find the key.

To achieve that, we need two helper functions:

 1. vy_run_estimate_stmt_count() estimates the number of tuples in
    the given run within the specified range. Basically, it finds
    the number of pages falling in the range, then scales down
    the total number of rows stored in the run proportionally,
    assuming that each page stores approximately the same number
    of rows.

 2. vy_run_estimate_key_at() finds a key at the given offset.
    Like vy_run_estimate_stmt_count(), this function assumes that
    each page stores approximately the same number of rows to
    find the page where the target key is located, then it returns
    the page min key, which should be a good enough approximation.

None of the functions accesses disk (yields).

Note that the target key may happen to be outside the target range, for
example, if the range is so small that there's no page fitting in it.
To follow the index:quantile() function protocol, we ignore such keys
(return NULL).

Also note that runs store extended keys so we need to strip extra parts
before returning the found key to the user.

Closes #11111

@TarantoolBot document
Title: Document `index:quantile()`

The new index method finds a quantile point in an indexed data range.
It takes the quantile level (0 < L < 1) and optionally the target range
boundaries and returns such a key that the ratio of tuples less than
the key equals L.

Example:

```lua
local s = box.schema.space.create('test')
s:create_index('pk')

for i = 1, 100 do
    s:insert({i * i, i})
end

-- Find the median in the whole index.
s.index.pk:quantile(0... (continued)

Run Details

70034 of 123619 branches covered (56.65%)

89 of 92 new or added lines in 3 files covered. (96.74%)

193 existing lines in 21 files now uncovered.

103159 of 117948 relevant lines covered (87.46%)

1908792.38 hits per line