memory-limited tree

bulk inserts optimization: caching keys in binary tree

11 files changed, 162 insertions, 27 deletions

diff --git a/myisam/ft_boolean_search.c b/myisam/ft_boolean_search.c
index 8f7f8ab5d73..3562e05006a 100644
--- a/myisam/ft_boolean_search.c
+++ b/myisam/ft_boolean_search.c
@@ -198,8 +198,8 @@ FT_DOCLIST *ft_boolean_search(MI_INFO *info, uint keynr, byte *query,
   aio.end=query+query_len;
   aio.total_yes=aio.total_no=0;
 
-  init_tree(&aio.dtree,0,sizeof(FT_SUPERDOC),(qsort_cmp2)&FT_SUPERDOC_cmp,0,
-            NULL);
+  init_tree(&aio.dtree,0,0,sizeof(FT_SUPERDOC),(qsort_cmp2)&FT_SUPERDOC_cmp,0,
+            NULL, NULL);
 
   if (do_boolean(&aio,0,0,0,0))
     goto err;
diff --git a/myisam/ft_nlq_search.c b/myisam/ft_nlq_search.c
index 6d76fcef6e8..350a60708f6 100644
--- a/myisam/ft_nlq_search.c
+++ b/myisam/ft_nlq_search.c
@@ -163,8 +163,8 @@ FT_DOCLIST *ft_nlq_search(MI_INFO *info, uint keynr, byte *query,
 
   bzero(&allocated_wtree,sizeof(allocated_wtree));
 
-  init_tree(&aio.dtree,0,sizeof(FT_SUPERDOC),(qsort_cmp2)&FT_SUPERDOC_cmp,0,
-            NULL);
+  init_tree(&aio.dtree,0,0,sizeof(FT_SUPERDOC),(qsort_cmp2)&FT_SUPERDOC_cmp,0,
+            NULL, NULL);
 
   if(!(wtree=ft_parse(&allocated_wtree,query,query_len)))
     return NULL;
diff --git a/myisam/ft_parser.c b/myisam/ft_parser.c
index ee4b5ea7202..73d9eccfd16 100644
--- a/myisam/ft_parser.c
+++ b/myisam/ft_parser.c
@@ -226,7 +226,7 @@ TREE * ft_parse(TREE *wtree, byte *doc, int doclen)
 
   if (!is_tree_inited(wtree))
   {
-    init_tree(wtree,0,sizeof(FT_WORD),(qsort_cmp2)&FT_WORD_cmp,0,NULL);
+    init_tree(wtree,0,0,sizeof(FT_WORD),(qsort_cmp2)&FT_WORD_cmp,0,NULL, NULL);
   }
 
   while (ft_simple_get_word(&doc,end,&w))
diff --git a/myisam/ft_stopwords.c b/myisam/ft_stopwords.c
index d3dedc4c406..8565a153b81 100644
--- a/myisam/ft_stopwords.c
+++ b/myisam/ft_stopwords.c
@@ -41,8 +41,8 @@ int ft_init_stopwords(const char **sws)
   if(!stopwords3)
   {
     if(!(stopwords3=(TREE *)my_malloc(sizeof(TREE),MYF(0)))) return -1;
-    init_tree(stopwords3,0,sizeof(FT_STOPWORD),(qsort_cmp2)&FT_STOPWORD_cmp,0,
-	      NULL);
+    init_tree(stopwords3,0,0,sizeof(FT_STOPWORD),(qsort_cmp2)&FT_STOPWORD_cmp,0,
+	      NULL, NULL);
   }
 
   if(!sws) return 0;
diff --git a/myisam/mi_extra.c b/myisam/mi_extra.c
index e1e4fe75a07..d7f3e4dc04a 100644
--- a/myisam/mi_extra.c
+++ b/myisam/mi_extra.c
@@ -336,6 +336,24 @@ int mi_extra(MI_INFO *info, enum ha_extra_function function)
   case HA_EXTRA_QUICK:
     info->quick_mode=1;
     break;
+  case HA_EXTRA_BULK_INSERT_BEGIN:
+    error=_mi_init_bulk_insert(info);
+    break;
+  case HA_EXTRA_BULK_INSERT_END:
+    if (info->bulk_insert)
+    {
+      uint i;
+      for (i=0 ; i < share->base.keys ; i++)
+      {
+        if (is_tree_inited(& info->bulk_insert[i]))
+        {
+          delete_tree(& info->bulk_insert[i]);
+        }
+      }
+      my_free((void *)info->bulk_insert, MYF(0));
+      info->bulk_insert=0;
+    }
+    break;
   case HA_EXTRA_NO_ROWS:
     if (!share->state.header.uniques)
       info->opt_flag|= OPT_NO_ROWS;
diff --git a/myisam/mi_open.c b/myisam/mi_open.c
index 7f94de9ffa2..d4b677e12dd 100644
--- a/myisam/mi_open.c
+++ b/myisam/mi_open.c
@@ -461,6 +461,7 @@ MI_INFO *mi_open(const char *name, int mode, uint open_flags)
     share->options|=HA_OPTION_READ_ONLY_DATA;
   info.lock_type=F_UNLCK;
   info.quick_mode=0;
+  info.bulk_insert=0;
   info.errkey= -1;
   info.page_changed=1;
   pthread_mutex_lock(&share->intern_lock);
diff --git a/myisam/mi_static.c b/myisam/mi_static.c
index bb7fece4d18..389aac3142a 100644
--- a/myisam/mi_static.c
+++ b/myisam/mi_static.c
@@ -40,7 +40,7 @@ my_bool myisam_concurrent_insert=0;
 #endif
 my_off_t myisam_max_extra_temp_length= MI_MAX_TEMP_LENGTH;
 my_off_t myisam_max_temp_length= MAX_FILE_SIZE;
-
+uint myisam_bulk_insert_tree_size=8192*1024;
 
 /* read_vec[] is used for converting between P_READ_KEY.. and SEARCH_ */
 /* Position is , == , >= , <= , > , < */
diff --git a/myisam/mi_write.c b/myisam/mi_write.c
index f31e43e52ab..5624e0ac44c 100644
--- a/myisam/mi_write.c
+++ b/myisam/mi_write.c
@@ -96,27 +96,27 @@ int mi_write(MI_INFO *info, byte *record)
   {
     if (((ulonglong) 1 << i) & share->state.key_map)
     {
-      if (share->concurrent_insert)
+      if (share->concurrent_insert && ! info->bulk_insert)
       {
 	rw_wrlock(&share->key_root_lock[i]);
 	share->keyinfo[i].version++;
       }
-      if (share->keyinfo[i].flag & HA_FULLTEXT )                  /* SerG */
-      {                                                           /* SerG */
-        if (_mi_ft_add(info,i,(char*) buff,record,filepos))       /* SerG */
-        {                                                         /* SerG */
+      if (share->keyinfo[i].flag & HA_FULLTEXT )
+      {
+        if (_mi_ft_add(info,i,(char*) buff,record,filepos))
+        {
 	  if (share->concurrent_insert)
 	    rw_unlock(&share->key_root_lock[i]);
-          DBUG_PRINT("error",("Got error: %d on write",my_errno));  /* SerG */
-          goto err;                                                 /* SerG */
-        }                                                           /* SerG */
-      }                                                             /* SerG */
-      else                                                          /* SerG */
+          DBUG_PRINT("error",("Got error: %d on write",my_errno));
+          goto err;
+        }
+      }
+      else
       {
 	uint key_length=_mi_make_key(info,i,buff,record,filepos);
 	if (_mi_ck_write(info,i,buff,key_length))
 	{
-	  if (share->concurrent_insert)
+	  if (share->concurrent_insert && ! info->bulk_insert)
 	    rw_unlock(&share->key_root_lock[i]);
 	  DBUG_PRINT("error",("Got error: %d on write",my_errno));
 	  goto err;
@@ -156,7 +156,6 @@ err:
       {
 	if (share->concurrent_insert)
 	  rw_wrlock(&share->key_root_lock[i]);
-	/* The following code block is for text searching by SerG */
 	if (share->keyinfo[i].flag & HA_FULLTEXT)
         {
           if (_mi_ft_del(info,i,(char*) buff,record,filepos))
@@ -196,11 +195,29 @@ err2:
 
 	/* Write one key to btree */
 
-int _mi_ck_write(register MI_INFO *info, uint keynr, uchar *key,
+int _mi_ck_write(MI_INFO *info, uint keynr, uchar *key, uint key_length)
+{
+  DBUG_ENTER("_mi_ck_write");
+
+  if (info->bulk_insert && is_tree_inited(& info->bulk_insert[keynr]))
+  {
+    DBUG_RETURN(_mi_ck_write_tree(info, keynr, key, key_length));
+  }
+  else
+  {
+    DBUG_RETURN(_mi_ck_write_btree(info, keynr, key, key_length));
+  }
+} /* _mi_ck_write */
+
+/**********************************************************************
+ *                Normal insert code                                  *
+ **********************************************************************/
+
+int _mi_ck_write_btree(register MI_INFO *info, uint keynr, uchar *key,
 		 uint key_length)
 {
   int error;
-  DBUG_ENTER("_mi_ck_write");
+  DBUG_ENTER("_mi_ck_write_btree");
 
   if (info->s->state.key_root[keynr] == HA_OFFSET_ERROR ||
       (error=w_search(info,info->s->keyinfo+keynr,key, key_length,
@@ -208,7 +225,7 @@ int _mi_ck_write(register MI_INFO *info, uint keynr, uchar *key,
 		      (my_off_t) 0, 1)) > 0)
     error=_mi_enlarge_root(info,keynr,key);
   DBUG_RETURN(error);
-} /* _mi_ck_write */
+} /* _mi_ck_write_btree */
 
 
 	/* Make a new root with key as only pointer */
@@ -682,3 +699,98 @@ static int _mi_balance_page(register MI_INFO *info, MI_KEYDEF *keyinfo,
 err:
   DBUG_RETURN(-1);
 } /* _mi_balance_page */
+
+/**********************************************************************
+ *                Bulk insert code                                    *
+ **********************************************************************/
+
+typedef struct {
+  MI_INFO *info;
+  uint keynr;
+} bulk_insert_param;
+
+int _mi_ck_write_tree(register MI_INFO *info, uint keynr, uchar *key,
+		 uint key_length)
+{
+  int error;
+  DBUG_ENTER("_mi_ck_write_tree");
+
+  error= tree_insert(& info->bulk_insert[keynr], key,
+         key_length + info->s->rec_reflength) ? 0 : HA_ERR_OUT_OF_MEM ;
+
+  DBUG_RETURN(error);
+} /* _mi_ck_write_tree */
+
+/* typeof(_mi_keys_compare)=qsort_cmp2 */
+static int keys_compare(bulk_insert_param *param, uchar *key1, uchar *key2)
+{
+  uint not_used;
+  return _mi_key_cmp(param->info->s->keyinfo[param->keynr].seg,
+              key1, key2, USE_WHOLE_KEY, SEARCH_SAME, &not_used);
+}
+
+static int keys_free(uchar *key, TREE_FREE mode, bulk_insert_param *param)
+{
+  /* probably I can use info->lastkey here, but I'm not sure,
+     and to be safe I'd better use local lastkey.
+     Monty, feel free to comment on this */
+  uchar lastkey[MI_MAX_KEY_BUFF];
+  uint keylen;
+  MI_KEYDEF *keyinfo;
+
+  switch (mode) {
+    case free_init:
+      if (param->info->s->concurrent_insert)
+      {
+        rw_wrlock(&param->info->s->key_root_lock[param->keynr]);
+        param->info->s->keyinfo[param->keynr].version++;
+      }
+      return 0;
+    case free_free:
+      keyinfo=param->info->s->keyinfo+param->keynr;
+      keylen=_mi_keylength(keyinfo, key);
+      memcpy(lastkey, key, keylen);
+      return _mi_ck_write_btree(param->info,param->keynr,lastkey, 
+                 keylen - param->info->s->rec_reflength);
+    case free_end:
+      if (param->info->s->concurrent_insert)
+        rw_unlock(&param->info->s->key_root_lock[param->keynr]);
+      return 0;
+  }
+  return -1;
+}
+
+int _mi_init_bulk_insert(MI_INFO *info)
+{
+  MYISAM_SHARE *share=info->s;
+  MI_KEYDEF *key=share->keyinfo;
+  bulk_insert_param *params;
+  uint i;
+
+  if (info->bulk_insert)
+    return 0;
+  
+  info->bulk_insert=(TREE *)my_malloc(
+      (sizeof(TREE)+sizeof(bulk_insert_param))*share->base.keys, MYF(0));
+
+  if (!info->bulk_insert)
+    return HA_ERR_OUT_OF_MEM;
+  
+  params=(bulk_insert_param *)(info->bulk_insert+share->base.keys);
+  
+  for (i=0 ; i < share->base.keys ; i++,key++,params++)
+  {
+    params->info=info;
+    params->keynr=i;
+    if (!(key->flag & HA_NOSAME) && share->base.auto_key != i+1
+        && test(share->state.key_map & ((ulonglong) 1 << i)))
+    {
+      init_tree(& info->bulk_insert[i], 0, myisam_bulk_insert_tree_size, 0,
+          (qsort_cmp2)keys_compare, 0,
+          (tree_element_free) keys_free, (void *)params);
+    }
+    else
+     info->bulk_insert[i].root=0; 
+  }
+  return 0;
+}
diff --git a/myisam/myisamdef.h b/myisam/myisamdef.h
index 7c8a4a113f4..427ccba71ed 100644
--- a/myisam/myisamdef.h
+++ b/myisam/myisamdef.h
@@ -18,6 +18,7 @@
 
 #include "myisam.h"			/* Structs & some defines */
 #include "myisampack.h"			/* packing of keys */
+#include <my_tree.h>
 #ifdef THREAD
 #include <my_pthread.h>
 #include <thr_lock.h>
@@ -259,6 +260,7 @@ struct st_myisam_info {
   my_bool page_changed;		/* If info->buff can't be used for rnext */
   my_bool buff_used;		/* If info->buff has to be reread for rnext */
   my_bool use_packed_key;		/* For MYISAMMRG */
+  TREE   *bulk_insert;   /* accumulate indexfile changes between mi_write's */
   myf lock_wait;			/* is 0 or MY_DONT_WAIT */
   int (*read_record)(struct st_myisam_info*, my_off_t, byte*);
   LIST	open_list;
@@ -641,7 +643,9 @@ my_bool check_table_is_closed(const char *name, const char *where);
 int mi_open_datafile(MI_INFO *info, MYISAM_SHARE *share);
 int mi_open_keyfile(MYISAM_SHARE *share);
 
-/* Functions needed by mi_check */
+int _mi_init_bulk_insert(MI_INFO *info);
+
+    /* Functions needed by mi_check */
 void mi_check_print_error _VARARGS((MI_CHECK *param, const char *fmt,...));
 void mi_check_print_warning _VARARGS((MI_CHECK *param, const char *fmt,...));
 void mi_check_print_info _VARARGS((MI_CHECK *param, const char *fmt,...));
diff --git a/myisam/myisamlog.c b/myisam/myisamlog.c
index 8ff9bb0dc1a..36817ac2842 100644
--- a/myisam/myisamlog.c
+++ b/myisam/myisamlog.c
@@ -331,8 +331,8 @@ static int examine_log(my_string file_name, char **table_names)
 
   init_io_cache(&cache,file,0,READ_CACHE,start_offset,0,MYF(0));
   bzero((gptr) com_count,sizeof(com_count));
-  init_tree(&tree,0,sizeof(file_info),(qsort_cmp2) file_info_compare,1,
-	    (void(*)(void*)) file_info_free);
+  init_tree(&tree,0,0,sizeof(file_info),(qsort_cmp2) file_info_compare,1,
+	    (tree_element_free) file_info_free, NULL);
   VOID(init_key_cache(KEY_CACHE_SIZE,(uint) (10*4*(IO_SIZE+MALLOC_OVERHEAD))));
 
   files_open=0; access_time=0;
diff --git a/myisam/myisampack.c b/myisam/myisampack.c
index 90ba655e41f..3037f00250b 100644
--- a/myisam/myisampack.c
+++ b/myisam/myisampack.c
@@ -674,7 +674,7 @@ static HUFF_COUNTS *init_huff_count(MI_INFO *info,my_off_t records)
 	  (type == FIELD_NORMAL ||
 	   type == FIELD_SKIPP_ZERO))
 	count[i].max_zero_fill= count[i].field_length;
-      init_tree(&count[i].int_tree,0,-1,(qsort_cmp2) compare_tree,0,NULL);
+      init_tree(&count[i].int_tree,0,0,-1,(qsort_cmp2) compare_tree,0,NULL,NULL);
       if (records && type != FIELD_BLOB && type != FIELD_VARCHAR)
 	count[i].tree_pos=count[i].tree_buff =
 	  my_malloc(count[i].field_length > 1 ? tree_buff_length : 2,