[SERVER-55186] Experiment with binary search in $in SBE implementation Created: 15/Mar/21  Updated: 06/Dec/22

Status: Backlog
Project: Core Server
Component/s: None
Affects Version/s: None
Fix Version/s: None

Type: Improvement Priority: Major - P3
Reporter: Nikita Lapkov (Inactive) Assignee: Backlog - Query Execution
Resolution: Unresolved Votes: 0
Labels: sbe-post-v1
Remaining Estimate: Not Specified
Time Spent: Not Specified
Original Estimate: Not Specified

Assigned Teams:
Query Execution
Participants:

 Description   

Classic engine uses binary search to check if equalities specified in $in match expression contain given BSON element. Equalities are stored as a vector of deduplicated and sorted BSON elements (see _equalitySet field of InMatchExpression).

SBE uses ArraySet (see corresponding builder) to construct equalities set, ignoring the fact that equalities are deduplicated and sorted.

We should try to experiment with binary search implementation in SBE. This can potentially be beneficial since we do not need to spend time constructing ArraySet and we use the pre-processing of equalities set performed in InMatchExpression.


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