[SERVER-53503] Performance issue for $reduce vs. $map Created: 23/Dec/20 Updated: 27/Oct/23 Resolved: 07/May/21 |
|
| Status: | Closed |
| Project: | Core Server |
| Component/s: | Aggregation Framework |
| Affects Version/s: | 4.4.2 |
| Fix Version/s: | None |
| Type: | Improvement | Priority: | Minor - P4 |
| Reporter: | Wernfried Domscheit | Assignee: | Edwin Zhou |
| Resolution: | Works as Designed | Votes: | 0 |
| Labels: | aggregation-framework, performance | ||
| Remaining Estimate: | Not Specified | ||
| Time Spent: | Not Specified | ||
| Original Estimate: | Not Specified | ||
| Sprint: | Query Optimization 2021-05-03, Query Optimization 2021-05-17 |
| Participants: |
| Description |
| Comments |
| Comment by Edwin Zhou [ 07/May/21 ] | |||||||||||||||||||||||||||||||
|
Hi wernfried.domscheit@sunrise.net, Our investigation has led us to believe the current implementation of $reduce is working as designed. It appears the actual culprit is the $concatArrays expression used within the $reduce pipeline. When using $reduce, we build a new array by sequentially appending either the original value (if it differs from the previous value) or null. When we append to the new array with $concatArrays, it creates a copy of the array every time it appends arrays. For example, if we need to sequentially append 1000 values:
This involves a quadratic (N^2) number of element copies, copying an array for each element in the array that $reduce is working on. It does not appear trivial to eliminate the copying without a significant rework to the functionality of $concatArray When using $map, even though each array element is accessed twice, there is no O(N^2) copying involved. Instead every array value is sequentially replaced by the corresponding element from the original array (or null), preserving its structure. We hope this answers your inquiry. Best, | |||||||||||||||||||||||||||||||
| Comment by Edwin Zhou [ 24/Mar/21 ] | |||||||||||||||||||||||||||||||
|
Hi wernfried.domscheit@sunrise.net, Great work discovering a faster pipeline to fulfill your use case! It's indeed unusual and unhelpful behavior that two pipelines that perform the same task can have such a significant performance difference, and we agree that it's worth investigating. However, since we're hoping to improve the performance of reduce, I'll change this to an improvement and assign it to the appropriate team to further this investigation. Thanks, | |||||||||||||||||||||||||||||||
| Comment by Wernfried Domscheit [ 24/Mar/21 ] | |||||||||||||||||||||||||||||||
|
Actually this version is even faster:
On my test it takes app 3000ms instead of 4600ms Best Regards
| |||||||||||||||||||||||||||||||
| Comment by Wernfried Domscheit [ 24/Mar/21 ] | |||||||||||||||||||||||||||||||
|
Hi Edwin Zhou Your optimized pipeline requires a proper sorting of the values. In my application this is often the case, however it is not guaranteed. The array could be like this: { x: [22, 22, 80, 80, 80, 80, 80, 443, 443, 443, 80, 80, 80, 80, 5223, 5224] } For the moment I have to stick to the first version. Best Regards
| |||||||||||||||||||||||||||||||
| Comment by Edwin Zhou [ 23/Mar/21 ] | |||||||||||||||||||||||||||||||
|
Hi wernfried.domscheit@sunrise.net, I apologize for the delay in my investigation. I indeed noticed a similar regression between the two pipelines. The pipeline with $reduce took 8305ms to execute, and the pipeline with $map took 4587ms to execute, which is a significant regression! I took the time to optimize the $reduce pipeline and removed a $let stage:
This pipeline took 5596ms to execute:
While this doesn't match the desired performance of $map, it is a significant improvement from the previous pipeline using $reduce. Have you been able to settle on a pipeline that works best for you? Best, |