From: Tomas Vondra <tomas.vondra@2ndquadrant.com>
To: Andres Freund <andres@anarazel.de>
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 20:57:44 +0100
Message-ID: <ebe8b411-006e-7863-3c60-67ddafe1c636@2ndquadrant.com> (raw)
In-Reply-To: <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>
<20171206193545.3imvbfwjgrmuho3s@alap3.anarazel.de>
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
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: tomas.vondra@2ndquadrant.com, andres@anarazel.de, 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: <ebe8b411-006e-7863-3c60-67ddafe1c636@2ndquadrant.com>
* 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