Re: polyphase merge?

Dear All,

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

I am new to postgresql, hence any advice would be appreciated.

Can anybody give me some advice on how it can done?
1. how a run should be represented? should I reuse the tape mechanism? e.g.
1 tape 1 run
- or should I use a temp buffer?

2. How memory should be allocated? I assume I divide the memory equally to k
runs, hence each run will get M/k memory. Each read of a run would be of
size M/k bytes.

3. Prefetching. Then, we can precompute the read sequence of blocks of run
during the entire merge process. Based on this, we know the blocks of run to
be prefetched at a point of time.

3. Is it possible to perform read/write I/O while the merge is being
performed? Hence we overlap I/O and computation.

4. any other issue needs consideration?

Best regards,

Don

On Thu, Jan 29, 2009 at 4:11 PM, Don Marvick <donmarvick(at)gmail(dot)com> wrote:

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