[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:
Duplicate
duplicates SERVER-21697 Plan ranking should take query and in... Closed
Related
related to SERVER-13211 Optimal index not chosen for query pl... Closed
is related to DOCS-12781 [Server] Document that explain neithe... Backlog
Sprint: Query 2019-06-17
Participants:
Case:

 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:

db.plan_test.drop()
db.plan_test.createIndexes([{X: 1, Z: 1}, {X: 1, Y: 1}])
for (i = 0; i < 500; i++) { db.plan_test.insert({X: "x", Y: 1, Z: 1}) }
for (i = 0; i < 500; i++) { db.plan_test.insert({X: "x", Y: 2, Z: 2}) }
db.setProfilingLevel(2)
db.adminCommand({setParameter: 1, logLevel: 2})
db.plan_test.find({X: "x", Y: 1})
db.plan_test.find({X: "x", Y: 2})

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):

2019-04-25T20:14:25.023-0700 D COMMAND  [conn2] run command test.$cmd { find: "plan_test", filter: { X: "x", Y: 1.0 }, lsid: { id: UUID("14329441-8b72-4488-906b-534a6b101234") }, $db: "test" }
2019-04-25T20:14:25.023-0700 D QUERY    [conn2] Relevant index 0 is kp: { X: 1.0, Z: 1.0 } name: 'X_1_Z_1' io: { v: 2, key: { X: 1.0, Z: 1.0 }, name: "X_1_Z_1", ns: "test.plan_test" }
2019-04-25T20:14:25.023-0700 D QUERY    [conn2] Relevant index 1 is kp: { X: 1.0, Y: 1.0 } name: 'X_1_Y_1' io: { v: 2, key: { X: 1.0, Y: 1.0 }, name: "X_1_Y_1", ns: "test.plan_test" }
2019-04-25T20:14:25.026-0700 D QUERY    [conn2] Scoring query plan: IXSCAN { X: 1, Z: 1 } planHitEOF=0
2019-04-25T20:14:25.026-0700 D QUERY    [conn2] score(2.0003) = baseScore(1) + productivity((101 advanced)/(101 works) = 1) + tieBreakers(0.0001 noFetchBonus + 0.0001 noSortBonus + 0.0001 noIxisectBonus = 0.0003)
2019-04-25T20:14:25.026-0700 D QUERY    [conn2] Scoring query plan: IXSCAN { X: 1, Y: 1 } planHitEOF=0
2019-04-25T20:14:25.026-0700 D QUERY    [conn2] score(2.0003) = baseScore(1) + productivity((101 advanced)/(101 works) = 1) + tieBreakers(0.0001 noFetchBonus + 0.0001 noSortBonus + 0.0001 noIxisectBonus = 0.0003)
2019-04-25T20:14:25.026-0700 D QUERY    [conn2] Winning plan: IXSCAN { X: 1, Z: 1 }
2019-04-25T20:14:25.027-0700 I COMMAND  [conn2] command test.plan_test appName: "MongoDB Shell" command: find { find: "plan_test", filter: { X: "x", Y: 1.0 }, lsid: { id: UUID("14329441-8b72-4488-906b-534a6b101234") }, $db: "test" } planSummary: IXSCAN { X: 1, Z: 1 } cursorid:68197214193 keysExamined:101 docsExamined:101 fromMultiPlanner:1 numYields:2 nreturned:101 reslen:5851 locks:{ Global: { acquireCount: { r: 3 } }, Database: { acquireCount: { r: 3 } }, Collection: { acquireCount: { r: 3 } } } protocol:op_msg 3ms
...
2019-04-25T20:14:29.570-0700 D COMMAND  [conn2] run command test.$cmd { find: "plan_test", filter: { X: "x", Y: 2.0 }, lsid: { id: UUID("14329441-8b72-4488-906b-534a6b101234") }, $db: "test" }
2019-04-25T20:14:29.572-0700 D QUERY    [conn2] score(1.16835) = baseScore(1) + productivity((101 advanced)/(601 works) = 0.168053) + tieBreakers(0.0001 noFetchBonus + 0.0001 noSortBonus + 0.0001 noIxisectBonus = 0.0003)
2019-04-25T20:14:29.572-0700 I COMMAND  [conn2] command test.plan_test appName: "MongoDB Shell" command: find { find: "plan_test", filter: { X: "x", Y: 2.0 }, lsid: { id: UUID("14329441-8b72-4488-906b-534a6b101234") }, $db: "test" } planSummary: IXSCAN { X: 1, Z: 1 } cursorid:65081750386 keysExamined:601 docsExamined:601 numYields:5 nreturned:101 reslen:5851 locks:{ Global: { acquireCount: { r: 6 } }, Database: { acquireCount: { r: 6 } }, Collection: { acquireCount: { r: 6 } } } protocol:op_msg 1ms

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:

> db.plan_test.explain().find({X: "x", Y: 2})
{
	"queryPlanner" : {
		"plannerVersion" : 1,
		"namespace" : "test.plan_test",
		"indexFilterSet" : false,
		"parsedQuery" : {
			"$and" : [
				{
					"X" : {
						"$eq" : "x"
					}
				},
				{
					"Y" : {
						"$eq" : 2
					}
				}
			]
		},
		"winningPlan" : {
			"stage" : "FETCH",
			"inputStage" : {
				"stage" : "IXSCAN",
				"keyPattern" : {
					"X" : 1,
					"Y" : 1
				},
				"indexName" : "X_1_Y_1",
				"isMultiKey" : false,
				"multiKeyPaths" : {
					"X" : [ ],
					"Y" : [ ]
				},
				"isUnique" : false,
				"isSparse" : false,
				"isPartial" : false,
				"indexVersion" : 2,
				"direction" : "forward",
				"indexBounds" : {
					"X" : [
						"[\"x\", \"x\"]"
					],
					"Y" : [
						"[2.0, 2.0]"
					]
				}
			}
		},
		"rejectedPlans" : [
			{
				"stage" : "FETCH",
				"filter" : {
					"Y" : {
						"$eq" : 2
					}
				},
				"inputStage" : {
					"stage" : "IXSCAN",
					"keyPattern" : {
						"X" : 1,
						"Z" : 1
					},
					"indexName" : "X_1_Z_1",
					"isMultiKey" : false,
					"multiKeyPaths" : {
						"X" : [ ],
						"Z" : [ ]
					},
					"isUnique" : false,
					"isSparse" : false,
					"isPartial" : false,
					"indexVersion" : 2,
					"direction" : "forward",
					"indexBounds" : {
						"X" : [
							"[\"x\", \"x\"]"
						],
						"Z" : [
							"[MinKey, MaxKey]"
						]
					}
				}
			}
		]
	},
	"serverInfo" : {
		"host" : "st-bartle1.local",
		"port" : 27017,
		"version" : "4.0.3",
		"gitVersion" : "7ea530946fa7880364d88c8d8b6026bbc9ffa48c"
	},
	"ok" : 1
}



 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 SERVER-21697. Both suggest that, when two plans tie, we could prefer one plan or another depending on whether the set of indexed fields has a larger intersection set with the paths stated in the query. We could add a heuristic like you describe for the simplistic case of a query that just uses one index, and which has only equality predicates. Fixing this more generally involves a few complicating factors:

  • the set of fields in the sort, and their ordering
  • the set of required fields in the projection
  • whether each field in the compound index is ascending or descending
  • the ordering of the fields in the compound index
  • whether the index is sparse
  • whether the index is multikey
  • whether the predicates imply ranges or points
  • special index types, like text and geo

I am closing this ticket as a duplicate of SERVER-21697. Perhaps you could elaborate on this ticket about whether there is a specific pain or problem you are experiencing as a result of this behavior? In some cases, plan cache eviction and replanning may result in the system choosing the superior index in subsequent executions of the query shape.

I wanted to address a few of the other points you brought up in this ticket as well.

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.

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:

  • I would say that this problem is a manifestation of SERVER-20616. That this ticket, in addition to SERVER-21697, suggest a heuristic to work around SERVER-20616 in some cases.
  • You mentioned above that explain always performs plan selection rather than reading from the plan cache. This is expected behavior. SERVER-16895 tracks a request to allow explain to use the plan cache on an opt-in basis.

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 SERVER-21697.

Best,
Dave

Comment by Asya Kamsky [ 02/May/19 ]

Related to SERVER-21697 and SERVER-13211 - possibly duplicate of one of them?

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:

> db.plan_test.getPlanCache().getPlansByQuery({X: "x", Y: 2})
{
	"plans" : [
		{
			"details" : {
				"solution" : "(index-tagged expression tree: tree=Node\n---Leaf X_1_Z_1, pos: 0, can combine? 1\n---Leaf \n)"
			},
			"reason" : {
				"score" : 2.0003,
				"stats" : {
					"stage" : "FETCH",
					"filter" : {
						"Y" : {
							"$eq" : 1
						}
					},
					"nReturned" : 101,
					"executionTimeMillisEstimate" : 10,
					"works" : 101,
					"advanced" : 101,
					"needTime" : 0,
					"needYield" : 0,
					"saveState" : 1,
					"restoreState" : 1,
					"isEOF" : 0,
					"invalidates" : 0,
					"docsExamined" : 101,
					"alreadyHasObj" : 0,
					"inputStage" : {
						"stage" : "IXSCAN",
						"nReturned" : 101,
						"executionTimeMillisEstimate" : 10,
						"works" : 101,
						"advanced" : 101,
						"needTime" : 0,
						"needYield" : 0,
						"saveState" : 1,
						"restoreState" : 1,
						"isEOF" : 0,
						"invalidates" : 0,
						"keyPattern" : {
							"X" : 1,
							"Z" : 1
						},
						"indexName" : "X_1_Z_1",
						"isMultiKey" : false,
						"multiKeyPaths" : {
							"X" : [ ],
							"Z" : [ ]
						},
						"isUnique" : false,
						"isSparse" : false,
						"isPartial" : false,
						"indexVersion" : 2,
						"direction" : "forward",
						"indexBounds" : {
							"X" : [
								"[\"x\", \"x\"]"
							],
							"Z" : [
								"[MinKey, MaxKey]"
							]
						},
						"keysExamined" : 101,
						"seeks" : 1,
						"dupsTested" : 0,
						"dupsDropped" : 0,
						"seenInvalidated" : 0
					}
				}
			},
			"feedback" : {
				"nfeedback" : 1,
				"scores" : [
					{
						"score" : 1.1683532445923461
					}
				]
			},
			"filterSet" : false
		},
		{
			"details" : {
				"solution" : "(index-tagged expression tree: tree=Node\n---Leaf X_1_Y_1, pos: 0, can combine? 1\n---Leaf X_1_Y_1, pos: 1, can combine? 1\n)"
			},
			"reason" : {
				"score" : 2.0003,
				"stats" : {
					"stage" : "FETCH",
					"nReturned" : 101,
					"executionTimeMillisEstimate" : 0,
					"works" : 101,
					"advanced" : 101,
					"needTime" : 0,
					"needYield" : 0,
					"saveState" : 1,
					"restoreState" : 1,
					"isEOF" : 0,
					"invalidates" : 0,
					"docsExamined" : 101,
					"alreadyHasObj" : 0,
					"inputStage" : {
						"stage" : "IXSCAN",
						"nReturned" : 101,
						"executionTimeMillisEstimate" : 0,
						"works" : 101,
						"advanced" : 101,
						"needTime" : 0,
						"needYield" : 0,
						"saveState" : 1,
						"restoreState" : 1,
						"isEOF" : 0,
						"invalidates" : 0,
						"keyPattern" : {
							"X" : 1,
							"Y" : 1
						},
						"indexName" : "X_1_Y_1",
						"isMultiKey" : false,
						"multiKeyPaths" : {
							"X" : [ ],
							"Y" : [ ]
						},
						"isUnique" : false,
						"isSparse" : false,
						"isPartial" : false,
						"indexVersion" : 2,
						"direction" : "forward",
						"indexBounds" : {
							"X" : [
								"[\"x\", \"x\"]"
							],
							"Y" : [
								"[1.0, 1.0]"
							]
						},
						"keysExamined" : 101,
						"seeks" : 1,
						"dupsTested" : 0,
						"dupsDropped" : 0,
						"seenInvalidated" : 0
					}
				}
			},
			"feedback" : {
 
			},
			"filterSet" : false
		}
	],
	"timeOfCreation" : ISODate("2019-04-26T03:14:25.026Z"),
	"ok" : 1
}

Comment by David Bartley [ 26/Apr/19 ]

Ah, so it looks like explain is actually rescoring the plans:

2019-04-25T20:26:13.635-0700 D COMMAND  [conn2] run command test.$cmd { explain: { find: "plan_test", filter: { X: "x", Y: 2.0 } }, verbosity: "queryPlanner", lsid: { id: UUID("14329441-8b72-4488-906b-534a6b101234") }, $db: "test" }
2019-04-25T20:26:13.636-0700 D QUERY    [conn2] Relevant index 0 is kp: { X: 1.0, Z: 1.0 } name: 'X_1_Z_1' io: { v: 2, key: { X: 1.0, Z: 1.0 }, name: "X_1_Z_1", ns: "test.plan_test" }
2019-04-25T20:26:13.636-0700 D QUERY    [conn2] Relevant index 1 is kp: { X: 1.0, Y: 1.0 } name: 'X_1_Y_1' io: { v: 2, key: { X: 1.0, Y: 1.0 }, name: "X_1_Y_1", ns: "test.plan_test" }
2019-04-25T20:26:13.637-0700 D QUERY    [conn2] Scoring query plan: IXSCAN { X: 1, Z: 1 } planHitEOF=0
2019-04-25T20:26:13.637-0700 D QUERY    [conn2] score(1.0003) = baseScore(1) + productivity((0 advanced)/(101 works) = 0) + tieBreakers(0.0001 noFetchBonus + 0.0001 noSortBonus + 0.0001 noIxisectBonus = 0.0003)
2019-04-25T20:26:13.637-0700 D QUERY    [conn2] Scoring query plan: IXSCAN { X: 1, Y: 1 } planHitEOF=0
2019-04-25T20:26:13.637-0700 D QUERY    [conn2] score(2.0003) = baseScore(1) + productivity((101 advanced)/(101 works) = 1) + tieBreakers(0.0001 noFetchBonus + 0.0001 noSortBonus + 0.0001 noIxisectBonus = 0.0003)
2019-04-25T20:26:13.637-0700 D QUERY    [conn2] Winning plan: IXSCAN { X: 1, Y: 1 }

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.

Generated at Thu Feb 08 04:56:07 UTC 2024 using Jira 9.7.1#970001-sha1:2222b88b221c4928ef0de3161136cc90c8356a66.