Uploaded image for project: 'Core Server'
  1. Core Server
  2. SERVER-14034

Sorted $in query with large number of elements can't use merge sort

    • Type: Icon: Bug Bug
    • Resolution: Done
    • Priority: Icon: Major - P3 Major - P3
    • 2.6.4, 2.7.2
    • Affects Version/s: 2.6.1
    • Component/s: Querying
    • None
    • ALL

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

            Assignee:
            david.storch@mongodb.com David Storch
            Reporter:
            asya.kamsky@mongodb.com Asya Kamsky
            Votes:
            0 Vote for this issue
            Watchers:
            6 Start watching this issue

              Created:
              Updated:
              Resolved: