Calculate skip value for given record for sorted paging

This is called “forward paging” which is a concept you can use to “efficiently page” through results in a “forward” direction when using “sorted” results.

JavaScript logic included (because it works in the shell), but not hard to translate.

The concept in general:

{ "_id": 1, "a": 3 },
{ "_id": 2, "a": 3 },
{ "_id": 3, "a": 3 },
{ "_id": 4, "a": 2 },
{ "_id": 5, "a": 1 },
{ "_id": 6, "a": 0 }

Consider those “already sorted” documents ( for convienience ) as an example of results we want to “page” by “two” items per page.

In the first instance you do something like this:

var lastVal = null,
    lastSeen = [];

db.collection.find().sort({ "a": -1 }).limit(2).forEach(function(doc) {
    if ( lastVal != doc.a ) {
        lastSeen = [];
    }
    lastVal = doc.a;
    lastSeen.push( doc._id );
    // do something useful with each document matched
});

Now those lastVal and lastSeen are something you store in something like a “session variable” than can be accessed on the next request in terms of web applications, or otherwise something similar where not.

What they should contain though are the very last value you were sorting on and the list of “unique” _id values that were seen since that value did not change. Hence:

lastVal = 3,
lastSeen = [1,2];

The point is that when the request for the “next page” comes around then you want to use those variables for something like this:

var lastVal = 3,
    lastSeen = [1,2];

db.collection.find({ 
    "_id": { "$nin": lastSeen }, 
    "a": { "$lte": lastVal }
}).sort({ "a": -1 }).limit(2).forEach(function(doc) {
    if ( lastVal != doc.a ) {
        lastSeen = [];
    }
    lastVal = doc.a;
    lastSeen.push( doc._id );
    // do something useful with each document matched
});

What that does is “exclude” all values of _id that are recorded in lastSeen from the list of results, as well as make sure that all results need to be “less than or equal to” ( descending order ) the lastVal recorded for the sort field “a”.

This yields the next two results in the collection:

{ "_id": 3, "a": 3 },
{ "_id": 4, "a": 2 },

But after processing our values now look like this:

lastVal = 2,
lastSeen = [4];

So now the logic follows that you don’t need to exclude the other _id values seen before since you are only really looking for values of “a” than are “less than or equal to” the lastVal and since there was only “one” _id value seen at that value then only exclude that one.

This of course yields the next page on using the same code as just above:

{ "_id": 5, "a": 1 },
{ "_id": 6, "a": 0 }

That is the most effiecient way to “forward page” through results in general and is particularly useful for efficient paging of “sorted” results.

If however you want to “jump” to page 20 or similar action at any stage then this is not for you. You are stuck with the traditional .skip() and .limit() approach to be able to do this by “page number” since there is no other rational way to “calculate” this.

So it all depends on how your application is implementing “paging” and what you can live with. The .skip() and .limit() approach suffers the performance of “skipping” and can be avoided by using the approach here.

On the other hand, if you want “jump to page” then “skipping” is your only real option unless you want to build a “cache” of results. But that’s another issue entirely.

More Related Contents:

Leave a Comment Cancel reply