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

Prefix enabled search near only returns matching keys

    • Type: Icon: Bug Bug
    • Resolution: Fixed
    • Priority: Icon: Major - P3 Major - P3
    • WT10.0.1, 5.0.4, 4.4.10, 5.1.0-rc0
    • Affects Version/s: None
    • Component/s: None
    • None
    • 5
    • Storage - Ra 2021-09-20

      Context:
      A prefix search_near() call is a search_near() call configured with cursor configuration as prefix_key=true. The configuration allows the search_near() to exit early when the search reaches a key that is lexicographically greater than the intended set key.

      Prefix search_near() function calls become useful when keys are not all visible to the transaction. For example, in a table of keys ranging from "aaa" - "zzz" of timestamp 50, and the search_near() of key "aa" operates on a timestamp 25. A normal search_near() function would traverse all keys in the tree, to return WT_NOTFOUND. When prefix_key=true is configured, the search_near() function will only look at key ranges in the tree from "aaa" - "aaz", reducing the number of traversals needed to return back WT_NOTFOUND.

      Steps to reproduce the issues:

      Insert keys "aaa" - "aay" with timestamp 200
      Insert key "aaz" with timestamp 50
      Call search_near() with key "az", timestamp 100 (see problem 1)
      Call search_near() with key "aaza", timestamp 100 (see problem 2)

      Problem 1:
      With a transaction of read timestamp 100, search_near() for the key "az". The expected behaviour is WT_NOTFOUND, since there are no keys that match the prefix "az". However, the current output is returning back the closest visible entry "aaz". From looking at the code:

              if (btree->type == BTREE_ROW) {
                  WT_ERR(__cursor_row_search(cbt, true, NULL, NULL));
                  WT_ERR(__wt_cursor_valid(cbt, cbt->tmp, WT_RECNO_OOB, &valid));
              }
      

      The valid variable indicates if the cursor positioned by cursor_row_search is a valid entry. If so, the search_near returns back what the cursor is positioned on. In our case, the cursor is positioned on the key "aaz" after the call to cursor_row_search, which is a valid entry. However, it does not match the prefix key.

      Problem 2:
      With a transaction of read timestamp 100 and a search_near() call on a longer prefix "aaza", the expected behaviour is WT_NOTFOUND since there are no keys that have the same prefix "aaza". However, the current output is returning back the closest visible entry "aaz".

        1. repro-1.py
          3 kB
          Etienne Petrel

            Assignee:
            etienne.petrel@mongodb.com Etienne Petrel
            Reporter:
            jie.chen@mongodb.com Jie Chen
            Jie Chen
            Votes:
            0 Vote for this issue
            Watchers:
            5 Start watching this issue

              Created:
              Updated:
              Resolved: