How to search the minimum free value

Question

I have a table like this:

create table thing (
  id bigint primary key auto_increment,
  code integer not null,
  description varchar(100)
);

The table usually has consecutives codes but the user has the posibility of change the generates code for other more convenient for him, so he can break the chain. Also he can remove some thing.

So, I'm trying to figure out how to get the first not used code.

For instance:

If I have 1, 2, I want to get 3
If I have 1, 2, 3, 50 and 51, I want to get 4.

I have thought in the next two queries which resolve my problem but none of them seems to be a good option.

The first one uses an exists which I think it is inefficient since it has quadratic order.

select min(code)+1 from thing t
where not exists (select * from thing where code = t.code + 1);

The second is impossible to implement on Hibernate HQL queries since I am trying to use a strange join clause t1.code = t2.code - 1

select min(t1.code)+ 1 
from thing t1 left join thing t2 on t1.code = t2.code - 1
where t2.id is null;

http://stackoverflow.com/questions/684106/find-the-smallest-unused-number-in-sql-server — Hugo Sousa, Feb 04 '15 at 23:59
It's a good related question, but it didn't solve my problem. The solutions includes Exists or strange left join that I can't use on Hibernate — JCalcines, Feb 05 '15 at 00:06
What are you going to do with the first 'unused' code once you get it? — Strawberry, Feb 05 '15 at 00:10
I want to suggest to the user to use that value, so he doesn't have to think about the new code for the `thing`. — JCalcines, Feb 05 '15 at 00:12

score 1 · Answer 1 · answered Feb 05 '15 at 09:10

How about this technique. Create a temporary table @values

DECLARE @values AS TABLE(value INT);

Fill it with all integers from 1 to MAX(code) + 1

DECLARE @limit AS INT;
SET @limit = (SELECT MAX(ISNULL(code, 0)) + 1 FROM thing);
DECLARE @i INT;
SET @i = 1;
WHILE (@i <= @limit)
BEGIN
    INSERT INTO @values VALUES(@i);
    SET @i = @i + 1;
END

Then the following query gives you the solution

SELECT TOP 1 v.value
FROM @values AS v
LEFT OUTER JOIN thing AS t ON v.value = t.code
WHERE t.code IS NULL

score 0 · Answer 2 · answered Feb 05 '15 at 00:03

0

Here is a function to find all gaps:

SELECT (t1.id + 1) as gap_starts_at, 
   (SELECT MIN(t3.id) -1 FROM thing t3 WHERE t3.id > t1.id) as     gap_ends_at
FROM thing t1
WHERE NOT EXISTS (SELECT t2.id FROM thing t2 WHERE t2.id = t1.id + 1)
HAVING gap_ends_at IS NOT NULL

gap_starts_at - first id in current gap
gap_ends_at - last id in current gap

answered Feb 05 '15 at 00:03

Jay

2,656
1
16
24

Your solution is pretty similar to my first solution, but I want to avoid to use `EXISTS` if I can – JCalcines Feb 05 '15 at 00:10

Strawberry · Answer 3 · 2015-02-05T11:17:09.673

0

Here's one idea. It's not a complete solution, but it's something to think about...

SELECT x.code+1 
  FROM thing x 
  LEFT 
 OUTER
  JOIN thing y 
    ON y.code = x.code+1 
 WHERE y.code IS NULL 
 ORDER 
    BY x.code 
 LIMIT 1;
+----------+
| x.code+1 |
+----------+
|        4 |
+----------+

edited Feb 05 '15 at 11:17

answered Feb 05 '15 at 00:17

Strawberry

33,750
13
40
57

Right, I had already thought abouta that (My second option) but I can't do that kind of join in Hibernate – JCalcines Feb 05 '15 at 10:30
I don't really know hibernate, but my understanding is that it *does* support `left outer join` – Strawberry Feb 05 '15 at 10:55
Yes It does but I can't define the fields that It uses for join and also I have to predefine de relationship in the model. – JCalcines Feb 05 '15 at 22:51

How to search the minimum free value

3 Answers3