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
Views: Raw Message | Whole Thread | Download mbox | Resend email
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 Content-Type Size
hashsort.c text/plain 3.1 KB
tuplegen.c text/plain 450 bytes
hash_index_build.patch text/plain 20.4 KB

Responses

Browse pgsql-patches by date

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