Re: [HACKERS] Poor memory context performance in large hash joins

On 2017-02-23 17:28:26 -0500, Tom Lane wrote:
> Jeff Janes <jeff.janes@gmail.com> writes:
> > The number of new chunks can be almost as as large as the number of old
> > chunks, especially if there is a very popular value.  The problem is that
> > every time an old chunk is freed, the code in aset.c around line 968 has to
> > walk over all the newly allocated chunks in the linked list before it can
> > find the old one being freed.  This is an N^2 operation, and I think it has
> > horrible CPU cache hit rates as well.
> 
> Maybe it's time to convert that to a doubly-linked list.

Yes, I do think so. Given that we only have that for full blocks, not
for small chunks, the cost seems neglegible.

That would also, partially, address the performance issue
http://archives.postgresql.org/message-id/d15dff83-0b37-28ed-0809-95a5cc7292ad%402ndquadrant.com
addresses, in a more realistically backpatchable manner.

Jeff, do you have a handy demonstrator?


> Although if the
> hash code is producing a whole lot of requests that are only a bit bigger
> than the separate-block threshold, I'd say It's Doing It Wrong.  It should
> learn to aggregate them into larger requests.

That's probably right, but we can't really address that in the
back-branches.  And to me this sounds like something we should address
in the branches, not just in master.  Even if we'd also fix the
hash-aggregation logic, I think such an O(n^2) behaviour in the
allocator is a bad idea in general, and we should fix it anyway.

Regards,

Andres