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

Inefficient plan for $or query

    XMLWordPrintable

    Details

    • Type: Bug
    • Status: Closed
    • Priority: Major - P3
    • Resolution: Duplicate
    • Affects Version/s: None
    • Fix Version/s: None
    • Component/s: Querying
    • Labels:
      None
    • Operating System:
      ALL
    • Steps To Reproduce:
      Hide

      Initializing the database:

      for (let i= 1; i <= 2; i++) {
         for (let x = 1; x <= 100; x++ ) {
            for (let y = 1; y <= 100; y++) {
               db.records.insert({i, x, y});
            }
         }
      }
       
      db.records.ensureIndex({i: 1, x: 1, y: 1});
      

      Queries:

      db.records.find({i:1, $or: [{x: 50, y: {$gt: 50}}, {x: {$gt: 50}}]}).sort({x: 1, y: 1}).explain('executionStats')
      db.records.find({$or: [{i: 1, x: 50, y: {$gt: 50}}, {i: 1, x: {$gt: 50}}]}).sort({x: 1, y: 1}).explain('executionStats')
      

      Show
      Initializing the database: for (let i= 1; i <= 2; i++) { for (let x = 1; x <= 100; x++ ) { for (let y = 1; y <= 100; y++) { db.records.insert({i, x, y}); } } }   db.records.ensureIndex({i: 1, x: 1, y: 1}); Queries: db.records.find({i:1, $or: [{x: 50, y: {$gt: 50}}, {x: {$gt: 50}}]}).sort({x: 1, y: 1}).explain( 'executionStats' ) db.records.find({$or: [{i: 1, x: 50, y: {$gt: 50}}, {i: 1, x: {$gt: 50}}]}).sort({x: 1, y: 1}).explain( 'executionStats' )

      Description

      The first query will result in an inefficient index scan for i=1, doing the rest of the filtering in the FETCH stage:

      {
      	"queryPlanner" : {
      		"plannerVersion" : 1,
      		"namespace" : "test.records",
      		"indexFilterSet" : false,
      		"parsedQuery" : {
      			"$and" : [
      				{
      					"$or" : [
      						{
      							"$and" : [
      								{
      									"x" : {
      										"$eq" : 50
      									}
      								},
      								{
      									"y" : {
      										"$gt" : 50
      									}
      								}
      							]
      						},
      						{
      							"x" : {
      								"$gt" : 50
      							}
      						}
      					]
      				},
      				{
      					"i" : {
      						"$eq" : 1
      					}
      				}
      			]
      		},
      		"winningPlan" : {
      			"stage" : "FETCH",
      			"filter" : {
      				"$or" : [
      					{
      						"$and" : [
      							{
      								"x" : {
      									"$eq" : 50
      								}
      							},
      							{
      								"y" : {
      									"$gt" : 50
      								}
      							}
      						]
      					},
      					{
      						"x" : {
      							"$gt" : 50
      						}
      					}
      				]
      			},
      			"inputStage" : {
      				"stage" : "IXSCAN",
      				"keyPattern" : {
      					"i" : 1,
      					"x" : 1,
      					"y" : 1
      				},
      				"indexName" : "i_1_x_1_y_1",
      				"isMultiKey" : false,
      				"multiKeyPaths" : {
      					"i" : [ ],
      					"x" : [ ],
      					"y" : [ ]
      				},
      				"isUnique" : false,
      				"isSparse" : false,
      				"isPartial" : false,
      				"indexVersion" : 2,
      				"direction" : "forward",
      				"indexBounds" : {
      					"i" : [
      						"[1.0, 1.0]"
      					],
      					"x" : [
      						"[MinKey, MaxKey]"
      					],
      					"y" : [
      						"[MinKey, MaxKey]"
      					]
      				}
      			}
      		},
      		"rejectedPlans" : [ ]
      	},
      	"executionStats" : {
      		"executionSuccess" : true,
      		"nReturned" : 5050,
      		"executionTimeMillis" : 18,
      		"totalKeysExamined" : 10000,
      		"totalDocsExamined" : 10000,
      		"executionStages" : {
      			"stage" : "FETCH",
      			"filter" : {
      				"$or" : [
      					{
      						"$and" : [
      							{
      								"x" : {
      									"$eq" : 50
      								}
      							},
      							{
      								"y" : {
      									"$gt" : 50
      								}
      							}
      						]
      					},
      					{
      						"x" : {
      							"$gt" : 50
      						}
      					}
      				]
      			},
      			"nReturned" : 5050,
      			"executionTimeMillisEstimate" : 22,
      			"works" : 10001,
      			"advanced" : 5050,
      			"needTime" : 4950,
      			"needYield" : 0,
      			"saveState" : 78,
      			"restoreState" : 78,
      			"isEOF" : 1,
      			"invalidates" : 0,
      			"docsExamined" : 10000,
      			"alreadyHasObj" : 0,
      			"inputStage" : {
      				"stage" : "IXSCAN",
      				"nReturned" : 10000,
      				"executionTimeMillisEstimate" : 0,
      				"works" : 10001,
      				"advanced" : 10000,
      				"needTime" : 0,
      				"needYield" : 0,
      				"saveState" : 78,
      				"restoreState" : 78,
      				"isEOF" : 1,
      				"invalidates" : 0,
      				"keyPattern" : {
      					"i" : 1,
      					"x" : 1,
      					"y" : 1
      				},
      				"indexName" : "i_1_x_1_y_1",
      				"isMultiKey" : false,
      				"multiKeyPaths" : {
      					"i" : [ ],
      					"x" : [ ],
      					"y" : [ ]
      				},
      				"isUnique" : false,
      				"isSparse" : false,
      				"isPartial" : false,
      				"indexVersion" : 2,
      				"direction" : "forward",
      				"indexBounds" : {
      					"i" : [
      						"[1.0, 1.0]"
      					],
      					"x" : [
      						"[MinKey, MaxKey]"
      					],
      					"y" : [
      						"[MinKey, MaxKey]"
      					]
      				},
      				"keysExamined" : 10000,
      				"seeks" : 1,
      				"dupsTested" : 0,
      				"dupsDropped" : 0,
      				"seenInvalidated" : 0
      			}
      		}
      	},
      	"serverInfo" : {
      		"host" : "local",
      		"port" : 27017,
      		"version" : "3.4.10",
      		"gitVersion" : "078f28920cb24de0dd479b5ea6c66c644f6326e9"
      	},
      	"ok" : 1
      }
      

      The second equivalent query, in which the i=1 condition has been manually inserted into both clauses, is much better:

      {
      	"queryPlanner" : {
      		"plannerVersion" : 1,
      		"namespace" : "test.records",
      		"indexFilterSet" : false,
      		"parsedQuery" : {
      			"$or" : [
      				{
      					"$and" : [
      						{
      							"i" : {
      								"$eq" : 1
      							}
      						},
      						{
      							"x" : {
      								"$eq" : 50
      							}
      						},
      						{
      							"y" : {
      								"$gt" : 50
      							}
      						}
      					]
      				},
      				{
      					"$and" : [
      						{
      							"i" : {
      								"$eq" : 1
      							}
      						},
      						{
      							"x" : {
      								"$gt" : 50
      							}
      						}
      					]
      				}
      			]
      		},
      		"winningPlan" : {
      			"stage" : "SUBPLAN",
      			"inputStage" : {
      				"stage" : "FETCH",
      				"inputStage" : {
      					"stage" : "SORT_MERGE",
      					"sortPattern" : {
      						"x" : 1,
      						"y" : 1
      					},
      					"inputStages" : [
      						{
      							"stage" : "IXSCAN",
      							"keyPattern" : {
      								"i" : 1,
      								"x" : 1,
      								"y" : 1
      							},
      							"indexName" : "i_1_x_1_y_1",
      							"isMultiKey" : false,
      							"multiKeyPaths" : {
      								"i" : [ ],
      								"x" : [ ],
      								"y" : [ ]
      							},
      							"isUnique" : false,
      							"isSparse" : false,
      							"isPartial" : false,
      							"indexVersion" : 2,
      							"direction" : "forward",
      							"indexBounds" : {
      								"i" : [
      									"[1.0, 1.0]"
      								],
      								"x" : [
      									"[50.0, 50.0]"
      								],
      								"y" : [
      									"(50.0, inf.0]"
      								]
      							}
      						},
      						{
      							"stage" : "IXSCAN",
      							"keyPattern" : {
      								"i" : 1,
      								"x" : 1,
      								"y" : 1
      							},
      							"indexName" : "i_1_x_1_y_1",
      							"isMultiKey" : false,
      							"multiKeyPaths" : {
      								"i" : [ ],
      								"x" : [ ],
      								"y" : [ ]
      							},
      							"isUnique" : false,
      							"isSparse" : false,
      							"isPartial" : false,
      							"indexVersion" : 2,
      							"direction" : "forward",
      							"indexBounds" : {
      								"i" : [
      									"[1.0, 1.0]"
      								],
      								"x" : [
      									"(50.0, inf.0]"
      								],
      								"y" : [
      									"[MinKey, MaxKey]"
      								]
      							}
      						}
      					]
      				}
      			}
      		},
      		"rejectedPlans" : [ ]
      	},
      	"executionStats" : {
      		"executionSuccess" : true,
      		"nReturned" : 5050,
      		"executionTimeMillis" : 10,
      		"totalKeysExamined" : 5050,
      		"totalDocsExamined" : 5050,
      		"executionStages" : {
      			"stage" : "SUBPLAN",
      			"nReturned" : 5050,
      			"executionTimeMillisEstimate" : 0,
      			"works" : 10103,
      			"advanced" : 5050,
      			"needTime" : 5052,
      			"needYield" : 0,
      			"saveState" : 78,
      			"restoreState" : 78,
      			"isEOF" : 1,
      			"invalidates" : 0,
      			"inputStage" : {
      				"stage" : "FETCH",
      				"nReturned" : 5050,
      				"executionTimeMillisEstimate" : 0,
      				"works" : 10102,
      				"advanced" : 5050,
      				"needTime" : 5052,
      				"needYield" : 0,
      				"saveState" : 78,
      				"restoreState" : 78,
      				"isEOF" : 1,
      				"invalidates" : 0,
      				"docsExamined" : 5050,
      				"alreadyHasObj" : 0,
      				"inputStage" : {
      					"stage" : "SORT_MERGE",
      					"nReturned" : 5050,
      					"executionTimeMillisEstimate" : 0,
      					"works" : 10102,
      					"advanced" : 5050,
      					"needTime" : 5052,
      					"needYield" : 0,
      					"saveState" : 78,
      					"restoreState" : 78,
      					"isEOF" : 1,
      					"invalidates" : 0,
      					"sortPattern" : {
      						"x" : 1,
      						"y" : 1
      					},
      					"dupsTested" : 5050,
      					"dupsDropped" : 0,
      					"inputStages" : [
      						{
      							"stage" : "IXSCAN",
      							"nReturned" : 50,
      							"executionTimeMillisEstimate" : 0,
      							"works" : 51,
      							"advanced" : 50,
      							"needTime" : 0,
      							"needYield" : 0,
      							"saveState" : 78,
      							"restoreState" : 78,
      							"isEOF" : 1,
      							"invalidates" : 0,
      							"keyPattern" : {
      								"i" : 1,
      								"x" : 1,
      								"y" : 1
      							},
      							"indexName" : "i_1_x_1_y_1",
      							"isMultiKey" : false,
      							"multiKeyPaths" : {
      								"i" : [ ],
      								"x" : [ ],
      								"y" : [ ]
      							},
      							"isUnique" : false,
      							"isSparse" : false,
      							"isPartial" : false,
      							"indexVersion" : 2,
      							"direction" : "forward",
      							"indexBounds" : {
      								"i" : [
      									"[1.0, 1.0]"
      								],
      								"x" : [
      									"[50.0, 50.0]"
      								],
      								"y" : [
      									"(50.0, inf.0]"
      								]
      							},
      							"keysExamined" : 50,
      							"seeks" : 1,
      							"dupsTested" : 0,
      							"dupsDropped" : 0,
      							"seenInvalidated" : 0
      						},
      						{
      							"stage" : "IXSCAN",
      							"nReturned" : 5000,
      							"executionTimeMillisEstimate" : 0,
      							"works" : 5001,
      							"advanced" : 5000,
      							"needTime" : 0,
      							"needYield" : 0,
      							"saveState" : 78,
      							"restoreState" : 78,
      							"isEOF" : 1,
      							"invalidates" : 0,
      							"keyPattern" : {
      								"i" : 1,
      								"x" : 1,
      								"y" : 1
      							},
      							"indexName" : "i_1_x_1_y_1",
      							"isMultiKey" : false,
      							"multiKeyPaths" : {
      								"i" : [ ],
      								"x" : [ ],
      								"y" : [ ]
      							},
      							"isUnique" : false,
      							"isSparse" : false,
      							"isPartial" : false,
      							"indexVersion" : 2,
      							"direction" : "forward",
      							"indexBounds" : {
      								"i" : [
      									"[1.0, 1.0]"
      								],
      								"x" : [
      									"(50.0, inf.0]"
      								],
      								"y" : [
      									"[MinKey, MaxKey]"
      								]
      							},
      							"keysExamined" : 5000,
      							"seeks" : 1,
      							"dupsTested" : 0,
      							"dupsDropped" : 0,
      							"seenInvalidated" : 0
      						}
      					]
      				}
      			}
      		}
      	},
      	"serverInfo" : {
      		"host" : "local",
      		"port" : 27017,
      		"version" : "3.4.10",
      		"gitVersion" : "078f28920cb24de0dd479b5ea6c66c644f6326e9"
      	},
      	"ok" : 1
      }
      

        Attachments

          Issue Links

            Activity

              People

              Assignee:
              kelsey.schubert Kelsey T Schubert
              Reporter:
              Sintendo Bram Speeckaert [X] (Inactive)
              Participants:
              Votes:
              0 Vote for this issue
              Watchers:
              4 Start watching this issue

                Dates

                Created:
                Updated:
                Resolved: