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 F37A89DCA31;
	Fri, 17 Feb 2006 12:31:45 -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 67459-10; Fri, 17 Feb 2006 12:31:43 -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 027FE9DC84B;
	Fri, 17 Feb 2006 12:31:41 -0400 (AST)
Received: from kleptog by svana.org with local (Exim 4.50)
	id 1FA8Vv-0003Q1-Mi; Sat, 18 Feb 2006 03:31:23 +1100
Date: Fri, 17 Feb 2006 17:31:23 +0100
From: Martijn van Oosterhout <kleptog@svana.org>
To: Scott Lamb <slamb@slamb.org>
Cc: Mark Lewis <mark.lewis@mir3.com>, Tom Lane <tgl@sss.pgh.pa.us>,
	"Craig A. James" <cjames@modgraph-usa.com>,
	Markus Schaber <schabi@logix-tt.com>,
	pgsql-performance@postgresql.org, pgsql-hackers@postgresql.org
Subject: Re: qsort again (was Re: [PERFORM] Strange Create Index
Message-ID: <20060217163123.GE9254@svana.org>
Reply-To: Martijn van Oosterhout <kleptog@svana.org>
References: <7.0.1.0.2.20060215194635.03b55da0@earthlink.net>
	<21615.1140052893@sss.pgh.pa.us>
	<7.0.1.0.2.20060215223710.03a7c618@earthlink.net>
	<20060216113522.GA3461@uio.no>
	<7.0.1.0.2.20060216071053.0385a1a8@earthlink.net>
	<43F481CD.2010509@logix-tt.com> <43F4A7D8.4050907@modgraph-usa.com>
	<29277.1140110108@sss.pgh.pa.us>
	<1140128256.9076.254.camel@archimedes>
	<8F91CB67-8459-4B65-ADDC-A47A135E0767@slamb.org>
Mime-Version: 1.0
Content-Type: multipart/signed; micalg=pgp-sha1;
	protocol="application/pgp-signature"; boundary="3O1VwFp74L81IIeR"
Content-Disposition: inline
In-Reply-To: <8F91CB67-8459-4B65-ADDC-A47A135E0767@slamb.org>
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/662
X-Sequence-Number: 79800


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

On Fri, Feb 17, 2006 at 08:18:41AM -0800, Scott Lamb wrote:
> On Feb 16, 2006, at 2:17 PM, Mark Lewis wrote:
> >Data types which could probably provide a useful function for f =20
> >would be
> >int2, int4, oid, and possibly int8 and text (at least for SQL_ASCII).
>=20
> ...and with some work, floats (I think just the exponent would work, =20
> if nothing else). bytea. Probably just about anything.
>=20
> Interesting. If you abandon the idea that collisions should be =20
> impossible (they're not indexes) or extremely rare (they're not =20
> hashes), it's pretty easy to come up with a decent hint to avoid a =20
> lot of dereferences.

Yep, pretty much for any datatype you create a mapping function to map
it to a signed int32. All you have to guarentee is that f(a) > f(b)
implies that a > b. Only if f(a) =3D=3D f(b) do you need to compare a and
b.

You then change the sorting code to have an array of (Datum,int32)
(ouch, double the storage) where the int32 is the f(Datum). And in the
comparison routines you first check the int32. If they give an order
you're done. On match you do the full comparison.

For integer types (int2,int4,int8,oid) the conversion is straight
forward. For float you'd use the exponent and the first few bits of the
mantissa. For strings you'd have to bail, or use a strxfrm equivalent.
NULL would be INT_MAX pr INT_MIN depending on where you want it. Thing
is, even if you don't have such a function and always return zero, the
results will still be right.

Not a new idea, but it would be very nice to implement. If would
produce nice speedups for type where comparisons are expensive. And
more importantly, the bulk of the comparisons can be moved inline and
make the whole cache-friendlyness discussed here much more meaningful.

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.

--3O1VwFp74L81IIeR
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)

iD8DBQFD9fpbIB7bNG8LQkwRAqGiAJ99zj5mcaHkYCccW87sug+nbloTGwCgjaNd
ND3PDJKC6kq3Adbfzzmqi0Y=
=i14/
-----END PGP SIGNATURE-----

--3O1VwFp74L81IIeR--