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 7B23B9DC83D; Thu, 16 Feb 2006 09:38:50 -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 92236-10; Thu, 16 Feb 2006 09:38:53 -0400 (AST) X-Greylist: from auto-whitelisted by SQLgrey- X-Greylist: from auto-whitelisted by SQLgrey- Received: from smtpauth08.mail.atl.earthlink.net (smtpauth08.mail.atl.earthlink.net [209.86.89.68]) by postgresql.org (Postfix) with ESMTP id 62F1A9DC82A; Thu, 16 Feb 2006 09:38:48 -0400 (AST) DomainKey-Signature: a=rsa-sha1; q=dns; c=nofws; s=dk20050327; d=earthlink.net; b=RSTQxNw+GEjxmft7HywTnPolmWCqxdiO2P8+CmeDIlnF9J8JX1qhJB4hdrNKZ/IM; h=Received:Message-Id:X-Mailer:Date:To:From:Subject:In-Reply-To:References:Mime-Version:Content-Type:X-ELNK-Trace:X-Originating-IP; Received: from [71.243.43.186] (helo=ron-6d52adff2a6.earthlink.net) by smtpauth08.mail.atl.earthlink.net with asmtp (Exim 4.34) id 1F9jLP-0000mN-NJ; Thu, 16 Feb 2006 08:38:51 -0500 Message-Id: <7.0.1.0.2.20060216082618.03ad7e48@earthlink.net> X-Mailer: QUALCOMM Windows Eudora Version 7.0.1.0 Date: Thu, 16 Feb 2006 08:38:45 -0500 To: Florian Weimer ,pgsql-performance@postgresql.org, pgsql-hackers@postgresql.org From: Ron Subject: Re: [PERFORM] qsort again In-Reply-To: <873bijsdvb.fsf@mid.deneb.enyo.de> 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> <1140055972.31672.42.camel@localhost.localdomain> <873bijsdvb.fsf@mid.deneb.enyo.de> Mime-Version: 1.0 Content-Type: text/plain; charset="us-ascii"; format=flowed X-ELNK-Trace: acd68a6551193be5d780f4a490ca69563f9fea00a6dd62bc480b186c8c60dfc7dcbc075b2a287ed5350badd9bab72f9c350badd9bab72f9c350badd9bab72f9c X-Originating-IP: 71.243.43.186 X-Virus-Scanned: by amavisd-new at hub.org X-Spam-Status: No, score=0.465 required=5 tests=[AWL=-0.014, DNS_FROM_RFC_ABUSE=0.479] X-Spam-Score: 0.465 X-Spam-Level: X-Archive-Number: 200602/620 X-Sequence-Number: 79758 At 07:10 AM 2/16/2006, Florian Weimer wrote: >* Neil Conway: > > > On Wed, 2006-02-15 at 18:28 -0500, Tom Lane wrote: > >> It seems clear that our qsort.c is doing a pretty awful job of picking > >> qsort pivots, while glibc is mostly managing not to make that mistake. > >> I haven't looked at the glibc code yet to see what they are doing > >> differently. > > > > glibc qsort is actually merge sort, so I'm not surprised it avoids this > > problem. > >qsort also performs twice as many key comparisons as the theoretical >minimum. The theoretical minimum number of comparisons for a general purpose comparison based sort is O(lgN!). QuickSort uses 2NlnN ~= 1.38NlgN or ~1.38x the optimum without tuning (see Knuth, Sedgewick, Corman, ... etc) OTOH, QuickSort uses ~2x as many =moves= as the theoretical minimum unless tuned, and moves are more expensive than compares in modern systems. See my other posts for QuickSort tuning methods that attempt to directly address both issues. Ron