Any comment about Two Ways Replacement Selection (two heaps instead of just
one) ?
--------------------------------------------------
From: "Simon Riggs" <[EMAIL PROTECTED]>
Sent: Tuesday, November 27, 2007 1:03 PM
To: <[EMAIL PROTECTED]>
Cc: <pgsql-hackers@postgresql.org>
Subject: Re: [HACKERS] Replacement Selection
On Tue, 2007-11-27 at 09:25 +0100, [EMAIL PROTECTED] 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
---------------------------(end of broadcast)---------------------------
TIP 1: if posting/reading through Usenet, please send an appropriate
subscribe-nomail command to [EMAIL PROTECTED] so that your
message can get through to the mailing list cleanly
