Cursor based pagination
Tags: softwareengineering, programming
Published: 2023-01-21 13:56:20

*This article was originally published in my [Personal Blog](https://www.yieldcode.blog/post/cursor-based-pagination)*

Traditional pagination existed for many years. But it’s not useful for platforms with huge amount of user generated content. Luckily, there is an alternative solution for such systems.

<!--more-->

## Traditional pagination
Before we jump into the solution, let’s look at traditional pagination and it’s drawbacks. Let’s say we have a database table for forum posts that looks like this:
| ID  | Title     | Content      | LastActiveDate      |
| --- | --------- | ------------ | ------------------- |
| 1   | Some post | Some content | 2022-11-26T14:00:00 |

In this case, `LastActiveDate`—indicates the date when the post was last active (i.e., a comment was published).

We want to display a front page with all the posts sorted by `LastActiveDate`. Since we don’t know how much data we can have, we decide on an arbitrary **page size** of 10. And then, in order to display the posts on a particular page, we will use the following query:
```sql
SELECT * FROM posts
ORDER BY LastActiveDate
LIMIT ${pageSize}
OFFSET ${(currentPage - 1) * pageSize}
```

The math is very simple. Given a specific page, say **2**, we will select all items starting from offset `(2 - 1) * 10 = 10`, limiting the selection to 10 elements, and the result will be all the items in group of `[10,20)`.

Usually, with traditional pagination, we also need to have another query in order to generate the visual pagination itself. And for that we need to know the total amount of pages we have, which can be done by:
```typescript
const totalItems = await sql("SELECT count(ID) FROM posts") as number;
const totalPages = Math.ceil(totalItems / pageSize);
```

### Drawbacks
This pagination style, however, has one major drawback. Let’s say I’ve navigated to page 1 of the forum and then decided to go make some tea. After coming back and seeing that no posts on the first page are of interest to me, I navigate to the second page and find out that it includes 2 posts from the first page.

This happens because during the time I was making and drinking my tea, some older posts that were not among the 10 posts on the first page — were updated, hence changing their `LastActiveDate` to be the most recent. Upon navigating to the second page, I now see 10 more posts, but because of the shift in order, 2 posts from the first 10 — were pushed into the second 10 on the second page.

Usually, on platforms with low update rates, like a small forum — this drawback is not that critical. Occasionally users will see content on the next page, which appeared on the previous page — but the frequency during which it happens — is low. We can increase the page size to say 15, 20, 25, or even 30 posts per page — and since forums often have activity concentrated in few popular or new posts on the first page, the chance of seeing the same data on next pages — is small, and we can live with that.

However, for high throughput platforms like Twitter, or machine-to-machine streaming services — this case is unacceptable. Image navigating Twitter only to see the same content over and over again, because the rate at which content is created on Twitter is rapid, and thus content from the previous page is always pushed down to the next page.

In order to solve this problem, let me introduce — Cursor based pagination.

## Cursor based pagination
Let’s say we want our forum pagination to never display data from previous pages. When a user navigates to the second page — she will always see data that suppose to be on that page. This can be achieved with cursor based pagination.

### How cursor based pagination works
In cursor based pagination, we do not have logical pages. Instead, each page returns the data that suppose to be displayed on that page as well as a **token** to retrieve the next page. The token is usually opaque, and for the end user it has no meaning — but our system knows to read it and generate the next page based on it.

This brings me to the first drawback of cursor based pagination:
> [!attention] 
> Cursor based pagination is **forward**. It does not support going back (i.e. navigating from second page back to first, or from third back to second); nor it supports *skipping* pages (i.e. going to page 5 from page 2).

On a platform like forum, this might not be very useful. Forums are typically meant to be *browsed*, so users always can jump to a specific page, navigate backwards and forwards, or event jump to the last page. However, — on platforms with *infinite* scrolling navigation, like feeds, this solution is perfect.

### Cursor based pagination example
Let’s say our product manager came up with the terrible idea of turning our 90s looking forum with traditional pagination, to 2000s looking forum with infinite scroll feed. We’ve tried to warn him that this is a bad idea, but he insisted that users wanted it. And so let’s turn our forums’ traditional pagination — to cursor based instead.

First, we need to select the cursor. Since forum posts are often sorted in chronological order from newest to oldest post, it makes sense to use the `LastActiveDate` as a cursor. Hence, the retrieval of a particular pages’ data can be done like this:
```typescript
async function getPosts(cursor: null | Date) {
	const posts = await table("posts").select("*").orderBy("LastActiveDate", "DESC").limit(PAGE_SIZE).where(q => {
		if(cursor) {
			q.where("LastActiveDate", "<", cursor);
		}
	});

	return {posts, nextPageCursor: posts.length ? posts[posts.length - 1]["LastActiveDate"] : null}
}
```

*Disclaimer: The query builder is a pseudocode, but can be achieved with tools like [KnexJS](https://knexjs.org/)*

For every call, we fetch the first `PAGE_SIZE` posts and provide a cursor to the next page, which is equal to the `LastActiveDate` of the last post in our current batch (or `null` if no posts exist). If the `cursor` is `null` — we start from the first page.

Since our posts are always sorted in chronologically descending order, our pagination becomes consistent.

Let’s try to do a visualization. Let’s imagine we have the following database:
| ID  | Title   | ….  | LastActiveDate      |
| --- | ------- | --- | ------------------- |
| 1   | Title 1 |     | 2022-01-10T00:00:00 |
| 2   | Title 2 |     | 2022-01-09T00:00:00 |
| 3   | Title 3 |     | 2022-01-08T00:00:00 |
| 4   | Title 4 |     | 2022-01-07T00:00:00 |
| 5   | Title 5 |     | 2022-01-06T00:00:00 |

> [!disclaimer]
> I’ve intentionally sorted the posts by `LastActiveDate` to easier visualize the process. Obviously, the data does not need to be sorted in advance, since SQLs `SORT BY LastActiveDate DESC` handles the sorting.

For the sake of simplicity, let’s set our page size to 2. Upon first execution, we will get posts 1 and 2 and our `nextPageCursor` will be equal to `2022-01-09T00:00:00` (which is the `LastActiveDate` of the second post).

As we would like to retrieve the next page, we will provide the `nextPageCursor` to our function, and since the query looks at posts older than `2022-01-09T00:00:00` we will get two more posts — IDs 3 and 4.

Now — let's come back to our tea scenario. Imagine I’m looking at the forum's first page with posts 1 and 2, and before clicking *next*, I go to drink tea. During that time, someone posts a new comment in post ID 3 — thus altering its `LastActiveDate` to be today (let’s say today is `2022-01-11T00:00:00`). The table will now look like this:
| ID  | Title   | ….  | LastActiveDate      |
| --- | ------- | --- | ------------------- |
| 3   | Title 3 |     | 2022-01-11T00:00:00 |
| 1   | Title 1 |     | 2022-01-10T00:00:00 |
| 2   | Title 2 |     | 2022-01-09T00:00:00 |
| 4   | Title 4 |     | 2022-01-07T00:00:00 |
| 5   | Title 5 |     | 2022-01-06T00:00:00 |

When I come back to the computer, I click *next page*. In our traditional navigation — my action would have returned posts with IDs 2 and 4, thus “leaking” the second post from the first page to the second.

Cursor based navigation, with the cursor of `2022-01-09T00:00:00`, would however return posts with IDs 4 and 5 as expected. Notice how post ID 3 is skipped and will never be seen by me, unless I start over from page 1. It’s important to point out that this flaw is not a problem of the cursor based pagination — but rather a problem with the way we’ve *implemented* cursor based pagination. Different use cases — have different implementations. It is possible to implement cursor base pagination which takes into account newer content as well. It, however, makes little sense to do so in a context of a forum, since in forums — going forward in pagination — means seeing older content.

As I’ve said before, we do lose some functionality — namely: going backwards (from page 2 to page 1 for example) and skipping pages (from page 2 to page 7 for example). So this approach is not useable for *browsing* content in a paginated manner, but it is a good approach to implement infinite scrolling without encountering duplicate content.

### Bonus—don’t use dates and or timestamps as cursor
I could have ended the article here, but I’m pretty sure if I did so — I’d get criticized for using date as a cursor. And this will be a well deserved criticism.

You see — the entire point of cursor based navigation — is to create a consistent stream of data without repetitions. Yes — you give away some features, but in exchange you get fresh data for each page. As I’ve said — some systems might benefit from it.

However, — by using dates as cursors — you run into the same problem. You can encounter content repetition. Let’s assume we have a high traffic forum with a very active community. Let’s look at a subset of such forums posts table:
| ID  | Title   | ….  | LastActiveDate      |
| --- | ------- | --- | ------------------- |
| 675 | Title 1 |  …   | 2022-01-10T12:31:22 |
| 123 | Title 2 |   …  | 2022-01-10T12:30:48 |
| 534 | Title 3 |    … | 2022-01-10T12:30:23 |
| 301 | Title 4 |     …| 2022-01-10T12:30:23 |
| 231 | Title 5 |     …| 2022-01-10T12:30:23 |
| 945 | Title 6 |     …| 2022-01-10T12:30:17 |

*Disclaimer: as earlier, the data is sorted by `LastActiveDate` for demonstration purposes only.*

For the sake of example, let’s say our page size is 2. And since we are looking at a subset of data, let’s say we hold a `nextPageCursor` of `2022-01-10T12:31:22`. What will be the result of the invocation of `getPosts("2022-01-10T12:31:22");`? If you’ve read through the article and understood it well, you would be correct to answer: posts 123 and 534. And what will be the `nextPageCursor` value for that invocation? The correct answer is `2022-01-10T12:30:23`.

Now, here’s the problem. Let’s say you want to navigate to the next page using `nextPageCursor = '2022-01-10T12:30:23'`. What would be the result? That’s true — post ID 945. Since the query we’ve written earlier, translates to:
```sql
SELECT * FROM posts
ORDER BY LastActiveDate DESC
WHERE LastActiveDate < '2022-01-10T12:30:23'
LIMIT 2
```

We are skipping posts ID 301 and ID 231. The hasty among you might just run and replace `<` to `<=`, but this introduces another issue. Now, instead of getting post ID 945 you get posts ID 534 and ID 301. So not only you are getting post ID 534 **again**, your `nextPageCursor` is set to `2022-01-10T12:30:23` so you're essentially stuck in an endless loop (unless someone decides to update one of the posts).

Dates, although provide chronological order, **are not** providers of uniqueness. In a system with high rate of content, you might end up with collisions. And I know what you are thinking about: *I’ll just add milliseconds!* While milliseconds *might* help you to prevent this issue in human generated content (although there is still a chance of collision, depending on the traffic and the nature of the system) — they are not a solution for machine generated content in systems with high rate of content generation. There are other solutions, like content versioning, to provide uniqueness of the cursor.

Also keep in mind that cursors do not have to be bound to one specific dimension. I once designed a system where the cursor was a JSON that held multiple vectors for data retrieval. This JSON was then `base64` encoded and was used as a cursor for navigation. So you could combine multiple fields, and any other data you would want, inside the cursor. As long as you can pass the cursor in the URL and your system can decode it — it’s a viable solution.