From: Greg Stark <gsstark@mit.edu>
To: Tom Lane <tgl@sss.pgh.pa.us>
Cc: Jeffrey W. Baker <jwbaker@acm.org>
Cc: Luke Lonergan <llonergan@greenplum.com>
Cc: Josh Berkus <josh@agliodbs.com>
Cc: Ron Peacetree <rjpeace@earthlink.net>
Cc: pgsql-hackers@postgresql.org
Cc: pgsql-performance@postgresql.org
Subject: Re: [HACKERS] A Better External Sort?
Date: 01 Oct 2005 12:17:17 -0400
Message-ID: <87r7b5ciuq.fsf@stark.xeocode.com> (raw)
In-Reply-To: <5709.1128146518@sss.pgh.pa.us>
References: <BF616D3C.104C3%llonergan@greenplum.com>
<1128015863.11474.9.camel@noodles>
<5709.1128146518@sss.pgh.pa.us>
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
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: gsstark@mit.edu, tgl@sss.pgh.pa.us, jwbaker@acm.org, llonergan@greenplum.com, josh@agliodbs.com, rjpeace@earthlink.net, pgsql-hackers@postgresql.org
Subject: Re: [HACKERS] A Better External Sort?
In-Reply-To: <87r7b5ciuq.fsf@stark.xeocode.com>
* 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