Re: Replacement Selection

"Tom Lane" <tgl@sss.pgh.pa.us> writes:

> AFAICS that produces runs that are *exactly* the same length as Knuth's
> method --- you're just using a different technique for detecting when
> the run is over, to wit "record is not in heap" vs "record is in heap
> but with a higher run number".  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:
 revision 1.2 date: 1999-10-30 18:27:15 +0100;  author: tgl;  state: Exp;  lines: +423 -191;
 Further performance improvements in sorting: reduce number of comparisons during initial run formation by keeping both
currentrun and next-run tuples in the same heap (yup, Knuth is smarter than I am). And, during merge passes, make use
ofavailable sort memory to load multiple tuples from any one input 'tape' at a time, thereby improving locality of
accessto the temp file.
 

--  Gregory Stark EnterpriseDB          http://www.enterprisedb.com Ask me about EnterpriseDB's On-Demand Production
Tuning