Re: Replacement Selection

On Tue, 2007-11-27 at 09:25 +0100, mac_man2005(at)hotmail(dot)it wrote:

> Others optimizations, for example, can be done with the "virtual
> concatenation" technique:
> storing a cache of couples (first_element,last_element) for each created
> run. This
> could be useful in case we can find 2 couples (first_element_1,
> last_element_1) and
> (first_element_2, last_element_2) with last_element_1 <= first_element_2.
> In this case, those runs too can be seen as belonging to the same "logical
> run"
> (actually they are 2 RS different physical runs, or even 4 in 2WRS
> but can be seen as just one by mergesort). Of course, once those 2 (or 4)
> runs are
> logically merged into that only one, this last one in turn could be merged
> to other runs.
>
> What does all that imply? Mergesort would actually consider a smaller number
> of runs
> (since it should just work on logical runs). This means less jumps between
> runs on disk.

That's actually a refinement of an idea I've been working on for
optimizing sort. I'll post those separately.

--
Simon Riggs
2ndQuadrant http://www.2ndQuadrant.com