Skip site navigation (1) Skip section navigation (2)

Re: Re: Which qsort is used

From: Manfred Koizar <mkoi-pg(at)aon(dot)at>
To: Tom Lane <tgl(at)sss(dot)pgh(dot)pa(dot)us>
Cc: "Dann Corbit" <DCorbit(at)connx(dot)com>, "Qingqing Zhou" <zhouqq(at)cs(dot)toronto(dot)edu>, "Bruce Momjian" <pgman(at)candle(dot)pha(dot)pa(dot)us>, "Luke Lonergan" <llonergan(at)greenplum(dot)com>, "Neil Conway" <neilc(at)samurai(dot)com>, pgsql-hackers(at)postgresql(dot)org
Subject: Re: Re: Which qsort is used
Date: 2005-12-22 00:43:34
Message-ID: odqjq1tv6cb77ri4df0aehqal8o0ljtkar@4ax.com (view raw or flat)
Thread:
Lists: pgsql-hackers
On Sat, 17 Dec 2005 00:03:25 -0500, Tom Lane <tgl(at)sss(dot)pgh(dot)pa(dot)us>
wrote:
>I've still got a problem with these checks; I think they are a net
>waste of cycles on average.  [...]
> and when they fail, those cycles are entirely wasted;
>you have not advanced the state of the sort at all.

How can we make the initial check "adavance the state of the sort"?
One answer might be to exclude the sorted sequence at the start of the
array from the qsort, and merge the two sorted lists as the final
stage of the sort.

Qsorting N elements costs O(N*lnN), so excluding H elements from the
sort reduces the cost by at least O(H*lnN).  The merge step costs O(N)
plus some (<=50%) more memory, unless someone knows a fast in-place
merge.  So depending on the constant factors involved there might be a
usable solution.

I've been playing with some numbers and assuming the constant factors
to be equal for all the O()'s this method starts to pay off at
	  H      for N
	  20       100
	 130      1000
	8000    100000
Servus
 Manfred

In response to

Responses

pgsql-hackers by date

Next:From: Jim C. NasbyDate: 2005-12-22 00:54:08
Subject: Re: Automatic function replanning
Previous:From: Tom LaneDate: 2005-12-22 00:07:23
Subject: Re: Unsplitting btree index leaf pages

Privacy Policy | About PostgreSQL
Copyright © 1996-2014 The PostgreSQL Global Development Group