[SERVER-29550] Leverage multiKeyPath information to prevent filtering in FETCH with negation operator Created: 11/Jun/17  Updated: 06/Dec/22

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

Type: Improvement Priority: Major - P3
Reporter: Chris Harris Assignee: Backlog - Query Optimization
Resolution: Unresolved Votes: 0
Labels: neweng
Remaining Estimate: Not Specified
Time Spent: Not Specified
Original Estimate: Not Specified

Issue Links:
Related
related to SERVER-3173 Planner should use path-level multike... Closed
Assigned Teams:
Query Optimization
Participants:

 Description   

Traditionally when an operation such as $ne is applied to a field in a multikey index, appropriate index bounds may be applied but a filter in the FETCH stage is required to confirm if the entire document satisfies the condition. It seems that it should be possible to avoid this check starting in 3.4 if the field with the operator is not an array (based on the multiKeyPath knowledge).

Projection added below to emphasize the potential improvements, but the filter check happens regardless.

diff:PRIMARY> db.version()
3.4.3
diff:PRIMARY> 
diff:PRIMARY> db.collection.drop()
true
diff:PRIMARY> 
diff:PRIMARY> db.collection.createIndex({x:1,y:1})
{
	"createdCollectionAutomatically" : true,
	"numIndexesBefore" : 1,
	"numIndexesAfter" : 2,
	"ok" : 1
}
diff:PRIMARY> 
diff:PRIMARY> 
diff:PRIMARY> 
diff:PRIMARY> db.collection.explain().find({x:{$ne:1}},{_id:0, x:1})
{
	"queryPlanner" : {
		"plannerVersion" : 1,
		"namespace" : "test.collection",
		"indexFilterSet" : false,
		"parsedQuery" : {
			"$nor" : [
				{
					"x" : {
						"$eq" : 1
					}
				}
			]
		},
		"winningPlan" : {
			"stage" : "PROJECTION",
			"transformBy" : {
				"_id" : 0,
				"x" : 1
			},
			"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" : [
						"[MinKey, 1.0)",
						"(1.0, MaxKey]"
					],
					"y" : [
						"[MinKey, MaxKey]"
					]
				}
			}
		},
		"rejectedPlans" : [ ]
	},
	"serverInfo" : {
		"host" : "Chriss-MacBook-Pro.local",
		"port" : 30001,
		"version" : "3.4.3",
		"gitVersion" : "f07437fb5a6cca07c10bafa78365456eb1d6d5e1"
	},
	"ok" : 1
}
diff:PRIMARY> 
diff:PRIMARY> 
diff:PRIMARY> db.collection.insert({x:1, y:[1,100]})
WriteResult({ "nInserted" : 1 })
diff:PRIMARY> 
diff:PRIMARY> 
diff:PRIMARY> db.collection.explain().find({x:{$ne:1}},{_id:0, x:1})
{
	"queryPlanner" : {
		"plannerVersion" : 1,
		"namespace" : "test.collection",
		"indexFilterSet" : false,
		"parsedQuery" : {
			"$nor" : [
				{
					"x" : {
						"$eq" : 1
					}
				}
			]
		},
		"winningPlan" : {
			"stage" : "PROJECTION",
			"transformBy" : {
				"_id" : 0,
				"x" : 1
			},
			"inputStage" : {
				"stage" : "FETCH",
				"filter" : {
					"$nor" : [
						{
							"x" : {
								"$eq" : 1
							}
						}
					]
				},
				"inputStage" : {
					"stage" : "IXSCAN",
					"keyPattern" : {
						"x" : 1,
						"y" : 1
					},
					"indexName" : "x_1_y_1",
					"isMultiKey" : true,
					"multiKeyPaths" : {
						"x" : [ ],
						"y" : [
							"y"
						]
					},
					"isUnique" : false,
					"isSparse" : false,
					"isPartial" : false,
					"indexVersion" : 2,
					"direction" : "forward",
					"indexBounds" : {
						"x" : [
							"[MinKey, 1.0)",
							"(1.0, MaxKey]"
						],
						"y" : [
							"[MinKey, MaxKey]"
						]
					}
				}
			}
		},
		"rejectedPlans" : [ ]
	},
	"serverInfo" : {
		"host" : "Chriss-MacBook-Pro.local",
		"port" : 30001,
		"version" : "3.4.3",
		"gitVersion" : "f07437fb5a6cca07c10bafa78365456eb1d6d5e1"
	},
	"ok" : 1
}



 Comments   
Comment by Asya Kamsky [ 12/Jun/17 ]

As result of SERVER-3173 FETCH is no longer present for equality or range query, however, it still seems to FETCH when $ne is used:

db.collection.explain().find({x:{$ne:1}},{_id:0, x:1})
{
	"queryPlanner" : {
		"plannerVersion" : 1,
		"namespace" : "test.collection",
		"indexFilterSet" : false,
		"parsedQuery" : {
			"$nor" : [
				{
					"x" : {
						"$eq" : 1
					}
				}
			]
		},
		"winningPlan" : {
			"stage" : "PROJECTION",
			"transformBy" : {
				"_id" : 0,
				"x" : 1
			},
			"inputStage" : {
				"stage" : "FETCH",
				"filter" : {
					"$nor" : [
						{
							"x" : {
								"$eq" : 1
							}
						}
					]
				},
				"inputStage" : {
					"stage" : "IXSCAN",
					"keyPattern" : {
						"x" : 1,
						"y" : 1
					},
					"indexName" : "x_1_y_1",
					"isMultiKey" : true,
					"multiKeyPaths" : {
						"x" : [ ],
						"y" : [
							"y"
						]
					},
					"isUnique" : false,
					"isSparse" : false,
					"isPartial" : false,
					"indexVersion" : 2,
					"direction" : "forward",
					"indexBounds" : {
						"x" : [
							"[MinKey, 1.0)",
							"(1.0, MaxKey]"
						],
						"y" : [
							"[MinKey, MaxKey]"
						]
					}
				}
			}
		},
		"rejectedPlans" : [ ]
	},
	"serverInfo" : {
		"host" : "erh-twinb",
		"port" : 35600,
		"version" : "3.5.7-105-g3fc53d7",
		"gitVersion" : "3fc53d74622c9d4dcf8281e605a03ef437cb2d01"
	},
	"ok" : 1
}
>

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