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

box: introduce next and previous prefix iterators #10028

Merged
merged 1 commit into from
May 22, 2024

Conversation

alyapunov
Copy link
Contributor

Implement 'np' (next prefix) and 'pp' (previous prefix) iterators. They work only in memtx tree and in a nutshell searches for strings with greater ('np') or less ('pp') prefix of size as in given key, comparing with given key.

Closes #9994

@TarantoolBot document
Title:'np' and 'pp' (next/previous prefix) iterators

Now there are two more iterators avaialbe: 'np' (next prefix) and 'pp' (previous prefix). They work only in memtx tree. Also, if the last part of key is not a string, they degrade to 'gt' and 'lt' iterators.

These iterators introduce special comparison of the last part of key (if it is a string). In terms of lua, if s is the search part, and t is the corresponding tuple part, 'np' iterator searches for the first tuple with string.sub(t, 1, #s) > s, while 'pp' searches for the last tuple with string.sub(t, 1, #s) < s.

Comparison of all other parts of the key remains normal.

As usual, these iterators are available both in select and pairs, in index and space methods.

Similar to all other tree iterators, they change only initial search of selection. Once the first tuple found, the rest are selected sequentially in direct (for 'np') or reverse (for 'pp') order of the index.

For example:

tarantool> s:select{}
---
- - ['a']
  - ['aa']
  - ['ab']
  - ['b']
  - ['ba']
  - ['bb']
  - ['c']
  - ['ca']
  - ['cb']
...

tarantool> s:select({'b'}, {iterator = 'np'})
---
- - ['c']
  - ['ca']
  - ['cb']
...

tarantool> s:select({'b'}, {iterator = 'pp'})
---
- - ['ab']
  - ['aa']
  - ['a']
...

@alyapunov alyapunov requested a review from a team as a code owner May 17, 2024 16:31
@alyapunov alyapunov requested review from drewdzzz and Gumix May 17, 2024 16:32
@alyapunov alyapunov force-pushed the gh-9994-next-prefix-iterator branch 2 times, most recently from 6ec0d2b to 28bc8bf Compare May 17, 2024 16:39
@coveralls
Copy link

coveralls commented May 17, 2024

Coverage Status

coverage: 87.1% (+0.003%) from 87.097%
when pulling f852aa3 on alyapunov:gh-9994-next-prefix-iterator
into ab0f791
on tarantool:master
.

@sergepetrenko sergepetrenko assigned Gumix and drewdzzz and unassigned sergepetrenko May 20, 2024
Copy link
Contributor

@drewdzzz drewdzzz left a comment

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

LGTM

@drewdzzz drewdzzz removed their assignment May 20, 2024
@alyapunov alyapunov force-pushed the gh-9994-next-prefix-iterator branch from 79150bd to 756fc62 Compare May 21, 2024 16:03
@Gumix Gumix assigned alyapunov and unassigned Gumix May 21, 2024
@alyapunov alyapunov force-pushed the gh-9994-next-prefix-iterator branch from 756fc62 to aa75730 Compare May 22, 2024 10:14
Implement 'np' (next prefix) and 'pp' (previous prefix) iterators.
They work only in memtx tree and in a nutshell searches for
strings with greater ('np') or less ('pp') prefix of size as in
given key, comparing with given key.

Closes tarantool#9994

@TarantoolBot document
Title: 'np' and 'pp' (next/previous prefix) iterators

Now there are two more iterators available: 'np' (next prefix)
and 'pp' (previous prefix). They work only in memtx tree. Also,
if the last part of key is not a string, they degrade to 'gt'
and 'lt' iterators.

These iterators introduce special comparison of the last part of
key (if it is a string). In terms of lua, if s is the search part,
and t is the corresponding tuple part, 'np' iterator searches for
the first tuple with string.sub(t, 1, #s) > s, while 'pp' searches
for the last tuple with string.sub(t, 1, #s) < s.

Comparison of all other parts of the key remains normal.

As usual, these iterators are available both in select and pairs,
in index and space methods.

Similar to all other tree iterators, they change only initial
search of selection. Once the first tuple found, the rest are
selected sequentially in direct (for 'np') or reverse (for 'pp')
order of the index.

For example:
```
tarantool> s:select{}
---
- - ['a']
  - ['aa']
  - ['ab']
  - ['b']
  - ['ba']
  - ['bb']
  - ['c']
  - ['ca']
  - ['cb']
...

tarantool> s:select({'b'}, {iterator = 'np'})
---
- - ['c']
  - ['ca']
  - ['cb']
...

tarantool> s:select({'b'}, {iterator = 'pp'})
---
- - ['ab']
  - ['aa']
  - ['a']
...
```
@alyapunov alyapunov force-pushed the gh-9994-next-prefix-iterator branch from aa75730 to f852aa3 Compare May 22, 2024 10:16
@alyapunov alyapunov added the full-ci Enables all tests for a pull request label May 22, 2024
@alyapunov
Copy link
Contributor Author

Both problems that lint was found are false-positive.

@alyapunov alyapunov merged commit 96df090 into tarantool:master May 22, 2024
92 of 93 checks passed
@alyapunov alyapunov deleted the gh-9994-next-prefix-iterator branch May 24, 2024 15:21
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Labels
full-ci Enables all tests for a pull request
Projects
None yet
Development

Successfully merging this pull request may close these issues.

new iterator for TREE index: NP (NextPrefix)
6 participants