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

The planner can add an unnecessary in-memory sort stage for .min()/.max() queries

    • Type: Icon: Bug Bug
    • Resolution: Done
    • Priority: Icon: Major - P3 Major - P3
    • 3.2.3, 3.3.2
    • Affects Version/s: 2.6.9, 3.0.2
    • Component/s: Querying
    • Environment:
      Ubuntu 12.04
    • Fully Compatible
    • Linux
    • Hide

      So, first step, create a collection with a compound multikey index.

      > var now = new Date().getTime(); 
      > for (var i = 0; i < 10000; i++) { 
             db.SampleLong.insert({_id: ObjectId(), a: [{_id: 1}, {_id: i + 2}], t: NumberLong(now + i)}) 
        }
      > db.SampleLong.ensureIndex({"a._id": 1, t: -1}, {background: true})
      

      In 2.4.13, we have this when executing an ordered query using min / max

      > db.SampleLong.find({"a._id": 1, t: {"$lt": NumberLong("1429191483598"), "$gte": NumberLong("1429191473599")}}).min({"a._id": 1, t: NumberLong("1429191483598")}).max({"a._id": 1, t: NumberLong("1429191473599")}).limit(10).sort({t: -1}).explain()
      {
          "cursor" : "BtreeCursor a._id_1_t_-1",
          "isMultiKey" : true,
          "n" : 10,
          "nscannedObjects" : 11,
          "nscanned" : 11,
          "nscannedObjectsAllPlans" : 11,
          "nscannedAllPlans" : 11,
          "scanAndOrder" : false,
          "indexOnly" : false,
          "nYields" : 0,
          "nChunkSkips" : 0,
          "millis" : 0,
          "indexBounds" : {
              "start" : {
                  "a._id" : 1,
                  "t" : NumberLong("1429191483598")
              },
              "end" : {
                  "a._id" : 1,
                  "t" : NumberLong("1429191473599")
              }
          },
          "server" : "frank:27017"
      }
      

      And, now, the same query but on 2.6.9 (same result with MongoDB 3.0.2). MongoDB set the scanAndOrder to true whereas the index is already sorted.

      > db.SampleLong.find({"a._id": 1, t: {"$lt": NumberLong("1429191483598"), "$gte": NumberLong("1429191473599")}}).min({"a._id": 1, t: NumberLong("1429191483598")}).max({"a._id": 1, t: NumberLong("1429191473599")}).limit(10).sort({t: -1}).explain()
      {
          "clauses" : [
              {
                  "cursor" : "BtreeCursor a._id_1_t_-1",
                  "isMultiKey" : true,
                  "n" : 10,
                  "nscannedObjects" : 9999,
                  "nscanned" : 10000,
                  "scanAndOrder" : true,
                  "indexOnly" : false,
                  "nChunkSkips" : 0,
                  "indexBounds" : {
      
                  }
              },
              {
                  "cursor" : "BtreeCursor a._id_1_t_-1",
                  "isMultiKey" : true,
                  "n" : 0,
                  "nscannedObjects" : 0,
                  "nscanned" : 0,
                  "scanAndOrder" : true,
                  "indexOnly" : false,
                  "nChunkSkips" : 0,
                  "indexBounds" : {
      
                  }
              }
          ],
          "cursor" : "QueryOptimizerCursor",
          "n" : 10,
          "nscannedObjects" : 9999,
          "nscanned" : 10000,
          "nscannedObjectsAllPlans" : 9999,
          "nscannedAllPlans" : 10000,
          "scanAndOrder" : false,
          "nYields" : 78,
          "nChunkSkips" : 0,
          "millis" : 49,
          "server" : "frank:27017",
          "filterSet" : false
      }
      
      Show
      So, first step, create a collection with a compound multikey index. > var now = new Date().getTime(); > for ( var i = 0; i < 10000; i++) { db.SampleLong.insert({_id: ObjectId(), a: [{_id: 1}, {_id: i + 2}], t: NumberLong(now + i)}) } > db.SampleLong.ensureIndex({ "a._id" : 1, t: -1}, {background: true }) In 2.4.13, we have this when executing an ordered query using min / max > db.SampleLong.find({ "a._id" : 1, t: { "$lt" : NumberLong( "1429191483598" ), "$gte" : NumberLong( "1429191473599" )}}).min({ "a._id" : 1, t: NumberLong( "1429191483598" )}).max({ "a._id" : 1, t: NumberLong( "1429191473599" )}).limit(10).sort({t: -1}).explain() { "cursor" : "BtreeCursor a._id_1_t_-1" , "isMultiKey" : true , "n" : 10, "nscannedObjects" : 11, "nscanned" : 11, "nscannedObjectsAllPlans" : 11, "nscannedAllPlans" : 11, "scanAndOrder" : false , "indexOnly" : false , "nYields" : 0, "nChunkSkips" : 0, "millis" : 0, "indexBounds" : { "start" : { "a._id" : 1, "t" : NumberLong( "1429191483598" ) }, "end" : { "a._id" : 1, "t" : NumberLong( "1429191473599" ) } }, "server" : "frank:27017" } And, now, the same query but on 2.6.9 (same result with MongoDB 3.0.2). MongoDB set the scanAndOrder to true whereas the index is already sorted. > db.SampleLong.find({ "a._id" : 1, t: { "$lt" : NumberLong( "1429191483598" ), "$gte" : NumberLong( "1429191473599" )}}).min({ "a._id" : 1, t: NumberLong( "1429191483598" )}).max({ "a._id" : 1, t: NumberLong( "1429191473599" )}).limit(10).sort({t: -1}).explain() { "clauses" : [ { "cursor" : "BtreeCursor a._id_1_t_-1" , "isMultiKey" : true , "n" : 10, "nscannedObjects" : 9999, "nscanned" : 10000, "scanAndOrder" : true , "indexOnly" : false , "nChunkSkips" : 0, "indexBounds" : { } }, { "cursor" : "BtreeCursor a._id_1_t_-1" , "isMultiKey" : true , "n" : 0, "nscannedObjects" : 0, "nscanned" : 0, "scanAndOrder" : true , "indexOnly" : false , "nChunkSkips" : 0, "indexBounds" : { } } ], "cursor" : "QueryOptimizerCursor" , "n" : 10, "nscannedObjects" : 9999, "nscanned" : 10000, "nscannedObjectsAllPlans" : 9999, "nscannedAllPlans" : 10000, "scanAndOrder" : false , "nYields" : 78, "nChunkSkips" : 0, "millis" : 49, "server" : "frank:27017" , "filterSet" : false }
    • Query F (02/01/16), Query 10 (02/22/16)

      IndexScanNode::computeProperties() computes sort orders provided by the index scan. It obtains some of these sort orders by looking at the contents of its IndexBounds instance. However, it fails to compute some obvious sort orders when isSimpleRange is true. As a result, plans for .min()/.max() queries may involve an unnecessary in-memory SORT stage.

      Original Description

      We currently run a sharding in production in 2.4.13 with a fairly large collection and a compound multikey index. We met the problem with multi key index with unbound limit that we solved using cursor.min and cursor.max.
      But after upgrading to 2.6.9, we realized that the behavior between the two versions has changed. MongoDB uses the correct index but specifies a scanAndOrder to true even if the index is well sorted.
      I have asked the question on stackoverflow but didn't receive so far any answers.
      http://stackoverflow.com/questions/29679635/behavior-has-changed-between-mongodb-2-4-and-2-6-for-cursor-min-max

            Assignee:
            tess.avitabile@mongodb.com Tess Avitabile (Inactive)
            Reporter:
            PierreCoquentin Pierre Coquentin
            Votes:
            0 Vote for this issue
            Watchers:
            12 Start watching this issue

              Created:
              Updated:
              Resolved: