Cursor-Based Pagination in Go

July 11, 2022

Programming Go

Cursor-based pagination is very popular these days. We are seeing more and more companies using it in their APIs. It goes well with infinite scroll, and it is efficient on big data sets compared to traditional offset-based pagination.

However, it’s much harder to implement, and doesn’t have the ability to jump to a page.

It works by making use of cursors that represent a specific position within the data set. The server generates these cursors and includes them in the response along with the requested data. The client can then use the cursor to request the next page of results.

We would return the first 10 rows and include a cursor that represents the position or index of the last row in the dataset. This cursor could be based on a timestamp, such as the creation time, or the ID of the last row.

When the client requests the next page, they would include the cursor we had sent along with the previous page. The server would use this cursor to retrieve the next 10 rows after the cursor position, and return them along with a new cursor representing the position of the last row on the current page. This process can continue until there are no more rows to retrieve, or until the user chooses to stop paginating.

After the first page, the server has to send two cursors to the client - one for going forward, one for going backward. We can call these cursors, Prev and Next so that we can understand which direction the caller wants to go, from the cursor they provide.

If the client provides Prev cursor, we would return the previous rows before the cursor just like when going forward.

The Need for a Unique, Sequential Column

In cursor-based pagination, a unique, sequential column that we can sort our table with is required. If the column we choose is not unique we can potentially skip records.

Let’s say we chose the name column as our cursor, and we have some duplicate values.

id | name        |
---+-------------+
 4 | Red Shirt   |
 5 | White Shirt |
 6 | White Shirt |
 7 | Blue Scarf  |
 8 | Black Scarf |

For example, a page finishes with White Shirt with ID 5. If we say, give me the records after “White Shirt”, this would skip product with ID 6. To avoid this we need a unique column for our cursors. Since we want to sort our table with this column, it has to be sequential as well.

The Logic

Before we jump to the implementation, I suggest we take a couple of minutes to understand the logic behind it. To visualize the process, we can use a number line.

Imagine the created_at values as just days, so our latest row is inserted on 26th, the last one on 22nd, and the default sorting is in descending order.

We are expecting two arguments from our client, which can be named as Prev and Next, representing two cursors. The cursor we receive will determine the direction we are going. When we get a Next cursor, we’ll go from 26 to 22. When we get a Prev cursor, it’s going to be the other way around.

Our default order is descending so while going forward, from 26 to 22, we want rows with earlier dates. So we can use, WHERE p.created_at < $1 ORDER BY created_at DESC LIMIT $2. $1 will be the Next cursor. We are using DESC because we want our result to be in descending order.

Going backward is a little tricky.

Say we want to receive the results from 22 to 26. We want to get rows with more recent dates. While going backward we need to reverse the order. Why?

Let’s say the limit is 3, and we want rows 23, 24 and 25. So our Prev cursor will be 22. So we can use the following WHERE clause - with 22 as the Prev cursor in place of $1:

WHERE p.created_at > 22 ORDER BY created_at DESC LIMIT 3

However, since all rows to the left of 22 are bigger than 22, we’ll always get 26, 25, and 24 no matter what we provide as Prev cursor.

In order to only get the rows after 22, we have to reverse the order:

Now we can use WHERE p.created_at > $1 ORDER BY created_at ASC LIMIT 3, and it will give the next 3 rows, after 22.

Of course, after this, we have to sort the results in descending order again. This can be done by wrapping the query with a WITH statement.

1
2
3
4


WITH p AS (
  SELECT * FROM products p WHERE p.created_at > prev_cursor ORDER BY created_at ASC LIMIT 3
)
SELECT * FROM p ORDER BY created_at DESC

If we had joins we could add the order by statement at the end like so:

1
2
3
4
5


SELECT *
FROM (SELECT * FROM products p WHERE p.created_at > $1 ORDER BY created_at ASC LIMIT $2) p
LEFT JOIN product_variations pv ON p.id = pv.product_id
LEFT JOIN variations v ON pv.variation_id = v.id
ORDER BY created_at DESC

I hope, it is more clear. We are using one of the cursors as a point in the dataset and returning rows adjacent to it.

In a nutshell: Keep the original order while going forward. Reverse the order in the where clause while going backward, then reverse the results back to the original order.

Now that we got an introduction, I would like to share how we can implement pagination with cursors in Go only using the standard library.

Data Model

First we should define our schema. To make things easy, we can work on a simple table.

1
2
3
4
5


CREATE TABLE IF NOT EXISTS products(
  id BIGSERIAL UNIQUE PRIMARY KEY,
  created_at TIMESTAMPTZ DEFAULT NOW(),
  name VARCHAR NOT NULL
)

As we said, we need a sequential column to use as a cursor. created_at column would be great for this.

Implementation

Let’s look at the function signature.

1
2
3
4
5
6
7
8


type Cursors struct {
	Prev string // provided when going backward
	Next string // provided when going forward
}

func (store ProductStore) GetProducts(
	ctx context.Context, cursors Cursors, limit int,
) ([]product.Product, Cursors, error)

Our function receives 2 cursors. Prev cursor will be provided when the caller wants to go to the previous page, and Next cursor to go to the next page. We’ll also receive a limit parameter.

First thing we do inside the function is to validate the parameters.

1
2
3
4
5
6


if limit == 0 {
  return []product.Product{}, Cursors{}, errors.New("limit cannot be zero")
}
if cursors.Next != "" && cursors.Prev != "" {
  return []product.Product{}, Cursors{}, errors.New("two cursors cannot be provided at the same time")
}

Depending on the use case, limit can be empty as well. In this example, we can make it required.

We can’t have two cursors at the same time though. It would mean that the caller wants to move to both directions at the same time.

After validating the parameters, we have to build our query.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34


values := make([]interface{}, 0, 4)
rowsLeftQuery := "SELECT COUNT(*) FROM products p"
pagination := ""

// Going forward
if cursors.Next != "" {
  rowsLeftQuery += " WHERE p.created_at < $1"
  pagination += "WHERE p.created_at < $1 ORDER BY created_at DESC LIMIT $2"
  values = append(values, cursors.Next, limit)
}

// Going backward
if cursors.Prev != "" {
  rowsLeftQuery += " WHERE p.created_at > $1"
  pagination += "WHERE p.created_at > $1 ORDER BY created_at ASC LIMIT $2"
  values = append(values, cursors.Prev, limit)
}

// No cursors: Going forward from the beginning
if cursors.Next == "" && cursors.Prev == "" {
  pagination = " ORDER BY p.created_at DESC LIMIT $1"
  values = append(values, limit)
}

stmt := fmt.Sprintf(`
  WITH p AS (
    SELECT * FROM products p %s
  )
  SELECT id, created_at, name, 
  (%s) AS rows_left,
  (SELECT COUNT(*) FROM products) AS total
  FROM p
  ORDER BY created_at DESC
`, pagination, rowsLeftQuery)

There are 2 subqueries, one for the total count, and the other for the number of rows left on the direction we are going. They’ll slow down the query, but they are useful for computing the cursors. We’ll get back to these later.

While going forward and backward we have to modify rowsLeftQuery, to get the number of rows left going towards that direction.

Next, we are running the query and parsing the results, nothing special here.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22


rows, err := store.db.Query(stmt, values...)
if err != nil {
  return nil, Cursors{}, fmt.Errorf("failed to get products. error: %v", err)
}
defer rows.Close()

var (
  rowsLeft int
  total    int
  pp       = []product.Product{}
)

for rows.Next() {
  var p product.Product

  err := rows.Scan(&p.ID, &p.CreatedAt, &p.Name, &rowsLeft, &total)
  if err != nil {
    return []product.Product{}, Cursors{}, err
  }

  pp = append(pp, p)
}

At this point, we have to compute the cursors we’ll return. We have to return a Next cursor when we have a next page, and Prev cursor when we have a previous page. We’ll return both when we are somewhere in the middle.

In our query, we are computing the total number of rows, and the number of rows left in the direction we are going. We’ll use these numbers to understand if we are at the last page.

This way of identifying first and last pages requires 2 subqueries. If you have a more efficient way of doing this, please let me know.

Again, we can visualize the direction using a number line.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40


var (
		prevCursor string // cursor we return when there is a previous page
		nextCursor string // cursor we return when there is a next page
	)

	//  A     B     C			D			E
	//  |-----|-----|-----|-----|

	// When we receive a next cursor, direction = A->E
	// When we receive a prev cursor, direction = E->A

	switch {

	// 1. If there are no results we don't have to compute the cursors
	case rowsLeft < 0: // or just len(pp) == 0

	// 2. On A, direction A->E (going forward), return only next cursor
	case cursors.Prev == "" && cursors.Next == "":
		nextCursor = pp[len(pp)-1].CreatedAt.UTC().Format(time.RFC3339)

	// 3. On E, direction A->E (going forward), return only prev cursor
	case cursors.Next != "" && rowsLeft == len(pp):
		prevCursor = pp[0].CreatedAt.UTC().Format(time.RFC3339)

	// 4. On A, direction E->A (going backward), return only next cursor
	case cursors.Prev != "" && rowsLeft == len(pp):
		nextCursor = pp[len(pp)-1].CreatedAt.UTC().Format(time.RFC3339)

	// 5. On E, direction E->A (going backward), return only prev cursor
	case cursors.Prev != "" && total == rowsLeft:
		prevCursor = pp[0].CreatedAt.UTC().Format(time.RFC3339)

	// 6. Somewhere in the middle
	default:
		nextCursor = pp[len(pp)-1].CreatedAt.UTC().Format(time.RFC3339)
		prevCursor = pp[0].CreatedAt.UTC().Format(time.RFC3339)

	}

	return pp, Cursors{Prev: prevCursor, Next: nextCursor}, nil

We can determine the direction from the provided cursor, if we receive Next we want to go next, and vice versa.

First scenario is when we don’t have any rows, so we won’t return any cursors.
When we don’t receive any cursors, that means we are on the first page, going forward. In this case, we won’t have a previous page, so we’ll only return Next. We can return the created_at field of the last row.
Eventually the caller will reach the end while going forward. If rowsLeft equals the number of rows returned, it means we are at the end. We can also check for rowsLeft <= limit. We should only return Prev since there is no page left in this direction.
Next case is when we reach the end while going backward, so from E to A. We can have the same logic and check rowsLeft == len(res) to identify we are at the end. We should only return Next.
This case can only happen when the caller provides a Prev timestamp that is smaller than E’s timestamp. At this point, we can only go backward, so only Prev cursor is returned.
If one of the cursors is between E and A, we have to return both cursors to indicate that caller can go both ways.

And that’s about it. We can return the rows, with cursors, and we are done.

Here is the complete code:

  1
  2
  3
  4
  5
  6
  7
  8
  9
 10
 11
 12
 13
 14
 15
 16
 17
 18
 19
 20
 21
 22
 23
 24
 25
 26
 27
 28
 29
 30
 31
 32
 33
 34
 35
 36
 37
 38
 39
 40
 41
 42
 43
 44
 45
 46
 47
 48
 49
 50
 51
 52
 53
 54
 55
 56
 57
 58
 59
 60
 61
 62
 63
 64
 65
 66
 67
 68
 69
 70
 71
 72
 73
 74
 75
 76
 77
 78
 79
 80
 81
 82
 83
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115


// ...

type Cursors struct {
	Prev string
	Next string
}

func (store Store) GetProducts(
	ctx context.Context, cursors Cursors, limit int,
) ([]product.Product, Cursors, error) {
	if limit == 0 {
		return []product.Product{}, Cursors{}, errors.New("limit cannot be zero")
	}
	if cursors.Next != "" && cursors.Prev != "" {
		return []product.Product{}, Cursors{}, errors.New("two cursors cannot be provided at the same time")
	}

	values := make([]interface{}, 0, 4)
	rowsLeftQuery := "SELECT COUNT(*) FROM products p"
	pagination := ""

	if cursors.Next != "" {
		f := fmt.Sprintf("p.created_at < $%d", len(values)+1)
		rowsLeftQuery += fmt.Sprintf(" WHERE %s", f)
		pagination += fmt.Sprintf("WHERE %s ORDER BY created_at DESC LIMIT $%d", f, len(values)+2)
		values = append(values, cursors.Next, limit)
	}

	if cursors.Prev != "" {
		f := fmt.Sprintf("p.created_at > $%d", len(values)+1)
		rowsLeftQuery += fmt.Sprintf(" WHERE %s", f)
		pagination += fmt.Sprintf("WHERE %s ORDER BY created_at ASC LIMIT $%d", f, len(values)+2)
		values = append(values, cursors.Prev, limit)
	}

	if cursors.Next == "" && cursors.Prev == "" {
		pagination = fmt.Sprintf(" ORDER BY p.created_at DESC LIMIT $%d", len(values)+1)
		values = append(values, limit)
	}

	stmt := fmt.Sprintf(`
		WITH p AS (
			SELECT * FROM products p %s
		)
		SELECT id, created_at, name, 
		(%s) AS rows_left,
		(SELECT COUNT(*) FROM products) AS total
		FROM p
		ORDER BY created_at DESC
	`, pagination, rowsLeftQuery)

	rows, err := store.db.Query(stmt, values...)
	if err != nil {
		return nil, Cursors{}, fmt.Errorf("failed to get products. error: %v", err)
	}
	defer rows.Close()

	var (
		rowsLeft int
		total    int
		pp       = []product.Product{}
	)

	for rows.Next() {
		var p product.Product

		err := rows.Scan(&p.ID, &p.CreatedAt, &p.Name, &rowsLeft, &total)
		if err != nil {
			return []product.Product{}, Cursors{}, err
		}

		pp = append(pp, p)
	}

	var (
		prevCursor string // cursor we return when there is a prev page
		nextCursor string // cursor we return when there is a next page
	)

	//  A     B     C			D			E
	//  |-----|-----|-----|-----|

	// When we receive a next cursor, direction = A->E
	// When we receive a prev cursor, direction = E->A

	switch {

	// *If there are no results we don't have to compute the cursors
	case rowsLeft < 0:

	// *On A, direction A->E (going forward), return only next cursor
	case cursors.Prev == "" && cursors.Next == "":
		nextCursor = pp[len(pp)-1].CreatedAt.UTC().Format(time.RFC3339)

	// *On E, direction A->E (going forward), return only prev cursor
	case cursors.Next != "" && rowsLeft == len(pp):
		prevCursor = pp[0].CreatedAt.UTC().Format(time.RFC3339)

	// *On A, direction E->A (going backward), return only next cursor
	case cursors.Prev != "" && rowsLeft == len(pp):
		nextCursor = pp[len(pp)-1].CreatedAt.UTC().Format(time.RFC3339)

	// *On E, direction E->A (going backward), return only prev cursor
	case cursors.Prev != "" && total == rowsLeft:
		prevCursor = pp[0].CreatedAt.UTC().Format(time.RFC3339)

	// *Somewhere in the middle
	default:
		nextCursor = pp[len(pp)-1].CreatedAt.UTC().Format(time.RFC3339)
		prevCursor = pp[0].CreatedAt.UTC().Format(time.RFC3339)

	}

	return pp, Cursors{Prev: prevCursor, Next: nextCursor}, nil
}

Testing

Cursor based pagination has a complex logic, so we should test it extensively both manually and with automated tests. Here we can add 6 distinct cases, but having more test cases would be better for a real world scenario.

Manually testing is a good idea as well, for example inserting 50 rows and paginating in both directions to check if everything is fine.

While testing functions that talk to a database I use this approach. It involves using a docker container for the database, running tests inside separate schemas, and using go-cmp package for comparison.

Let’s start with the first scenario, requesting the first page.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53


func TestGetProducts_FirstPage_Limit5(t *testing.T) {
	db := test.SetupDB(t)
	test.CreateProductTable(t, db)

	store := postgres.NewStore(db)

	_, err := db.Exec(`
		INSERT INTO products(created_at, name)
		VALUES
			('2022-05-23 13:29:16', 'Shirt'),
			('2022-05-24 13:29:16', 'Polo'),
			('2022-05-25 13:29:16', 'T-Shirt'),
			('2022-05-26 13:29:16', 'Pants'),
			('2022-05-27 13:29:16', 'Socks'),
			('2022-05-28 13:29:16', 'Shoes'),
			('2022-05-29 13:29:16', 'Hat'),
			('2022-05-30 13:29:16', 'Glasses')
	`)
	if err != nil {
		t.Fatal(err)
	}

	cursors := postgres.Cursors{} // passing empty cursors, meaning we want the first page
	limit := 5

	pp, nextCursors, err := store.GetProducts(context.TODO(), cursors, limit)
	if err != nil {
		t.Fatal(err)
	}

	// we shouldn't get any `Prev` cursor because there is no previous page, we are on the
	// first page. We should get a cursor for the next page, which should be the creation date
	// of the last row we receive
	expectedCursors := postgres.Cursors{Next: "2022-05-26T13:29:16Z"}

	if diff := cmp.Diff(expectedCursors, nextCursors); diff != "" {
		t.Errorf("cursors are different (-want +got):\n%s", diff)
	}

	// we expect to receive the first 5 products sorted by creation date in descending order
	expectedProducts := []product.Product{
		{Name: "Glasses"},
		{Name: "Hat"},
		{Name: "Shoes"},
		{Name: "Socks"},
		{Name: "Pants"},
	}

	ignoreOpts := cmpopts.IgnoreFields(product.Product{}, "ID", "CreatedAt")
	if diff := cmp.Diff(expectedProducts, pp, ignoreOpts); diff != "" {
		t.Errorf("products are different (-want +got):\n%s", diff)
	}
}

In this test, we are inserting 8 rows and passing no cursors with a limit of 5. So we should receive the first 5 rows sorted by creation date in descending order., and we should receive only a Next cursor meaning there is no previous page, but a next page.

We can combine all the remaining scenarios in a table test since all will be using the same setup.

  1
  2
  3
  4
  5
  6
  7
  8
  9
 10
 11
 12
 13
 14
 15
 16
 17
 18
 19
 20
 21
 22
 23
 24
 25
 26
 27
 28
 29
 30
 31
 32
 33
 34
 35
 36
 37
 38
 39
 40
 41
 42
 43
 44
 45
 46
 47
 48
 49
 50
 51
 52
 53
 54
 55
 56
 57
 58
 59
 60
 61
 62
 63
 64
 65
 66
 67
 68
 69
 70
 71
 72
 73
 74
 75
 76
 77
 78
 79
 80
 81
 82
 83
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139


func TestGetProducts(t *testing.T) {
	db := test.SetupDB(t)
	test.CreateProductTable(t, db)

	store := postgres.NewStore(db)

	_, err := db.Exec(`
		INSERT INTO products(created_at, name)
		VALUES
			('2022-05-23 13:29:16', 'Shirt'),
			('2022-05-24 13:29:16', 'Polo'),
			('2022-05-25 13:29:16', 'T-Shirt'),
			('2022-05-26 13:29:16', 'Pants'),
			('2022-05-27 13:29:16', 'Socks'),
			('2022-05-28 13:29:16', 'Shoes'),
			('2022-05-29 13:29:16', 'Hat'),
			('2022-05-30 13:29:16', 'Glasses')
	`)
	if err != nil {
		t.Fatal(err)
	}

	testCases := []struct {
		desc             string
		cursors          postgres.Cursors
		limit            int
		expectedProducts []product.Product
		expectedCursors  postgres.Cursors
	}{
		{
			desc:  "first page limit 5",
			limit: 5,
			expectedProducts: []product.Product{
				{Name: "Glasses"},
				{Name: "Hat"},
				{Name: "Shoes"},
				{Name: "Socks"},
				{Name: "Pants"},
			},
			expectedCursors: postgres.Cursors{
				Next: "2022-05-26T13:29:16Z",
			},
		},
		{
			desc:  "Next page limit 3",
			limit: 3,
			cursors: postgres.Cursors{
				Next: "2022-05-28T13:29:16Z",
			},
			expectedProducts: []product.Product{
				{Name: "Socks"},
				{Name: "Pants"},
				{Name: "T-Shirt"},
			},
			expectedCursors: postgres.Cursors{
				Prev: "2022-05-27T13:29:16Z",
				Next: "2022-05-25T13:29:16Z",
			},
		},
		{
			desc:  "going forward last page limit 3",
			limit: 3,
			cursors: postgres.Cursors{
				Next: "2022-05-26T13:29:16Z",
			},
			expectedProducts: []product.Product{
				{Name: "T-Shirt"},
				{Name: "Polo"},
				{Name: "Shirt"},
			},
			expectedCursors: postgres.Cursors{
				Prev: "2022-05-25T13:29:16Z",
			},
		},
		{
			desc:  "Go back first page limit 3",
			limit: 3,
			cursors: postgres.Cursors{
				Prev: "2022-05-22T13:29:16Z",
			},
			expectedProducts: []product.Product{
				{Name: "T-Shirt"},
				{Name: "Polo"},
				{Name: "Shirt"},
			},
			expectedCursors: postgres.Cursors{
				Prev: "2022-05-25T13:29:16Z",
			},
		},
		{
			desc:  "Go back limit 3",
			limit: 3,
			cursors: postgres.Cursors{
				Prev: "2022-05-24T13:29:16Z",
			},
			expectedProducts: []product.Product{
				{Name: "Socks"},
				{Name: "Pants"},
				{Name: "T-Shirt"},
			},
			expectedCursors: postgres.Cursors{
				Next: "2022-05-25T13:29:16Z",
				Prev: "2022-05-27T13:29:16Z",
			},
		},
		{
			desc:  "Go back last page limit 3",
			limit: 3,
			cursors: postgres.Cursors{
				Prev: "2022-05-27T13:29:16Z",
			},
			expectedProducts: []product.Product{
				{Name: "Glasses"},
				{Name: "Hat"},
				{Name: "Shoes"},
			},
			expectedCursors: postgres.Cursors{
				Next: "2022-05-28T13:29:16Z",
			},
		},
	}
	for _, tC := range testCases {
		t.Run(tC.desc, func(t *testing.T) {
			pp, nextCursors, err := store.GetProducts(context.TODO(), tC.cursors, tC.limit)
			if err != nil {
				t.Fatal(err)
			}

			if diff := cmp.Diff(tC.expectedCursors, nextCursors); diff != "" {
				t.Errorf("cursors are different (-want +got):\n%s", diff)
			}

			ignoreOpts := cmpopts.IgnoreFields(product.Product{}, "ID", "CreatedAt")
			if diff := cmp.Diff(tC.expectedProducts, pp, ignoreOpts); diff != "" {
				t.Errorf("products are different (-want +got):\n%s", diff)
			}
		})
	}
}

So these tests insert a bunch of products, call GetProducts with different cursors and limits, and check the result. We could also test the validations separately.

One thing to note is that, it is a common practice to Base64 encode the cursors.

I hope this was helpful. If you have any remarks, please let me know by dropping a comment. Any feedback would be appreciated.

The complete code can be found here