Hashing Algorithm

At 10:02 PM +0200 4/10/99, Raoul A. Joemman wrote:
>Hash tables are very fast for exact key maches, but not when there are to
>much overflow pages.
>Almost all our tables are btree.  I want to make some off them hash but I
>don't know how much overflows there will be after modification.
>Does somebody know which hashing algorithm Ingres uses. Because I want to
>calculate the number off overflow pages before I modify the table and not
>just try and see.

I don't know the exact algorithm.  Hashing tends to be very algorithm
sensitive.  I think you would be better off modifying the table (or a copy)
and examining the results;  I think it's unlikely you would get sufficiently
reliable answers otherwise, unless you were working with the source code
at your elbow.

Remember that the number of overflow pages is only part of the picture.
More important is the distribution.  In a large table, having 50% of
the table in overflow pages may not be bad if nearly all hash chains are
just 2 pages long.  If many hash chains are more than say 3 or 4 pages
long you may need to adjust parameters such as the number of main pages.
You can determine the distribution by examining tids (a table scan proceeds
down each hash chain in turn, so the tid sequence tells you about the
hash chains);  or with OpenIngres/Ingres II you can issue the
MODIFY table TO TABLE_DEBUG WITH TABLE_OPTION=2
command (note this is not documented in the SQL Reference). The second part
of the output shows you the hash chain distribution pictorially.


Karl R. Schendel, Jr.
K/B Computer Associates   schendel@kbcomputer.com
Ingres and Unix Expertise

President, North American Ingres Users Association
president@naiua.org
Ingres Q & A
Back to William's Home Page
Email William