How does sorting work with `$or` and `$in` queries in MongoDB?

Question

This is a follow-up to this question - see that for context.

This question concerns a couple of special cases of the linked question - namely how sorting in MongoDB works when using $in or $or operators, and how to ensure use of an index for sorting vs. an in-memory sort.

$in:

For example, assume we have a collection where the document structure is

{a: XXX, b: XXX}

... and we have a compound index on a and b in that order and want to run the query

{a: {$in: [4, 6, 2, 1, 3, 10]}, b: {$gt: 1, $lt: 6}}

How would the sort proceed if it was on a or b? $in is an equality operator of sorts, but it seems to me that a sort on b with an index is impossible even so. A sort on a using an index is only possible if the $in value array is sorted first, I think - but I don't know if MongoDB does this.

$or:

Since $or queries, IIUC, are processed as multiple queries and can presumably use their respective indexes for sorts, do the sorted results get merged somehow or does $or force an in-memory sort of all the results? If the former, what is the time complexity of this process?

Answer 1

Note: This answer is based on MongoDB 3.2.4.

It is worthwhile to discover the use of explain() in MongoDB. The explain() output of a query (e.g. db.collection.explain().find(...)) allows you to check which index is used in a query, and using db.collection.explain('executionStats') will also show you whether the query succeeds or fails due to in-memory SORT limitation.

$in

A $in query can be thought of as a series of equality queries. For example, {a: {$in: [1,3,5]}} could be thought of as {a:1}, {a:3}, {a:5}. MongoDB will sort the $in array before proceeding with the query, so that {$in: [3,5,1]} is no different to {$in: [1,3,5]}.

Let's assume the collection has an index of

{a:1, b:1}

• Sorting by a

    db.coll.find({a: {$in: [1,3,5]}}).sort({a:1})
  

  MongoDB will be able to use the {a:1,b:1} index, since this query can be thought of as a union of {a:1}, {a:3}, {a:5} queries. Sorting by {a:1} allows the use of index prefix, so MongoDB does not need to perform an in-memory sort.

  The same situation also applies to the query:

    db.coll.find({a: {$in: [1,3,5]} ,b:{$gte:1, $lt:2}}).sort({a:1})
  

  since sort({a:1}) also uses the index prefix (a in this case), an in-memory SORT stage is therefore not required.

• Sorting by b

  This is a more interesting case compared to sorting by a. For example:

    db.coll.find({a: {$in: [1,3,5]}}).sort({b:1})
  

  The explain() output of this query will have a stage called SORT_MERGE. Remember that the find() portion of the query can be thought of as {a:1}, {a:3}, {a:5}.

  The query db.coll.find({a:1}).sort({b:1}) does not need to have an in-memory SORT stage due to the nature of the {a:1,b:1} index: that is, MongoDB can simply walk the (sorted) index and return documents sorted by b after satisfying the equality parameter on a. E.g., for each a, there are many b which are already sorted by b due to the index.

  Using $in, the overall query can be thought of as:

  • db.coll.find({a:1}).sort({b:1})
  • db.coll.find({a:3}).sort({b:1})
  • db.coll.find({a:5}).sort({b:1})
  • Take the individual query results above, and perform a merge using the value of b. The query does not need an in-memory sort stage because the individual query results are already sorted by b. MongoDB just need to merge the (already sorted) sub-query results into a single result.

  Similarly, the query

    db.coll.find({a: {$in: [1,3,5]} ,b:{$gte:1, $lt:2}}).sort({b:1})
  

  also uses a SORT_MERGE stage and is very similar to the query above. The difference is that the individual queries output documents based on a range of b (instead of every b) for each a (which will be sorted by b due to the index {a:1,b:1}). Hence, the query does not need an in-memory sort stage.

$or

For an $or query to use an index, every clause in the $or expression must have an index associated with it. If this requirement is satisfied, it is possible for the query to employ a SORT_MERGE stage just like an $in query. For example:

db.coll.explain().find({$or:[{a:1},{a:3},{a:5}]}).sort({b:1})

will have an almost identical query plan, index use, and SORT_MERGE stage as in the $in example above. Essentially, the query can be thought as:

• db.coll.find({a:1}).sort({b:1})
• db.coll.find({a:3}).sort({b:1})
• db.coll.find({a:5}).sort({b:1})
• Take the individual query results above, and perform a merge using the value of b.

just like the $in example before.

However, this query:

db.coll.explain().find({$or:[{a:1},{b:1}]}).sort({b:1})

cannot use any index (since we do not have the {b:1} index). This query will result in a collection scan, and consequently will have an in-memory sort stage since no index is used.

If, however, we create the index {b:1}, the query will proceed like:

• db.coll.find({a:1}).sort({b:1})
• db.coll.find({b:1}).sort({b:1})
• Take the individual query results above, and perform a merge using the value of b (which is already sorted at both sub-queries, due to the indexes {a:1,b:1} and {b:1}).

and MongoDB will combine the results of {a:1} and {b:1} queries and perform a merge on the results. The merging process is linear time, e.g. O(n).

In conclusion, in a $or query, every term must have an index, including the sort() stage. Otherwise, MongoDB will will have to perform an in-memory sort.