[SERVER-14034] Sorted $in query with large number of elements can't use merge sort Created: 22/May/14  Updated: 11/Jul/16  Resolved: 04/Jun/14

Status: Closed
Project: Core Server
Component/s: Querying
Affects Version/s: 2.6.1
Fix Version/s: 2.6.4, 2.7.2

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:
Depends
Related
related to SERVER-14071 For queries with .sort(), bad non-blo... Closed
related to SERVER-14070 Compound index not providing sort if ... Closed
Tested
Operating System: ALL
Backport Completed:
Participants:

 Description   
Issue Status as of Jul 22, 2014

ISSUE SUMMARY

The query planner in MongoDB contains a mechanism called "explode for sort" that allows for efficient non-blocking sorts using indexes for queries that are unions of point intervals. The "explode for sort" mechanism creates a number of individual index scan stages that can later be combined with a merge sort to yield the final sorted result.

The current implementation of the query planner limits the number of such index scan stages to perform a merge sort to 50 as a hard-coded value. This limit can be reached quickly and needs to be increased.

Example:

For an index on {a:1, b:1, c:1} and a query of the type

db.coll.find( {
  a: {$in: [ 1, 2, 3, 4, 5, 6, 7, 8, 9, 10 ] }, 
  b: {$in: [ 1, 2, 3, 4, 5, 6 ] }
).sort( {c: 1} )

the query planner would create 60 (10 * 6) index scan stages. This number is above the threshold of 50 and the query would not be eligible for the "explode to sort" optimization and could therefore not use the index {a:1, b:1, c:1} to sort. Instead, it would execute an in-memory sort.

USER IMPACT
Users with sorted $in arrays leading to more than 50 index scan stages might see significant performance impact due to the blocking sort.

WORKAROUNDS
None.

AFFECTED VERSIONS
All production release versions since 2.6.0 are affected by this issue.

FIX VERSION
The fix is included in the 2.6.4 production release.

RESOLUTION DETAILS
The maximum number index scan stages eligible for the "explode for sort" optimization has been increased from 50 to 200 and additionally the constant has been made a "query knob", exposed in query_knobs.cpp.

Original description

I have these indexes:

_id:1 (default)

_a:1, _id:1 (shard key)

Observed that query of the form: _a $in [ long list ] , _id {$lt: value} sorted by _id picks _id index when there are no results that match, but of course where there are results, _a_id index is much better. edit long list happens to have 53 elements, just above the 50 threshold. Example:

> db.content.find({ "_a" : { "$in" : [ "0", "1", "1495", "2", "3", "4", "415", "6", "7", "8", "2861", "9", "11", "405", "5963", "16", "12542", "2188", "20", "25", "8404", "7402", "28", "2006", "36", "2101", "51", "49", "1504", "4484", "2674", "3101", "197", "738", "1981", "5425", "763", "320", "1417", "10793", "1585", "373", "100", "101", "9926", "588", "1675", "1684", "255", "14304", "252", "2629", "355" ] }, "_id" : { "$lt" : ObjectId("537e3a08e4b08013741909d5")} }).sort({_id:-1}).explain(true)
{
	"cursor" : "BtreeCursor _id_ reverse",
	"isMultiKey" : false,
	"n" : 0,
	"nscannedObjects" : 0,
	"nscanned" : 0,
	"nscannedObjectsAllPlans" : 0,
	"nscannedAllPlans" : 0,
	"scanAndOrder" : false,
	"indexOnly" : false,
	"nYields" : 0,
	"nChunkSkips" : 0,
	"millis" : 0,
	"indexBounds" : {
		"_id" : [
			[
				ObjectId("537e3a08e4b08013741909d5"),
				ObjectId("000000000000000000000000")
			]
		]
	},
	"allPlans" : [
		{
			"cursor" : "BtreeCursor _id_ reverse",
			"isMultiKey" : false,
			"n" : 0,
			"nscannedObjects" : 0,
			"nscanned" : 0,
			"scanAndOrder" : false,
			"indexOnly" : false,
			"nChunkSkips" : 0,
			"indexBounds" : {
				"_id" : [
					[
						ObjectId("537e3a08e4b08013741909d5"),
						ObjectId("000000000000000000000000")
					]
				]
			}
		},
		{
			"cursor" : "BtreeCursor  reverse",
			"isMultiKey" : false,
			"n" : 0,
			"nscannedObjects" : 0,
			"nscanned" : 0,
			"scanAndOrder" : true,
			"indexOnly" : false,
			"nChunkSkips" : 0,
			"indexBounds" : {
				"_a" : [
					[
						"9926",
						"9926"
					],
					[
						"9",
						"9"
					],
					[
						"8404",
						"8404"
					],
					[
						"8",
						"8"
					],
					[
						"763",
						"763"
					],
					[
						"7402",
						"7402"
					],
					[
						"738",
						"738"
					],
					[
						"7",
						"7"
					],
					[
						"6",
						"6"
					],
					[
						"5963",
						"5963"
					],
					[
						"588",
						"588"
					],
					[
						"5425",
						"5425"
					],
					[
						"51",
						"51"
					],
					[
						"49",
						"49"
					],
					[
						"4484",
						"4484"
					],
					[
						"415",
						"415"
					],
					[
						"405",
						"405"
					],
					[
						"4",
						"4"
					],
					[
						"373",
						"373"
					],
					[
						"36",
						"36"
					],
					[
						"355",
						"355"
					],
					[
						"320",
						"320"
					],
					[
						"3101",
						"3101"
					],
					[
						"3",
						"3"
					],
					[
						"2861",
						"2861"
					],
					[
						"28",
						"28"
					],
					[
						"2674",
						"2674"
					],
					[
						"2629",
						"2629"
					],
					[
						"255",
						"255"
					],
					[
						"252",
						"252"
					],
					[
						"25",
						"25"
					],
					[
						"2188",
						"2188"
					],
					[
						"2101",
						"2101"
					],
					[
						"2006",
						"2006"
					],
					[
						"20",
						"20"
					],
					[
						"2",
						"2"
					],
					[
						"1981",
						"1981"
					],
					[
						"197",
						"197"
					],
					[
						"1684",
						"1684"
					],
					[
						"1675",
						"1675"
					],
					[
						"16",
						"16"
					],
					[
						"1585",
						"1585"
					],
					[
						"1504",
						"1504"
					],
					[
						"1495",
						"1495"
					],
					[
						"14304",
						"14304"
					],
					[
						"1417",
						"1417"
					],
					[
						"12542",
						"12542"
					],
					[
						"11",
						"11"
					],
					[
						"10793",
						"10793"
					],
					[
						"101",
						"101"
					],
					[
						"100",
						"100"
					],
					[
						"1",
						"1"
					],
					[
						"0",
						"0"
					]
				],
				"_id" : [
					[
						ObjectId("537e3a08e4b08013741909d5"),
						ObjectId("000000000000000000000000")
					]
				]
			}
		}
	],
	"server" : "shard-0.Socialite-Stage.6519.mongodbdns.com:27019",
	"filterSet" : false,
	"stats" : {
		"type" : "FETCH",
		"works" : 2,
		"yields" : 0,
		"unyields" : 0,
		"invalidates" : 0,
		"advanced" : 0,
		"needTime" : 0,
		"needFetch" : 0,
		"isEOF" : 1,
		"alreadyHasObj" : 0,
		"forcedFetches" : 0,
		"matchTested" : 0,
		"children" : [
			{
				"type" : "IXSCAN",
				"works" : 1,
				"yields" : 0,
				"unyields" : 0,
				"invalidates" : 0,
				"advanced" : 0,
				"needTime" : 0,
				"needFetch" : 0,
				"isEOF" : 1,
				"keyPattern" : "{ _id: 1 }",
				"boundsVerbose" : "field #0['_id']: (ObjectId('537e3a08e4b08013741909d5'), ObjectId('000000000000000000000000')]",
				"isMultiKey" : 0,
				"yieldMovedCursor" : 0,
				"dupsTested" : 0,
				"dupsDropped" : 0,
				"seenInvalidated" : 0,
				"matchTested" : 0,
				"keysExamined" : 0,
				"children" : [ ]
			}
		]
	}
}

Same query with _id changed to match more data:

shard_0:PRIMARY> db.content.find({ "_a" : { "$in" : [ "0", "1", "1495", "2", "3", "4", "415", "6", "7", "8", "2861", "9", "11", "405", "5963", "16", "12542", "2188", "20", "25", "8404", "7402", "28", "2006", "36", "2101", "51", "49", "1504", "4484", "2674", "3101", "197", "738", "1981", "5425", "763", "320", "1417", "10793", "1585", "373", "100", "101", "9926", "588", "1675", "1684", "255", "14304", "252", "2629", "355" ] }, "_id" : { "$lt" : ObjectId("537e5a08e4b08013741909d5")} }).sort({_id:-1}).explain(true)
{
	"cursor" : "BtreeCursor _a_1__id_1 reverse",
	"isMultiKey" : false,
	"n" : 39,
	"nscannedObjects" : 39,
	"nscanned" : 53,
	"nscannedObjectsAllPlans" : 120,
	"nscannedAllPlans" : 135,
	"scanAndOrder" : true,
	"indexOnly" : false,
	"nYields" : 1,
	"nChunkSkips" : 0,
	"millis" : 5,
	"indexBounds" : {
		"_a" : [
			[
				"9926",
				"9926"
			],
			[
				"9",
				"9"
			],
			[
				"8404",
				"8404"
			],
			[
				"8",
				"8"
			],
			[
				"763",
				"763"
			],
			[
				"7402",
				"7402"
			],
			[
				"738",
				"738"
			],
			[
				"7",
				"7"
			],
			[
				"6",
				"6"
			],
			[
				"5963",
				"5963"
			],
			[
				"588",
				"588"
			],
			[
				"5425",
				"5425"
			],
			[
				"51",
				"51"
			],
			[
				"49",
				"49"
			],
			[
				"4484",
				"4484"
			],
			[
				"415",
				"415"
			],
			[
				"405",
				"405"
			],
			[
				"4",
				"4"
			],
			[
				"373",
				"373"
			],
			[
				"36",
				"36"
			],
			[
				"355",
				"355"
			],
			[
				"320",
				"320"
			],
			[
				"3101",
				"3101"
			],
			[
				"3",
				"3"
			],
			[
				"2861",
				"2861"
			],
			[
				"28",
				"28"
			],
			[
				"2674",
				"2674"
			],
			[
				"2629",
				"2629"
			],
			[
				"255",
				"255"
			],
			[
				"252",
				"252"
			],
			[
				"25",
				"25"
			],
			[
				"2188",
				"2188"
			],
			[
				"2101",
				"2101"
			],
			[
				"2006",
				"2006"
			],
			[
				"20",
				"20"
			],
			[
				"2",
				"2"
			],
			[
				"1981",
				"1981"
			],
			[
				"197",
				"197"
			],
			[
				"1684",
				"1684"
			],
			[
				"1675",
				"1675"
			],
			[
				"16",
				"16"
			],
			[
				"1585",
				"1585"
			],
			[
				"1504",
				"1504"
			],
			[
				"1495",
				"1495"
			],
			[
				"14304",
				"14304"
			],
			[
				"1417",
				"1417"
			],
			[
				"12542",
				"12542"
			],
			[
				"11",
				"11"
			],
			[
				"10793",
				"10793"
			],
			[
				"101",
				"101"
			],
			[
				"100",
				"100"
			],
			[
				"1",
				"1"
			],
			[
				"0",
				"0"
			]
		],
		"_id" : [
			[
				ObjectId("537e5a08e4b08013741909d5"),
				ObjectId("000000000000000000000000")
			]
		]
	},
	"allPlans" : [
		{
			"cursor" : "BtreeCursor _a_1__id_1 reverse",
			"isMultiKey" : false,
			"n" : 39,
			"nscannedObjects" : 39,
			"nscanned" : 53,
			"scanAndOrder" : true,
			"indexOnly" : false,
			"nChunkSkips" : 0,
			"indexBounds" : {
				"_a" : [
					[
						"9926",
						"9926"
					],
					[
						"9",
						"9"
					],
					[
						"8404",
						"8404"
					],
					[
						"8",
						"8"
					],
					[
						"763",
						"763"
					],
					[
						"7402",
						"7402"
					],
					[
						"738",
						"738"
					],
					[
						"7",
						"7"
					],
					[
						"6",
						"6"
					],
					[
						"5963",
						"5963"
					],
					[
						"588",
						"588"
					],
					[
						"5425",
						"5425"
					],
					[
						"51",
						"51"
					],
					[
						"49",
						"49"
					],
					[
						"4484",
						"4484"
					],
					[
						"415",
						"415"
					],
					[
						"405",
						"405"
					],
					[
						"4",
						"4"
					],
					[
						"373",
						"373"
					],
					[
						"36",
						"36"
					],
					[
						"355",
						"355"
					],
					[
						"320",
						"320"
					],
					[
						"3101",
						"3101"
					],
					[
						"3",
						"3"
					],
					[
						"2861",
						"2861"
					],
					[
						"28",
						"28"
					],
					[
						"2674",
						"2674"
					],
					[
						"2629",
						"2629"
					],
					[
						"255",
						"255"
					],
					[
						"252",
						"252"
					],
					[
						"25",
						"25"
					],
					[
						"2188",
						"2188"
					],
					[
						"2101",
						"2101"
					],
					[
						"2006",
						"2006"
					],
					[
						"20",
						"20"
					],
					[
						"2",
						"2"
					],
					[
						"1981",
						"1981"
					],
					[
						"197",
						"197"
					],
					[
						"1684",
						"1684"
					],
					[
						"1675",
						"1675"
					],
					[
						"16",
						"16"
					],
					[
						"1585",
						"1585"
					],
					[
						"1504",
						"1504"
					],
					[
						"1495",
						"1495"
					],
					[
						"14304",
						"14304"
					],
					[
						"1417",
						"1417"
					],
					[
						"12542",
						"12542"
					],
					[
						"11",
						"11"
					],
					[
						"10793",
						"10793"
					],
					[
						"101",
						"101"
					],
					[
						"100",
						"100"
					],
					[
						"1",
						"1"
					],
					[
						"0",
						"0"
					]
				],
				"_id" : [
					[
						ObjectId("537e5a08e4b08013741909d5"),
						ObjectId("000000000000000000000000")
					]
				]
			}
		},
		{
			"cursor" : "BtreeCursor _id_ reverse",
			"isMultiKey" : false,
			"n" : 0,
			"nscannedObjects" : 81,
			"nscanned" : 82,
			"scanAndOrder" : false,
			"indexOnly" : false,
			"nChunkSkips" : 0,
			"indexBounds" : {
				"_id" : [
					[
						ObjectId("537e5a08e4b08013741909d5"),
						ObjectId("000000000000000000000000")
					]
				]
			}
		}
	],
	"server" : "shard-0.Socialite-Stage.6519.mongodbdns.com:27019",
	"filterSet" : false,
	"stats" : {
		"type" : "SORT",
		"works" : 82,
		"yields" : 1,
		"unyields" : 1,
		"invalidates" : 0,
		"advanced" : 39,
		"needTime" : 40,
		"needFetch" : 0,
		"isEOF" : 1,
		"forcedFetches" : 0,
		"memUsage" : 4782,
		"memLimit" : 33554432,
		"children" : [
			{
				"type" : "KEEP_MUTATIONS",
				"works" : 40,
				"yields" : 1,
				"unyields" : 1,
				"invalidates" : 0,
				"advanced" : 39,
				"needTime" : 0,
				"needFetch" : 0,
				"isEOF" : 1,
				"children" : [
					{
						"type" : "FETCH",
						"works" : 40,
						"yields" : 1,
						"unyields" : 1,
						"invalidates" : 0,
						"advanced" : 39,
						"needTime" : 0,
						"needFetch" : 0,
						"isEOF" : 1,
						"alreadyHasObj" : 0,
						"forcedFetches" : 0,
						"matchTested" : 0,
						"children" : [
							{
								"type" : "IXSCAN",
								"works" : 39,
								"yields" : 1,
								"unyields" : 1,
								"invalidates" : 0,
								"advanced" : 39,
								"needTime" : 0,
								"needFetch" : 0,
								"isEOF" : 1,
								"keyPattern" : "{ _a: 1.0, _id: 1.0 }",
								"boundsVerbose" : "field #0['_a']: [\"9926\", \"9926\"], [\"9\", \"9\"], [\"8404\", \"8404\"], [\"8\", \"8\"], [\"763\", \"763\"], [\"7402\", \"7402\"], [\"738\", \"738\"], [\"7\", \"7\"], [\"6\", \"6\"], [\"5963\", \"5963\"], [\"588\", \"588\"], [\"5425\", \"5425\"], [\"51\", \"51\"], [\"49\", \"49\"], [\"4484\", \"4484\"], [\"415\", \"415\"], [\"405\", \"405\"], [\"4\", \"4\"], [\"373\", \"373\"], [\"36\", \"36\"], [\"355\", \"355\"], [\"320\", \"320\"], [\"3101\", \"3101\"], [\"3\", \"3\"], [\"2861\", \"2861\"], [\"28\", \"28\"], [\"2674\", \"2674\"], [\"2629\", \"2629\"], [\"255\", \"255\"], [\"252\", \"252\"], [\"25\", \"25\"], [\"2188\", \"2188\"], [\"2101\", \"2101\"], [\"2006\", \"2006\"], [\"20\", \"20\"], [\"2\", \"2\"], [\"1981\", \"1981\"], [\"197\", \"197\"], [\"1684\", \"1684\"], [\"1675\", \"1675\"], [\"16\", \"16\"], [\"1585\", \"1585\"], [\"1504\", \"1504\"], [\"1495\", \"1495\"], [\"14304\", \"14304\"], [\"1417\", \"1417\"], [\"12542\", \"12542\"], [\"11\", \"11\"], [\"10793\", \"10793\"], [\"101\", \"101\"], [\"100\", \"100\"], [\"1\", \"1\"], [\"0\", \"0\"], field #1['_id']: (ObjectId('537e5a08e4b08013741909d5'), ObjectId('000000000000000000000000')]",
								"isMultiKey" : 0,
								"yieldMovedCursor" : 0,
								"dupsTested" : 0,
								"dupsDropped" : 0,
								"seenInvalidated" : 0,
								"matchTested" : 0,
								"keysExamined" : 53,
								"children" : [ ]
							}
						]
					}
				]
			}
		]
	}
}
shard_0:PRIMARY>

I noticed this when queries were slow - and it turned out it was using _id plan (profiling showed that).



 Comments   
Comment by Githook User [ 17/Jul/14 ]

Author:

{u'username': u'dstorch', u'name': u'David Storch', u'email': u'david.storch@10gen.com'}

Message: SERVER-14034 increase max scans from explodeForSort to 200
(cherry picked from commit 659d9ecb48f0bbddfac486962c1622737641ebc7)
Branch: v2.6
https://github.com/mongodb/mongo/commit/4723061180216589d7c4fae94988a97724310660

Comment by Githook User [ 17/Jul/14 ]

Author:

{u'username': u'dstorch', u'name': u'David Storch', u'email': u'david.storch@10gen.com'}

Message: SERVER-14034 make kMaxScansToExplode a query knob
(cherry picked from commit 0ae43e5c66c119e2963e7a58fa9cb37b8c87ff06)
Branch: v2.6
https://github.com/mongodb/mongo/commit/f71b3b73424bfa5e8746829c43e472100e413bcb

Comment by Githook User [ 04/Jun/14 ]

Author:

{u'username': u'dstorch', u'name': u'David Storch', u'email': u'david.storch@10gen.com'}

Message: SERVER-14034 increase max scans from explodeForSort to 200
Branch: master
https://github.com/mongodb/mongo/commit/659d9ecb48f0bbddfac486962c1622737641ebc7

Comment by Githook User [ 04/Jun/14 ]

Author:

{u'username': u'dstorch', u'name': u'David Storch', u'email': u'david.storch@10gen.com'}

Message: SERVER-14034 make kMaxScansToExplode a query knob
Branch: master
https://github.com/mongodb/mongo/commit/0ae43e5c66c119e2963e7a58fa9cb37b8c87ff06

Comment by Asya Kamsky [ 02/Jun/14 ]

Reopening this to triage separately from the related SERVER-14070 and SERVER-14071 and SERVER-13675

Comment by J Rassi [ 27/May/14 ]

After discussion with asya / hari.khalsa@10gen.com / david.storch, I've filed SERVER-14070 and SERVER-14071 to track the two underlying issues generating the problem reported in this ticket. Resolving as dup.

Comment by J Rassi [ 22/May/14 ]

Asya, can you also include the output of running PlanCache().getPlansByQuery() on this query?

Comment by J Rassi [ 22/May/14 ]

This looks like a dup of SERVER-12923, david.storch?

Asya, can you confirm that 2.4 picks the desired index on the same data set? Both 2.4 and 2.6 use a similar strategy to rank plans that include a blocking stage, but 2.6 has a small (but quantifiable) additional tendency towards plans without a blocking stage.

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