From: Tom Lane <tgl@sss.pgh.pa.us>
To: Mark Lewis <mark.lewis@mir3.com>
Cc: Ron Peacetree <rjpeace@earthlink.net>
Cc: Simon Riggs <simon@2ndquadrant.com>
Cc: pgsql-hackers@postgresql.org
Cc: pgsql-performance@postgresql.org
Subject: Re: [PERFORM] Releasing memory during External sorting?
Date: Fri, 23 Sep 2005 14:15:40 -0400
Message-ID: <5441.1127499340@sss.pgh.pa.us> (raw)
In-Reply-To: <1127497383.23567.218.camel@archimedes>
References: <2559192.1127494115558.JavaMail.root@elwamui-huard.atl.sa.earthlink.net>
<5021.1127495844@sss.pgh.pa.us>
<1127497383.23567.218.camel@archimedes>
Mark Lewis <mark.lewis@mir3.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
Reply instructions:
You may reply publicly to this message via plain-text email
using any one of the following methods:
* Reply to all the recipients using the --to and --cc options:
reply via email
To: pgsql-performance@postgresql.org
Cc: tgl@sss.pgh.pa.us, mark.lewis@mir3.com, rjpeace@earthlink.net, simon@2ndquadrant.com, pgsql-hackers@postgresql.org
Subject: Re: [PERFORM] Releasing memory during External sorting?
In-Reply-To: <5441.1127499340@sss.pgh.pa.us>
* Save the following mbox file, import it into your mail client,
and reply-to-all from there: mbox
This inbox is served by DDX for PostgreSQL; see mirroring instructions
for how to clone and mirror all data and code used for this inbox