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

Inefficient plan for $or query

XMLWordPrintableJSON

    • Type: Icon: Bug Bug
    • Resolution: Duplicate
    • Priority: Icon: Major - P3 Major - P3
    • None
    • Affects Version/s: None
    • Component/s: Querying
    • Labels:
      None
    • ALL
    • 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' )

      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
}

            Assignee:
            kelsey.schubert@mongodb.com Kelsey Schubert
            Reporter:
            Sintendo Bram Speeckaert [X]
            Votes:
            0 Vote for this issue
            Watchers:
            4 Start watching this issue

              Created:
              Updated:
              Resolved: