Fix for bug#5138: hash indexes on heap tables support statistics.

 KEY::rec_per_key is updated every time 1/HEAP_STATS_UPDATE_THRESHOLD part of table records has been changed.


heap/_check.c:
  Hash indexes on heap tables now support statistics - number of hash buckets. The value is updated on any insert/delete operation.
heap/hp_clear.c:
  Hash indexes on heap tables now support statistics - number of hash buckets. The value is updated on any insert/delete operation.
heap/hp_create.c:
  Hash indexes on heap tables now support statistics - number of hash buckets. The value is updated on any insert/delete operation.
heap/hp_delete.c:
  Hash indexes on heap tables now support statistics - number of hash buckets. The value is updated on any insert/delete operation.
heap/hp_hash.c:
  Hash indexes on heap tables now support statistics - number of hash buckets. The value is updated on any insert/delete operation.
heap/hp_write.c:
  Hash indexes on heap tables now support statistics - number of hash buckets. The value is updated on any insert/delete operation.
include/heap.h:
  Hash indexes on heap tables now support statistics - number of hash buckets. The value is updated on any insert/delete operation.
mysql-test/r/heap.result:
  Fix for bug#5138: store/use statistics for hash indexes on heap tables
mysql-test/r/heap_hash.result:
  Fix for bug#5138: store/use statistics for hash indexes on heap tables
mysql-test/r/myisam.result:
  Fix for bug#5138: store/use statistics for hash indexes on heap tables
mysql-test/t/heap_hash.test:
  Fix for bug#5138: store/use statistics for hash indexes on heap tables
sql/structs.h:
  Added comments

6 files changed, 68 insertions, 10 deletions

diff --git a/heap/_check.c b/heap/_check.c
index 233cb8cb0c5..a745aee48bf 100644
--- a/heap/_check.c
+++ b/heap/_check.c
@@ -102,9 +102,11 @@ static int check_one_key(HP_KEYDEF *keydef, uint keynr, ulong records,
   int error;
   uint i,found,max_links,seek,links;
   uint rec_link;				/* Only used with debugging */
+  uint hash_buckets_found;
   HASH_INFO *hash_info;
 
   error=0;
+  hash_buckets_found= 0;
   for (i=found=max_links=seek=0 ; i < records ; i++)
   {
     hash_info=hp_find_hash(&keydef->block,i);
@@ -128,21 +130,32 @@ static int check_one_key(HP_KEYDEF *keydef, uint keynr, ulong records,
 	  found++;
       }
       if (links > max_links) max_links=links;
+      hash_buckets_found++;
     }
   }
   if (found != records)
   {
-    DBUG_PRINT("error",("Found %ld of %ld records"));
+    DBUG_PRINT("error",("Found %ld of %ld records", found, records));
+    error=1;
+  }
+  if (keydef->hash_buckets != hash_buckets_found)
+  {
+    DBUG_PRINT("error",("Found %ld buckets, stats shows %ld buckets",
+                        hash_buckets_found, keydef->hash_buckets));
     error=1;
   }
   DBUG_PRINT("info",
-	     ("records: %ld   seeks: %d   max links: %d   hitrate: %.2f",
+	     ("records: %ld   seeks: %d   max links: %d   hitrate: %.2f   "
+              "buckets: %d",
 	      records,seek,max_links,
-	      (float) seek / (float) (records ? records : 1)));
+	      (float) seek / (float) (records ? records : 1), 
+              hash_buckets_found));
   if (print_status)
-    printf("Key: %d  records: %ld   seeks: %d   max links: %d   hitrate: %.2f\n",
+    printf("Key: %d  records: %ld   seeks: %d   max links: %d   "
+           "hitrate: %.2f   buckets: %d\n",
 	   keynr, records, seek, max_links,
-	   (float) seek / (float) (records ? records : 1));
+	   (float) seek / (float) (records ? records : 1), 
+           hash_buckets_found);
   return error;
 }
 
diff --git a/heap/hp_clear.c b/heap/hp_clear.c
index 4440344f990..596d71ebe9c 100644
--- a/heap/hp_clear.c
+++ b/heap/hp_clear.c
@@ -97,6 +97,7 @@ void hp_clear_keys(HP_SHARE *info)
         VOID(hp_free_level(block,block->levels,block->root,(byte*) 0));
       block->levels=0;
       block->last_allocated=0;
+      keyinfo->hash_buckets= 0;
     }
   }
   info->index_length=0;
diff --git a/heap/hp_create.c b/heap/hp_create.c
index 02725576c8f..d1783118c0d 100644
--- a/heap/hp_create.c
+++ b/heap/hp_create.c
@@ -128,6 +128,7 @@ int heap_create(const char *name, uint keys, HP_KEYDEF *keydef,
 		   max_records);
 	keyinfo->delete_key= hp_delete_key;
 	keyinfo->write_key= hp_write_key;
+        keyinfo->hash_buckets= 0;
       }
     }
     share->min_records= min_records;
diff --git a/heap/hp_delete.c b/heap/hp_delete.c
index c918cf37f05..a89fe49f495 100644
--- a/heap/hp_delete.c
+++ b/heap/hp_delete.c
@@ -151,6 +151,8 @@ int hp_delete_key(HP_INFO *info, register HP_KEYDEF *keyinfo,
     pos->ptr_to_rec=empty->ptr_to_rec;
     pos->next_key=empty->next_key;
   }
+  else
+    keyinfo->hash_buckets--;
 
   if (empty == lastpos)			/* deleted last hash key */
     DBUG_RETURN (0);
@@ -187,7 +189,11 @@ int hp_delete_key(HP_INFO *info, register HP_KEYDEF *keyinfo,
     }
     pos3= pos;				/* Link pos->next after lastpos */
   }
-  else pos3= 0;				/* Different positions merge */
+  else
+  {
+    pos3= 0;				/* Different positions merge */
+    keyinfo->hash_buckets--;
+  }
 
   empty[0]=lastpos[0];
   hp_movelink(pos3, empty, pos->next_key);
diff --git a/heap/hp_hash.c b/heap/hp_hash.c
index 71eecc8bdf2..2108765cc7f 100644
--- a/heap/hp_hash.c
+++ b/heap/hp_hash.c
@@ -196,7 +196,18 @@ byte *hp_search_next(HP_INFO *info, HP_KEYDEF *keyinfo, const byte *key,
 }
 
 
-	/* Calculate pos according to keys */
+/*
+  Calculate position number for hash value.
+  SYNOPSIS
+    hp_mask()
+      hashnr     Hash value
+      buffmax    Value such that
+                 2^(n-1) < maxlength <= 2^n = buffmax
+      maxlength  
+  
+  RETURN
+    Array index, in [0..maxlength)
+*/
 
 ulong hp_mask(ulong hashnr, ulong buffmax, ulong maxlength)
 {
@@ -205,7 +216,12 @@ ulong hp_mask(ulong hashnr, ulong buffmax, ulong maxlength)
 }
 
 
-	/* Change link from pos to new_link */
+/*
+  Change
+    next_link -> ... -> X -> pos
+  to
+    next_link -> ... -> X -> newlink
+*/
 
 void hp_movelink(HASH_INFO *pos, HASH_INFO *next_link, HASH_INFO *newlink)
 {
diff --git a/heap/hp_write.c b/heap/hp_write.c
index 3b0ec76d616..853360976bf 100644
--- a/heap/hp_write.c
+++ b/heap/hp_write.c
@@ -36,7 +36,7 @@ int heap_write(HP_INFO *info, const byte *record)
   byte *pos;
   HP_SHARE *share=info->s;
   DBUG_ENTER("heap_write");
-
+  printf("heap_write\n");
 #ifndef DBUG_OFF
   if (info->mode & O_RDONLY)
   {
@@ -180,15 +180,31 @@ int hp_write_key(HP_INFO *info, HP_KEYDEF *keyinfo,
     DBUG_RETURN(-1);				/* No more memory */
   halfbuff= (long) share->blength >> 1;
   pos= hp_find_hash(&keyinfo->block,(first_index=share->records-halfbuff));
-
+  
+  /*
+    We're about to add one more hash position, with hash_mask=#records. 
+    Entries that should be relocated to that position are currently members 
+    of the list that starts at #first_index position.
+    At #first_index position there may be either:
+    a) A list of items with hash_mask=first_index. The list contains 
+       1) entries that should be relocated to the list that starts at new 
+          position we're adding
+       2) entries that should be left in the list starting at #first_index 
+          position 
+    or
+    b) An entry with hashnr != first_index. We don't need to move it.
+  */
   if (pos != empty)				/* If some records */
   {
     do
     {
       hashnr = hp_rec_hashnr(keyinfo, pos->ptr_to_rec);
       if (flag == 0)				/* First loop; Check if ok */
+      {
+        /* Bail out if we're dealing with case b) from above comment */
 	if (hp_mask(hashnr, share->blength, share->records) != first_index)
 	  break;
+      }
       if (!(hashnr & halfbuff))
       {						/* Key will not move */
 	if (!(flag & LOWFIND))
@@ -245,6 +261,9 @@ int hp_write_key(HP_INFO *info, HP_KEYDEF *keyinfo,
       }
     }
     while ((pos=pos->next_key));
+    
+    if ((flag & (LOWFIND | HIGHFIND)) == (LOWFIND | HIGHFIND)) 
+      keyinfo->hash_buckets++;
 
     if ((flag & (LOWFIND | LOWUSED)) == LOWFIND)
     {
@@ -265,6 +284,7 @@ int hp_write_key(HP_INFO *info, HP_KEYDEF *keyinfo,
   {
     pos->ptr_to_rec=recpos;
     pos->next_key=0;
+    keyinfo->hash_buckets++;
   }
   else
   {
@@ -280,6 +300,7 @@ int hp_write_key(HP_INFO *info, HP_KEYDEF *keyinfo,
     }
     else
     {
+      keyinfo->hash_buckets++;
       pos->ptr_to_rec=recpos;
       pos->next_key=0;
       hp_movelink(pos, gpos, empty);