[SERVER-31929] Inefficient plan for $or query Created: 12/Nov/17  Updated: 07/Dec/17  Resolved: 13/Nov/17

Status: Closed
Project: Core Server
Component/s: Querying
Affects Version/s: None
Fix Version/s: None

Type: Bug Priority: Major - P3
Reporter: Bram Speeckaert [X] Assignee: Kelsey Schubert
Resolution: Duplicate Votes: 0
Labels: None
Remaining Estimate: Not Specified
Time Spent: Not Specified
Original Estimate: Not Specified

Issue Links:
Duplicate
duplicates SERVER-13732 Predicates in top-level implicit AND ... Closed
Operating System: ALL
Steps To Reproduce:

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

Participants:

 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
}



 Comments   
Comment by Kelsey Schubert [ 13/Nov/17 ]

Hi Sintendo,

Thank you for the detailed report and clear steps to reproduce. This issue has been resolved under SERVER-13732, and will be included in MongoDB 3.6. If you would let to test this fix or other new features in MongoDB 3.6, please feel free to download the most recent release candidate.

Kind regards,
Kelsey

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