How to apply pagination on big database ?

[VincentClair]

If I want to apply pagination to some objects, the better way seems to be compatible with Relay.
I have read all specifications about relay, and seen that you have already implemented Connections and Nodes (this last one seems not to be mandatory, but hardly advise).

I think i must use ConnectionBuilder::connectionFromArraySlice directly, with the result of a query to my database (with doctrine) and the arguments (first, after, etc.). Must i pass something special like total number of entities ?

I have read too a discussion about adding arguments for filtering/ordering. graphql/graphql-relay-js#20
Have you some advices for this ?

[mcg-web]

The builder alone can't answer to this issue. To be possible the logic of calculating the offset and length should be separate from the spliter it self. So you can use this parameter to get your results from db and then the builder could finish the work.

[VincentClair]

After a lot of reading, i came with this answer to my problem:
There is two types of pagination:

• "traditional" limit/offset pagination (or page number pagination)
• cursor based pagination, as proposed by Relay specification.

This last one, as said in facebook/relay#540, cursor "pagination model is optimized for infinite scrolling" and data that are heavily update. Think about a list with lot of news comments, etc. like in Facebook. If we scroll, we want to be sure to not repeat the same news: cursors is made for that, to be sure to continue were the last request ended, ever if there is some inserted or delete entries. Its important to noticed that cursor pagination method may apply to an natural ordering and unique field (id, micro timestamp, etc.).

Limit/offset pagination could be a solution when there is no such modifications on entries. It be acceptable if we get the same entry on the next page, because there is a new one during navigation.

So for now, I just implemented the easier solution. Here is an example of an entry point:

            users:
                type: "[User]"
                args:
                    limit:
                        description: "Pagination limit."
                        type: "Int"
                    offset:
                        description: "Pagination limit offset."
                        type: "Int"
                    orderBy:
                        description: "Ordering infos"
                        type: "[String]"
                    filterExpression:
                        description: "Filter expression to apply to users"
                        type: "String"
                resolve: "@=service('loyalty_user.user_manager').find(args)"

This is a temporary solution, as i must resolve a way to get back the number of results to send to client.
I think the next step is to introduce a UserPaginator object that give that number and the result of users entry point. So, I will not implemented Edges and PageInfo in Relay way, to keep a little more simple, because I don't need edges properties. I note that my pagination is applied directly to a "root repository"( if it is a good name), and not a collection depending from a root object.

Finally, i have an idea in mind to apply cursor pagination, but it need some heavy tests for performances:

• get all ids from table, applying filters and order by (could be cumbersome)
• cache the result
• apply {first/after} to get a set of ids (could be cumbersome)
• get relevant entries by querying with the set of ids.

Maybe someone has a point of view or a better solution ?

PS: I don't precise the way i made filters (filterExpression - https://github.com/K-Phoen/RulerZBundle) but i really opened to deal with that too.
Thanks for your help

[mcg-web]

I have an idea on the subject but a must first POC to be sure it works.

[mcg-web]

You can get a working example here mcg-web/graphql-symfony-doctrine-sandbox. In this file you can see how I create a pagination on the faction ships.

This query can be a good start:

query RebelsShipConnectionQuery {
  fake {
    name
    first: ships(first: 5) {
      ...shipConnection
    }
    withLastAndAfter: ships(last: 3, after: "YXJyYXljb25uZWN0aW9uOjE=") {
      ...shipConnection
    }
    withLastAndBeforeAndAfter: ships(last: 3, before: "YXJyYXljb25uZWN0aW9uOjQ=", after: "YXJyYXljb25uZWN0aW9uOjE=") {
      ...shipConnection
    }
    originalShips: ships(first: 2) {
      ...shipConnection
    }
    moreShips: ships(first: 3, after: "YXJyYXljb25uZWN0aW9uOjE=") {
      ...shipConnection
    }
  }
}

fragment shipConnection on ShipConnection {
  sliceSize
  edges {
    cursor
    node {
      name
    }
  }
  pageInfo {
    hasNextPage
    hasPreviousPage
  }
}

[VincentClair]

Thanks for your POC. I came the same way in my side. It works while there is no order by on query nor deletion on ships. So ConnectionBuilder::getOffsetWithDefault does not return an accurate value.
The problem I see with cursor based pagination is, if i apply a order on results, like ships by name, id order will change, so offset/limit will be irrelevant.
Am i right ?

[ooflorent]

The purpose of cursors is to drastically improve fetching performance on large paginated connections. Let's say we want to retrieve a list of events ordered by date. In SQL you would select them this way:

SELECT `id`, `date`, `type` FROM `events` 
WHERE `user_id` = :viewer
ORDER BY `date` DESC
LIMIT :offset, :page_size

If you want to read the 20th page, your DBAL needs to skip the 19th first pages which is really expensive, even with caching.

In contrario, in Relay, you can specify a cursor with after:

viewer {
  events(first: $first, after: $after) {
    edges {
      node {
        date
        type
      }
    }
  }
}

The following request could be translated by your GraphQL implementation into this SQL query:

SELECT `id`, `date`, `type` FROM `events` 
WHERE `user_id` = :viewer
  AND `id` > :after  -- This is the key part
ORDER BY `date` DESC
LIMIT 0, :page_size  -- Here it starts at 0

See the optimization? The database will only read page_size rows since the id is indexed and it would be easy to skip dead rows.

[VincentClair]

I really see the optimization, but i think it could not apply to my use case.
I'm not using connection type, but just a classic repository.

To work, cursor pagination must apply to data that dates is linked to id.
To clarify this, I take a sample with those data in database:

1  2016-03-12
2  2016-02-01
3  2016-04-30
4  2016-10-12
5  2016-03-07
6  2016-03-11
7  2016-01-12
8  2016-08-08
9  2016-07-25
10 2016-11-04

Dates does not follow id order. If i sort by date DESC, i get :

10 2016-11-04
4  2016-10-12
8  2016-08-08
9  2016-07-25
3  2016-04-30
1  2016-03-12
6  2016-03-11
5  2016-03-07
2  2016-02-01
7  2016-01-12

If i apply a pagination to show the 3 first items, i get:

10 2016-11-04
4  2016-10-12
8  2016-08-08

As I understand, if we want the next set of items, we query for first: 3 after: 8. Cursor is based on last ID of our current set.
So the corresponding SQL query would be:

SELECT `id`, `date`, `type` FROM `events` 
WHERE `id` > 8
ORDER BY `date` DESC
LIMIT 0, 3

But WHERE id > 8 give me only the item with id 9:

9  2016-07-25

But the good result for the next page should be:

9  2016-07-25
3  2016-04-30
1  2016-03-12

So id order need to follow sort order (here date).
This is why pagination cursor could be apply only on something like a couple id/creation date (or something more complicated, but with more database queries).
What is my mistake ?

[VincentClair]

We could also used date in place of id in where clause. But cursor must be based on a microtime datetime at least (see conflicts http://cramer.io/2011/03/08/building-cursors-for-the-disqus-api)

[mcg-web]

I'm closing this because not really a generic solution to this, feel free to reopen if needed :)