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 920929DC9B9; Thu, 16 Feb 2006 18:17: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 26710-04; Thu, 16 Feb 2006 18:17:42 -0400 (AST) X-Greylist: from auto-whitelisted by SQLgrey- X-Greylist: from auto-whitelisted by SQLgrey- Received: from mir3-fs.mir3.com (mail.mir3.com [65.208.188.100]) by postgresql.org (Postfix) with ESMTP id 5C3E29DC9BF; Thu, 16 Feb 2006 18:17:35 -0400 (AST) Received: mir3-fs.mir3.com 172.16.1.11 from 172.16.2.68 172.16.2.68 via HTTP with MS-WebStorage 6.0.6249 Received: from archimedes.mirlogic.com by mir3-fs.mir3.com; 16 Feb 2006 14:17:36 -0800 Subject: Re: qsort again (was Re: [PERFORM] Strange Create Index From: Mark Lewis To: Tom Lane Cc: "Craig A. James" , Markus Schaber , pgsql-performance@postgresql.org, pgsql-hackers@postgresql.org In-Reply-To: <29277.1140110108@sss.pgh.pa.us> 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> Content-Type: text/plain Content-Transfer-Encoding: 7bit Organization: MIR3, Inc. Date: Thu, 16 Feb 2006 14:17:36 -0800 Message-Id: <1140128256.9076.254.camel@archimedes> Mime-Version: 1.0 X-Mailer: Evolution 2.0.2 (2.0.2-22) X-Virus-Scanned: by amavisd-new at hub.org X-Spam-Status: No, score=0.121 required=5 tests=[AWL=0.120, UNPARSEABLE_RELAY=0.001] X-Spam-Score: 0.121 X-Spam-Level: X-Archive-Number: 200602/642 X-Sequence-Number: 79780 On Thu, 2006-02-16 at 12:15 -0500, Tom Lane wrote: > Once or twice we've kicked around the idea of having some > datatype-specific sorting code paths alongside the general-purpose one, > but I can't honestly see this as being workable from a code maintenance > standpoint. > > regards, tom lane 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) So if a data type supports the sortKey interface you could perform the sort on f(value) and only refer back to the actual element comparison functions when two sortKeys have the same value. 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). Depending on the overhead, you might not even need to maintain 2 independent search code paths, since you could always use f(x)=0 as the default sortKey function which would degenerate to the exact same sort behavior in use today. -- Mark Lewis