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)

9 files changed, 227 insertions, 113 deletions

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 */
@@ -787,6 +768,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.
      */
     if (!F_ISSET(cbt, WT_CBT_ITERATE_NEXT))
@@ -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):