Finish the CE part of the logarithmic offset RFC#10317
Merged
locker merged 4 commits intotarantool:masterfrom Sep 13, 2024
Merged
Finish the CE part of the logarithmic offset RFC#10317locker merged 4 commits intotarantool:masterfrom
locker merged 4 commits intotarantool:masterfrom
Conversation
f976931 to
5b982c5
Compare
b879ab6 to
2541bbd
Compare
mkostoevr
commented
Aug 1, 2024
11f1ff5 to
009b15a
Compare
009b15a to
68c7c76
Compare
1ea421e to
8e12b82
Compare
drewdzzz
requested changes
Sep 3, 2024
ca35e20 to
b16dff6
Compare
e1539da to
666f401
Compare
666f401 to
c5a2009
Compare
c5a2009 to
3a67264
Compare
3a67264 to
8702ece
Compare
drewdzzz
approved these changes
Sep 10, 2024
Contributor
drewdzzz
left a comment
There was a problem hiding this comment.
Thanks for the patch, LGTM!
locker
approved these changes
Sep 11, 2024
Contributor
Author
|
@lenkis, please take a look at the new version of the changelogs/unreleased/gh-8204-select-offset-count-perf.md. |
This method is used in order to perform the iterator creation with the offset specified. The generic implementation performs the regular iterator creation and skips the specified amount of tuples checking the fiber slice in the way, but now it's possible to implement an accelerated version of select with offset if an index supports that. Part of tarantool#8204 NO_DOC=internal NO_TEST=covered by existing tests NO_CHANGELOG=internal
Contributor
Author
|
Rebased and dropped the --- a/src/box/memtx_tx.c
+++ b/src/box/memtx_tx.c
@@ -340,12 +340,6 @@ memtx_tx_count_gap_item_new(struct txn *txn, enum iterator_type type,
const char *key, uint32_t part_count,
struct tuple *until, hint_t until_hint);
-/**
- * Destroy the count gap item.
- */
-static void
-memtx_tx_count_gap_item_destroy(struct gap_item_base *base);
-
/**
* Helper structure for searching for point_hole_item in the hash table,
* @sa point_hole_item_pool.
@@ -2983,7 +2977,6 @@ memtx_tx_delete_gap(struct gap_item_base *item)
pool = &txm.nearby_gap_item_mempoool;
break;
case GAP_COUNT:
- memtx_tx_count_gap_item_destroy(item);
pool = &txm.count_gap_item_mempool;
break;
case GAP_FULL_SCAN:
@@ -3372,7 +3365,11 @@ memtx_tx_nearby_gap_item_new(struct txn *txn, enum iterator_type type,
}
/**
- * Allocate and create count gap item.
+ * Allocate and create count gap item. The @a until tuple's story must have
+ * a gap item from the @a txn transaction or be tracked by it, so the story
+ * is not deleted by the garbage collector and the tuple is not deleted (if
+ * it's not NULL).
+ *
* Note that in_read_gaps base member must be initialized later.
*/
static struct count_gap_item *
@@ -3392,23 +3389,10 @@ memtx_tx_count_gap_item_new(struct txn *txn, enum iterator_type type,
sizeof(item->short_key), &item->key_len);
item->until = until;
item->until_hint = until_hint;
- if (item->until != NULL)
- tuple_ref(item->until);
return item;
}
-/**
- * Destroy the count gap item.
- */
-static void
-memtx_tx_count_gap_item_destroy(struct gap_item_base *base)
-{
- struct count_gap_item *item = (struct count_gap_item *)base;
- if (item->until != NULL)
- tuple_unref(item->until);
-}
-
/**
* Allocate and create full scan gap item.
* Note that in_read_gaps base member must be initialized later.
@@ -3465,6 +3449,8 @@ memtx_tx_track_gap_slow(struct txn *txn, struct space *space, struct index *inde
* tuples are skipped by a transaction without reading.
*
* @return the amount of invisible tuples counted.
+ *
+ * @pre The @a until tuple (if not NULL) must be clarified by @a txn.
*/
uint32_t
memtx_tx_track_count_until_slow(struct txn *txn, struct space *space,
diff --git a/src/box/memtx_tx.h b/src/box/memtx_tx.h
index dae5daf593..82ef370504 100644
--- a/src/box/memtx_tx.h
+++ b/src/box/memtx_tx.h
@@ -356,6 +356,8 @@ memtx_tx_track_count(struct txn *txn, struct space *space,
* NB: can trigger story garbage collection.
*
* @return the amount of invisible tuples counted.
+ *
+ * @pre The @a until tuple (if not NULL) must be clarified by @a txn.
*/
static inline uint32_t
memtx_tx_track_count_until(struct txn *txn, struct space *space, |
xuniq
approved these changes
Sep 12, 2024
This patch rewrites the memtx tree iterator creation path so it handles the offset parameter taking advantage of offset-based functions of the BPS tree with BPS_INNER_CARD config. It also introduces the memtx_tx_index_invisible_count_matching_until function which counts the amount of tuples matching with a key and iterator type until a tuple that are invisible to a transaction. Since the invisible count is required in order to update the tree iterator, the garbage collection is not performed in it anymore, it is performed in the `index_size` methods of memtx indexes instead. Part of tarantool#8204 @TarantoolBot document Title: select with offset and count are now logarithmic in memtx tree Product: Tarantool Since: 3.3.0 Root document: https://www.tarantool.io/en/doc/latest/reference/reference_lua/box_index/count/#lua-function.index_object.count > Iterate over an index, counting the number of tuples which match > the key-value. This is no longer true for the memtx tree index, where count has a logarithmic complexity (`O(log(size))` where `size` is the amount of tuples in the index) and it does not iterate over the index. --- Root document: https://www.tarantool.io/en/doc/latest/reference/reference_lua/box_index/select/#lua-function.index_object.select > `offset` – the number of tuples to skip (use this parameter carefully > when scanning large data sets). The part about large datasets is not actual for the memtx tree index now, since the complexity of select with offset there is logarithmic too (it does not scan the space either). > Use the offset option carefully when scanning large data sets as it > linearly increases the number of scanned tuples and leads to a full > space scan. Instead, you can use the after and fetch_pos options. Ditto. --- Root document: https://www.tarantool.io/en/doc/latest/platform/engines/memtx_vinyl_diff/ > count() function Takes a constant amount of time Now it takes logarithmic time as mentioned above.
The purpose of the argument is identical to the one in the `select`: it makes the iterator skip first N tuples prior to return. The `box_index_iterator_after` is removed as unused, since it's only been used by the Lua site for the `pairs` iterator creation. Part of tarantool#8204 @TarantoolBot document Title: A new `offset` parameter of the `index:pairs` method Product: Tarantool Since: 3.3.0 Now the `index:pairs` method supports the `offset` parameter which may be used to skip the specified amount of tuples of the iterator. If the skip caused the iterator to exhaust, it behaves as expected (no tuple is returned).
The method is used to get the (potential) 1-based iterator-relative position in the index of a tuple matching a key. Closes tarantool#8204 @TarantoolBot document Title: A new `index:offset_of` method introduced Product: Tarantool Since: 3.3.0 The method returns 0-based offset in the index of a first tuple matching the provided key and iterator. The position is counted from the beginning or end of the space depending on the iterator direction, for example: ``` lua -- index: {{1}, {3}} index:offset_of({3}, {iterator = 'eq'}) -- returns 1: [1, <3>] index:offset_of({3}, {iterator = 'req'}) -- returns 0: [<3>, 1] ``` In case there's no tuple matching the key and iterator in the index the function returns the position a matching tuple would be placed at if existed, for example: ``` lua -- index: {{1}, {3}} index:offset_of({2}, {iterator = 'eq'}) -- 1: [1, <2>, 3] index:offset_of({4}, {iterator = 'req'}) -- 0: [<4>, 3, 1] ``` This works with any iterator: ``` lua -- index: {{1}, {3}} index:offset_of({0}, {iterator = 'ge'}) -- 0: [<1>, 3] index:offset_of({1}, {iterator = 'lt'}) -- 2: [3, 1, <...>] -- index: {{'b'}, {'bb'}, {'bc'}, {'c'}, {'cc'}} index:offset_of({'b'}, {iterator = 'np'}) -- 3: [b, bb, bc, <c>, cc] index:offset_of({'cc'}, {iterator = 'pp'}) -- 1: [cc, <c>, bc, bb, b] ```
This file contains hidden or bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment
7 participants
Add this suggestion to a batch that can be applied as a single commit.This suggestion is invalid because no changes were made to the code.Suggestions cannot be applied while the pull request is closed.Suggestions cannot be applied while viewing a subset of changes.Only one suggestion per line can be applied in a batch.Add this suggestion to a batch that can be applied as a single commit.Applying suggestions on deleted lines is not supported.You must change the existing code in this line in order to create a valid suggestion.Outdated suggestions cannot be applied.This suggestion has been applied or marked resolved.Suggestions cannot be applied from pending reviews.Suggestions cannot be applied on multi-line comments.Suggestions cannot be applied while the pull request is queued to merge.Suggestion cannot be applied right now. Please check back later.
This patchset completes the CE part of the logarithmic offset RFC:
selectwithoffsetin memtx;offsetparameter ofindex:pairsmethod;index:offset_ofmethod.Closes #8204