[SERVER-13273] multiple predicates for $all and multiKey index is order dependent Created: 19/Mar/14  Updated: 30/Jul/15  Resolved: 17/Jul/14

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

Type: Bug Priority: Major - P3
Reporter: Asya Kamsky Assignee: David Storch
Resolution: Done Votes: 0
Labels: None
Remaining Estimate: Not Specified
Time Spent: Not Specified
Original Estimate: Not Specified

Issue Links:
Related
related to SERVER-12281 When choosing multikey index bounds, ... Backlog
Operating System: ALL
Participants:

 Description   

In 2.6.0-rc1 I have an array "attr" which is indexed. Its contents are strings. In a query of type:

db.prod2.find({attr:{$all:["string1","string2","string3"]}})

The nscanned seems to be dependent on the order of values inside the $all list. Putting the more selective string first causes nscanned to be equal to number of documents with that string present.

Explain(true) shows only one index boundary is considered - the one that's listed first.

Note: this does not happen if the array elements are subdocuments and $elemMatch is used - then explain(true) shows that each of the elements in the $all list are tried and the one that's most selective is chosen regardless of the order they are given in.



 Comments   
Comment by David Storch [ 17/Jul/14 ]

You can't combine bounds from multiple predicates over a multikey index. 2.6 currently picks an arbitrary predicate to use to build the bounds (the first one). This behavior might change as described by SERVER-12281. However, this is expected 2.6 behavior for the time being, so I'm resolving as "Works as Designed".

Comment by Asya Kamsky [ 19/Mar/14 ]

dynamic@asyaRS:PRIMARY(2.6.0-rc1) > db.prod2.getIndexes()
[
	{
		"v" : 1,
		"key" : {
			"_id" : 1
		},
		"name" : "_id_",
		"ns" : "dynamic.prod2"
	},
	{
		"v" : 1,
		"key" : {
			"attr" : 1
		},
		"name" : "attr_1",
		"ns" : "dynamic.prod2"
	},
	{
		"v" : 1,
		"key" : {
			"type" : 1
		},
		"name" : "type_1",
		"ns" : "dynamic.prod2"
	}
]
dynamic@asyaRS:PRIMARY(2.6.0-rc1) > db.prod2.find({attr:{$all:["manufacturer::FooBar","style::xxx","color::blue","size::8B"]}}).explain(true)
{
	"cursor" : "BtreeCursor attr_1",
	"isMultiKey" : true,
	"n" : 1,
	"nscannedObjects" : 214,
	"nscanned" : 214,
	"nscannedObjectsAllPlans" : 214,
	"nscannedAllPlans" : 317,
	"scanAndOrder" : false,
	"indexOnly" : false,
	"nYields" : 1,
	"nChunkSkips" : 0,
	"millis" : 1,
	"indexBounds" : {
		"attr" : [
			[
				"manufacturer::FooBar",
				"manufacturer::FooBar"
			]
		]
	},
	"allPlans" : [
		{
			"cursor" : "BtreeCursor attr_1",
			"isMultiKey" : true,
			"n" : 1,
			"nscannedObjects" : 214,
			"nscanned" : 214,
			"scanAndOrder" : false,
			"indexOnly" : false,
			"nChunkSkips" : 0,
			"indexBounds" : {
				"attr" : [
					[
						"manufacturer::FooBar",
						"manufacturer::FooBar"
					]
				]
			}
		},
		{
			"cursor" : "Complex Plan",
			"n" : 0,
			"nscannedObjects" : 0,
			"nscanned" : 103,
			"nChunkSkips" : 0
		}
	],
	"server" : "asyasmacbook.local:27017",
	"filterSet" : false,
	"stats" : {
		"type" : "KEEP_MUTATIONS",
		"works" : 215,
		"yields" : 1,
		"unyields" : 1,
		"invalidates" : 0,
		"advanced" : 1,
		"needTime" : 213,
		"needFetch" : 0,
		"isEOF" : 1,
		"children" : [
			{
				"type" : "FETCH",
				"works" : 215,
				"yields" : 1,
				"unyields" : 1,
				"invalidates" : 0,
				"advanced" : 1,
				"needTime" : 213,
				"needFetch" : 0,
				"isEOF" : 1,
				"alreadyHasObj" : 0,
				"forcedFetches" : 0,
				"matchTested" : 1,
				"children" : [
					{
						"type" : "IXSCAN",
						"works" : 214,
						"yields" : 1,
						"unyields" : 1,
						"invalidates" : 0,
						"advanced" : 214,
						"needTime" : 0,
						"needFetch" : 0,
						"isEOF" : 1,
						"keyPattern" : "{ attr: 1.0 }",
						"boundsVerbose" : "field #0['attr']: [\"manufacturer::FooBar\", \"manufacturer::FooBar\"]",
						"isMultiKey" : 1,
						"yieldMovedCursor" : 0,
						"dupsTested" : 214,
						"dupsDropped" : 0,
						"seenInvalidated" : 0,
						"matchTested" : 0,
						"keysExamined" : 214,
						"children" : [ ]
					}
				]
			}
		]
	}
}
dynamic@asyaRS:PRIMARY(2.6.0-rc1) > db.prod2.find({$and:[{attr:"size::8B"},{attr:"manufacturer::FooBar"},{attr:"style::xxx"},{"attr":"color::blue"}]}).explain(true)
{
	"cursor" : "BtreeCursor attr_1",
	"isMultiKey" : true,
	"n" : 1,
	"nscannedObjects" : 104,
	"nscanned" : 104,
	"nscannedObjectsAllPlans" : 104,
	"nscannedAllPlans" : 208,
	"scanAndOrder" : false,
	"indexOnly" : false,
	"nYields" : 1,
	"nChunkSkips" : 0,
	"millis" : 0,
	"indexBounds" : {
		"attr" : [
			[
				"size::8B",
				"size::8B"
			]
		]
	},
	"allPlans" : [
		{
			"cursor" : "BtreeCursor attr_1",
			"isMultiKey" : true,
			"n" : 1,
			"nscannedObjects" : 104,
			"nscanned" : 104,
			"scanAndOrder" : false,
			"indexOnly" : false,
			"nChunkSkips" : 0,
			"indexBounds" : {
				"attr" : [
					[
						"size::8B",
						"size::8B"
					]
				]
			}
		},
		{
			"cursor" : "Complex Plan",
			"n" : 0,
			"nscannedObjects" : 0,
			"nscanned" : 104,
			"nChunkSkips" : 0
		}
	],
	"server" : "asyasmacbook.local:27017",
	"filterSet" : false,
	"stats" : {
		"type" : "KEEP_MUTATIONS",
		"works" : 105,
		"yields" : 1,
		"unyields" : 1,
		"invalidates" : 0,
		"advanced" : 1,
		"needTime" : 103,
		"needFetch" : 0,
		"isEOF" : 1,
		"children" : [
			{
				"type" : "FETCH",
				"works" : 105,
				"yields" : 1,
				"unyields" : 1,
				"invalidates" : 0,
				"advanced" : 1,
				"needTime" : 103,
				"needFetch" : 0,
				"isEOF" : 1,
				"alreadyHasObj" : 0,
				"forcedFetches" : 0,
				"matchTested" : 1,
				"children" : [
					{
						"type" : "IXSCAN",
						"works" : 104,
						"yields" : 1,
						"unyields" : 1,
						"invalidates" : 0,
						"advanced" : 104,
						"needTime" : 0,
						"needFetch" : 0,
						"isEOF" : 1,
						"keyPattern" : "{ attr: 1.0 }",
						"boundsVerbose" : "field #0['attr']: [\"size::8B\", \"size::8B\"]",
						"isMultiKey" : 1,
						"yieldMovedCursor" : 0,
						"dupsTested" : 104,
						"dupsDropped" : 0,
						"seenInvalidated" : 0,
						"matchTested" : 0,
						"keysExamined" : 104,
						"children" : [ ]
					}
				]
			}
		]
	}
}

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