Description:
In the case where most searches on a HASH key of HEAP table will result in non-match, the
implementation is currently unoptimized and inferior to traditional sparsely populated
hashing algorithms. An optimal solution is provided below, which maximizes speed and
minimizes memory usage.
These cases can be quite important. For example, in our application we want to have a
table of tokens which indicate a message is a spam. Typically these tokens will be very
few in number, yet the total number of tokens to be tested will be very large. Perhaps
several orders of magnitude between the two, so perhaps 99.99% of searches will result in
a non-match.
(1) Please refer to following prequisite bug report, where I studied the "mysys/hash.c"
source code (granted the "heap/hash.c" may differ slightly but I think all points herein
remain valid and applicable):
http://bugs.mysql.com/bug.php?id=7817
Currently, the HASH key implementation _never_ has an empty hash bucket, the # of buckets
is always equal the # of records, and the overhead for duplicates is almost the same as
for non-matches.
The algorithm for searching is:
* calculate hash index of search key into hash table array
* In a loop, test for key match in each linked node in hash table array
* If record of 1st node in loop has a key whose hash index does not
match the calculated hash index, then search key does not exist
and exit loop
* loop ends with last linked node
Additionally (but not crucial to my reason for optimizing this) there are even rarer more
degenerate (even slower) cases:
* a non-match may in some cases require walking entire linked list in the
loop, when record of 1st node in loop has a key whose hash index _does_
match the calculated hash index
* without "MTF" optimization, duplicates may in some cases require walking
entire linked list in the loop
(2) Thus for both non-matches and duplicates, minimally the hash index function must be
called twice and at least one key compared. For long char() keys this can be quite
expensive.
(3) In the prequisite bug report above, I already proposed a faster hash function. This
will help, especially duplicates, but is lacking for non-matches. Also I proposed an
"MTF" algorithm so that searching for MRU duplicates results in less slowdown due to
duplicates.
(4) However, #3 still does not make non-matches as fast as for a sparsely populated hash
table. Thus I propose that a new keyword be added, e.g. "HASH_QUICK (multiple)", for
which in addition to the hash table buckets for hash.h::HASH_LINK, there is also a
duplicate hash table buckets array where each bucket is 1 bit and the # of buckets (the
TSIZE per source code of the optimal hash function I suggested) is much greater than
("multiple" multiplied by) the number of records. For example, if the TSIZE for the bit
bucket array was 32 times larger than for the HASH_LINK bucket array, then the bit bucket
array would only consume 50% less memory than the HASH_LINK bucket array (because
HASH_LINK is 64 bits on 32 bit cpu). The bit bucket array and HASH_LINK bucket array
could each use different hash functions as well, if desired.
Thus for most non-matches (roughly 31/32 if use 32 as "multiple") it would only involve
masking the hash function return value to the appropriate bit and if bit is not set then
immediately return non-match. If bit is set, then continue with HASH key code.
How to repeat:
Please read Description.
Suggested fix:
Please read Description.
