[SERVER-65270] Multi-planned SBE queries involving large documents do not respect the 'sort' option Created: 05/Apr/22  Updated: 29/Oct/23  Resolved: 08/Apr/22

Status: Closed
Project: Core Server
Component/s: None
Affects Version/s: None
Fix Version/s: 5.3.2, 6.0.0-rc0

Type: Bug Priority: Blocker - P1
Reporter: Ian Boros Assignee: Ian Boros
Resolution: Fixed Votes: 0
Labels: bkp, query-director-triage
Remaining Estimate: Not Specified
Time Spent: Not Specified
Original Estimate: Not Specified

Issue Links:
Backports
Depends
Backwards Compatibility: Fully Compatible
Operating System: ALL
Backport Requested:
v5.3
Sprint: QE 2022-04-18
Participants:

 Description   

Running a simple query like

db.c.find({a:1}).sort({b:1,c:1})

may not actually return the results in the requested order when SBE is used, large documents are present and multi-planning occurs.

The reason for this is the behavior we have at the command level for dealing with full batches. After we've pulled a document from a PlanExecutor, if it will not fit in the batch being sent to the user, we "stash" it, essentially giving it back to the PlanExecutor so that it can be consumed later.

Sadly, this stash is implemented with a queue, which means that when a document is "stashed" it is returned in FIFO order.

With SBE, this stash is pre-populated with the results gathered during multi planning. So, if a query has a non empty stash, and one of the documents does not fit into the batch, the document will be put at the end of the queue, and the ordering provided by the query plan is lost.

In the classic engine, a queue is also used for the stash, but, because the stash is never pre-populated, the it always has a size of 0 or 1. In this case, the FIFO behavior is the same as LIFO. There is a separate stash within the MULTI_PLAN stage for each candidate that is only read from. So, this bug is specific to SBE, though the logic for this in the classic engine should also be cleaned up.

Instead of using a queue for the stash, we should use a double ended list, and we should push to the front of the list when stashing a document that won't fit in the next batch.

 

The easiest way to expose this behavior is to query on a collection with documents that are large, since it's likely that no more than one will fit in a batch.

Example repro:

(function() {                                                                                                                                                 
    function makeDoc(i) {                                                                                                                                     
        return {                                                                                                                                              
            _id: i,                                                                                                                                           
                                                                                                                                                              
            filterKey: 1,                                                                                                                                                                                                                                                                      
            num: i,                                                                                                                                           
                                                                                                                                                              
            bytes: BinData(0, "A".repeat(13981014) + "==")                                                                                                    
        };                                                                                                                                                    
    }                                                                                                                                                         
                                                                                                                                                              
    for (let i = 0; i < 10; i++) {                                                                                                                            
        assert.commandWorked(db.test.insert(makeDoc(i)));                                                                                                     
    }                                                                                                                                                         
                                                                                                                                                              
    // Two possible indexes can answer the query.                                                                                                             
    assert.commandWorked(db.test.createIndex({filterKey: 1, num:1, foo:1}));                                                                                  
    assert.commandWorked(db.test.createIndex({filterKey: 1, num:1}));                                                                                         
                                                                                                                                                              
    print("Running query\n");                                                                                                                                 
    const sortSpec = {num: 1};                                                                                                                                
                                                                                                                                                              
    // We do a "client side projection," to simplify the repro, and avoid printing out the massive                                                            
    // BinData string.                                                                                                                                        
    let seqNumRes = [];                                                                                                                                       
    db.test.find({filterKey: 1}).sort(sortSpec).forEach(doc => seqNumRes.push(doc.num));                                                                      
                                                                                                                                                              
    // This returns the results out of order.                                                                                                     
    // [ 0, 2, 4, 6, 8, 1, 5, 9, 7, 3 ]                                                                                                                       
    print("Result: " + tojson(seqNumRes));                                                                                                                    
    print("Explain: " + tojson(db.test.find({filterKey: 1}).sort(sortSpec).explain()));                                                                       
})();  



 Comments   
Comment by Githook User [ 18/Apr/22 ]

Author:

{'name': 'Ian Boros', 'email': 'ian.boros@mongodb.com', 'username': 'borosaurus'}

Message: SERVER-65270 Fix bug related to queries on large documents not respecting the sort option

(cherry picked from commit 5b5b505f0db2e145f40bde4e2ac2d5c56bc0b263)
Branch: v5.3
https://github.com/mongodb/mongo/commit/b731a58ff399ae1558bbaa0fb9b3da1d49d18313

Comment by Githook User [ 07/Apr/22 ]

Author:

{'name': 'Ian Boros', 'email': 'ian.boros@mongodb.com', 'username': 'borosaurus'}

Message: SERVER-65270 Fix bug related to queries on large documents not respecting the sort option
Branch: master
https://github.com/mongodb/mongo/commit/5b5b505f0db2e145f40bde4e2ac2d5c56bc0b263

Comment by Ian Boros [ 05/Apr/22 ]

I think the fix is here is pretty straightforward. I'll see if I run into anything else later tonight.

Generated at Thu Feb 08 06:02:16 UTC 2024 using Jira 9.7.1#970001-sha1:2222b88b221c4928ef0de3161136cc90c8356a66.