Re: Replacement Selection

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


--------------------------------------------------
From: "Simon Riggs" <simon@2ndquadrant.com>
Sent: Tuesday, November 27, 2007 1:03 PM
To: <mac_man2005@hotmail.it>
Cc: <pgsql-hackers@postgresql.org>
Subject: Re: [HACKERS] Replacement Selection

> On Tue, 2007-11-27 at 09:25 +0100, mac_man2005@hotmail.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
>