Re: [PATCH]-hash index improving - Mailing list pgsql-hackers

On Tue, Jul 22, 2008 at 08:36:34PM -0700, Dann Corbit wrote:
> > -----Original Message-----
> > From: pgsql-hackers-owner@postgresql.org [mailto:pgsql-hackers-
> > owner@postgresql.org] On Behalf Of Xiao Meng
> > Sent: Tuesday, July 22, 2008 7:57 PM
> > To: Simon Riggs
> > Cc: pgsql-hackers@postgresql.org
> > Subject: Re: [HACKERS] [PATCH]-hash index improving
> > 
> > Well, I'll do it after I finish my second patch.
> > Hash index should be more efficient than btree when N is big enough.
> > It seems meaningful to find how big N is in an experiment way.
> 
> The savings will depend on many factors.  Another thing (besides volume) which is important is the sort of key data
beingindexed.
 
> 
> Consider a unique key on six varchar(40) fields:
> 
> 1.  Country
> 2.  State/Province
> 3.  City
> 4.  Division
> 5.  Branch
> 6.  Office
> 
> Typically, a key such as this will have lots of clumps of similar data, only being differentiated with the final
segment. This sort of index is often used for reporting purposes.  To determine a unique entry, it is not unlikely that
morethan 200 characters will be traversed.  A hash index gets a special boost here because a much smaller data
signatureis stored.  Even a 64 bit hash occupies only 8 bytes.  On the other hand, consider an index on a field
consistingof a single character.  Here, the pages of the b-tree will have a huge volume of entries per page, requiring
fewerpages to search, and the hash index is many times larger and hence more pages will have to be loaded.
 
> 
> These things make a hash index desirable:
> 1. Unique index
> 2. Long keys
> 3. Huge data cardinality
> 4. Equality search
> 
> These things make a hash index undesirable:
> 1.  Non-unique index
> 2.  Short keys
> 3.  Small data sets
> 
I mentioned in a previous E-mail, adding some additional informational settings
that can be used like fill-factor to improve the layout and performance of a hash
index. They are roughly:  - number of elements  - maximum number of elements  - multiplicity - estimate of element
repetitionin a non-unique index
 
Knowing the number of elements in advance can allow the index to be pre-created
in the optimal layout and disk footprint. For every multiple of 256, you can
reduce the space needed by the hash value stored by 8-bits. For large indexes
you can store a 64-bit hash in the same space as the 32-bit hash in a small
index. This will allow for the use of larger hash values which will result in
better data distribution between the buckets and more O(1) like behavior.

> These things render a hash index as worthless (except in COMBINATION with a b-tree type index):
> 1.  Need for range searches like BETWEEN
> 2.  Need for ORDER BY on the column(s)
> 
> As an aside:
> I guess it will also be nice if you can CLUSTER both index and data values on the hash.  It may need a different
algorithmthan a b-tree clustering concept.  I know that Rdb uses different kinds of storage areas for hashed indexes
versesb-tree indexes.
 
> 
Clustering a hash index will allow for much smaller indexes through the use
of prefix-compression of the common heap tuple id's. Now an entry in the hash
index would need sizeof(hash) + sizeof(heap tuple id) which is 4 + 6 = 10bytes
before clustering. After clustering and for large indexes, this could drop to
4bytes per entry plus a constant value.

> This effort to create hashed indexes is very valuable.  Because it becomes more and more dominant as the data scales
up,right at the point when things get tougher is when it becomes the most helpful.  If you have a tiny table, it does
noteven matter if you index it, because (for instance) 10 rows will probably always stay in memory and iteration will
findwhat is needed instantly.  But if you have hundreds of millions of rows or billions of rows, now is when
performancereally matters.  So when the data scales to preposterous size (which it has an uncanny ability to do) the
boostof performance becomes even more valuable.
 

Although it is a clear theoretical benefit from the O(1) lookup for large indexes,
I think that the cross-over point between btree and hash indexes may take place
for smaller indexes than might be expected due to the possibly smaller memory footprint
needed for the hash index. Of course, this will all need to be tested.

Regards,
Ken