[SERVER-35693] Parsing of $in takes quadratic time due to O(n^2) boost::flat_set constructor Created: 19/Jun/18 Updated: 29/Oct/23 Resolved: 21/Jun/18 |
|
| Status: | Closed |
| Project: | Core Server |
| Component/s: | Querying |
| Affects Version/s: | 3.2.19, 3.4.9, 3.6.5, 4.0.0-rc6 |
| Fix Version/s: | 3.2.21, 3.4.16, 3.6.6, 4.0.1, 4.1.1 |
| Type: | Bug | Priority: | Critical - P2 |
| Reporter: | David Storch | Assignee: | David Storch |
| Resolution: | Fixed | Votes: | 0 |
| Labels: | None | ||
| Remaining Estimate: | Not Specified | ||
| Time Spent: | Not Specified | ||
| Original Estimate: | Not Specified | ||
| Issue Links: |
|
||||||||||||||||||||||||||||||||
| Backwards Compatibility: | Fully Compatible | ||||||||||||||||||||||||||||||||
| Operating System: | ALL | ||||||||||||||||||||||||||||||||
| Backport Requested: |
v4.0, v3.6, v3.4, v3.2
|
||||||||||||||||||||||||||||||||
| Sprint: | Query 2018-07-02 | ||||||||||||||||||||||||||||||||
| Participants: | |||||||||||||||||||||||||||||||||
| Case: | (copied to CRM) | ||||||||||||||||||||||||||||||||
| Linked BF Score: | 0 | ||||||||||||||||||||||||||||||||
| Description |
|
As of the fix for https://svn.boost.org/trac10/ticket/13140 For $in predicates with many elements, this causes a substantial performance regression. It is observable in that a large $in where the elements are pre-sorted outperforms a large $in where the elements are random by orders of magnitude. (When the $in elements are pre-sorted, the boost::flat_set constructor always inserts at the end of its vector, resulting in O(n log n) runtime.) We should either patch boost to improve the boost::flat_set constructor's performance, or work around the issue by pre-sorting the $in elements prior to invoking the constructor. |
| Comments |
| Comment by Githook User [ 29/Jun/18 ] |
|
Author: {'username': 'dstorch', 'name': 'David Storch', 'email': 'david.storch@10gen.com'}Message: (cherry picked from commit a6eae4759b792f86284006d475b00559fe96953c) |
| Comment by Githook User [ 28/Jun/18 ] |
|
Author: {'username': 'dstorch', 'name': 'David Storch', 'email': 'david.storch@10gen.com'}Message: |
| Comment by Githook User [ 22/Jun/18 ] |
|
Author: {'username': 'dstorch', 'name': 'David Storch', 'email': 'david.storch@10gen.com'}Message: (cherry picked from commit 50c6a174e67cdef97b1877b5ce8916dc55725fd5) |
| Comment by Githook User [ 22/Jun/18 ] |
|
Author: {'username': 'dstorch', 'name': 'David Storch', 'email': 'david.storch@10gen.com'}Message: (cherry picked from commit a6eae4759b792f86284006d475b00559fe96953c) |
| Comment by Githook User [ 21/Jun/18 ] |
|
Author: {'username': 'dstorch', 'name': 'David Storch', 'email': 'david.storch@10gen.com'}Message: |
| Comment by David Storch [ 20/Jun/18 ] |
|
The proposed fix for this ticket works around the issue in the query processing layer of the MongoDB server. In addition, we may wish to pursue a fix in the boost library itself. I have filed |