From: Tom Lane <tgl@sss.pgh.pa.us>
To: Thomas Munro <thomas.munro@enterprisedb.com>
cc: Andres Freund <andres@anarazel.de>,
        "Todd A. Cook" <tcook@blackducksoftware.com>,
        Tomas Vondra <tomas.vondra@2ndquadrant.com>,
        PostgreSQL Bugs <pgsql-bugs@postgresql.org>
Subject: Re: BUG #14932: SELECT DISTINCT val FROM table gets stuck in an
 infinite loop
In-reply-to: 
 <CAEepm=3SC9zYLKhvtZbsnwf9vEpi96WCGz1rdGLofuzBau=fqA@mail.gmail.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>
Comments: In-reply-to Thomas Munro <thomas.munro@enterprisedb.com>
	message dated "Tue, 28 Nov 2017 15:20:40 +1300"
MIME-Version: 1.0
Content-Type: text/plain; charset="us-ascii"
Content-ID: <17356.1511841783.1@sss.pgh.pa.us>
Content-Transfer-Encoding: quoted-printable
Date: Mon, 27 Nov 2017 23:03:03 -0500
Message-ID: <17357.1511841783@sss.pgh.pa.us>
Precedence: bulk

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=3D# select hashint8(val), count(*) from reproducer group by 1 o=
rder 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.

(I wonder whether these loops oughtn't contain CHECK_FOR_INTERRUPTS,
btw.)

			regards, tom lane