Pagination implementation for real-life database

[mattecapu]

In all the examples I can find, paginated queries are made against a mockup database which is just a JS array, and thus it is simply passed through connectionFromArray to return the correct paginated result (like the Star Wars example mentioned in the README).
For a real-life database, query all records and then pass them to connectionFromPromisedArray doesn't seem to be a good solution, as it will easily break your perfomance/crash your server as soon as you're doing anything at (even modest) scale

So what solutions should you use to avoid insane database fetching?

(I'm using a SQL database but I think a good solution to this problem applies to pretty much every not-a-js-array dbms)

[OlegIlyenko]

Recently @chandu0101 created a nice and relatively big example of a relay application which uses MongoDB and sangria (scala GraphQL implementation).

If you don't mind looking at some scala code, then I would suggest to check out this function:

https://github.com/chandu0101/sri-sangria-example/blob/master/server/src/main/scala/sri/sangria/mongoserver/services/BaseService.scala#L52-L99

It creates a relay Connection which is based on MongoDB query. It also properly handles relay-style pagination and the result set, which comes from the DB, always contains only relevant documents. This particular example uses mongo's skip and limit to archive this. But I can also imagine other strategies to do this - for instance using an ID-based cursors which would be even more efficient.

Even though this example uses sangria-relay, conceptually it is very similar to reference implementation.

[GuillaumeLeclerc]

From all the solutions I found on the internet (including this one). It seems it does not work if data is inserted in the database during the lifetime of a cursor.

Am I wrong ?

Is there a generic solution ?

[GuillaumeLeclerc]

I thought about a solution to solve the data insertion:

• If there is no before nor after cursor I execute the database query but I only select the Ids, not the content. generate a new queryId (uuidv4) and save the Id's I get to a redis hastable where the key is the queryId
• If there is a cursor I extract the queryId from the cursor and get the list of Id's from the database
• I use the query args to compute which Id's the client is interested in
• I make a database query including the corresponding Ids
• Return the result

I have a compliant implementation for Mongoose database I can share if anyone interested.

My only concern Is how long should I keep the queries in my redis server.

[sibelius]

@mattecapu this package relay-mongodb-connection creates relay connection from mongodb cursors, it also uses skip and limit

[mattecapu]

Thank you @sibelius and @OlegIlyenko, your links were a good starting place for understanding what was going on in the creation of a ConnectionType response.

My solution was to not use createConnection* utilities but to create a ConnectionType response by myself.

Essentially I encode information about the ordering field (i.e. the ID) in the cursor and then use that to query results with ID >= or <= than cursor. The first and last parameters are handled with some clever LIMITing and order reversing.

My actual use case was a little more complicated because I'm fetching from multiple tables. Thus after retrieving the minimum required records I'm doing an additional round of sorting and cutting.

I'd be happy to provide some code examples if someone needs them.

[sibelius]

@mattecapu I think u should provide some code examples to help people understand better how to implement a cursor

[mattecapu]

Well the point is, if you implement a ConnectionType for an endpoint you just need to

• accept connectionArgs parameters
• return a suitable response in the shape { edges: [{ cursor, node }], pageInfo: { hasNextPage, hasPreviousPage, startCursor, endCursor }

Cursors can be any string you want. Normally Relay defaults to arrayconnection:<id> converted to base64 to make it opaque (you shouldn't actually relay on the implementation details of the cursors).

I used <type_name>:<id> converted to base64 as cursors.

Then a request to my endpoint look like this

endpoint(after: "sdflkjsdlfkjslkdf", first: 10) {
   # stuff
}

Basically, any request described by the specification is supported.

Thus when I get the request I process it in the following way:

1. Start from the greedy query: SELECT * FROM table
2. If the after argument is provided, add id > parsed_cursor to the WHERE clause
3. If the before argument is provided, add id < parsed_cursor to the WHERE clause
4. If the first argument is provided, add ORDER BY id DESC LIMIT first+1 to the query
5. If the last argument is provided, add ORDER BY id ASC LIMIT last+1 to the query
6. If the last argument is provided, I reverse the order of the results
7. If the first argument is provided then I set hasPreviousPage: false (see spec for a description of this behavior).
8. If no less than first+1 results are returned, I set hasNextPage: true, otherwise I set it to false.
9. If the last argument is provided then I set hasNextPage: false (see spec for a description of this behavior).
10. If no less last+1 results are returned, I set hasPreviousPage: true, otherwise I set it to false.

Using this "algorithm", only the needed data is fetched. While after and before can be both set, I make sure first and last args are treated as mutually exclusive to avoid making a mess. The spec itself discourage making requests with both the arguments set.

Notably, I return an object with the shape described above (and in the linked spec) and I don't use the connectionFromArray helper, which expects a raw collection to slice accordingly to the args.

EDIT: The above algorithm produces array with different orders depending on which of first or last is used to paginate. This is against the specification, so there should be one more step:

11. Re-order results in a consistent manner (e.g. by creation date)

Thanks to @Sytten for bringing this problem to my attention.

EDIT2: The above ordering reflects pagination, not chronological order. Hence first is interpreted as 'first to be displayed', not 'first chronologically'. Therefore, you might want to swap ASC and DESC in step (4) and (5). Thanks to @Sytten for bringing this problem to my attention.

[wincent]

That's a really great write-up @mattecapu. I'm going to close this out now but that is exactly the kind of thing that would work well in the documentation (could be something in a code comment, in the README, or we could start an examples folder). Would be happy to look at a PR adding something like that.

[GuillaumeLeclerc]

@mattecapu It seems the algorithm does not work if there was an deletion in the database between two paginated queries and/or if we want to sort by anything else than Id's right ?

[oexza]

@mattecapu what happens when the ids are not ordered? i.e they are UUIDs, id > paresedValue will be useless.

[mattecapu]

Sorry @GuillaumeLeclerc I lost your question in a notification misunderstanding with GitHub.
I'm going to address your question together with @oexza new comment.

As laid out in the comment above, my algorithm as both the limitations you guys noticed, but we can easily generalize it to overcome them.
My idea is to use creation timestamps as "order-providers", instead of abusing of the id field, which by the way, isn't guaranteed to be sequential anyway (in my specific use case, it was).

To support dynamic data getting deleted or added inbetween queries, paginating with creationTime works like a charm, especially with Relay caching mechanism.

Eventually, we can provide a further generalization by not fixing an order-provider field but let it be dynamic, effectively allowing a lot of different orders on the data, which can come in handy. This is pretty simple to implement too, but gets complicated once you have to support dynamic data.
I supect there's no silver bullet for this use case, but I might be wrong.

@wincent I'll see what I can do! Thanks for the appreciation.

[joonhocho]

I came across this issue and I wanted to share a Node.js library that I created a while ago.
https://github.com/joonhocho/graphql-relay-connection
It helps you easily create a custom relay connections.
You can create connections for MongoDB, simple number arrays, etc by providing few functions.
I hope this can help.

[Naoto-Ida]

@mattecapu Great post! Just wanted to say it helped out a lot. We had some tweaking to do since we accept arguments other than the Relay args spec.

[Naoto-Ida]

Everything was working great with @mattecapu's solution,
but I ran into one rare situation as such and am in quite a pickle...
wondering if any of you have run into this issue.

We have one query for events that returns data in a specific order.
This specific order, which is passed as part of an SQL statement, includes things like how many times that event's page has been viewed, whether it has an promotional image, etc. Basically about 5 *** DESCs in ORDER BY.

We have an events query like this:

{
  viewer {
    events(first: 1, inCountry: Japan) {
      edges {
        node {
          id
          name
        }
      }
    }
  }
}

first and last can be dealt with as addressed above; flip all of the multiple ORDER BY DESC to ORDER BY ASC.

But when you introduce after & before, it is very difficult to serve the correct data that corresponds to the given Node ID, as due to the nature of our query, it is not as simple as saying event.id > 1 or event.createAt > xxxx when after & before are passed.