[SERVER-41872] PlanEnumerator AndAssignment::choices ordering not stable and is relevant to set of plans generated Created: 21/Jun/19 Updated: 29/Oct/23 Resolved: 18/Oct/19 |
|
| Status: | Closed |
| Project: | Core Server |
| Component/s: | None |
| Affects Version/s: | 4.2.0-rc1 |
| Fix Version/s: | 4.3.1, 4.2.4, 4.0.21 |
| Type: | Bug | Priority: | Major - P3 |
| Reporter: | James Wahlin | Assignee: | James Wahlin |
| Resolution: | Fixed | Votes: | 0 |
| Labels: | greenerbuild, query-44-grooming | ||
| Remaining Estimate: | Not Specified | ||
| Time Spent: | Not Specified | ||
| Original Estimate: | Not Specified | ||
| Issue Links: |
|
||||||||||||||||
| Backwards Compatibility: | Fully Compatible | ||||||||||||||||
| Operating System: | ALL | ||||||||||||||||
| Backport Requested: |
v4.2, v4.0, v3.6
|
||||||||||||||||
| Sprint: | Query 2019-07-15, Query 2019-07-29, Query 2019-08-12, Query 2019-08-26 | ||||||||||||||||
| Participants: | |||||||||||||||||
| Linked BF Score: | 0 | ||||||||||||||||
| Description |
|
The following diff includes a jstest that will shift between 2 sets of candidate plans depending on the run. We would expect the set of plans generated to remain constant across test executions.
|
| Comments |
| Comment by Githook User [ 03/Nov/20 ] | ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
|
Author: {'name': 'Charlie Swanson', 'email': 'charlie.swanson@mongodb.com', 'username': 'cswanson310'}Message: Revert " This reverts commit b010331e00cb46efe4e98e0f74150854b4407d67. | ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
| Comment by Githook User [ 30/Sep/20 ] | ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
|
Author: {'name': 'James Wahlin', 'email': 'james.wahlin@mongodb.com', 'username': 'jameswahlin'}Message: (cherry picked from commit 6ca9be706ce03a2c79d29feac3cfd294cc09445d) | ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
| Comment by Githook User [ 30/Sep/20 ] | ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
|
Author: {'name': 'James Wahlin', 'email': 'james.wahlin@mongodb.com', 'username': 'jameswahlin'}Message: (cherry picked from commit 6ca9be706ce03a2c79d29feac3cfd294cc09445d) | ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
| Comment by Githook User [ 07/Feb/20 ] | ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
|
Author: {'name': 'James Wahlin', 'username': 'jameswahlin', 'email': 'james.wahlin@mongodb.com'}Message: (cherry picked from commit 6ca9be706ce03a2c79d29feac3cfd294cc09445d) | ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
| Comment by Githook User [ 18/Oct/19 ] | ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
|
Author: {'username': 'jameswahlin', 'email': 'james.wahlin@mongodb.com', 'name': 'James Wahlin'}Message: | ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
| Comment by James Wahlin [ 27/Sep/19 ] | ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
|
On evaluating this again today, I found that we can replace the stdx::unordered_map with std::map for IndexToPredMap. Performance is in-line with existing implementation and this provides stable ordering. My earlier findings detailed above were incorrect due to a log level 0 debug message I forgot to remove when testing. Will post a patch for this next week. | ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
| Comment by James Wahlin [ 13/Sep/19 ] | ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
|
I spent time today reviewing potential fixes. The three options I identified are: The simplest solution would be #3. Use of a std::map would allow for us to maintain a stable iteration state. I ran a perf patch which changed both idxToFirst and idxToNotFirst to use std::set. This proved to have a meaningful impact on performance so won't be viable. I plan to follow this with a patch that only makes the change to idxToFirst, but suspect there may still be an impact as we perform lookups in this structure as well. For #1, 'choices' is a list of AndEnumerableState, which then contains 2 vectors containing 'OneIndexAssignment' and 'MemoID'. It is not immediately clear to me how we would want to sort this list though we could spend more time thinking about it. | ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
| Comment by Charlie Swanson [ 12/Sep/19 ] | ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
|
james.wahlin can you give a shot at fixing this as part of BF Friday? Thanks! | ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
| Comment by James Wahlin [ 04/Sep/19 ] | ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
|
david.storch to clarify, in the 0 and 1 solution case, the PlanEnumerator generates 12 plans which are then passed to QueryPlannerAnalysis::analyzeDataAccess() to determine whether they are valid solutions. QueryPlannerAnalysis::analyzeDataAccess() is the step that is removing either 11 or 12 plans from contention. The reason that plans are removed is that they are not covered plans and QueryPlanner::plan() is executed with the NO_UNCOVERED_PROJECTIONS option. When 0 solutions are produced, QueryPlanner::plan() is executed a second time with the projection omitted. This allows for all 12 plans to be considered. | ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
| Comment by David Storch [ 30/Aug/19 ] | ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
|
james.wahlin, thanks for the detailed write-up! There's a part of this that I'm missing, though. Based on the memo structures from the logs, it looks like there are a large number of valid plans that could be output by the plan enumerator. Therefore, I'm confused as to how we end up with either 0 or 1 total solutions produced (depending on the ordering of the memo). Are solutions being generated and discarded? I'm not aware of any case where we would do this other than discarding index intersection plans, but in both memos it looks like we would generate plans without ixisect first and then move onto ixisect plans later. | ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
| Comment by James Wahlin [ 28/Aug/19 ] | ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
|
This is caused by a combination of the following:
For our reproduction case, the initial call to QueryPlanner::plan() generates either zero or one solution. The following is an example PlanEnumerator memo generated for each: Zero solution memo
One solution memo
The solution that is produced in one case and not in the other is represented by the following Node/Choice combinations in the above memos:
In the case where we produce zero solutions, the PlanEnumerator reaches a point where the OrAssignment counter is equal to _orLimit (aka internalQueryEnumerationMaxOrSolutions) prior to reaching the valid solution. In the case where we produce one solution, the valid solution is generated at an earlier point, prior to reaching this limit. Given the above, we will need a way to ensure that we enumerate over all plans in the same order, regardless of the iteration order provided by the PlanEnumerator's unordered_set structures. Additionally we should evaluate whether the limits we have in place are reasonable for a case like this. It is unfortunate in this case that our limits lead us to produce no solutions when one exists. | ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
| Comment by James Wahlin [ 27/Aug/19 ] | ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
|
The cause for this change in behavior is It is likely that the absl::node_hash_map ordering is less stable then our previous unordered_map implementation for this use case, exposing us to different table ordering on subsequent runs. Next step is to understand where in our PlanEnumerator code it is that IndexToPredMap order can impact the results of PlanEnumeration. | ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
| Comment by James Wahlin [ 27/Aug/19 ] | ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
|
Currently in the PlanEnumerator we use an unordered_map to store AND node index intersection assignments. We did work under Next step on this ticket is to understand how this was broken for the provided reproducer. It is worth noting that we would like stable plan selection regardless of both unordered_map usage and of index creation order. This means that just changing IndexToPredMap from unordered_map to map is not likely to be sufficient and could also hurt performance. | ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
| Comment by James Wahlin [ 03/Jul/19 ] | ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
|
I spent more time looking at this today. I found that the inputs to QueryPlanner::plan() are identical for both plan set variants. Where things start to differ is in plan enumeration. Dumping the memo for each to a log string shows that while the content appears to be the same, the ordering within the "choices" list is different. The MatchExpression list structure then changes after a call to resolveOrPushdowns() within prepareForAccessPlanning(). We then perform access planning, and find a single covered solution (which is accepted) in one case and no covered solutions in the other. My guess at this point is that the "choice" ordering within the memo affects the point in which we perform an OR pushdown and that mutation of the tree for OR pushdown impacts subsequent access planning. This is just a theory - I don't have evidence yet to back this. Here is an update to the patch above which includes logging for the memo and MatchExpression tree post OR pushdown. To compare between the 2 sets of plans, I did the following:
|