Fix for bug#5138 continued: added comments, removed extra debug printf calls, changed ha_heap::records_in_range to use table->rec_per_key.

heap/hp_block.c:
  Fix for bug#5138 continued: Added comments.
heap/hp_delete.c:
  Fix for bug#5138 continued: Added comments.
heap/hp_write.c:
  Fix for bug#5138 continued: Added comments, removed unneeded printf
include/heap.h:
  Fix for bug#5138 continued: Added comments.
mysql-test/r/heap_hash.result:
  Fix for bug#5138 continued: added FLUSH TABLES and rec_per_key estimates tests, updated test results
mysql-test/t/heap_hash.test:
  Fix for bug#5138 continued: added FLUSH TABLES and rec_per_key estimates tests, updated test results
sql/ha_heap.cc:
  Fix for bug#5138 continued: 
    fixed comments to be correct
    removed unneded printf
    use TABLE::rec_per_key for records_in_range statistics

7 files changed, 208 insertions, 59 deletions

diff --git a/heap/hp_block.c b/heap/hp_block.c
index 6a022fb3084..f26b208b521 100644
--- a/heap/hp_block.c
+++ b/heap/hp_block.c
@@ -18,12 +18,19 @@
 
 #include "heapdef.h"
 
-	/* Find record according to record-position */
+/*
+  Find record according to record-position.
+      
+  The record is located by factoring position number pos into (p_0, p_1, ...) 
+  such that
+     pos = SUM_i(block->level_info[i].records_under_level * p_i)
+  {p_0, p_1, ...} serve as indexes to descend the blocks tree.
+*/
 
 byte *hp_find_block(HP_BLOCK *block, ulong pos)
 {
   reg1 int i;
-  reg3 HP_PTRS *ptr;
+  reg3 HP_PTRS *ptr; /* block base ptr */
 
   for (i=block->levels-1, ptr=block->root ; i > 0 ; i--)
   {
@@ -34,8 +41,18 @@ byte *hp_find_block(HP_BLOCK *block, ulong pos)
 }
 
 
-	/* get one new block-of-records. Alloc ptr to block if neaded */
-	/* Interrupts are stopped to allow ha_panic in interrupts */
+/*
+  Get one new block-of-records. Alloc ptr to block if needed
+  SYNOPSIS
+    hp_get_new_block()
+      block             HP_BLOCK tree-like block
+      alloc_length OUT  Amount of memory allocated from the heap
+      
+  Interrupts are stopped to allow ha_panic in interrupts 
+  RETURN
+    0  OK
+    1  Out of memory
+*/
 
 int hp_get_new_block(HP_BLOCK *block, ulong *alloc_length)
 {
@@ -46,6 +63,18 @@ int hp_get_new_block(HP_BLOCK *block, ulong *alloc_length)
     if (block->level_info[i].free_ptrs_in_block)
       break;
 
+  /*
+    Allocate space for leaf block plus space for upper level blocks up to
+    first level that has a free slot to put the pointer. 
+    In some cases we actually allocate more then we need:
+    Consider e.g. a situation where we have one level 1 block and one level 0
+    block, the level 0 block is full and this function is called. We only 
+    need a leaf block in this case. Nevertheless, we will get here with i=1 
+    and will also allocate sizeof(HP_PTRS) for non-leaf block and will never 
+    use this space.
+    This doesn't add much overhead - with current values of sizeof(HP_PTRS) 
+    and my_default_record_cache_size we get about 1/128 unused memory.
+   */
   *alloc_length=sizeof(HP_PTRS)*i+block->records_in_block* block->recbuffer;
   if (!(root=(HP_PTRS*) my_malloc(*alloc_length,MYF(0))))
     return 1;
@@ -60,21 +89,33 @@ int hp_get_new_block(HP_BLOCK *block, ulong *alloc_length)
     dont_break();		/* Dont allow SIGHUP or SIGINT */
     if ((uint) i == block->levels)
     {
+      /* Adding a new level on top of the existing ones. */
       block->levels=i+1;
+      /*
+        Use first allocated HP_PTRS as a top-level block. Put the current
+        block tree into the first slot of a new top-level block.
+      */
       block->level_info[i].free_ptrs_in_block=HP_PTRS_IN_NOD-1;
       ((HP_PTRS**) root)[0]= block->root;
       block->root=block->level_info[i].last_blocks= root++;
     }
+    /* Occupy the free slot we've found at level i */
     block->level_info[i].last_blocks->
       blocks[HP_PTRS_IN_NOD - block->level_info[i].free_ptrs_in_block--]=
 	(byte*) root;
-
+    
+    /* Add a block subtree with each node having one left-most child */
     for (j=i-1 ; j >0 ; j--)
     {
       block->level_info[j].last_blocks= root++;
       block->level_info[j].last_blocks->blocks[0]=(byte*) root;
       block->level_info[j].free_ptrs_in_block=HP_PTRS_IN_NOD-1;
     }
+    
+    /* 
+      root now points to last (block->records_in_block* block->recbuffer)
+      allocated bytes. Use it as a leaf block.
+    */
     block->level_info[0].last_blocks= root;
     allow_break();		/* Allow SIGHUP & SIGINT */
   }
diff --git a/heap/hp_delete.c b/heap/hp_delete.c
index a89fe49f495..9cf8b8936b6 100644
--- a/heap/hp_delete.c
+++ b/heap/hp_delete.c
@@ -97,8 +97,8 @@ int hp_rb_delete_key(HP_INFO *info, register HP_KEYDEF *keyinfo,
     flag		Is set if we want's to correct info->current_ptr
 
   RETURN
-    0	ok
-    #	error number
+    0      Ok
+    other  Error code
 */
 
 int hp_delete_key(HP_INFO *info, register HP_KEYDEF *keyinfo,
diff --git a/heap/hp_write.c b/heap/hp_write.c
index 853360976bf..43cee67b39c 100644
--- a/heap/hp_write.c
+++ b/heap/hp_write.c
@@ -36,7 +36,6 @@ 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)
   {
@@ -160,7 +159,31 @@ static byte *next_free_record_pos(HP_SHARE *info)
 	      block_pos*info->block.recbuffer);
 }
 
-	/* Write a hash-key to the hash-index */
+
+/*
+  Write a hash-key to the hash-index
+  SYNOPSIS
+    info     Heap table info
+    keyinfo  Key info
+    record   Table record to added
+    recpos   Memory buffer where the table record will be stored if added 
+             successfully
+  NOTE
+    Hash index uses HP_BLOCK structure as a 'growable array' of HASH_INFO 
+    structs. Array size == number of entries in hash index.
+    hp_mask(hp_rec_hashnr()) maps hash entries values to hash array positions.
+    If there are several hash entries with the same hash array position P,
+    they are connected in a linked list via HASH_INFO::next_key. The first 
+    list element is located at position P, next elements are located at 
+    positions for which there is no record that should be located at that
+    position. The order of elements in the list is arbitrary.
+
+  RETURN
+    0  - OK
+    -1 - Out of memory
+    HA_ERR_FOUND_DUPP_KEY - Duplicate record on unique key. The record was 
+    still added and the caller must call hp_delete_key for it.
+*/
 
 int hp_write_key(HP_INFO *info, HP_KEYDEF *keyinfo,
 		 const byte *record, byte *recpos)
@@ -182,33 +205,52 @@ int hp_write_key(HP_INFO *info, HP_KEYDEF *keyinfo,
   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 
+    We're about to add one more hash array position, with hash_mask=#records.
+    The number of hash positions will change and some entries might need to 
+    be relocated to the newly added position. Those entries are currently 
+    members of the list that starts at #first_index position (this is 
+    guaranteed by properties of hp_mask(hp_rec_hashnr(X)) mapping function)
+    At #first_index position currently there may be either:
+    a) An entry with hashnr != first_index. We don't need to move it.
+    or
+    b) A list of items with hash_mask=first_index. The list contains entries
+       of 2 types:
        1) entries that should be relocated to the list that starts at new 
-          position we're adding
+          position we're adding ('uppper' list)
        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.
+          position ('lower' list)
   */
   if (pos != empty)				/* If some records */
   {
     do
     {
       hashnr = hp_rec_hashnr(keyinfo, pos->ptr_to_rec);
-      if (flag == 0)				/* First loop; Check if ok */
+      if (flag == 0)
       {
-        /* Bail out if we're dealing with case b) from above comment */
+        /* 
+          First loop, bail out if we're dealing with case a) from above 
+          comment
+        */
 	if (hp_mask(hashnr, share->blength, share->records) != first_index)
 	  break;
       }
+      /*
+        flag & LOWFIND - found a record that should be put into lower position
+        flag & LOWUSED - lower position occupied by the record
+        Same for HIGHFIND and HIGHUSED and 'upper' position
+
+        gpos  - ptr to last element in lower position's list
+        gpos2 - ptr to last element in upper position's list
+
+        ptr_to_rec - ptr to last entry that should go into lower list.
+        ptr_to_rec2 - same for upper list.
+      */
       if (!(hashnr & halfbuff))
-      {						/* Key will not move */
+      {						
+        /* Key should be put into 'lower' list */
 	if (!(flag & LOWFIND))
 	{
+          /* key is the first element to go into lower position */
 	  if (flag & HIGHFIND)
 	  {
 	    flag=LOWFIND | HIGHFIND;
@@ -219,16 +261,21 @@ int hp_write_key(HP_INFO *info, HP_KEYDEF *keyinfo,
 	  }
 	  else
 	  {
-	    flag=LOWFIND | LOWUSED;		/* key isn't changed */
+            /*
+              We can only get here at first iteration: key is at 'lower' 
+              position pos and should be left here.
+            */
+	    flag=LOWFIND | LOWUSED;
 	    gpos=pos;
 	    ptr_to_rec=pos->ptr_to_rec;
 	  }
 	}
 	else
-	{
+        {
+          /* Already have another key for lower position */
 	  if (!(flag & LOWUSED))
 	  {
-	    /* Change link of previous LOW-key */
+	    /* Change link of previous lower-list key */
 	    gpos->ptr_to_rec=ptr_to_rec;
 	    gpos->next_key=pos;
 	    flag= (flag & HIGHFIND) | (LOWFIND | LOWUSED);
@@ -238,19 +285,21 @@ int hp_write_key(HP_INFO *info, HP_KEYDEF *keyinfo,
 	}
       }
       else
-      {						/* key will be moved */
+      {
+        /* key will be put into 'higher' list */
 	if (!(flag & HIGHFIND))
 	{
 	  flag= (flag & LOWFIND) | HIGHFIND;
 	  /* key shall be moved to the last (empty) position */
-	  gpos2 = empty; empty=pos;
+	  gpos2= empty;
+          empty= pos;
 	  ptr_to_rec2=pos->ptr_to_rec;
 	}
 	else
 	{
 	  if (!(flag & HIGHUSED))
 	  {
-	    /* Change link of previous hash-key and save */
+	    /* Change link of previous upper-list key and save */
 	    gpos2->ptr_to_rec=ptr_to_rec2;
 	    gpos2->next_key=pos;
 	    flag= (flag & LOWFIND) | (HIGHFIND | HIGHUSED);
@@ -262,8 +311,14 @@ int hp_write_key(HP_INFO *info, HP_KEYDEF *keyinfo,
     }
     while ((pos=pos->next_key));
     
-    if ((flag & (LOWFIND | HIGHFIND)) == (LOWFIND | HIGHFIND)) 
+    if ((flag & (LOWFIND | HIGHFIND)) == (LOWFIND | HIGHFIND))
+    {
+      /*
+        If both 'higher' and 'lower' list have at least one element, now
+        there are two hash buckets instead of one.
+      */
       keyinfo->hash_buckets++;
+    }
 
     if ((flag & (LOWFIND | LOWUSED)) == LOWFIND)
     {
diff --git a/include/heap.h b/include/heap.h
index e3e7f228421..5e83a6e2cb5 100644
--- a/include/heap.h
+++ b/include/heap.h
@@ -63,18 +63,48 @@ typedef struct st_heap_ptrs
 
 struct st_level_info
 {
-  uint free_ptrs_in_block,records_under_level;
-  HP_PTRS *last_blocks;			/* pointers to HP_PTRS or records */
+  /* Number of unused slots in *last_blocks HP_PTRS block (0 for 0th level) */
+  uint free_ptrs_in_block;
+  
+  /*
+    Maximum number of records that can be 'contained' inside of each element
+    of last_blocks array. For level 0 - 1, for level 1 - HP_PTRS_IN_NOD, for 
+    level 2 - HP_PTRS_IN_NOD^2 and so forth.
+  */
+  uint records_under_level;
+
+  /*
+    Ptr to last allocated HP_PTRS (or records buffer for level 0) on this 
+    level.
+  */
+  HP_PTRS *last_blocks;			
 };
 
-typedef struct st_heap_block		/* The data is saved in blocks */
+
+/*
+  Heap table records and hash index entries are stored in HP_BLOCKs.
+  HP_BLOCK is used as a 'growable array' of fixed-size records. Size of record
+  is recbuffer bytes.
+  The internal representation is as follows:
+  HP_BLOCK is a hierarchical structure of 'blocks'.
+  A block at level 0 is an array records_in_block records. 
+  A block at higher level is an HP_PTRS structure with pointers to blocks at 
+  lower levels.
+  At the highest level there is one top block. It is stored in HP_BLOCK::root.
+
+  See hp_find_block for a description of how record pointer is obtained from 
+  its index.
+  See hp_get_new_block 
+*/
+
+typedef struct st_heap_block
 {
-  HP_PTRS *root;
+  HP_PTRS *root;                        /* Top-level block */ 
   struct st_level_info level_info[HP_MAX_LEVELS+1];
-  uint levels;
-  uint records_in_block;		/* Records in a heap-block */
+  uint levels;                          /* number of used levels */
+  uint records_in_block;		/* Records in one heap-block */
   uint recbuffer;			/* Length of one saved record */
-  ulong last_allocated;			/* Blocks allocated, used by keys */
+  ulong last_allocated; /* number of records there is allocated space for */
 } HP_BLOCK;
 
 struct st_heap_info;			/* For referense */
diff --git a/mysql-test/r/heap_hash.result b/mysql-test/r/heap_hash.result
index 29287b23745..4f5de197858 100644
--- a/mysql-test/r/heap_hash.result
+++ b/mysql-test/r/heap_hash.result
@@ -233,6 +233,19 @@ id	select_type	table	type	possible_keys	key	key_len	ref	rows	Extra
 insert into t1 select * from t1;
 explain select * from t1 where a='aaaa';
 id	select_type	table	type	possible_keys	key	key_len	ref	rows	Extra
+1	SIMPLE	t1	ref	a	a	8	const	1	Using where
+explain select * from t1 where a='aaab';
+id	select_type	table	type	possible_keys	key	key_len	ref	rows	Extra
+1	SIMPLE	t1	ref	a	a	8	const	1	Using where
+explain select * from t1 where a='aaac';
+id	select_type	table	type	possible_keys	key	key_len	ref	rows	Extra
+1	SIMPLE	t1	ref	a	a	8	const	1	Using where
+explain select * from t1 where a='aaad';
+id	select_type	table	type	possible_keys	key	key_len	ref	rows	Extra
+1	SIMPLE	t1	ref	a	a	8	const	1	Using where
+flush tables;
+explain select * from t1 where a='aaaa';
+id	select_type	table	type	possible_keys	key	key_len	ref	rows	Extra
 1	SIMPLE	t1	ref	a	a	8	const	2	Using where
 explain select * from t1 where a='aaab';
 id	select_type	table	type	possible_keys	key	key_len	ref	rows	Extra
@@ -248,16 +261,16 @@ delete from t1;
 insert into t1 select * from t2;
 explain select * from t1 where a='aaaa';
 id	select_type	table	type	possible_keys	key	key_len	ref	rows	Extra
-1	SIMPLE	t1	ref	a	a	8	const	2	Using where
+1	SIMPLE	t1	ref	a	a	8	const	1	Using where
 explain select * from t1 where a='aaab';
 id	select_type	table	type	possible_keys	key	key_len	ref	rows	Extra
-1	SIMPLE	t1	ref	a	a	8	const	2	Using where
+1	SIMPLE	t1	ref	a	a	8	const	1	Using where
 explain select * from t1 where a='aaac';
 id	select_type	table	type	possible_keys	key	key_len	ref	rows	Extra
-1	SIMPLE	t1	ref	a	a	8	const	2	Using where
+1	SIMPLE	t1	ref	a	a	8	const	1	Using where
 explain select * from t1 where a='aaad';
 id	select_type	table	type	possible_keys	key	key_len	ref	rows	Extra
-1	SIMPLE	t1	ref	a	a	8	const	2	Using where
+1	SIMPLE	t1	ref	a	a	8	const	1	Using where
 drop table t1, t2;
 create table t1 (
 id int unsigned not null primary key auto_increment, 
@@ -305,6 +318,7 @@ insert into t1 (name) select name from t2;
 insert into t1 (name) select name from t2;
 insert into t1 (name) select name from t2;
 insert into t1 (name) select name from t2;
+flush tables;
 select count(*) from t1 where name='Matt';
 count(*)
 7
@@ -314,9 +328,8 @@ id	select_type	table	type	possible_keys	key	key_len	ref	rows	Extra
 show index from t1;
 Table	Non_unique	Key_name	Seq_in_index	Column_name	Collation	Cardinality	Sub_part	Packed	Null	Index_type	Comment
 t1	0	PRIMARY	1	id	NULL	91	NULL	NULL		HASH	
-t1	1	heap_idx	1	name	NULL	15	NULL	NULL		HASH	
+t1	1	heap_idx	1	name	NULL	13	NULL	NULL		HASH	
 t1	1	btree_idx	1	name	A	NULL	NULL	NULL		BTREE	
-flush tables;
 show index from t1;
 Table	Non_unique	Key_name	Seq_in_index	Column_name	Collation	Cardinality	Sub_part	Packed	Null	Index_type	Comment
 t1	0	PRIMARY	1	id	NULL	91	NULL	NULL		HASH	
@@ -333,9 +346,12 @@ show index from t3;
 Table	Non_unique	Key_name	Seq_in_index	Column_name	Collation	Cardinality	Sub_part	Packed	Null	Index_type	Comment
 t3	1	a	1	a	NULL	NULL	NULL	NULL		HASH	
 t3	1	a	2	b	NULL	15	NULL	NULL		HASH	
-flush tables;
 show index from t3;
 Table	Non_unique	Key_name	Seq_in_index	Column_name	Collation	Cardinality	Sub_part	Packed	Null	Index_type	Comment
 t3	1	a	1	a	NULL	NULL	NULL	NULL		HASH	
-t3	1	a	2	b	NULL	13	NULL	NULL		HASH	
-drop table t1,t2;
+t3	1	a	2	b	NULL	15	NULL	NULL		HASH	
+explain select * from t1 ignore key(btree_idx), t3 where t1.name='matt' and t3.a = concat('',t1.name) and t3.b=t1.name;
+id	select_type	table	type	possible_keys	key	key_len	ref	rows	Extra
+1	SIMPLE	t1	ref	heap_idx	heap_idx	20	const	7	Using where
+1	SIMPLE	t3	ref	a	a	40	func,const	6	Using where
+drop table t1, t2, t3;
diff --git a/mysql-test/t/heap_hash.test b/mysql-test/t/heap_hash.test
index df233633840..6d8fdec4b9e 100644
--- a/mysql-test/t/heap_hash.test
+++ b/mysql-test/t/heap_hash.test
@@ -168,6 +168,14 @@ explain select * from t1 where a='aaab';
 explain select * from t1 where a='aaac';
 explain select * from t1 where a='aaad';
 insert into t1 select * from t1;
+
+explain select * from t1 where a='aaaa';
+explain select * from t1 where a='aaab';
+explain select * from t1 where a='aaac';
+explain select * from t1 where a='aaad';
+
+# a known effect: table reload causes statistics to be updated:
+flush tables;
 explain select * from t1 where a='aaaa';
 explain select * from t1 where a='aaab';
 explain select * from t1 where a='aaac';
@@ -203,7 +211,6 @@ insert into t1 (name) values ('Matt'), ('Lilu'), ('Corbin'), ('Carly'),
   ('Suzy'), ('Hoppy'), ('Burrito'), ('Mimi'), ('Sherry'), ('Ben'), ('Phil'), 
   ('Emily'), ('Mike');
 insert into t2 select * from t1;
-
 explain select * from t1 where name='matt';
 explain select * from t2 where name='matt';
 
@@ -222,12 +229,11 @@ insert into t1 (name) select name from t2;
 insert into t1 (name) select name from t2;
 insert into t1 (name) select name from t2;
 insert into t1 (name) select name from t2;
-
+flush tables;
 select count(*) from t1 where name='Matt';
 explain select * from t1 ignore index (btree_idx) where name='matt';
 show index from t1;
 
-flush tables;
 show index from t1;
 
 create table t3
@@ -238,8 +244,10 @@ create table t3
 ) engine=heap;
 insert into t3 select name, name from t1;
 show index from t3;
-flush tables;
 show index from t3;
 
-drop table t1,t2;
+# test rec_per_key use for joins.
+explain select * from t1 ignore key(btree_idx), t3 where t1.name='matt' and t3.a = concat('',t1.name) and t3.b=t1.name;
+
+drop table t1, t2, t3;
 
diff --git a/sql/ha_heap.cc b/sql/ha_heap.cc
index 7643037e24f..5e79ee02745 100644
--- a/sql/ha_heap.cc
+++ b/sql/ha_heap.cc
@@ -32,8 +32,14 @@ const char **ha_heap::bas_ext() const
 
 /*
   Hash index statistics is updated (copied from HP_KEYDEF::hash_buckets to 
-  rec_per_key) after 1/HEAP_STATS_UPDATE_THRESHOLD records have been inserted/
-  updated/deleted. delete_all_rows() and table flush cause immediate update.
+  rec_per_key) after 1/HEAP_STATS_UPDATE_THRESHOLD fraction of table records 
+  have been inserted/updated/deleted. delete_all_rows() and table flush cause 
+  immediate update.
+
+  NOTE
+   hash index statistics must be updated when number of table records changes
+   from 0 to non-zero value and vice versa. Otherwise records_in_range may 
+   erroneously return 0 and 'range' may miss records.
 */
 #define HEAP_STATS_UPDATE_THRESHOLD 10
 
@@ -94,7 +100,6 @@ void ha_heap::set_keys_for_scanning(void)
 
 void ha_heap::update_key_stats()
 {
-  printf("update_key_stats\n");
   for (uint i= 0; i < table->keys; i++)
   {
     KEY *key=table->key_info+i;
@@ -425,13 +430,7 @@ ha_rows ha_heap::records_in_range(uint inx, key_range *min_key,
       max_key->flag != HA_READ_AFTER_KEY)
     return HA_POS_ERROR;			// Can only use exact keys
   else
-  {
-    ha_rows records= file->s->records;
-    if (!records)
-      return 0;
-    ha_rows res= records / file->s->keydef[inx].hash_buckets;
-    return res ? res : 1;
-  }
+    return key->rec_per_key[key->key_parts-1];
 }