How to implement cursors for pagination in an api

Question

This is similar to to this question which doesn't have any answers. I've read all about how to use cursors with the twitter, facebook, and disqus api's and also this article about how disqus generally built their cursors, but I still cannot seem to grok the concept of how they work and how to implement a similar solution in my own projects. Can someone explain specifically the different techniques and concepts behind them?

Answer 1

Lets first understand why offset pagination fails for large data sets with an example.

Clients provide two parameters limit for number of results and offset and for page offset. For example, with offset = 40, limit = 20, we can tell the database to return the next 20 items, skipping the first 40.

Drawbacks:

• Using LIMIT OFFSET doesn’t scale well for large datasets. As the offset increases the farther you go within the dataset, the database still has to read up to offset + count rows from disk, before discarding the offset and only returning count rows.
• If items are being written to the dataset at a high frequency, the page window becomes unreliable, potentially skipping or returning duplicate results.

---

How Cursors solve this ?

Cursor-based pagination works by returning a pointer to a specific item in the dataset. On subsequent requests, the server returns results after the given pointer.

We will use parameters next_cursor along with limit as the parameters provided by client in this case.

Let’s assume we want to paginate from the most recent user to the oldest user.When client request for the first time , suppose we select the first page through query:

SELECT * FROM users
WHERE team_id = %team_id
ORDER BY id DESC
LIMIT %limit

Where limit is equal to limit plus one, to fetch one more result than the count specified by the client. The extra result isn’t returned in the result set, but we use the ID of the value as the next_cursor.

The response from the server would be:

{
   "users": [...],
   "next_cursor": "1234",  # the user id of the extra result
}

The client would then provide next_cursor as cursor in the second request.

SELECT * FROM users
WHERE team_id = %team_id
AND id <= %cursor
ORDER BY id DESC
LIMIT %limit

With this, we’ve addressed the drawbacks of offset based pagination:

• Instead of the window being calculated from scratch on each request based on the total number of items, we’re always fetching the next count rows after a specific reference point. If items are being written to the dataset at a high frequency, the overall position of the cursor in the set might change, but the pagination window adjusts accordingly.
• This will scale well for large datasets. We’re using a WHERE clause to fetch rows with id values less than the last id from the previous page. This lets us leverage the index on the column and the database doesn’t have to read any rows that we’ve already seen.

For detailed explanation you can visit this wonderful engineering article from slack!