[SERVER-2328] right now btree gets split 10/90 on right of rightmost bucket, 50/50 everywhere else. Should also do 90/10 on left of leftmost Created: 04/Jan/11  Updated: 06/Dec/22  Resolved: 14/Sep/18

Status: Closed
Project: Core Server
Component/s: Index Maintenance, MMAPv1
Affects Version/s: None
Fix Version/s: None

Type: Improvement Priority: Major - P3
Reporter: Antoine Girbal Assignee: Backlog - Storage Execution Team
Resolution: Won't Fix Votes: 1
Labels: None
Remaining Estimate: Not Specified
Time Spent: Not Specified
Original Estimate: Not Specified

Assigned Teams:
Storage Execution
Participants:

 Description   

some people create their index thinking about the usual query more than inserts.
For example for gridfs, people usually will query db.files.find(

{filename: "file"}

).sort(

{uploadDate: -1}

) to have most recent first.
And so index may get created like

{filename: 1, uploadDate: -1}

(which is what Python driver does).
But the actual inserts go with increasing date, so the btree grows by splitting 50/50 (left side).
The index ends up being twice as large as if the index was created in reverse order.

Inserted 100000 increasing numbers into ascending index:
> db.time.$time_1.stats()
{
"ns" : "mydb.time.$time_1",
"sharded" : false,
"primary" : "shard0000",
"ns" : "mydb.time.$time_1",
"count" : 452,
"size" : 3702784,
"avgObjSize" : 8192,
"storageSize" : 13191168,
"numExtents" : 4,
"nindexes" : 0,
"lastExtentSize" : 10438656,
"paddingFactor" : 1,
"flags" : 0,
"totalIndexSize" : 0,
"indexSizes" : {

},
"ok" : 1
}

Inserted 100000 decreasing numbers into ascending index:
> db.time.$time_1.stats()
{
"ns" : "test.time.$time_1",
"sharded" : false,
"primary" : "shard0001",
"ns" : "test.time.$time_1",
"count" : 813,
"size" : 6660096,
"avgObjSize" : 8192,
"storageSize" : 11141120,
"numExtents" : 4,
"nindexes" : 0,
"lastExtentSize" : 8388608,
"paddingFactor" : 1,
"flags" : 0,
"totalIndexSize" : 0,
"indexSizes" : {

},
"ok" : 1
}

we should split 90/10 on left of leftmost so that the order of index really doesnt matter.



 Comments   
Comment by Aaron Staple [ 04/Jan/11 ]

Right now we are actually doing a 90/10 split on the rightmost key of any bucket, not just the rightmost bucket. This was the requested initial implementation. We should probably do it just on the right bucket.

Mathias had some thoughts on caching the leftmost and rightmost buckets - these cached values could be used to determine if we are on left or rightmost bucket, or we could also determine these cases based on tree traversal.

Generated at Thu Feb 08 02:59:38 UTC 2024 using Jira 9.7.1#970001-sha1:2222b88b221c4928ef0de3161136cc90c8356a66.