Re: [PERFORM] tricky query

[John A Meinel]

Merlin Moncure wrote:

On Tue, Jun 28, 2005 at 12:02:09 -0400,
 Merlin Moncure <[EMAIL PROTECTED]> 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
=:->

signature.asc
Description: OpenPGP digital signature