I must precise that it's not the improvement. Other more complex algorithms
correspond to the refinements, but at the moment I just want to know which
part of PostgreSQL code does what. I also implemented Replacement Selection
(RS) so if I'm able to integrate my RS I hope I would be able to integrate
the others too.
Anyway, even in my RS implementation a longer run is created. The first M
initialization elements will surely form part of the current run. M is the
memory size so at least a run sized M will be created. After initialization,
the elements are not suddenly output, but an element from heap is output
into run as soon as I get an element from stream. In other words, for each
element from stream, the root element of the heap is output, and the input
element takes the root place into the heap. If that element is a "good
record" I just heapify (since the element will be placed at the now free
root place). If that input element is a dead record I swap it with the last
leaf and reduce the heap size.
--------------------------------------------------
From: "Tom Lane" <[EMAIL PROTECTED]>
Sent: Monday, November 26, 2007 7:31 PM
To: <[EMAIL PROTECTED]>
Cc: <pgsql-hackers@postgresql.org>
Subject: Re: [HACKERS] Replacement Selection
<[EMAIL PROTECTED]> writes:
3) Start run generation. As for this phase, I see PostgreSQL code (as
Knuth
algorithm) marks elements belonging to runs in otder to know which run
they
belong to and to know when the current heap has finished building the
current run. I don't memorize this kind of info. I just output from heap
to
run all of the elements going into the current run. The elements supposed
to
go into the next run (I call them "dead records") are still stored into
main
memory, but as leaves of the heap. This implies reducing the heap size
and
so heapifying a smaller number of elements each time I get a dead record
(it's not necessary to sort dead records). When the heap size is zero a
new
run is created heapifying all the dead records currently present into
main
memory.
Why would this be an improvement over Knuth? AFAICS you can't generate
longer runs this way, and it's not saving any time --- in fact it's
costing time, because re-heapifying adds a lot of new comparisons.
regards, tom lane
---------------------------(end of broadcast)---------------------------
TIP 9: In versions below 8.0, the planner will ignore your desire to
choose an index scan if your joining column's datatypes do not
match
