[SERVER-13618] Optimization for sorted $in queries not applied to reverse sort order Created: 16/Apr/14  Updated: 11/Jul/16  Resolved: 17/Apr/14

Status: Closed
Project: Core Server
Component/s: Querying
Affects Version/s: 2.6.0
Fix Version/s: 2.6.1, 2.7.0

Type: Bug Priority: Minor - P4
Reporter: David Storch Assignee: David Storch
Resolution: Done Votes: 0
Labels: None
Remaining Estimate: Not Specified
Time Spent: Not Specified
Original Estimate: Not Specified

Issue Links:
Related
is related to SERVER-13611 Missing sort order for compound index... Closed
is related to SERVER-1205 $or sort does not use index ranges ex... Closed
Operating System: ALL
Backport Completed:
Participants:

 Description   
Issue Status as of April 21, 2014

ISSUE SUMMARY
Queries using $in and .sort() can be handled efficiently by "exploding" the index bounds of the $in predicates and creating several child index scans. In the case where the sort order is reversed from the index spec the query planner adds a blocking sort stage at the end, which impacts the performance and can be avoided.

USER IMPACT
If users rely on these kinds of queries with $in and sort, they can experience slower than expected query results in some cases. If the size of returned documents exceeds the limit of 32MB, the query fails with an error.

WORKAROUNDS
If only the reverse sort order is required, the index can be re-created with the last field order reversed. If both sort orders are required, no workaround is known.

RESOLUTION
The query planner now correctly detects the reverse sort order and does not sort the documents in memory anymore.

AFFECTED VERSIONS
Version 2.6.0 is affected by this bug.

PATCHES
The patch is included in the 2.6.1 production release.

Original description

Say we have index {a: 1, b: 1, c: 1} and we issue the following query:

t.find({a: {$in: [1, 2]}, b: {$in: [3, 4]}}).sort({c: 1});

The explode for scans hack (see SERVER-1205), is able to avoid a blocking sort stage for this query by merge sorting over four child index scans with the following bounds:

  • a: [[1, 1]], b: [[3, 3]]
  • a: [[1, 1]], b: [[4, 4]]
  • a: [[2, 2]], b: [[3, 3]]
  • a: [[2, 2]], b: [[4, 4]]

We should be able to do the same thing for query

t.find({a: {$in: [1, 2]}, b: {$in: [3, 4]}}).sort({c: -1});

simply by reversing the direction of the index scans. However, explodeForSort() fails and we end up creating a plan with a blocking sort for the query with .sort({c: -1}).



 Comments   
Comment by Githook User [ 17/Apr/14 ]

Author:

{u'username': u'dstorch', u'name': u'David Storch', u'email': u'david.storch@10gen.com'}

Message: SERVER-13618 explode for sort tries reversing index scan direction
(cherry picked from commit ce52f313ca52759d606886641f44541bd7baf5bd)
Branch: v2.6
https://github.com/mongodb/mongo/commit/eeef3c3ded2d8d55345af8b11041bafae8783958

Comment by Githook User [ 17/Apr/14 ]

Author:

{u'username': u'dstorch', u'name': u'David Storch', u'email': u'david.storch@10gen.com'}

Message: SERVER-13618 explode for sort tries reversing index scan direction
Branch: master
https://github.com/mongodb/mongo/commit/ce52f313ca52759d606886641f44541bd7baf5bd

Generated at Thu Feb 08 03:32:18 UTC 2024 using Jira 9.7.1#970001-sha1:2222b88b221c4928ef0de3161136cc90c8356a66.