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

pinned page cursor searches could check parent keys

    • Type: Icon: Improvement Improvement
    • Resolution: Done
    • Priority: Icon: Major - P3 Major - P3
    • WT2.8.0
    • Affects Version/s: None
    • Component/s: None
    • None

      michael.cahill, alexander.gorrod, we do a current-page check when a WT_CURSOR.search or WT_CURSOR.search-near operation is done on a cursor that's holding a page pinned, that is, if the cursor is holding a leaf page pinned, cursor search first checks if the search is directed at that leaf page before doing the more general full-tree search.

      I think it would be possible to check the leaf page's parent keys before doing the full binary search of the leaf page, avoiding the binary search entirely when the cursor is being re-positioned, at the cost of two additional searches when the cursor is not being re-positioned.

      To show the best case, I inserted a set of key/value pairs into 16KB leaf pages and then alternated cursor searches between two leaf pages. With a check of the parent page keys, the run is 31.38 seconds, without the check it's 36.02 seconds, a roughly 12% improvement.

      I used 16KB deliberately, and with smaller page sizes there's less improvement, as the comparisons of the parent page keys becomes a significant percentage of the comparisons done by the binary search. We could skip the test for small pages, of course.

      This change won't slow down searches where the cursor doesn't have a page pinned, but it will add two additional comparisons to searches of pinned pages that are going to succeed, where the key being searched for is on the page.

      Another note: to make this work, the search function has to look at the leaf page's parent key for itself, and for the subsequent key in the parent page's index. The former is safe, but the latter is a little trickier – I think it's safe, but, for example, that next WT_REF/WT_PAGE combination can split while we're looking at the key.

            Assignee:
            keith.bostic@mongodb.com Keith Bostic (Inactive)
            Reporter:
            keith.bostic@mongodb.com Keith Bostic (Inactive)
            Votes:
            0 Vote for this issue
            Watchers:
            2 Start watching this issue

              Created:
              Updated:
              Resolved: