"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