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 87063D9921 for ; Tue, 27 Sep 2005 09:49:26 -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 29406-09 for ; Tue, 27 Sep 2005 12:49:17 +0000 (GMT) Received: from rproxy.gmail.com (rproxy.gmail.com [64.233.170.201]) by svr1.postgresql.org (Postfix) with ESMTP id 7FBFBD98E4 for ; Tue, 27 Sep 2005 09:49:18 -0300 (ADT) Received: by rproxy.gmail.com with SMTP id 40so77592rnz for ; Tue, 27 Sep 2005 05:49:22 -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=mwx3NMMs/pENNWoASxt7xIMcXOpMTU7l2nBGdcE8nxwTV5tZqER9f8Bk3UnX6jEy01xTz92k5I8tzdqpitjy21GUzsBtZBVeDJG9QjES4Y32EZTOMwaP7Za8+cC+P7HxRuelBoAd985tWSt/xssDH8BZ79PL7VkT3gBm5xdt300= Received: by 10.11.33.25 with SMTP id g25mr10391cwg; Tue, 27 Sep 2005 05:49:22 -0700 (PDT) Received: by 10.11.119.38 with HTTP; Tue, 27 Sep 2005 05:49:22 -0700 (PDT) Message-ID: <36e6829205092705492b0c9fdd@mail.gmail.com> Date: Tue, 27 Sep 2005 08:49:22 -0400 From: "Jonah H. Harris" Reply-To: "Jonah H. Harris" To: Ron Peacetree Subject: Re: [PERFORM] A Better External Sort? Cc: Tom Lane , pgsql-hackers@postgresql.org, pgsql-performance@postgresql.org In-Reply-To: <10783357.1127797759038.JavaMail.root@elwamui-polski.atl.sa.earthlink.net> MIME-Version: 1.0 Content-Type: multipart/alternative; boundary="----=_Part_1923_2109684.1127825362178" References: <10783357.1127797759038.JavaMail.root@elwamui-polski.atl.sa.earthlink.net> X-Virus-Scanned: by amavisd-new at hub.org X-Spam-Status: No, hits=0.381 required=5 tests=[AWL=0.061, HTML_10_20=0.295, HTML_MESSAGE=0.001, RCVD_BY_IP=0.024] X-Spam-Level: X-Archive-Number: 200509/1224 X-Sequence-Number: 73621 ------=_Part_1923_2109684.1127825362178 Content-Type: text/plain; charset=ISO-8859-1 Content-Transfer-Encoding: quoted-printable Content-Disposition: inline Ron, Again, if you feel strongly enough about the theory to argue it, I recommen= d that you spend your time constructively; create an implemenation of it. Citing academics is cool and all, but code speaks louder than theory in thi= s case. As Tom mentioned, this has to be portable. Making assumptions about computing architectures (especially those in the future), is fine for theory, but not practical for something that needs to be maintained in the real-world. Go forth and write thy code. -Jonah On 9/27/05, Ron Peacetree wrote: > > SECOND ATTEMPT AT POST. Web mailer appears to have > eaten first one. I apologize in advance if anyone gets two > versions of this post. > =3Dr > > >From: Tom Lane > >Sent: Sep 26, 2005 9:42 PM > >Subject: Re: [HACKERS] [PERFORM] A Better External Sort? > > > >So far, you've blithely assumed that you know the size of a cache line, > >the sizes of L1 and L2 cache, > > > NO. I used exact values only as examples. Realistic examples drawn > from an extensive survey of past, present, and what I could find out > about future systems; but only examples nonetheless. For instance, > Hennessy and Patterson 3ed points out that 64B cache lines are > optimally performing for caches between 16KB and 256KB. The same > source as well as sources specifically on CPU memory hierarchy > design points out that we are not likely to see L1 caches larger than > 256KB in the forseeable future. > > The important point was the idea of an efficient Key, rather than > Record, sort using a CPU cache friendly data structure with provably > good space and IO characteristics based on a reasonable model of > current and likely future single box computer architecture (although > it would be fairly easy to extend it to include the effects of > networking.) > > No apriori exact or known values are required for the method to work. > > > >and that you are working with sort keys that you can efficiently pack > >into cache lines. > > > Not "pack". "map". n items can not take on more than n values. n > values can be represented in lgn bits. Less efficient mappings can > also work. Either way I demonstrated that we have plenty of space in > a likely and common cache line size. Creating a mapping function > to represent m values in lgm bits is a well known hack, and if we keep > track of minimum and maximum values for fields during insert and > delete operations, we can even create mapping functions fairly easily. > (IIRC, Oracle does keep track of minimum and maximum field > values.) > > > >And that you know the relative access speeds of the caches and > >memory so that you can schedule transfers, > > > Again, no. I created a reasonable model of a computer system that > holds remarkably well over a _very_ wide range of examples. I > don't need the numbers to be exactly right to justify my approach > to this problem or understand why other approaches may have > downsides. I just have to get the relative performance of the > system components and the relative performance gap between them > reasonably correct. The stated model does that very well. > > Please don't take my word for it. Go grab some random box: > laptop, desktop, unix server, etc and try it for yourself. Part of the > reason I published the model was so that others could examine it. > > > >and that the hardware lets you get at that transfer timing. > > > Never said anything about this, and in fact I do not need any such. > > > >And that the number of distinct key values isn't very large. > > > Quite the opposite in fact. I went out of my way to show that the > method still works well even if every Key is distinct. It is _more > efficient_ when the number of distinct keys is small compared to > the number of data items, but it works as well as any other Btree > would when all n of the Keys are distinct. This is just a CPU cache > and more IO friendly Btree, not some magical and unheard of > technique. It's just as general purpose as Btrees usually are. > > I'm simply looking at the current and likely future state of computer > systems architecture and coming up with a slight twist on how to use > already well known and characterized techniques. not trying to start > a revolution. > > > I'm trying very hard NOT to waste anyone's time around here. > Including my own > Ron > > ---------------------------(end of broadcast)--------------------------- > TIP 5: don't forget to increase your free space map settings > -- Respectfully, Jonah H. Harris, Database Internals Architect EnterpriseDB Corporation http://www.enterprisedb.com/ ------=_Part_1923_2109684.1127825362178 Content-Type: text/html; charset=ISO-8859-1 Content-Transfer-Encoding: quoted-printable Content-Disposition: inline Ron,

Again, if you feel strongly enough about the theory to argue it, I recommend that you spend your time constructively; create an implemenation of it.  Citing academics is cool and all, but code speaks louder than theory in this case.  As Tom mentioned, this has to be portable.  Making assumptions about computing architectures (especially those in the future), is fine for theory, but not practical for something that needs to be maintained in the real-world.  Go forth and write thy code.

-Jonah

On 9/27/05, Ron Peacetree <rjpeace@earthlink.net> wrote:
SECOND ATTEMPT AT POST.  Web mailer appears to have
eaten firs= t one.  I apologize in advance if anyone gets two
versions of = this post.
=3Dr

>From: Tom Lane <tgl@sss.pgh.pa.us >
>Sent: Sep 26, 2005 9:42 PM
>Subject: Re: [HACKERS] [P= ERFORM] A Better External Sort?
>
>So far, you've blithely assu= med that you know the size of a cache line,
>the sizes of L1 and L2 c= ache,
>
NO.  I used exact values only as examples.  = ;Realistic examples drawn
from an extensive survey of past, present, and= what I could find out
about future systems; but only examples nonethele= ss.  For instance,
Hennessy and Patterson 3ed points out that 64B cache lines are
optim= ally performing for caches between 16KB and 256KB.  The same
s= ource as well as sources specifically on CPU memory hierarchy
design poi= nts out that we are not likely to see L1 caches larger than
256KB in the forseeable future.

The important point was the idea= of an efficient Key, rather than
Record, sort using a CPU cache friendl= y data structure with provably
good space and IO characteristics based o= n a reasonable model of
current and likely future single box computer architecture (althoughit would be fairly easy to extend it to include the effects of
networki= ng.)

No apriori exact or known values are required for the method to= work.


>and that you are working with sort keys that you can effici= ently pack
>into cache lines.
>
Not "pack". &= nbsp;"map".  n items can not take on more than n values= .  n
values can be represented in lgn bits.  Less ef= ficient mappings can
also work.  Either way I demonstrated that we have plenty of = space in
a likely and common cache line size.  Creating a mapp= ing function
to represent m values in lgm bits is a well known hack, and= if we keep
track of minimum and maximum values for fields during insert= and
delete operations, we can even create mapping functions fairly easily.<= br>(IIRC, Oracle does keep track of minimum and maximum field
values.)

>And that you know the relative access speeds of the caches an= d
>memory so that you can schedule transfers,
>
Again, no.&nb= sp; I created a reasonable model of a computer system that
holds re= markably well over a _very_ wide range of examples.  I
don't n= eed the numbers to be exactly right to justify my approach
to this problem or understand why other approaches may have
downside= s.  I just have to get the relative performance of the
system = components and the relative performance gap between them
reasonably corr= ect.  The stated model does that very well.

Please don't take my word for it.  Go grab some random bo= x:
laptop, desktop, unix server, etc and try it for yourself.  = ;Part of the
reason I published the model was so that others could exami= ne it.


>and that the hardware lets you get at that transfer timing.
>
= Never said anything about this, and in fact I do not need any such.

=
>And that the number of distinct key values isn't very large.
>
Quite the opposite in fact.  I went out of my way to show= that the
method still works well even if every Key is distinct. &n= bsp;It is _more
efficient_ when the number of distinct keys is small com= pared to
the number of data items, but it works as well as any other Btr= ee
would when all n of the Keys are distinct.  This is just a CP= U cache
and more IO friendly Btree, not some magical and unheard of
t= echnique.  It's just as general purpose as Btrees usually are.
I'm simply looking at the current and likely future state of computer
systems architecture and coming up with a slight twist on how to usealready well known and characterized techniques. not trying to start
a = revolution.


I'm trying very hard NOT to waste anyone's time arou= nd here.
Including my own
Ron

---------------------------(end of broad= cast)---------------------------
TIP 5: don't forget to increase your fr= ee space map settings



--=20
Respectfully,

Jonah H. Harris, Database Internals Architect
E= nterpriseDB Corporation
http://= www.enterprisedb.com/
------=_Part_1923_2109684.1127825362178--