Message-ID: <42C1A81D.1060507@arbash-meinel.com>
Date: Tue, 28 Jun 2005 14:42:21 -0500
From: John A Meinel <john@arbash-meinel.com>
User-Agent: Mozilla Thunderbird 1.0.2 (Windows/20050317)
MIME-Version: 1.0
To: Merlin Moncure <merlin.moncure@rcsonline.com>
Cc: Bruno Wolff III <bruno@wolff.to>,
	Postgresql Performance <pgsql-performance@postgresql.org>,
	elein <elein@varlena.com>
Subject: Re: tricky query
References: <6EE64EF3AB31D5448D0007DD34EEB3415C2C07@Herge.rcsinc.local>
In-Reply-To: <6EE64EF3AB31D5448D0007DD34EEB3415C2C07@Herge.rcsinc.local>
Content-Type: multipart/signed; micalg=pgp-sha1;
	protocol="application/pgp-signature";
	boundary="------------enig8E27A38A36BB7C7B26DF7894"

This is an OpenPGP/MIME signed message (RFC 2440 and 3156)
--------------enig8E27A38A36BB7C7B26DF7894
Content-Type: text/plain; charset=ISO-8859-1; format=flowed
Content-Transfer-Encoding: 7bit

Merlin Moncure wrote:

>>On Tue, Jun 28, 2005 at 12:02:09 -0400,
>>  Merlin Moncure <merlin.moncure@rcsonline.com> wrote:
>>
>>
>>>Confirmed.  Hats off to you, the above some really wicked querying.
>>>IIRC I posted the same question several months ago with no response
>>>
>>>
>and
>
>
>>>had given up on it.  I think your solution (smallest X1 not in X) is
>>>
>>>
>a
>
>
>>>good candidate for general bits, so I'm passing this to varlena for
>>>review :)
>>>
>>>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;
>>>
>>>
>>You need to rework this to check to see if row '1' is missing. The
>>above returns the start of the first gap after the first row that
>>isn't missing.
>>
>>
>
>Correct.
>
>In fact, I left out a detail in my original request in that I had a
>starting value (easily supplied with where clause)...so what I was
>really looking for was a query which started at a supplied value and
>looped forwards looking for an empty slot.  John's supplied query is a
>drop in replacement for a plpgsql routine which does exactly this.
>
>The main problem with the generate_series approach is that there is no
>convenient way to determine a supplied upper bound.  Also, in some
>corner cases of my problem domain the performance was not good.
>
>Merlin
>
>
Actually, if you already have a lower bound, then you can change it to:

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

This would actually really help performance if you have a large table
and then empty entries start late.

On my system, where the first entry is 64k, doing where id > 60000
speeds it up back to 80ms instead of 1000ms.
John
=:->


--------------enig8E27A38A36BB7C7B26DF7894
Content-Type: application/pgp-signature; name="signature.asc"
Content-Description: OpenPGP digital signature
Content-Disposition: attachment; filename="signature.asc"

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

iD8DBQFCwagdJdeBCYSNAAMRAu3aAJ94iU6MAnyzRGS0+GBO6JasQtwlnQCeNQdA
8wbx+wpu3au8H0HtZRWoJEg=
=0GN4
-----END PGP SIGNATURE-----

--------------enig8E27A38A36BB7C7B26DF7894--