Uploaded image for project: 'WiredTiger'
  1. WiredTiger
  2. WT-7912

Fix prefix search near optimisation to handle scenarios where the key range is split across pages.

    XMLWordPrintable

    Details

    • Type: Bug
    • Status: Open
    • Priority: Major - P3
    • Resolution: Unresolved
    • Affects Version/s: None
    • Fix Version/s: 5.1 Required
    • Component/s: None
    • Labels:
      None
    • Story Points:
      8
    • Sprint:
      Storage - Ra 2021-10-04

      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 stat
       
      def 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)
      

        Attachments

          Issue Links

            Activity

              People

              Assignee:
              backlog-server-storage-engines Backlog - Storage Engines Team
              Reporter:
              luke.pearson Luke Pearson
              Collaborators:
              Etienne Petrel
              Votes:
              0 Vote for this issue
              Watchers:
              24 Start watching this issue

                Dates

                Created:
                Updated: