[SERVER-81094] Opening databases at startup has quadratic behaviour Created: 15/Sep/23  Updated: 27/Oct/23  Resolved: 27/Oct/23

Status: Closed
Project: Core Server
Component/s: None
Affects Version/s: None
Fix Version/s: 7.2.0-rc0

Type: Bug Priority: Major - P3
Reporter: Josef Ahmad Assignee: David Dominguez Sal
Resolution: Fixed Votes: 0
Labels: None
Remaining Estimate: Not Specified
Time Spent: Not Specified
Original Estimate: Not Specified

Attachments: PNG File flame_graph.png     File flame_graph.svg    
Issue Links:
Related
Assigned Teams:
Storage Execution EMEA
Backwards Compatibility: Fully Compatible
Operating System: ALL
Sprint: Execution EMEA Team 2023-10-30
Participants:

 Description   

Startup opens all databases, and for each opened database, it compares it against all previously opened databases to check for duplicates. This is quadratic. A test opening 50k databases takes about a minute; with 100k databases, it takes over ten minutes.



 Comments   
Comment by Githook User [ 27/Oct/23 ]

Author:

{'name': 'David Dominguez-Sal', 'email': 'david.dominguez@mongodb.com', 'username': ''}

Message: SERVER-81094 Added new indexation in DatabaseImpl for constant time location of conflicting databases by name
Branch: master
https://github.com/mongodb/mongo/commit/2d7f612e46c0469fca43069b5a3fcde9e68b9439

Comment by David Dominguez Sal [ 27/Oct/23 ]

Added a new index to provide constant complexity for name collision lookup

Comment by David Dominguez Sal [ 17/Oct/23 ]

The new implementation takes constant time to open a DB. So, the growth is now linear instead of quadratic.

Performance test for DatabaseImpl::openDB:

Old implementation

Tables Time[ms]
100 0
1000 5
5000 129
10000 583
50000 25782
100000 110487

New implementation

Tables Time[ms]
100 0
1000 2
5000 9
10000 17
50000 94
100000 195
Generated at Thu Feb 08 06:45:27 UTC 2024 using Jira 9.7.1#970001-sha1:2222b88b221c4928ef0de3161136cc90c8356a66.