[SERVER-60202] Speed up isOnStepRelativeTo() with binary search Created: 24/Sep/21 Updated: 06/Dec/22 Resolved: 04/Oct/21 |
|
| Status: | Closed |
| Project: | Core Server |
| Component/s: | None |
| Affects Version/s: | None |
| Fix Version/s: | None |
| Type: | Improvement | Priority: | Major - P3 |
| Reporter: | Davis Haupt (Inactive) | Assignee: | Backlog - Query Optimization |
| Resolution: | Won't Fix | Votes: | 0 |
| Labels: | None | ||
| Remaining Estimate: | Not Specified | ||
| Time Spent: | Not Specified | ||
| Original Estimate: | Not Specified | ||
| Issue Links: |
|
||||||||
| Assigned Teams: |
Query Optimization
|
||||||||
| Participants: | |||||||||
| Description |
|
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. |
| Comments |
| Comment by Davis Haupt (Inactive) [ 04/Oct/21 ] |
|
Left comment on the ticket that performance differences observed in testing can't be explained by isOnStepRelativeTo(), so this optimization is not necessary. |
| Comment by Davis Haupt (Inactive) [ 04/Oct/21 ] |
|
After PERF-2380, it's clear that for densification workloads, pipelines working with numeric and millisecond step units run with similar latencies, and pipelines working with hour and month step units run about slower, especially with partitions and smaller steps. It would make sense that any discrepancy would be more visible with those settings since smaller step sizes and partitioning the collection both result in more documents being generated. The gaps are visible even in the range: "full" case with no partitions, however, which is one piece of evidence to suggest that the discrepancies are not directly related to this function. What's interesting is that month and hour step units are so similar. If there was an inefficiency within isOnStepRelativeTo(), I would expect hour to be grouped with millisecond and numeric units. I would guess that the differing performance for numeric steps and date units larger than millisecond lies in the implementation of dateAdd() function. |
| Comment by Davis Haupt (Inactive) [ 28/Sep/21 ] |
|
After some refactoring and optimization, isOnStepRelativeTo() is only being called with `_current` as the base rather than any lower bound. Since `_current` is generally being updated/incremented as documents are generated, this makes it very likely that there will never be a loop with more than a few iterations, even in the worst case. This should be confirmed with PERF-2381, but if there is no real difference between constant and variable-length unit durations, then this ticket can be closed. |