Subject: Re: [PERFORM] Releasing memory during External sorting?
From: Mark Lewis <mark.lewis@mir3.com>
To: Tom Lane <tgl@sss.pgh.pa.us>
Cc: Ron Peacetree <rjpeace@earthlink.net>,
	Simon Riggs <simon@2ndquadrant.com>, pgsql-hackers@postgresql.org,
	pgsql-performance@postgresql.org
In-Reply-To: <5021.1127495844@sss.pgh.pa.us>
References: 
 <2559192.1127494115558.JavaMail.root@elwamui-huard.atl.sa.earthlink.net>
	<5021.1127495844@sss.pgh.pa.us>
Content-Type: text/plain
Organization: MIR3, Inc.
Date: Fri, 23 Sep 2005 10:43:02 -0700
Message-Id: <1127497383.23567.218.camel@archimedes>
Mime-Version: 1.0
Content-Transfer-Encoding: 7bit

operations != passes.  If you were clever, you could probably write a
modified bubble-sort algorithm that only made 2 passes.  A pass is a
disk scan, operations are then performed (hopefully in memory) on what
you read from the disk.  So there's no theoretical log N lower-bound on
the number of disk passes.

Not that I have anything else useful to add to this discussion, just a
tidbit I remembered from my CS classes back in college :)

-- Mark

On Fri, 2005-09-23 at 13:17 -0400, Tom Lane wrote:
> Ron Peacetree <rjpeace@earthlink.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
> 
> ---------------------------(end of broadcast)---------------------------
> TIP 9: In versions below 8.0, the planner will ignore your desire to
>        choose an index scan if your joining column's datatypes do not
>        match