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 E1DD79DCBDB for ; Thu, 2 Mar 2006 14:50:29 -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 38811-07 for ; Thu, 2 Mar 2006 14:50:29 -0400 (AST) X-Greylist: domain auto-whitelisted by SQLgrey- Received: from nproxy.gmail.com (nproxy.gmail.com [64.233.182.194]) by postgresql.org (Postfix) with ESMTP id 005BF9DCBB6 for ; Thu, 2 Mar 2006 14:50:24 -0400 (AST) Received: by nproxy.gmail.com with SMTP id l24so113594nfc for ; Thu, 02 Mar 2006 10:50:24 -0800 (PST) DomainKey-Signature: a=rsa-sha1; q=dns; c=nofws; s=beta; d=gmail.com; h=received:message-id:date:from:to:subject:cc:in-reply-to:mime-version:content-type:references; b=r6Erten03FkaEQ4xuLzRAX853aVNtBxCI9sUKJVvB35kSf8xfMF1tsv0DQE5t5n5ATd1yYejTDOAxvG5uncVtm2DhPdvluiw4fNJO2QtDRRoQiE1W19EWhEzbCOI8tJx2SdpvATrRs3MlzbZ8DwJCdiDCQkE9yh2FIhRlRehkOg= Received: by 10.48.238.20 with SMTP id l20mr785913nfh; Thu, 02 Mar 2006 10:50:24 -0800 (PST) Received: by 10.48.213.12 with HTTP; Thu, 2 Mar 2006 10:50:24 -0800 (PST) Message-ID: <36e682920603021050s4d8a6a02j3c0acf54f19e4881@mail.gmail.com> Date: Thu, 2 Mar 2006 13:50:24 -0500 From: "Jonah H. Harris" To: "Bruce Momjian" Subject: Re: qsort again (was Re: [PERFORM] Strange Create Index behaviour) Cc: "Dann Corbit" , "Tom Lane" , Ron , pgsql-performance@postgresql.org, pgsql-hackers@postgresql.org In-Reply-To: <200603021817.k22IHnY08016@candle.pha.pa.us> MIME-Version: 1.0 Content-Type: multipart/alternative; boundary="----=_Part_4984_1958656.1141325424234" References: <200603021817.k22IHnY08016@candle.pha.pa.us> X-Virus-Scanned: by amavisd-new at hub.org X-Spam-Status: No, score=0.46 required=5 tests=[AWL=-0.041, HTML_MESSAGE=0.001, RAZOR2_CHECK=0.5] X-Spam-Score: 0.46 X-Spam-Level: X-Archive-Number: 200603/135 X-Sequence-Number: 80533 ------=_Part_4984_1958656.1141325424234 Content-Type: text/plain; charset=ISO-8859-1 Content-Transfer-Encoding: quoted-printable Content-Disposition: inline My introsort is almost complete and its the fastest variant of quicksort I can find, I'll submit it to -patches in the next couple days as-well. On 3/2/06, Bruce Momjian wrote: > > > Added to TODO: > > * Improve port/qsort() to handle sorts with 50% unique and 50% > duplicate > value [qsort] > > This involves choosing better pivot points for the quicksort. > > > > -------------------------------------------------------------------------= -- > > Dann Corbit wrote: > > > > > > > -----Original Message----- > > > From: pgsql-hackers-owner@postgresql.org [mailto:pgsql-hackers- > > > owner@postgresql.org] On Behalf Of Tom Lane > > > Sent: Wednesday, February 15, 2006 5:22 PM > > > To: Ron > > > Cc: pgsql-performance@postgresql.org; pgsql-hackers@postgresql.org > > > Subject: Re: [HACKERS] qsort again (was Re: [PERFORM] Strange Create > > Index > > > behaviour) > > > > > > Ron writes: > > > > How are we choosing our pivots? > > > > > > See qsort.c: it looks like median of nine equally spaced inputs (ie, > > > the 1/8th points of the initial input array, plus the end points), > > > implemented as two rounds of median-of-three choices. With half of > > the > > > data inputs zero, it's not too improbable for two out of the three > > > samples to be zeroes in which case I think the med3 result will be > > zero > > > --- so choosing a pivot of zero is much more probable than one would > > > like, and doing so in many levels of recursion causes the problem. > > > > Adding some randomness to the selection of the pivot is a known > > technique to fix the oddball partitions problem. However, Bentley and > > Sedgewick proved that every quick sort algorithm has some input set tha= t > > makes it go quadratic (hence the recent popularity of introspective > > sort, which switches to heapsort if quadratic behavior is detected. Th= e > > C++ template I submitted was an example of introspective sort, but > > PostgreSQL does not use C++ so it was not helpful). > > > > > I think. I'm not too sure if the code isn't just being sloppy about > > the > > > case where many data values are equal to the pivot --- there's a > > special > > > case there to switch to insertion sort, and maybe that's getting > > invoked > > > too soon. > > > > Here are some cases known to make qsort go quadratic: > > 1. Data already sorted > > 2. Data reverse sorted > > 3. Data organ-pipe sorted or ramp > > 4. Almost all data of the same value > > > > There are probably other cases. Randomizing the pivot helps some, as > > does check for in-order or reverse order partitions. > > > > Imagine if 1/3 of the partitions fall into a category that causes > > quadratic behavior (have one of the above formats and have more than > > CUTOFF elements in them). > > > > It is doubtful that the switch to insertion sort is causing any sort of > > problems. It is only going to be invoked on tiny sets, for which it ha= s > > a fixed cost that is probably less that qsort() function calls on sets > > of the same size. > > > > >It'd be useful to get a line-level profile of the behavior of > > > this code in the slow cases... > > > > I guess that my in-order or presorted tests [which often arise when > > there are very few distinct values] may solve the bad partition > > problems. Don't forget that the algorithm is called recursively. > > > > > regards, tom lane > > > > > > ---------------------------(end of > > broadcast)--------------------------- > > > TIP 3: Have you checked our extensive FAQ? > > > > > > http://www.postgresql.org/docs/faq > > > > ---------------------------(end of broadcast)--------------------------= - > > TIP 2: Don't 'kill -9' the postmaster > > > > -- > Bruce Momjian http://candle.pha.pa.us > SRA OSS, Inc. http://www.sraoss.com > > + If your life is a hard drive, Christ can be your backup. + > > ---------------------------(end of broadcast)--------------------------- > TIP 6: explain analyze is your friend > -- Jonah H. Harris, Database Internals Architect EnterpriseDB Corporation 732.331.1324 ------=_Part_4984_1958656.1141325424234 Content-Type: text/html; charset=ISO-8859-1 Content-Transfer-Encoding: quoted-printable Content-Disposition: inline My introsort is almost complete and its the fastest variant of quicksort I can find, I'll submit it to -patches in the next couple days as-well.

On 3/2/06, Bruce Momjian <pgman@candle.pha.pa.us> wrote:

Added to TODO:

        *= Improve port/qsort() to handle sorts with 50% unique and 50% duplicate
=           value [qsort]
          This invo= lves choosing better pivot points for the quicksort.


---------------------------------------------------------------------------=

Dann Corbit wrote:
>
>
> > -----Original Messa= ge-----
> > From: pgsql-hackers-owner@postgresql.org [mailto:pgsql-hackers-
> > owner@postgresql.org] On Behalf Of Tom Lane
> > Sent: Wedne= sday, February 15, 2006 5:22 PM
> > To: Ron
> > Cc: pgsql-performance@postgresql.org; pgsql-hackers@postgresql.org
> > Su= bject: Re: [HACKERS] qsort again (was Re: [PERFORM] Strange Create
> Index
> > behaviour)
> >
> > Ron <rjpeace@earthlink.net> writes= :
> > > How are we choosing our pivots?
> >
> &g= t; See=20 qsort.c: it looks like median of nine equally spaced inputs (ie,
> &g= t; the 1/8th points of the initial input array, plus the end points),
&g= t; > implemented as two rounds of median-of-three choices.  Wi= th half of
> the
> > data inputs zero, it's not too improbable for two= out of the three
> > samples to be zeroes in which case I think t= he med3 result will be
> zero
> > --- so choosing a pivot of= zero is much more probable than one would
> > like, and doing so in many levels of recursion causes the pro= blem.
>
> Adding some randomness to the selection of the pivot = is a known
> technique to fix the oddball partitions problem. &n= bsp;However, Bentley and
> Sedgewick proved that every quick sort algorithm has some input se= t that
> makes it go quadratic (hence the recent popularity of intros= pective
> sort, which switches to heapsort if quadratic behavior is d= etected.  The
> C++ template I submitted was an example of introspective sort, but=
> PostgreSQL does not use C++ so it was not helpful).
>
>= ; > I think.  I'm not too sure if the code isn't just being sl= oppy about
> the
> > case where many data values are equal to the pivo= t --- there's a
> special
> > case there to switch to insert= ion sort, and maybe that's getting
> invoked
> > too soon.
>
> Here are some cases known to make qsort go quadratic:
&= gt; 1. Data already sorted
> 2. Data reverse sorted
> 3. Data o= rgan-pipe sorted or ramp
> 4. Almost all data of the same value
>
> There are probably other cases.  Randomizing the piv= ot helps some, as
> does check for in-order or reverse order partitio= ns.
>
> Imagine if 1/3 of the partitions fall into a category t= hat causes
> quadratic behavior (have one of the above formats and have more th= an
> CUTOFF elements in them).
>
> It is doubtful that th= e switch to insertion sort is causing any sort of
> problems. &n= bsp;It is only going to be invoked on tiny sets, for which it has
> a fixed cost that is probably less that qsort() function calls on = sets
> of the same size.
>
> >It'd be useful to get a = line-level profile of the behavior of
> > this code in the slow ca= ses...
>
> I guess that my in-order or presorted tests [which often a= rise when
> there are very few distinct values] may solve the bad par= tition
> problems.  Don't forget that the algorithm is call= ed recursively.
>
> >            = ;         regards, tom lane
> >
> > ---------------------------(end= of
> broadcast)---------------------------
> > TIP 3: Have = you checked our extensive FAQ?
> >
> >            = ;    htt= p://www.postgresql.org/docs/faq
>
> -----------------------= ----(end of broadcast)---------------------------
> TIP 2: Don't 'kil= l -9' the postmaster
>

--
  Bruce Momjian   http://candle.pha.pa.us
  SRA OSS, In= c.   http://www.sraoss.com<= br>
  + If your life is a hard drive, Christ can be your backu= p. +

---------------------------(end of broadcast)----------------------= -----
TIP 6: explain analyze is your friend


--
Jonah H. Harris, Database Internals Architect EnterpriseDB Corporation
732.331.1324
------=_Part_4984_1958656.1141325424234--