[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:
|
| Comments |
| Comment by David Storch [ 27/Mar/23 ] |
|
The current list of benchmarks for which we still see regressions considered "critical" is:
|
| 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? |