Getting an unused number from a set of numbers?

2 Dec 2005 11:57 AM

Lisa Pearlson

Hi,

Imagine I have a set of numbers: 1, 2, 5, 6, 9, ....., 10000

I wish to fetch one number that IS NOT already in the set.

I can do some kind of FOR/NEXT loop, taking id 1, checking if it already
exists, and keep incrementing this id until I find one that does't exist
yet. This obviously will get slower and slower as there are more records (on
the lower end) in the table.
And, it's not set, but sequential based.

Any other way to do this (getting a random number instead of starting with 1
is also not an option)?

I'm interested in knowing about this situation just out of curiosity. In
practice I am going to use an identity field.

Lisa

2 Dec 2005 12:03 PM

Tom Moreau

Try:

select top 1
    o.MyCol + 1
from
    MyTable    o
where not exists
(
    select
        *
    from
        MyTable    i
    where
        i.MyCol = o.MyCol + 1
)

--
Tom

----------------------------------------------------
Thomas A. Moreau, BSc, PhD, MCSE, MCDBA
SQL Server MVP
Columnist, SQL Server Professional
Toronto, ON Canada
www.pinpub.com
..

"Lisa Pearlson" <no@spam.plz> wrote in message
news:OLm0Mez9FHA.4084@TK2MSFTNGP10.phx.gbl...
Hi,

Imagine I have a set of numbers: 1, 2, 5, 6, 9, ....., 10000

I wish to fetch one number that IS NOT already in the set.

I can do some kind of FOR/NEXT loop, taking id 1, checking if it already
exists, and keep incrementing this id until I find one that does't exist
yet. This obviously will get slower and slower as there are more records (on
the lower end) in the table.
And, it's not set, but sequential based.

Any other way to do this (getting a random number instead of starting with 1
is also not an option)?

I'm interested in knowing about this situation just out of curiosity. In
practice I am going to use an identity field.

Lisa

2 Dec 2005 12:58 PM

Razvan Socol

Hi, Tom

You forgot an "ORDER BY MyCol" at the end of the query. It works
without it, too, but it gives a random unused number, instead of the
first unused number.

Another way would be:

select min(o.MyCol) + 1
from MyTable o
where not exists (
select * from MyTable i
where i.MyCol = o.MyCol + 1
)

Razvan

2 Dec 2005 1:13 PM

Lisa Pearlson

Hey thanks guys.. makes sense :)

Lisa

Show quote

"Razvan Socol" <rso***@gmail.com> wrote in message
news:1133528332.598132.229030@g14g2000cwa.googlegroups.com...
> Hi, Tom
>
> You forgot an "ORDER BY MyCol" at the end of the query. It works
> without it, too, but it gives a random unused number, instead of the
> first unused number.
>
> Another way would be:
>
> select min(o.MyCol) + 1
> from MyTable o
> where not exists (
> select * from MyTable i
> where i.MyCol = o.MyCol + 1
> )
>
> Razvan
>

2 Dec 2005 1:09 PM

--CELKO--

>> I have a set of numbers: 1, 2, 5, 6, 9, ....., 10000; I wish to fetch one number that IS NOT already in the set. <<

SELECT CASE WHEN MIN (i+1) <= MIN(i-1)
                THEN MIN (i+1) ELSE MIN(i-1) END
                AS available_nbr
FROM NumberList
WHERE (I+1) NOT IN (SELECT i FROM NumberList)
   AND (I-1) NOT IN (SELECT i FROM NumberList);

You can get a -1 returned if you have a full list, but you did not give
us any rules. Add more cases to handle it as yuou wish.

2 Dec 2005 1:18 PM

Razvan Socol

Hi, Joe

As I see it, the condition "MIN (i+1) <= MIN(i-1)" that you used in
your query, will always be false (assuming that i is not NULL). You
might want to read your query again...

Razvan

2 Dec 2005 3:34 PM

Alexander Kuznetsov

> As I see it, the condition "MIN (i+1) <= MIN(i-1)" that you used in
> your query, will always be false (assuming that i is not NULL)

not exactly, not always. It works for this data:

create table NumberList(i int)
insert into NumberList values(1)
insert into NumberList values(2)
insert into NumberList values(3)
insert into NumberList values(5)
insert into NumberList values(7)

SELECT
--MIN (i+1) mplus, MIN(i-1) mminus,
CASE WHEN MIN (i+1) <= MIN(i-1)
                THEN MIN (i+1) ELSE MIN(i-1) END
                AS available_nbr
FROM NumberList
WHERE (I+1) NOT IN (SELECT i FROM NumberList)
   AND (I-1) NOT IN (SELECT i FROM NumberList);

available_nbr
-------------
4

drop table NumberList

but it won't work for this data:

insert into NumberList values(1)
insert into NumberList values(2)
insert into NumberList values(3)
insert into NumberList values(5)
----- I added 6 here
insert into NumberList values(6)
insert into NumberList values(7)

--- gap at 4 not detected
available_nbr
-------------
NULL

2 Dec 2005 7:50 PM

Razvan Socol

Razvan Socol wrote:

> > As I see it, the condition "MIN (i+1) <= MIN(i-1)" that you used in
> > your query, will always be false (assuming that i is not NULL)

Alexander Kuznetsov wrote:

> not exactly, not always. It works for this data: [...]
> but it won't work for this data: [...]

Indeed, Celko's query happens to work only in some particular cases.
But I was saying that the condition in the CASE expression always
evaluates to false, so he may as well wrote "SELECT MIN(i-1) AS
available_nbr FROM NumberList WHERE ...". Anyway, his WHERE condition
is so weird (and of course, buggy, as you pointed out), so I cannot
guess what he was trying to do.

Razvan

2 Dec 2005 9:51 PM

Alexander Kuznetsov

> But I was saying that the condition in the CASE expression always
> evaluates to false

Razvan,

I agree to that. It looks like I misunderstood you, sorry for that.
BTW, I guess your last name is Slavic, right?

3 Dec 2005 6:03 PM

--CELKO--

Let's try this when I am awake and sober:

CREATE TABLE NumberList
(i INTEGER NOT NULL PRIMARY KEY);

INSERT INTO NumberList(i) VALUES(2);
INSERT INTO NumberList(i) VALUES(3);
INSERT INTO NumberList(i) VALUES(5)
INSERT INTO NumberList(i) VALUES(7);

-- INSERT INTO NumberList(i)
SELECT CASE WHEN MIN(i) = 1
            THEN (SELECT MIN(i+1)
                    FROM NumberList
                   WHERE (i+1) NOT IN (SELECT i FROM NumberList)
                     AND (i+1) <= 10000)
            ELSE 1 END AS available_nbr
FROM NumberList;
SELECT * FROM NumberList;

The WHEN clause should be pretty fast, since we have an index on the i
column and since most optimizers keep the min and max in the stats.
The scalar subquery is not bad if you have a good optimizer -- Ingres
will do this the same way as an EXISTS() for example. Basically, it
does some math on the AND predicate, and knows that the PRIMARY is
ordered, so you can stop when the scan gets its first hit.

The expensive solutions will be anything with an OUTER JOIN or more
than one self-join.

2 Dec 2005 4:53 PM

Tony Rogerson

Thats hellishy inefficient...

The expression will negate a useful use of an index.

The NOT IN is to be avoided also.

--
Tony Rogerson
SQL Server MVP
http://sqlserverfaq.com - free video tutorials

Show quote

"--CELKO--" <jcelko***@earthlink.net> wrote in message
news:1133528948.795727.87980@z14g2000cwz.googlegroups.com...
>>> I have a set of numbers: 1, 2, 5, 6, 9, ....., 10000; I wish to fetch
>>> one number that IS NOT already in the set. <<
>
> SELECT CASE WHEN MIN (i+1) <= MIN(i-1)
>                THEN MIN (i+1) ELSE MIN(i-1) END
>                AS available_nbr
> FROM NumberList
> WHERE (I+1) NOT IN (SELECT i FROM NumberList)
>   AND (I-1) NOT IN (SELECT i FROM NumberList);
>
> You can get a -1 returned if you have a full list, but you did not give
> us any rules. Add more cases to handle it as yuou wish.
>

2 Dec 2005 8:08 PM

Steve Kass

Did you test this on anything at all? It's garbage, nothing more.

First of all, MIN(i+1) can never be <= MIN(i-1),
since MIN(i+1) = 2 + MIN(i-1). But that's just a
waste-of-code and confusion issue, while the WHERE
condition is where the garbage is. The condition admits
only those rows of the table where neither I+1 nor I-1
(presumably you mean i+1 and i-1) is in the table. So
using an unnecessary CASE expression, you select the
smallest integer N for which

N is *not* in the table, *and*
N+1 *is* in the table, *and*
N+2 is *not* in the table

Example: if the NumberList table represents the set {2, 3, 5, 6},
the query returns one row, with NULL as available_nbr. Huh?

SK

--CELKO-- wrote:
Show quote

>>>I have a set of numbers: 1, 2, 5, 6, 9, ....., 10000; I wish to fetch one number that IS NOT already in the set. <<
>
>
> SELECT CASE WHEN MIN (i+1) <= MIN(i-1)
>                 THEN MIN (i+1) ELSE MIN(i-1) END
>                 AS available_nbr
>   FROM NumberList
> WHERE (I+1) NOT IN (SELECT i FROM NumberList)
>    AND (I-1) NOT IN (SELECT i FROM NumberList);
>
> You can get a -1 returned if you have a full list, but you did not give
> us any rules. Add more cases to handle it as yuou wish.
>

3 Dec 2005 1:44 PM

--CELKO--

>> Imagine I have a set of numbers: 1, 2, 5, 6, 9, ....., 10000 <<

I read it to mean that we model a set as a table with constraints, so
we have:

CREATE TABLE NumberList
(i INTEGER NOT NULL PRIMARY KEY
CHECK(i BETWEEN 1 AND 10000));

But since Lisa did not post any DDL, it was worth bringing up the
problem of limits.

3 Dec 2005 3:45 PM

Steve Kass

--CELKO-- wrote:

>>>Imagine I have a set of numbers: 1, 2, 5, 6, 9, ....., 10000 <<
>>>
>>>
>
>I read it to mean that we model a set as a table with constraints, so
>we have:
>
>

And how does this explain why you posted junk code
that for example returns NULL when the table contains the four
numbers 2, 3, 5, and 6 (the useless CASE condition you wrote aside)?

SK

Show quote

>CREATE TABLE NumberList
>(i INTEGER NOT NULL PRIMARY KEY
> CHECK(i BETWEEN 1 AND 10000));
>
>But since Lisa did not post any DDL, it was worth bringing up the
>problem of limits.
>
>
>

2 Dec 2005 4:57 PM

Tony Rogerson

Here is a method that won't involve a NOT EXISTS, could be more efficient
depending on your real data...

declare @nums table(i int)

insert @nums values(1)
insert @nums values(2)
insert @nums values(3)
insert @nums values(5)
insert @nums values(7)

select number + 1
from (
    select is_missing = case when n2.i is null then 1 else 0 end,
           number = n.i
    from @nums n
        left outer join @nums n2 on n2.i = n.i + 1
    ) as d
where d.is_missing = 1

--
Tony Rogerson
SQL Server MVP
http://sqlserverfaq.com - free video tutorials

Show quote

"Lisa Pearlson" <no@spam.plz> wrote in message
news:OLm0Mez9FHA.4084@TK2MSFTNGP10.phx.gbl...
> Hi,
>
> Imagine I have a set of numbers: 1, 2, 5, 6, 9, ....., 10000
>
> I wish to fetch one number that IS NOT already in the set.
>
> I can do some kind of FOR/NEXT loop, taking id 1, checking if it already
> exists, and keep incrementing this id until I find one that does't exist
> yet. This obviously will get slower and slower as there are more records
> (on the lower end) in the table.
> And, it's not set, but sequential based.
>
> Any other way to do this (getting a random number instead of starting with
> 1 is also not an option)?
>
> I'm interested in knowing about this situation just out of curiosity. In
> practice I am going to use an identity field.
>
> Lisa
>

2 Dec 2005 5:10 PM

Tony Rogerson

Actually, suprisingly, on my particular test base here the NOT EXISTS....
The first query takes 7% of the batch run time and the latter 93%.

select top 10 n.id + 1
from mb_message n
where not exists (
    select *
    from mb_message n2
    where n2.id = n.id + 1
    )
order by id

select top 10 id = n.id
from mb_message n
    left outer join mb_message n2 on n2.id = n.id + 1
where n2.id is null
order by id

--
Tony Rogerson
SQL Server MVP
http://sqlserverfaq.com - free video tutorials

Show quote

"Tony Rogerson" <tonyroger***@sqlserverfaq.com> wrote in message
news:%23cAjMD29FHA.3804@TK2MSFTNGP14.phx.gbl...
> Here is a method that won't involve a NOT EXISTS, could be more efficient
> depending on your real data...
>
> declare @nums table(i int)
>
> insert @nums values(1)
> insert @nums values(2)
> insert @nums values(3)
> insert @nums values(5)
> insert @nums values(7)
>
> select number + 1
> from (
>    select is_missing = case when n2.i is null then 1 else 0 end,
>           number = n.i
>    from @nums n
>        left outer join @nums n2 on n2.i = n.i + 1
>    ) as d
> where d.is_missing = 1
>
>
> --
> Tony Rogerson
> SQL Server MVP
> http://sqlserverfaq.com - free video tutorials
>
>
> "Lisa Pearlson" <no@spam.plz> wrote in message
> news:OLm0Mez9FHA.4084@TK2MSFTNGP10.phx.gbl...
>> Hi,
>>
>> Imagine I have a set of numbers: 1, 2, 5, 6, 9, ....., 10000
>>
>> I wish to fetch one number that IS NOT already in the set.
>>
>> I can do some kind of FOR/NEXT loop, taking id 1, checking if it already
>> exists, and keep incrementing this id until I find one that does't exist
>> yet. This obviously will get slower and slower as there are more records
>> (on the lower end) in the table.
>> And, it's not set, but sequential based.
>>
>> Any other way to do this (getting a random number instead of starting
>> with 1 is also not an option)?
>>
>> I'm interested in knowing about this situation just out of curiosity. In
>> practice I am going to use an identity field.
>>
>> Lisa
>>
>
>

2 Dec 2005 5:10 PM

Alexander Kuznetsov

Tony,

since only 1 missing number is required, it might be even faster with
TOP 1

select TOP 1 number + 1
from (
    select is_missing = case when n2.i is null then 1 else 0 end,
           number = n.i
    from @nums n
        left outer join @nums n2 on n2.i = n.i + 1
    ) as d
where d.is_missing = 1

Makes sense?

2 Dec 2005 5:15 PM

Alexander Kuznetsov

> a method that won't involve a NOT EXISTS, could be more efficient
> depending on your real data...

interesting, I usually see NOT EXISTS being more efficient than the
equvalent left outer join, at least for big tables where it really
matters.
Do you have an example where NOT EXISTS is less efficient?