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).
- related to
-
SERVER-14071 For queries with .sort(), bad non-blocking plan can be cached if there are zero results
-
- Closed
-
-
SERVER-14070 Compound index not providing sort if equality predicate given on sort field
-
- Closed
-