Re: Replacement Selection

Gregory Stark <stark(at)enterprisedb(dot)com> writes:
> "Tom Lane" <tgl(at)sss(dot)pgh(dot)pa(dot)us> writes:
>> I guess you would save some comparisons
>> while the heap is shrinking, but it's not at all clear that you'd save
>> more than what it will cost you to re-heapify all the dead records once
>> the run is over.

> This sounded familiar... It sounds a lot like what this CVS log message is
> describing as a mistaken idea:

Wow, I had forgotten all about that; but yeah this sounds exactly like
my first-cut rewrite of PG's sorting back in 1999. I have some vague
memory of having dismissed Knuth's approach as being silly because of
the extra space and (small number of) cycles needed to compare run
numbers in the heap. I hadn't realized that there was an impact on
total number of comparisons required :-(

The discussion from that time period in pgsql-hackers makes it sound
like you need a large test case to notice the problem, though.

regards, tom lane