From: Tomas Vondra <tomas.vondra@2ndquadrant.com>
To: Tom Lane <tgl@sss.pgh.pa.us>
To: Andres Freund <andres@anarazel.de>
Cc: Todd A. Cook <tcook@blackducksoftware.com>
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: Thu, 7 Dec 2017 00:45:34 +0100
Message-ID: <0e91ba4e-5afc-220e-b1f7-56a838aee845@2ndquadrant.com> (raw)
In-Reply-To: <16912.1512600919@sss.pgh.pa.us>
References: <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>
<67e5af9b-f509-7b9e-f7a1-e01112f6c18d@2ndquadrant.com>
<20171206211225.zcp2crfr3bssn3xr@alap3.anarazel.de>
<21d507d9-9024-33a8-37c8-b472b3dce7df@blackducksoftware.com>
<20171206214003.lvz3q5coaewxr7vp@alap3.anarazel.de>
<16912.1512600919@sss.pgh.pa.us>
On 12/06/2017 11:55 PM, Tom Lane wrote:
> Andres Freund <andres@anarazel.de> writes:
>> On 2017-12-06 16:38:18 -0500, Todd A. Cook wrote:
>>> I found this problem when I dropped 10.1 into a test environment to see
>>> what would happen. There was no deliberate attempt to break anything.
>
>> Read Thomas' message at: http://archives.postgresql.org/message-id/263b03b1-3e1c-49ca-165a-8ac6751419c4%402ndquadrant.com
>
> I'm confused by Tomas' claim that
>
>>> (essentially hashint8 only ever produces 60% of
>>> values from [0,1000000], which likely increases collision rate).
>
> This is directly contradicted by the simple experiments I've done, eg
>
> regression=# select count(distinct hashint8(v)) from generate_series(0,1000000::int8) v;
> count
> --------
> 999879
> (1 row)
>
> regression=# select count(distinct hashint8(v) & (1024*1024-1)) from generate_series(0,1000000::int8) v;
> count
> --------
> 644157
> (1 row)
>
> regression=# select count(distinct hashint8(v) & (1024*1024-1)) from generate_series(0,10000000::int8) v;
> count
> ---------
> 1048514
> (1 row)
>
> It's certainly not perfect, but I'm not observing any major failure to
> span the output space.
>
That is not the claim I was making, though. When generating data sets
I've been considering only values where hashint8(v) is between 0 and
1000000 *without* the masking. Otherwise growing the hash table would
break the "chain" of values in the hash table, which would resolve the
issue with SH_GROW_MAX_MOVE.
So you'd have to do something like this:
select count(distinct hashint8(v))
from generate_series(0,1000000::int8) v
where hashint8(v) between 0 and 1024*1024;
but to get some numbers you'd have to also increase the value passed to
generate_series (because it'll filter most of the values).
Which is why I generated the data by an ugly C program, similar to the
attached one. It keeps a small bitmap for generated hashes in the [0,1M]
range, and prints the number of bits set after every 1e9 values processed.
What I do see is this:
i=1000000000 nset=217666
i=2000000000 nset=389526
i=3000000000 nset=525135
i=4000000000 nset=632305
i=5000000000 nset=659574
i=6000000000 nset=659574
i=7000000000 nset=659574
i=8000000000 nset=659574
i=9000000000 nset=659574
...
So somewhere between 4e9 and 5e9 we generate 659574 hashes in the range,
and then never increase it further.
I don't know if this an issue in practice, but it seems that for large
hash tables (on bigint), growing the hash table may not be that great
improvement because we're not really doubling the number of slots we can
hit directly. We'll probably find an empty slot nearby, though.
It was just an observation - I only noticed that because I tried to
construct the adversarial data set on bigint, and couldn't make it work
no matter what.
regards
--
Tomas Vondra http://www.2ndQuadrant.com
PostgreSQL Development, 24x7 Support, Remote DBA, Training & Services
Attachments:duplicities-bigint.c (text/x-csrc, 1.7K) download
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <limits.h>
#include <sys/time.h>
#define rot(x,k) (((x)<<(k)) | ((x)>>(32-(k))))
#define mix(a,b,c) \
{ \
a -= c; a ^= rot(c, 4); c += b; \
b -= a; b ^= rot(a, 6); a += c; \
c -= b; c ^= rot(b, 8); b += a; \
a -= c; a ^= rot(c,16); c += b; \
b -= a; b ^= rot(a,19); a += c; \
c -= b; c ^= rot(b, 4); b += a; \
}
#define final(a,b,c) \
{ \
c ^= b; c -= rot(b,14); \
a ^= c; a -= rot(c,11); \
b ^= a; b -= rot(a,25); \
c ^= b; c -= rot(b,16); \
a ^= c; a -= rot(c, 4); \
b ^= a; b -= rot(a,14); \
c ^= b; c -= rot(b,24); \
}
typedef unsigned long Size;
unsigned int
hash_int4(unsigned int k)
{
register unsigned int a,
b,
c;
a = b = c = 0x9e3779b9 + (unsigned int) sizeof(unsigned int) + 3923095;
a += k;
final(a, b, c);
return c;
}
unsigned int
hash_int8(long unsigned int k)
{
long int val = k;
unsigned int lohalf = (unsigned int) val;
unsigned int hihalf = (unsigned int) (val >> 32);
lohalf ^= (val >= 0) ? hihalf : ~hihalf;
return hash_int4(lohalf);
}
void main()
{
long unsigned int i;
long unsigned int max_hash = 1048576;
Size len = max_hash / 8;
unsigned char *bitmap;
int search = 500;
int nset = 0;
long unsigned int start;
int r = 0;
char str[17];
bitmap = malloc(len);
memset(bitmap, 0, len);
for (i = 0; i < ULONG_MAX; i++)
{
unsigned int h;
int byte;
int bit;
h = hash_int8(i);
if ((i > 0) && (i % 1000000000 == 0))
printf("i=%lu nset=%d\n", i, nset);
if (h >= max_hash)
continue;
byte = h / 8;
bit = h % 8;
if ((bitmap[byte] & (0x01 << bit)) != 0)
continue;
bitmap[byte] |= (0x01 << bit);
nset++;
}
}
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, tgl@sss.pgh.pa.us, andres@anarazel.de, tcook@blackducksoftware.com, thomas.munro@enterprisedb.com
Subject: Re: BUG #14932: SELECT DISTINCT val FROM table gets stuck in an infinite loop
In-Reply-To: <0e91ba4e-5afc-220e-b1f7-56a838aee845@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