Обсуждение: polyphase merge?

Dear All,<br /><br />I apologize if this has been discussed before. I have tried to search to the mailing list and
couldnot find an exact answer.<br /><br />Currently, Postgres uses Knuth's Algorithm 5.4.2D to perform external merge
sort.IMHO the algorithm is designed for tapes. <br /><br />Why don't the simple text book merge pattern described in
KnuthPage 365 (5.4.9) is used for disk based system? The same merge pattern is also described in Ramakrishnan text book
andit is optimal if seek time is not counted, which of course not the real-world case.<br /><br />Best regards,<br
/><br/>Don<br /><br /> 

Dear All,<br /><br />Since nobody replied, I would give it a try. I am going to implement the merge pattern described
inKnuth Page 365 (5.4.9), essentially it is as follow:<br />- create initial runs using replacement selection
(basicallythis is as in the current implementation)<br /> - add enough dummy runs of size 0 so that the number of
sortedrun minus one can be divided by k-1 (k is merge fan in)<br />- repetitively merge k smallest runs until only 1
runleft<br /><br />I am new to postgresql, hence any advice would be appreciated.<br /><br />Can anybody give me some
adviceon how it can done? <br />1. how a run should be represented? should I reuse the tape mechanism? e.g. 1 tape 1
run<br/>- or should I use a temp buffer?<br /><br />2. How memory should be allocated? I assume I divide the memory
equallyto k runs, hence each run will get M/k memory. Each read of a run would be of size M/k bytes. <br /><br />3.
Prefetching.Then, we can precompute the read sequence of blocks of run during the entire merge process. Based on this,
weknow the blocks of run to be prefetched at a point of time.<br /><br />3. Is it possible to perform read/write I/O
whilethe merge is being performed? Hence we overlap I/O and computation.<br /><br />4. any other issue needs
consideration?<br/><br />Best regards,<br /><br />Don<br /><br /><div class="gmail_quote">On Thu, Jan 29, 2009 at 4:11
PM,Don Marvick <span dir="ltr"><<a href="mailto:donmarvick@gmail.com">donmarvick@gmail.com</a>></span> wrote:<br
/><blockquoteclass="gmail_quote" style="border-left: 1px solid rgb(204, 204, 204); margin: 0pt 0pt 0pt 0.8ex;
padding-left:1ex;">Dear All,<br /><br />I apologize if this has been discussed before. I have tried to search to the
mailinglist and could not find an exact answer.<br /><br />Currently, Postgres uses Knuth's Algorithm 5.4.2D to perform
externalmerge sort. IMHO the algorithm is designed for tapes. <br /><br />Why don't the simple text book merge pattern
describedin Knuth Page 365 (5.4.9) is used for disk based system? The same merge pattern is also described in
Ramakrishnantext book and it is optimal if seek time is not counted, which of course not the real-world case.<br /><br
/>Bestregards,<br /><font color="#888888"><br />Don<br /><br /></font></blockquote></div><br /> 

On Wed, 2009-02-04 at 14:42 +0800, Don Marvick wrote:

> 4. any other issue needs consideration?

Most attempts to improve sorting further have fallen to nothing because
of the lack of repeatable test results. In particular, coming up with
test cases *after* writing the code is a good way to get lost in
discussions and have your work passed over.

The best starting point is to collect a number of test cases, both
typical and extreme cases. Do some research to show that "typical" cases
really are that and be prepared for some expressions of reasonable
doubt. Publish that data so test results can be objectively verified and
then measure those cases on existing code, with various settings of
tunable parameters.

Then it will be a simple matter to prove your changes are effective in
target cases without damaging other cases. We would also want the
changes to work automatically without additional tunable parameters.

-- Simon Riggs           www.2ndQuadrant.comPostgreSQL Training, Services and Support

Is this basically the same as our current algorithm but without
multiplexing the tapes onto single files? I have been wondering
whether we multiplex the tapes any better than filesystems can lay out
separate files actually.

Or is there something else that's different here?

-- 
greg

On Wed, 2009-02-04 at 10:55 +0000, Greg Stark wrote:
> Is this basically the same as our current algorithm but without
> multiplexing the tapes onto single files? I have been wondering
> whether we multiplex the tapes any better than filesystems can lay out
> separate files actually.

I don't think you'll be able to do that more efficiently than we already
do. Read the top of tuplesort.c

-- Simon Riggs           www.2ndQuadrant.comPostgreSQL Training, Services and Support

Greg Stark <stark@enterprisedb.com> writes:
> Is this basically the same as our current algorithm but without
> multiplexing the tapes onto single files? I have been wondering
> whether we multiplex the tapes any better than filesystems can lay out
> separate files actually.

The reason for the multiplexing is so that space can get re-used
quickly.  If each tape were represented as a separate file, there would
be no way to release blocks as they're read; you could only give back
the whole file after reaching end of tape.  Which would at least double
the amount of disk space needed to sort X amount of data.  (It's
actually even worse, more like 4X, though the multiplier might depend on
the number of "tapes" --- I don't recall the details anymore.)

The penalty we pay is that in the later merge passes, the blocks
representing a single tape aren't very well ordered.

It might be interesting to think about some compromise that wastes a
little more space in order to get better sequentiality of disk access.
It'd be easy to do if we were willing to accept a 2X space penalty,
but I'm not sure if that would fly or not.  It definitely *wasn't*
acceptable to the community a few years ago when the current code was
written.  Disks have gotten bigger since then, but so have the problems
people want to solve.
        regards, tom lane

Don Marvick <donmarvick@gmail.com> writes:
> Since nobody replied, I would give it a try. I am going to implement the
> merge pattern described in Knuth Page 365 (5.4.9), essentially it is as
> follow:
> - create initial runs using replacement selection (basically this is as in
> the current implementation)
> - add enough dummy runs of size 0 so that the number of sorted run minus one
> can be divided by k-1 (k is merge fan in)
> - repetitively merge k smallest runs until only 1 run left

How is this better than, or even different from, what is there now?
        regards, tom lane

Simon Riggs <simon@2ndQuadrant.com> writes:

> On Wed, 2009-02-04 at 10:55 +0000, Greg Stark wrote:
>> Is this basically the same as our current algorithm but without
>> multiplexing the tapes onto single files? I have been wondering
>> whether we multiplex the tapes any better than filesystems can lay out
>> separate files actually.
>
> I don't think you'll be able to do that more efficiently than we already
> do. Read the top of tuplesort.c

Huh?

The question I posed was whether we do it any better than filesystems do, not
whether we could do a better job. If filesystems can do as good a job then we
might as well create separate files for each tape and let the filesystem
decide where to allocate space. That would mean we could massively simplify
logtape.c and just create a separate file for every tape.

Possible reasons that filesystems could do better than us are that they have
access to more information about actual storage layout on disk, that they have
more information about hardware characteristics, and that it would give the
filesystem cache a better idea of the access pattern which logtape.c might be
confusing the picture of currently.

On the other hand possible reasons why filesystems would suck at this include
creating and deleting new files being a slow or locking operation on many
filesystems, and dealing with directories of large numbers of files being
poorly optimized on others.

--  Gregory Stark EnterpriseDB          http://www.enterprisedb.com Ask me about EnterpriseDB's RemoteDBA services!

Good point. I would note this issue. Thanks for the advice :).<br /><br />Regards,<br /><br />Don<br /><br /><div
class="gmail_quote">OnWed, Feb 4, 2009 at 6:09 PM, Simon Riggs <span dir="ltr"><<a
href="mailto:simon@2ndquadrant.com">simon@2ndquadrant.com</a>></span>wrote:<br /><blockquote class="gmail_quote"
style="border-left:1px solid rgb(204, 204, 204); margin: 0pt 0pt 0pt 0.8ex; padding-left: 1ex;"><div class="Ih2E3d"><br
/>On Wed, 2009-02-04 at 14:42 +0800, Don Marvick wrote:<br /><br /> > 4. any other issue needs consideration?<br
/><br/></div>Most attempts to improve sorting further have fallen to nothing because<br /> of the lack of repeatable
testresults. In particular, coming up with<br /> test cases *after* writing the code is a good way to get lost in<br />
discussionsand have your work passed over.<br /><br /> The best starting point is to collect a number of test cases,
both<br/> typical and extreme cases. Do some research to show that "typical" cases<br /> really are that and be
preparedfor some expressions of reasonable<br /> doubt. Publish that data so test results can be objectively verified
and<br/> then measure those cases on existing code, with various settings of<br /> tunable parameters.<br /><br /> Then
itwill be a simple matter to prove your changes are effective in<br /> target cases without damaging other cases. We
wouldalso want the<br /> changes to work automatically without additional tunable parameters.<br /><font
color="#888888"><br/> --<br />  Simon Riggs           <a href="http://www.2ndQuadrant.com"
target="_blank">www.2ndQuadrant.com</a><br/>  PostgreSQL Training, Services and Support<br /><br
/></font></blockquote></div><br/> 

This is what I understand from existing implementation:<br />- fix the merge fan in F, and number of tapes=F+1<br />-
foreach sorted run generated, we have a formula to determine which tape it belongs to<br />- the sorted run is added to
theend of the tape<br /> - all sorted runs have been added to tape. There is always an empty tape called output tape<br
/>-add dummy runs if necessary, to each tape<br />- merge the input tapes, write result to output tape, until one of
theinput tape is empty<br /> - repeat this process until 1 sorted run remains<br /><br /><br />I think the main
differenceis that at each step, the current impl does not merge the smallest k-runs. It merges from the beginning of
eachtape. For 1 pass, this does not make any difference. For 2 passes onwards there are some differences. In some
complexquery, where the memory is eaten by some other operators, more passes are needed and the differences become
larger.This is the only improvement that can be achieved. Let me know if this does not make any sense.<br /><br
/>Regardingdisk layout, I am open to suggestion whether we should reuse the tape module or not. <br /><br /><br /><br
/><divclass="gmail_quote">On Wed, Feb 4, 2009 at 11:20 PM, Tom Lane <span dir="ltr"><<a
href="mailto:tgl@sss.pgh.pa.us">tgl@sss.pgh.pa.us</a>></span>wrote:<br /><blockquote class="gmail_quote"
style="border-left:1px solid rgb(204, 204, 204); margin: 0pt 0pt 0pt 0.8ex; padding-left: 1ex;"><div class="Ih2E3d">Don
Marvick<<a href="mailto:donmarvick@gmail.com">donmarvick@gmail.com</a>> writes:<br /> > Since nobody replied,
Iwould give it a try. I am going to implement the<br /> > merge pattern described in Knuth Page 365 (5.4.9),
essentiallyit is as<br /> > follow:<br /> > - create initial runs using replacement selection (basically this is
asin<br /> > the current implementation)<br /> > - add enough dummy runs of size 0 so that the number of sorted
runminus one<br /> > can be divided by k-1 (k is merge fan in)<br /> > - repetitively merge k smallest runs until
only1 run left<br /><br /></div>How is this better than, or even different from, what is there now?<br /><br />        
              regards, tom lane<br /></blockquote></div><br /> 

Hmm probably it's worth to try this. Has anybody try this before? If not, I am interested to give it a try.<br /><br
/>Regards,<br/><br />Don<br /><br /><div class="gmail_quote">On Wed, Feb 4, 2009 at 11:25 PM, Gregory Stark <span
dir="ltr"><<ahref="mailto:stark@enterprisedb.com">stark@enterprisedb.com</a>></span> wrote:<br /><blockquote
class="gmail_quote"style="border-left: 1px solid rgb(204, 204, 204); margin: 0pt 0pt 0pt 0.8ex; padding-left:
1ex;"><divclass="Ih2E3d">Simon Riggs <simon@2ndQuadrant.com> writes:<br /><br /> > On Wed, 2009-02-04 at 10:55
+0000,Greg Stark wrote:<br /> >> Is this basically the same as our current algorithm but without<br /> >>
multiplexingthe tapes onto single files? I have been wondering<br /> >> whether we multiplex the tapes any better
thanfilesystems can lay out<br /> >> separate files actually.<br /> ><br /> > I don't think you'll be able
todo that more efficiently than we already<br /> > do. Read the top of tuplesort.c<br /><br /></div>Huh?<br /><br />
Thequestion I posed was whether we do it any better than filesystems do, not<br /> whether we could do a better job. If
filesystemscan do as good a job then we<br /> might as well create separate files for each tape and let the
filesystem<br/> decide where to allocate space. That would mean we could massively simplify<br /> logtape.c and just
createa separate file for every tape.<br /><br /> Possible reasons that filesystems could do better than us are that
theyhave<br /> access to more information about actual storage layout on disk, that they have<br /> more information
abouthardware characteristics, and that it would give the<br /> filesystem cache a better idea of the access pattern
whichlogtape.c might be<br /> confusing the picture of currently.<br /><br /> On the other hand possible reasons why
filesystemswould suck at this include<br /> creating and deleting new files being a slow or locking operation on
many<br/> filesystems, and dealing with directories of large numbers of files being<br /> poorly optimized on
others.<br/><font color="#888888"><br /> --<br />  Gregory Stark<br />  EnterpriseDB          <a
href="http://www.enterprisedb.com"target="_blank">http://www.enterprisedb.com</a><br />  Ask me about EnterpriseDB's
RemoteDBAservices!<br /></font></blockquote></div><br />