[SERVER-24027] The planner does not consider reversing index scan direction in order to obtain a SORT_MERGE plan Created: 03/May/16  Updated: 09/Oct/17  Resolved: 13/Jan/17

Status: Closed
Project: Core Server
Component/s: Querying
Affects Version/s: 3.2.3
Fix Version/s: 3.4.2, 3.5.2

Type: Bug Priority: Major - P3
Reporter: Mark Brinsmead Assignee: Tess Avitabile (Inactive)
Resolution: Done Votes: 1
Labels: neweng
Remaining Estimate: Not Specified
Time Spent: Not Specified
Original Estimate: Not Specified

Issue Links:
Backports
Related
is related to SERVER-31280 Implementing paging using range queri... Closed
Backwards Compatibility: Fully Compatible
Operating System: ALL
Backport Requested:
v3.4, v3.2
Steps To Reproduce:

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
Participants:

 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.



 Comments   
Comment by Alessandro Gherardi [ 21/Jan/17 ]

Thanks!

Comment by Githook User [ 20/Jan/17 ]

Author:

{u'username': u'tessavitabile', u'name': u'Tess Avitabile', u'email': u'tess.avitabile@mongodb.com'}

Message: SERVER-24027 Planner should consider reversing index scan direction in order to obtain a SORT_MERGE plan
Branch: v3.4
https://github.com/mongodb/mongo/commit/e03e7cc9b087f0a95d519b767c1491cfb23f4c74

Comment by David Storch [ 19/Jan/17 ]

Hi agherardi,

After review of the backport requests, we have decided that we can safely backport this change to 3.4 but not to 3.2. This should become available in one of the next patch releases of the 3.4.x series. If you are on 3.2 and require this fix, you will need to upgrade.

Best,
Dave

Comment by David Storch [ 17/Jan/17 ]

Hi agherardi,

A backport may not be possible, especially to the v3.2 branch. However, I will put this ticket in line to go through our normal backport approval process for both the v3.2 and v3.4 branches in order to determine whether the fix is possible/admissible in these branches.

Best,
Dave

Comment by Alessandro Gherardi [ 17/Jan/17 ]

Thank you for fixing this issue.

Would you consider back-porting the patch to 3.2.X?

Comment by Githook User [ 13/Jan/17 ]

Author:

{u'username': u'tessavitabile', u'name': u'Tess Avitabile', u'email': u'tess.avitabile@mongodb.com'}

Message: SERVER-24027 Planner should consider reversing index scan direction in order to obtain a SORT_MERGE plan
Branch: master
https://github.com/mongodb/mongo/commit/be58d599fd9df085c94be3c22051f04aa3df5c13

Comment by David Storch [ 20/Dec/16 ]

Hi agherardi, this ticket has a fixVersion of "planned but not scheduled", which means we intend to implement the improvement but currently have no timeframe for this work. Looking at its position in our backlog, I would say there is some chance that this will be released as part of version 3.6.

Comment by Alessandro Gherardi [ 20/Dec/16 ]

Hello - Any updates on this issue? Thanks.

Comment by Nate Smith [ 14/Jul/16 ]

Mark, thank you for the excellent description of the issue. We've also run into this issue using Mongo 3.0.11 and were expecting a single index to be able to support both forward and backward direction scans, but find that using an $or limits us to a forward direction on the index currently.

Comment by David Storch [ 04/May/16 ]

Simpler repro:

db.c.drop();
db.c.ensureIndex({a: 1});
db.c.find({$or: [{a: 1, b: 1}, {a: {$lt: 0}}]}).sort({a: -1}).explain().queryPlanner.winningPlan;

Comment by David Storch [ 04/May/16 ]

Hi mark.brinsmead,

Thanks for the issue report. I looked into the cause of this behavior and found that this is indeed a missing optimization in the query planner. The code with the defect dates to version 2.6.0, so I believe this affects all versions of 2.6, 3.0, and 3.2. There is even a comment in the planner with a TODO about this:

https://github.com/mongodb/mongo/blob/r3.3.5/src/mongo/db/query/planner_access.cpp#L1110-L1112

I will move this ticket onto our team's backlog in a Needs Triage state, and we will review together at our next triage meeting.

Best,
Dave

Generated at Thu Feb 08 04:05:10 UTC 2024 using Jira 9.7.1#970001-sha1:2222b88b221c4928ef0de3161136cc90c8356a66.