[SERVER-66510] Improve performance of large $in queries in SBE Created: 16/May/22  Updated: 30/Mar/23

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

Type: Task Priority: Major - P3
Reporter: Ethan Zhang (Inactive) Assignee: Backlog - Query Execution
Resolution: Unresolved Votes: 0
Labels: None
Remaining Estimate: Not Specified
Time Spent: Not Specified
Original Estimate: Not Specified

Assigned Teams:
Query Execution
Sprint: QE 2022-06-13, QE 2022-06-27, QE 2022-07-11, QE 2022-07-25, QE 2022-08-08, QE 2022-08-22
Participants:

 Description   

The SBE implementation requires an entire $in array to be converted into an internal ArraySet type. This is a costly operation that needs to be performed for each input query, even with enabled auto-parameterization. The new plan cache cannot help here.

Relevant microbenchmarks:

  • Queries.UnindexedLargeInNonMatching -24.57%
  • Queries.UnindexedVeryLargeInSortedMatching -50.26%
  • Queries.UnindexedLargeInMatching -24.36%


 Comments   
Comment by David Storch [ 27/Mar/23 ]

The current list of benchmarks for which we still see regressions considered "critical" is:

  • Aggregation.UnindexedLargeInMatching
  • Aggregation.UnindexedLargeInNonMatching
  • Aggregation.UnindexedVeryLargeInSortedMatching
  • Queries.IdentityView.UnindexedLargeInMatching
  • Queries.IdentityView.UnindexedLargeInNonMatching
  • Queries.IdentityView.UnindexedVeryLargeInSortedMatching
  • Queries.UnindexedLargeInMatching
  • Queries.UnindexedLargeInNonMatching
  • Queries.UnindexedVeryLargeInSortedMatching
  • Queries.UnindexedVeryLargeInUnsortedMatching
Comment by Zixuan Zhuang [ 18/Aug/22 ]

We decided to keep the sbe $in implementation as-is, the root cause of regression is that sbe stage builder constructs an additional hash table for $in array, this allows us to use faster hash lookup during runtime, the overhead is only significant for tiny collections. (details in Large $in Benchmark and Profiling)

Comment by Kyle Suarez [ 07/Jul/22 ]

For an indexed $in, it turns out that the system needs the sort to happen. We're a little blocked here. Need to schedule a meeting to brainstorm?

david.storch@mongodb.com says that we could generate the index bounds unsorted and then sort those bounds, but it feels like that defeats the entire purpose of avoiding the sort.

Comment by David Storch [ 23/Jun/22 ]

zixuan.zhuang@mongodb.com has discovered that part of the problem is that even when the $in executes in SBE, the MatchExpression code still prepares a deduplicated and sorted vector of the $in elements. This is wasted effort since it is only needed for MatchExpression execution, but the actual execution ends up happening in SBE.

Comment by Pawel Terlecki [ 17/Jun/22 ]

Thanks for the details, anton.korshunov@mongodb.com. Yes makes sense to use the same trick.

Comment by Anton Korshunov [ 17/Jun/22 ]

pawel.terlecki@mongodb.com It's both. First of all, we need to copy (and convert to an SBE value) each element in a large $in array into an internal ArraySet type, and we need to do it even with the plan cache and auto-parameterization when we bind in input parameters (that's why the plan cache project didn't make a huge difference in recovering the performance of large $in queries). The classic engine doesn't make any copies - it creates a new vector of BSONElements which point to the same memory in the original find command BSON, and then simply sorts and dedups this vector, so we really spend time only on sorting. This issue manifests in Queries.UnindexedLargeInNonMatching and Queries.UnindexedLargeInMatching queries.

Secondly, we cannot exploit the fact that the input array is already pre-sorted, so the classic engine simply bails out if the original input arrays is already sorted, while in SBE we yet again create a full copy of the $in equalities. This manifests in Queries.UnindexedVeryLargeInSortedMatching.

The last time we discussed it with martin.neupauer@mongodb.com we figured that one way to recover the perf would be to use the same approach as the classic engine and use a binary search to lookup for matches.

Comment by Pawel Terlecki [ 16/Jun/22 ]

anton.korshunov@mongodb.commartin.neupauer@mongodb.com i may be remembering wrong. is it just about the expensive copying into an internal ArraySet type or also not using the binary search when array is sorted?

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