Subject: Re: Memory-Bounded Hash Aggregation
To: Jeff Davis <pgsql@j-davis.com>, Peter Geoghegan <pg@bowt.ie>
Cc: Tomas Vondra <tomas.vondra@2ndquadrant.com>,
 Taylor Vesely <tvesely@pivotal.io>, Adam Lee <ali@pivotal.io>,
 Melanie Plageman <mplageman@pivotal.io>,
 PostgreSQL Hackers <pgsql-hackers@postgresql.org>
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>
From: Heikki Linnakangas <hlinnaka@iki.fi>
Message-ID: <b2c6d4c1-9298-4dfd-2763-cd080b23a826@iki.fi>
Date: Tue, 4 Feb 2020 18:10:15 +0200
User-Agent: Mozilla/5.0 (X11; Linux x86_64; rv:68.0) Gecko/20100101
 Thunderbird/68.4.1
MIME-Version: 1.0
In-Reply-To: <97c46a59c27f3c38e486ca170fcbc618d97ab049.camel@j-davis.com>
Content-Type: text/plain; charset=utf-8; format=flowed
Content-Language: en-US
Content-Transfer-Encoding: 7bit
Precedence: bulk

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