To: Tom Lane <tgl@sss.pgh.pa.us>
Cc: "Jeffrey W. Baker" <jwbaker@acm.org>,
	Luke Lonergan <llonergan@greenplum.com>, Josh Berkus <josh@agliodbs.com>,
	Ron Peacetree <rjpeace@earthlink.net>, pgsql-hackers@postgresql.org,
	pgsql-performance@postgresql.org
Subject: Re: [HACKERS] A Better External Sort?
References: <BF616D3C.104C3%llonergan@greenplum.com>
	<1128015863.11474.9.camel@noodles> <5709.1128146518@sss.pgh.pa.us>
In-Reply-To: <5709.1128146518@sss.pgh.pa.us>
From: Greg Stark <gsstark@mit.edu>
Organization: The Emacs Conspiracy; member since 1992
Date: 01 Oct 2005 12:17:17 -0400
Message-ID: <87r7b5ciuq.fsf@stark.xeocode.com>
Lines: 33
User-Agent: Gnus/5.09 (Gnus v5.9.0) Emacs/21.4
MIME-Version: 1.0
Content-Type: text/plain; charset=us-ascii


Tom Lane <tgl@sss.pgh.pa.us> writes:

> "Jeffrey W. Baker" <jwbaker@acm.org> writes:
> > 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.
> 
> I had more or less despaired of this thread yielding any usable ideas
> :-( but I think you have one here.  The reason the current code uses a
> six-way merge is that Knuth's figure 70 (p. 273 of volume 3 first
> edition) shows that there's not much incremental gain from using more
> tapes ... if you are in the regime where number of runs is much greater
> than number of tape drives.  But if you can stay in the regime where
> only one merge pass is needed, that is obviously a win.

Is that still true when the multiple tapes are being multiplexed onto a single
actual file on disk?

That brings up one of my pet features though. The ability to declare multiple
temporary areas on different spindles and then have them be used on a rotating
basis. So a sort could store each tape on a separate spindle and merge them
together at full sequential i/o speed.

This would make the tradeoff between multiway merges and many passes even
harder to find though. The broader the multiway merges the more sort areas
would be used which would increase the likelihood of another sort using the
same sort area and hurting i/o performance.

-- 
greg