From: John A Meinel <john@arbash-meinel.com>
To: Merlin Moncure <merlin.moncure@rcsonline.com>
Cc: Postgresql Performance <pgsql-performance@postgresql.org>
Cc: elein <elein@varlena.com>
Subject: Re: tricky query
Date: Tue, 28 Jun 2005 11:25:56 -0500
Message-ID: <42C17A14.3040100@arbash-meinel.com> (raw)
In-Reply-To: <6EE64EF3AB31D5448D0007DD34EEB3415C2BFF@Herge.rcsinc.local>
References: <6EE64EF3AB31D5448D0007DD34EEB3415C2BFF@Herge.rcsinc.local>
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
=:->
Attachments:
signature.asc (application/pgp-signature, 252B) download
Reply instructions:
You may reply publicly to this message via plain-text email
using any one of the following methods:
* Reply to all the recipients using the --to and --cc options:
reply via email
To: pgsql-performance@postgresql.org
Cc: john@arbash-meinel.com, merlin.moncure@rcsonline.com, elein@varlena.com
Subject: Re: tricky query
In-Reply-To: <42C17A14.3040100@arbash-meinel.com>
* Save the following mbox file, import it into your mail client,
and reply-to-all from there: mbox
This inbox is served by DDX for PostgreSQL; see mirroring instructions
for how to clone and mirror all data and code used for this inbox