How to find unused ID in a column?

Question

Possible Duplicate:
SQL query to find Missing sequence numbers

I have a table which has a user Id column, The user could select which user ID to add in the table. I am wondering if there is a one sql code that could point me to the list of unused user id or even just the smallest unused ID?

For example, I have the following IDs

USER_ID 1 2 3 5 6 7 8 10

I would like to know if there is a way to select 4 or even selecting 4 and 9?

Answer 1

You can try using the "NOT IN" clause:

select
    user_id
from table
where
    user_id not in (select user_id from another_table)

Like this:

select
    u1.user_id + 1 as start
from users as u1
  left outer join users as u2 on u1.user_id + 1 = u2.id
where
    u2.id is null

From here.

Answer 2

Short of looping through all the ids (perhaps using binary search tree logic?) I don't have a good answer for you.

I would ask what you want this for? By their nature, ids are essentially meaningless - all they do is identify some data, not describe it, and as such it shouldn't be a problem if you have large gaps in your user ids. (In fact, some people would say that it's even better to have unguessable ids, to avoid users tampering with information to find security holes)

Answer 3

Given that SQL is generally a set-based language, the only way I could think to do this would be to create the full set of ID's, and outer join your table where no ID's matched. Problem with that is if your table has a significant number of records, you would have to generate a temporary table containing every ID from 1 through MAX(USER_ID). Given a table with tens or hundreds of millions of records, that could be very slow.

Just out of curiosity, why do you need to know the ID holes? Is there some specific reason, or are you just trying to not "waste" an ID? Given the processing effort to find the holes, I would think it is more efficient to just let them be.

Answer 4

It depends on the Database you are using. If you are using Oracle, something like this will work: Step 1: Find out max value of userid in your table:

    select max(userid) from tbl_userid 

    let this number be m

Step 2: Find out the max value of rownum in the foll query

    select rownum from all_objects

Step 3: If the max value is greater than m then you can use the foll query to list your unused user ids

    select user_id 
    from tbl_userid
    where user_id NOT IN (select rownum from all_objects)

If max value returned by step 2 is less than m you can tweak your query to the following

    select user_id 
    from tbl_userid
    where user_id NOT IN 
                  (select rownum 
                   from (select * 
                         from all_objects 
                         UNION ALL 
                         select * from all_objects)
                  )

Repeat the UNION ALL until you get max(rownum) >= m

If you are using SQL server, kindly let me know. There is no direct equivalent of ROWNUM pseudocolumn in sql server but there are workarounds using the RANK() function.

Answer 5

Here's one way to do it using SQL Server 2005 or later. It may or may not work efficiently for you:

insert into T values
  (1),(2),(3),(5),(6),(9),(11);

with Trk as (
  select userid,
    row_number() over (
      order by userid
    ) as rk
  from T
), Truns(start,finish,gp) as (
     select -1+min(userid), 1+max(userid),
     userid-rk
     from Trk
     group by userid-rk
), Tregroup as (
  select start, finish,
    row_number() over (
      order by gp 
    ) as rk
  from Truns
), Tpre as (
  select a.finish, b.start
  from Tregroup as a full outer join Tregroup as b
  on a.rk + 1 = b.rk
) 
  select
    rtrim(finish) + case when start = finish then '' else + '-' + rtrim(start) end as gap
  from Tpre
  where finish+start is not null
drop table T;