Uploaded image for project: 'Core Server'
  1. Core Server
  2. SERVER-40844

Better tie breaking of "perfect" indexes

    XMLWordPrintable

    Details

    • Type: Improvement
    • Status: Closed
    • Priority: Major - P3
    • Resolution: Duplicate
    • Affects Version/s: 3.4.20, 4.0.9
    • Fix Version/s: None
    • Component/s: Querying
    • Labels:
      None
    • Sprint:
      Query 2019-06-17

      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
      }
      

        Attachments

          Issue Links

            Activity

              People

              Assignee:
              david.storch David Storch
              Reporter:
              bartle David Bartley
              Participants:
              Votes:
              0 Vote for this issue
              Watchers:
              6 Start watching this issue

                Dates

                Created:
                Updated:
                Resolved: