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

Missing sort order for compound index leads to unnecessary in-memory sort

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

      Issue Status as of April 18, 2014

      ISSUE SUMMARY
      In query execution, the index scan phase returns a stream of documents and a set of all sort orders that are satisfied by the stream. Version 2.6.0 contains a logical bug that in some cases misses a sort order in this set. This can lead to an additional in-memory sort phase that would not be necessary.

      USER IMPACT
      This is a behavior change from version 2.4 that can negatively impact performance of the affected queries. In cases where the size of returned documents exceeds the limit of 32MB, the query fails with an error.

      WORKAROUNDS
      In most cases, an appropriate index can be found that supports the sort. See the ticket comments for details and an example.

      RESOLUTION
      The patch fixes a logical error in the query execution code and now properly returns all sort orders.

      AFFECTED VERSIONS
      Version 2.6.0 is affected by this issue.

      PATCHES
      The patch is included in the 2.6.1 production release.

      Original description

      Suppose you have a compound index {a: 1, b: 1, c: 1, d: 1} and a query with point intervals over 'a' and 'b'. The index scan can provide the following sort orders (both ascending and descending):

      {a: 1}, {a: 1, b: 1}, {a: 1, b: 1, c: 1}, {a: 1, b: 1 c: 1, d: 1}, {b: 1, c: 1, d: 1}, {c: 1, d: 1}, and {c: 1}
      

      The code as it stands considers all of these sort orders except for one: {c: 1}. Specifically, it misses prefixes of the sort orders which do not begin with the first field in the compound index.

      There appears to be a regression in the sort phase between 2.6.0 and 2.4.8.
      It's easiest to illustrate it with an an example. In 2.4.8 the sort uses the index, whereas in 2.6.0 it doesn't, which in our case leads to an overflow error.

      db.slices.drop()
      var c = Array(250000);
      for(i=0; i<250000; i++) c[i] = i;
      
      db.slices.ensureIndex({group:1, rs:1, timestamp:1, _id : 1 });
      for(i = 0; i < 100; i++) { db.slices.insert({group : "A", rs: "name", timestamp : new Date(), dan : "bp", data:c});}
      

      In 2.4.8

      > db.slices.find({group : "A", rs:"name"}, {data : 0}).sort({timestamp : -1}).explain()
      {
      	"cursor" : "BtreeCursor group_1_rs_1_timestamp_1__id_1 reverse",
      	"isMultiKey" : false,
      	"n" : 100,
      	"nscannedObjects" : 100,
      	"nscanned" : 100,
      	"nscannedObjectsAllPlans" : 100,
      	"nscannedAllPlans" : 100,
      	"scanAndOrder" : false,
      	"indexOnly" : false,
      	"nYields" : 0,
      	"nChunkSkips" : 0,
      	"millis" : 0,
      	"indexBounds" : {
      		"group" : [
      			[
      				"A",
      				"A"
      			]
      		],
      		"rs" : [
      			[
      				"name",
      				"name"
      			]
      		],
      		"timestamp" : [
      			[
      				{
      					"$maxElement" : 1
      				},
      				{
      					"$minElement" : 1
      				}
      			]
      		],
      		"_id" : [
      			[
      				{
      					"$maxElement" : 1
      				},
      				{
      					"$minElement" : 1
      				}
      			]
      		]
      	},
      	"server" : "boxster:27017"
      }
      

      In 2.6.0:

      db.slices.find({group : "A", rs:"name"}, {data : 0}).sort({timestamp : -1}).explain()
      2014-04-16T11:23:57.863-0400 error: {
      	"$err" : "Runner error: Overflow sort stage buffered data usage of 35000910 bytes exceeds internal limit of 33554432 bytes",
      	"code" : 17144
      

      If the sort is changed to

      {timestamp : 1}

      to match the direction of the index, the query behaves as expected in 2.6.0.

      > db.slices.find({group : "A", rs:"name"}, {data : 0}).sort({timestamp : 1}).explain()
      {
      	"clauses" : [
      		{
      			"cursor" : "BtreeCursor group_1_rs_1_timestamp_1__id_1",
      			"isMultiKey" : false,
      			"n" : 100,
      			"nscannedObjects" : 100,
      			"nscanned" : 100,
      			"scanAndOrder" : false,
      			"indexOnly" : false,
      			"nChunkSkips" : 0,
      			"indexBounds" : {
      				"group" : [
      					[
      						"A",
      						"A"
      					]
      				],
      				"rs" : [
      					[
      						"name",
      						"name"
      					]
      				],
      				"timestamp" : [
      					[
      						{
      							"$minElement" : 1
      						},
      						{
      							"$maxElement" : 1
      						}
      					]
      				],
      				"_id" : [
      					[
      						{
      							"$minElement" : 1
      						},
      						{
      							"$maxElement" : 1
      						}
      					]
      				]
      			}
      		}
      	],
      	"cursor" : "QueryOptimizerCursor",
      	"n" : 100,
      	"nscannedObjects" : 100,
      	"nscanned" : 100,
      	"nscannedObjectsAllPlans" : 100,
      	"nscannedAllPlans" : 100,
      	"scanAndOrder" : false,
      	"nYields" : 1,
      	"nChunkSkips" : 0,
      	"millis" : 0,
      	"server" : "boxster:27017",
      	"filterSet" : false
      }
      

      Credit: danny.gottlieb@gmail.com

            Assignee:
            david.storch@mongodb.com David Storch
            Reporter:
            steve.briskin Steve Briskin (Inactive)
            Votes:
            0 Vote for this issue
            Watchers:
            10 Start watching this issue

              Created:
              Updated:
              Resolved: