Re: Hash index todo list item

On Wed, Sep 05, 2007 at 03:07:03PM -0500, Kenneth Marshall wrote:
> On Sun, Sep 02, 2007 at 01:04:04PM -0500, Kenneth Marshall wrote:
> > Dear PostgreSQL Hackers:
> >
> > After following the hackers mailing list for quite a while,
> > I am going to start investigating what will need to be done
> > to improve hash index performance. Below are the pieces of
> > this project that I am currently considering:
> >
> > 1. Characterize the current hash index implementation against
> > the BTree index, with a focus on space utilization and
> > lookup performance against a collection of test data. This
> > will give a baseline performance test to evaluate the impact
> > of changes. I initially do not plan to bench the hash creation
> > process since my initial focus will be on lookup performance.
> >
>
> Here are very basic results for a table with 1.6m entries:
>
> postgres=# CREATE TABLE dict (word varchar(100));
> CREATE TABLE
>
> postgres=# COPY dict FROM '/tmp/words';
> COPY 1648379
> postgres=# select count(*) from dict;
> count
> ---------
> 1648379
> (1 row)
>
> Time: 11187.418 ms
> postgres=# select count(*) from dict;
> count
> ---------
> 1648379
> (1 row)
>
> Time: 6040.912 ms
> postgres=# CREATE INDEX wordhash ON dict USING hash (word);
> CREATE INDEX
> Time: 11108707.160 ms
>
> postgres=# select * from dict where word = 'avatar';
> word
> --------
> avatar
> (1 row)
>
> Time: 79.823 ms
> postgres=# select * from dict where word = 'zebra';
> word
> -------
> zebra
> (1 row)
>
> Time: 9.864 ms
> postgres=# select * from dict where word = 'turkey';
> word
> --------
> turkey
> (1 row)
>
> Time: 18.418 ms
> Time: 1.045 ms
> Time: 1.257 ms
> Time: 1.080 ms
>
> postgres=# CREATE INDEX wordbtree ON dict USING btree (word);
> CREATE INDEX
>
> Time: 25438.884 ms
>
> postgres=# select * from dict where word = 'avatar';
> word
> --------
> avatar
> (1 row)
>
> Time: 13.400 ms
> postgres=# select * from dict where word = 'zebra';
> word
> -------
> zebra
> (1 row)
>
> Time: 1.173 ms
> postgres=# select * from dict where word = 'turkey';
> word
> --------
> turkey
> (1 row)
>
> Time: 1.186 ms
> Time: 1.103 ms
> Time: 1.099 ms
> Time: 1.108 ms
>
> ------------------------------
> Size of table = 87556096
>
> Size of hash index = 268451840
> Size of btree index = 53510144
>
> From my very small sample on an unloaded machine, a hash index lookup
> took the least amount of time. It had a much larger initial time which
> could be attributable to cache population effects. The size is 5X that
> of the Btree index. I will continue to improve the test suite as more
> granularity is needed. If anyone has a good data generator, please let
> me know. Otherwise I will just roll my own.
>
> Regards,
> Ken
>
I have just re-ran the previous benchmark against 8.3beta1 (versus 8.2)
including the hash index sorted build patch and the results are below:

test=# CREATE TABLE dict (word varchar(100));
CREATE TABLE
Time: 24.463 ms
test=# COPY dict FROM '/tmp/cracklib-words';
LOG: checkpoints are occurring too frequently (21 seconds apart)
HINT: Consider increasing the configuration parameter "checkpoint_segments".
COPY 1648379
Time: 44470.235 ms
test=# select count(*) from dict;
count
---------
1648379
(1 row)

Time: 4553.924 ms
test=# CREATE INDEX wordhash ON dict USING hash (word);
CREATE INDEX
Time: 85905.960 ms
test=# select * from dict where word = 'avatar';
word
--------
avatar
(1 row)

Time: 592.906 ms
test=# select * from dict where word = 'zebra';
word
-------
zebra
(1 row)

Time: 21.458 ms
test=# select * from dict where word = 'turkey';
word
--------
turkey
(1 row)

Time: 22.532 ms
Time: 1.224 ms
Time: 1.200 ms
Time: 1.264 ms
test=# CREATE INDEX wordbtree ON dict USING btree (word);
CREATE INDEX
Time: 33714.874 ms
test=# select * from dict where word = 'avatar';
word
--------
avatar
(1 row)

Time: 24.296 ms
test=# select * from dict where word = 'zebra';
word
-------
zebra
(1 row)

Time: 1.400 ms
test=# select * from dict where word = 'turkey';
word
--------
turkey
(1 row)

Time: 28.302 ms
Time: 1.284 ms
Time: 1.313 ms

---------------------------------------
Size of table = 69877760

Size of hash index = 268451840
Size of btree index = 48570368

I just wanted to have this baseline for future patches since
8.3 is just around the bend. As expected, the sorted build
process is a huge improvement from the unsorted original.

Regards,
Ken Marshall