[SERVER-30449] ProjectionSpecValidator is O(N**2) in number of fields in the projection Created: 31/Jul/17 Updated: 30/Oct/23 Resolved: 11/Oct/17 |
|
| Status: | Closed |
| Project: | Core Server |
| Component/s: | Aggregation Framework |
| Affects Version/s: | None |
| Fix Version/s: | 3.4.11, 3.6.0-rc0 |
| Type: | Bug | Priority: | Major - P3 |
| Reporter: | Mathias Stearn | Assignee: | Bernard Gorman |
| Resolution: | Fixed | Votes: | 0 |
| Labels: | neweng | ||
| Remaining Estimate: | Not Specified | ||
| Time Spent: | Not Specified | ||
| Original Estimate: | Not Specified | ||
| Issue Links: |
|
||||||||||||
| Backwards Compatibility: | Fully Compatible | ||||||||||||
| Operating System: | ALL | ||||||||||||
| Backport Requested: |
v3.4
|
||||||||||||
| Sprint: | Query 2017-09-11, Query 2017-10-02, Query 2017-10-23 | ||||||||||||
| Participants: | |||||||||||||
| Description |
|
If it held the _seenPaths in a std::set() rather than a vector, it could check for prefix issues in O(N*logN) time. It may also be possible to use a StringMap to do it in O(N). |
| Comments |
| Comment by Daniel Grigg [ 26/Oct/17 ] | |||||||||||||||||||||||||||
|
Sweet! Thanks for getting this through so quickly! | |||||||||||||||||||||||||||
| Comment by Bernard Gorman [ 26/Oct/17 ] | |||||||||||||||||||||||||||
|
danielgrigg, this fix has now been backported to the 3.4 branch. Unfortunately, it narrowly missed the recent release of 3.4.10, but will be available in 3.4.11 (and, of course, in 3.6!) | |||||||||||||||||||||||||||
| Comment by Githook User [ 26/Oct/17 ] | |||||||||||||||||||||||||||
|
Author: {'email': 'bernard.gorman@gmail.com', 'name': 'Bernard Gorman', 'username': 'gormanb'}Message: | |||||||||||||||||||||||||||
| Comment by Githook User [ 11/Oct/17 ] | |||||||||||||||||||||||||||
|
Author: {'email': 'bernard.gorman@gmail.com', 'name': 'Bernard Gorman', 'username': 'gormanb'}Message: | |||||||||||||||||||||||||||
| Comment by David Storch [ 10/Oct/17 ] | |||||||||||||||||||||||||||
|
danielgrigg, we definitely plan to evaluate backport to the 3.4 branch once this is pushed to the master branch. Based on the proposed change in code review, a backport looks feasible. | |||||||||||||||||||||||||||
| Comment by Daniel Grigg [ 27/Sep/17 ] | |||||||||||||||||||||||||||
|
Oh man I'm looking forward to this! Are there plans to back port to 3.4 cross fingers or will we have to wait for 3.6? | |||||||||||||||||||||||||||
| Comment by Bernard Gorman [ 12/Sep/17 ] | |||||||||||||||||||||||||||
|
Some more representative results, 100 iterations on standalone mongod built with --opt=on:
| |||||||||||||||||||||||||||
| Comment by David Storch [ 11/Sep/17 ] | |||||||||||||||||||||||||||
|
bernard.gorman, woah! I am now satisfied with the resolution of | |||||||||||||||||||||||||||
| Comment by Bernard Gorman [ 11/Sep/17 ] | |||||||||||||||||||||||||||
|
Initial re-implementation with std::set and using the test data supplied by the customer on | |||||||||||||||||||||||||||
| Comment by Charlie Swanson [ 31/Aug/17 ] | |||||||||||||||||||||||||||
|
Moving to Needs Triage to re-evaluate as a team |