Find gap in sequence with Java Persistence Query Language

Question

In my table I have a column that acts like a sequence, only it's not auto incremented, the incrementation is done in code.

A crude representation of the table would be like this:

id	fruit	sequence
1	apple	1
2	apple	2
3	apple	3
4	apple	10
5	orange	1
6	orange	2

As you can see I have gaps in my sequence column and I want to find that gap, where it starts and where it ends. For example, make a query that finds the start of the gap with fruit = apple and then the end of the gap, like so: "4-9"

Right now I use this solution with native query in JPA: which works great but is only usable for mysql, can this be done with entitymanager and JPQL? The reason behind this is to be able to switch from one type of database to another.

Yuriy Tsarkov · Answer 1 · 2021-04-24T20:18:36.003

The short answer is no. JPA and JPQL is not intended for a purposes like yours. And the solution you follow is not about JPA but about MySQL issue and it's tagged correspondly. Why don't you move this calculations to the service layer? In this case you will automatically get rid of DBMS-dependency problem. For instance:

public interface FruitRepository extends CrudRepository<Fruit, Long> {
  
  @Query("select f.sequence from Fruit f where f.fruit = :name order by f.sequence"
  List<Long> getSequencesByFruitName(@Param("name") String fruitName);
}

I added ordering here only to be sure that elements will be returned ascendingly. If this is unreachable case for you then just remove it from the query.

Ok then, at the Service layer we'll implement the calculation:

@Service
public class FruitServiceImpl implements FruitService {

  private FruitRepository fruitRepository;

  public FruitServiceImpl(FruitRepository fruitRepository) {
    this.fruitRepository = fruitRepository;
  }

  public void logic() {
    ********************
    List<Long> list = fruitRepository.getSequencesByFruitName("apple");
    List<Pair<Long, Long>> gaps = new ArrayList<>();
    for (int i = 0; i < list.size() - 1; i++) {
      if (list.get(i + 1) > list.get(i) + 1) {
        gaps.add(Pair.of(list.get(i) + 1, list.get(i + 1) - 1));
      }
    }
    ********************    
  }
}

That's one way of doing it but the issue here is performance. Having 20000 items in-memory is much slower than doing an sql query. But I guess that always will be the case... Thanks though! — Keystone Jack, Apr 25 '21 at 17:13

score 1 · Answer 2 · answered Apr 26 '21 at 17:06

1

You can find the 'lowest' gap in the sequence using the following query:

SELECT MIN(s1.sequence) + 1
FROM FruitSequence s1
WHERE NOT EXISTS(
    SELECT id FROM FruitSequence s2
    WHERE s1.fruit = s2.fruit
    AND s1.sequence + 1 = s2.sequence)

You can use this query repeatedly to get subsequent free ids. If using Hibernate, you could even use an unrelated join in place of the EXISTS operator.

answered Apr 26 '21 at 17:06

crizzis

9,978
2
28
47

This would not get the range , only the first and lowest gap, right? – Keystone Jack Apr 26 '21 at 17:10
Right, although having obtained the low end of the range, it's easy to write a (very similar) query to find the high end – crizzis Apr 26 '21 at 17:13
I guess, but if there are multiple gaps in the sequence it becomes a bit trickier... – Keystone Jack Apr 26 '21 at 17:16
How so? You're looking for the lowest sequence number greater than the low end that doesn't have a predecessor (as opposed to a successor in the above query). The number of gaps doesn't matter. – crizzis Apr 26 '21 at 17:18
Let say that you first find sequence 1 through 3, which can be done with MIN and MAX. But then you have a gap at 6-10 as well. Which I guess is not that difficult since you can query multiple time. – Keystone Jack Apr 26 '21 at 17:46

Find gap in sequence with Java Persistence Query Language

2 Answers2