How to Implement Cursor Pagination Like a Pro

Megan Chang
Sep 13, 2019 · 9 min read

So you’ve decided to implement cursor pagination in your website. Well, you’ve come to the right place! (If you’re not entirely convinced cursors is right for you, first, check out the benefits in this article to see if it is indeed the right option for you.)

First, you will need a unique, sequential column (e.g. timestamps, usernames, emails, etc.). Keep in mind that the data will be sorted by this column. So if, for instance, you wanted to sort a user list by last name, which is generally not considered a unique column, there will be additional work necessary. (If this is the case, never fear! Scroll to the bottom of this article for some tips to get around this limitation.)

But first, let’s discuss the ideal scenario.

Cursor Implementation

If offset pagination is an array, then cursor pagination is a linked list. Where offset grabs records based on where they are located in the table like an index, cursors use a pointer that points to a specific record and grabs the records following this specific record.

To better understand this concept, let’s take a look at the SQL statements used to generate the first 2 pages of the following user list.

╔═════════════╦═══════════════╗
║ Last Name ║ First Name ║
╠═════════════╬═══════════════╣
║ Bagshot ║ Bathilda ║
║ Black ║ Sirius ║
║ Brown ║ Lavender ║
║ Chang ║ Cho ║
║ Creevey ║ Colin ║
║ Crouch ║ Bartemius ║
║ Delacour ║ Fleur ║
║ Diggle ║ Dedalus ║
║ Diggory ║ Cedric ║
║ Dumbledore ║ Aberforth ║
║ Dumbledore ║ Albus ║
║ Dursley ║ Dudley ║
║ Dursley ║ Petunia ║
║ Dursley ║ Vernon ║
║ Filch ║ Argus ║
║ Finnigan ║ Seamus ║
║ Fletcher ║ Mundungus ║
╚═════════════╩═══════════════╝

With a limit of 5 per page, we would expect the first and second page to look like:

Page 1:
╔═════════════╦═══════════════╗
║ Last Name ║ First Name ║
╠═════════════╬═══════════════╣
║ Bagshot ║ Bathilda ║
║ Black ║ Sirius ║
║ Brown ║ Lavender ║
║ Chang ║ Cho ║
║ Creevey ║ Colin ║
╚═════════════╩═══════════════╝
Page 2:
╔═════════════╦═══════════════╗
║ Last Name ║ First Name ║
╠═════════════╬═══════════════╣
║ Crouch ║ Bartemius ║
║ Delacour ║ Fleur ║
║ Diggle ║ Dedalus ║
║ Diggory ║ Cedric ║
║ Dumbledore ║ Aberforth ║
╚═════════════╩═══════════════╝

The SQL statements to generate each page, respectively:

SELECT * FROM users WHERE "" > last_name ORDER BY last_name LIMIT 5
SELECT * FROM users WHERE "Creevey" > last_name ORDER BY last_name LIMIT 5

In addition to the list of users, the following paging object would also be included in the server response for each page, respectively:

{
“cursor”: {
“previous_page”: null,
“next_page”: "next___Creevey"
}
}
{
“cursor”: {
“previous_page”: "prev___Crouch" ,
“next_page”: "next___Dumbledore"
}
}

Analysis of Cursor Implementation

The Prefix

Since cursors serve as a pointer to a specific record in a dataset, the backend must have some way to distinguish whether we want the next page (i.e. records after this cursor) or the previous page (i.e. records before this cursor).

One way to make this distinction, is to add a prefix that can be parsed out before being sent into the SQL statement. For example, prev___ and next___. This way, only 2 parameters are required for this endpoint: limit and cursor.

Another way to do this, is by simply sending a third parameter page that can be equal to next or prev. This way, we can avoid the prefix entirely.

There are many other ways you can implement this, but really it is up to your team and the API documentation you agree upon.

In some applications, where a previous page is never needed, this prefix or parameter can be omitted entirely. This might be the case in applications like Slack’s conversations where the next page of data is triggered by scrolling to the top of the page.

The Null Cursor

Typically, the frontend needs to tell users whether or not a next or previous page even exists. For instance, if you are on the first page of data, there should only be a next button. But if you are on the second page, we would expect to see both a next and previous button.

With cursors, we know whether a page is available when its respective cursor is not null. Notice for Page 1, the previous_cursor is null, indicating that there is no previous page available.

Easy enough!

But what about the next page? Again, there are probably several ways to do this. But one way, is to query the database to the limit+1 instead of just the limit.

If the limit+1 does not exist, then send a null cursor.

Or in our case the limit+1 does not exist! So send a null cursor!

As for the previous page, if the cursor sent to the backend is an empty string "" we can safely assume that we are at the first page, and therefore there is no previous page. Thus, the previous_cursor is null.

Base 64 Encoding

It is common practice to base 64 encode cursors. So instead of:

{
“cursor”: {
“previous_page”: "prev___Crouch" ,
“next_page”: "next___Dumbledore"
}
}

You will actually see something like:

{
“cursor”: {
“previous_page”: "cHJldl9fX0Nyb3VjaA==" ,
“next_page”: "bmV4dF9fX0R1bWJsZWRvcmU="
}
}

To be honest, I have no idea why, but if you do know, feel free to leave some knowledge in the comments below!

Previous/Next & ASC/DESC Order

Implementing cursor pagination with the option of both previous or next page & ascending or descending order is truly a test of wills and determination. And LOTS of trial and error.

There are four different possible scenarios that require four slightly different SQL queries. To build the correct SQL query, we will choose a scenario and write a test case for it. A test case will include an input (cursor) and output (set of records).

SCENARIO 1: Next Page in ASC Order

Let’s choose a random set of 5 as our expected output:

╔═════════════╦═══════════════╗
║ Last Name ║ First Name ║
╠═════════════╬═══════════════╣
║ Chang ║ Cho ║
║ Creevey ║ Colin ║
║ Crouch ║ Bartemius ║
║ Delacour ║ Fleur ║
║ Diggle ║ Dedalus ║
╚═════════════╩═══════════════╝

To generate this output from a next_cursor, the cursor value must be Brown. Since it is the last row before this set. Generating the SQL query from this is fairly straightforward:

SELECT * FROM users WHERE "Brown" > last_name ORDER BY last_name ASC LIMIT 5

We’ve seen this before, and it makes sense. Next, let’s move on to a trickier case.

SCENARIO 2: Previous Page in ASC Order

We can use the same expected output as before since that output is also in ASC order. However, this time, it was generated from a prev_cursor, so the cursor value will be the first row after the set:Diggory. Thus, the SQL query looks like:

SELECT * FROM users WHERE "Diggory" < last_name ORDER BY last_name DESC LIMIT 5

Wait a second? DESC , but I thought you said we were testing the ASC case! We are, but try for yourself and you’ll see the problem that arises when using ASC . We would actually get the following output:

╔═════════════╦═══════════════╗
║ Last Name ║ First Name ║
╠═════════════╬═══════════════╣
║ Bagshot ║ Bathilda ║
║ Black ║ Sirius ║
║ Brown ║ Lavender ║
║ Chang ║ Cho ║
║ Creevey ║ Colin ║
╚═════════════╩═══════════════╝

Keep messing with your SQL statement until this makes sense to you. Try using different cursors and see what happens. (Hint: You should see this exact same set for every cursor).

Once you are convinced, take a look at the correct SQL query. While the set of records is correct, it is retrieved from the database in the wrong order. So, before returning it to the frontend, we must reverse the order of the data.

And there you have it! I’ll let you figure out how to do it for the DESC cases, but be sure to use the same process of creating a test case. Then, play with the SQL query until the expected outcome is returned. The three parameters you will have to play with are:

  • the operator in the cursor comparison (i.e. < or >)

Hint: You may notice some correlation between the operator and order.

Tip: Focus on the first 2 parameters (i.e. operator and order) first. Once you have the correct set of data, then it’s an easy matter of reversing the order if necessary.

Why a Unique, Sequential Column Is Absolutely Necessary

The column must be sequential so that we can order by that column and correctly perform the cursor comparison. But why does it have to be unique?

Let’s assume we are on Page 2 and would like to load Page 3. To do this, we would pass the next_cursor provided on Page 2 which would generate the following SQL query:

SELECT * FROM users WHERE "Dumbledore" > last_name ORDER BY last_name LIMIT 5

Uh oh! Do you see the problem here? Rather than receiving the expected output of:

Page 3:
╔═════════════╦═══════════════╗
║ Last Name ║ First Name ║
╠═════════════╬═══════════════╣
║ Dumbledore ║ Albus ║
║ Dursley ║ Dudley ║
║ Dursley ║ Petunia ║
║ Dursley ║ Vernon ║
║ Filch ║ Argus ║
╚═════════════╩═══════════════╝

We would instead get:

Page 3:
╔═════════════╦═══════════════╗
║ Last Name ║ First Name ║
╠═════════════╬═══════════════╣
║ Dursley ║ Dudley ║
║ Dursley ║ Petunia ║
║ Dursley ║ Vernon ║
║ Filch ║ Argus ║
║ Finnigan ║ Seamus ║
╚═════════════╩═══════════════╝

We skipped Albus Dumbledore! And that is just not ok.

But what if you have to order by last name? Well let’s see what we can do…

No Unique Sequential Column?

Even though I read just about everywhere that a unique, sequential column is absolutely necessary, I assumed that if this column did not explicitly exist, one could simply concatenate a few fields together in the SQL query like a makeshift cursor-on-the-fly column. Right? Wrong!

While the output was as expected, all of the advantages in time efficiency were lost. In fact, the time efficiency was worse than offset pagination. The graph below shows the results of implementing four different types of pagination on a table containing 7.3 million records:

At first glance, these results just seem wrong, but let’s dive deeper into what’s going on here.

Time Complexity Analysis

N refers to the whole data set (i.e. 7.3 million in this case) and W refers to the number of elements that meet the WHERE criteria.

Basically, the WHERE criteria has first priority in the SQL statement, so it will go through the entire set of data N concatenating the last and first name, then determining whether or not it is greater than "DumbledoreAberforth" . If it is, then it is excluded from the set, and therefore the second CONCAT for the ORDER BY never occurs. That is why the page loading time actually gets faster as you get to later pages. Because more rows are excluded by the WHERE clause, and therefore fewer ORDER BY concatenations are occurring. The same phenomenon occurs with the 2-tuple column comparison. Though, as it turns out, the concatenation function is much, much slower.

Just to make sure you feel the full impact of this time complexity, let’s zoom in on Page 1. For both offset and cursor pagination, the time will be a function O(5). In our experiment, this took 0.18 seconds to execute. For the 2 column cursor, it took about 4 seconds to load, and for the concatenated cursor (concatenated), it took 14 seconds. And that’s all just to load the very first page of data.

In conclusion, please, please for the love of God, do not concatenate your cursors, especially if you are dealing with large sets of data.

Recommendation

To avoid creating a monster, use cursor pagination correctly. This means, sort users only by a unique sequential column, such as usernames or emails.

If you must order by a non-unique column such as last_name, consider creating a new column that is populated with the concatenated cursor. Then you don’t have to concatenate on the fly in the database, which we want to avoid at all costs.

If you don’t want to add a new column to your database just for sorting purposes, consider abandoning cursor pagination entirely and instead use the default offset pagination instead as it will perform better for earlier pages, which users will encounter most often.

Good Luck!

Now you have all the tools necessary to implement cursor pagination in your website. Good luck and let me know how it goes!

Megan Chang

Written by

Just a young software developer living in a crazy start-up world and loving every minute of it.

Welcome to a place where words matter. On Medium, smart voices and original ideas take center stage - with no ads in sight. Watch
Follow all the topics you care about, and we’ll deliver the best stories for you to your homepage and inbox. Explore
Get unlimited access to the best stories on Medium — and support writers while you’re at it. Just $5/month. Upgrade