[SERVER-13831] Find with $gte/$gt/$lte/$lt on Date field and sorting on another field leads to unnecessary in-memory sort without using index Created: 05/May/14  Updated: 20/Mar/15  Resolved: 20/Mar/15

Status: Closed
Project: Core Server
Component/s: Querying
Affects Version/s: 2.6.0
Fix Version/s: None

Type: Bug Priority: Major - P3
Reporter: Rudi Wijaya Assignee: J Rassi
Resolution: Done Votes: 0
Labels: None
Remaining Estimate: Not Specified
Time Spent: Not Specified
Original Estimate: Not Specified

Issue Links:
Related
related to SERVER-12923 Plan ranking is bad for plans with bl... Backlog
Operating System: ALL
Participants:

 Description   

MongoDB 2.6.0 fails to use any index when range querying field A and sorting field B. Both fields are indexed. Both fields are Date.

Given a compound index

{voidTime: 1, movementTime: 1}

all these 4 queries should be able to use this index:

1. db.stockReservation.find({ "voidTime" : {$in: [ISODate('2014-05-05T01:22:12.580Z'), ISODate('2014-05-05T01:29:28.528Z'), ISODate('2014-05-05T01:30:55.111Z')]}}) .explain()
2. db.stockReservation.find({ "voidTime" : {$in: [ISODate('2014-05-05T01:22:12.580Z'), ISODate('2014-05-05T01:29:28.528Z'), ISODate('2014-05-05T01:30:55.111Z')]}}) .sort({movementTime: 1}).explain()
3. db.stockReservation.find({ "voidTime" : { "$gte" : ISODate("2014-05-04T17:00:00.000Z") , "$lt" : ISODate("2014-05-05T10:20:13.894Z")}}) .explain()
4. db.stockReservation.find({ "voidTime" : { "$gte" : ISODate("2014-05-04T17:00:00.000Z") , "$lt" : ISODate("2014-05-05T10:20:13.894Z")}}) .sort({movementTime: 1}) .explain()

However MongoDB 2.6.0 fails to use index when sorting for case #4.

This did not happen to MongoDB 2.4.x. This is similar to SERVER-13611. However SERVER-13611 also happens to a "simple" query, while this bug only happens for range queries (i.e. $gte/$gt/$lte/$lt).

Explain results :

bippo:PRIMARY> db.stockReservation.ensureIndex({voidTime: 1, movementTime:1})
{ "numIndexesBefore" : 23, "note" : "all indexes already exist", "ok" : 1 }
bippo:PRIMARY> db.stockReservation.find({ "voidTime" : {$in: [ISODate('2014-05-05T01:22:12.580Z'), ISODate('2014-05-05T01:29:28.528Z'), ISODate('2014-05-05T01:30:55.111Z')]}}) .explain()
{
        "cursor" : "BtreeCursor voidTime_1_movementTime_1",
        "isMultiKey" : false,
        "n" : 3,
        "nscannedObjects" : 3,
        "nscanned" : 3,
        "nscannedObjectsAllPlans" : 6,
        "nscannedAllPlans" : 6,
        "scanAndOrder" : false,
        "indexOnly" : false,
        "nYields" : 0,
        "nChunkSkips" : 0,
        "millis" : 0,
        "indexBounds" : {
                "voidTime" : [
                        [
                                ISODate("2014-05-05T01:22:12.580Z"),
                                ISODate("2014-05-05T01:22:12.580Z")
                        ],
                        [
                                ISODate("2014-05-05T01:29:28.528Z"),
                                ISODate("2014-05-05T01:29:28.528Z")
                        ],
                        [
                                ISODate("2014-05-05T01:30:55.111Z"),
                                ISODate("2014-05-05T01:30:55.111Z")
                        ]
                ],
                "movementTime" : [
                        [
                                {
                                        "$minElement" : 1
                                },
                                {
                                        "$maxElement" : 1
                                }
                        ]
                ]
        },
        "filterSet" : false
}
 
bippo:PRIMARY> db.stockReservation.find({ "voidTime" : {$in: [ISODate('2014-05-05T01:22:12.580Z'), ISODate('2014-05-05T01:29:28.528Z'), ISODate('2014-05-05T01:30:55.111Z')]}}) .sort({movementTime: 1}).explain()
{
        "clauses" : [
                {
                        "cursor" : "BtreeCursor voidTime_1_movementTime_1",
                        "isMultiKey" : false,
                        "n" : 1,
                        "nscannedObjects" : 1,
                        "nscanned" : 1,
                        "scanAndOrder" : false,
                        "indexOnly" : false,
                        "nChunkSkips" : 0,
                        "indexBounds" : {
                                "voidTime" : [
                                        [
                                                ISODate("2014-05-05T01:22:12.580Z"),
                                                ISODate("2014-05-05T01:22:12.580Z")
                                        ]
                                ],
                                "movementTime" : [
                                        [
                                                {
                                                        "$minElement" : 1
                                                },
                                                {
                                                        "$maxElement" : 1
                                                }
                                        ]
                                ]
                        }
                },
                {
                        "cursor" : "BtreeCursor voidTime_1_movementTime_1",
                        "isMultiKey" : false,
                        "n" : 1,
                        "nscannedObjects" : 1,
                        "nscanned" : 1,
                        "scanAndOrder" : false,
                        "indexOnly" : false,
                        "nChunkSkips" : 0,
                        "indexBounds" : {
                                "voidTime" : [
                                        [
                                                ISODate("2014-05-05T01:29:28.528Z"),
                                                ISODate("2014-05-05T01:29:28.528Z")
                                        ]
                                ],
                                "movementTime" : [
                                        [
                                                {
                                                        "$minElement" : 1
                                                },
                                                {
                                                        "$maxElement" : 1
                                                }
                                        ]
                                ]
                        }
                },
                {
                        "cursor" : "BtreeCursor voidTime_1_movementTime_1",
                        "isMultiKey" : false,
                        "n" : 1,
                        "nscannedObjects" : 1,
                        "nscanned" : 1,
                        "scanAndOrder" : false,
                        "indexOnly" : false,
                        "nChunkSkips" : 0,
                        "indexBounds" : {
                                "voidTime" : [
                                        [
                                                ISODate("2014-05-05T01:30:55.111Z"),
                                                ISODate("2014-05-05T01:30:55.111Z")
                                        ]
                                ],
                                "movementTime" : [
                                        [
                                                {
                                                        "$minElement" : 1
                                                },
                                                {
                                                        "$maxElement" : 1
                                                }
                                        ]
                                ]
                        }
                }
        ],
        "cursor" : "QueryOptimizerCursor",
        "n" : 3,
        "nscannedObjects" : 3,
        "nscanned" : 3,
        "nscannedObjectsAllPlans" : 6,
        "nscannedAllPlans" : 6,
        "scanAndOrder" : false,
        "nYields" : 0,
        "nChunkSkips" : 0,
        "millis" : 0,
        "filterSet" : false
}
 
bippo:PRIMARY> db.stockReservation.find({ "voidTime" : { "$gte" : ISODate("2014-05-04T17:00:00.000Z") , "$lt" : ISODate("2014-05-05T10:20:13.894Z")}}) .explain()
{
        "cursor" : "BtreeCursor voidTime_1_movementTime_1",
        "isMultiKey" : false,
        "n" : 342,
        "nscannedObjects" : 342,
        "nscanned" : 342,
        "nscannedObjectsAllPlans" : 443,
        "nscannedAllPlans" : 444,
        "scanAndOrder" : false,
        "indexOnly" : false,
        "nYields" : 2,
        "nChunkSkips" : 0,
        "millis" : 1,
        "indexBounds" : {
                "voidTime" : [
                        [
                                ISODate("2014-05-04T17:00:00Z"),
                                ISODate("2014-05-05T10:20:13.894Z")
                        ]
                ],
                "movementTime" : [
                        [
                                {
                                        "$minElement" : 1
                                },
                                {
                                        "$maxElement" : 1
                                }
                        ]
                ]
        },
        "filterSet" : false
}
 
bippo:PRIMARY> db.stockReservation.find({ "voidTime" : { "$gte" : ISODate("2014-05-04T17:00:00.000Z") , "$lt" : ISODate("2014-05-05T10:20:13.894Z")}}) .sort({movementTime: 1}) .explain()
{
        "cursor" : "BtreeCursor movementTime_1",
        "isMultiKey" : false,
        "n" : 342,
        "nscannedObjects" : 43029,
        "nscanned" : 43029,
        "nscannedObjectsAllPlans" : 43674,
        "nscannedAllPlans" : 43675,
        "scanAndOrder" : false,
        "indexOnly" : false,
        "nYields" : 340,
        "nChunkSkips" : 0,
        "millis" : 119,
        "indexBounds" : {
                "movementTime" : [
                        [
                                {
                                        "$minElement" : 1
                                },
                                {
                                        "$maxElement" : 1
                                }
                        ]
                ]
        },
        "filterSet" : false
}
bippo:PRIMARY> 

With data too big, this will give error:
"Runner error: Overflow sort stage buffered data usage of X bytes exceeds internal limit of 33554432 bytes"

But even when error not occurred, the query will be very inefficient.



 Comments   
Comment by Ramon Fernandez Marina [ 20/Mar/15 ]

rudi, in addition to the comment above, you may want to check the documentation on when can an index be used to provide a sort. You may also want to watch SERVER-13197 which is opened to improve the computation of index bounds in cases like the ones you describe.

Since there's no evidence of a bug in the server I'm going to resolve this ticket. For MongoDB-related support discussion please post on the mongodb-user group or Stack Overflow with the mongodb tag, where your question will reach a larger audience. A question like this involving more discussion would be best posted on the mongodb-user group.

Regards,
Ramón.

Comment by Hendy Irawan [ 08/May/14 ]

rassi@10gen.com what do you think about the exhibits I mentioned in the latest comments ?

Comment by Hendy Irawan [ 06/May/14 ]

Tested with 2.6.1, same (incorrect) behavior as 2.6.0: (no bounds even I've used hint)

> db.stockReservation.find({ "voidTime" : { "$gte" : ISODate("2014-05-04T17:00:00.000Z") , "$lt" : ISODate("2014-05-05T10:20:13.894Z")}}) .sort({movementTime: 1}) ._addSpecial('$hint', 'movementTime_1_voidTime_1').explain()
{
        "cursor" : "BtreeCursor movementTime_1_voidTime_1",
        "isMultiKey" : false,
        "n" : 342,
        "nscannedObjects" : 43043,
        "nscanned" : 43043,
        "nscannedObjectsAllPlans" : 43043,
        "nscannedAllPlans" : 43043,
        "scanAndOrder" : false,
        "indexOnly" : false,
        "nYields" : 12948,
        "nChunkSkips" : 0,
        "millis" : 12407,
        "indexBounds" : {
                "movementTime" : [
                        [
                                {
                                        "$minElement" : 1
                                },
                                {
                                        "$maxElement" : 1
                                }
                        ]
                ],
                "voidTime" : [
                        [
                                {
                                        "$minElement" : 1
                                },
                                {
                                        "$maxElement" : 1
                                }
                        ]
                ]
        },
        "server" : "hendy.dev:27017",
        "filterSet" : false
}
 
> db.version()
2.6.1

Comment by Hendy Irawan [ 06/May/14 ]

I think I've found it this time.

Test case with explicit compound index :

> db.stockReservation.ensureIndex({movementTime:1, voidTime:1})
> db.stockReservation.find({ "voidTime" : { "$gte" : ISODate("2014-05-04T17:00:00.000Z") , "$lt" : ISODate("2014-05-05T10:20:13.894Z")}}) .sort({movementTime: 1}) ._addSpecial('$hint', 'movementTime_1_voidTime_1').explain()

MongoDB 2.6.0 :

> db.stockReservation.find({ "voidTime" : { "$gte" : ISODate("2014-05-04T17:00:00.000Z") , "$lt" : ISODate("2014-05-05T10:20:13.894Z")}}) .sort({movementTime: 1}) ._addSpecial('$hint', 'movementTime_1_voidTime_1').explain()
{
        "cursor" : "BtreeCursor movementTime_1_voidTime_1",
        "isMultiKey" : false,
        "n" : 342,
        "nscannedObjects" : 43043,
        "nscanned" : 43043,
        "nscannedObjectsAllPlans" : 43043,
        "nscannedAllPlans" : 43043,
        "scanAndOrder" : false,
        "indexOnly" : false,
        "nYields" : 355,
        "nChunkSkips" : 0,
        "millis" : 3480,
        "indexBounds" : {
                "movementTime" : [
                        [
                                {
                                        "$minElement" : 1
                                },
                                {
                                        "$maxElement" : 1
                                }
                        ]
                ],
                "voidTime" : [
                        [
                                {
                                        "$minElement" : 1
                                },
                                {
                                        "$maxElement" : 1
                                }
                        ]
                ]
        },
        "server" : "hendy.dev:27017",
        "filterSet" : false
}

MongoDB 2.4.10 :

> db.stockReservation.find({ "voidTime" : { "$gte" : ISODate("2014-05-04T17:00:00.000Z") , "$lt" : ISODate("2014-05-05T10:20:13.894Z")}}) .sort({movementTime: 1}) ._addSpecial('$hint', 'movementTime_1_voidTime_1').explain()
{
        "cursor" : "BtreeCursor movementTime_1_voidTime_1",
        "isMultiKey" : false,
        "n" : 342,
        "nscannedObjects" : 342,
        "nscanned" : 41122,
        "nscannedObjectsAllPlans" : 342,
        "nscannedAllPlans" : 41122,
        "scanAndOrder" : false,
        "indexOnly" : false,
        "nYields" : 0,
        "nChunkSkips" : 0,
        "millis" : 54,
        "indexBounds" : {
                "movementTime" : [
                        [
                                {
                                        "$minElement" : 1
                                },
                                {
                                        "$maxElement" : 1
                                }
                        ]
                ],
                "voidTime" : [
                        [
                                ISODate("2014-05-04T17:00:00Z"),
                                ISODate("2014-05-05T10:20:13.894Z")
                        ]
                ]
        },
        "server" : "hendy.dev:27018"
}

Note that both versions use the exact same index, however 2.4.10 bounds on the voidTime part while 2.6.0 doesn't use the bounds, yielding significant difference for nscannedObjects.

Comment by Hendy Irawan [ 06/May/14 ]

Thank you so much rassi@10gen.com for the detailed explanation.

However, MongoDB 2.6.0's approach leads to the ""Runner error: Overflow sort stage buffered data usage of X bytes exceeds internal limit of 33554432 bytes" with the 2.7 GB collection, while MongoDB 2.4.10's choice is working fine.

So I'm rather curious here, why would MongoDB 2.6.0 choose a query plan that it "knows" will exceed its sort buffer (since it knows the size of the index), while the other query plan will fit the memory limit just fine. Or is it by design?

Can you suggest what hint I should use in order to retain the query plan (as chosen by MongoDB 2.4.10) in this case?

Or alternatively, what index should I create in order to do that query as efficiently (both memory & speed) as possible on the 2.7 GB collection? Adding a compound index on both fields (matching the direction of the sort) doesn't seem to help

Comment by J Rassi [ 05/May/14 ]

This is expected behavior.

Your query is of the form:

find({creationTime: {$lt: ...}}).sort({movementTime:1})

You have two indexes that are relevant to this query:

{creationTime: -1}
{movementTime: -1}

Two query plans are considered:

  1. Perform an unbounded index scan on the "movementTime" index (which already provides the requested sort order), and discard results that don't match the "creationTime" predicate.
  2. Perform a bounded index scan on the "creationTime" index, and order the results based an in-memory sort on the "movementTime" field.

You can see both of these query plans with explain(true):

> db.returnToVendorShipment.find({ "creationTime" : { "$lt" : ISODate()}}).sort({movementTime: 1}).explain(true).allPlans
[
	{
		"cursor" : "BtreeCursor movementTime_-1 reverse", // note scanAndOrder is false, note indexBounds is unbounded
		"isMultiKey" : false,
		"n" : 84,
		"nscannedObjects" : 84,
		"nscanned" : 84,
		"scanAndOrder" : false,
		"indexOnly" : false,
		"nChunkSkips" : 0,
		"indexBounds" : {
			"movementTime" : [
				[
					{
						"$minElement" : 1
					},
					{
						"$maxElement" : 1
					}
				]
			]
		}
	},
	{
		"cursor" : "BtreeCursor creationTime_-1", // note scanAndOrder is true, note indexBounds is bounded
		"isMultiKey" : false,
		"n" : 0,
		"nscannedObjects" : 84,
		"nscanned" : 84,
		"scanAndOrder" : true,
		"indexOnly" : false,
		"nChunkSkips" : 0,
		"indexBounds" : {
			"creationTime" : [
				[
					ISODate("2014-05-05T18:36:24.714Z"),
					true
				]
			]
		}
	}
]

Neither of these plans is inherently superior to the other; which query plan is picked depends on the data distribution:

  • Suppose no documents match the "creationTime" predicate. Plan #1 will scan all entries in the "movementTime" index. Plan #2 will scan zero entries in the "creationTime" index, and perform an in-memory sort on zero documents. In this case, plan #2 is better.
  • Suppose all documents match the "creationTime" predicate. Plan #1 will scan all entries in the "movementTime" index. Plan #2 will scan all entries in the "creationTime" index and perform an in-memory sort on the full collection. In this case, plan #1 is better.

It follows that the "best plan" depends on the number of documents that match the "creationTime" predicate and the number of documents in the collection. Your two queries differ in how many documents match the predicate, so it's reasonable that one of them is assigned plan #1 and the other one is assigned plan #2. MongoDB chooses a winning query plan (basically) by running all candidate plans for a "trial period", and then choosing the plan that finishes first. This method is not foolproof, however, for a number of reasons (to give one example: since plans are cached in a normalized form in which predicate values are removed, it's possible that a highly-selective predicate generates a winning query plan that later performs sub-optimally when it is invoked for use on a not very selective predicate of the same normalized form). In addition, note that plan #1 is heavy on I/O and light on CPU, and plan #2 is light on I/O and heavy on CPU; the tradeoff between I/O resources and CPU resources is specific to the database's working conditions (and subjective, at that). The MongoDB 2.6 release included significant work on the query subsystem, which changed the exact set of circumstances under which one of these plans is chosen over the other; the difference you're seeing between MongoDB 2.4 and MongoDB 2.6 is likely a result of this work. In addition, note that SERVER-12923 (linked) is tracking an outstanding issue where plans that use an in-memory sort are chosen more rarely than they should be; I suggest watching that ticket for updates.

The hint() functionality exists for the circumstances under which the query engine picks a query plan that doesn't work well for your use case. I suggest adding a hint to your query to fix the issue with your application, which will force the query engine to use the index of your choosing.

Comment by Hendy Irawan [ 05/May/14 ]

I've managed to reproduce this issue on a much smaller collection containing 84 documents, and the bug does not occur with 2.4.10 :

test case:

db.version()
 
db.returnToVendorShipment.count()
// NON-buggy query
db.returnToVendorShipment.find({ "creationTime" : { "$lt" : ISODate("2014-02-13T06:40:02.000Z")}}) .sort({movementTime: 1}) .explain()
// buggy query
db.returnToVendorShipment.find({ "creationTime" : { "$lt" : ISODate("2014-02-13T06:40:03.000Z")}}) .sort({movementTime: 1}) .explain()

Note that the visible difference between NON-buggy query vs trigger query is that the NON-buggy query returns 40 documents while buggy query returns 41 documents.

MongoDB 2.6.0 results

Notice that MongoDB 2.6.0 unable to use proper indexBounds for the buggy query (41 documents)

bippo:PRIMARY> db.version()
2.6.0
 
bippo:PRIMARY> db.returnToVendorShipment.count()
84
 
bippo:PRIMARY> db.returnToVendorShipment.find({ "creationTime" : { "$lt" : ISODate("2014-02-13T06:40:02.000Z")}}) .sort({movementTime: 1}) .explain()
{
        "cursor" : "BtreeCursor creationTime_-1",
        "isMultiKey" : false,
        "n" : 40,
        "nscannedObjects" : 40,
        "nscanned" : 40,
        "nscannedObjectsAllPlans" : 123,
        "nscannedAllPlans" : 124,
        "scanAndOrder" : true,
        "indexOnly" : false,
        "nYields" : 1,
        "nChunkSkips" : 0,
        "millis" : 0,
        "indexBounds" : {
                "creationTime" : [
                        [
                                ISODate("2014-02-13T06:40:02Z"),
                                true
                        ]
                ]
        },
        "filterSet" : false
}
 
bippo:PRIMARY> db.returnToVendorShipment.find({ "creationTime" : { "$lt" : ISODate("2014-02-13T06:40:03.000Z")}}) .sort({movementTime: 1}) .explain()
{
        "cursor" : "BtreeCursor movementTime_-1 reverse",
        "isMultiKey" : false,
        "n" : 41,
        "nscannedObjects" : 84,
        "nscanned" : 84,
        "nscannedObjectsAllPlans" : 125,
        "nscannedAllPlans" : 125,
        "scanAndOrder" : false,
        "indexOnly" : false,
        "nYields" : 1,
        "nChunkSkips" : 0,
        "millis" : 0,
        "indexBounds" : {
                "movementTime" : [
                        [
                                {
                                        "$minElement" : 1
                                },
                                {
                                        "$maxElement" : 1
                                }
                        ]
                ]
        },
        "filterSet" : false
}

MongoDB 2.4.10 results

Notice that MongoDB 2.4.10 can use proper indexBounds for the both queries

> db.version()
2.4.10
> 
> db.returnToVendorShipment.count()
84
> 
> db.returnToVendorShipment.find({ "creationTime" : { "$lt" : ISODate("2014-02-13T06:40:02.000Z")}}) .sort({movementTime: 1}) .explain()
{
        "cursor" : "BtreeCursor creationTime_-1",
        "isMultiKey" : false,
        "n" : 40,
        "nscannedObjects" : 40,
        "nscanned" : 40,
        "nscannedObjectsAllPlans" : 111,
        "nscannedAllPlans" : 120,
        "scanAndOrder" : true,
        "indexOnly" : false,
        "nYields" : 0,
        "nChunkSkips" : 0,
        "millis" : 1,
        "indexBounds" : {
                "creationTime" : [
                        [
                                ISODate("2014-02-13T06:40:02Z"),
                                true
                        ]
                ]
        },
        "server" : "hendy.dev:27017"
}
> 
> db.returnToVendorShipment.find({ "creationTime" : { "$lt" : ISODate("2014-02-13T06:40:03.000Z")}}) .sort({movementTime: 1}) .explain()
{
        "cursor" : "BtreeCursor creationTime_-1",
        "isMultiKey" : false,
        "n" : 41,
        "nscannedObjects" : 41,
        "nscanned" : 41,
        "nscannedObjectsAllPlans" : 114,
        "nscannedAllPlans" : 123,
        "scanAndOrder" : true,
        "indexOnly" : false,
        "nYields" : 0,
        "nChunkSkips" : 0,
        "millis" : 1,
        "indexBounds" : {
                "creationTime" : [
                        [
                                ISODate("2014-02-13T06:40:03Z"),
                                true
                        ]
                ]
        },
        "server" : "hendy.dev:27017"
}

rassi@10gen.com I'd like to send you the collection dump over private email to test it yourself. It's small (~190 KB compressed)

Comment by Hendy Irawan [ 05/May/14 ]

I've confirmed that this issue does not occur on 2.4.10, so indeed this is a regression with MongoDB 2.6.0 :

Loading similarly large (even larger this tim) 2.7 GB collection to MongoDB 2.4.10 gives me the following for Query #4 : (note that indexBounds use proper range for voidTime, and nscannedObjects is much smaller, just 342 compared to MongoDB 2.6.0's 43029)

> db.stockReservation.find({ "voidTime" : { "$gte" : ISODate("2014-05-04T17:00:00.000Z") , "$lt" : ISODate("2014-05-05T10:20:13.894Z")}}) .sort({movementTime: 1}) .explain()
{
        "cursor" : "BtreeCursor movementTime_-1_voidTime_-1 reverse",
        "isMultiKey" : false,
        "n" : 342,
        "nscannedObjects" : 342,
        "nscanned" : 41106,
        "nscannedObjectsAllPlans" : 41734,
        "nscannedAllPlans" : 82499,
        "scanAndOrder" : false,
        "indexOnly" : false,
        "nYields" : 15,
        "nChunkSkips" : 0,
        "millis" : 15881,
        "indexBounds" : {
                "movementTime" : [
                        [
                                {
                                        "$minElement" : 1
                                },
                                {
                                        "$maxElement" : 1
                                }
                        ]
                ],
                "voidTime" : [
                        [
                                ISODate("2014-05-04T17:00:00Z"),
                                ISODate("2014-05-05T10:20:13.894Z")
                        ]
                ]
        },
        "server" : "hendy.dev:27017"
}
> db.version()
2.4.10

Comment by Hendy Irawan [ 05/May/14 ]

By the way I haven't been able to reproduce this bug with a simplified test case:

db.version();
 
db.datetest.insert({void: ISODate('2014-05-04T17:00:00.000Z'), modification: ISODate('2014-05-03T17:00:00.000Z')});
db.datetest.insert({void: ISODate('2013-05-04T17:00:00.000Z'), modification: ISODate('2014-02-04T17:00:00.000Z')});
db.datetest.insert({void: ISODate('2014-05-04T13:00:00.000Z'), modification: ISODate('2014-05-04T05:00:00.000Z')});
 
db.datetest.ensureIndex({void: 1, modification: 1});
 
db.datetest.find({void: {$gte: ISODate('2014-04-01T00:00:00.000Z')}}).sort({modification: 1}).explain();
 
db.datetest.find({void: {$gte: ISODate('2014-04-01T00:00:00.000Z'), $lte: ISODate('2015-04-01T00:00:00.000Z')}}).sort({modification: 1}).explain();

MongoDB 2.6.0 correctly uses the index for the range queries with sorting : (notice indexBounds)

> db.version();
2.6.0
> 
> db.datetest.insert({void: ISODate('2014-05-04T17:00:00.000Z'), modification: ISODate('2014-05-03T17:00:00.000Z')});
WriteResult({ "nInserted" : 1 })
> db.datetest.insert({void: ISODate('2013-05-04T17:00:00.000Z'), modification: ISODate('2014-02-04T17:00:00.000Z')});
WriteResult({ "nInserted" : 1 })
> db.datetest.insert({void: ISODate('2014-05-04T13:00:00.000Z'), modification: ISODate('2014-05-04T05:00:00.000Z')});
WriteResult({ "nInserted" : 1 })
> 
> db.datetest.ensureIndex({void: 1, modification: 1});
{
        "createdCollectionAutomatically" : false,
        "numIndexesBefore" : 1,
        "numIndexesAfter" : 2,
        "ok" : 1
}
> 
> db.datetest.find({void: {$gte: ISODate('2014-04-01T00:00:00.000Z')}}).sort({modification: 1}).explain();
{
        "cursor" : "BtreeCursor void_1_modification_1",
        "isMultiKey" : false,
        "n" : 2,
        "nscannedObjects" : 2,
        "nscanned" : 2,
        "nscannedObjectsAllPlans" : 2,
        "nscannedAllPlans" : 2,
        "scanAndOrder" : true,
        "indexOnly" : false,
        "nYields" : 0,
        "nChunkSkips" : 0,
        "millis" : 1,
        "indexBounds" : {
                "void" : [
                        [
                                ISODate("2014-04-01T00:00:00Z"),
                                ISODate("0NaN-NaN-NaNTNaN:NaN:NaNZ")
                        ]
                ],
                "modification" : [
                        [
                                {
                                        "$minElement" : 1
                                },
                                {
                                        "$maxElement" : 1
                                }
                        ]
                ]
        },
        "server" : "hendy.dev:27017",
        "filterSet" : false
}
> 
> db.datetest.find({void: {$gte: ISODate('2014-04-01T00:00:00.000Z'), $lte: ISODate('2015-04-01T00:00:00.000Z')}}).sort({modification: 1}).explain();
{
        "cursor" : "BtreeCursor void_1_modification_1",
        "isMultiKey" : false,
        "n" : 2,
        "nscannedObjects" : 2,
        "nscanned" : 2,
        "nscannedObjectsAllPlans" : 2,
        "nscannedAllPlans" : 2,
        "scanAndOrder" : true,
        "indexOnly" : false,
        "nYields" : 0,
        "nChunkSkips" : 0,
        "millis" : 0,
        "indexBounds" : {
                "void" : [
                        [
                                ISODate("2014-04-01T00:00:00Z"),
                                ISODate("2015-04-01T00:00:00Z")
                        ]
                ],
                "modification" : [
                        [
                                {
                                        "$minElement" : 1
                                },
                                {
                                        "$maxElement" : 1
                                }
                        ]
                ]
        },
        "server" : "hendy.dev:27017",
        "filterSet" : false
}

Perhaps this is due to our large dataset or index configuration?

Comment by Hendy Irawan [ 05/May/14 ]

rassi@10gen.com Please reconsider. Our issue summary was inaccurate regarding the sorting.

Query #4 should be able to use an index in order to select the initial documents (before sorting phase), however MongoDB scans all documents in the 43029-document collection (2.7 GB size): (note that indexBounds lacks any range for voidTime)

bippo:PRIMARY> db.stockReservation.find({ "voidTime" : { "$gte" : ISODate("2014-05-04T17:00:00.000Z") , "$lt" : ISODate("2014-05-05T10:20:13.894Z")}}) .sort({movementTime: 1}) .explain()
{
        "cursor" : "BtreeCursor movementTime_1",
        "isMultiKey" : false,
        "n" : 342,
        "nscannedObjects" : 43029,
        "nscanned" : 43029,
        "nscannedObjectsAllPlans" : 43674,
        "nscannedAllPlans" : 43675,
        "scanAndOrder" : false,
        "indexOnly" : false,
        "nYields" : 340,
        "nChunkSkips" : 0,
        "millis" : 119,
        "indexBounds" : {
                "movementTime" : [
                        [
                                {
                                        "$minElement" : 1
                                },
                                {
                                        "$maxElement" : 1
                                }
                        ]
                ]
        },
        "filterSet" : false
}

Compare this with Query #3 that has exact same criteria but is able to use an index for selecting.

Comment by J Rassi [ 05/May/14 ]

See http://docs.mongodb.org/manual/tutorial/sort-results-with-indexes/ for a tutorial covering this subject in further detail.

Comment by J Rassi [ 05/May/14 ]

MongoDB 2.6.0 fails to use any index when range querying field A and sorting field B

The index {A:1, B:1} is not able to satisfy a range query on A combined with a sort on B. Using this index, an in-memory sort on B is always required.

Consider the query find({A: {$gt: 0, $lt: 30}).sort({B: 1}), and the pair of documents X = {A: 10, B: 20}, Y = {A: 20, B: 10}. The documents are stored in order (X, Y) in the index, but must be returned in order (Y, X) for the query; that is, an in-memory sort is required to correctly order them.

This did not happen to MongoDB 2.4.x.

This is not the case: see the following shell session with mongod 2.4.10:

> db.version()
2.4.10
> db.stockReservation.ensureIndex({voidTime:1,movementTime:1})
{ "ok" : 1 }
> db.stockReservation.find({ "voidTime" : { "$gte" : ISODate("2014-05-04T17:00:00.000Z") , "$lt" : ISODate("2014-05-05T10:20:13.894Z")}}).sort( {movementTime: 1} ).explain().cursor
BtreeCursor voidTime_1_movementTime_1
> db.stockReservation.find({ "voidTime" : { "$gte" : ISODate("2014-05-04T17:00:00.000Z") , "$lt" : ISODate("2014-05-05T10:20:13.894Z")}}).sort( {movementTime: 1} ).explain().scanAndOrder
true

Resolving as works-as-designed.

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