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>
From: Tomas Vondra <tomas.vondra@2ndquadrant.com>
Message-ID: <ebe8b411-006e-7863-3c60-67ddafe1c636@2ndquadrant.com>
Date: Wed, 6 Dec 2017 20:57:44 +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: <20171206193545.3imvbfwjgrmuho3s@alap3.anarazel.de>
Content-Type: text/plain; charset=utf-8
Content-Language: en-US
Content-Transfer-Encoding: 7bit
Precedence: bulk


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.

regards

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