[SERVER-19394] Results in incorrect order for query with bounded sort on multi-key field when SORT_MERGE plan used Created: 14/Jul/15  Updated: 06/Dec/22  Resolved: 10/Nov/17

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

Type: Bug Priority: Major - P3
Reporter: J Rassi Assignee: Backlog - Query Team (Inactive)
Resolution: Done Votes: 0
Labels: None
Remaining Estimate: Not Specified
Time Spent: Not Specified
Original Estimate: Not Specified

Issue Links:
Related
related to SERVER-11878 Results in incorrect order for sharde... Closed
is related to SERVER-19397 Results in incorrect order for comple... Closed
is related to SERVER-19402 Change semantics of sorting by array ... Closed
Assigned Teams:
Query
Operating System: ALL
Participants:

 Description   

The SORT_MERGE query stage uses BSONElement::woCompare() to compare WorkingSetMembers from its child stages, instead using the SortStageKeyGenerator to generate sort keys. As a result, query plans that use the SORT_MERGE stage which are performing a bounded sort on a multi-key field can generate results in incorrect order. This issue is quite similar to SERVER-11878.

To reproduce:

> db.bar.drop()
true
> db.bar.insert({_id: 0, a: [8], b: 1})
WriteResult({ "nInserted" : 1 })
> db.bar.insert({_id: 1, a: [6, 10], b: 1})
WriteResult({ "nInserted" : 1 })
> db.bar.ensureIndex({a: 1})
{
	"createdCollectionAutomatically" : false,
	"numIndexesBefore" : 1,
	"numIndexesAfter" : 2,
	"ok" : 1
}
> db.bar.find({$or: [{a: {$gt: 7}}, {a: {$gt: 6}}]}).sort({a: 1}) // SORT_MERGE not used: correct order.
{ "_id" : 0, "a" : [ 8 ], "b" : 1 }
{ "_id" : 1, "a" : [ 6, 10 ], "b" : 1 }
> db.bar.find({$or: [{a: {$gt: 7}, b: 1}, {a: {$gt: 6}, b: 1}]}).sort({a: 1}) // SORT_MERGE used: incorrect order.
{ "_id" : 1, "a" : [ 6, 10 ], "b" : 1 }
{ "_id" : 0, "a" : [ 8 ], "b" : 1 }



 Comments   
Comment by David Storch [ 10/Nov/17 ]

This bug has been fixed as part of SERVER-19402. Resolving as Gone Away. Note that SERVER-19402 changes the semantics of sorting by array fields, thereby making it illegal for a multikey index to provide a non-blocking sort plan. Please review the issue status box in that ticket for more details.

Comment by J Rassi [ 14/Jul/15 ]

Explain output for the query not using the SORT_MERGE stage:

> db.bar.find({$or: [{a: {$gt: 7}}, {a: {$gt: 6}}]}).sort({a: 1}).explain()
{
	"queryPlanner" : {
		"plannerVersion" : 1,
		"namespace" : "test.bar",
		"indexFilterSet" : false,
		"parsedQuery" : {
			"$or" : [
				{
					"a" : {
						"$gt" : 7
					}
				},
				{
					"a" : {
						"$gt" : 6
					}
				}
			]
		},
		"winningPlan" : {
			"stage" : "FETCH",
			"inputStage" : {
				"stage" : "IXSCAN",
				"keyPattern" : {
					"a" : 1
				},
				"indexName" : "a_1",
				"isMultiKey" : true,
				"isUnique" : false,
				"isSparse" : false,
				"isPartial" : false,
				"indexVersion" : 1,
				"direction" : "forward",
				"indexBounds" : {
					"a" : [
						"(6.0, inf.0]"
					]
				}
			}
		},
		"rejectedPlans" : [ ]
	},
	"serverInfo" : {
		"host" : "rassi",
		"port" : 27017,
		"version" : "3.1.6-pre-",
		"gitVersion" : "63863aefa21b33e6f84b8b466f70581dd921dba7"
	},
	"ok" : 1
}

Explain output for the query using the SORT_MERGE stage:

> db.bar.find({$or: [{a: {$gt: 7}, b: 1}, {a: {$gt: 6}, b: 1}]}).sort({a: 1}).explain()
{
	"queryPlanner" : {
		"plannerVersion" : 1,
		"namespace" : "test.bar",
		"indexFilterSet" : false,
		"parsedQuery" : {
			"$or" : [
				{
					"$and" : [
						{
							"b" : {
								"$eq" : 1
							}
						},
						{
							"a" : {
								"$gt" : 7
							}
						}
					]
				},
				{
					"$and" : [
						{
							"b" : {
								"$eq" : 1
							}
						},
						{
							"a" : {
								"$gt" : 6
							}
						}
					]
				}
			]
		},
		"winningPlan" : {
			"stage" : "SORT_MERGE",
			"sortPattern" : {
				"a" : 1
			},
			"inputStages" : [
				{
					"stage" : "FETCH",
					"filter" : {
						"b" : {
							"$eq" : 1
						}
					},
					"inputStage" : {
						"stage" : "IXSCAN",
						"keyPattern" : {
							"a" : 1
						},
						"indexName" : "a_1",
						"isMultiKey" : true,
						"isUnique" : false,
						"isSparse" : false,
						"isPartial" : false,
						"indexVersion" : 1,
						"direction" : "forward",
						"indexBounds" : {
							"a" : [
								"(7.0, inf.0]"
							]
						}
					}
				},
				{
					"stage" : "FETCH",
					"filter" : {
						"b" : {
							"$eq" : 1
						}
					},
					"inputStage" : {
						"stage" : "IXSCAN",
						"keyPattern" : {
							"a" : 1
						},
						"indexName" : "a_1",
						"isMultiKey" : true,
						"isUnique" : false,
						"isSparse" : false,
						"isPartial" : false,
						"indexVersion" : 1,
						"direction" : "forward",
						"indexBounds" : {
							"a" : [
								"(6.0, inf.0]"
							]
						}
					}
				}
			]
		},
		"rejectedPlans" : [ ]
	},
	"serverInfo" : {
		"host" : "rassi",
		"port" : 27017,
		"version" : "3.1.6-pre-",
		"gitVersion" : "63863aefa21b33e6f84b8b466f70581dd921dba7"
	},
	"ok" : 1
}

Edit: The internalQueryPlanOrChildrenIndependently parameter was set to 'false' for the above two executions in order to simplify the explain output, though the same problem also manifests when the flag is set to true.

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