Gregory Stark <stark@enterprisedb.com> writes:
> "Tom Lane" <tgl@sss.pgh.pa.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