From: Tom Lane <tgl@sss.pgh.pa.us>
To: Thomas Munro <thomas.munro@enterprisedb.com>
Cc: Andres Freund <andres@anarazel.de>
Cc: Todd A. Cook <tcook@blackducksoftware.com>
Cc: Tomas Vondra <tomas.vondra@2ndquadrant.com>
Cc: PostgreSQL Bugs <pgsql-bugs@postgresql.org>
Subject: Re: BUG #14932: SELECT DISTINCT val FROM table gets stuck in an infinite loop
Date: Mon, 27 Nov 2017 23:03:03 -0500
Message-ID: <17357.1511841783@sss.pgh.pa.us> (raw)
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>
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.
(I wonder whether these loops oughtn't contain CHECK_FOR_INTERRUPTS,
btw.)
regards, tom lane
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: tgl@sss.pgh.pa.us, thomas.munro@enterprisedb.com, andres@anarazel.de, tcook@blackducksoftware.com, tomas.vondra@2ndquadrant.com
Subject: Re: BUG #14932: SELECT DISTINCT val FROM table gets stuck in an infinite loop
In-Reply-To: <17357.1511841783@sss.pgh.pa.us>
* 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