[SERVER-57513] SBE multi-planning can incorrectly favor a blocking SORT plan over a non-blocking plan Created: 07/Jun/21 Updated: 29/Oct/23 Resolved: 19/Jul/21 |
|
| Status: | Closed |
| Project: | Core Server |
| Component/s: | None |
| Affects Version/s: | None |
| Fix Version/s: | 5.1.0-rc0 |
| Type: | Bug | Priority: | Major - P3 |
| Reporter: | Martin Neupauer | Assignee: | David Storch |
| Resolution: | Fixed | Votes: | 0 |
| Labels: | sbe-post-v1, sbe-rollout | ||
| Remaining Estimate: | Not Specified | ||
| Time Spent: | Not Specified | ||
| Original Estimate: | Not Specified | ||
| Issue Links: |
|
||||||||
| Backwards Compatibility: | Fully Compatible | ||||||||
| Operating System: | ALL | ||||||||
| Sprint: | Query Execution 2021-06-28, Query Execution 2021-07-12, Query Execution 2021-07-26 | ||||||||
| Participants: | |||||||||
| Description |
|
Rerunning the famous Eliot's chess query game-search-test.js (github.com) shows different winning plans are selected.
We have to understand what is going on |
| Comments |
| Comment by Vivian Ge (Inactive) [ 06/Oct/21 ] | ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
|
Updating the fixversion since branching activities occurred yesterday. This ticket will be in rc0 when it’s been triggered. For more active release information, please keep an eye on #server-release. Thank you! | ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
| Comment by Githook User [ 19/Jul/21 ] | ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
|
Author: {'name': 'David Storch', 'email': 'david.storch@mongodb.com', 'username': 'dstorch'}Message: | ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
| Comment by David Storch [ 16/Jun/21 ] | ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
|
I've figured it out. The query is this:
We have single-field indexes on each of the fields mentioned in the match expression as well as on "date". The classic engine selects the following winning plan:
This plan scans the entire {date: 1} index, thereby avoiding a blocking SORT, and applies the filter to each of the corresponding documents. It ran in 58 milliseconds on my machine. SBE, on the other hand, is picking the following plan:
This is a bounded scan on the {minutes: 1} index followed by a blocking SORT. It ran in 120 milliseconds on my machine, which seems to confirm that the classic engine chose the right plan and the SBE engine chose the wrong one. The allPlansExecution output was unhelpful for diagnosing this bug due to
This shows scoring information for the five candidate plans. The first four involve a blocking sort, whereas the last is the non-blocking plan which scans the {date: 1} index. I confirmed using gdb that each of the first four blocking sort plans early-exited with a QueryTrialRunCompleted exception. This means that they each returned zero results during the trial period; the one advance listed in the productivity formula is due to this logic. Namely, we always add one to the actual number of advances. The fifth plan returned all 20 results during the trial period, resulting in 21 being used as the numerator for calculating the productivity ratio. So why did the {minutes: 1} plan end up beating the {date: 1} plan. Let's compare their productivity ratios:
The {minutes: 1} plan appears to be more productive because its denominator is so small. But why is the denominator so small? This means that the trial period ended after performing only about 60 reads from storage, whereas the trial period ended for all the other candidate plans after performing thousands of reads. The reason has to do with the early-exit logic implemented in the SBE sort stage. The current logic is to abort the trial period after a certain number of results have been ingested by the sort stage. In this case, that number of results is 20 because of the limit(20) in the query. This logic seems to be flawed, because we are scoring the plan not based on the ratio of the number of results ingested by the sort to numReads, but based on the ratio of the number of results ultimately returned at the root of the tree to numReads. Although it is true that the blocking sort plan which returns its first batch of results to the sort stage fastest is the best amongst the set of candidate plans which have a blocking sort, it doesn't seem valid to compare the resulting score of a blocking sort plan to a non-blocking one. This example shows that the blocking sort plan that exits earliest can have an artificially inflated score relative to candidate plans which do not have a blocking sort stage. I see two possible ways to fix SBE's plan selection logic for sorts:
| ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
| Comment by Kyle Suarez [ 15/Jun/21 ] | ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
|
martin.neupauer, could you share what plan we expect and what plan we actually get with SBE enabled? |