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