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

Search history store can potentially walk the whole history store tree

    XMLWordPrintable

    Details

    • Type: Improvement
    • Status: Closed
    • Priority: Major - P3
    • Resolution: Fixed
    • Affects Version/s: None
    • Fix Version/s: WT10.0.0, 4.4.0-rc8, 4.7.0
    • Component/s: None
    • Labels:
      None
    • Story Points:
      8
    • Sprint:
      Storage - Ra 2020-06-01, Storage - Ra 2020-06-15

      Description

      When debugging WT-5665, I noticed we may walk the entire history store tree for searching. The test reads data without a timestamp. Suppose the value we want to search doesn't exist, we place the history store cursor on the key larger than the one we want to search and call prev in __wt_hs_cursor_position. The prev call may potentially walk the whole tree and return not found because all the keys' tombstones are visible to the current search transaction.

      This problem is exacerbated if we read without a timestamp. However, even if we read with a timestamp, this still can be pretty costly as a large chunk of the tree may be with tombstones that have timestamps visible to the search.

        Attachments

          Issue Links

            Activity

              People

              Assignee:
              alex.cameron Alex Cameron (Inactive)
              Reporter:
              chenhao.qu Chenhao Qu
              Votes:
              0 Vote for this issue
              Watchers:
              19 Start watching this issue

                Dates

                Created:
                Updated:
                Resolved: