[SERVER-19397] Results in incorrect order for complex $or query with bounded sort on multi-key field when SORT 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
related to SERVER-19394 Results in incorrect order for query ... Closed
is related to SERVER-19402 Change semantics of sorting by array ... Closed
Assigned Teams:
Query
Operating System: ALL
Participants:

 Description   

The SortStageKeyGenerator component of the SORT query stage does not properly extract bounds from queries if the bounds generation planning process generates an OR plan. As a result, certain $or queries that use the SORT stage which are performing a bounded sort on a multi-key field can generate results in incorrect order.

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.find({$or: [{a: {$gt: 7}}, {a: {$gt: 6}}]}).sort({a: 1}) // Bounds generation planning generates FETCH <= IXSCAN plan: 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}) // Bounds generation planning generates OR plan: incorrect order.
{ "_id" : 1, "a" : [ 6, 10 ], "b" : 1 }
{ "_id" : 0, "a" : [ 8 ], "b" : 1 }

Both of the above plans generate SORT <= COLLSCAN plans (as the collection has no indexes), but they differ in the bounds generation planning process. For the first query, bounds generation planning yields sort key bounds of (6, infinity), as a FETCH <= IXSCAN plan is generated where the index scan stage has these bounds. For the second query, bounds generation planning yields no sort key bounds, as an OR plan is generated and the SortStageKeyGenerator does not handle these plans.



 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 ]

Solution from bounds generation planning for first query ({$or: [{a: {$gt: 7}}, {a: {$gt: 6}}]}):

FETCH
---fetched = 1
---sortedByDiskLoc = 0
---getSort = [{ a: 1 }, ]
---Child:
------IXSCAN
---------keyPattern = { a: 1.0 }
---------direction = 1
---------bounds = field #0['a']: (6.0, inf.0]
---------fetched = 0
---------sortedByDiskLoc = 0
---------getSort = [{ a: 1 }, ]

Solution from bounds generation planning for second query ({$or: [{a: {$gt: 7}, b: 1}, {a: {$gt: 6}, b: 1}]}):

OR
---fetched = 1
---sortedByDiskLoc = 0
---getSort = []
---Child 0:
------FETCH
---------filter:
                b == 1.0
---------fetched = 1
---------sortedByDiskLoc = 0
---------getSort = [{ a: 1 }, ]
---------Child:
------------IXSCAN
---------------keyPattern = { a: 1.0 }
---------------direction = 1
---------------bounds = field #0['a']: (7.0, inf.0]
---------------fetched = 0
---------------sortedByDiskLoc = 0
---------------getSort = [{ a: 1 }, ]
 
---Child 1:
------FETCH
---------filter:
                b == 1.0
---------fetched = 1
---------sortedByDiskLoc = 0
---------getSort = [{ a: 1 }, ]
---------Child:
------------IXSCAN
---------------keyPattern = { a: 1.0 }
---------------direction = 1
---------------bounds = field #0['a']: (6.0, inf.0]
---------------fetched = 0
---------------sortedByDiskLoc = 0
---------------getSort = [{ a: 1 }, ]

Link to code in SortStageKeyGenerator that needs to be updated to handle an OR plan: <https://github.com/mongodb/mongo/blob/r3.1.5/src/mongo/db/exec/sort.cpp#L240-L258>.

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