Details
Description
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.
Attachments
Issue Links
- 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
-
WT-7264 Creating a new configuration for search near that allows it to exit quickly when searching for prefixes
-
- Closed
-
-
SERVER-61185 Use prefix_search for unique index lookup
-
- Closed
-
-
WT-8280 Temporarily disable prefix assert
-
- Closed
-
- is related to
-
WT-7264 Creating a new configuration for search near that allows it to exit quickly when searching for prefixes
-
- Closed
-
-
SERVER-70882 Add a new concurrency workload for the issue identified in WT-7912
-
- Closed
-
- related to
-
WT-8909 Disable cpp test search_near_01 on 4.4
-
- Closed
-