[SERVER-19996] Queries which specify sort and batch size can generate results out of order, if documents concurrently updated Created: 17/Aug/15  Updated: 21/Dec/15  Resolved: 18/Sep/15

Status: Closed
Project: Core Server
Component/s: Querying
Affects Version/s: None
Fix Version/s: 3.0.9, 3.1.9

Type: Bug Priority: Major - P3
Reporter: J Rassi Assignee: David Storch
Resolution: Done Votes: 0
Labels: neweng
Remaining Estimate: Not Specified
Time Spent: Not Specified
Original Estimate: Not Specified

Issue Links:
Duplicate
Related
related to SERVER-17011 Cursor can return objects out of orde... Closed
Backwards Compatibility: Fully Compatible
Operating System: ALL
Backport Completed:
Sprint: Quint 9 09/18/15
Participants:

 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



 Comments   
Comment by Githook User [ 21/Dec/15 ]

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

Comment by Githook User [ 18/Sep/15 ]

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

Comment by YunHe Wang [ 17/Sep/15 ]

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.

Comment by David Storch [ 08/Sep/15 ]

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.

Generated at Thu Feb 08 03:52:48 UTC 2024 using Jira 9.7.1#970001-sha1:2222b88b221c4928ef0de3161136cc90c8356a66.