Use less memory when growing HEAP tables. See MDEV-436

mysql-test/suite/heap/heap.result:
  Added test case for MDEV-436
mysql-test/suite/heap/heap.test:
  Added test case for MDEV-436
storage/heap/hp_block.c:
  Don't allocate a set of HP_PTRS when not needed. This saves us about 1024 bytes for most allocations.
storage/heap/hp_create.c:
  Made the initial allocation of block sizes depending on min_records and max_records.

2 files changed, 29 insertions, 17 deletions

diff --git a/storage/heap/hp_block.c b/storage/heap/hp_block.c
index 90efeeb7924..01978e2b4e8 100644
--- a/storage/heap/hp_block.c
+++ b/storage/heap/hp_block.c
@@ -64,18 +64,19 @@ int hp_get_new_block(HP_BLOCK *block, size_t *alloc_length)
       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.
+    Allocate space for leaf block (data) plus space for upper level blocks
+    up to first level that has a free slot to put the pointer.
+    If this is a new level, we have to allocate pointers to all future
+    lower levels.
+
+    For example, for level 0, we allocate data for X rows.
+    When level 0 is full, we allocate data for HPTRS_IN_NODE + X rows.
+    Next time we allocate data for X rows.
+    When level 1 is full, we allocate data for HPTRS_IN_NODE at level 2 and 1
+    + X rows at level 0.
    */
-  *alloc_length=sizeof(HP_PTRS)*i+block->records_in_block* block->recbuffer;
+  *alloc_length= (sizeof(HP_PTRS)* ((i == block->levels) ? i : i - 1) +
+                  block->records_in_block* block->recbuffer);
   if (!(root=(HP_PTRS*) my_malloc(*alloc_length,MYF(MY_WME))))
     return 1;
 
diff --git a/storage/heap/hp_create.c b/storage/heap/hp_create.c
index 22ab9b54a85..d170d1abc65 100644
--- a/storage/heap/hp_create.c
+++ b/storage/heap/hp_create.c
@@ -245,21 +245,32 @@ static void init_block(HP_BLOCK *block, uint reclength, ulong min_records,
 {
   uint i,recbuffer,records_in_block;
 
-  max_records= max(min_records,max_records);
+  /*
+    If not min_records and max_records are given, optimize for 1000 rows
+  */
+  if (!min_records)
+    min_records= min(1000, max_records);
   if (!max_records)
-    max_records= 1000;			/* As good as quess as anything */
-  recbuffer= (uint) (reclength + sizeof(uchar**) - 1) & ~(sizeof(uchar**) - 1);
-  records_in_block= max_records / 10;
+    max_records= max(min_records, 1000);
 
   /*
     We don't want too few records_in_block as otherwise the overhead of
     of the HP_PTRS block will be too notable
   */
-  records_in_block= min(1000, max_records);
+  records_in_block= max(1000, min_records);
+  records_in_block= min(records_in_block, max_records);
+  /* If big max_records is given, allocate bigger blocks */
+  records_in_block= max(records_in_block, max_records / 10);
+  /* We don't want too few blocks per row either */
   if (records_in_block < 10)
     records_in_block= 10;
 
-  /* The + 1 is there to ensure that we get at least 1 row per level */
+  recbuffer= (uint) (reclength + sizeof(uchar**) - 1) & ~(sizeof(uchar**) - 1);
+  /*
+    Don't allocate more than my_default_record_cache_size per level.
+    The + 1 is there to ensure that we get at least 1 row per level (for
+    the exceptional case of very long rows)
+  */
   if (records_in_block*recbuffer >
       (my_default_record_cache_size-sizeof(HP_PTRS)*HP_MAX_LEVELS))
     records_in_block= (my_default_record_cache_size - sizeof(HP_PTRS) *