Fix off-by-one error in btree->maximum_depth

XMLWordPrintableJSON

    • Type: Bug
    • Resolution: Fixed
    • Priority: Minor - P4
    • WT12.0.0, 8.2.0-rc0
    • Affects Version/s: None
    • Component/s: Btree
    • None
    • Storage Engines, Storage Engines - Transactions
    • None
    • None
    • 0

      WT_BTREE.maximum_depth tracks the maximum depth of any search in the btree. This is available as the btree_maximum_depth data source statistic.

      It looks like we have an off by one error in computing this value and it is always one greater than it should be.

      This is computed in __wt_row_search():

          /* Search the internal pages of the tree. */
          current = &btree->root;
          for (depth = 2, pindex = NULL;; ++depth) {
              parent_pindex = pindex;
              page = current->page;
              if (page->type != WT_PAGE_ROW_INT)
                  break;
      
          . . .
      
          }
      
          /* Track how deep the tree gets. */
          if (depth > btree->maximum_depth)
              btree->maximum_depth = depth;
      

      The loop, above, is the relevant portion of descending a btree until we reach a leaf page. The elided part of the loop selects the correct child and pages it in, updating current to point to the child.

      The break statement shown near the beginning of the loop is where we exit the loop in non-error cases. If the current page is a leaf page (i.e., not WT_PAGE_ROW_INT), then we exit the loop, and update btree->maximum_depth the search was deeper than it's previous value.

      The problem here is initializing depth to 2, as can be seen by looking at what happens if we have a tree where the root points directly to leaf pages.

      On the first iteration of the loop, depth is initialized to 2. current points to the root page, which has page->type == WT_PAGE_ROW_INT.

      The body of the loop selects the correct child page, and updates current to point to it (reading it into cache if needed), and return to the beginning of the loop, where we increment depth to 3. This time the current page is not WT_PAGE_ROW_INT, so we break out of the loop with depth == 3, even though the three only had two levels.

            Assignee:
            Keith Smith
            Reporter:
            Keith Smith
            Votes:
            0 Vote for this issue
            Watchers:
            2 Start watching this issue

              Created:
              Updated:
              Resolved: