-
Type:
Bug
-
Resolution: Fixed
-
Priority:
Blocker - P1
-
Affects Version/s: None
-
Component/s: None
-
Fully Compatible
-
ALL
-
v5.3
-
QE 2022-04-18
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()));
})();