X-Original-To: pgsql-performance-postgresql.org@localhost.postgresql.org
Received: from localhost (unknown [200.46.204.144])
	by svr1.postgresql.org (Postfix) with ESMTP id D5DB552A34
	for <pgsql-performance-postgresql.org@localhost.postgresql.org>;
	Tue, 28 Jun 2005 12:20:37 -0300 (ADT)
Received: from svr1.postgresql.org ([200.46.204.71])
	by localhost (av.hub.org [200.46.204.144]) (amavisd-new, port 10024)
	with ESMTP id 52946-09
	for <pgsql-performance-postgresql.org@localhost.postgresql.org>;
	Tue, 28 Jun 2005 15:20:33 +0000 (GMT)
Received: from ebrsrv01.ebravo.it (host53-205.pool8534.interbusiness.it
	[85.34.205.53])
	by svr1.postgresql.org (Postfix) with ESMTP id 93B0852A15
	for <pgsql-performance@postgresql.org>;
	Tue, 28 Jun 2005 12:20:29 -0300 (ADT)
Received: from [192.168.11.103] ([192.168.11.103]) (authenticated)
	by ebrsrv01.ebravo.it (8.11.6/8.12.5) with ESMTP id j5SFKIY26481;
	Tue, 28 Jun 2005 17:20:18 +0200
Message-ID: <42C16AAD.4070903@streppone.it>
Date: Tue, 28 Jun 2005 17:20:13 +0200
From: Cosimo Streppone <cosimo@streppone.it>
User-Agent: Mozilla Thunderbird 1.0 (X11/20041206)
X-Accept-Language: it, it-it, en-us, en
MIME-Version: 1.0
To: Merlin Moncure <merlin.moncure@rcsonline.com>
Cc: Postgresql Performance <pgsql-performance@postgresql.org>
Subject: Re: tricky query
References: <6EE64EF3AB31D5448D0007DD34EEB3415C2BEC@Herge.rcsinc.local>
In-Reply-To: <6EE64EF3AB31D5448D0007DD34EEB3415C2BEC@Herge.rcsinc.local>
Content-Type: text/plain; charset=ISO-8859-1; format=flowed
Content-Transfer-Encoding: 7bit
X-Virus-Scanned: by amavisd-new at hub.org
X-Spam-Status: No, hits=0.05 tagged_above=0 required=5 tests=FORGED_RCVD_HELO
X-Spam-Level: 
X-Archive-Number: 200506/563
X-Sequence-Number: 13200

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