Have you considered no-offset pagination?

[ieugen]

Hi,

First of all: nice library. I haven't used it yet but I'm planning to use it when I get to a new project.
Have you considered keyset/seek pagination? Offset based pagination has performance issues with big tables.

[1] https://use-the-index-luke.com/no-offset

[igdianov]

@ieugen Thank you for feedback. The keyset pagination method does offer significant performance improvements.

Keyset is efficient than an OFFSET based paging/scrolling because this approach can scroll to the next and previous page in O(log n), whereas using OFFSET results in a complexity of O(n), thus making it harder to get to latter pages in big data sets. This is due to how a keyset paginated query can efficiently traverse an index on the DBMS side. Using OFFSET paging requires actually counting tuples that should be skipped which is less efficient.

On the surface, it is relatively simple to to do on the client side using existing where argument in select field with criteria and corresponding sort order and by implementing support for a special argument in select field to specify maxResults in order to limit number of records in the query. The harder part is that the order by clause must establish a deterministic row sequence. That is a prerequisite to using a simple range condition for the page breaks.

Without a deterministic order by clause, the database by definition does not deliver a deterministic row sequence. The only reason you usually get a consistent row sequence is that the database usually executes the query in the same way. Without deterministic order, the database could in fact shuffle the rows having the same values and still fulfill the order by clause. The database may also shuffle the result because it might utilize parallel query execution. That means that the same execution plan can result in a different row sequence because the executing threads finish in a non-deterministic order.

To create deterministic row order, we need to extend the order by clause with the primary key field to get a deterministic row sequence. Furthermore, we must apply the “comes after” logic to sort order columns together to get the desired result:

For example, using Jpa query to get the first page result with 10 rows:

SELECT sale FROM Sales sale
ORDER BY sale.date ASC, sale.id ASC
FETCH FIRST 10 ROWS ONLY

In order to go to next page, the where clause must consist of two parts and use values from the last result. The first part considers the sale dates not seen in the last result and uses a greater than (>) condition which will use the database index if needed to efficiently retrieve records. The second part of the where clause removes the excess rows that were already shown on the previous page using primary key index.

SELECT sale FROM Sales sale
WHERE sale.date > : ?result[9].date OR (
    sale.date = : ?result[9].date AND
    sale.id > : ?result[9].id
)
ORDER BY sale.date ASC, sale.id ASC
FETCH FIRST 10 ROWS ONLY

Go to previous page:

SELECT sale FROM Sales sale
WHERE sale.date < : ?result[0].date OR (
    sale.date = : ?result[0].date AND
    sale.id < : ?result[0].id
)
ORDER BY sale.date ASC, sale.id ASC
FETCH FIRST 10 ROWS ONLY

In summary, to solve the problem, the Keyset paged query builder should augment the order and where clauses with primary key field in order to keep deterministic row order in the result.

Without the sort order, we can use the primary key field value for after and before pages query using where argument because the library already sets primary key sort order by default.

In the first step, I can add support to specify maxResults argument to pass to Jpa query and augment sort order builder to always add primary key field to guarantee deterministic sort order in the result. After that, we can play with existing query where arguments on a test data set to create a better use case for keyset based pagination parameters.

Let me know your thoughts...

[ieugen]

That sounds about right. Very detailed explanation. For Postgresql you can use a special sintax: the row syntax. But thatcis a detail.

Right now I am working with Blaze persistence to do keyset (working on a POC). I think it is a good source of inspiration. It has good documentation and I believe some tests as well.

https://blazebit.com/blog/2016/pagination-blog-post.html

[ieugen]

Regarding the implementation, I think it is important to note:
Only one sort direction is allowed. All asc or all desc.

Serialization of the columns used for cursor should happen.

I concatenate the values using a . character. I turn longs and ints to hexstring and strings to base64 url safe strings.

Cursor looks like a JWT token.

I don't encode the column names in the token to make it shorter.

Each entity has only a few fields that can be used to sort by and I maintain the list hardcoded on the server.

Since in UI I allow to sort by only one column at a time (does not make sense to do more in JS, not building a full spreadsheet app) i can skip from including in token the un used columns.

So token looks like this for me:

Aa233ff..f0077bb

[igdianov]

@ieugen So, I am thinking it would be relatively simple to make test case based on the example from https://blazebit.com/blog/2016/pagination-blog-post.html. The only requirement to enable keyset method work is to have an entity field that with the value generated from timestamp or auto-incremented when record inserted in the database to keep the consistent sort order.

To make the entity eligible for keyset pagination, the attribute must be annotated with something like @GraphQLKeysetPageId.

Then SchemaBuilder implementation can augment the fields in the page argument to pass optional keysetPageId parameter that should be extracted from the data received from the past result.

Then QueryBuilder implementation can detect and apply keysetPageId to criteria expression together with maxResults to limit records in the query.

For this method to work with the library, the client application must keep the same sort order between keyset page requests.

Test case concept outline:

// initial query using offset pagination
PagedList<Cat> page3 = cbf.create(em, Cat.class)
    .orderByAsc("id") // unique ordering is required for pagination
    .page(6, 3)
    .withKeysetExtraction(true)
    .getResultList();

// keyset pagination for querying the next page
PagedList<Cat> page4 = cbf.create(em, Cat.class)
    .orderByAsc("id")
    .page(page3.getKeysetPage(), 9, 3)
    .withKeysetExtraction(true)
    .getResultList();

// keyset pagination for querying the previous page
PagedList<Cat> page2 = cbf.create(em, Cat.class)
    .orderByAsc("id")
    .page(page3.getKeysetPage(), 3, 3)
    .withKeysetExtraction(true)
    .getResultList();

TODO:

• Design GraphQL Keyset schema fields
• Implement failing unit tests with data
• Implement Keyset pagination

[ieugen]

From my understanding, you can sort by many columns, the pagination needs to take this into account.
Usually the ID is last and you get a column like name.

We need to send the cursor to the client and encode in the cursor this information somehow.