[SERVER-65527] Use range bounded cursors in place of prefix search_near on unique indexes Created: 13/Apr/22  Updated: 16/Jan/24  Resolved: 26/Oct/22

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

Type: Improvement Priority: Major - P3
Reporter: Deepti Hasija Assignee: Gregory Wlodarek
Resolution: Fixed Votes: 0
Labels: None
Remaining Estimate: Not Specified
Time Spent: Not Specified
Original Estimate: Not Specified

Attachments: PNG File lower-bound-inefficient.png     PNG File master-search-next.png    
Issue Links:
Depends
depends on WT-9324 Add additional logic to cursor->searc... Closed
Related
related to SERVER-61185 Use prefix_search for unique index lo... Closed
related to SERVER-68380 Investigate MongoDB code that can use... Closed
Backwards Compatibility: Fully Compatible
Sprint: Execution Team 2022-08-08, Execution Team 2022-08-22, Execution Team 2022-10-03, Storage Engines - 2022-10-31
Participants:

 Description   

Unique index duplicate key check searches for the key's existence before insertion into the index. search_near cursor API is used for the purpose. With durable history, the search through a table with a lot of deleted content became more expensive hence causing regression with insertion into the unique indexes. A prefix-search API was added that would cause search_near to early exit if the search was past the prefix. The prefix-search is being replaced by a feature to configure bounds on a cursor.

An existing prefix search can be replaced with a cursor bound on the prefix. This ticket will do so for the above-mentioned unique index usage in the server.



 Comments   
Comment by Githook User [ 26/Oct/22 ]

Author:

{'name': 'Gregory Wlodarek', 'email': 'gregory.wlodarek@mongodb.com', 'username': 'GWlodarek'}

Message: SERVER-65527 Use range bounded cursors in place of prefix search_near on unique indexes
Branch: master
https://github.com/mongodb/mongo/commit/41efbd3eb4c79a9739b8360dd3acfa9f931fc5da

Comment by Sulabh Mahajan [ 25/Aug/22 ]

We have decided to put down this ticket for more time. We want to get feedback from bounded cursors on SERVER-65528 first as that seems to be the use case that will directly benefit from bounding the cursors.

Comment by Jie Chen [ 23/Aug/22 ]

From my understanding, I can give a go at explaining the differences in performance, especially why lower bound have little to no performance increase compared to a regular search near.

When the user only sets the lower bound, and performs a next(). WiredTiger internally positions the cursor on the lower bound, and does this through performing a search near on the lower bound. In the case that the data range has lots of invisible records between the lower bound and the first visible key, the bounded cursor functionality has would not early exit in this case because there are no upper bounds set. Thus doing so, it can potentially act exactly how a regular search near would work and explain the similar performance as a regular search near.

In the case that we do set the lower bound and upper bound, and if WT performs a next() it would internally perform search near the cursor on the lower, but be able to early exit on the upper bound. Which can possibly explain the big difference in performance here.

It would be interesting to check the performance of only setting the upper bound and performing a prev(). I would imagine it would behave the same since it also does a search near in this case. Something more interesting would be setting the upper bound and performing a search near as well.

Edit: When a lower bound is set, WT would internally call cursor_row_search() which attempts to position the cursor closest to the key (irrelevant of visibility). Furthermore the range cursor will check the visibility of the key. If the current position is not visible, we will perform a next() to find a visible key. My assumption is that the next() is taking a long time The range cursor project will look into this.

Comment by Sulabh Mahajan [ 22/Aug/22 ]

I scaled the repro up by a factor of 10 to get more input into performance differences, here is the time taken by the unique index updates:

Version Time taken (ms)
Master 4609
Master without prefix search 332583
Lower-and-upper-bounds-search-near 5161
Lower-and-upper-bounds-next 5043
Lower-bound-next 304351

I suspect that the versions where we set both the bounds would have been faster than the master if we would not been making a separate copy for the upper bound (prefix key's last byte incremented).

next = both upper and lower bounds then next() call to find the record
search-near = both upper and lower bounds then search_near() call to find the record
master = prefix search

The part that is unexpected is the version where we set the lower bound and follow with a next (I think it is the same for search-near) has to skip through a lot of records for some reason. This version is almost as inefficient as not having any bounds or prefix search:

lower-bound-next = Lower bound only then next() call to find the record
master-prefix-off = search-near with no bounds and no prefix search.

Comment by Sulabh Mahajan [ 12/Aug/22 ]

Here is the update from the work so far. I have tried to follow 2/3 approaches:

  • Bound the cursor to lower=prefix-key,inclusive and to upper=prefix-key-last-byte-incremented,exclusive. Do a search_near as before.
  • Bound the cursor to lower=prefix-key,inclusive and put no upper bound. Instead of a search_near, do a next and let the cursor bound only return keys that match the prefix.
  • Bound the cursor to lower=prefix-key,inclusive and to upper=prefix-key-last-byte-incremented,exclusive. Instead of a search_near, do a next and let the cursor bound only return keys that match the prefix.

I have run MongoDB patch tests and all approaches seem to work and not produce any immediately obvious bugs. I am still using the repro script from SERVER-56509 to test the performance locally. All approaches improve the performance compared to not having any sort of prefix search. Having an upper bound seems to be necessary for now - even when doing next instead of search_near. I am not sure why, I expected we wont be needing upper bound if we use next call. The best performance comes from having both the bounds and doing a next instead of search_near.

The next steps:

  • Understand the results - why not setting an upper bound and doing a next() is not as performant as setting an upper bound.
  • Run more conclusive performance testing
  • Discuss the results with the execution and WiredTiger team to decide which approach to follow. A similar approach could be used in other places in the code, so a discussion would help to generalise the approach.
Comment by Yujin Kang Park [ 06/Jul/22 ]

Depends on WT-9324 which makes search_near use the cursor bounds.

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