Re: Replacement Selection

Any comment about Two Ways Replacement Selection (two heaps instead of just
one) ?

--------------------------------------------------
From: "Simon Riggs" <simon(at)2ndquadrant(dot)com>
Sent: Tuesday, November 27, 2007 1:03 PM
To: <mac_man2005(at)hotmail(dot)it>
Cc: <pgsql-hackers(at)postgresql(dot)org>
Subject: Re: [HACKERS] 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
>
>
> ---------------------------(end of broadcast)---------------------------
> TIP 7: You can help support the PostgreSQL project by donating at
>
> http://www.postgresql.org/about/donate
>