From: Andres Freund <andres@anarazel.de>
To: Tomas Vondra <tomas.vondra@2ndquadrant.com>
Cc: Todd A. Cook <tcook@blackducksoftware.com>
Cc: Tom Lane <tgl@sss.pgh.pa.us>
Cc: Thomas Munro <thomas.munro@enterprisedb.com>
Cc: PostgreSQL Bugs <pgsql-bugs@postgresql.org>
Subject: Re: BUG #14932: SELECT DISTINCT val FROM table gets stuck in an infinite loop
Date: Wed, 6 Dec 2017 11:35:45 -0800
Message-ID: <20171206193545.3imvbfwjgrmuho3s@alap3.anarazel.de> (raw)
In-Reply-To: <263b03b1-3e1c-49ca-165a-8ac6751419c4@2ndquadrant.com>
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>
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
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-bugs@postgresql.org
Cc: andres@anarazel.de, tomas.vondra@2ndquadrant.com, tcook@blackducksoftware.com, tgl@sss.pgh.pa.us, thomas.munro@enterprisedb.com
Subject: Re: BUG #14932: SELECT DISTINCT val FROM table gets stuck in an infinite loop
In-Reply-To: <20171206193545.3imvbfwjgrmuho3s@alap3.anarazel.de>
* 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