User-Agent: Microsoft-Entourage/11.2.0.050811
Date: Thu, 29 Sep 2005 21:22:27 -0700
Subject: Re: [PERFORM] A Better External Sort?
From: "Luke Lonergan" <llonergan@greenplum.com>
To: "Jeffrey W. Baker" <jwbaker@acm.org>
Cc: "Josh Berkus" <josh@agliodbs.com>,
 "Ron Peacetree" <rjpeace@earthlink.net>,
	pgsql-hackers@postgresql.org, pgsql-performance@postgresql.org
Message-ID: <BF620B93.10588%llonergan@greenplum.com>
Thread-Topic: [HACKERS] [PERFORM] A Better External Sort?
Thread-Index: AcXFdpBwzwcGjTFpEdqrvAANk63kWA==
In-Reply-To: <1128015863.11474.9.camel@noodles>
MIME-Version: 1.0
Content-Type: text/plain;
 charset=us-ascii
Content-Transfer-Encoding: 7bit

Jeff,

On 9/29/05 10:44 AM, "Jeffrey W. Baker" <jwbaker@acm.org> wrote:

> On Thu, 2005-09-29 at 10:06 -0700, Luke Lonergan wrote:
> Looking through tuplesort.c, I have a couple of initial ideas.  Are we
> allowed to fork here?  That would open up the possibility of using the
> CPU and the I/O in parallel.  I see that tuplesort.c also suffers from
> the kind of postgresql-wide disease of calling all the way up and down a
> big stack of software for each tuple individually.  Perhaps it could be
> changed to work on vectors.

Yes!
 
> I think the largest speedup will be to dump the multiphase merge and
> merge all tapes in one pass, no matter how large M.  Currently M is
> capped at 6, so a sort of 60GB with 1GB sort memory needs 13 passes over
> the tape.  It could be done in a single pass heap merge with N*log(M)
> comparisons, and, more importantly, far less input and output.

Yes again, see above.
 
> I would also recommend using an external processes to asynchronously
> feed the tuples into the heap during the merge.

Simon Riggs is working this idea a bit - it's slightly less interesting to
us because we already have a multiprocessing executor.  Our problem is that
4 x slow is still far too slow.

> What's the timeframe for 8.2?

Let's test it out in Bizgres!
 
- Luke