Re: [PERFORM] Releasing memory during External sorting?

From: Tom Lane <tgl(at)sss(dot)pgh(dot)pa(dot)us>
To: Ron Peacetree <rjpeace(at)earthlink(dot)net>
Cc: Simon Riggs <simon(at)2ndquadrant(dot)com>, pgsql-hackers(at)postgresql(dot)org, pgsql-performance(at)postgresql(dot)org
Subject: Re: [PERFORM] Releasing memory during External sorting?
Date: 2005-09-23 17:17:24
Message-ID: 5021.1127495844@sss.pgh.pa.us
Views: Raw Message | Whole Thread | Download mbox | Resend email
Thread:
Lists: pgsql-hackers pgsql-performance

Ron Peacetree <rjpeace(at)earthlink(dot)net> writes:
> 2= No optimal external sorting algorithm should use more than 2 passes.
> 3= Optimal external sorting algorithms should use 1 pass if at all possible.

A comparison-based sort must use at least N log N operations, so it
would appear to me that if you haven't got approximately log N passes
then your algorithm doesn't work.

regards, tom lane

In response to

Responses

Browse pgsql-hackers by date

  From Date Subject
Next Message Bruce Momjian 2005-09-23 17:37:18 Re: 2 forks for md5?
Previous Message Ron Peacetree 2005-09-23 16:48:35 Re: [PERFORM] Releasing memory during External sorting?

Browse pgsql-performance by date

  From Date Subject
Next Message Stef 2005-09-23 17:18:03 Re: VACUUM FULL vs CLUSTER
Previous Message Gurpreet Aulakh 2005-09-23 17:15:36 Re: Query slower on 8.0.3 (Windows) vs 7.3 (cygwin)