When we search for a key using the prefix search near optimization implemented in WT-7264 we early exit the search if _cursor_row_next or _cursor_row_prev return WT_NOTFOUND. However those functions return WT_NOTFOUND when they step to the end or the start of the page. As such if the prefix key_range extends across multiple pages the search will incorrectly return WT_NOTFOUND when in fact we should have found a value.
In order to fix this we'd need to differentiate between a prefix not found return and an end of page not found return. This could be implemented using a new WT error code.
I've written a python reproducer to demonstrate the flaw in the current algorithm:
import time, wiredtiger, wttest, unittest
from wiredtiger import statdef timestamp_str(t):
return '%x' % t# test_search_near01.py
# Test various prefix search near scenarios.
class test_search_near01(wttest.WiredTigerTestCase):
conn_config = 'statistics=(all)'
session_config = 'isolation=snapshot' def get_stat(self, stat, local_session = None):
if (local_session != None):
stat_cursor = local_session.open_cursor('statistics:')
else:
stat_cursor = self.session.open_cursor('statistics:')
val = stat_cursor[stat][2]
stat_cursor.close()
return val def test_base_scenario(self):
uri = 'table:test_base_scenario'
self.session.create(uri, 'key_format=u,value_format=u')
cursor = self.session.open_cursor(uri)
session2 = self.conn.open_session()
cursor3 = self.session.open_cursor(uri, None, "debug=(release_evict=true)") # Basic character array.
l = "abcdefghijklmnopqrstuvwxyz" # Start our older reader.
session2.begin_transaction() # Insert very large values so we fill the page content with less than 26 keys.
# The key range that we search for will be a minimum of 26 keys.
key_value = "abcde" * 100000
key_count = 26*26*26
# Insert keys aaa -> zzz.
for i in range (0, 26):
for j in range (0, 26):
for k in range (0, 26):
cursor[l[i] + l[j] + l[k]] = key_value # Evict the whole range.
for i in range (0, 26):
for j in range (0, 26):
for k in range (0, 26):
cursor3.set_key(l[i] + l[j] + l[k])
cursor3.search()
cursor3.reset() # Search near for the "aa" part of the range.
cursor2 = session2.open_cursor(uri)
cursor2.set_key('aa')
cursor2.search_near() skip_count = self.get_stat(stat.conn.cursor_next_skip_lt_100)
# This should be equal to roughly key_count * 2 as the aa range will be traversed forwards
# And then backwards, this assertion failing demonstrates the issue.
self.assertGreater(skip_count, key_count * 2)
In addition to fixing the code, the search near test created as part of WT-7924 should be executed with a more stressful configuration so keys are written across multiple pages. This configuration is a good start if not enough.
- depends on
-
WT-7264 Creating a new configuration for search near that allows it to exit quickly when searching for prefixes
-
- Closed
-
-
WT-7924 Create a stress test for prefix search near key validation
-
- Closed
-
- is depended on by
-
-
- Closed
-
-
-
- Closed
-
-
-
- Closed
-
- is related to
-
-
- Closed
-
-
-
- Closed
-
- related to
-
-
- Closed
-