X-Original-To: pgsql-hackers-postgresql.org@localhost.postgresql.org
Received: from localhost (av.hub.org [200.46.204.144])
	by postgresql.org (Postfix) with ESMTP id B5FD39DCAD7;
	Fri, 17 Feb 2006 11:54:13 -0400 (AST)
Received: from postgresql.org ([200.46.204.71])
	by localhost (av.hub.org [200.46.204.144]) (amavisd-new, port 10024)
	with ESMTP id 61431-07; Fri, 17 Feb 2006 11:54:18 -0400 (AST)
X-Greylist: from auto-whitelisted by SQLgrey-
X-Greylist: from auto-whitelisted by SQLgrey-
Received: from svana.org (svana.org [125.62.94.225])
	by postgresql.org (Postfix) with ESMTP id CDEEE9DCA95;
	Fri, 17 Feb 2006 11:54:10 -0400 (AST)
Received: from kleptog by svana.org with local (Exim 4.50)
	id 1FA7vi-0003Kt-Ks; Sat, 18 Feb 2006 02:53:58 +1100
Date: Fri, 17 Feb 2006 16:53:58 +0100
From: Martijn van Oosterhout <kleptog@svana.org>
To: Ron <rjpeace@earthlink.net>
Cc: Markus Schaber <schabi@logix-tt.com>, pgsql-performance@postgresql.org,
	pgsql-hackers@postgresql.org
Subject: Re: qsort again (was Re: [PERFORM] Strange Create
Message-ID: <20060217155358.GD9254@svana.org>
Reply-To: Martijn van Oosterhout <kleptog@svana.org>
References: <20060216113522.GA3461@uio.no>
	<7.0.1.0.2.20060216071053.0385a1a8@earthlink.net>
	<20060216144833.GG26127@svana.org>
	<7.0.1.0.2.20060216100954.035b5ee0@earthlink.net>
	<7.0.1.0.2.20060216110249.0395d2b0@earthlink.net>
	<87FA36B4-CD97-4CF5-B9B3-02FEEA25CC95@slamb.org>
	<7.0.1.0.2.20060216133801.03a7ab50@earthlink.net>
	<7.0.1.0.2.20060217004822.039d46a8@earthlink.net>
	<43F5A341.5090808@logix-tt.com>
	<7.0.1.0.2.20060217080226.03a11010@earthlink.net>
Mime-Version: 1.0
Content-Type: multipart/signed; micalg=pgp-sha1;
	protocol="application/pgp-signature"; boundary="oj4kGyHlBMXGt3Le"
Content-Disposition: inline
In-Reply-To: <7.0.1.0.2.20060217080226.03a11010@earthlink.net>
X-PGP-Key-ID: Length=1024; ID=0x0DC67BE6
X-PGP-Key-Fingerprint: 295F A899 A81A 156D B522  48A7 6394 F08A 0DC6 7BE6
X-PGP-Key-URL: <http://svana.org/kleptog/0DC67BE6.pgp.asc>
User-Agent: Mutt/1.5.9i
X-SA-Exim-Connect-IP: <locally generated>
X-SA-Exim-Mail-From: kleptog@svana.org
X-SA-Exim-Scanned: No (on svana.org); SAEximRunCond expanded to false
X-Virus-Scanned: by amavisd-new at hub.org
X-Spam-Status: No, score=0.123 required=5 tests=[AWL=0.123]
X-Spam-Score: 0.123
X-Spam-Level: 
X-Archive-Number: 200602/660
X-Sequence-Number: 79798


--oj4kGyHlBMXGt3Le
Content-Type: text/plain; charset=us-ascii
Content-Disposition: inline
Content-Transfer-Encoding: quoted-printable

On Fri, Feb 17, 2006 at 08:23:40AM -0500, Ron wrote:
> >For this mapping, you need a full table sort.
> One physical IO pass should be all that's needed.  However, let's=20
> pretend you are correct and that we do need to sort the table to get=20
> the key mapping.  Even so, we would only need to do it =3Donce=3D and=20
> then we would be able to use and incrementally update the results=20
> forever afterward.  Even under this assumption, one external sort to=20
> save all subsequent such sorts seems well worth it.
>=20
> IOW, even if I'm wrong about the initial cost to do this; it is still=20
> worth doing ;-)

I think you're talking about something different here. You're thinking
of having the whole table sorted and when you add a new value you add
it in such a way to keep it sorted. The problem is, what do you sort it
by? If you've sorted the table by col1, then when the user does ORDER
BY col2 it's useless.

Indeed, this is what btrees do, you store the order of the table
seperate from the data. And you can store multiple orders. But even
then, when someone does ORDER BY lower(col1), it's still useless.

And you're right, we still need to do the single mass sort in the
beginning, which is precisely what we're trying to optimise here.

> ??? You do not need to resort already ordered data to insert a new=20
> element into it such that the data stays ordered!  Once we have done=20
> the key ordering operation once, we should not ever need to do it=20
> again on the original data.  Else most sorting algorithms wouldn't work ;=
-)

We already do this with btree indexes. I'm not sure what you are
proposing that improves on that.

Have a nice day,
--=20
Martijn van Oosterhout   <kleptog@svana.org>   http://svana.org/kleptog/
> Patent. n. Genius is 5% inspiration and 95% perspiration. A patent is a
> tool for doing 5% of the work and then sitting around waiting for someone
> else to do the other 95% so you can sue them.

--oj4kGyHlBMXGt3Le
Content-Type: application/pgp-signature; name="signature.asc"
Content-Description: Digital signature
Content-Disposition: inline

-----BEGIN PGP SIGNATURE-----
Version: GnuPG v1.4.1 (GNU/Linux)

iD8DBQFD9fGWIB7bNG8LQkwRAuEGAKCBmgneGkWhYa2RIkkjFcbs13VnywCgi78D
FDv+hOlXVbTw8evk84RBIak=
=bszz
-----END PGP SIGNATURE-----

--oj4kGyHlBMXGt3Le--