Cursor based pagination for table without a unique and sequential id column?

I’m investigating using cursor-based pagination. I have the following (postgres) table:

CREATE TABLE label (
    tenantId VARCHAR(256) NOT NULL,
    tagFieldName VARCHAR(256) NOT NULL,
    tagId VARCHAR(256) NOT NULL,
    "key" VARCHAR(256) NOT NULL,
    "value" VARCHAR(256) NOT NULL,
    PRIMARY KEY (tenantId, tagFieldName, tagId, "key"),
    CONSTRAINT fkTag FOREIGN KEY (tenantId, tagFieldName, tagId) REFERENCES tag (tenantId, fieldName, id)
);

and had begun to sketch out the pagination query (not tested):

CriteriaBuilder criteriaBuilder = entityManager
            .getCriteriaBuilder();

CriteriaQuery<Label> criteriaQuery = criteriaBuilder
        .createQuery(Label.class);

Root<Label> root = criteriaQuery.from(Label.class);

final Predicate tenantIdPredicate = criteriaBuilder.equal(root.get("tenantId"), "jim");
final Predicate fieldNamePredicate = criteriaBuilder.equal(root.get("fieldName"), "work");
final Predicate idPredicate = criteriaBuilder.equal(root.get("id"), "work1");

CriteriaQuery<Label> select = criteriaQuery
        .select(root).where(criteriaBuilder.and(tenantIdPredicate, fieldNamePredicate, idPredicate));

criteriaQuery.orderBy(
        criteriaBuilder.asc(root.get("tenantId")),
        criteriaBuilder.asc(root.get("fieldName")),
        criteriaBuilder.asc(root.get("id")),
        criteriaBuilder.asc(root.get("key")));

TypedQuery<Label> typedQuery = entityManager.createQuery(select);

typedQuery.setMaxResults(100);

List<Label> labels = typedQuery.getResultList();

I’ve been reading these posts:

https://slack.engineering/evolving-api-pagination-at-slack-1c1f644f8e12

https://engineering.mixmax.com/blog/api-paging-built-the-right-way/

https://coderwall.com/p/lkcaag/pagination-you-re-probably-doing-it-wrong

which both state that the cursor should be a unique, sequential column to paginate on.

However, my table does not have an auto-incrementing sequential primary key.

Instead it’s primary key is a composite key of these four fields, which together are unique, but not sequential:

PRIMARY KEY (tenantId, tagFieldName, tagId, "key"),

Will I be able to implement a cursor-based pagination approach?

And also maybe allow users to specify a sort column, such as the sorting on the ‘value’ column?

Update: Based on @Lesiak’s comment, I believe the following queries may be close to what I want, keeping in mind that the tenantId, tagFieldName and tagId parts of the primary key will be known (the client provides this), but the key field of the primary key will not be known, and assuming the client has asked to sort on the value field.

-- First page
SELECT *
FROM label
WHERE
tenantId = 'jim' AND tagFieldName = 'work' AND tagId = 'work1'
ORDER BY value, tenantId, tagFieldName, tagId, key
LIMIT 2;

-- Next page (assuming the last result of the first query returned a record with the key `label-2-key` and and value `label-2-value`) 
SELECT *
FROM label
WHERE
tenantId = 'jim' AND tagFieldName = 'work' AND tagId = 'work1'
AND
(value, key) > ('label-2-value', 'label-2-key')
ORDER BY value, tenantId, tagFieldName, tagId, key
LIMIT 2;

Unrolling the row value expressions for the second (next page) query results in:

SELECT *
FROM label
WHERE
tenantId = 'jim' AND tagFieldName = 'work' AND tagId = 'work1'
AND
value > 'label-2-value' OR ((value = 'label-2-value') AND (key > 'label-2-key'))
ORDER BY value, tenantId, tagFieldName, tagId, key
LIMIT 2;

Which would translate to a JPA query something like (untested):

CriteriaBuilder criteriaBuilder = entityManager
            .getCriteriaBuilder();

CriteriaQuery<Label> criteriaQuery = criteriaBuilder
        .createQuery(Label.class);

Root<Label> root = criteriaQuery.from(Label.class);

final Predicate tenantIdEqualPredicate = criteriaBuilder.equal(root.get("tenantId"), tenantId);
final Predicate fieldNameEqualPredicate = criteriaBuilder.equal(root.get("fieldName"), fieldName);
final Predicate idEqualPredicate = criteriaBuilder.equal(root.get("id"), id);

// tenantId = 'jim' AND tagFieldName = 'work' AND tagId = 'work1'
Predicate primaryKeyPredicate = criteriaBuilder.and(tenantIdEqualPredicate, fieldNameEqualPredicate, idEqualPredicate);

final Predicate valueGreaterThanPredicate = criteriaBuilder.greaterThan(root.get("value"), "label-2-value");
final Predicate valueEqualPredicate = criteriaBuilder.equal(root.get("value"), "label-2-value");
final Predicate keyGreaterThanPredicate = criteriaBuilder.equal(root.get("key"), "label-2-key");

// value > 'label-2-value' OR ((value = 'label-2-value') AND (key > 'label-2-key'))
Predicate orderingPredicate = criteriaBuilder.or(
        valueGreaterThanPredicate, criteriaBuilder.and(valueEqualPredicate, keyGreaterThanPredicate));

CriteriaQuery<Label> select = criteriaQuery
        .select(root).where(
                criteriaBuilder.and(primaryKeyPredicate, orderingPredicate)); 

criteriaQuery.orderBy(
        criteriaBuilder.asc(root.get("value")),
        criteriaBuilder.asc(root.get("tenantId")),
        criteriaBuilder.asc(root.get("fieldName")),
        criteriaBuilder.asc(root.get("id")),
        criteriaBuilder.asc(root.get("key")));

TypedQuery<Label> typedQuery = entityManager.createQuery(select);

typedQuery.setMaxResults(Defaults.PAGE_SIZE);

List<Label> labels = typedQuery.getResultList();

My questions/concerns regarding this are:

The complexity that will result when the user specifies multiple sort fields, with some maybe in asc/desc order etc?
The user will also be able to specify filters for this request, for example ‘label exists’, ‘label key contains’ , ‘label key starts with’ etc, and how this will again add to the complexity of constructing the criteria objects?

Answer

Yes, you can implement keyset pagination with a composite key. But JPA is not ideal tool for that – you’ll have to construct your predicates yourself.

Details:

Let’s modify an example from a framework that natively supports keyset pagination: https://www.jooq.org/doc/latest/manual/sql-building/sql-statements/select-statement/seek-clause/

SELECT id1, id2, value
FROM t
WHERE (value, id1, id2) > (2, 533, 444)
ORDER BY value, id1, id2
LIMIT 5

This is the kind of query you want to generate with your implementation. Notice it first orders by a user-selected field, and then by all parts of composite id.

The problem is that JPA does not support row value expression predicates (and only some databases support them). You have to unroll them yourself:

(A, B) > (X, Y)

becomes:

(A > X)
  OR ((A = X) AND (B > Y))

As your PK has 4 fields, the resulting predicate will be quite long.

Advertisement

Answer