[SERVER-56157] Store MinMax data in flat data structure with user-defined field order Created: 19/Apr/21  Updated: 29/Oct/23  Resolved: 05/May/21

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

Type: Task Priority: Major - P3
Reporter: Henrik Edin Assignee: Henrik Edin
Resolution: Fixed Votes: 0
Labels: None
Remaining Estimate: Not Specified
Time Spent: Not Specified
Original Estimate: Not Specified

Issue Links:
Related
is related to SERVER-55942 Avoid sorting metadata object in Buck... Closed
Backwards Compatibility: Fully Compatible
Sprint: Execution Team 2021-05-03, Execution Team 2021-05-17
Participants:

 Description   

Currently the BucketCatalog uses a tree of StringMaps to store the min and max values for all fields stored in the bucket. This handles that objects inserted into the bucket may have an arbitrary field order set by the user.

We should be able to optimize for a fixed field order where we can traverse the MinMax tree in lock-step with traversing the object that is to be inserted. If the MinMax tree is stored in a flat data structure it should be very cache friendly for iteration at the cost of making insertions more expensive. Iterating over the object and to determine if min or max need to be updated or updating fields already existing is a way more common operation than encountering a field not previously seen in the bucket.

However, we still need to support objects with arbitrary field orders.



 Comments   
Comment by Githook User [ 05/May/21 ]

Author:

{'name': 'Henrik Edin', 'email': 'henrik.edin@mongodb.com', 'username': 'henrikedin'}

Message: SERVER-56157 Timeseries MinMax is now stored in a flat data structure to optimize traversal perf at the expense of inserts

When users are inserting measurements with a consistent field order we don't need to search and can just traverse the MinMax structure in lock-step with the measurement.
If users do not provide a consistent field order we fallback to map lookup when we reach a certain search threshold to limit impact of linear search.
Branch: master
https://github.com/mongodb/mongo/commit/3f43af643ccbd4bd2135dd5999410c2c5578fe1a

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