From: Martijn van Oosterhout <kleptog@svana.org>
To: Scott Lamb <slamb@slamb.org>
Cc: Mark Lewis <mark.lewis@mir3.com>
Cc: Tom Lane <tgl@sss.pgh.pa.us>
Cc: Craig A. James <cjames@modgraph-usa.com>
Cc: Markus Schaber <schabi@logix-tt.com>
Cc: pgsql-performance@postgresql.org
Cc: pgsql-hackers@postgresql.org
Subject: Re: qsort again (was Re: [PERFORM] Strange Create Index
Date: Fri, 17 Feb 2006 17:31:23 +0100
Message-ID: <20060217163123.GE9254@svana.org> (raw)
In-Reply-To: <8F91CB67-8459-4B65-ADDC-A47A135E0767@slamb.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>
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
> >would be
> >int2, int4, oid, and possibly int8 and text (at least for SQL_ASCII).
>
> ...and with some work, floats (I think just the exponent would work,
> if nothing else). bytea. Probably just about anything.
>
> Interesting. If you abandon the idea that collisions should be
> impossible (they're not indexes) or extremely rare (they're not
> hashes), it's pretty easy to come up with a decent hint to avoid a
> 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) == 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,
--
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.
Attachments:
signature.asc (application/pgp-signature, 188B) 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: kleptog@svana.org, slamb@slamb.org, mark.lewis@mir3.com, tgl@sss.pgh.pa.us, cjames@modgraph-usa.com, schabi@logix-tt.com, pgsql-hackers@postgresql.org
Subject: Re: qsort again (was Re: [PERFORM] Strange Create Index
In-Reply-To: <20060217163123.GE9254@svana.org>
* 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