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

btree row search performance

    • Type: Icon: Task Task
    • Resolution: Done
    • WT1.3
    • Affects Version/s: None
    • Component/s: None

      The inner loops of the row-store search routine has a check for an application-specific collator:

      #define WT_BTREE_CMP(s, bt, k1, k2, cmp)                                \
              (((bt)->collator == NULL) ?                                     \
              (((cmp) = __wt_btree_lex_compare((k1), (k2))), 0) :             \
              (bt)->collator->compare((bt)->collator, &(s)->iface,            \
                  (k1), (k2), &(cmp)))
      

      By removing the test for bt->collator == NULL, the inner loop for a skip-list search in *wt_search_insert() and in the btree page search in *wt_row_search() is roughly 15% faster:

       C: insert, key == 1: 1.95 
      NC: insert, key == 1: 1.73              11%     
      
       C: insert, key == 5000: 3.03
      NC: insert, key == 5000: 2.66           12%     
      
       C: insert, key == 9999: 0.82            0%      
      NC: insert, key == 9999: 0.83
      
       C: block, key == 1: 2.72               17%     
      NC: block, key == 1: 2.26 
      
       C: block, key == 5000: 0.83             8%      
      NC: block, key == 5000: 0.76
      
       C: block, key == 9999: 2.66            15%     
      NC: block, key == 9999: 2.25
      
      

      These are runs of 5 million searches on an inserted set of 10,000 key/value pairs, where we're first searching for the first record (key == 1), the middle record (key == 5000), and the last record (key == 9999).

      We could get this value back by creating two loops, where the value of the collator field is tested once, outside of the loop, at the cost of some code duplication.

      Is that worth doing?

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

              Created:
              Updated:
              Resolved: