Received: from localhost (maia-1.hub.org [200.46.204.191])
	by postgresql.org (Postfix) with ESMTP id B06829FB471
	for <pgsql-performance-postgresql.org@postgresql.org>;
	Sat, 14 Apr 2007 12:53:36 -0300 (ADT)
Received: from postgresql.org ([200.46.204.71])
	by localhost (mx1.hub.org [200.46.204.191]) (amavisd-maia, port 10024)
	with ESMTP id 60756-06 for
	<pgsql-performance-postgresql.org@postgresql.org>;
	Sat, 14 Apr 2007 12:53:20 -0300 (ADT)
X-Greylist: from auto-whitelisted by SQLgrey-1.7.4
Received: from sss.pgh.pa.us (sss.pgh.pa.us [66.207.139.130])
	by postgresql.org (Postfix) with ESMTP id EB26C9FB398
	for <pgsql-performance@postgresql.org>;
	Sat, 14 Apr 2007 12:52:49 -0300 (ADT)
Received: from sss2.sss.pgh.pa.us (tgl@localhost [127.0.0.1])
	by sss.pgh.pa.us (8.13.6/8.13.6) with ESMTP id l3EFqjhB004536;
	Sat, 14 Apr 2007 11:52:46 -0400 (EDT)
To: "Dann Corbit" <DCorbit@connx.com>
cc: "Alvaro Herrera" <alvherre@commandprompt.com>,
	pgsql-hackers@postgresql.org,
	"PostgreSQL Performance" <pgsql-performance@postgresql.org>,
	"Steve" <cheetah@tanabi.org>
Subject: Re: [HACKERS] choose_bitmap_and again (was Re: Strangely Variable
	Query Performance)
In-reply-to: 
 <D425483C2C5C9F49B5B7A41F89441547010005E0@postal.corporate.connx.com>
References: <Pine.GSO.4.64.0704121855300.17955@kittyhawk.tanabi.org>
	<10117.1176420763@sss.pgh.pa.us>
	<Pine.GSO.4.64.0704121928440.17955@kittyhawk.tanabi.org>
	<10355.1176422445@sss.pgh.pa.us>
	<Pine.GSO.4.64.0704122001160.17955@kittyhawk.tanabi.org>
	<10503.1176423606@sss.pgh.pa.us>
	<Pine.GSO.4.64.0704122025450.17955@kittyhawk.tanabi.org>
	<12360.1176436194@sss.pgh.pa.us>
	<Pine.GSO.4.64.0704122354430.17955@kit!tyhawk.tanabi.org>
	<26399.1176504501@sss.pgh.pa.us>
	<20070413232409.GI27255@alvh.no-ip.org>
	<D425483C2C5C9F49B5B7A41F89441547010005E0@postal.corporate.connx.com>
Comments: In-reply-to "Dann Corbit" <DCorbit@connx.com>
	message dated "Sat, 14 Apr 2007 02:04:24 -0700"
Date: Sat, 14 Apr 2007 11:52:45 -0400
Message-ID: <4535.1176565965@sss.pgh.pa.us>
From: Tom Lane <tgl@sss.pgh.pa.us>
X-Virus-Scanned: Maia Mailguard 1.0.1
X-Archive-Number: 200704/306
X-Sequence-Number: 24183

"Dann Corbit" <DCorbit@connx.com> writes:
> Instead of sorting, I suggest the quickselect() algorithm, which is
> O(n).

What for?  Common cases have less than half a dozen entries.  That is
not the place we need to be spending engineering effort --- what we
need to worry about is what's the choice algorithm, not implementation
details.

			regards, tom lane