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 |
Views: | Raw Message | Whole Thread | Download mbox | Resend email |
Thread: | |
Lists: | pgsql-hackers pgsql-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
From | Date | Subject | |
---|---|---|---|
Next Message | Martijn van Oosterhout | 2005-09-23 18:32:46 | Re: Releasing memory during External sorting? |
Previous Message | Jeremy Drake | 2005-09-23 18:07:30 | Re: 64-bit API for large objects |
From | Date | Subject | |
---|---|---|---|
Next Message | Martijn van Oosterhout | 2005-09-23 18:32:46 | Re: Releasing memory during External sorting? |
Previous Message | Chris Browne | 2005-09-23 17:48:32 | Re: VACUUM FULL vs CLUSTER |