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: <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>
 <ebe8b411-006e-7863-3c60-67ddafe1c636@2ndquadrant.com>
 <790BC80E-D8E5-499B-A1E3-8EE0752B53ED@anarazel.de>
 <06523583-b9c5-1424-ef0a-1fc8063e9ed7@2ndquadrant.com>
 <20171206204616.wcect35fuj5gjde2@alap3.anarazel.de>
From: Tomas Vondra <tomas.vondra@2ndquadrant.com>
Message-ID: <67e5af9b-f509-7b9e-f7a1-e01112f6c18d@2ndquadrant.com>
Date: Wed, 6 Dec 2017 22:05:22 +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: <20171206204616.wcect35fuj5gjde2@alap3.anarazel.de>
Content-Type: text/plain; charset=utf-8
Content-Language: en-US
Content-Transfer-Encoding: 7bit
Precedence: bulk


On 12/06/2017 09:46 PM, Andres Freund wrote:
> On 2017-12-06 21:38:42 +0100, Tomas Vondra wrote:
>> It's one thing when the hash table takes longer to lookup something or
> 
> longer aka "forever".
> 

Not necessarily.

The datasets I shared are somewhat extreme in the sense that there are
many contiguous sequences of hash values, but it only takes one such
sequence with at least SH_GROW_MAX_MOVE values to trigger the issue. So
the hash table may still be perfectly fine for most keys, and only
slightly slower for the keys in the sequence.

> 
>> when it consumes a bit more memory. Say, ~2x more than needed, give or
>> take. I'm perfectly fine with that, particularly when it's a worst-case
>> evil data set like this one.
> 
> I think the way to prevent that kind of attack is to add randomization.
> 

By randomization you mean universal hashing [1], or something else?

[1] https://en.wikipedia.org/wiki/Universal_hashing

In any case, randomization should make it much harder (or pretty much
impossible) to construct datasets that are guaranteed to cause failures
of this kind. No problem with that (although if someone hits the issue,
it will be more difficult to reproduce).

It would still be possible to hit it by chance, but that should be very
unlikely (OTOH the current code assumes the same thing about collisions
and sequences, and here we are.)

> 
>> FWIW I've constructed the data sets for two reasons - to convince myself
>> that my understanding of the simplehash code is correct, and to provide
>> a data set triggering the other growth condition in simplehash code. My
>> understanding is that if we stop growing the table after the load factor
>> drops below some threshold (as TL proposed earlier in this thread), it
>> should address both of these cases.
> 
> Yea, I'm not adverse to adding a few stopgaps that break in a less
> annoying manner. WAll I'm saying is that I don't think we need to be
> super concerned about this specific way of breaking things.
> 

OK, understood.


cheers

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