Date: Tue, 9 Sep 2008 08:48:39 -0500
From: Kenneth Marshall <ktm@rice.edu>
To: Alex Hunsaker <badalex@gmail.com>
Cc: Tom Lane <tgl@sss.pgh.pa.us>, Xiao Meng <mx.cogito@gmail.com>,
	Zdenek Kotala <Zdenek.Kotala@sun.com>, pgsql-patches@postgresql.org,
	"Jonah H. Harris" <jonah.harris@gmail.com>
Subject: Re: hash index improving v3
Message-ID: <20080909134839.GC6714@it.is.rice.edu>
References: <10995.1220577198@sss.pgh.pa.us> <11525.1220579153@sss.pgh.pa.us>
	<34d269d40809041854g355a8f68ga3a037a69e3d9fcb@mail.gmail.com>
	<11962.1220581027@sss.pgh.pa.us>
	<34d269d40809042048m3b532a5ej7a9588f63a788d0c@mail.gmail.com>
	<34d269d40809050912u33f2afc8mb90e316bc465136e@mail.gmail.com>
	<34d269d40809051321w2ed16037od0373a4a29c311f1@mail.gmail.com>
	<34d269d40809052249h59750f83v4b19a50d0555580@mail.gmail.com>
	<22574.1220728178@sss.pgh.pa.us>
	<34d269d40809061923k4c731481gf580d46d259defb0@mail.gmail.com>
MIME-Version: 1.0
Content-Type: text/plain; charset=us-ascii
Content-Disposition: inline
In-Reply-To: <34d269d40809061923k4c731481gf580d46d259defb0@mail.gmail.com>
User-Agent: Mutt/1.5.16 (2007-06-09)

On Sat, Sep 06, 2008 at 08:23:05PM -0600, Alex Hunsaker wrote:
> On Sat, Sep 6, 2008 at 1:09 PM, Tom Lane <tgl@sss.pgh.pa.us> wrote:
> >For the convenience of anyone intending to test, here is an updated
> >patch against CVS HEAD that incorporates Alex's fix.
> 
> Here are the results for a table containing 1 million entries that
> will generate hash collisions.  It paints a bad picture for the patch
> but then again im not sure how relevant the issue is.  For example
> yesterday I imported a table with 10 million collisions and the create
> index is still running (now at about ~18 hours).  Maybe we should warn
> if there are lots of collisions when creating the index and suggest
> you use a btree? Anyway here are the results.
> 
I think that the glacial speed for generating a big hash index is
the same problem that the original code faced. Because of the collisions
you are unable to achieve the correct packing that the code assumes.
This results in the splitting/copying of every page in the hash index,
a very slow proposition. I had suggested adding some additional parameters
like fillfactor to accomodate these sorts of situations. Since your test
cuts the effective fill by 2 because of the many collisions, you would
need to adjust that calculation to avoid the tremendous amount of random
I/O generated by that mis-assumption.

> ./pgbench -c1 -n -t10 -f bench_createindex.sql
> cvs head: tps = 0.002169
> v5          : tps = 0.002196
> 
> pgbench -c1 -n -t1000 -f bench_bitmap.sql
> cvs head: tps = 24.011871
> v5:           tps = 2.543123
> 
> pgbench -c1 -n -t1000 -f bench_index.sql
> cvs head: tps = 51.614502
> v5:           tps = 3.205542
> 
> pgbench -c1 -n -t1000 -f bench_seqscan.sql
> cvs head: tps = 8.553318
> v5:           tps = 9.836091
> 
> Table created via:
> create table test_hash (num int8);
> ./hash | psql -c 'copy test_hash from stdin;'

It would be useful to have an equivalent test for the hash-only
index without the modified int8 hash function, since that would
be more representative of its performance. The collision rates
that I was observing in my tests of the old and new mix() functions
was about 2 * (1/10000) of what you test generated. You could just
test against the integers between 1 and 2000000.

Ken