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 883DF9DC9B9;
	Thu, 16 Feb 2006 18:33:52 -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 34124-04; Thu, 16 Feb 2006 18:33:54 -0400 (AST)
X-Greylist: from auto-whitelisted by SQLgrey-
X-Greylist: from auto-whitelisted by SQLgrey-
Received: from moutng.kundenserver.de (moutng.kundenserver.de
	[212.227.126.188])
	by postgresql.org (Postfix) with ESMTP id 2B79E9DC873;
	Thu, 16 Feb 2006 18:33:49 -0400 (AST)
Received: from [84.157.0.176] (helo=lunix.schabi.de)
	by mrelayeu.kundenserver.de (node=mrelayeu3) with ESMTP (Nemesis),
	id 0MKxQS-1F9rh90aNq-0000Ak; Thu, 16 Feb 2006 23:33:51 +0100
Received: from [127.0.0.1] (localhost [127.0.0.1])
	by lunix.schabi.de (Postfix) with ESMTP id 53A961CC8D2;
	Thu, 16 Feb 2006 23:33:49 +0100 (CET)
Message-ID: <43F4FDCC.2000204@logix-tt.com>
Date: Thu, 16 Feb 2006 23:33:48 +0100
From: Markus Schaber <schabi@logix-tt.com>
User-Agent: Mozilla Thunderbird 1.0.7 (X11/20051017)
X-Accept-Language: de-DE, de, en-us, en
MIME-Version: 1.0
To: pgsql-performance@postgresql.org
CC: pgsql-hackers@postgresql.org
Subject: Re: qsort again (was Re: [PERFORM] Strange Create Index
References: <43F38867.6010701@gpdnet.co.uk> <19510.1140036968@sss.pgh.pa.us>	
	<19779.1140038874@sss.pgh.pa.us> <43F39E53.1020009@gpdnet.co.uk>	
	<20781.1140046109@sss.pgh.pa.us>	
	<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>
In-Reply-To: <1140128256.9076.254.camel@archimedes>
X-Enigmail-Version: 0.93.0.0
Content-Type: text/plain; charset=ISO-8859-15
Content-Transfer-Encoding: 7bit
X-Provags-ID: kundenserver.de abuse@kundenserver.de
	login:a9554655f07a4e401310f2acfb43f5bf
X-Virus-Scanned: by amavisd-new at hub.org
X-Spam-Status: No, score=0.12 required=5 tests=[AWL=0.120]
X-Spam-Score: 0.12
X-Spam-Level: 
X-Archive-Number: 200602/643
X-Sequence-Number: 79781

Hi, Mark,

Mark Lewis schrieb:

> It seems that instead of maintaining a different sorting code path for
> each data type, you could get away with one generic path and one
> (hopefully faster) path if you allowed data types to optionally support
> a 'sortKey' interface by providing a function f which maps inputs to 32-
> bit int outputs, such that the following two properties hold:
> 
> f(a)>=f(b) iff a>=b
> if a==b then f(a)==f(b)

Hmm, to remove redundancy, I'd change the <= to a < and define:

if a==b then f(a)==f(b)
if a<b  then f(a)<=f(b)

> 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).

With int2 or some restricted ranges of oid and int4, we could even
implement a bucket sort.

Markus