Alex Cole

a year ago

Fully Reactive Pagination

Many backends support paginating over large datasets. Some backends reactively push updates to the client when the data changes, but few support reactivity and pagination at the same time.

Convex is the reactive backend-as-a-service for modern application developers. Our reactive pagination allows developers to build apps with “Load More” buttons and “infinite scroll” UIs without giving up the automatic reactivity they love.

Reactive pagination presents some unique technical challenges. What happens if items are added or removed from a page? Will pages overlap? Will items be missed or rendered twice?

This post describes Convex’s solutions to these problems. But first, let’s start with the basics.

Offset Pagination

The simplest form of pagination is offset pagination. In this model, clients request results in incremental pages based on:

1. The number of items to load in this page.
2. An offset to begin this page at.

For example, if we wanted to paginate a large list of fruits, we could load the first 5 items with an API call like getFruits({ offset: 0, numItems: 5}):

[
  "Apple",
  "Banana",
  "Currant",
  "Durian",
  "Elderberry"
]

Then to load the next 5 we could call getFruits({ offset: 5, numItems: 5}):

[
  "Fig",
  "Grapefruit",
  "Huckleberry",
  "Jackfruit",
  "Kiwi"
 ]

One problem with this model is that it performs poorly if items are added or removed between API calls. For example, say that "Elderberry" is removed from the list after the first API call. Then "Grapefruit" will become the sixth item in the list and the start of our second page.

Now our second page loaded with getFruits({ offset: 5, numItems: 5}) would become:

[
  "Grapefruit",
  "Huckleberry",
  "Jackfruit",
  "Kiwi",
  "Lemon"
 ]

Putting these pages together, the client would see a list like:

       ┏ Apple
       ┃ Banana
page 1 ┫ Currant
       ┃ Durian
       ┗ Elderberry ← Removed after page 1 is loaded
         Fig
       ┏ Grapefruit
       ┃ Huckleberry
page 2 ┫ Jackfruit
       ┃ Kiwi
       ┗ Lemon
         ...

Note that "Fig" isn’t in either page! It was the 6th item when we loaded page 1, so it wasn’t included. By the time we loaded the 2nd page, it moved to the 5th position so it wasn’t included on page 2 either.

These types of correctness issue are a reason that many apps use cursor-based pagination instead.

Cursor-based Pagination

The standard approach to pagination uses cursors to identify where a page begins and ends within the list. Cursors are opaque strings that encode positions in a list.

Every time a client requests a page of items, they receive a cursor to continue the pagination along with their results. For example calling getFruits({ numItems: 5 }) could return:

{
  page: [
    "Apple",
    "Banana",
    "Currant",
    "Durian",
    "Elderberry"
  ],
  continueCursor: "u1oU8i23WMATVwA2CneZ"
}

If the client wants to load the next page, they can include the continuation cursor from the last page in their request to continue where they left off. In this example they would call getFruits({ numItems: 5, cursor: "u1oU8i23WMATVwA2CneZ" }) and get:

{
  page: [
    "Fig",
    "Grapefruit",
    "Huckleberry",
    "Jackfruit",
    "Kiwi"
  ],
  continueCursor: "y45NqH6EAwknDtdeF7Y7"
}

Client-side these can be concatenated together to form a single list. Visually, this looks like

       ┏ Apple
       ┃ Banana
page 1 ┃ Currant
       ┃ Durian
       ┗ Elderberry
       ┏ Fig
       ┃ Grapefruit
page 2 ┃ Huckleberry
       ┃ Jackfruit
       ┗ Kiwi
         ...

The Challenge of Reactivity

Most paginated apps are nonreactive; if you load a page of items, the client won’t notice if those items change. In Convex, all queries are automatically reactive. If the underlying data changes, Convex automatically reruns the query function and pushes a new result to the client. Naively paginating in this model can cause some interesting bugs to show up.

To see the problem, imagine that a user inserts "Coconut" into the list alphabetically after "Banana".

In our example, the client loaded 2 pages by calling getFruits({ numItems: 5 }) and getFruits({ numItems: 5, cursor: "u1oU8i23WMATVwA2CneZ" }). The first 5 elements of the list have changed, so getFruits({ numItems: 5 }) will recompute and automatically push the new results to the client. Now it returns:

{
  page: [
    "Apple",
    "Banana",
    "Coconut",
    "Currant",
    "Durian"
  ],
  continueCursor: "6FybVkA6X0abzz0XCVP3"
}

Now “Durian” is the 5th item of the list and the cursor "6FybVkA6X0abzz0XCVP3" refers to the position after “Durian”.

The second query for getFruits({ numItems: 5, cursor: "u1oU8i23WMATVwA2CneZ" }) hasn’t changed because the 5 items after "u1oU8i23WMATVwA2CneZ" are the same as before.

Now, our list looks like this:

       ┏ Apple
       ┃ Banana
page 1 ┫ Coconut ← New item inserted
       ┃ Currant
       ┗ Durian
         Elderberry
       ┏ Fig
       ┃ Grapefruit
page 2 ┫ Huckleberry
       ┃ Jackfruit
       ┗ Kiwi
         ...

Now “Elderberry” is between our two pages! It dropped off of page 1 when we added the new item but page 2 still begins at the same spot. From a user’s perspective, they would no longer see “Elderberry” in UI!

Similarly, if we had instead removed an item from the list (say "Currant") the two pages would overlap:

       ┏   Apple
       ┃   Banana
page 1 ┫   Durian
       ┃   Elderberry
       ┗ ┏ Fig
         ┃ Grapefruit
page 2 ━━┫ Huckleberry
         ┃ Jackfruit
         ┗ Kiwi
           ...

This also would create a confusing user experience. Why is "Fig" listed twice?

Many apps solve these problems with simple heuristics like “remove the duplicates and hope the data doesn’t change too much while paginating.” At Convex, we believe that correctness should come for free, so this won’t fly.

Making it Correct

To ensure that the concatenated list never has duplicates or misses items, we have to do something a little different. The key insight is to pin the endpoints of each page.

In this example we initially had that:

Page 1:

• Start: beginning of the list
• End: cursor "u1oU8i23WMATVwA2CneZ"

Page 2:

• Start: cursor "u1oU8i23WMATVwA2CneZ"
• End: cursor "y45NqH6EAwknDtdeF7Y7"

There was a gap between the pages because the end of page 1 moved to no longer match the start of page 2. If we can instead keep these endpoints constant, this won’t be a problem.

In our original example, the start of each page was a constant (it’s the cursor argument to the function), but the end of the page varied based on what position was 5 elements after the start.

In this new model, Convex will “remember” the end of each page as well. Whenever the query is recomputed, Convex ignores the numItems parameter and instead returns all items until the end cursor. This switches each page from a limit query (fetch 5 items) into a range query (fetch between cursors).

In our example, if we add "Coconut" to the list, page 1 would recompute and become:

{
  page: [
    "Apple",
    "Banana",
    "Coconut",
    "Currant",
    "Durian",
    "Elderberry"
  ],
  continueCursor: "u1oU8i23WMATVwA2CneZ"
}

Now page 1 has 6 items! It initially had 5, but now it grew to include a 6th. Putting this together with page 2, we can see that our pages continue to have no gaps or overlap:

       ┏ Apple
       ┃ Banana
page 1 ┃ Coconut ← New item inserted
       ┃ Currant
       ┃ Durian
       ┗ Elderberry
       ┏ Fig
       ┃ Grapefruit
page 2 ┃ Huckleberry
       ┃ Jackfruit
       ┗ Kiwi
         ...

Similarly, if we instead remove "Currant" from the list, page 1 will keep its endpoint and shrink to 4 items:

       ┏ Apple
       ┃ Banana
page 1 ┃ Durian
       ┗ Elderberry
       ┏ Fig
       ┃ Grapefruit
page 2 ┃ Huckleberry
       ┃ Jackfruit
       ┗ Kiwi
         ...

No matter what happens, the user will see a valid prefix of the list!

Convex implements this logic to pin the endpoints of each page completely internally. When you load a paginated query, Convex internally stores the endpoint of the page. Any time the query function is rerun, Convex uses that endpoint; no additional configuration needed!

Using it!

Using Convex’s reactive pagination is a breeze. To write a paginated query function, just call .paginate on the query:

// in convex/fruits.js
export const list = query(async ({ db }, { paginationOpts }) => {
  return await db.query("fruits").paginate(paginationOpts);
});

Then, you can load pages of this query with our usePaginatedQuery React hook:

const { results, status, loadMore } = usePaginatedQuery(api.fruits.list, {}, {
  initialNumItems: 5,
});

To learn more about Convex pagination check out the docs. Convex handles the complexity of making it correct and reactive so you don’t have to!