Subject: Re: BUG #14932: SELECT DISTINCT val FROM table gets stuck in an
 infinite loop
To: Andres Freund <andres@anarazel.de>, Tom Lane <tgl@sss.pgh.pa.us>
Cc: "Todd A. Cook" <tcook@blackducksoftware.com>,
 Thomas Munro <thomas.munro@enterprisedb.com>,
 PostgreSQL Bugs <pgsql-bugs@postgresql.org>
References: <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>
 <c15378b3-d4aa-a5c0-5538-dd52904dcbc6@2ndquadrant.com>
 <1773c302-2fb1-749f-8ccc-62b23617c5ac@blackducksoftware.com>
 <25629.1512580464@sss.pgh.pa.us>
 <20171206171923.dg7phzfh7nb4lou3@alap3.anarazel.de>
From: Tomas Vondra <tomas.vondra@2ndquadrant.com>
Message-ID: <7de4b2d6-b119-7d15-04d8-4c0fcb29cbc3@2ndquadrant.com>
Date: Sun, 10 Dec 2017 23:09:42 +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: <20171206171923.dg7phzfh7nb4lou3@alap3.anarazel.de>
Content-Type: multipart/mixed;
 boundary="------------AA55963C4B243112020E55DD"
Content-Language: en-US
Precedence: bulk

This is a multi-part message in MIME format.
--------------AA55963C4B243112020E55DD
Content-Type: text/plain; charset=utf-8
Content-Transfer-Encoding: 7bit


On 12/06/2017 06:19 PM, Andres Freund wrote:
> On 2017-12-06 12:14:24 -0500, Tom Lane wrote:
>> Checking out hashint8() on random data shows no such obvious fault.
>> You've apparently got a data set that exposes a weakness in hashint8,
>> but it's not very clear what that is.
> 
> It's intentionally designed to cause problems afaict:
> 
> http://archives.postgresql.org/message-id/861b9f1f-cdc0-bc49-2595-80bc39c37dc3%40blackducksoftware.com
> 
> 
>> In any case, the hashtable code needs to not fall over in the
>> presence of a lot of collisions, regardless of the exact reason
>> for there being a lot.
> 
> Yes, we need to be more resilient about it. Working on a patch.
> 

I've been playing with this a bit today (sorry for trespassing on your
turf a bit, but curiosity killed the cat), particularly with the tree
basic ideas mentioned in this thread. Let me share some numbers.

1) randomized hashing, i.e. using the extended hash functions and a
random seed

2) universal hashing [1], i.e. passing the hash through ((a*h+b) mod p)
formula, where h is "our" hash, and (a,b) are random and p is a prime.
This can't possibly fix the collisions reported by Todd, because the
result will remain the same. But it should fix "my" chains of values by
spreading them a bit (and the a,b,p values are generated on each grow,
so in the unlikely case where we get a chain, it should disappear after
a growth)

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

3) disabling growth of the hash table when the fillfactor would drop too
much (e.g. below 0.2)

Very rough patches for these three approaches are attached.


Now, some very rough numbers comparing the impact of those approaches
(and their combinations). The following two tables present timings for
for a couple of datasets - five cases without any collisions (allowing
us to quantify impact on regular datasets), the two datasets generated
by me (one without collisions, one with collisions), and the two issues
reported by Todd.

RH - randomized hashing (seed + extended)
UH - universal hashing
ST - stop growing

             master     RH     UH     ST    RH     UH    ST
    -------------------------------------------------------
    Ok/1        542    540    552    537    0%     2%   -1%
    Ok/2        232    221    242    237   -5%     4%    2%
    Ok/3        161    167    180    161    4%    12%    0%
    Ok/4        276    270    285    274   -2%     3%   -1%
    Ok/5        174    179    193    174    3%    11%    0%
    Tomas/1     543    555    551    533    2%     1%   -2%
    Tomas/2     OOM   2322   3251      -
    Todd/1      OOM    OOM     63     63
    Todd/2      OOM    OOM    OOM     72


This is mostly as expected, although I'm surprised that the universal
hashing seems to fix Todd's first reproducer. The "stop growing"
approach technically fixes "my" dataset, but it takes so much time I
haven't timed it.

In terms of slowdown (compared to master), I'd say RH and ST are mostly
neutral. Universal hashing has significant impact in some cases, but I
suppose that might be fixed by using a slightly different scheme
(instead of using simple modulo arithmetic).

Now, let's see on combinations of the approaches (broken into two
tables, so that it doesn't get mangled by mail clients):

             master  RH+UH  RH+ST  UH+ST  RH+UH+ST
    Ok/1        542    553    545    549       558
    Ok/2        232    241    234    241       250
    Ok/3        161    180    170    180       187
    Ok/4        276    274    270    285       290
    Ok/5        174    187    182    193       198
    Tomas/1     543    571    561    554       570
    Tomas/2       -   2380   2340   3130      2380
    Todd/1        -     61     65     63        64
    Todd/2        -      -     90     91        93

              RH+UH   RH+ST  UH+ST  RH+UH+ST
    Ok/1         2%      1%     1%        3%
    Ok/2         4%      1%     4%        8%
    Ok/3        12%      6%    12%       16%
    Ok/4        -1%     -2%     3%        5%
    Ok/5         7%      5%    11%       14%
    Tomas/1      5%      3%     2%        5%

It seems only the "stop growth" has to be part of the solution, as it's
included in any combination fixing all cases shared in this thread. I'd
say (randomized hashing + stop growing) seems like the best option.

FWIW I do agree the data sets shared in this thread are pretty extreme
and it doesn't make much sense to slow the regular cases. I'll be
perfectly happy if we stop the OOM, making those cases fast is a bonus.

regards

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

--------------AA55963C4B243112020E55DD
Content-Type: text/x-patch;
 name="0001-use-random-seed-for-hash-table.patch"
Content-Transfer-Encoding: 7bit
Content-Disposition: attachment;
 filename="0001-use-random-seed-for-hash-table.patch"