Horton

Re: Memory usage during sorting

Tom Lane <tgl@sss.pgh.pa.us>

View thread
From: Tom Lane <tgl@sss.pgh.pa.us>
To: Jeff Davis <pgsql@j-davis.com>
Cc: Jeff Janes <jeff.janes@gmail.com>, Robert Haas <robertmhaas@gmail.com>, Hitoshi Harada <umi.tanuki@gmail.com>, pgsql-hackers <pgsql-hackers@postgresql.org>
Date: 2012-04-13T13:51:27Z
Lists: pgsql-hackers

Commits

Same data as JSON: GET /api/v1/messages/:b64id/commits the thread's linked commits as JSON, with link sources. API reference →

  1. Improve performance of our private version of qsort. Per recent testing,

  2. Further performance improvements in sorting: reduce number of comparisons

Jeff Davis <pgsql@j-davis.com> writes:
> On Sun, 2012-03-18 at 11:25 -0400, Tom Lane wrote:
>> Yeah, that was me, and it came out of actual user complaints ten or more
>> years back.  (It's actually not 2X growth but more like 4X growth
>> according to the comments in logtape.c, though I no longer remember the
>> exact reasons why.)  We knew when we put in the logtape logic that we
>> were trading off speed for space, and we accepted that.

> I skimmed through TAOCP, and I didn't find the 4X number you are
> referring to, and I can't think what would cause that, either. The exact
> wording in the comment in logtape.c is "4X the actual data volume", so
> maybe that's just referring to per-tuple overhead?

My recollection is that that was an empirical measurement using the
previous generation of code.  It's got nothing to do with per-tuple
overhead IIRC, but with the fact that the same tuple can be sitting on
multiple "tapes" during a polyphase merge, because some of the tapes can
be lying fallow waiting for future use --- but data on them is still
taking up space, if you do nothing to recycle it.  The argument in the
comment shows why 2X is the minimum space growth for a plain merge
algorithm, but that's only a minimum.

			regards, tom lane