Date: Tue, 28 Jun 2005 18:42:05 +0100
From: Sam Mason <sam@samason.me.uk>
To: pgsql-performance@postgresql.org
Subject: Re: tricky query
Message-ID: <20050628174205.GT62747@colo.samason.me.uk>
Mail-Followup-To: Sam Mason <sam@samason.me.uk>,
	pgsql-performance@postgresql.org
References: <6EE64EF3AB31D5448D0007DD34EEB3415C2BEC@Herge.rcsinc.local>
	<42C167C6.5070108@arbash-meinel.com>
	<42C16FE4.2020803@arbash-meinel.com>
Mime-Version: 1.0
Content-Type: text/plain; charset=us-ascii
Content-Disposition: inline
In-Reply-To: <42C16FE4.2020803@arbash-meinel.com>
User-Agent: Mutt/1.4.2.1i

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