Date: Wed, 6 Dec 2017 11:35:45 -0800
From: Andres Freund <andres@anarazel.de>
To: Tomas Vondra <tomas.vondra@2ndquadrant.com>
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>
Subject: Re: BUG #14932: SELECT DISTINCT val FROM table gets stuck in an
 infinite loop
Message-ID: <20171206193545.3imvbfwjgrmuho3s@alap3.anarazel.de>
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>
MIME-Version: 1.0
Content-Type: text/plain; charset=us-ascii
Content-Disposition: inline
In-Reply-To: <263b03b1-3e1c-49ca-165a-8ac6751419c4@2ndquadrant.com>
Precedence: bulk

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.

Greetings,

Andres Freund