Message-ID: <42C17A14.3040100@arbash-meinel.com>
Date: Tue, 28 Jun 2005 11:25:56 -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: Postgresql Performance <pgsql-performance@postgresql.org>,
	elein <elein@varlena.com>
Subject: Re: tricky query
References: <6EE64EF3AB31D5448D0007DD34EEB3415C2BFF@Herge.rcsinc.local>
In-Reply-To: <6EE64EF3AB31D5448D0007DD34EEB3415C2BFF@Herge.rcsinc.local>
Content-Type: multipart/signed; micalg=pgp-sha1;
	protocol="application/pgp-signature";
	boundary="------------enigCEEFCB2A271606AE3B38C834"

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

Merlin Moncure wrote:

>John Meinel wrote:
>
>
>>See my follow up post, which enables an index scan. On my system with
>>90k rows, it takes no apparent time.
>>(0.000ms)
>>John
>>=:->
>>
>>
>
>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;
>
>Merlin
>
>
Just be aware that as your table fills it's holes, this query gets
slower and slower.
I've been doing some testing. And it starts at 0.00 when the first entry
is something like 3, but when you start getting to 16k it starts taking
more like 200 ms.

So it kind of depends how your table fills (and empties I suppose).

The earlier query was slower overall (since it took 460ms to read in the
whole table).
I filled up the table such that 63713 is the first empty space, and it
takes 969ms to run.
So actually if your table is mostly full, the first form is better.

But if you are going to have 100k rows, with basically random
distribution of empties, then the NOT EXISTS works quite well.

Just be aware of the tradeoff. I'm pretty sure the WHERE NOT EXISTS will
always use a looping structure, and go through the index in order.

John
=:->


--------------enigCEEFCB2A271606AE3B38C834
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

iD8DBQFCwXoUJdeBCYSNAAMRAkjLAKDEQ2oVyUsg5sIGaRNZKMNRqfb0SQCdF0Xo
JH6KkY4FxhHyCJCYsDm1bZk=
=WkpU
-----END PGP SIGNATURE-----

--------------enigCEEFCB2A271606AE3B38C834--