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 3F1AA9DCB61;
	Fri, 17 Feb 2006 15:43:40 -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 17365-08; Fri, 17 Feb 2006 15:43:39 -0400 (AST)
X-Greylist: from auto-whitelisted by SQLgrey-
X-Greylist: from auto-whitelisted by SQLgrey-
Received: from sss.pgh.pa.us (sss.pgh.pa.us [66.207.139.130])
	by postgresql.org (Postfix) with ESMTP id 2BB539DCB4D;
	Fri, 17 Feb 2006 15:43:36 -0400 (AST)
Received: from sss2.sss.pgh.pa.us (tgl@localhost [127.0.0.1])
	by sss.pgh.pa.us (8.13.1/8.13.1) with ESMTP id k1HJh6R1011802;
	Fri, 17 Feb 2006 14:43:07 -0500 (EST)
To: Mark Lewis <mark.lewis@mir3.com>
cc: David Lang <dlang@invendra.net>, Greg Stark <gsstark@mit.edu>,
	Markus Schaber <schabi@logix-tt.com>, pgsql-performance@postgresql.org,
	pgsql-hackers@postgresql.org
Subject: Re: qsort again (was Re: [PERFORM] Strange Create Index 
In-reply-to: <1140197437.9076.268.camel@archimedes> 
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>
	<43F4FDCC.2000204@logix-tt.com> <871wy23okp.fsf@stark.xeocode.com>
	<1140132189.9076.261.camel@archimedes>
	<Pine.LNX.4.62.0602162131211.20790@qnivq.ynat.uz>
	<1140197437.9076.268.camel@archimedes>
Comments: In-reply-to Mark Lewis <mark.lewis@mir3.com>
	message dated "Fri, 17 Feb 2006 09:30:37 -0800"
Date: Fri, 17 Feb 2006 14:43:06 -0500
Message-ID: <11801.1140205386@sss.pgh.pa.us>
From: Tom Lane <tgl@sss.pgh.pa.us>
X-Virus-Scanned: by amavisd-new at hub.org
X-Spam-Status: No, score=0.11 required=5 tests=[AWL=0.110]
X-Spam-Score: 0.11
X-Spam-Level: 
X-Archive-Number: 200602/671
X-Sequence-Number: 79809

Mark Lewis <mark.lewis@mir3.com> writes:
> I think we're actually on the same page here; you're right that the
> constraint above ( f(a)==f(b) iff a==b ) can't be extended to data types
> with more than 32 bits of value space.  But the constraint I listed was
> actually:

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

I believe Martijn had it right: the important constraint is

	f(a) > f(b) implies a > b

which implies by commutativity

	f(a) < f(b) implies a < b

and these two together imply

	a == b implies f(a) == f(b)

Now you can't do any sorting if you only have the equality rule, you
need the inequality rule.

			regards, tom lane