[SERVER-16750] Document never matching query predicate incorrectly returned by query if concurrently updated (WiredTiger) Created: 07/Jan/15  Updated: 14/Oct/22  Resolved: 15/Jan/15

Status: Closed
Project: Core Server
Component/s: Querying, Storage
Affects Version/s: 2.8.0-rc4
Fix Version/s: 3.0.0-rc6

Type: Bug Priority: Critical - P2
Reporter: J Rassi Assignee: David Storch
Resolution: Done Votes: 0
Labels: None
Remaining Estimate: Not Specified
Time Spent: Not Specified
Original Estimate: Not Specified

Issue Links:
Related
related to SERVER-16675 getMore looks up doc with invalid Rec... Closed
is related to SERVER-70446 [CQF] Enable yield-safe plans Backlog
Backwards Compatibility: Fully Compatible
Operating System: ALL
Participants:

 Description   

When a query run against a WiredTiger-enabled mongod yields (or is saved for a getMore), the query's storage-layer snapshot is dropped and later replaced by a new snapshot. For queries that perform multiple index lookups for a single document, this creates an opportunity for index key data saved by the query stage tree to be stale by the time the new snapshot is created. As a result, queries can return documents that never match the given predicate, if they partially match the predicate in an old snapshot and partially match the predicate in a new shapshot. For example, the below script shows a query with predicate {a: 1, b: 1} returning a document that matches predicates {a: 1} and {b: 1} at separate times, but never at the same time.

This issue does not affect mongod configured with the MMAPv1 storage engine, as the write invalidation framework forces queries to perform a full predicate re-evaluation on documents that are mutated over the course of the query's lifetime.

To reproduce, run the following shell script against a mongod configured with the WiredTiger storage engine:

db.foo.drop();
for (var i=0; i<1000; i++) {
    assert.writeOK(db.foo.insert({_id: i, a: 2, b: 1}));
}
assert.writeOK(db.foo.insert({_id: -1, a: 1, b: 2}));
assert.commandWorked(db.foo.ensureIndex({a: 1}));
assert.commandWorked(db.foo.ensureIndex({b: 1}));
 
// Add artificial score boost to AND_SORTED plans.
assert.commandWorked(db.adminCommand({setParameter: 1, internalQueryForceIntersectionPlans: true}));
 
// Increase frequency of yielding.
assert.commandWorked(db.adminCommand({setParameter: 1, internalQueryExecYieldIterations: 2}));
 
// In a parallel shell, continuously flop the "a" and "b" values of the {_id: -1} document.
startParallelShell(
    "while (true) { " +
    "   assert.writeOK(db.foo.update({_id: -1}, {$set: {a: 2, b: 1}})); " +
    "   assert.writeOK(db.foo.update({_id: -1}, {$set: {a: 1, b: 2}})); " +
    "}"
);
while (true) {
    // Run an AND_SORTED intersection query on a predicate that matches no documents.
    // This below assertion fails when the query incorrectly returns the {_id: -1} document.
    assert.eq(0, db.foo.find({a: 1, b: 1}, {_id: 0, a: 1, b: 1}).itcount());
}



 Comments   
Comment by Githook User [ 15/Jan/15 ]

Author:

{u'username': u'dstorch', u'name': u'David Storch', u'email': u'david.storch@10gen.com'}

Message: SERVER-16750 doc-locking storage engines must recheck exact predicates for index intersection
Branch: master
https://github.com/mongodb/mongo/commit/dbe1b1677a85721c6041903bc28411ca40682747

Comment by J Rassi [ 07/Jan/15 ]

eliot recommends to investigate an approach that forces a full predicate re-evaluation for plans where index intersection is used.

Comment by J Rassi [ 07/Jan/15 ]

Example query results:

> db.foo.find({a: 1, b: 1}, {_id: 0, a: 1, b: 1})
{ "a" : 1, "b" : 2 }

Query execution stats:

> db.foo.find({a: 1, b: 1}, {_id: 0, a: 1, b: 1}).explain("executionStats")
{
	"queryPlanner" : {
		"plannerVersion" : 1,
		"namespace" : "test.foo",
		"indexFilterSet" : false,
		"parsedQuery" : {
			"$and" : [
				{
					"a" : {
						"$eq" : 1
					}
				},
				{
					"b" : {
						"$eq" : 1
					}
				}
			]
		},
		"winningPlan" : {
			"stage" : "PROJECTION",
			"transformBy" : {
				"_id" : 0,
				"a" : 1,
				"b" : 1
			},
			"inputStage" : {
				"stage" : "KEEP_MUTATIONS",
				"inputStage" : {
					"stage" : "AND_SORTED",
					"inputStages" : [
						{
							"stage" : "IXSCAN",
							"keyPattern" : {
								"a" : 1
							},
							"indexName" : "a_1",
							"isMultiKey" : false,
							"direction" : "forward",
							"indexBounds" : {
								"a" : [
									"[1.0, 1.0]"
								]
							}
						},
						{
							"stage" : "IXSCAN",
							"keyPattern" : {
								"b" : 1
							},
							"indexName" : "b_1",
							"isMultiKey" : false,
							"direction" : "forward",
							"indexBounds" : {
								"b" : [
									"[1.0, 1.0]"
								]
							}
						}
					]
				}
			}
		},
		"rejectedPlans" : [
			{
				"stage" : "PROJECTION",
				"transformBy" : {
					"_id" : 0,
					"a" : 1,
					"b" : 1
				},
				"inputStage" : {
					"stage" : "KEEP_MUTATIONS",
					"inputStage" : {
						"stage" : "FETCH",
						"filter" : {
							"a" : {
								"$eq" : 1
							}
						},
						"inputStage" : {
							"stage" : "IXSCAN",
							"keyPattern" : {
								"b" : 1
							},
							"indexName" : "b_1",
							"isMultiKey" : false,
							"direction" : "forward",
							"indexBounds" : {
								"b" : [
									"[1.0, 1.0]"
								]
							}
						}
					}
				}
			},
			{
				"stage" : "PROJECTION",
				"transformBy" : {
					"_id" : 0,
					"a" : 1,
					"b" : 1
				},
				"inputStage" : {
					"stage" : "KEEP_MUTATIONS",
					"inputStage" : {
						"stage" : "FETCH",
						"filter" : {
							"b" : {
								"$eq" : 1
							}
						},
						"inputStage" : {
							"stage" : "IXSCAN",
							"keyPattern" : {
								"a" : 1
							},
							"indexName" : "a_1",
							"isMultiKey" : false,
							"direction" : "forward",
							"indexBounds" : {
								"a" : [
									"[1.0, 1.0]"
								]
							}
						}
					}
				}
			}
		]
	},
	"executionStats" : {
		"executionSuccess" : true,
		"nReturned" : 1,
		"executionTimeMillis" : 52,
		"totalKeysExamined" : 1002,
		"totalDocsExamined" : 0,
		"executionStages" : {
			"stage" : "PROJECTION",
			"nReturned" : 1,
			"executionTimeMillisEstimate" : 10,
			"works" : 1003,
			"advanced" : 1,
			"needTime" : 1001,
			"needFetch" : 0,
			"saveState" : 503,
			"restoreState" : 503,
			"isEOF" : 1,
			"invalidates" : 0,
			"transformBy" : {
				"_id" : 0,
				"a" : 1,
				"b" : 1
			},
			"inputStage" : {
				"stage" : "KEEP_MUTATIONS",
				"nReturned" : 1,
				"executionTimeMillisEstimate" : 10,
				"works" : 1003,
				"advanced" : 1,
				"needTime" : 1001,
				"needFetch" : 0,
				"saveState" : 503,
				"restoreState" : 503,
				"isEOF" : 1,
				"invalidates" : 0,
				"inputStage" : {
					"stage" : "AND_SORTED",
					"nReturned" : 1,
					"executionTimeMillisEstimate" : 10,
					"works" : 1003,
					"advanced" : 1,
					"needTime" : 1001,
					"needFetch" : 0,
					"saveState" : 503,
					"restoreState" : 503,
					"isEOF" : 1,
					"invalidates" : 0,
					"flagged" : 0,
					"matchTested" : 0,
					"failedAnd_0" : 0,
					"failedAnd_1" : 0,
					"inputStages" : [
						{
							"stage" : "IXSCAN",
							"nReturned" : 1,
							"executionTimeMillisEstimate" : 0,
							"works" : 2,
							"advanced" : 1,
							"needTime" : 0,
							"needFetch" : 0,
							"saveState" : 503,
							"restoreState" : 503,
							"isEOF" : 1,
							"invalidates" : 0,
							"keyPattern" : {
								"a" : 1
							},
							"indexName" : "a_1",
							"isMultiKey" : false,
							"direction" : "forward",
							"indexBounds" : {
								"a" : [
									"[1.0, 1.0]"
								]
							},
							"keysExamined" : 1,
							"dupsTested" : 0,
							"dupsDropped" : 0,
							"seenInvalidated" : 0,
							"matchTested" : 0
						},
						{
							"stage" : "IXSCAN",
							"nReturned" : 1001,
							"executionTimeMillisEstimate" : 10,
							"works" : 1001,
							"advanced" : 1001,
							"needTime" : 0,
							"needFetch" : 0,
							"saveState" : 503,
							"restoreState" : 503,
							"isEOF" : 1,
							"invalidates" : 0,
							"keyPattern" : {
								"b" : 1
							},
							"indexName" : "b_1",
							"isMultiKey" : false,
							"direction" : "forward",
							"indexBounds" : {
								"b" : [
									"[1.0, 1.0]"
								]
							},
							"keysExamined" : 1001,
							"dupsTested" : 0,
							"dupsDropped" : 0,
							"seenInvalidated" : 0,
							"matchTested" : 0
						}
					]
				}
			}
		}
	},
	"serverInfo" : {
		"host" : "rassi",
		"port" : 27017,
		"version" : "2.8.0-rc5-pre-",
		"gitVersion" : "e35f2d62ccabee95075dd03d2eac85339e063e37"
	},
	"ok" : 1
}
>

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