DomainKey-Signature: a=rsa-sha1; q=dns; c=nofws; s=beta; d=gmail.com;
	h=received:message-id:date:from:reply-to:to:subject:cc:in-reply-to:mime-version:content-type:content-transfer-encoding:content-disposition:references;
	b=pzcPfeR2M1/vKtJiHm2s6JtFN3be+xWpoq4TiX19VvJ/CWJ+91bL35ECwlkAa6o5z7Eqi0nPkrZsP1S5yYiCsaN437rm7OJ4uDo5FokAXkbzNmqbSC6Mx9xMkwHw+fS9jwwE5r5rktJodprSmcBn85CHP0LwZz5mxo6vVNtIf3s=
Message-ID: <758d5e7f05062823361c8840f4@mail.gmail.com>
Date: Wed, 29 Jun 2005 08:36:52 +0200
From: Dawid Kuroczko <qnex42@gmail.com>
Reply-To: Dawid Kuroczko <qnex42@gmail.com>
To: John A Meinel <john@arbash-meinel.com>
Subject: Re: tricky query
Cc: Merlin Moncure <merlin.moncure@rcsonline.com>,
	Bruno Wolff III <bruno@wolff.to>,
	Postgresql Performance <pgsql-performance@postgresql.org>,
	elein <elein@varlena.com>
In-Reply-To: <42C1A81D.1060507@arbash-meinel.com>
Mime-Version: 1.0
Content-Type: text/plain; charset=ISO-8859-1
Content-Transfer-Encoding: quoted-printable
Content-Disposition: inline
References: <6EE64EF3AB31D5448D0007DD34EEB3415C2C07@Herge.rcsinc.local>
	<42C1A81D.1060507@arbash-meinel.com>

On 6/28/05, John A Meinel <john@arbash-meinel.com> wrote:

> Actually, if you already have a lower bound, then you can change it to:
>=20
> 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 =3D t1.id+1)
>     ORDER BY t1.id LIMIT 1;
>=20
> This would actually really help performance if you have a large table
> and then empty entries start late.

You can also boost performance by creating a functional index!

CREATE UNIQUE INDEX id_test_id1_index ON id_test ((id+1));

...and then joining two tables and filtering results.  PostgreSQL (8.x)
will do Merge Full Join which will use both the indexes:

SELECT t2.id+1 FROM id_test t1 FULL OUTER JOIN id_test t2 ON (t1.id =3D
t2.id+1) WHERE t1.id IS NULL LIMIT 1;

 Limit  (cost=3D0.00..1.52 rows=3D1 width=3D4)
   ->  Merge Full Join  (cost=3D0.00..1523122.73 rows=3D999974 width=3D4)
         Merge Cond: ("outer".id =3D ("inner".id + 1))
         Filter: ("outer".id IS NULL)
         ->  Index Scan using id_test_pkey on id_test t1=20
(cost=3D0.00..18455.71 rows=3D999974 width=3D4)
         ->  Index Scan using id_test_id1_index on id_test t2=20
(cost=3D0.00..1482167.60 rows=3D999974 width=3D4)
(6 rows)

...the only drawback is having to keep two indexes instead of just one.
But for large tables I think it is really worth it

For my test case, the times are (1-1000000 range with 26 missing
rows):
NOT EXISTS -- 670ms
NOT IN -- 1800ms
indexed FULL OUTER -- 267ms

   Regards,
       Dawid

PS: Does it qualify for General Bits? ;-)))