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

Queries which specify sort and batch size can generate results out of order, if documents concurrently updated

    Details

    • Type: Bug
    • Status: Closed
    • Priority: Major - P3
    • Resolution: Fixed
    • Affects Version/s: None
    • Fix Version/s: 3.0.9, 3.1.9
    • Component/s: Querying
    • Labels:
    • Backwards Compatibility:
      Fully Compatible
    • Operating System:
      ALL
    • Backport Completed:
    • Sprint:
      Quint 9 09/18/15

      Description

      The KeepMutationsNode query solution node is added to the incorrect place in the query solution tree for "split limited sort" plans (which are generated when a sort and a positive ntoreturn are specified). As a consequence, if the documents to be returned are concurrently updated, the KeepMutationsStage can inject these documents into the result stream out of order.

      Affects versions released since 2.5.5.

      Reproduce with the following:

      db.foo.drop();
      for (var i = 0; i < 6; ++i) {
          db.foo.insert({a: 1, b: i, c: 1});
      }
      assert.commandWorked(db.adminCommand({setParameter: 1, internalQueryExecYieldIterations: 1}));
      db.foo.ensureIndex({a: 1});
      startParallelShell("for (;;) { db.foo.update({}, {$inc: {c: 1}}, {multi: true}); }");
      for (;;) {
          var results = db.foo.find({a: 1}).sort({b: 1}).batchSize(2).toArray();
          var resultsSorted = results.concat().sort(function(lhs, rhs) { return lhs.b - rhs.b; });
          assert.eq(results, resultsSorted);
      }
      

      Output generated:

      assert: [[
      	{
      		"_id" : ObjectId("55d2789ecce4f5bfbe04948f"),
      		"a" : 1,
      		"b" : 0,
      		"c" : 3
      	},
      	{
      		"_id" : ObjectId("55d2789ecce4f5bfbe049490"),
      		"a" : 1,
      		"b" : 1,
      		"c" : 3
      	},
      	{
      		"_id" : ObjectId("55d2789ecce4f5bfbe04948f"),
      		"a" : 1,
      		"b" : 0,
      		"c" : 3
      	},
      	{
      		"_id" : ObjectId("55d2789ecce4f5bfbe049490"),
      		"a" : 1,
      		"b" : 1,
      		"c" : 3
      	},
      	{
      		"_id" : ObjectId("55d2789ecce4f5bfbe049491"),
      		"a" : 1,
      		"b" : 2,
      		"c" : 3
      	},
      	{
      		"_id" : ObjectId("55d2789ecce4f5bfbe049492"),
      		"a" : 1,
      		"b" : 3,
      		"c" : 3
      	},
      	{
      		"_id" : ObjectId("55d2789ecce4f5bfbe049493"),
      		"a" : 1,
      		"b" : 4,
      		"c" : 3
      	},
      	{
      		"_id" : ObjectId("55d2789ecce4f5bfbe049494"),
      		"a" : 1,
      		"b" : 5,
      		"c" : 3
      	}
      ]] != [[
      	{
      		"_id" : ObjectId("55d2789ecce4f5bfbe04948f"),
      		"a" : 1,
      		"b" : 0,
      		"c" : 3
      	},
      	{
      		"_id" : ObjectId("55d2789ecce4f5bfbe04948f"),
      		"a" : 1,
      		"b" : 0,
      		"c" : 3
      	},
      	{
      		"_id" : ObjectId("55d2789ecce4f5bfbe049490"),
      		"a" : 1,
      		"b" : 1,
      		"c" : 3
      	},
      	{
      		"_id" : ObjectId("55d2789ecce4f5bfbe049490"),
      		"a" : 1,
      		"b" : 1,
      		"c" : 3
      	},
      	{
      		"_id" : ObjectId("55d2789ecce4f5bfbe049491"),
      		"a" : 1,
      		"b" : 2,
      		"c" : 3
      	},
      	{
      		"_id" : ObjectId("55d2789ecce4f5bfbe049492"),
      		"a" : 1,
      		"b" : 3,
      		"c" : 3
      	},
      	{
      		"_id" : ObjectId("55d2789ecce4f5bfbe049493"),
      		"a" : 1,
      		"b" : 4,
      		"c" : 3
      	},
      	{
      		"_id" : ObjectId("55d2789ecce4f5bfbe049494"),
      		"a" : 1,
      		"b" : 5,
      		"c" : 3
      	}
      ]] are not equal : undefined
      

        Issue Links

          Activity

          Hide
          david.storch David Storch added a comment -

          This problem is due not only to the KEEP_MUTATIONS stage being misplaced in the query plan tree: it's also due to SERVER-17011. The problem described in SERVER-17011 will be fixed with the introduction of the separate limit and batchSize fields in the find command, but this will not be available until version 3.2. Keeping this ticket open to see if we can design a targeted fix for the 3.0 and 2.6 branches.

          Show
          david.storch David Storch added a comment - This problem is due not only to the KEEP_MUTATIONS stage being misplaced in the query plan tree: it's also due to SERVER-17011 . The problem described in SERVER-17011 will be fixed with the introduction of the separate limit and batchSize fields in the find command, but this will not be available until version 3.2. Keeping this ticket open to see if we can design a targeted fix for the 3.0 and 2.6 branches.
          Hide
          yunhe.wang YunHe Wang added a comment -

          The reproduction actually catches the bug pointed out in SERVER-17011. The fix for this ticket will still address KeepMutationsNode being added out of place in "split limited sort" plans.

          Show
          yunhe.wang YunHe Wang added a comment - The reproduction actually catches the bug pointed out in SERVER-17011 . The fix for this ticket will still address KeepMutationsNode being added out of place in "split limited sort" plans.
          Hide
          xgen-internal-githook Githook User added a comment -

          Author:

          {u'username': u'yhjw88', u'name': u'Yunhe (John) Wang', u'email': u'yunhe.wang@mongodb.com'}

          Message: SERVER-19996 Keep Mutations no longer added on ntoreturn hack
          Branch: master
          https://github.com/mongodb/mongo/commit/e07a93a7ea6756434e0d3df38cdd1e6f5d5fd010

          Show
          xgen-internal-githook Githook User added a comment - Author: {u'username': u'yhjw88', u'name': u'Yunhe (John) Wang', u'email': u'yunhe.wang@mongodb.com'} Message: SERVER-19996 Keep Mutations no longer added on ntoreturn hack Branch: master https://github.com/mongodb/mongo/commit/e07a93a7ea6756434e0d3df38cdd1e6f5d5fd010
          Hide
          xgen-internal-githook Githook User added a comment -

          Author:

          {u'username': u'yhjw88', u'name': u'Yunhe (John) Wang', u'email': u'yunhe.wang@mongodb.com'}

          Message: SERVER-19996 Keep Mutations no longer added on ntoreturn hack

          (cherry picked from commit e07a93a7ea6756434e0d3df38cdd1e6f5d5fd010)

          Conflicts:
          src/mongo/db/query/planner_analysis.cpp
          Branch: v3.0
          https://github.com/mongodb/mongo/commit/6d5a1ddf9333de4520a1303a02b2f1377e7fd622

          Show
          xgen-internal-githook Githook User added a comment - Author: {u'username': u'yhjw88', u'name': u'Yunhe (John) Wang', u'email': u'yunhe.wang@mongodb.com'} Message: SERVER-19996 Keep Mutations no longer added on ntoreturn hack (cherry picked from commit e07a93a7ea6756434e0d3df38cdd1e6f5d5fd010) Conflicts: src/mongo/db/query/planner_analysis.cpp Branch: v3.0 https://github.com/mongodb/mongo/commit/6d5a1ddf9333de4520a1303a02b2f1377e7fd622

            People

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

              Dates

              • Created:
                Updated:
                Resolved:

                  Agile