Re: Polyphase Merge

On Mon, Jan 21, 2008 at 04:13:32PM -0500, Tom Lane wrote:
> Sam Mason <sam(at)samason(dot)me(dot)uk> writes:
> > It's really up to you to find answers to these questions, especially
> > the first one. Once you've designed an efficient algorithm then the
> > second point (which I'm interpreting as how you'd go about changing
> > tuplestore(?) so that things can be read in reverse order) should
> > just drop out as an implementation detail :) I'm guessing you'll
> > end up not reading the store in reverse order but arranging things
> > differently---it'll be interesting to see.
>
> I agree --- having to read the run back from external storage, only to
> write it out again with no further useful work done on it, sounds like
> a guaranteed loser.

Manolo's idea (wherever it came from) will generate longer runs in some
specific non-random data distributions (i.e. hopefully real life), but
it'll obviously only be a net win if this is offset by not having to do
any extra work reordering data. It would be great if it could be got to
work!

> To make this work you'll need some kind of ju-jitsu
> rearrangement that logically puts the run where it needs to go without
> physically moving any data.

yup, that's the fun part :)

Sam