MongoDB Paging using Ranged Queries (Avoiding Skip())

Paging in MongoDB has always raised a lot of questions from developers and DBAdmins alike. In this article I will attempt to deal with one of life’s greatest dilemmas and talk of pagination in MongoDB.

What is wrong with skip()?

Nothing. Skip is an awesome and necessary function for 90% of paging cases, however, there are certain times where skip becomes slow and cumbersome for the server to work on.

The first consideration with using skip is to understand exactly what is required to commit a skip of x documents. In order to do a skip MongoDB must effectively do the work server-side that you would normally do client side of reading each record out and going over it until it reaches the right one. It normally does this via the _id or $natural index.

That being said, skip will work wonders on small result sets so you must be aware at all times whether reading this post for your queries is actually micro-optimisation or not. I personally cannot tell you whether you are micro-optimising your queries. Skip deprecation should be done with massive testing prior to reading this post, however, I personally have found that skip can work effectively into the 100’s of thousands of rows, maybe up to a million.

Believing that avoiding skip will solve all your problems is bullshit.

I can no longer live with Skip() what are my choices?

The solution to using skip is, instead, to range on the index. There are two operators in MongoDB which help with this:

• $min
• $max

Essentially, these operators tell MongoDB to only take a portion of the index into account when you go to query. As an example:- imagine I wish to range 20 million records and my index is {_id: 1}:

var c = db.c.find().limit(page_size).sort({_id: 1});
c.min(the_id_of_the_previous_document_from_the_last_page);

As you can see I range the index without using range operators. This means that range operators, such as $gte are separate from the pagination allowing this method to cover all scenarios.

The hard part is making the index. There are many considerations to take into account with this type of querying, sharding being an obvious one. You want an index that covers your queries speed but is not so complex that it cannot be split off into chunks. The ideal solution is where you page from 1,000,000 to 1,000,020 using only a single node in the shard set.

Let’s take an example; say I am paginating a Facebook friends list. I might have an index of {user_id: 1, mutual: 1, mutual_friends_count: 1, date_created: 1}.

There are two ways querying this index can happen:

1. Without any complex operators to show all friends
2. With a complex $gte to accomodate showing only recent friends

In this case it might be better to make the index {user_id: 1, date_created: 1, mutual: 1, mutual_friends_count: 1} so you can house a user’s friend list per shard while having the detail data sorted by time so you can easily range on the data within that shard while confining your query to that shard only. This would then be a fast query and should return almost as fast using single server.

So, the biggest problem with range pagination is the index. If you can perfect the index then you can easily make these queries scale.

But… What about skipping huge sections of my data?

Now you have come to the nasty bit. If skipping huge amounts of data were that easy don’t you think MongoDB would already do it for you?

To skip huge sections you need to understand that it isn’t just the DB that has to do the work, the application has to do something as well. Just as many sites who deal with log data or other people’s drunk nights out like Cloudflare and Facebook does.

Facebook timelines and many other large paging systems now accommodate a large skip via the interface. Notice how you have that year filter on the right hand side of your new timeline? Well, that’s how they do it! They simply narrow down the index via a year you pick. Simple, clean, and more effective and user friendly than putting in a random page number into the address bar.

Cloudflare, on their statistics page, gives you a huge summary graph allowing you pick out specific ranges using your mouse to highlight parts of the graph. Again, this works a lot like Facebook’s own, whittling it down to a pre-defined set, or range, of documents.

In fact if you look at 99% of all applications, whether web based or not, that have to deal with huge amounts of data (like Apache logs) you will realise they do not implement normal paging.

So the first and most important thing to understand about how to do large scale paging is that you can no longer solve your problems with just a bit of HTML and a skip(), you need an interface.

Just look at how other programs/sites do it and you will realise how you should do it.

What if I need to pick random records out for paging or just in a normal query?

This is a little off topic but can be used for paging as well.

sometimes people like to pick random records out from their collection. One option is to use skip() like:

$cursor = $collection->find();
$cursor->skip(3);
$cursor->next();
$doc = $cursor->current();

And again, this is good for small skips. But what if you need to do this continuously and at random points?

If you were to do this often and in random ways it might be better to use an increment ID, combining another collection with findAndModify to produce an accurate document number (Doc Link).

This, however, induces problems, it is slow (findAndModify adds locks) and you must maintain this ID, especially when deletes occur. Here is a solution using $gte to get the next nearest number. If that row still exists it will get that row, if not then it will get the next nearest random number:

$cur = $db->collection->find(array('ai_id' => array('$gte' => 403454)))->order(array('ai_id' => SORT_ASC))->limit(1);
$cursor->next();
$doc = $cursor->current();

Post a comment if you would like further info or see errors.