X-Original-To: pgsql-hackers-postgresql.org@localhost.postgresql.org Received: from localhost (av.hub.org [200.46.204.144]) by svr1.postgresql.org (Postfix) with ESMTP id 19532D93CA for ; Sat, 24 Sep 2005 02:24:07 -0300 (ADT) Received: from svr1.postgresql.org ([200.46.204.71]) by localhost (av.hub.org [200.46.204.144]) (amavisd-new, port 10024) with ESMTP id 09150-08 for ; Sat, 24 Sep 2005 05:24:02 +0000 (GMT) Received: from zproxy.gmail.com (zproxy.gmail.com [64.233.162.200]) by svr1.postgresql.org (Postfix) with ESMTP id 621B5D7AB6 for ; Sat, 24 Sep 2005 02:24:01 -0300 (ADT) Received: by zproxy.gmail.com with SMTP id 40so786494nzk for ; Fri, 23 Sep 2005 22:24:01 -0700 (PDT) DomainKey-Signature: a=rsa-sha1; q=dns; c=nofws; s=beta; d=gmail.com; h=received:message-id:date:from:reply-to:to:subject:cc:in-reply-to:mime-version:content-type:references; b=LRH4GAGibSL9YlU0HlnEV7O44dISZYY2zeNL5hFEz3Bm908AAUOKGBivRt24310jZMfzDQtGVJJtvwH7GC6EajYVqejzqnoN9PMRgRYJn2nnN09j6Fg8pEmJ3j3lEgcHnYy8d0d/fCBlDUYAEiJLsvSR1QKXo+UimUj+lIrUzYg= Received: by 10.36.96.16 with SMTP id t16mr2516435nzb; Fri, 23 Sep 2005 22:24:01 -0700 (PDT) Received: by 10.37.22.65 with HTTP; Fri, 23 Sep 2005 22:24:01 -0700 (PDT) Message-ID: Date: Sat, 24 Sep 2005 08:24:01 +0300 From: Meir Maor Reply-To: Meir Maor To: Simon Riggs Subject: Re: Releasing memory during External sorting? Cc: pgsql-hackers@postgresql.org, pgsql-performance@postgresql.org In-Reply-To: <1127468233.4145.178.camel@localhost.localdomain> MIME-Version: 1.0 Content-Type: multipart/alternative; boundary="----=_Part_9878_20134342.1127539441198" References: <1127468233.4145.178.camel@localhost.localdomain> X-Virus-Scanned: by amavisd-new at hub.org X-Spam-Status: No, hits=0.172 required=5 tests=[AWL=-0.148, HTML_10_20=0.295, HTML_MESSAGE=0.001, RCVD_BY_IP=0.024] X-Spam-Level: X-Archive-Number: 200509/1050 X-Sequence-Number: 73447 ------=_Part_9878_20134342.1127539441198 Content-Type: text/plain; charset=ISO-8859-1 Content-Transfer-Encoding: quoted-printable Content-Disposition: inline Calculating Optimal memory for disk based sort is based only on minimizing IO. A previous post stated we can merge as many subfiles as we want in a single pass, this is not accurate, as we want to eliminate disk seeks also in the merge phase, also the merging should be done by reading blocks of data from each subfile= , if we have data of size N and M memory, then we will have K=3DN/M subfiles = to merge after sorting each. in the merge operation if we want to merge all blocks in one pass we will read M/K data from each subfile into memory and begin merging, we will read another M/K block when the buffer from a subfile is empty, we would like disk seek time to be irrelavant when comparing to sequential IO time. We notice that we are performing IO in blocks of N/K^2 which is M/(N/M)^2 let us assume that sequeential IO is done at 100MB/s and that a random seek requires ~15ms. and we want seek time to be irrelavnt in one order of magnitute we get, that in the time of one random seek we can read 1.5MB of data and would get optimal performance if we perform IO in blocks of 15MB. and since in the merge algorithm showed above we perform IO in blocks of M/= K we would like M>K*15MB which results in a very large memory requirement. M^2>N*15MB M>sqrt(N*15MB) for example for sorting 10GB of data, we would like M>380MB for optimal performance. alternativly if we can choose a diffrent algorithm in which we merge only a constant number of sunfiles to gether at a time but then we will require multiple passes to merge the entire file. we will require log(K) passes over the entire data and thi= s approach obviously improves with increase of memory. The first aproach requires 2 passes of the entire data and K^2+K random seeks, the second aproach(when merging l blocks at a time) requires: log(l,K) passes over the data and K*l+K random seeks. On 9/23/05, Simon Riggs wrote: > > I have concerns about whether we are overallocating memory for use in > external sorts. (All code relating to this is in tuplesort.c) > > When we begin a sort we allocate (work_mem | maintenance_work_mem) and > attempt to do the sort in memory. If the sort set is too big to fit in > memory we then write to disk and begin an external sort. The same memory > allocation is used for both types of sort, AFAICS. > > The external sort algorithm benefits from some memory but not much. > Knuth says that the amount of memory required is very low, with a value > typically less than 1 kB. I/O overheads mean that there is benefit from > having longer sequential writes, so the optimum is much larger than > that. I've not seen any data that indicates that a setting higher than > 16 MB adds any value at all to a large external sort. I have some > indications from private tests that very high memory settings may > actually hinder performance of the sorts, though I cannot explain that > and wonder whether it is the performance tests themselves that have > issues. > > Does anyone have any clear data that shows the value of large settings > of work_mem when the data to be sorted is much larger than memory? (I am > well aware of the value of setting work_mem higher for smaller sorts, so > any performance data needs to reflect only very large sorts). > > If not, I would propose that when we move from qsort to tapesort mode we > free the larger work_mem setting (if one exists) and allocate only a > lower, though still optimal setting for the tapesort. That way the > memory can be freed for use by other users or the OS while the tapesort > proceeds (which is usually quite a while...). > > Feedback, please. > > Best Regards, Simon Riggs > > > ---------------------------(end of broadcast)--------------------------- > TIP 5: don't forget to increase your free space map settings > ------=_Part_9878_20134342.1127539441198 Content-Type: text/html; charset=ISO-8859-1 Content-Transfer-Encoding: quoted-printable Content-Disposition: inline Calculating Optimal memory for disk based sort is based only on minimizing = IO.
A previous post stated we can merge as many subfiles as we want in a single= pass,
this is not accurate, as we want to eliminate disk seeks also in the merge = phase,
also the merging should be done by reading blocks of data from each subfile= ,
if we have data of size N and M memory, then we will have K=3DN/M subfiles = to merge
after sorting each.
in the merge operation if we want to merge all blocks in one pass we will r= ead
M/K data from each subfile into memory and begin merging, we will read anot= her M/K block
when the buffer from a subfile is empty,
we would like disk seek time to be irrelavant when comparing to sequential = IO time.
We notice that we are performing IO in blocks of N/K^2 which is M/(N/M)^2 <= br> let us assume that sequeential IO is done at 100MB/s and that
a random seek requires ~15ms. and we want seek time to be irrelavnt in one = order of
magnitute we get, that in the time of one random seek we can read 1.5MB of = data
and would get optimal performance if we perform IO in blocks of 15MB.
and since in the merge algorithm showed above we perform IO in blocks of M/= K
we would like M>K*15MB which results in a very large memory requirement.=
M^2>N*15MB
M>sqrt(N*15MB)
for example for sorting 10GB of data, we would like M>380MB
for optimal performance.

alternativly if we can choose a diffrent algorithm in which we merge only a= constant
number of sunfiles to gether at a time but then we will require multiple pa= sses to merge
the entire file. we will require log(K) passes over the entire data and thi= s approach obviously
improves with increase of memory.

The first aproach requires 2 passes of the entire data and K^2+K random see= ks,
the second aproach(when merging l blocks at a time) requires: log(l,K) pass= es over the data
and K*l+K random seeks.


On 9/23/05, Simon Riggs <simon@2ndq= uadrant.com> wrote:
I have concerns about whether we are overallocating memory for use in
ex= ternal sorts. (All code relating to this is in tuplesort.c)

When we = begin a sort we allocate (work_mem | maintenance_work_mem) and
attempt t= o do the sort in memory. If the sort set is too big to fit in
memory we then write to disk and begin an external sort. The same memor= y
allocation is used for both types of sort, AFAICS.

The external= sort algorithm benefits from some memory but not much.
Knuth says that = the amount of memory required is very low, with a value
typically less than 1 kB. I/O overheads mean that there is benefit from=
having longer sequential writes, so the optimum is much larger than
= that. I've not seen any data that indicates that a setting higher than
16 MB adds any value at all to a large external sort. I have some
indica= tions from private tests that very high memory settings may
actually hin= der performance of the sorts, though I cannot explain that
and wonder wh= ether it is the performance tests themselves that have
issues.

Does anyone have any clear data that shows the value of = large settings
of work_mem when the data to be sorted is much larger tha= n memory? (I am
well aware of the value of setting work_mem higher for s= maller sorts, so
any performance data needs to reflect only very large sorts).

If= not, I would propose that when we move from qsort to tapesort mode we
f= ree the larger work_mem setting (if one exists) and allocate only a
lower, though still optimal setting for the tapesort. That way the
memor= y can be freed for use by other users or the OS while the tapesort
proce= eds (which is usually quite a while...).

Feedback, please.

Best Regards, Simon Riggs


---------------------------(end of bro= adcast)---------------------------
TIP 5: don't forget to increase your = free space map settings

------=_Part_9878_20134342.1127539441198--