Date: Tue, 28 Jun 2005 10:12:46 -0500
From: Bruno Wolff III <bruno@wolff.to>
To: Merlin Moncure <merlin.moncure@rcsonline.com>
Cc: pgsql-performance@postgresql.org
Subject: Re: tricky query
Message-ID: <20050628151246.GA29773@wolff.to>
Mail-Followup-To: Bruno Wolff III <bruno@wolff.to>,
	Merlin Moncure <merlin.moncure@rcsonline.com>,
	pgsql-performance@postgresql.org
References: <6EE64EF3AB31D5448D0007DD34EEB3415C2BEC@Herge.rcsinc.local>
Mime-Version: 1.0
Content-Type: text/plain; charset=us-ascii
Content-Disposition: inline
In-Reply-To: <6EE64EF3AB31D5448D0007DD34EEB3415C2BEC@Herge.rcsinc.local>
User-Agent: Mutt/1.5.6i

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.