Subject: Re: BUG #14932: SELECT DISTINCT val FROM table gets stuck in an
 infinite loop
To: Tom Lane <tgl@sss.pgh.pa.us>, Andres Freund <andres@anarazel.de>
Cc: "Todd A. Cook" <tcook@blackducksoftware.com>,
 Thomas Munro <thomas.munro@enterprisedb.com>,
 PostgreSQL Bugs <pgsql-bugs@postgresql.org>
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>
From: Tomas Vondra <tomas.vondra@2ndquadrant.com>
Message-ID: <0e91ba4e-5afc-220e-b1f7-56a838aee845@2ndquadrant.com>
Date: Thu, 7 Dec 2017 00:45:34 +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: <16912.1512600919@sss.pgh.pa.us>
Content-Type: multipart/mixed;
 boundary="------------3F757AA8719B60C565E1099D"
Content-Language: en-US
Precedence: bulk

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


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

--------------3F757AA8719B60C565E1099D
Content-Type: text/x-csrc;
 name="duplicities-bigint.c"
Content-Transfer-Encoding: 7bit
Content-Disposition: attachment;
 filename="duplicities-bigint.c"

#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++;
	}
}

--------------3F757AA8719B60C565E1099D--