From: Tom Lane <tgl@sss.pgh.pa.us>
To: Ron Peacetree <rjpeace@earthlink.net>
Cc: Simon Riggs <simon@2ndquadrant.com>
Cc: pgsql-hackers@postgresql.org
Cc: pgsql-performance@postgresql.org
Subject: Re: [PERFORM] Releasing memory during External sorting?
Date: Fri, 23 Sep 2005 13:17:24 -0400
Message-ID: <5021.1127495844@sss.pgh.pa.us> (raw)
In-Reply-To: <2559192.1127494115558.JavaMail.root@elwamui-huard.atl.sa.earthlink.net>
References: <2559192.1127494115558.JavaMail.root@elwamui-huard.atl.sa.earthlink.net>
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
Reply instructions:
You may reply publicly to this message via plain-text email
using any one of the following methods:
* Reply to all the recipients using the --to and --cc options:
reply via email
To: pgsql-performance@postgresql.org
Cc: tgl@sss.pgh.pa.us, rjpeace@earthlink.net, simon@2ndquadrant.com, pgsql-hackers@postgresql.org
Subject: Re: [PERFORM] Releasing memory during External sorting?
In-Reply-To: <5021.1127495844@sss.pgh.pa.us>
* Save the following mbox file, import it into your mail client,
and reply-to-all from there: mbox
This inbox is served by DDX for PostgreSQL; see mirroring instructions
for how to clone and mirror all data and code used for this inbox