[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:
Backports
Duplicate
is duplicated by SERVER-30633 Large performance regression for larg... Closed
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: SERVER-30449 Reimplement ProjectionSpecValidator::ensurePathDoesNotConflictOrThrow using std::set
Branch: v3.4
https://github.com/mongodb/mongo/commit/1b740935e30f2e77bd1035194a402a52f0509f28

Comment by Githook User [ 11/Oct/17 ]

Author:

{'email': 'bernard.gorman@gmail.com', 'name': 'Bernard Gorman', 'username': 'gormanb'}

Message: SERVER-30449 Reimplement ProjectionSpecValidator::ensurePathDoesNotConflictOrThrow using std::set
Branch: master
https://github.com/mongodb/mongo/commit/bf805395e5943fe2db2391688b2eb124377e6456

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:

master --opt=on master + patch --opt=on 3.2.16 GA

{
    "_id" : null,
    "count" : 100,
    "min" : 40845,
    "max" : 47354,
    "avg" : 42613.16
}

{
    "_id" : null,
    "count" : 100,
    "min" : 1345,
    "max" : 1550,
    "avg" : 1426.7
}

{
    "_id" : null,
    "count" : 100,
    "min" : 1191,
    "max" : 1414,
    "avg" : 1286.78
}

Comment by David Storch [ 11/Sep/17 ]

bernard.gorman, woah! I am now satisfied with the resolution of SERVER-30633 as a dup of this ticket. Glad your initial work on this looks promising.

Comment by Bernard Gorman [ 11/Sep/17 ]

Initial re-implementation with std::set and using the test data supplied by the customer on SERVER-30633 reduced the runtime on my laptop from ~17 minutes to... 7 seconds. Note that both runs were on mongod built with --opt=off.

Comment by Charlie Swanson [ 31/Aug/17 ]

Moving to Needs Triage to re-evaluate as a team

Generated at Thu Feb 08 04:23:51 UTC 2024 using Jira 9.7.1#970001-sha1:2222b88b221c4928ef0de3161136cc90c8356a66.