Skip to content
New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

Document index:quantile() #4975

Open
TarantoolBot opened this issue Mar 10, 2025 · 0 comments
Open

Document index:quantile() #4975

TarantoolBot opened this issue Mar 10, 2025 · 0 comments

Comments

@TarantoolBot
Copy link
Collaborator

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:

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.5) -- returns {2601}

-- Find the 90th percentile among all keys < 1000
s.index.pk:quantile(0.9, {}, {1000}) -- returns {784}

The target range is defined as the intersection of the following read
requests:

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

This means that using the empty key {} or nil for both begin_key
and end_key finds the quantile in the whole index. The function raises
an error if there can't possibly be any tuples in the target range, i.e.
if key_begin >= key_end.

The function returns nil if there are no tuples in the target
range or if it failed to find the quantile due to the limitations of
the storage engine, which are described below.

The function is implemented by memtx and vinyl tree indexes only.
In memtx the function returns the quantile point exactly. It has
the logarithmic complexity. It may return nil only if there are
no tuples in the target range. There's guaranteed to be a tuple
in the target range corresponding to the returned key.

The vinyl implementation returns the quantile point with a reasonable
degree of error for performance considerations. It has the logarithmic
complexity as well. There may or may not be a tuple in the target
range corresponding to the returned key. The function may return nil
even if the target range is not empty, in particular, if there are
no disk layers or if the range is smaller than the vinyl page size.

The function doesn't yield.

The function doesn't participate in transactions.

Like other index methods, index:quantile() can be used through
a space object as space:quantile(), in which case it works as
a shortcut for the primary index.

For more details, see the RFC document: https://github.com/orgs/tarantool/discussions/11194
Requested by @locker in tarantool/tarantool@a8df9b5.

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Labels
None yet
Projects
None yet
Development

No branches or pull requests

1 participant