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

Re: Replacement Selection

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

In response to

pgsql-hackers by date

Next:From: Jacob RiefDate: 2007-11-26 22:56:39
Subject: Table inheritance, unique constraints and foreign key problem
Previous:From: Dave PageDate: 2007-11-26 22:53:19
Subject: Re: Locating sharedir in PostgreSQL on Windows

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