From: Tomas Vondra <tomas.vondra@2ndquadrant.com>
To: Todd A. Cook <tcook@blackducksoftware.com>
To: Tom Lane <tgl@sss.pgh.pa.us>
To: Thomas Munro <thomas.munro@enterprisedb.com>
Cc: Andres Freund <andres@anarazel.de>
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 14:33:36 +0100
Message-ID: <c15378b3-d4aa-a5c0-5538-dd52904dcbc6@2ndquadrant.com> (raw)
In-Reply-To: <219b37b2-d740-d04a-203a-49ae422028f7@blackducksoftware.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>
<219b37b2-d740-d04a-203a-49ae422028f7@blackducksoftware.com>
On 12/05/2017 11:33 PM, Todd A. Cook wrote:
> On 12/05/17 17:01, Tomas Vondra wrote:
>>
>>
>> On 12/05/2017 10:23 PM, Todd A. Cook wrote:
>>> On 11/27/17 23:03, Tom Lane wrote:
>>>> Thomas Munro <thomas.munro@enterprisedb.com> writes:
>>>>> When SH_INSERT tries to insert that final extra value, insertdist
>>>>> keeps exceeding SH_GROW_MAX_DIB (25) no matter how many times we
>>>>> double the size (at least until my computer gives up, somewhere around
>>>>> 11 doublings and 75GB of virtual memory). If you set SH_GROW_MAX_DIB
>>>>> to 26 then it succeeds, but I guess some other attack could be crafted
>>>>> for that. What is the theory behind this parameter?
>>>>
>>>> You beat me to it --- after looking at simplehash.h I'd guessed that
>>>> either the SH_GROW_MAX_DIB or SH_GROW_MAX_MOVE code path was causing
>>>> an infinite loop, but I'd not gotten to determining which one yet.
>>>>
>>>> I'd ask what's the theory behind SH_GROW_MAX_MOVE, as well. Neither
>>>> of them are obviously loop-proof.
>>>>
>>>> Note that the sample data has a lot of collisions:
>>>>
>>>> regression=# select hashint8(val), count(*) from reproducer group by 1
>>>> order by 2 desc;
>>>> hashint8 | count
>>>> -------------+-------
>>>> 441526644 | 2337
>>>> -1117776826 | 1221
>>>> -1202007016 | 935
>>>> -2068831050 | 620
>>>> 1156644653 | 538
>>>> 553783815 | 510
>>>> 259780770 | 444
>>>> 371047036 | 394
>>>> 915722575 | 359
>>>> ... etc etc ...
>>>>
>>>> It's evidently more complicated than just that the code fails with
>>>> more than SH_GROW_MAX_DIB duplicate hashcodes, but I suspect not
>>>> by a lot. There needs to be a safety valve that prevents letting
>>>> the hash fill factor approach zero, which is what's happening in
>>>> this test case.
>>>
>>> FWIW, I can also reproduce the infinite loop with 167834 unique values.
>>>
>>
>> Unique values or unique *hash* values?
>
> Unique values.
>
>
>> Can you share the data, so that whoever fixes the bug can verify it also
>> fixes your example?
>
> Sure. It's attached.
>
Seems the dataset has pretty much the same issue as the one reported
before, that is
select hashint8(val), count(distinct val), count(*) from temp_f_03 group
by 1 order by 2 desc;
hashint8 | count | count
-------------+-------+-------
-1971396144 | 45 | 45
2035896403 | 42 | 42
-1633843397 | 30 | 30
1425704662 | 29 | 29
-455482779 | 22 | 22
-300163565 | 17 | 17
-1803963420 | 17 | 17
-537082846 | 14 | 14
603707034 | 13 | 13
-176369887 | 12 | 12
1274957136 | 11 | 11
1465522632 | 11 | 11
-1589862230 | 10 | 10
-1145403239 | 10 | 10
i.e. there are many hash collisions (more than in the other data set).
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, tcook@blackducksoftware.com, tgl@sss.pgh.pa.us, thomas.munro@enterprisedb.com, andres@anarazel.de
Subject: Re: BUG #14932: SELECT DISTINCT val FROM table gets stuck in an infinite loop
In-Reply-To: <c15378b3-d4aa-a5c0-5538-dd52904dcbc6@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