Re: Replacement Selection

"Tom Lane" <tgl(at)sss(dot)pgh(dot)pa(dot)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 current run and next-run tuples
in the same heap (yup, Knuth is smarter than I am). And, during merge
passes, make use of available sort memory to load multiple tuples from any
one input 'tape' at a time, thereby improving locality of access to the temp
file.

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