pg.ddx.io  pgsql-hackers@postgresql.org mailing list archive  

help / color / mirror / Atom feed
From: Heikki Linnakangas <hlinnaka@iki.fi>
To: Jeff Davis <pgsql@j-davis.com>
To: Peter Geoghegan <pg@bowt.ie>
Cc: Tomas Vondra <tomas.vondra@2ndquadrant.com>
Cc: Taylor Vesely <tvesely@pivotal.io>
Cc: Adam Lee <ali@pivotal.io>
Cc: Melanie Plageman <mplageman@pivotal.io>
Cc: PostgreSQL Hackers <pgsql-hackers@postgresql.org>
Subject: Re: Memory-Bounded Hash Aggregation
Date: Tue, 4 Feb 2020 18:10:15 +0200
Message-ID: <b2c6d4c1-9298-4dfd-2763-cd080b23a826@iki.fi> (raw)
In-Reply-To: <97c46a59c27f3c38e486ca170fcbc618d97ab049.camel@j-davis.com>
References: <507ac540ec7c20136364b5272acbcd4574aa76ef.camel@j-davis.com>
	<20190703001753.s5e5cme3ucjgeu6c@development>
	<e13b52d4d8f9c10f7b58f39270213b868c99b685.camel@j-davis.com>
	<20190711155520.zqipi23o3yybx7ym@development>
	<9be86fc1adc315f69b8af4b379087ab451008d8a.camel@j-davis.com>
	<20190802064405.GA94036@mars.local>
	<617fea8258ba3df7bc8b21cd7f3afc219f2383d9.camel@j-davis.com>
	<20190802152123.ichmacgx3y3x7dc3@development>
	<CAFaX_4Ls5UGQ2UDYkWhn2xFq=V6BKpUbKSQnWmy27VWhQ2=enA@mail.gmail.com>
	<e52707d4665e32867fb6dd181825ef15f853b8bf.camel@j-davis.com>
	<20191214173225.3kzsbncr6brpxdll@development>
	<d72e494db7b075ef02c3163e6614e698701d2c3e.camel@j-davis.com>
	<775d754c-9a61-5363-6998-f87d15f1b592@iki.fi>
	<e5566f7def33a9e9fdff337cca32d07155d7b635.camel@j-davis.com>
	<CAH2-WznXPuKOee6EMxc7jD4vSQv=yFVVTz6gridGkmzxTSkyNA@mail.gmail.com>
	<6e2b4a4475a690fa515829950aeed935696b0df3.camel@j-davis.com>
	<97c46a59c27f3c38e486ca170fcbc618d97ab049.camel@j-davis.com>

On 03/02/2020 20:29, Jeff Davis wrote:
> 1. Use a minheap for the freelist. The original design used an array
> that had to be sorted between a read (which frees a block) and a write
> (which needs to sort the array to consume the lowest block number). The
> comments said:
> 
>    * sorted.  This is an efficient way to handle it because we expect
> cycles
>    * of releasing many blocks followed by re-using many blocks, due to
>    * the larger read buffer.
> 
> But I didn't find a case where that actually wins over a simple
> minheap. With that in mind, a minheap seems closer to what one might
> expect for that purpose, and more robust when the assumptions don't
> hold up as well. If someone knows of a case where the re-sorting
> behavior is important, please let me know.

A minheap certainly seems more natural for that. I guess re-sorting the 
array would be faster in the extreme case that you free almost all of 
the blocks, and then consume almost all of the blocks, but I don't think 
the usage pattern is ever that extreme. Because if all the data fit in 
memory, we wouldn't be spilling in the first place.

I wonder if a more advanced heap like the pairing heap or fibonacci heap 
would perform better? Probably doesn't matter in practice, so better 
keep it simple...

> Changing to a minheap effectively solves the problem for HashAgg,
> though in theory the memory consumption of the freelist itself could
> become significant (though it's only 0.1% of the free space being
> tracked).

We could fairly easily spill parts of the freelist to disk, too, if 
necessary. But it's probably not worth the trouble.

> 2. Lazily-allocate the read buffer. The write buffer was always lazily-
> allocated, so this patch creates better symmetry. More importantly, it
> means freshly-rewound tapes don't have any buffer allocated, so it
> greatly expands the number of tapes that can be managed efficiently as
> long as only a limited number are active at once.

Makes sense.

> 3. Allow expanding the number of tapes for an existing tape set. This
> is useful for HashAgg, which doesn't know how many tapes will be needed
> in advance.

I'd love to change the LogicalTape API so that you could allocate and 
free tapes more freely. I wrote a patch to do that, as part of replacing 
tuplesort.c's polyphase algorithm with a simpler one (see [1]), but I 
never got around to committing it. Maybe the time is ripe to do that now?

[1] 
https://www.postgresql.org/message-id/420a0ec7-602c-d406-1e75-1ef7ddc58d83@iki.fi

- Heikki





view thread (81+ messages)  latest in thread

Message-ID: <b2c6d4c1-9298-4dfd-2763-cd080b23a826@iki.fi>
Permalink:  ../b2c6d4c1-9298-4dfd-2763-cd080b23a826@iki.fi/
Also on:    postgresql.org/message-id/b2c6d4c1-9298-4dfd-2763-cd080b23a826@iki.fi

 · 

reply
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-hackers@postgresql.org
  Cc: hlinnaka@iki.fi, pgsql@j-davis.com, pg@bowt.ie, tomas.vondra@2ndquadrant.com, tvesely@pivotal.io, ali@pivotal.io, mplageman@pivotal.io
  Subject: Re: Memory-Bounded Hash Aggregation
  In-Reply-To: <b2c6d4c1-9298-4dfd-2763-cd080b23a826@iki.fi>

* 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