how find "holes" in auto_increment column?

Question

when I DELETE, as example, the id 3, I have this:

id | name
 1 |
 2 |    
 4 |
 5 |
 ...

now, I want to search for the missing id(s), because i want to fill the id again with:

INSERT INTO xx (id,...) VALUES (3,...)

is there a way to search for "holes" in the auto_increment index?

thanks!

Answer 1

You can find the top value of gaps like this:

select t1.id - 1 as missing_id
from mytable t1
left join mytable t2 on t2.id = t1.id - 1
where t2.id is null

Answer 2

The purpose of AUTO_INCREMENT is to generate simple unique and meaningless identifiers for your rows. As soon as you plan to re-use those IDs, they're no longer unique (not at least in time) so I have the impression that you are not using the right tool for the job. If you decide to get rid of AUTO_INCREMENT, you can do all your inserts with the same algorithm.

As about the SQL code, this query will match existing rows with the rows that has the next ID:

SELECT a.foo_id, b.foo_id
FROM foo a
LEFT JOIN foo b ON a.foo_id=b.foo_id-1

E.g.:

 1 NULL
 4 NULL
10 NULL
12 NULL
17 NULL
19   20
20 NULL
24   25
25   26
26   27
27 NULL

So it's easy to filter out rows and get the first gap:

SELECT MIN(a.foo_id)+1 AS next_id
FROM foo a
LEFT JOIN foo b ON a.foo_id=b.foo_id-1
WHERE b.foo_id IS NULL

Take this as a starting point because it still needs some tweaking:

• You need to consider the case where the lowest available number is the lowest possible one.
• You need to lock the table to handle concurrent inserts.
• In my computer it's slow as hell with big tables.

Answer 3

I think the only way you can do this is with a loop: Any other solutions wont show gaps bigger than 1:

insert into XX values (1)
insert into XX values (2)
insert into XX values (4)
insert into XX values (5)
insert into XX values (10)

declare @min int
declare @max int

select @min=MIN(ID) from xx
select @max=MAX(ID) from xx

while @min<@max begin
    if not exists(select 1 from XX where id = @min+1) BEGIN
        print 'GAP: '+ cast(@min +1 as varchar(10))
    END

    set @min=@min+1
end

result:

GAP: 3
GAP: 6
GAP: 7
GAP: 8
GAP: 9

Answer 4

First, I agree with the comments that you shouldn't try filling in holes. You won't be able to find all the holes with a single SQL statement. You'll have to loop through all possible numbers starting with 1 until you find a hole. You could write a sql function to do this for you that could then be used in a function. So if you wrote a function called find_first_hole you could then call it in an insert like:

INSERT INTO xx (id, ...) VALUES (find_first_hole(), ...)

Answer 5

This is a gaps&island problem, see my (and other) replies here and here. In most cases, gaps&islands problems are most elegantly solved using recursive CTE's, which are not available in mysql.