Pagination queries with compound keys are optimized well for ascending sorts, but not for descending sorts.

A workaround exists, but it requires a hint and the creation of both ascending and descending indexes.

The issue

You need to do "pagination" queries, with both an ascending case, and a descending case. MongoDB 3.2.3 is doing a good job of optimizing the ascending case to avoid non-blocking sorts (that is, to "sort" using an index), but it is failing to do the same in the descending case, even when both ascending and descending indexes are provided.

The predicates in each case are mirror images:

Ascending Case

OR  ( time > some_value,
      AND  ( time = some_value, _id > another_value )
    )

Descending Case

OR  ( time < some_value,
      AND  ( time = some_value, _id < another_value )
    )

These predicates provide the starting point for a "page" of data – a limit(xxx) clause on the query provides the end point.

The trouble seems to be that the optimizer is handling the OR'ed conditions independently. In both cases, the optimizer appears to be taking the conditions
(time < some_value) and (time > some_value) and performing a forward range scan on the ascending index (time: 1, _id:1}.

In the ascending case, this is okay. All steps in the plan read data from the index ordered in ascending order of time and _id, and the results can then be merged with a SORT_MERGE step.

In the descending case, though, data from one step is sorted in ascending order and in another it is sorted in descending order. It is not possible to use SORT_MERGE to merge these, so the entire dataset must be read and then (re-)sorted.

Workaround

To avoid this unwanted behavior in the descending case, I provided both ascending and descending indexes (that is, I added an index on {time: -1, id: -1} ) and then specified a hint to make the optimizer use the descending index in the descending case of the query. With the descending index and the hint,the optimizer then uses the index to produce _all subsets of data in descending order, so then can then be efficiently merged with a SORT_MERGE step

db.events.createIndex({time: -1, _id: -1});
db.events.find(
{ "$or" : [ { "time" : { "$lt" : ISODate("2016-02-13T21:59:22.141Z")}} , 
        { "time" : ISODate("2016-02-13T21:59:22.141Z") , "_id" : { "$lt" : { "$uuid" : "213a4dd4-2ad8-4fa4-80be-6a3f20562e57"}}}
    ]})
.sort({ "time" : -1 , "_id" : -1}).limit(550)
.hint("time_-1__id_-1")
.explain()

If you want to perform your pagination queries in both ascending and descending order, you will need to provide both ascending and descending indexes, and you will also need to hint the descending index in the descending use-case.