Uploaded image for project: 'Core Server'
  1. Core Server
  2. SERVER-24027

The planner does not consider reversing index scan direction in order to obtain a SORT_MERGE plan

    XMLWordPrintable

    Details

    • Type: Bug
    • Status: Closed
    • Priority: Major - P3
    • Resolution: Fixed
    • Affects Version/s: 3.2.3
    • Fix Version/s: 3.4.2, 3.5.2
    • Component/s: Querying
    • Labels:
    • Backwards Compatibility:
      Fully Compatible
    • Operating System:
      ALL
    • Backport Requested:
      v3.4, v3.2
    • Steps To Reproduce:
      Hide

      Ascending case:

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

      descending case:

      db.events.find(
        { "$or" :
          [
            { "time" : { "$lt" : ISODate("2016-03-14T05:49:47.198Z")}},
            { "time" : ISODate("2016-03-14T05:49:47.198Z") , "_id" : { "$lt" : { "$uuid" : "a87276c-4986-4b9f-aacb-eedfa2a4b2ed"}}}
          ]
        }
      ).sort({ "time" : -1 , "_id" : -1}).limit(550).explain()
      

      In the "ascending case" both $OR clauses are handles with ascending index-based sorts, and a SORT-MERGE.

      In the descending case, one clause gets a descending range scan and the other an ascending range scan. The results are then passed to an in-memory sort.

      Providing a descending index and hinting it provides the "descending case" with a plan that is a mirror image to the "ascending case", as one would hope.

      Show
      Ascending case: db.events.find( { "$or" : [ { "time" : { "$gt" : ISODate("2016-02-13T21:59:22.141Z")}} , { "time" : ISODate("2016-02-13T21:59:22.141Z") , "_id" : { "$gt" : { "$uuid" : "213a4dd4-2ad8-4fa4-80be-6a3f20562e57"}}} ] } ).sort({ "time" : 1 , "_id" : 1}).limit(550).explain() descending case: db.events.find( { "$or" : [ { "time" : { "$lt" : ISODate("2016-03-14T05:49:47.198Z")}}, { "time" : ISODate("2016-03-14T05:49:47.198Z") , "_id" : { "$lt" : { "$uuid" : "a87276c-4986-4b9f-aacb-eedfa2a4b2ed"}}} ] } ).sort({ "time" : -1 , "_id" : -1}).limit(550).explain() In the "ascending case" both $OR clauses are handles with ascending index-based sorts, and a SORT-MERGE. In the descending case, one clause gets a descending range scan and the other an ascending range scan. The results are then passed to an in-memory sort. Providing a descending index and hinting it provides the "descending case" with a plan that is a mirror image to the "ascending case", as one would hope.
    • Sprint:
      Query 2017-01-23

      Description

      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.

        Attachments

          Issue Links

            Activity

              People

              • Votes:
                1 Vote for this issue
                Watchers:
                14 Start watching this issue

                Dates

                • Created:
                  Updated:
                  Resolved: