As part of our REST APIs, we commonly have to implement pagination, allowing our users to retrieve large quantities of records via a series of short requests that avoid blocking our servers. There are two common solutions to pagination, the simpler skip/limit technique, and the more complex cursor technique. Here we’ll delve into the differences between the two techniques, the issues involved and why we have come to prefer cursors.
Skip/Limit Technique
Imagine you have the following JSON records in your database table.
{ user: 2, score: 7 }
{ user: 3, score: 9 }
{ user: 4, score: 3 }
{ user: 5, score: 4 }
Now imagine you want to retrieve the records using pagination with 2 records per page. To get the first page, you would skip 0 records, and limit by 2 records providing you with the following records.
{ user: 2, score: 7 }
{ user: 3, score: 9 }
To get the second page, you would skip 2 records, and again limit by 2 records leaving you with the following records.
{ user: 4, score: 3 }
{ user: 5, score: 4 }
As you can see, despite the contrived record limit, this technique is pretty simple. However, this technique has a problem when you sort records as shown in the next section.
Skip/Limit Problem
You start to run into problems with the skip/limit technique when you introduce custom sorting options. Imagine you have the following JSON records in your database table.
{ user: 2, score: 7 }
{ user: 3, score: 9 }
{ user: 4, score: 3 }
{ user: 5, score: 4 }
Now imagine you want to receive the records in descending order of score and paginate to 2 records per page, perhaps to create some kind of leaderboard. To get the first page, you would sort the scores in descending order, skip 0 records, and the limit by 2 records. This would return the following two records from the full record list above.
{ user: 3, score: 9 }
{ user: 2, score: 7 }
Now imagine that you want to get the second page. To get the second page, following the skip/limit technique, you would sort the scores in descending order, skip 2 records, and limit by the 2 records. However, imagine that since retrieving the first page, a new record has been added (highlighted below), so now you have the following JSON records in your database table.
{ user: 2, score: 7 }
{ user: 3, score: 9 }
{ user: 4, score: 3 }
{ user: 5, score: 4 }
{ user: 1, score: 7 }
Following the skip/limit technique, when you retrieve the second page, you will actually receive one of the items from the first page again (highlighted below).
{ user: 2, score: 7 }
{ user: 5, score: 4 }
This duplication of records is the problem with the skip/limit technique and it’s exacerbated when you have more records, but even worse when records can be updated/mutated. If you can avoid updating records then you can use the cursor technique (explained in the next section) to avoid this problem. In our case we often work with xAPI statements which we avoid updating because they’re supposed to be immutable.
Cursor Technique
So starting from the same place as the last two sections, imagine again that you have the following JSON records in your database table.
{ user: 2, score: 7 }
{ user: 3, score: 9 }
{ user: 4, score: 3 }
{ user: 5, score: 4 }
As with the previous section, you want to receive the records in descending order of score and paginate to 2 records per page. To get the first page, we must again sort the scores in descending order, but in order for the “cursor” technique to work, we must also sort them in ascending order by some unique identifier. In this case our unique identifier is the “user” property, however, it’s more typically the “id” or “_id” property. Following this sort, we limit by 2 records as usual and this would return the following two records from the full record list above.
{ user: 3, score: 9 }
{ user: 2, score: 7 }
Imagine once again, that a new record has been inserted (highlighted below) before you retrieve the second page. So now you have the following JSON records in your database table.
{ user: 2, score: 7 }
{ user: 3, score: 9 }
{ user: 4, score: 3 }
{ user: 5, score: 4 }
{ user: 1, score: 7 }
To get the second page we can use our last record from the first page as the “cursor”. For the cursor to work, we must again sort the records by score in descending order and sort them in ascending order by our unique identifier. This puts the records in the following order. Note that the new record is highlighted and the records from the first page are also highlighted.
{ user: 3, score: 9 }
{ user: 1, score: 7 }
{ user: 2, score: 7 }
{ user: 5, score: 4 }
{ user: 4, score: 3 }
Following the sort, we use the cursor to filter records with a score less than or equal to 7 and a user property greater than to 2. Then as usual we limit by 2 records to get the following records in the second page.
{ user: 5, score: 4 }
{ user: 4, score: 3 }
Notice that whilst this means the new record is not retrieved, it avoids duplicating the record from the first page in the second page which causes confusion, especially when dealing with a larger volume of records.
Join us
We’re often hiring - you can find all our job listings on our website.
Top comments (0)