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

Re: [PERFORM] Releasing memory during External sorting?

From: Tom Lane <tgl(at)sss(dot)pgh(dot)pa(dot)us>
To: Mark Lewis <mark(dot)lewis(at)mir3(dot)com>
Cc: Ron Peacetree <rjpeace(at)earthlink(dot)net>,Simon Riggs <simon(at)2ndquadrant(dot)com>, pgsql-hackers(at)postgresql(dot)org,pgsql-performance(at)postgresql(dot)org
Subject: Re: [PERFORM] Releasing memory during External sorting?
Date: 2005-09-23 18:15:40
Message-ID: 5441.1127499340@sss.pgh.pa.us (view raw or flat)
Thread:
Lists: pgsql-hackerspgsql-performance
Mark Lewis <mark(dot)lewis(at)mir3(dot)com> writes:
> operations != passes.  If you were clever, you could probably write a
> modified bubble-sort algorithm that only made 2 passes.  A pass is a
> disk scan, operations are then performed (hopefully in memory) on what
> you read from the disk.  So there's no theoretical log N lower-bound on
> the number of disk passes.

Given infinite memory that might be true, but I don't think I believe it
for limited memory.  If you have room for K tuples in memory then it's
impossible to perform more than K*N useful comparisons per pass (ie, as
each tuple comes off the disk you can compare it to all the ones
currently in memory; anything more is certainly redundant work).  So if
K < logN it's clearly not gonna work.

It's possible that you could design an algorithm that works in a fixed
number of passes if you are allowed to assume you can hold O(log N)
tuples in memory --- and in practice that would probably work fine,
if the constant factor implied by the O() isn't too big.  But it's not
really solving the general external-sort problem.

			regards, tom lane

In response to

pgsql-performance by date

Next:From: Martijn van OosterhoutDate: 2005-09-23 18:32:46
Subject: Re: Releasing memory during External sorting?
Previous:From: Chris BrowneDate: 2005-09-23 17:48:32
Subject: Re: VACUUM FULL vs CLUSTER

pgsql-hackers by date

Next:From: Martijn van OosterhoutDate: 2005-09-23 18:32:46
Subject: Re: Releasing memory during External sorting?
Previous:From: Jeremy DrakeDate: 2005-09-23 18:07:30
Subject: Re: 64-bit API for large objects

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