[SERVER-9540] How to get the previous mongoDB document from a compound index Created: 02/May/13  Updated: 16/May/13  Resolved: 06/May/13

Status: Closed
Project: Core Server
Component/s: Internal Client
Affects Version/s: 2.2.0
Fix Version/s: None

Type: Question Priority: Minor - P4
Reporter: George Thompson Assignee: Thomas Rueckstiess
Resolution: Duplicate Votes: 0
Labels: query
Remaining Estimate: Not Specified
Time Spent: Not Specified
Original Estimate: Not Specified
Environment:

Windows 7 64 bit SP1


Issue Links:
Duplicate
duplicates SERVER-9547 min() / max() with descending order s... Closed
Participants:

 Description   

I asked this at mongo-usr, mongo-dev and Stack Overflow with no luck. I may be obtuse and am missing something fundamentally simple.

Given this data with a unique compound index:

db.employees.drop()
db.employees.insert( { employeenum : 1, check : "A" } )
db.employees.insert( { employeenum : 1, check : "B" } )
db.employees.insert( { employeenum : 2, check : "A" } )
db.employees.insert( { employeenum : 2, check : "B" } )
db.employees.insert( { employeenum : 2, check : "C" } )
db.employees.insert( { employeenum : 5, check : "E" } )
db.employees.insert( { employeenum : 6, check : "A" } )
db.employees.ensureIndex( { employeenum: 1, check : 1 }, {unique: true} )

If I want the next document in the index after {{

{ employeenum : 5, check : "E" }

}}. I can do this:

db.employees.find({ query: { $or: [ { employeenum: { $gt: 5 } }, { check: { $gt: "E" } } ] }, $min: { employeenum: 5, check: "E" }, $maxScan: 2 })

which returns {{

{ employeenum : 6, check : "A" }

}}.

But how do I traverse backwards from {{

{ employeenum : 5, check : "E" }

}}? How do I fetch {{

{employeenum : 2, check : "C" }

}}? The way I am doing it:

{ query: { $or: [ { employeenum: { $lt: 5 } }, { check: { $lt: "E" } } ] }, $hint: { employeenum: -1, check: -1 }, $min: { employeenum: 5, check: "E" }, $maxScan: 2 }

requires a reverse index, a very inefficient solution. Is there a better way? B-tree indexes are bi-directional.

One suggested:

db.Emp.find({$or:[{employeenum{$lt:5}}]}).sort({employeenum:-1,check:-1}).limit(1)

And yes that will gets me 2-C. Now, how to go from 2-C to 2-B? This:

db.employees.find({$or:[{employeenum:{$lt:2}},{check:{$lt:"C"}}]}).sort({employ??eenum:-1,check:-1}).limit(1)

returns {{

{"employeenum" : 6, "check" : "A"}

}} I need a general way to traverse the index from a point on the index. I am using the C++ driver but using the shell here for illustration. We are developing a rapid development tool using mongoDB as the underlying database. This is a (presumably) simple use case: A window displays a single document from a collection with a compound index. The user presses a button to display the next document using the compound index. Or another button to display the previous.

I did try:

db.employees.find({ query: { $or: [ { employeenum: { $lt: 5 } }, { check: { $lt: "E" } } ] }, $max: { employeenum: 5, check: "E" }, orderby: { employeenum: -1, check: -1 }, $maxScan: 2,  $explain: false })

But that crashed the server every time which raises a concern that a shell users could crash the server with an (apparently) malformed query in a mission critical application such as ours.



 Comments   
Comment by George Thompson [ 06/May/13 ]

Created SERVER-9598

Comment by George Thompson [ 06/May/13 ]

Yes, I built a debug version for use with the C++ driver. No, I don't believe it is index corruption since I can replicate this with a small set of test data, first dropping the test collection. Possibly it is related to SERVER-9547 which quietly fails to return documents.

I'll file a separate ticket with a full stack trace.

Thanks

Comment by Tad Marshall [ 06/May/13 ]

Hi George,

Can you file a separate ticket for the unhandled exception in Windows? Steps to reproduce, a full stack trace (assuming that you got one) and enough log lines before the stack trace to provide context would be helpful.

The unhandled exception you got (0x80000003) is a breakpoint exception, which is odd because we do not have breakpoints in our released (prebuilt) code. If you built a debug version yourself then this would make sense; we do have breakpoints in the debug build.

The assertion failure is suggesting index corruption. If your query is able to produce this assertion in a non-corrupt index, this would be good to know. If reindexing made the crashes stop, this would tend to confirm the corrupt index theory.

Tad

Comment by George Thompson [ 06/May/13 ]

Hi Thomas,

That is exactly what I wanted to do. Thank you very much for your help on this issue.

For single key backward traversal, I was using:

db.docs.find({number: {$lt: 4}}).sort({number: -1}).limit(1)

On my setup (Windows 7 64 bit SP1 & mongoDB 2.2.0)

db.docs.find().max({number: 4}).sort({number: -1})

crashes the mongoDB server with:

Mon May 06 09:21:32 [conn1]  PAY.docs Assertion failure la <= 0xffffff c:\mongodb\src\mongo\db\btree.h 243
...
Mon May 06 09:21:33 [conn1] *** unhandled exception 0x80000003 at 0x000007FEFDF03172, terminating

I have been using the second reverse index workdaround. Disk space isn't an issue. My main concern is that this will be required for all indexes that require bi-directional traversal, say, an index on name, address, etc. The small impact will accumulate.

I'll keep an eye on SERVER-9547 and hope.

Thanks for the less complex find query for forward traversal.

Comment by Thomas Rueckstiess [ 06/May/13 ]

Hi George,

Just to confirm that this is what you want to achieve:

You'd like to traverse documents from a (compound) index forwards and backwards in the order they're stored in the index, starting from a given document. Is that correct?

Walking the index forward (in the direction it was specified) works fine, and I believe you don't even need the complex find query that you used in your examples:

Assuming you want to start at {employeenum:2,check:"B"}, walking forwards:

db.employees.find().min({employeenum : 2, check : "B"})

This results in:

{ "_id" : ObjectId("518317d5639296eff07632d7"), "employeenum" : 2, "check" : "B" }
{ "_id" : ObjectId("518317d5639296eff07632d8"), "employeenum" : 2, "check" : "C" }
{ "_id" : ObjectId("518317d5639296eff07632d9"), "employeenum" : 5, "check" : "E" }
{ "_id" : ObjectId("518317d6639296eff07632da"), "employeenum" : 6, "check" : "A" }

If you don't want the first document, you can add .skip(1) to the query.

Now for the backwards case. One would expect that adding a .sort({employeenum:-1,check:-1}) would do the trick, but the desired behavior is currently not implemented yet when using .min() / .max(). I've opened a separate server issue where I've minimized your example, using a simple index on a single field, but the result is the same. The additional .sort() causes 0 documents to be returned. See SERVER-9547.

As a work-around until this feature is implemented, I see two alternatives:

  1. You can create a second index traversing the documents in the opposite direction. This has only a very small impact on insert speed, but it does double the space requirements for the index. If space isn't an issue, I would recommend this solution.

  2. Alternatively, you can store the link information explicitly in the document. Basically you'd store a (doubly) linked list, by using a reference field to the primary key of the previous/next document. However, this only makes sense if you are willing to accept an additional round-trip to the database per document. If you implement some sort of paging behavior, as you describe it, where the user presses a button to move forward/backward, this may be an acceptable solution.

I hope that one of these work-arounds is suitable for your use-case.

Thank you for submitting this issue. I will link this ticket to SERVER-9547 and then close it, as we have the necessary description of the problem in a more concise format in SERVER-9547. Feel free to comment on the other ticket and upvote it if you like this to be prioritized.

Regards,
Thomas

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