SEO

I need a fast way (sql only preferred) to solve the following problem:

I need the smallest integer that is greater than zero that is not in the
column of a table. In other words, if an 'id' column has values
1,2,3,4,6 and 7, I need a query that returns the value of 5.

I've already worked out a query using generate_series (not scalable) and
pl/pgsql. An SQL only solution would be preferred, am I missing
something obvious?

Merlin

---------------------------(end of broadcast)---------------------------
TIP 3: if posting/reading through Usenet, please send an appropriate
subscribe-nomail command to majordomo@postgresql.org so that your
message can get through to the mailing list cleanly

On Tue, Jun 28, 2005 at 10:21:16 -0400,
Merlin Moncure <merlin.moncure@rcsonline.com> wrote:
> I need a fast way (sql only preferred) to solve the following problem:
>
> I need the smallest integer that is greater than zero that is not in the
> column of a table. In other words, if an 'id' column has values
> 1,2,3,4,6 and 7, I need a query that returns the value of 5.
>
> I've already worked out a query using generate_series (not scalable) and
> pl/pgsql. An SQL only solution would be preferred, am I missing
> something obvious?

I would expect that using generate series from the 1 to the max (using
order by and limit 1 to avoid extra sequential scans) and subtracting
out the current list using except and then taking the minium value
would be the best way to do this if the list is pretty dense and
you don't want to change the structure.

If it is sparse than you can do a special check for 1 and if that
is present find the first row whose successor is not in the table.
That shouldn't be too slow.

If you are willing to change the structure you might keep one row for
each number and use a flag to mark which ones are empty. If there are
relatively few empty rows at any time, then you can create a partial
index on the row number for only empty rows.

---------------------------(end of broadcast)---------------------------
TIP 3: if posting/reading through Usenet, please send an appropriate
subscribe-nomail command to majordomo@postgresql.org so that your
message can get through to the mailing list cleanly

Merlin Moncure wrote:

>I need a fast way (sql only preferred) to solve the following problem:
>
>I need the smallest integer that is greater than zero that is not in the
>column of a table. In other words, if an 'id' column has values
>1,2,3,4,6 and 7, I need a query that returns the value of 5.
>
>I've already worked out a query using generate_series (not scalable) and
>pl/pgsql. An SQL only solution would be preferred, am I missing
>something obvious?
>
>Merlin
>
>

Not so bad. Try something like this:

SELECT min(id+1) as id_new FROM table
WHERE (id+1) NOT IN (SELECT id FROM table);

Now, this requires probably a sequential scan, but I'm not sure how you
can get around that.
Maybe if you got trickier and did some ordering and limits. The above
seems to give the right answer, though.

I don't know how big you want to scale to.

You might try something like:
SELECT id+1 as id_new FROM t
WHERE (id+1) NOT IN (SELECT id FROM t)
ORDER BY id LIMIT 1;

John
=:->


-----BEGIN PGP SIGNATURE-----
Version: GnuPG v1.4.0 (Cygwin)
Comment: Using GnuPG with Thunderbird - http://enigmail.mozdev.org

iD8DBQFCwWfGJdeBCYSNAAMRAsNFAKCdYfJ4aZjw0bNhNnCcug H8qnn2ngCfTWTz
Aus1toBGdKn7YRJA8ZePgmg=
=JxB0
-----END PGP SIGNATURE-----

Merlin Moncure wrote:
>I've already worked out a query using generate_series (not scalable) and
>pl/pgsql. An SQL only solution would be preferred, am I missing
>something obvious?

I would be tempted to join the table to itself like:

SELECT id+1
FROM foo
WHERE id > 0
AND i NOT IN (SELECT id-1 FROM foo)
LIMIT 1;

Seems to work for me. Not sure if that's good enough for you, but
it may help.

Sam

---------------------------(end of broadcast)---------------------------
TIP 1: subscribe and unsubscribe commands go to majordomo@postgresql.org

John A Meinel wrote:

> Merlin Moncure wrote:
>
>> I need a fast way (sql only preferred) to solve the following problem:
>>
>> I need the smallest integer that is greater than zero that is not in the
>> column of a table. In other words, if an 'id' column has values
>> 1,2,3,4,6 and 7, I need a query that returns the value of 5.
>>
>> I've already worked out a query using generate_series (not scalable) and
>> pl/pgsql. An SQL only solution would be preferred, am I missing
>> something obvious?
>>
>> Merlin
>>
>>
>
> Not so bad. Try something like this:
>
> SELECT min(id+1) as id_new FROM table
> WHERE (id+1) NOT IN (SELECT id FROM table);
>
> Now, this requires probably a sequential scan, but I'm not sure how you
> can get around that.
> Maybe if you got trickier and did some ordering and limits. The above
> seems to give the right answer, though.
>
> I don't know how big you want to scale to.
>
> You might try something like:
> SELECT id+1 as id_new FROM t
> WHERE (id+1) NOT IN (SELECT id FROM t)
> ORDER BY id LIMIT 1;
>
> John
> =:->

Well, I was able to improve it to using appropriate index scans.
Here is the query:

SELECT t1.id+1 as id_new FROM id_test t1
WHERE NOT EXISTS
(SELECT t2.id FROM id_test t2 WHERE t2.id = t1.id+1)
ORDER BY t1.id LIMIT 1;

I created a test table which has 90k randomly inserted rows. And this is
what EXPLAIN ANALYZE says:

QUERY PLAN

----------------------------------------------------------------------------------------------------------------------------------------
Limit (cost=0.00..12.10 rows=1 width=4) (actual time=0.000..0.000 rows=1 loops=1)
-> Index Scan using id_test_pkey on id_test t1 (cost=0.00..544423.27 rows=45000 width=4) (actual time=0.000..0.000 rows=1 loops=1)
Filter: (NOT (subplan))
SubPlan
-> Index Scan using id_test_pkey on id_test t2 (cost=0.00..6.01 rows=1 width=4) (actual time=0.000..0.000 rows=1 loops=15)
Index Cond: (id = ($0 + 1))
Total runtime: 0.000 ms
(7 rows)

The only thing I have is a primary key index on id_test(id);

John
=:->


-----BEGIN PGP SIGNATURE-----
Version: GnuPG v1.4.0 (Cygwin)
Comment: Using GnuPG with Thunderbird - http://enigmail.mozdev.org

iD8DBQFCwW/kJdeBCYSNAAMRApBOAKDEkbTzHJyRuY8G5pem30paTdVxRACgt ZyC
XjeAl8xiAkEGQvTF5PZLokY=
=R+bb
-----END PGP SIGNATURE-----

Merlin Moncure wrote:

> I need a fast way (sql only preferred) to solve the following problem:
> I need the smallest integer that is greater than zero that is not in the
> column of a table.
>
> I've already worked out a query using generate_series (not scalable) and
> pl/pgsql. An SQL only solution would be preferred, am I missing
> something obvious?

Probably not, but I thought about this "brute-force" approach... :-)
This should work well provided that:

- you have a finite number of integers. Your column should have a biggest
integer value with a reasonable maximum like 100,000 or 1,000,000.
#define YOUR_MAX 99999

- you can accept that query execution time depends on smallest integer found.
The bigger the found integer, the slower execution you get.

Ok, so:

Create a relation "integers" (or whatever) with every single integer from 1 to
YOUR_MAX:

CREATE TABLE integers (id integer primary key);
INSERT INTO integers (id) VALUES (1);
INSERT INTO integers (id) VALUES (2);
...
INSERT INTO integers (id) VALUES (YOUR_MAX);

Create your relation:

CREATE TABLE merlin (id integer primary key);
<and fill it with values>

Query is simple now:

SELECT a.id FROM integers a
LEFT JOIN merlin b ON a.id=b.id
WHERE b.id IS NULL
ORDER BY a.id LIMIT 1;

Execution times with 100k tuples in "integers" and
99,999 tuples in "merlin":

>\timing
Timing is on.
>select i.id from integers i left join merlin s on i.id=s.id where s.id is
null order by i.id limit 1;
99999

Time: 233.618 ms
>insert into merlin (id) values (99999);
INSERT 86266614 1
Time: 0.579 ms
>delete from merlin where id=241;
DELETE 1
Time: 0.726 ms
>select i.id from integers i left join merlin s on i.id=s.id where s.id is
null order by i.id limit 1;
241

Time: 1.336 ms
>

--
Cosimo


---------------------------(end of broadcast)---------------------------
TIP 8: explain analyze is your friend

John A Meinel wrote:
>SELECT t1.id+1 as id_new FROM id_test t1
> WHERE NOT EXISTS
> (SELECT t2.id FROM id_test t2 WHERE t2.id = t1.id+1)
> ORDER BY t1.id LIMIT 1;

This works well on sparse data, as it only requires as many index
access as it takes to find the first gap. The simpler "NOT IN"
version that everybody seems to have posted the first time round
has a reasonably constant (based on the number of rows, not gap
position) startup time but the actual time spent searching for the
gap is much lower.

I guess the version you use depends on how sparse you expect the
data to be. If you expect your query to have to search through
more than half the table before finding the gap then you're better
off using the "NOT IN" version, otherwise the "NOT EXISTS" version
is faster -- on my system anyway.

Hope that's interesting!


Sam

---------------------------(end of broadcast)---------------------------
TIP 9: In versions below 8.0, the planner will ignore your desire to
choose an index scan if your joining column's datatypes do not
match

John A Meinel wrote:
> John A Meinel wrote:
>> Merlin Moncure wrote:
>>
>>> I need the smallest integer that is greater than zero that is not in the
>>> column of a table. In other words, if an 'id' column has values
>>> 1,2,3,4,6 and 7, I need a query that returns the value of 5.
>>
>> [...]
>
> Well, I was able to improve it to using appropriate index scans.
> Here is the query:
>
> SELECT t1.id+1 as id_new FROM id_test t1
> WHERE NOT EXISTS
> (SELECT t2.id FROM id_test t2 WHERE t2.id = t1.id+1)
> ORDER BY t1.id LIMIT 1;

I'm very interested in this "tricky query".
Sorry John, but if I populate the `id_test' relation
with only 4 tuples with id values (10, 11, 12, 13),
the result of this query is:

cosimo=> create table id_test (id integer primary key);
NOTICE: CREATE TABLE / PRIMARY KEY will create implicit index 'id_test_pkey'
for table 'id_test'
CREATE TABLE
cosimo=> insert into id_test values (10); -- and 11, 12, 13, 14
INSERT 7457570 1
INSERT 7457571 1
INSERT 7457572 1
INSERT 7457573 1
INSERT 7457574 1
cosimo=> SELECT t1.id+1 as id_new FROM id_test t1 WHERE NOT EXISTS (SELECT
t2.id FROM id_test t2 WHERE t2.id = t1.id+1) ORDER BY t1.id LIMIT 1;
id_new
--------
15
(1 row)

which if I understand correctly, is the wrong answer to the problem.
At this point, I'm starting to think I need some sleep... :-)

--
Cosimo


---------------------------(end of broadcast)---------------------------
TIP 5: Have you checked our extensive FAQ?

http://www.postgresql.org/docs/faq

John A Meinel schrieb:

> John A Meinel wrote:
>
>>
>
> Well, I was able to improve it to using appropriate index scans.
> Here is the query:
>
> SELECT t1.id+1 as id_new FROM id_test t1
> WHERE NOT EXISTS
> (SELECT t2.id FROM id_test t2 WHERE t2.id = t1.id+1)
> ORDER BY t1.id LIMIT 1;
>
> I created a test table which has 90k randomly inserted rows. And this is
> what EXPLAIN ANALYZE says:
>
>


As Cosimo stated the result can be wrong. The result is always wrong
when the id with value 1 does not exist.

--
Best Regards / Viele Grüße

Sebastian Hennebrueder

----

http://www.laliluna.de

Tutorials for JSP, JavaServer Faces, Struts, Hibernate and EJB

Get support, education and consulting for these technologies - uncomplicated and cheap.


---------------------------(end of broadcast)---------------------------
TIP 8: explain analyze is your friend