Uploaded image for project: 'Core Server'
  1. Core Server
  2. SERVER-60202

Speed up isOnStepRelativeTo() with binary search

    • Type: Icon: Improvement Improvement
    • Resolution: Won't Fix
    • Priority: Icon: Major - P3 Major - P3
    • None
    • Affects Version/s: None
    • Component/s: None
    • Labels:
      None
    • Query Optimization

      Numeric ranges use some modulo arithmetic to determine whether a given value is on-step relative to the lower bound of an explicit range in constant time, and and date ranges with units that are smaller than one month use the same, after converting the dates to milliseconds. Time units that are a month long are longer cannot be represented with a constant number of milliseconds due to different lengths of months and leap days in different years. The current solution is to iterate up from the lower bound, incrementing by the step defined in the range, until the given value is either met (on step) or passed (off step).

       

      This function is called once for every document generated and could lead to performance issues in edge cases where there are lots of off-step documents between existing ones.

       

      The function could be sped up to perform a binary search for the given value rather than iterating up from the bottom of the range. Investigate after writing performance tests to see if a considerable amount of time is being spent inside this function for the affected time units.

            Assignee:
            backlog-query-optimization [DO NOT USE] Backlog - Query Optimization
            Reporter:
            davis.haupt@mongodb.com Davis Haupt (Inactive)
            Votes:
            0 Vote for this issue
            Watchers:
            1 Start watching this issue

              Created:
              Updated:
              Resolved: