Skip site navigation (1) Skip section navigation (2)

Re: Replacement Selection

From: Gregory Stark <stark(at)enterprisedb(dot)com>
To: "Tom Lane" <tgl(at)sss(dot)pgh(dot)pa(dot)us>
Cc: <mac_man2005(at)hotmail(dot)it>, <pgsql-hackers(at)postgresql(dot)org>
Subject: Re: Replacement Selection
Date: 2007-11-26 22:37:14
Message-ID: 87k5o4eiqt.fsf@oxford.xeocode.com (view raw or flat)
Thread:
Lists: pgsql-hackers
"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

In response to

Responses

pgsql-hackers by date

Next:From: Mark Cave-AylandDate: 2007-11-26 22:49:20
Subject: Re: Locating sharedir in PostgreSQL on Windows
Previous:From: Tom LaneDate: 2007-11-26 22:34:03
Subject: Re: [GENERAL] Empty arrays with ARRAY[]

Privacy Policy | About PostgreSQL
Copyright © 1996-2014 The PostgreSQL Global Development Group