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

    XMLWordPrintable

    Details

    • Type: Bug
    • Status: Closed
    • Priority: Major - P3
    • Resolution: Fixed
    • Affects Version/s: 2.6.9, 3.0.2
    • Fix Version/s: 3.2.3, 3.3.2
    • Component/s: Querying
    • Labels:
    • Environment:
      Ubuntu 12.04
    • Backwards Compatibility:
      Fully Compatible
    • Operating System:
      Linux
    • Backport Completed:
    • Steps To Reproduce:
      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 }
    • Sprint:
      Query F (02/01/16), Query 10 (02/22/16)

      Description

      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

        Attachments

          Issue Links

            Activity

              People

              • Votes:
                0 Vote for this issue
                Watchers:
                13 Start watching this issue

                Dates

                • Created:
                  Updated:
                  Resolved: