Subject: Re: BUG #14932: SELECT DISTINCT val FROM table gets stuck in an
 infinite loop
To: Andres Freund <andres@anarazel.de>
Cc: "Todd A. Cook" <tcook@blackducksoftware.com>, Tom Lane
 <tgl@sss.pgh.pa.us>, Thomas Munro <thomas.munro@enterprisedb.com>,
 PostgreSQL Bugs <pgsql-bugs@postgresql.org>
References: <20171127185700.1470.20362@wrigleys.postgresql.org>
 <fd924fd9-8f27-d945-04a9-57b503896107@2ndquadrant.com>
 <7a22f496-92b5-d199-984e-183965918304@blackducksoftware.com>
 <20171127221041.mezzysc4zcfsqkyc@alap3.anarazel.de>
 <CAEepm=3SC9zYLKhvtZbsnwf9vEpi96WCGz1rdGLofuzBau=fqA@mail.gmail.com>
 <17357.1511841783@sss.pgh.pa.us>
 <9cd29b81-7ba1-91a2-f491-9014f4ac87e6@blackducksoftware.com>
 <2a76784c-06cb-46ec-35be-9895d144b839@2ndquadrant.com>
 <263b03b1-3e1c-49ca-165a-8ac6751419c4@2ndquadrant.com>
 <20171206193545.3imvbfwjgrmuho3s@alap3.anarazel.de>
 <ebe8b411-006e-7863-3c60-67ddafe1c636@2ndquadrant.com>
 <790BC80E-D8E5-499B-A1E3-8EE0752B53ED@anarazel.de>
From: Tomas Vondra <tomas.vondra@2ndquadrant.com>
Message-ID: <06523583-b9c5-1424-ef0a-1fc8063e9ed7@2ndquadrant.com>
Date: Wed, 6 Dec 2017 21:38:42 +0100
User-Agent: Mozilla/5.0 (X11; Linux x86_64; rv:52.0) Gecko/20100101
 Thunderbird/52.3.0
MIME-Version: 1.0
In-Reply-To: <790BC80E-D8E5-499B-A1E3-8EE0752B53ED@anarazel.de>
Content-Type: text/plain; charset=utf-8
Content-Language: en-US
Content-Transfer-Encoding: 7bit
Precedence: bulk


On 12/06/2017 09:00 PM, Andres Freund wrote:
> 
> 
> On December 6, 2017 11:57:44 AM PST, Tomas Vondra <tomas.vondra@2ndquadrant.com> wrote:
>>
>>
>> On 12/06/2017 08:35 PM, Andres Freund wrote:
>>> On 2017-12-06 20:32:24 +0100, Tomas Vondra wrote:
>>>> On 12/05/2017 11:01 PM, Tomas Vondra wrote:
>>>>>
>>>>> Based on the initial discussion, the problem here is twofold.
>>>>>
>>>>> Firstly, the code assumes that if it gets certain number of bucket
>>>>> collisions (essentially, the initial bucket and certain number of
>>>>> neighboring buckets already being full), making the table larger is
>>>>> guaranteed to reduce the number of collisions.
>>>>>
>>>>> Which is obviously untrue for duplicate hash values, but it may
>> also
>>>>> happen for distinct hash values that form a chain (think a sequence
>> of
>>>>> hash values 1,2,3,4,5,6,7,...,K - that is never gonna get fixed).
>>>
>>>> I've managed to construct (by sheer brute force) an example that
>> breaks
>>>> simplehash in this way. It triggers the growth by having a sequence
>> of
>>>> distinct but consecutive hash values, e.g. 1, 2, 3, 4, ..., 1000,
>> and
>>>> then trying to insert a value with duplicate hash (say, 4).
>>>
>>> I fail to be excited by this. That's possible for any sort of
>> hashtable
>>> in some way. You might hit issues due to resizing or due to lookup
>>> performance, but you'll hit problem. That's a fairly fundamental
>> issue
>>> of pure hashtables.
>>>
>>
>> Eh? I think you misunderstood the issue this triggers. I'm perfectly
>> fine with poor lookup performance - that's expected and reasonable. But
>> it actually triggers the same behavior as the already presented
>> example,
>> i.e. the hash table grows indefinitely (so eventually gets OOM).
>>
>> I really doubt allocating 3GB of memory (which is when my laptop gives
>> up and kills the query) to do distinct on 50MB table is a sane
>> behavior.
>> Even if the table is constructed in so intentionally evil way.
> 
> No, I got that. I just don't think time and memory are that different.
>
It's one thing when the hash table takes longer to lookup something or
when it consumes a bit more memory. Say, ~2x more than needed, give or
take. I'm perfectly fine with that, particularly when it's a worst-case
evil data set like this one.

But it's a very different situation when it consumes tens of GBs of
memory (essentially building the largest possible hash table, despite
the load factor dropping to 0), because the code grows the hash table
assuming it will magically resolve the collisions. And even if the
machine has enough RAM, it's guaranteed to fail we'll try growing the
table beyond that limit.

I don't quite understand why should that be OK? It doesn't seem very
sane to me.

FWIW I've constructed the data sets for two reasons - to convince myself
that my understanding of the simplehash code is correct, and to provide
a data set triggering the other growth condition in simplehash code. My
understanding is that if we stop growing the table after the load factor
drops below some threshold (as TL proposed earlier in this thread), it
should address both of these cases.

cheers

-- 
Tomas Vondra                  http://www.2ndQuadrant.com
PostgreSQL Development, 24x7 Support, Remote DBA, Training & Services