[SERVER-40844] Better tie breaking of "perfect" indexes Created: 26/Apr/19 Updated: 05/Jul/21 Resolved: 05/Jun/19 |
|
| Status: | Closed |
| Project: | Core Server |
| Component/s: | Querying |
| Affects Version/s: | 3.4.20, 4.0.9 |
| Fix Version/s: | None |
| Type: | Improvement | Priority: | Major - P3 |
| Reporter: | David Bartley | Assignee: | David Storch |
| Resolution: | Duplicate | Votes: | 0 |
| Labels: | None | ||
| Remaining Estimate: | Not Specified | ||
| Time Spent: | Not Specified | ||
| Original Estimate: | Not Specified | ||
| Issue Links: |
|
||||||||||||||||||||
| Sprint: | Query 2019-06-17 | ||||||||||||||||||||
| Participants: | |||||||||||||||||||||
| Case: | (copied to CRM) | ||||||||||||||||||||
| Description |
|
Given indexes {X: 1, Y: 1} and {X: 1, Z: 1}, it seems like it should be the case that a query {X: "x", Y: 1} would always select the former index, given that it's a "perfect" match. However, in practice this isn't always the case; the query planner will score them equally if a given query runs equally "fast" on both. This can happen if the documents that query would return are located at the start of the index bounds. Here's a specific repro:
Note that the order of index creation may matter; in practice, ties are broken by selecting whichever index is "first", and my testing has indicated that it's not consistently the first-created index, though I'm unsure exactly how the candidate plans are actually ordered. The above will result in the following logs (from 4.0):
In this case, for the first query, both indexes can service the query without needing to advance, so "works" is the same. The relevant cases where bonuses are awarded are also the same, so they truly are tied. However, it should be the case the the perfectly matching index should be awarded a bonus. To make matters even more confusing, explain actually indicates that the better index will be used for the 2nd query:
|
| Comments |
| Comment by David Storch [ 06/Jun/19 ] | |||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
|
bartle I filed DOCS-12781 to track the documentation improvement you suggested! | |||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
| Comment by David Bartley [ 05/Jun/19 ] | |||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
|
I also wasn't able to consistently reproduce, since, as you mention, ties are broken arbitrarily. I ended up having to repeatedly wipe the db, restart mongod, and recreate the indexes until it reproduced. I still think it's worth noting in the documentation how the plan cache interacts with "explain" (i.e. cached plans are ignored). The current documentation says "MongoDB runs the query optimizer to choose the winning plan"; I'd suggest something like "MongoDB runs the query optimizer, ignoring any cached query plans, to choose the winning plan". | |||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
| Comment by David Storch [ 05/Jun/19 ] | |||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
|
Hi bartle, As Asya mentioned above, I think the central issue reported here is a duplicate of
I am closing this ticket as a duplicate of I wanted to address a few of the other points you brought up in this ticket as well.
When two plans tie, the one that is ultimately chosen is arbitrary. From the system's perspective they are identical and the actual choice is implementation dependent. There is no guarantee of stability of this choice across multiple executions of the plan selection code. There is no hidden tie breaker beyond the score itself that makes this choice deterministic, and there are no tests which expect a particular plan to end up executing in the case of a tie. A tie is a tie, and the ultimate fix is to improve the scoring function to avoid ties altogether. Looking at it with this lens, the fact that we may end up with a different plan with and without explain is not a bug, though it is surprising behavior. However, I could not reproduce this using the code snippet from the description of this ticket. In both the logs and in explain for both example queries, I see that the IXSCAN { X: 1, Y: 1 } plan is selected. As one final note, I wanted to draw your attention to a few related tickets that may be of interest:
Hopefully this all makes sense and feel free to follow-up with questions or comments! As I said, a better understanding of the impact of this behavior could help us in prioritizing the work for Best, | |||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
| Comment by Asya Kamsky [ 02/May/19 ] | |||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
|
Related to Also maybe somewhat related to SERVER-20616. | |||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
| Comment by Danny Hatcher (Inactive) [ 29/Apr/19 ] | |||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
|
Hi David, I've forwarded this onto the query team to take a look. Danny | |||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
| Comment by David Bartley [ 26/Apr/19 ] | |||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
|
Even using db.plan_test.getPlanCache().getPlansByQuery({X: "x", Y: 2}) doesn't make it clear what's going on; it just shows the plans as scoring equally, though at least the winning plan is listed first:
| |||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
| Comment by David Bartley [ 26/Apr/19 ] | |||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
|
Ah, so it looks like explain is actually rescoring the plans:
It's not obvious from https://docs.mongodb.com/manual/reference/command/explain/ that this behaviour occurs, and I would have expected that the plan cache would have been used instead. | |||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
| Comment by David Bartley [ 26/Apr/19 ] | |||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
|
I actually think the confusing explain behaviour is worth a separate bug, since it'd still presumably have the same behaviour for other ties not related to this bug. |