n Oosterhout
> Cc: Tom Lane; Dann Corbit; Qingqing Zhou; Bruce Momjian; Luke
Lonergan;
> Neil Conway; pgsql-hackers@postgresql.org
> Subject: Re: [HACKERS] Re: Which qsort is used
>
> On Thu, 22 Dec 2005 08:01:00 +0100, Martijn van Oosterhout
> wrote:
> >But where are you
On Thu, 22 Dec 2005 08:01:00 +0100, Martijn van Oosterhout
wrote:
>But where are you including the cost to check how many cells are
>already sorted? That would be O(H), right?
Yes. I didn't mention it, because H < N.
> This is where we come back
>to the issue that comparisons in PostgreSQL are
On Thu, Dec 22, 2005 at 01:43:34AM +0100, Manfred Koizar wrote:
> 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 dependin
On Sat, 17 Dec 2005 00:03:25 -0500, Tom Lane <[EMAIL PROTECTED]>
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 ma
Martin,
On 12/19/05 3:37 AM, "Martijn van Oosterhout" wrote:
> I'm not sure whether we have a conclusion here, but I do have one
> question: is there a significant difference in the number of times the
> comparison routines are called? Comparisons in PostgreSQL are fairly
> expensive given the f
On Fri, Dec 16, 2005 at 10:43:58PM -0800, Dann Corbit wrote:
> I am actually quite impressed with the excellence of Bentley's sort out
> of the box. It's definitely the best library implementation of a sort I
> have seen.
I'm not sure whether we have a conclusion here, but I do have one
question:
> -Original Message-
> From: Tom Lane [mailto:[EMAIL PROTECTED]
> Sent: Friday, December 16, 2005 10:41 PM
> To: Dann Corbit
> Cc: Qingqing Zhou; Bruce Momjian; Luke Lonergan; Neil Conway; pgsql-
> [EMAIL PROTECTED]
> Subject: Re: [HACKERS] Re: Which qsort is u
"Dann Corbit" <[EMAIL PROTECTED]> writes:
>> I've still got a problem with these checks; I think they are a net
>> waste of cycles on average.
> The benchmarks say that they (order checks) are a good idea on average
> for ordered data, random data, and partly ordered data.
There are lies, damn li
> -Original Message-
> From: Qingqing Zhou [mailto:[EMAIL PROTECTED]
> Sent: Friday, December 16, 2005 10:13 PM
> To: Dann Corbit
> Cc: Tom Lane; Bruce Momjian; Luke Lonergan; Neil Conway; pgsql-
> [EMAIL PROTECTED]
> Subject: RE: [HACKERS] Re: Which qsort is used
>
On Sat, 17 Dec 2005, Dann Corbit wrote:
>
> The benchmarks say that they (order checks) are a good idea on average
> for ordered data, random data, and partly ordered data.
>
I interpret that in linux, 500 seems a divide for qsortpdq. Before
that number, it wins, after that, bsd wins more.
> -Original Message-
> From: Tom Lane [mailto:[EMAIL PROTECTED]
> Sent: Friday, December 16, 2005 9:03 PM
> To: Dann Corbit
> Cc: Qingqing Zhou; Bruce Momjian; Luke Lonergan; Neil Conway; pgsql-
> [EMAIL PROTECTED]
> Subject: Re: [HACKERS] Re: Which qsort is used
>
"Dann Corbit" <[EMAIL PROTECTED]> writes:
> Both of them are modified versions of Bentley's sort algorithm.
Jon Bentley of Bell Labs? Small world ... he was my thesis adviser
for awhile when he was at CMU. He's a good algorithms man, for sure.
> I just added the in-order check to both of them,
> -Original Message-
> From: [EMAIL PROTECTED] [mailto:pgsql-hackers-
> [EMAIL PROTECTED] On Behalf Of Qingqing Zhou
> Sent: Friday, December 16, 2005 5:14 PM
> To: Bruce Momjian
> Cc: Luke Lonergan; Tom Lane; Neil Conway; pgsql-hackers@postgresql.org
> Subject: Re
On Fri, 16 Dec 2005, Bruce Momjian wrote:
>
> At this point, I think we have done enough testing on enough platforms
> to just use port/qsort on all platforms in 8.2. It seems whenever
> someone tries to improve the BSD qsort, they make it worse.
>
Not necessariliy true. Dann Corbit sent me an
Luke Lonergan wrote:
> Tom,
>
> On 12/12/05 2:47 PM, "Tom Lane" <[EMAIL PROTECTED]> wrote:
>
> > As those results suggest, there can be huge differences in sort
> > performance depending on whether the input is random, nearly sorted,
> > nearly reverse sorted, possesses many equal keys, etc. It
15 matches
Mail list logo
