Skip site navigation (1) Skip section navigation (2)

Hash Index Build Patch

From: Tom Raney <twraney(at)comcast(dot)net>
To: pgsql-patches(at)postgresql(dot)org
Subject: Hash Index Build Patch
Date: 2007-09-26 04:53:55
Message-ID: 46F9E5E3.5040201@comcast.net (view raw or flat)
Thread:
Lists: pgsql-patches
Hello All,

We have prepared a patch (against CVS HEAD)for the TODO item:
* Hash
   -During index creation, pre-sort the tuples to improve build speed
      http://archives.postgresql.org/pgsql-hackers/2007-03/msg01199.php

Details of this patch's performance improvements can be found at 
http://web.cecs.pdx.edu/~raneyt/pg/.
 
For example, in one 12 million tuple example, the 8.2.4 hash index
build required over 2.8 hours while this patch's build required 80
seconds. Hash build times are now comparable to BTree build times,
for example, for a 60 million tuple example the patched hash index
build time is 8.1 minutes and the BTree build time is 4.6 minutes.

We used spool functions from the BTree code to sort the index
tuples. Sorting is done on the hash value of the tuples.  The hash
value depends on the number of primary bucket pages (henceforth
just bucket pages) that will be required to fit all the index
tuples. So, before sorting, the base relation is scanned to get
the total number of tuples. Then, the fill factor (either default
or user defined, as applicable) is used to get the estimate of the
number of bucket pages.

The 8.2.4 code builds the index by inserting one tuple at a time
and splitting buckets as needed.  We pre-allocate the estimated
number of bucket pages all at once. This avoids bucket page splits
and thus redistribution of index tuples between the bucket page
that caused the split and the newly created bucket page.

We changed the values of low_mask, high_mask and max_bucket, used
by hashkey2bucket () while inserting index tuples to bucket pages.
They are set as follows:
Low_mask = (power of 2 value-1) less than the estimate.
High_mask = (power of 2 value-1) greater than the estimate.
Max_bucket = estimated number of bucket -1 (because bucket numbers
start from 0).

(Please note: hashsort.c is a new file and resides in 
src/backend/access/hash/)

We have also attached the simple data generator we used in the
tests.  Our SQL statements were as follows:

DROP TABLE IF EXISTS test;

CREATE TABLE test (
   value      INTEGER
);

COPY test FROM 'data';
\timing
CREATE INDEX hash ON test USING HASH(value);

Regards,
Shreya Bhargava <shreya_bhargav(at)yahoo(dot)com>
Tom Raney <twraney(at)comcast(dot)net>


Attachment: hash_index_build.patch
Description: text/plain (20.4 KB)
Attachment: tuplegen.c
Description: text/plain (450 bytes)
Attachment: hashsort.c
Description: text/plain (3.1 KB)

Responses

pgsql-patches by date

Next:From: Bruce MomjianDate: 2007-09-26 08:23:20
Subject: Re: Error correction for n_dead_tuples
Previous:From: ITAGAKI TakahiroDate: 2007-09-26 04:43:34
Subject: Re: Thread-safe PREPARE in ecpg

Privacy Policy | About PostgreSQL
Copyright © 1996-2014 The PostgreSQL Global Development Group