Jan 1st, 2022

📖 Paginating Large, Ordered Data Sets with Cursor-Based Pagination

Hey there 👋 I would like to quickly plug a product I am working on to make teams move faster, happier. If you are building a software product and want an easy way to deploy and manage your cloud resources, set up preview environments, and understand what you're running, make sure to check it out!

In my guide on designing scalable APIs, I emphasized implementing strict limits to how many entries are sent back for endpoints that return multiple items. The idea was that as long as you’re not completely sure that the data to be returned is limited to a small number of items, always use pagination.

Pagination can come in many ways, one of them being actual pages, a good example of this being the Google search results. When querying the database containing all the pages, a subset of the pages will match your search term and will be divided up into pages, served one by one.

When implementing this pagination technique with the classic LIMIT and OFFSET keywords, databases like PostgreSQL will load the full result set into memory, scan it for all results you’re interested in and return those, skipping all values until the OFFSET is reached, then capping the results once the LIMIT is reached.

When you’re dealing with just a few values, it’ll be fast. But if you’re dealing with a large number of rows, it will slow down considerably compared to alternatives.

An introduction to cursor-based pagination

One such alternative is to use cursors. In essence, cursors are some kind of token or value you pass the database so it knows where to continue serving results from. Imagine it like a bookmark in the results, giving the database a hint of which row it last returned.

Cursor-based pagination will allow your application’s consumers to specify how many items they want to receive (enforcing an upper bound), then return both the data and a cursor that you need to specify for the next request, which then loads the next chunk of data and another token, and repeating this process until no more items are available.

The beauty of this approach is that with some assumptions, you can estimate how complex your queries will be: Users can never query more items than you allowed, PostgreSQL will stay responsive serving your data (we’ll get to how this is done), and applications can implement infinite pagination.

A downside of this approach is that you cannot just jump to a certain page. Cursors only determine which point to keep reading from, but you can’t just create a cursor to start on page 4 of 10.

Cursor-based pagination has been made popular in the GraphQL ecosystem as Relay, the GraphQL library powering Meta, has created a standard approach to pagination: According to the spec, fields that offer pagination will return a connection type, which is a list of elements, and information on the pagination.

type Post {
  id: ID!
  title: String!
}

type PostEdge {
  node: Post
  cursor: ID!
}

type PostConnection {
  edges: [PostEdge!]!
  pageInfo: PageInfo
}

type Query {
  posts(first: Int = 25, last: Int, before: ID, after: ID): PostConnection
}
type PageInfo {
  hasNextPage: Boolean!
  hasPreviousPage: Boolean!
  startCursor: ID!
  endCursor: ID!
}

The schema above allows you to query a list of post edges, which then return the actual post itself. This representation very closely follows a graph design, where edges could have information on their own (such as loading your friends in a social network where a friend is just a user but the edge contains details about the relationship between you and them).

For some cases, it might not be necessary to expose edges, so you can trim the schema to have connections return nodes immediately. It is still very important to return a connection as you want to include the pageInfo field next to the result set, so clients will use this rather than building their own logic and finding the cursor to continue.

The PageInfo type includes all relevant information regarding the pagination state: hasNextPage and hasPreviousPage tell you if items are remaining in a given direction. startCursor and endCursor are the cursors (here IDs) of the first and last item in the returned list.

This pagination example implements both forward and backward pagination, but as a consumer, you must decide for one every time you send a query.

Forward pagination expects first & optionally after for subsequent requests, returning the first n posts (after and not including a given post). When running this query for the first time, you just specify first, and receive a list of PostEdge items. When hasNextPage of pageInfo is true, the following request would specify first as last time, but also after, which takes the value of endCursor (or the ID of the last item in the list).

Backward pagination is essentially the opposite, returning the last n items before a given cursor.

Forward and backward pagination merely concerns the direction of pagination: You can implement the underlying order in your application, or have users supply an expected order. The final application will combine both direction and order of items.

According to the spec, it is very important that the order of returned items stays consistent throughout the process of fetching items, you should never receive the same item twice, and it stays constant regardless of forward or backward pagination. When using forward pagination (with after), the first item in the result set should be closest to after. When using backward pagination, the last item in the result set should be closest to before.

Implementing cursor-based pagination

In this example, we use ID cursors, but which attribute you pick is up to you. In the following, we’ll assume that our cursor refers to the ID of the entity to be returned. We’ll also focus on the database side of things, it’s up to you how you want to expose the pagination, one way would be to use the GraphQL schema I introduced earlier.

Let’s start by adding some entries to understand how our pagination works step by step.

select "id", "title" from "post";
| id                          | title |
|-----------------------------|-------|
| 236UV30CwhgaMiGKYbC4xm4KkUg | a     |
| 236UVhAGEKHSHAt3HekgSuW7zNw | b     |
| 236UWIrPdkjY2FQ1pluzGm6amXs | c     |
| 236UWqgz6Hili6vAC3DE0Gh4Ihe | d     |
| 236UXdxv812J7t3AveqnudxG6SI | d     |
| 236UYXcEANLN2F8K5A0d45k2DQo | e     |

We’ll work with a post, which receives a unique ID and a title. You might notice a duplicate title d, we’ll make use of that one later on!

As PostgreSQL will choose an order it likes best when you don’t explicitly specify one, we’ll want to sort by ID ascending just to make sure we receive a consistent order. Not doing this opens you to very weird bugs where pagination breaks because PostgreSQL decided to swap the order in some request, it’s not fun debugging that, so we’ll always specify a default order!

select "id", "title" from "post" order by "id" asc;
| id                          | title |
|-----------------------------|-------|
| 236UV30CwhgaMiGKYbC4xm4KkUg | a     |
| 236UVhAGEKHSHAt3HekgSuW7zNw | b     |
| 236UWIrPdkjY2FQ1pluzGm6amXs | c     |
| 236UWqgz6Hili6vAC3DE0Gh4Ihe | d     |
| 236UXdxv812J7t3AveqnudxG6SI | d     |
| 236UYXcEANLN2F8K5A0d45k2DQo | e     |

For the beginning, we just want to implement forward pagination. For this, we’ll receive a numeric value for first and an optional ID for after. We’ll consider the first request where only first is specified.

Since we’re dealing with just a few items, let’s use a first value and thus a page size of 3.

select "id", "title" from "post" order by "id" asc limit 3;
| id                          | title |
|-----------------------------|-------|
| 236UV30CwhgaMiGKYbC4xm4KkUg | a     | <-- start cursor
| 236UVhAGEKHSHAt3HekgSuW7zNw | b     |
| 236UWIrPdkjY2FQ1pluzGm6amXs | c     | <-- end cursor, next after

Alright, so far so good. Our response would now contain the edges related to the posts titled a, b, and c, and a pageInfo of... well what exactly? Earlier I introduced the pageSize type to include information on whether there’s a previous or next page, and the cursors to continue paginating.

Since we’re dealing with forward pagination, let’s just focus on hasNextPage and endCursor here. endCursor is the ID of the last element of the current page, so 236UWIrPdkjY2FQ1pluzGm6amXs. hasNextPage could be determined by writing a query like this

select count(*) > 3 from (
	select "id" from "post" order by "id" asc limit 3 + 1
) as "data";

This query simply loads one item more than we’d expect, verifying that the following page isn’t empty. If that’s the case, hasNextPage is true.

For subsequent requests, let’s now handle the case that both first and after are specified.

select "id", "title"
from "post"
where "id" > '236UWIrPdkjY2FQ1pluzGm6amXs' -- ID of post with content c
order by "id" asc
limit 3 + 1;
| id                          | title |
|-----------------------------|-------|
| 236UWqgz6Hili6vAC3DE0Gh4Ihe | d     | <-- start cursor
| 236UXdxv812J7t3AveqnudxG6SI | d     |
| 236UYXcEANLN2F8K5A0d45k2DQo | e     | <-- end cursor

We did a lot in this query, so let’s break it down. What we kept from the previous query is the ordering by ID ascending, as well as the limit that includes one row more than we’ll return, to determine that another page exists. What’s new is the condition we passed: To respect the ordering, we want to retrieve all posts after the endCursor, so all elements that come after the last item of the previous page.

This works because we are consistently ordering by the unique attribute id in ascending order. It’s very important to reason about the meaning of the order you’re using. In our case, we didn’t care about any particular order, we just wanted it to be consistent through the process of pagination which takes multiple requests that run at any point in time, completely stateless.

Of course, we also assumed no post would be added in between, because there’s no sane way that we could include that in our pagination if we’re not sorting by the time of post creation ascending, so that all new items come last and posts that were potentially created after we started paginating could still be included. If this sounds complicated, that’s because it is pretty tricky.

What we could also see in this request is that we only received three elements from a potential page size of 4. This means that, at the time of querying, no more data was available that met the criteria, hasNextPage would thus be false.

Now that we have forward pagination, we can also paginate the other way around! Backward pagination receives last and before.

select "id", "title"
from (
	select "id", "title"
	from "post"
	order by "id" desc
	limit 3 + 1 -- last + 1
) as "data" order by "id" asc;
| id                          | title |
|-----------------------------|-------|
| 236UWIrPdkjY2FQ1pluzGm6amXs | c     | <-- entry for hasPreviousPage
| 236UWqgz6Hili6vAC3DE0Gh4Ihe | d     | <-- start cursor, next before
| 236UXdxv812J7t3AveqnudxG6SI | d     |
| 236UYXcEANLN2F8K5A0d45k2DQo | e     | <-- end cursor

Now it’s getting more interesting. If you remember the previous section that discussed the Relay spec, for backward pagination we’re expecting results to be in the same order, just starting from the other end. Because of this, we first load the last n + 1 entries in the data set by using descending order, then flip the items by reordering again to get the correct ascending order.

This way, you completely avoid offsetting, but you should keep in mind that ordering can be very expensive if you’re not using an index on the columns you’re ordering by.

The first row of the response merely acts as a signal that hasPreviousPage is true, as there is more data to be loaded. The second row is the actual first item in the list to be returned, and the startCursor, which will be returned and passed as before in the next request.

select "id", "title" from (
	select "id", "title"
	from "post"
	where "id" < '236UWqgz6Hili6vAC3DE0Gh4Ihe'
	order by "id" desc
	limit 3 + 1
) as "data" order by "id" asc;
| id                          | title |
|-----------------------------|-------|
| 236UV30CwhgaMiGKYbC4xm4KkUg | a     |
| 236UVhAGEKHSHAt3HekgSuW7zNw | b     |
| 236UWIrPdkjY2FQ1pluzGm6amXs | c     |

And once again, we’ve reached the end of the list, as there are only three items for a page size of 4. This time around, we added a condition to return all entries before the start cursor of the previous request.

This is a very simple implementation of forward and backward cursor-based pagination that, with the right database configuration and indices in place, will scale to giant data sets just fine, while allowing you to estimate the complexity of an incoming request, making sure no consumer accidentally (or intentionally) freezes the database and/or other related systems.

In the following, we’ll continue the journey with ordering on multiple non-ID attributes.

Ordering with two attributes

In case you want to order by a different attribute, say the title, you’ll have to convert cursors to their respective attribute values as well. It’s also important to make sure that the attribute you’re ordering by is unique, and otherwise, a tie-breaker is supplied in the form of a secondary order. We’ll see all of this in action in the following query.

We’ll use the forward pagination case again, but this time, sorted by the title. We’ll assume that we want to load the first 3 posts.

select "id", "title"
from "post"
order by "title" asc, "id" asc
limit 3 + 1; # first + 1
| id                          | title |
|-----------------------------|-------|
| 236UV30CwhgaMiGKYbC4xm4KkUg | a     | <-- startCursor
| 236UVhAGEKHSHAt3HekgSuW7zNw | b     |
| 236UWIrPdkjY2FQ1pluzGm6amXs | c     | <-- endCursor
| 236UWqgz6Hili6vAC3DE0Gh4Ihe | d     | <-- hasNextPage: true

Note that we included a tie-breaker for ordering, sorting by title ascending first, and for posts with the same title, sorting by ID ascending second.

This returns 236UWIrPdkjY2FQ1pluzGm6amXs as the endCursor used in the next request and hasNextPage true as we received 1 more than the first value.

For the next page, we’ll add our cursor, albeit slightly differently than in the first example.

select "id", "title"
from "post"
where
	"title" > (select "title" from "post" where "id" = '236UWIrPdkjY2FQ1pluzGm6amXs') or
	("title" = (select "title" from "post" where "id" = '236UWIrPdkjY2FQ1pluzGm6amXs') and
	"id" > '236UWIrPdkjY2FQ1pluzGm6amXs')
order by "title" asc, "id" asc
limit 3 + 1;

Let’s start to analyze this query by breaking down what it does. Similar to the previous query, we want to return 3 + 1 items (based on first and the check for hasNextPage), ordered by title first, then ID in case of the same title.

This order is also reflected in our cursor statement now: We will target all entries with a title greater than the title of the cursor, or entries with the same title but a larger ID value. This is important for the case where your cursor has the same title value as the first element(s) of the next page. Adding just the first condition would lead to skipping all values with the same title but greater IDs, omitting rows you expected to receive.

This case is really important to understand and only exists because our title attribute isn’t unique.

To see what would happen in this case, let’s keep only the first condition and assume our cursor is the first post with the title d, so the ID and cursor are 236UWqgz6Hili6vAC3DE0Gh4Ihe.

select "id", "title"
from "post"
where
	"title" > (select "title" from "post" where "id" = '236UWqgz6Hili6vAC3DE0Gh4Ihe')
order by "title" asc, "id" asc
limit 3 + 1;
| id                          | title |
|-----------------------------|-------|
| 236UYXcEANLN2F8K5A0d45k2DQo | e     |

As we can see, we receive only the post titled e because the title is greater than d, the value of the cursor we passed. If we didn’t know the content we’re dealing with, we might assume that everything’s working fine, I mean we’re receiving a result that’s clearly after d, right?

Unfortunately, it’s not as easy. Restoring the query to include the secondary ordering step, we’ll receive slightly different results.

select "id", "title"
from "post"
where
	"title" > (select "title" from "post" where "id" = '236UWqgz6Hili6vAC3DE0Gh4Ihe') or
	("title" = (select "title" from "post" where "id" = '236UWqgz6Hili6vAC3DE0Gh4Ihe') and
	"id" > '236UWqgz6Hili6vAC3DE0Gh4Ihe')
order by "title" asc, "id" asc
limit 3 + 1;
| id                          | title |
|-----------------------------|-------|
| 236UXdxv812J7t3AveqnudxG6SI | d     |
| 236UYXcEANLN2F8K5A0d45k2DQo | e     |

Here we can see, that another post with the title d is returned. This result reflects the actual result we expect to receive when we continue paginating after the first post titled d.

While this solution works as intended now, it’s important to keep in mind that ordering by arbitrary attributes can cause huge performance hits when indices are missing or configured incorrectly.

For example, it took around 200ms to run the previous statement on a table with about 2m entries. When adding an index just for the title, the time tripled to around 600ms. This shows that sometimes, arbitrarily-placed indices can cause a worse performance than not adding any additional indices at all, so getting the right indices for the right queries is as important as any other part of implementing pagination.

Ordering with n attributes

Now that we’ve implemented ordering by a non-ID attribute, we might want to add even more dimensions: What if we wanted to order posts by likes, then dislikes, then creation time, then ID?

As you might already imagine, this simply expands the query in the condition and ordering statements and requires some fine-tuning with the indices.

The forward pagination query for follow-up requests could look something like the following

select "id", "title"
from "post"
where
	"likes" > (select "likes" from "post" where "id" = '236UWqgz6Hili6vAC3DE0Gh4Ihe') or
	(
	  "likes" = (select "likes" from "post" where "id" = '236UWqgz6Hili6vAC3DE0Gh4Ihe' and
	  (
	    "dislikes" > (select "dislikes" from "post" where "id" = '236UWqgz6Hili6vAC3DE0Gh4Ihe') or
	    ("dislikes" = (select "dislikes" from "post" where "id" = '236UWqgz6Hili6vAC3DE0Gh4Ihe') and
    	  (
	        "created_at" > (select "created_at" from "post" where "id" = '236UWqgz6Hili6vAC3DE0Gh4Ihe') or
	        ("created_at" = (select "created_at" from "post" where "id" = '236UWqgz6Hili6vAC3DE0Gh4Ihe') and
	          "id" > '236UWqgz6Hili6vAC3DE0Gh4Ihe'
	        )
        )
	    )
	  )
	))
order by "likes" asc, "dislikes" asc, "created_at" asc, "id" asc
limit 3 + 1;

On second thought, this query is absolutely crazy, please don’t even think of writing something like this! I think at this point it would be reasonable to ask why so many tiers of ordering are required and whether it could be possible to optimize the data model, for example by combining likes/dislikes in a ratio, and using IDs ordered by the timestamp of generation. With this, the query could be reduced to

select "id", "title"
from "post"
where
	"like_dislike_ratio" > (select "like_dislike_ratio" from "post" where "id" = '236UWqgz6Hili6vAC3DE0Gh4Ihe') or
	("like_dislike_ratio" = (select "title" from "post" where "id" = '236UWqgz6Hili6vAC3DE0Gh4Ihe') and
	"id" > '236UWqgz6Hili6vAC3DE0Gh4Ihe')
order by "like_dislike_ratio" asc, "id" asc
limit 3 + 1;

This makes it much simpler to read, understand, and execute! So as you can see, it’s not just about writing smart SQL statements, it’s also thinking about how your data should be structured to work best for your use case, how many levels of ordering you might need, and if that’s really necessary to solve the problem at hand.


Alright, that’s a very database-focused introduction on cursor-based pagination! I hope you found this useful and might take a thought or two from this when implementing pagination for your product. To give a tl;dr for this: Always paginate, never expose full data sets, add the right indices and test your setup against multiple cases and big sample data sets.

Thanks for reading this post 🙌 I would like to quickly plug a product I am working on to make teams move faster, happier. If you are building a software product and want an easy way to deploy and manage your cloud resources, set up preview environments, and understand what you're running, make sure to check it out!

Bruno Scheufler

Software Engineering, Management

On other platforms