From b9bdbb8040b71262d737b6481b212b00f38b9d1b Mon Sep 17 00:00:00 2001 From: Etienne Petrel Date: Mon, 4 Jul 2022 22:59:34 +0000 Subject: Import wiredtiger: 6cb26d60ec92eabdcb50badee7cc1f2205ba7384 from branch mongodb-master ref: 1a6de5cd90..6cb26d60ec for: 6.1.0-rc0 WT-9516 Use cursor_row_search on bounded next/prev impl (#8085) --- src/third_party/wiredtiger/import.data | 2 +- src/third_party/wiredtiger/src/btree/bt_curnext.c | 37 +++---- src/third_party/wiredtiger/src/btree/bt_curprev.c | 37 +++---- src/third_party/wiredtiger/src/btree/bt_cursor.c | 69 ++++++++++++ .../wiredtiger/src/include/btree_inline.h | 61 ----------- src/third_party/wiredtiger/src/include/extern.h | 4 +- .../wiredtiger/src/include/wiredtiger.in | 11 +- .../wiredtiger/test/suite/test_cursor_bound05.py | 116 +++++++++++++++++++++ src/third_party/wiredtiger/test/suite/wtbound.py | 3 - 9 files changed, 227 insertions(+), 113 deletions(-) create mode 100644 src/third_party/wiredtiger/test/suite/test_cursor_bound05.py (limited to 'src/third_party') diff --git a/src/third_party/wiredtiger/import.data b/src/third_party/wiredtiger/import.data index 1c2ba3e0f6b..4f416cbae26 100644 --- a/src/third_party/wiredtiger/import.data +++ b/src/third_party/wiredtiger/import.data @@ -2,5 +2,5 @@ "vendor": "wiredtiger", "github": "wiredtiger/wiredtiger.git", "branch": "mongodb-master", - "commit": "1a6de5cd900a85d95087fdb2acb74493bacded0c" + "commit": "6cb26d60ec92eabdcb50badee7cc1f2205ba7384" } diff --git a/src/third_party/wiredtiger/src/btree/bt_curnext.c b/src/third_party/wiredtiger/src/btree/bt_curnext.c index aa106d2504a..b716a5ad6c0 100644 --- a/src/third_party/wiredtiger/src/btree/bt_curnext.c +++ b/src/third_party/wiredtiger/src/btree/bt_curnext.c @@ -756,26 +756,7 @@ __wt_btcur_next_prefix(WT_CURSOR_BTREE *cbt, WT_ITEM *prefix, bool truncating) need_walk = false; session = CUR2S(cbt); total_skipped = 0; - /* - * If we have a bound set we should position our cursor appropriately if it isn't already - * positioned. - * - * In one scenario this function returns and needs to walk to the next record. In that case we - * set a boolean. We need to be careful that the entry flag isn't set so we don't re-enter - * search near. - * - * This logic must come before the call to __wt_cursor_func_init, as it will set the cbt active - * flag which changes the logic flow within the subsequent search near resulting in a - * segmentation fault. It is better to not set state prior to calling search near. Additionally - * the cursor initialization function does take a snapshot if required as does cursor search - * near. - */ - if (F_ISSET(cursor, WT_CURSTD_BOUND_LOWER) && !WT_CURSOR_IS_POSITIONED(cbt) && - !F_ISSET(cursor, WT_CURSTD_BOUND_ENTRY)) { - WT_ERR(__wt_btcur_bounds_row_position(session, cbt, true, &need_walk)); - if (!need_walk) - return (0); - } + WT_STAT_CONN_DATA_INCR(session, cursor_next); flags = WT_READ_NO_SPLIT | WT_READ_SKIP_INTL; /* tree walk flags */ @@ -786,6 +767,21 @@ __wt_btcur_next_prefix(WT_CURSOR_BTREE *cbt, WT_ITEM *prefix, bool truncating) WT_ERR(__wt_cursor_func_init(cbt, false)); + /* + * If we have a bound set we should position our cursor appropriately if it isn't already + * positioned. It is possible that the positioning function can directly return the record. For + * that to happen, the cursor must be placed on a valid record and must be positioned on the + * first record within the bounds. If the record is not valid or is not positioned within the + * bounds, continue the next traversal logic. + */ + if (F_ISSET(cursor, WT_CURSTD_BOUND_LOWER) && !WT_CURSOR_IS_POSITIONED(cbt)) { + WT_ERR(__wt_btcur_bounds_row_position(session, cbt, true, &need_walk)); + if (!need_walk) { + __wt_value_return(cbt, cbt->upd_value); + goto done; + } + } + /* * If we aren't already iterating in the right direction, there's some setup to do. */ @@ -899,6 +895,7 @@ __wt_btcur_next_prefix(WT_CURSOR_BTREE *cbt, WT_ITEM *prefix, bool truncating) WT_ERR_TEST(cbt->ref == NULL, WT_NOTFOUND, false); } +done: err: if (total_skipped < 100) WT_STAT_CONN_DATA_INCR(session, cursor_next_skip_lt_100); diff --git a/src/third_party/wiredtiger/src/btree/bt_curprev.c b/src/third_party/wiredtiger/src/btree/bt_curprev.c index 85b75d88e16..8ce4a73efff 100644 --- a/src/third_party/wiredtiger/src/btree/bt_curprev.c +++ b/src/third_party/wiredtiger/src/btree/bt_curprev.c @@ -693,26 +693,6 @@ __wt_btcur_prev(WT_CURSOR_BTREE *cbt, bool truncating) session = CUR2S(cbt); total_skipped = 0; - /* - * If we have a bound set we should position our cursor appropriately if it isn't already - * positioned. - * - * In one scenario this function returns and needs to walk to the next record. In that case we - * set a boolean. We need to be careful that the entry flag isn't set so we don't re-enter - * search near. - * - * This logic must come before the call to __wt_cursor_func_init, as it will set the cbt active - * flag which changes the logic flow within the subsequent search near resulting in a - * segmentation fault. It is better to not set state prior to calling search near. Additionally - * the cursor initialization function does take a snapshot if required as does cursor search - * near. - */ - if (F_ISSET(cursor, WT_CURSTD_BOUND_UPPER) && !WT_CURSOR_IS_POSITIONED(cbt) && - !F_ISSET(cursor, WT_CURSTD_BOUND_ENTRY)) { - WT_ERR(__wt_btcur_bounds_row_position(session, cbt, false, &need_walk)); - if (!need_walk) - return (0); - } WT_STAT_CONN_DATA_INCR(session, cursor_prev); /* tree walk flags */ @@ -723,6 +703,22 @@ __wt_btcur_prev(WT_CURSOR_BTREE *cbt, bool truncating) F_CLR(cursor, WT_CURSTD_KEY_SET | WT_CURSTD_VALUE_SET); WT_ERR(__wt_cursor_func_init(cbt, false)); + + /* + * If we have a bound set we should position our cursor appropriately if it isn't already + * positioned. It is possible that the positioning function can directly return the record. For + * that to happen, the cursor must be placed on a valid record and must be positioned on the + * first record within the bounds. If the record is not valid or is not positioned within the + * bounds, continue the prev traversal logic. + */ + if (F_ISSET(cursor, WT_CURSTD_BOUND_UPPER) && !WT_CURSOR_IS_POSITIONED(cbt)) { + WT_ERR(__wt_btcur_bounds_row_position(session, cbt, false, &need_walk)); + if (!need_walk) { + __wt_value_return(cbt, cbt->upd_value); + goto done; + } + } + /* * If we aren't already iterating in the right direction, there's some setup to do. */ @@ -838,6 +834,7 @@ __wt_btcur_prev(WT_CURSOR_BTREE *cbt, bool truncating) WT_ERR_TEST(cbt->ref == NULL, WT_NOTFOUND, false); } +done: err: if (total_skipped < 100) WT_STAT_CONN_DATA_INCR(session, cursor_prev_skip_lt_100); diff --git a/src/third_party/wiredtiger/src/btree/bt_cursor.c b/src/third_party/wiredtiger/src/btree/bt_cursor.c index 0135b91e428..5eddf2e8629 100644 --- a/src/third_party/wiredtiger/src/btree/bt_cursor.c +++ b/src/third_party/wiredtiger/src/btree/bt_cursor.c @@ -2113,3 +2113,72 @@ __wt_btcur_close(WT_CURSOR_BTREE *cbt, bool lowlevel) return (ret); } + +/* + * __wt_btcur_bounds_row_position -- + * A unpositioned bounded cursor need to start its cursor next and prev walk from the lower or + * upper bound depending on which direction it is going. This function calls cursor row search + * to position the cursor appropriately. + */ +int +__wt_btcur_bounds_row_position( + WT_SESSION_IMPL *session, WT_CURSOR_BTREE *cbt, bool next, bool *need_walkp) +{ + + WT_CURSOR *cursor; + WT_ITEM *bound; + bool key_out_of_bounds, valid; + uint64_t bound_flag, bound_flag_inclusive; + + key_out_of_bounds = false; + *need_walkp = false; + cursor = &cbt->iface; + bound = next ? &cursor->lower_bound : &cursor->upper_bound; + bound_flag = next ? WT_CURSTD_BOUND_UPPER : WT_CURSTD_BOUND_LOWER; + bound_flag_inclusive = next ? WT_CURSTD_BOUND_LOWER_INCLUSIVE : WT_CURSTD_BOUND_UPPER_INCLUSIVE; + + if (next) + WT_STAT_CONN_DATA_INCR(session, cursor_bounds_next_unpositioned); + else + WT_STAT_CONN_DATA_INCR(session, cursor_bounds_prev_unpositioned); + + WT_ASSERT(session, WT_DATA_IN_ITEM(bound)); + __wt_cursor_set_raw_key(cursor, bound); + WT_RET(__cursor_row_search(cbt, false, NULL, NULL)); + /* + * If there's an exact match, the row-store search function built the key in the cursor's + * temporary buffer. + */ + WT_RET(__wt_cursor_valid(cbt, (cbt->compare == 0 ? cbt->tmp : NULL), WT_RECNO_OOB, &valid)); + + /* + * Clear the cursor key set flag, as we don't want to return the internal set key to the user. + */ + F_CLR(cursor, WT_CURSTD_KEY_SET); + /* If the record is valid, set the cursor's key to the record. */ + if (valid) + WT_RET(__wt_key_return(cbt)); + + /* + * FIXME-WT-9324: When search_near_bounded is implemented then remove this. If search near + * returns a value, ensure it's within the bounds. + */ + if (valid && cbt->compare == 0 && F_ISSET(cursor, bound_flag_inclusive)) + return (0); + else if ((next ? cbt->compare > 0 : cbt->compare < 0) && valid) { + /* + * If cursor row search returns a non-exact key, check the returned key against the upper + * bound if doing a next, and the lower bound if doing a prev to ensure the key is within + * bounds. If not, there are no visible records, return WT_NOTFOUND. + */ + if (F_ISSET(cursor, bound_flag)) { + WT_RET(__wt_row_compare_bounds( + session, cursor, S2BT(session)->collator, next, &key_out_of_bounds)); + if (key_out_of_bounds) + return (WT_NOTFOUND); + } + return (0); + } + *need_walkp = true; + return (0); +} diff --git a/src/third_party/wiredtiger/src/include/btree_inline.h b/src/third_party/wiredtiger/src/include/btree_inline.h index d21475f1867..c7c371ae049 100644 --- a/src/third_party/wiredtiger/src/include/btree_inline.h +++ b/src/third_party/wiredtiger/src/include/btree_inline.h @@ -2230,64 +2230,3 @@ unlock: WT_REF_UNLOCK(ref, previous_state); return (0); } - -/* - * __wt_btcur_bounds_row_position -- - * A unpositioned bounded cursor need to start its cursor next and prev walk from the lower or - * upper bound depending on which direction it is going. This function calls search near to - * position the cursor appropriately. - */ -static inline int -__wt_btcur_bounds_row_position( - WT_SESSION_IMPL *session, WT_CURSOR_BTREE *cbt, bool next, bool *need_walk) -{ - - WT_CURSOR *cursor; - WT_DECL_RET; - WT_ITEM *bound; - int exact; - bool key_out_of_bounds; - uint64_t bound_flag, bound_flag_inclusive; - - key_out_of_bounds = false; - cursor = &cbt->iface; - bound = next ? &cursor->lower_bound : &cursor->upper_bound; - bound_flag = next ? WT_CURSTD_BOUND_UPPER : WT_CURSTD_BOUND_LOWER; - bound_flag_inclusive = next ? WT_CURSTD_BOUND_LOWER_INCLUSIVE : WT_CURSTD_BOUND_UPPER_INCLUSIVE; - exact = 0; - - if (next) - WT_STAT_CONN_DATA_INCR(session, cursor_bounds_next_unpositioned); - else - WT_STAT_CONN_DATA_INCR(session, cursor_bounds_prev_unpositioned); - - WT_ASSERT(session, WT_DATA_IN_ITEM(bound)); - __wt_cursor_set_raw_key(cursor, bound); - F_SET(cursor, WT_CURSTD_BOUND_ENTRY); - ret = cursor->search_near(cursor, &exact); - F_CLR(cursor, WT_CURSTD_BOUND_ENTRY); - WT_RET(ret); - - /* - * FIXME-WT-9324: When search_near_bounded is implemented then remove this. If search near - * returns a higher value, ensure it's within the upper bound. - */ - if (exact == 0 && F_ISSET(cursor, bound_flag_inclusive)) { - return (0); - } else if (next ? exact > 0 : exact < 0) { - /* - * If search near returns a non-exact key, check the returned key against the upper bound if - * doing a next, and the lower bound if doing a prev to ensure the key is within bounds. If - * not, there are no visible records, return WT_NOTFOUND. - */ - if (F_ISSET(cursor, bound_flag)) { - WT_RET(__wt_row_compare_bounds( - session, cursor, S2BT(session)->collator, next, &key_out_of_bounds)); - if (key_out_of_bounds) - return (WT_NOTFOUND); - } - return (0); - } - *need_walk = true; - return (0); -} diff --git a/src/third_party/wiredtiger/src/include/extern.h b/src/third_party/wiredtiger/src/include/extern.h index 57fc075583a..19cd98b8d30 100644 --- a/src/third_party/wiredtiger/src/include/extern.h +++ b/src/third_party/wiredtiger/src/include/extern.h @@ -258,6 +258,8 @@ extern int __wt_bm_corrupt(WT_BM *bm, WT_SESSION_IMPL *session, const uint8_t *a size_t addr_size) WT_GCC_FUNC_DECL_ATTRIBUTE((warn_unused_result)); extern int __wt_bm_read(WT_BM *bm, WT_SESSION_IMPL *session, WT_ITEM *buf, const uint8_t *addr, size_t addr_size) WT_GCC_FUNC_DECL_ATTRIBUTE((warn_unused_result)); +extern int __wt_btcur_bounds_row_position(WT_SESSION_IMPL *session, WT_CURSOR_BTREE *cbt, bool next, + bool *need_walkp) WT_GCC_FUNC_DECL_ATTRIBUTE((warn_unused_result)); extern int __wt_btcur_close(WT_CURSOR_BTREE *cbt, bool lowlevel) WT_GCC_FUNC_DECL_ATTRIBUTE((warn_unused_result)); extern int __wt_btcur_compare(WT_CURSOR_BTREE *a_arg, WT_CURSOR_BTREE *b_arg, int *cmpp) @@ -2026,8 +2028,6 @@ static inline double __wt_eviction_dirty_target(WT_CACHE *cache) WT_GCC_FUNC_DECL_ATTRIBUTE((warn_unused_result)); static inline int __wt_btcur_bounds_early_exit(WT_SESSION_IMPL *session, WT_CURSOR_BTREE *cbt, bool next, bool *key_out_of_bounds) WT_GCC_FUNC_DECL_ATTRIBUTE((warn_unused_result)); -static inline int __wt_btcur_bounds_row_position(WT_SESSION_IMPL *session, WT_CURSOR_BTREE *cbt, - bool next, bool *need_walk) WT_GCC_FUNC_DECL_ATTRIBUTE((warn_unused_result)); static inline int __wt_btcur_skip_page(WT_SESSION_IMPL *session, WT_REF *ref, void *context, bool visible_all, bool *skipp) WT_GCC_FUNC_DECL_ATTRIBUTE((warn_unused_result)); static inline int __wt_btree_block_free(WT_SESSION_IMPL *session, const uint8_t *addr, diff --git a/src/third_party/wiredtiger/src/include/wiredtiger.in b/src/third_party/wiredtiger/src/include/wiredtiger.in index 2823fbf8b98..ea5a86c23dc 100644 --- a/src/third_party/wiredtiger/src/include/wiredtiger.in +++ b/src/third_party/wiredtiger/src/include/wiredtiger.in @@ -772,12 +772,11 @@ struct __wt_cursor { #define WT_CURSTD_RAW_SEARCH 0x004000000ull #define WT_CURSTD_VALUE_EXT 0x008000000ull /* Value points out of tree. */ #define WT_CURSTD_VALUE_INT 0x010000000ull /* Value points into tree. */ -#define WT_CURSTD_BOUND_ENTRY 0x020000000ull -#define WT_CURSTD_BOUND_LOWER 0x040000000ull /* Lower bound. */ -#define WT_CURSTD_BOUND_LOWER_INCLUSIVE 0x080000000ull /* Inclusive lower bound. */ -#define WT_CURSTD_BOUND_UPPER 0x100000000ull /* Upper bound. */ -#define WT_CURSTD_BOUND_UPPER_INCLUSIVE 0x200000000ull /* Inclusive upper bound. */ -#define WT_CURSTD_VERSION_CURSOR 0x400000000ull /* Version cursor. */ +#define WT_CURSTD_BOUND_LOWER 0x020000000ull /* Lower bound. */ +#define WT_CURSTD_BOUND_LOWER_INCLUSIVE 0x040000000ull /* Inclusive lower bound. */ +#define WT_CURSTD_BOUND_UPPER 0x080000000ull /* Upper bound. */ +#define WT_CURSTD_BOUND_UPPER_INCLUSIVE 0x100000000ull /* Inclusive upper bound. */ +#define WT_CURSTD_VERSION_CURSOR 0x200000000ull /* Version cursor. */ /* AUTOMATIC FLAG VALUE GENERATION STOP 64 */ #define WT_CURSTD_KEY_SET (WT_CURSTD_KEY_EXT | WT_CURSTD_KEY_INT) #define WT_CURSTD_VALUE_SET (WT_CURSTD_VALUE_EXT | WT_CURSTD_VALUE_INT) diff --git a/src/third_party/wiredtiger/test/suite/test_cursor_bound05.py b/src/third_party/wiredtiger/test/suite/test_cursor_bound05.py new file mode 100644 index 00000000000..cd164615714 --- /dev/null +++ b/src/third_party/wiredtiger/test/suite/test_cursor_bound05.py @@ -0,0 +1,116 @@ +#!/usr/bin/env python +# +# Public Domain 2014-present MongoDB, Inc. +# Public Domain 2008-2014 WiredTiger, Inc. +# +# This is free and unencumbered software released into the public domain. +# +# Anyone is free to copy, modify, publish, use, compile, sell, or +# distribute this software, either in source code form or as a compiled +# binary, for any purpose, commercial or non-commercial, and by any +# means. +# +# In jurisdictions that recognize copyright laws, the author or authors +# of this software dedicate any and all copyright interest in the +# software to the public domain. We make this dedication for the benefit +# of the public at large and to the detriment of our heirs and +# successors. We intend this dedication to be an overt act of +# relinquishment in perpetuity of all present and future rights to this +# software under copyright law. +# +# THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, +# EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF +# MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. +# IN NO EVENT SHALL THE AUTHORS BE LIABLE FOR ANY CLAIM, DAMAGES OR +# OTHER LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, +# ARISING FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR +# OTHER DEALINGS IN THE SOFTWARE. + +import wiredtiger, wttest +from wtscenario import make_scenarios +from wtbound import bound_base + +# test_cursor_bound04.py +# Test special scenario with cursor bound API. Make sure that internal cursor search properly +# positions the cursor with bounds set as the prefix of the records. +class test_cursor_bound04(bound_base): + file_name = 'test_cursor_bound04' + key_format = 'S' + start_key = 1000 + end_key = 2000 + + types = [ + ('file', dict(uri='file:', use_colgroup=False)), + ('table', dict(uri='table:', use_colgroup=False)) + ] + + config = [ + ('evict', dict(evict=True)), + ('no-evict', dict(evict=False)) + ] + scenarios = make_scenarios(types, config) + + def create_session_and_cursor(self): + uri = self.uri + self.file_name + create_params = 'value_format=S,key_format={}'.format(self.key_format) + self.session.create(uri, create_params) + + cursor = self.session.open_cursor(uri) + self.session.begin_transaction() + for i in range(self.start_key, self.end_key + 1): + cursor[self.gen_key(i)] = "value" + str(i) + self.session.commit_transaction() + + if (self.evict): + evict_cursor = self.session.open_cursor(uri, None, "debug=(release_evict)") + for i in range(self.start_key, self.end_key): + evict_cursor.set_key(self.gen_key(i)) + evict_cursor.search() + evict_cursor.reset() + return cursor + + def test_bound_special_scenario(self): + cursor = self.create_session_and_cursor() + + # Test bound api: Test prefix key with lower bound. + self.set_bounds(cursor, 10, "lower", True) + self.cursor_traversal_bound(cursor, 10, None, True) + self.cursor_traversal_bound(cursor, 10, None, False) + self.assertEqual(cursor.bound("action=clear"), 0) + + + # Test bound api: Test prefix key with upper bound. + self.set_bounds(cursor, 20, "upper", False) + self.cursor_traversal_bound(cursor, None, 20, True, 999) + self.cursor_traversal_bound(cursor, None, 20, False, 999) + self.assertEqual(cursor.bound("action=clear"), 0) + + # Test bound api: Test prefix key works with both bounds. + self.set_bounds(cursor, 10, "lower", True) + self.set_bounds(cursor, 20, "upper", False) + self.cursor_traversal_bound(cursor, 10, 20, True, 999) + self.cursor_traversal_bound(cursor, 10, 20, False, 999) + self.assertEqual(cursor.bound("action=clear"), 0) + + self.set_bounds(cursor, 10, "lower", True) + self.set_bounds(cursor, 11, "upper", False) + self.cursor_traversal_bound(cursor, 10, 11, True, 99) + self.cursor_traversal_bound(cursor, 10, 11, False, 99) + self.assertEqual(cursor.bound("action=clear"), 0) + + # Test bound api: Test early exit works with lower bound (Greater than data range). + self.set_bounds(cursor, 30, "lower", True) + self.cursor_traversal_bound(cursor, 30, None, True, 0) + self.cursor_traversal_bound(cursor, 30, None, False, 0) + self.assertEqual(cursor.bound("action=clear"), 0) + + # Test bound api: Test early exit works with upper bound (Greater than data range). + self.set_bounds(cursor, 40, "upper", False) + self.cursor_traversal_bound(cursor, None, 40, True, 1000) + self.cursor_traversal_bound(cursor, None, 40, False, 1000) + self.assertEqual(cursor.bound("action=clear"), 0) + + cursor.close() + +if __name__ == '__main__': + wttest.run() diff --git a/src/third_party/wiredtiger/test/suite/wtbound.py b/src/third_party/wiredtiger/test/suite/wtbound.py index bd8d913f55d..e91f161913d 100644 --- a/src/third_party/wiredtiger/test/suite/wtbound.py +++ b/src/third_party/wiredtiger/test/suite/wtbound.py @@ -130,9 +130,6 @@ class bound_base(wttest.WiredTigerTestCase): if (self.lower_inclusive and lower_key): self.assertTrue(self.check_key(lower_key) <= key) elif (lower_key): - # print("lower key:") - # print(lower_key) - # print(key) self.assertTrue(self.check_key(lower_key) < key) if (self.upper_inclusive and upper_key): -- cgit v1.2.1