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 22:05:22 +0100
Message-ID: <67e5af9b-f509-7b9e-f7a1-e01112f6c18d@2ndquadrant.com> (raw)
In-Reply-To: <20171206204616.wcect35fuj5gjde2@alap3.anarazel.de>
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>
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
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: <67e5af9b-f509-7b9e-f7a1-e01112f6c18d@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