merged

BitKeeper/etc/ignore:
  auto-union
myisam/myisamdef.h:
  Auto merged
sql/ha_berkeley.cc:
  Auto merged
sql/ha_innodb.h:
  Auto merged
sql/ha_myisam.cc:
  Auto merged
sql/handler.h:
  Auto merged
sql/item.cc:
  Auto merged
sql/item_func.cc:
  Auto merged
sql/mysql_priv.h:
  Auto merged
sql/mysqld.cc:
  Auto merged
sql/opt_range.cc:
  Auto merged
sql/slave.cc:
  Auto merged
sql/sql_acl.cc:
  Auto merged
sql/sql_base.cc:
  Auto merged
sql/sql_show.cc:
  Auto merged
sql/sql_test.cc:
  Auto merged
sql/table.cc:
  Auto merged

45 files changed, 911 insertions, 279 deletions

diff --git a/.bzrignore b/.bzrignore
index 3dc7f26cfbe..339dc8f33ee 100644
--- a/.bzrignore
+++ b/.bzrignore
@@ -590,6 +590,7 @@ sql/sql_yacc.cc
 sql/sql_yacc.h
 sql/sql_yacc.output
 sql/sql_yacc.yy.orig
+sql/udf_example.so
 sql_error.cc
 sql_prepare.cc
 stamp-h
diff --git a/heap/hp_info.c b/heap/hp_info.c
index 3122a665fac..e10d140e1f6 100644
--- a/heap/hp_info.c
+++ b/heap/hp_info.c
@@ -44,8 +44,7 @@ ulong heap_position_old(HP_INFO *info)
 /* Note that heap_info does NOT return information about the
    current position anymore;  Use heap_position instead */
 
-int heap_info(reg1 HP_INFO *info,reg2 HEAPINFO *x,
-	      int flag __attribute__((unused)))
+int heap_info(reg1 HP_INFO *info,reg2 HEAPINFO *x, int flag )
 {
   DBUG_ENTER("heap_info");
   x->records	 = info->s->records;
diff --git a/include/my_bitmap.h b/include/my_bitmap.h
index ca0037addfb..d3fcece290b 100644
--- a/include/my_bitmap.h
+++ b/include/my_bitmap.h
@@ -39,15 +39,23 @@ typedef struct st_bitmap
 #ifdef	__cplusplus
 extern "C" {
 #endif
-  extern my_bool bitmap_init(MY_BITMAP *bitmap, uint bitmap_size,
-			     my_bool thread_safe);
-  extern void bitmap_free(MY_BITMAP *bitmap);
-  extern void bitmap_set_bit(MY_BITMAP *bitmap, uint bitmap_bit);
-  extern uint bitmap_set_next(MY_BITMAP *bitmap);
-  extern void bitmap_set_all(MY_BITMAP* bitmap);
-  extern my_bool bitmap_is_set(MY_BITMAP* bitmap, uint bitmap_bit);
-  extern void bitmap_clear_all(MY_BITMAP* bitmap);
-  extern void bitmap_clear_bit(MY_BITMAP *bitmap, uint bitmap_bit);
+extern my_bool bitmap_cmp(MY_BITMAP *map1, MY_BITMAP *map2);
+extern my_bool bitmap_init(MY_BITMAP *map, uchar *buf, uint bitmap_size, my_bool thread_safe);
+extern my_bool bitmap_is_clear_all(MY_BITMAP *map);
+extern my_bool bitmap_is_prefix(MY_BITMAP *map, uint prefix_size);
+extern my_bool bitmap_is_set(MY_BITMAP *map, uint bitmap_bit);
+extern my_bool bitmap_is_set_all(MY_BITMAP *map);
+extern my_bool bitmap_is_subset(MY_BITMAP *map1, MY_BITMAP *map2);
+extern uint bitmap_set_next(MY_BITMAP *map);
+extern void bitmap_clear_all(MY_BITMAP *map);
+extern void bitmap_clear_bit(MY_BITMAP *map, uint bitmap_bit);
+extern void bitmap_free(MY_BITMAP *map);
+extern void bitmap_intersect(MY_BITMAP *map, MY_BITMAP *map2);
+extern void bitmap_set_all(MY_BITMAP *map);
+extern void bitmap_set_bit(MY_BITMAP *map, uint bitmap_bit);
+extern void bitmap_set_prefix(MY_BITMAP *map, uint prefix_size);
+extern void bitmap_subtract(MY_BITMAP *map, MY_BITMAP *map2);
+extern void bitmap_union(MY_BITMAP *map, MY_BITMAP *map2);
 #ifdef	__cplusplus
 }
 #endif
diff --git a/myisam/ft_boolean_search.c b/myisam/ft_boolean_search.c
index 2fbd6490cfd..104acf02324 100644
--- a/myisam/ft_boolean_search.c
+++ b/myisam/ft_boolean_search.c
@@ -168,7 +168,11 @@ static void _ftb_parse_query(FTB *ftb, byte **start, byte *end,
         ftbw->word[0]=w.len;
         if (param.yesno > 0) up->ythresh++;
         queue_insert(& ftb->queue, (byte *)ftbw);
+#ifdef TO_BE_REMOVED
+        /* after removing the following line,
+           ftb->with_scan handling can be simplified (no longer a bitmap) */
         ftb->with_scan|=(param.trunc & FTB_FLAG_TRUNC);
+#endif
         break;
       case 2: /* left bracket */
         ftbe=(FTB_EXPR *)alloc_root(&ftb->mem_root, sizeof(FTB_EXPR));
@@ -387,25 +391,34 @@ FT_INFO * ft_init_boolean_search(MI_INFO *info, uint keynr, byte *query,
 }
 
 
-/* returns 1 if str0 contain str1 */
+/* returns 1 if str0 ~= /\<str1\>/ */
 static int _ftb_strstr(const byte *s0, const byte *e0,
                 const byte *s1, const byte *e1,
                 CHARSET_INFO *cs)
 {
-  const byte *p;
+  const byte *p0, *p1;
+  my_bool s_after, e_before;
 
-  while (s0 < e0)
+  s_after=true_word_char(cs, s1[0]);
+  e_before=true_word_char(cs, e1[-1]);
+  p0=s0;
+
+  while (p0 < e0)
   {
-    while (s0 < e0 && cs->to_upper[(uint) (uchar) *s0++] !=
+    while (p0 < e0 && cs->to_upper[(uint) (uchar) *p0++] !=
 	   cs->to_upper[(uint) (uchar) *s1])
       /* no-op */;
-    if (s0 >= e0)
+    if (p0 >= e0)
       return 0;
-    p=s1+1;
-    while (s0 < e0 && p < e1 && cs->to_upper[(uint) (uchar) *s0] ==
-	   cs->to_upper[(uint) (uchar) *p])
-      s0++, p++;
-    if (p >= e1)
+
+    if (s_after && p0-1 > s0 && true_word_char(cs, p0[-2]))
+      continue;
+
+    p1=s1+1;
+    while (p0 < e0 && p1 < e1 && cs->to_upper[(uint) (uchar) *p0] ==
+	   cs->to_upper[(uint) (uchar) *p1])
+      p0++, p1++;
+    if (p1 == e1 && (!e_before || p0 == e0 || !true_word_char(cs, p0[0])))
       return 1;
   }
   return 0;
diff --git a/myisam/ft_parser.c b/myisam/ft_parser.c
index 14c67333734..57b379cfac0 100644
--- a/myisam/ft_parser.c
+++ b/myisam/ft_parser.c
@@ -73,15 +73,6 @@ FT_WORD * ft_linearize(TREE *wtree)
   DBUG_RETURN(wlist);
 }
 
-#define true_word_char(s,X)	(my_isalnum(s,X) || (X)=='_')
-#ifdef HYPHEN_IS_DELIM
-#define misc_word_char(X)	((X)=='\'')
-#else
-#define misc_word_char(X)	((X)=='\'' || (X)=='-')
-#endif
-#define word_char(s,X)		(true_word_char(s,X) || misc_word_char(X))
-
-
 /* returns:
  * 0 - eof
  * 1 - word found
diff --git a/myisam/ft_update.c b/myisam/ft_update.c
index cdf3b306087..8423b6898cd 100644
--- a/myisam/ft_update.c
+++ b/myisam/ft_update.c
@@ -21,13 +21,6 @@
 #include "ftdefs.h"
 #include <math.h>
 
-/**************************************************************
-   This is to make ft-code to ignore keyseg.length at all     *
-   and to index the whole VARCHAR/BLOB instead...             */
-#undef set_if_smaller
-#define set_if_smaller(A,B)                          /* no op */
-/**************************************************************/
-
 void _mi_ft_segiterator_init(MI_INFO *info, uint keynr, const byte *record,
 			     FT_SEG_ITERATOR *ftsi)
 {
@@ -88,7 +81,6 @@ uint _mi_ft_segiterator(register FT_SEG_ITERATOR *ftsi)
   {
     ftsi->len=uint2korr(ftsi->pos);
     ftsi->pos+=2;				 /* Skip VARCHAR length */
-    set_if_smaller(ftsi->len,ftsi->seg->length);
     DBUG_RETURN(1);
   }
   if (ftsi->seg->flag & HA_BLOB_PART)
@@ -96,7 +88,6 @@ uint _mi_ft_segiterator(register FT_SEG_ITERATOR *ftsi)
     ftsi->len=_mi_calc_blob_length(ftsi->seg->bit_start,ftsi->pos);
     memcpy_fixed((char*) &ftsi->pos, ftsi->pos+ftsi->seg->bit_start,
 		 sizeof(char*));
-    set_if_smaller(ftsi->len,ftsi->seg->length);
     DBUG_RETURN(1);
   }
   ftsi->len=ftsi->seg->length;
@@ -305,3 +296,53 @@ uint _ft_make_key(MI_INFO *info, uint keynr, byte *keybuf, FT_WORD *wptr,
   memcpy(buf+HA_FT_WLEN+2,wptr->pos,wptr->len);
   DBUG_RETURN(_mi_make_key(info,keynr,(uchar*) keybuf,buf,filepos));
 }
+
+/*
+  convert key value to ft2
+*/
+uint _mi_ft_convert_to_ft2(MI_INFO *info, uint keynr, uchar *key)
+{
+  my_off_t root;
+  DYNAMIC_ARRAY *da=info->ft1_to_ft2;
+  MI_KEYDEF *keyinfo=&info->s->ft2_keyinfo;
+  uchar *key_ptr=dynamic_array_ptr(da, 0), *end;
+  uint length, key_length;
+  DBUG_ENTER("_mi_ft_convert_to_ft2");
+
+  /* we'll generate one pageful at once, and insert the rest one-by-one */
+  /* calculating the length of this page ...*/
+  length=(keyinfo->block_length-2) / keyinfo->keylength;
+  set_if_smaller(length, da->elements);
+  length=length * keyinfo->keylength;
+
+  get_key_full_length_rdonly(key_length, key);
+  while (_mi_ck_delete(info, keynr, key, key_length) == 0)
+    /* nothing to do here.
+       _mi_ck_delete() will populate info->ft1_to_ft2 with deleted keys
+     */;
+
+  /* creating pageful of keys */
+  mi_putint(info->buff,length+2,0);
+  memcpy(info->buff+2, key_ptr, length);
+  info->buff_used=info->page_changed=1;           /* info->buff is used */
+  if ((root= _mi_new(info,keyinfo)) == HA_OFFSET_ERROR ||
+      _mi_write_keypage(info,keyinfo,root,info->buff))
+    DBUG_RETURN(-1);
+
+  /* inserting the rest of key values */
+  end=dynamic_array_ptr(da, da->elements);
+  for (key_ptr+=length; key_ptr < end; key_ptr+=keyinfo->keylength)
+    if(_mi_ck_real_write_btree(info, keyinfo, key_ptr, 0, &root, SEARCH_SAME))
+      DBUG_RETURN(-1);
+
+  /* now, writing the word key entry */
+  ft_intXstore(key+key_length, -da->elements);
+  _mi_dpointer(info, key+key_length+HA_FT_WLEN, root);
+
+  DBUG_RETURN(_mi_ck_real_write_btree(info,
+                                     info->s->keyinfo+keynr,
+                                     key, 0,
+                                     &info->s->state.key_root[keynr],
+                                     SEARCH_SAME));
+}
+
diff --git a/myisam/ftdefs.h b/myisam/ftdefs.h
index 88d7e79937b..c0a19262dcf 100644
--- a/myisam/ftdefs.h
+++ b/myisam/ftdefs.h
@@ -22,8 +22,9 @@
 #include <m_ctype.h>
 #include <my_tree.h>
 
-#define HYPHEN_IS_DELIM
-#define HYPHEN_IS_CONCAT     /* not used for now */
+#define true_word_char(s,X)	(my_isalnum(s,X) || (X)=='_')
+#define misc_word_char(X)	((X)=='\'')
+#define word_char(s,X)		(true_word_char(s,X) || misc_word_char(X))
 
 #define COMPILE_STOPWORDS_IN
 
diff --git a/myisam/fulltext.h b/myisam/fulltext.h
index ec267eb3e86..d8c74d4e94b 100644
--- a/myisam/fulltext.h
+++ b/myisam/fulltext.h
@@ -34,3 +34,5 @@ int  _mi_ft_cmp(MI_INFO *, uint, const byte *, const byte *);
 int  _mi_ft_add(MI_INFO *, uint, byte *, const byte *, my_off_t);
 int  _mi_ft_del(MI_INFO *, uint, byte *, const byte *, my_off_t);
 
+uint _mi_ft_convert_to_ft2(MI_INFO *, uint, uchar *);
+
diff --git a/myisam/mi_delete.c b/myisam/mi_delete.c
index 2ab5c5d0319..d8e1aef5eb6 100644
--- a/myisam/mi_delete.c
+++ b/myisam/mi_delete.c
@@ -18,6 +18,7 @@
 
 #include "fulltext.h"
 #include "rt_index.h"
+#include <assert.h>
 
 #ifdef	__WIN__
 #include <errno.h>
@@ -231,13 +232,22 @@ static int d_search(register MI_INFO *info, register MI_KEYDEF *keyinfo,
 
     get_key_full_length_rdonly(off, lastkey);
     subkeys=ft_sintXkorr(lastkey+off);
+    DBUG_ASSERT(info->ft1_to_ft2==0 || subkeys >=0);
     comp_flag=SEARCH_SAME;
     if (subkeys >= 0)
     {
       /* normal word, one-level tree structure */
-      DBUG_PRINT("info",("FT1"));
-      flag=(*keyinfo->bin_search)(info,keyinfo,anc_buff,key,USE_WHOLE_KEY,
-                                  comp_flag, &keypos, lastkey, &last_key);
+      if (info->ft1_to_ft2)
+      {
+        /* we're in ft1->ft2 conversion mode. Saving key data */
+        insert_dynamic(info->ft1_to_ft2, lastkey+off);
+      }
+      else
+      {
+        /* we need exact match only if not in ft1->ft2 conversion mode */
+        flag=(*keyinfo->bin_search)(info,keyinfo,anc_buff,key,USE_WHOLE_KEY,
+                                    comp_flag, &keypos, lastkey, &last_key);
+      }
       /* fall through to normal delete */
     }
     else
@@ -252,13 +262,11 @@ static int d_search(register MI_INFO *info, register MI_KEYDEF *keyinfo,
       if (subkeys == -1)
       {
         /* the last entry in sub-tree */
-        DBUG_PRINT("info",("FT2: the last entry"));
         _mi_dispose(info, keyinfo, root);
         /* fall through to normal delete */
       }
       else
       {
-        DBUG_PRINT("info",("FT2: going down"));
         keyinfo=&info->s->ft2_keyinfo;
         kpos-=keyinfo->keylength+nod_flag; /* we'll modify key entry 'in vivo' */
         key+=off;
diff --git a/myisam/mi_open.c b/myisam/mi_open.c
index c4b24acdb77..744bb9bb3b6 100644
--- a/myisam/mi_open.c
+++ b/myisam/mi_open.c
@@ -513,8 +513,8 @@ MI_INFO *mi_open(const char *name, int mode, uint open_flags)
 		       NullS))
     goto err;
   errpos=6;
-  
-  if (!have_rtree) 
+
+  if (!have_rtree)
     info.rtree_recursion_state= NULL;
 
   strmov(info.filename,org_name);
@@ -536,6 +536,7 @@ MI_INFO *mi_open(const char *name, int mode, uint open_flags)
   info.lock_type=F_UNLCK;
   info.quick_mode=0;
   info.bulk_insert=0;
+  info.ft1_to_ft2=0;
   info.errkey= -1;
   info.page_changed=1;
   pthread_mutex_lock(&share->intern_lock);
@@ -1112,7 +1113,7 @@ char *mi_recinfo_read(char *ptr, MI_COLUMNDEF *recinfo)
 
 /**************************************************************************
 Open data file with or without RAID
-We can't use dup() here as the data file descriptors need to have different 
+We can't use dup() here as the data file descriptors need to have different
 active seek-positions.
 
 The argument file_to_dup is here for the future if there would on some OS
diff --git a/myisam/mi_write.c b/myisam/mi_write.c
index 8e0b7e3530c..b6a7bf50dd0 100644
--- a/myisam/mi_write.c
+++ b/myisam/mi_write.c
@@ -18,6 +18,7 @@
 
 #include "fulltext.h"
 #include "rt_index.h"
+#include <assert.h>
 
 #ifdef	__WIN__
 #include <errno.h>
@@ -124,7 +125,7 @@ int mi_write(MI_INFO *info, byte *record)
       else
       {
         if (share->keyinfo[i].ck_insert(info,i,buff,
-        			_mi_make_key(info,i,buff,record,filepos)))
+			_mi_make_key(info,i,buff,record,filepos)))
         {
           if (local_lock_tree)
             rw_unlock(&share->key_root_lock[i]);
@@ -264,13 +265,32 @@ int _mi_ck_write_btree(register MI_INFO *info, uint keynr, uchar *key,
   else
     comp_flag=SEARCH_SAME;			/* Keys in rec-pos order */
 
+  error=_mi_ck_real_write_btree(info, keyinfo, key, key_length,
+                                root, comp_flag);
+  if (info->ft1_to_ft2)
+  {
+    if (!error)
+      error= _mi_ft_convert_to_ft2(info, keynr, key);
+    delete_dynamic(info->ft1_to_ft2);
+    my_free(info->ft1_to_ft2, MYF(0));
+    info->ft1_to_ft2=0;
+  }
+  DBUG_RETURN(error);
+} /* _mi_ck_write_btree */
+
+int _mi_ck_real_write_btree(MI_INFO *info, MI_KEYDEF *keyinfo,
+    uchar *key, uint key_length, my_off_t *root, uint comp_flag)
+{
+  int error;
+  DBUG_ENTER("_mi_ck_real_write_btree");
+  /* key_length parameter is used only if comp_flag is SEARCH_FIND */
   if (*root == HA_OFFSET_ERROR ||
       (error=w_search(info, keyinfo, comp_flag, key, key_length,
 		      *root, (uchar *) 0, (uchar*) 0,
 		      (my_off_t) 0, 1)) > 0)
     error=_mi_enlarge_root(info,keyinfo,key,root);
   DBUG_RETURN(error);
-} /* _mi_ck_write_btree */
+} /* _mi_ck_real_write_btree */
 
 
 	/* Make a new root with key as only pointer */
@@ -359,13 +379,11 @@ static int w_search(register MI_INFO *info, register MI_KEYDEF *keyinfo,
         keyinfo=&info->s->ft2_keyinfo;
         key+=off;
         keypos-=keyinfo->keylength; /* we'll modify key entry 'in vivo' */
-        if ((error=w_search(info, keyinfo, comp_flag, key, HA_FT_WLEN, root,
-                            (uchar *) 0, (uchar*) 0, (my_off_t) 0, 1)) > 0)
-        {
-          error=_mi_enlarge_root(info, keyinfo, key, &root);
-          _mi_dpointer(info, keypos+HA_FT_WLEN, root);
-        }
+        error=_mi_ck_real_write_btree(info, keyinfo, key, 0,
+                                      &root, comp_flag);
+        _mi_dpointer(info, keypos+HA_FT_WLEN, root);
         subkeys--; /* should there be underflow protection ? */
+        DBUG_ASSERT(subkeys < 0);
         ft_intXstore(keypos, subkeys);
         if (!error)
           error=_mi_write_keypage(info,keyinfo,page,temp_buff);
@@ -410,7 +428,6 @@ int _mi_insert(register MI_INFO *info, register MI_KEYDEF *keyinfo,
 	       uchar *key, uchar *anc_buff, uchar *key_pos, uchar *key_buff,
                uchar *father_buff, uchar *father_key_pos, my_off_t father_page,
 	       my_bool insert_last)
-
 {
   uint a_length,nod_flag;
   int t_length;
@@ -464,8 +481,56 @@ int _mi_insert(register MI_INFO *info, register MI_KEYDEF *keyinfo,
   a_length+=t_length;
   mi_putint(anc_buff,a_length,nod_flag);
   if (a_length <= keyinfo->block_length)
+  {
+    if (keyinfo->block_length - a_length < 32 &&
+        keyinfo->flag & HA_FULLTEXT && key_pos == endpos &&
+        info->s->base.key_reflength <= info->s->base.rec_reflength &&
+        info->s->options & (HA_OPTION_PACK_RECORD | HA_OPTION_COMPRESS_RECORD))
+    {
+      /*
+        Normal word. One-level tree. Page is almost full.
+        Let's consider converting.
+        We'll compare 'key' and the first key at anc_buff
+       */
+      uchar *a=key, *b=anc_buff+2+nod_flag;
+      uint alen, blen, ft2len=info->s->ft2_keyinfo.keylength;
+      /* the very first key on the page is always unpacked */
+      DBUG_ASSERT((*b & 128) == 0);
+#if HA_FT_MAXLEN >= 127
+      blen= mi_uint2korr(b); b+=2;
+#else
+      blen= *b++;
+#endif
+      get_key_length(alen,a);
+      DBUG_ASSERT(info->ft1_to_ft2==0);
+      if (alen == blen &&
+          mi_compare_text(keyinfo->seg->charset, a, alen, b, blen, 0)==0)
+      {
+        /* yup. converting */
+        info->ft1_to_ft2=(DYNAMIC_ARRAY *)
+          my_malloc(sizeof(DYNAMIC_ARRAY), MYF(MY_WME));
+        my_init_dynamic_array(info->ft1_to_ft2, ft2len, 300, 50);
+
+        /*
+          now, adding all keys from the page to dynarray
+          if the page is a leaf (if not keys will be deleted later)
+        */
+        if (!nod_flag)
+        {
+          /* let's leave the first key on the page, though, because
+             we cannot easily dispatch an empty page here */
+          b+=blen+ft2len+2;
+          for (a=anc_buff+a_length ; b < a ; b+=ft2len+2)
+            insert_dynamic(info->ft1_to_ft2, b);
+
+          /* fixing the page's length - it contains only one key now */
+          mi_putint(anc_buff,2+blen+ft2len+2,0);
+        }
+        /* the rest will be done when we're back from recursion */
+      }
+    }
     DBUG_RETURN(0);				/* There is room on page */
-
+  }
   /* Page is full */
   if (nod_flag)
     insert_last=0;
diff --git a/myisam/myisamdef.h b/myisam/myisamdef.h
index 9844bb7b36d..2c5d5eca756 100644
--- a/myisam/myisamdef.h
+++ b/myisam/myisamdef.h
@@ -222,7 +222,8 @@ struct st_myisam_info {
   MI_BLOB     *blobs;			/* Pointer to blobs */
   MI_BIT_BUFF  bit_buff;
   /* accumulate indexfile changes between write's */
-  TREE	      *bulk_insert;
+  TREE	        *bulk_insert;
+  DYNAMIC_ARRAY *ft1_to_ft2;            /* used only in ft1->ft2 conversion */
   char *filename;			/* parameter to open filename */
   uchar *buff,				/* Temp area for key */
 	*lastkey,*lastkey2;		/* Last used search key */
@@ -464,6 +465,9 @@ extern int _mi_delete_static_record(MI_INFO *info);
 extern int _mi_cmp_static_record(MI_INFO *info,const byte *record);
 extern int _mi_read_rnd_static_record(MI_INFO*, byte *,my_off_t, my_bool);
 extern int _mi_ck_write(MI_INFO *info,uint keynr,uchar *key,uint length);
+extern int _mi_ck_real_write_btree(MI_INFO *info, MI_KEYDEF *keyinfo,
+                                   uchar *key, uint key_length,
+                                   my_off_t *root, uint comp_flag);
 extern int _mi_enlarge_root(MI_INFO *info,MI_KEYDEF *keyinfo,uchar *key, my_off_t *root);
 extern int _mi_insert(MI_INFO *info,MI_KEYDEF *keyinfo,uchar *key,
 		      uchar *anc_buff,uchar *key_pos,uchar *key_buff,
diff --git a/mysql-test/r/fulltext.result b/mysql-test/r/fulltext.result
index e2d35973383..83c77949e2c 100644
--- a/mysql-test/r/fulltext.result
+++ b/mysql-test/r/fulltext.result
@@ -119,7 +119,8 @@ a	b
 MySQL has now support	for full-text search
 select * from t1 where MATCH a,b AGAINST ('"text i"' IN BOOLEAN MODE);
 a	b
-Full-text indexes	are called collections
+select * from t1 where MATCH a,b AGAINST ('"xt indexes"' IN BOOLEAN MODE);
+a	b
 select * from t1 where MATCH a AGAINST ("search" IN BOOLEAN MODE);
 a	b
 Full-text search in MySQL	implements vector space model
diff --git a/mysql-test/r/fulltext2.result b/mysql-test/r/fulltext2.result
index a35be210ece..687bc6edfa0 100644
--- a/mysql-test/r/fulltext2.result
+++ b/mysql-test/r/fulltext2.result
@@ -103,4 +103,106 @@ count(*)
 select count(*) from t1 where match a against ('aaazzz' in boolean mode);
 count(*)
 262
-DROP TABLE IF EXISTS t1;
+drop table t1;
+CREATE TABLE t1 (
+i int(10) unsigned not null auto_increment primary key,
+a varchar(255) not null,
+FULLTEXT KEY (a)
+) TYPE=MyISAM;
+select count(*) from t1 where match a against ('aaaxxx');
+count(*)
+260
+select count(*) from t1 where match a against ('aaayyy');
+count(*)
+250
+select count(*) from t1 where match a against ('aaazzz');
+count(*)
+255
+select count(*) from t1 where match a against ('aaaxxx' in boolean mode);
+count(*)
+260
+select count(*) from t1 where match a against ('aaayyy' in boolean mode);
+count(*)
+250
+select count(*) from t1 where match a against ('aaazzz' in boolean mode);
+count(*)
+255
+select count(*) from t1 where match a against ('aaaxxx aaayyy aaazzz');
+count(*)
+765
+select count(*) from t1 where match a against ('aaaxxx aaayyy aaazzz' in boolean mode);
+count(*)
+765
+select count(*) from t1 where match a against ('aaax*' in boolean mode);
+count(*)
+260
+select count(*) from t1 where match a against ('aaay*' in boolean mode);
+count(*)
+250
+select count(*) from t1 where match a against ('aaa*' in boolean mode);
+count(*)
+765
+insert t1 (a) values ('aaaxxx'),('aaayyy');
+insert t1 (a) values ('aaazzz'),('aaazzz'),('aaazzz'),('aaazzz'),('aaazzz');
+select count(*) from t1 where match a against ('aaaxxx');
+count(*)
+261
+select count(*) from t1 where match a against ('aaayyy');
+count(*)
+251
+select count(*) from t1 where match a against ('aaazzz');
+count(*)
+260
+insert t1 (a) values ('aaaxxx 000000');
+select count(*) from t1 where match a against ('000000');
+count(*)
+1
+delete from t1 where match a against ('000000');
+select count(*) from t1 where match a against ('000000');
+count(*)
+0
+select count(*) from t1 where match a against ('aaaxxx');
+count(*)
+261
+delete from t1 where match a against ('aaazzz');
+select count(*) from t1 where match a against ('aaaxxx' in boolean mode);
+count(*)
+261
+select count(*) from t1 where match a against ('aaayyy' in boolean mode);
+count(*)
+251
+select count(*) from t1 where match a against ('aaazzz' in boolean mode);
+count(*)
+0
+select count(*) from t1 where a = 'aaaxxx';
+count(*)
+261
+select count(*) from t1 where a = 'aaayyy';
+count(*)
+251
+select count(*) from t1 where a = 'aaazzz';
+count(*)
+0
+insert t1 (a) values ('aaaxxx 000000');
+select count(*) from t1 where match a against ('000000');
+count(*)
+1
+update t1 set a='aaazzz' where match a against ('000000');
+select count(*) from t1 where match a against ('aaaxxx' in boolean mode);
+count(*)
+261
+select count(*) from t1 where match a against ('aaazzz' in boolean mode);
+count(*)
+1
+update t1 set a='aaazzz' where a = 'aaaxxx';
+update t1 set a='aaaxxx' where a = 'aaayyy';
+select count(*) from t1 where match a against ('aaaxxx' in boolean mode);
+count(*)
+251
+select count(*) from t1 where match a against ('aaayyy' in boolean mode);
+count(*)
+0
+select count(*) from t1 where match a against ('aaazzz' in boolean mode);
+count(*)
+262
+drop table t1;
diff --git a/mysql-test/t/fulltext.test b/mysql-test/t/fulltext.test
index 8c6bb97edf1..5e5d64ced82 100644
--- a/mysql-test/t/fulltext.test
+++ b/mysql-test/t/fulltext.test
@@ -58,6 +58,7 @@ select * from t1 where MATCH a,b AGAINST ('"text search"  "now support"' IN BOOL
 select * from t1 where MATCH a,b AGAINST ('"text search" -"now support"' IN BOOLEAN MODE);
 select * from t1 where MATCH a,b AGAINST ('"text search" +"now support"' IN BOOLEAN MODE);
 select * from t1 where MATCH a,b AGAINST ('"text i"' IN BOOLEAN MODE);
+select * from t1 where MATCH a,b AGAINST ('"xt indexes"' IN BOOLEAN MODE);
 
 # boolean w/o index:
 
diff --git a/mysql-test/t/fulltext2.test b/mysql-test/t/fulltext2.test
index b739d60e3b3..a01ec3a59c9 100644
--- a/mysql-test/t/fulltext2.test
+++ b/mysql-test/t/fulltext2.test
@@ -94,5 +94,83 @@ select count(*) from t1 where match a against ('aaaxxx' in boolean mode);
 select count(*) from t1 where match a against ('aaayyy' in boolean mode);
 select count(*) from t1 where match a against ('aaazzz' in boolean mode);
 
-DROP TABLE IF EXISTS t1;
+drop table t1;
+
+CREATE TABLE t1 (
+  i int(10) unsigned not null auto_increment primary key,
+  a varchar(255) not null,
+  FULLTEXT KEY (a)
+) TYPE=MyISAM;
+
+# two-level entry, second-level tree with depth 2
+--disable_query_log
+let $1=260;
+while ($1)
+{
+  eval insert t1 (a) values ('aaaxxx');
+  dec $1;
+}
+let $1=255;
+while ($1)
+{
+  eval insert t1 (a) values ('aaazzz');
+  dec $1;
+}
+let $1=250;
+while ($1)
+{
+  eval insert t1 (a) values ('aaayyy');
+  dec $1;
+}
+--enable_query_log
+
+select count(*) from t1 where match a against ('aaaxxx');
+select count(*) from t1 where match a against ('aaayyy');
+select count(*) from t1 where match a against ('aaazzz');
+select count(*) from t1 where match a against ('aaaxxx' in boolean mode);
+select count(*) from t1 where match a against ('aaayyy' in boolean mode);
+select count(*) from t1 where match a against ('aaazzz' in boolean mode);
+select count(*) from t1 where match a against ('aaaxxx aaayyy aaazzz');
+select count(*) from t1 where match a against ('aaaxxx aaayyy aaazzz' in boolean mode);
+
+select count(*) from t1 where match a against ('aaax*' in boolean mode);
+select count(*) from t1 where match a against ('aaay*' in boolean mode);
+select count(*) from t1 where match a against ('aaa*' in boolean mode);
+
+# mi_write:
+
+insert t1 (a) values ('aaaxxx'),('aaayyy');
+insert t1 (a) values ('aaazzz'),('aaazzz'),('aaazzz'),('aaazzz'),('aaazzz');
+select count(*) from t1 where match a against ('aaaxxx');
+select count(*) from t1 where match a against ('aaayyy');
+select count(*) from t1 where match a against ('aaazzz');
+
+# mi_delete
+insert t1 (a) values ('aaaxxx 000000');
+select count(*) from t1 where match a against ('000000');
+delete from t1 where match a against ('000000');
+select count(*) from t1 where match a against ('000000');
+select count(*) from t1 where match a against ('aaaxxx');
+delete from t1 where match a against ('aaazzz');
+select count(*) from t1 where match a against ('aaaxxx' in boolean mode);
+select count(*) from t1 where match a against ('aaayyy' in boolean mode);
+select count(*) from t1 where match a against ('aaazzz' in boolean mode);
+# double-check without index
+select count(*) from t1 where a = 'aaaxxx';
+select count(*) from t1 where a = 'aaayyy';
+select count(*) from t1 where a = 'aaazzz';
+
+# update
+insert t1 (a) values ('aaaxxx 000000');
+select count(*) from t1 where match a against ('000000');
+update t1 set a='aaazzz' where match a against ('000000');
+select count(*) from t1 where match a against ('aaaxxx' in boolean mode);
+select count(*) from t1 where match a against ('aaazzz' in boolean mode);
+update t1 set a='aaazzz' where a = 'aaaxxx';
+update t1 set a='aaaxxx' where a = 'aaayyy';
+select count(*) from t1 where match a against ('aaaxxx' in boolean mode);
+select count(*) from t1 where match a against ('aaayyy' in boolean mode);
+select count(*) from t1 where match a against ('aaazzz' in boolean mode);
+
+drop table t1;
 
diff --git a/mysys/my_bitmap.c b/mysys/my_bitmap.c
index 8834dda98e1..70b15eaa1d8 100644
--- a/mysys/my_bitmap.c
+++ b/mysys/my_bitmap.c
@@ -27,7 +27,7 @@
 #include <assert.h>
 #include <m_string.h>
 
-inline void bitmap_lock(MY_BITMAP* map)
+inline void bitmap_lock(MY_BITMAP *map)
 {
 #ifdef THREAD
   if (map->thread_safe)
@@ -35,7 +35,7 @@ inline void bitmap_lock(MY_BITMAP* map)
 #endif
 }
 
-inline void bitmap_unlock(MY_BITMAP* map)
+inline void bitmap_unlock(MY_BITMAP *map)
 {
 #ifdef THREAD
   if (map->thread_safe)
@@ -43,9 +43,10 @@ inline void bitmap_unlock(MY_BITMAP* map)
 #endif
 }
 
-my_bool bitmap_init(MY_BITMAP *map, uint bitmap_size, my_bool thread_safe)
+my_bool bitmap_init(MY_BITMAP *map, uchar *buf, uint bitmap_size, my_bool thread_safe)
 {
-  if (!(map->bitmap=(uchar*) my_malloc((bitmap_size+7)/8,
+  if (!(map->bitmap=buf) &&
+      !(map->bitmap=(uchar*) my_malloc((bitmap_size+7)/8,
 				       MYF(MY_WME | MY_ZEROFILL))))
     return 1;
   DBUG_ASSERT(bitmap_size != ~(uint) 0);
@@ -72,6 +73,7 @@ void bitmap_free(MY_BITMAP *map)
 
 void bitmap_set_bit(MY_BITMAP *map, uint bitmap_bit)
 {
+  DBUG_ASSERT(map->bitmap);
   if (bitmap_bit < map->bitmap_size)
   {
     bitmap_lock(map);
@@ -80,7 +82,6 @@ void bitmap_set_bit(MY_BITMAP *map, uint bitmap_bit)
   }
 }
 
-
 uint bitmap_set_next(MY_BITMAP *map)
 {
   uchar *bitmap=map->bitmap;
@@ -88,6 +89,7 @@ uint bitmap_set_next(MY_BITMAP *map)
   uint bitmap_size=map->bitmap_size;
   uint i;
 
+  DBUG_ASSERT(map->bitmap);
   bitmap_lock(map);
   for (i=0; i < bitmap_size ; i++, bitmap++)
   {
@@ -110,9 +112,9 @@ uint bitmap_set_next(MY_BITMAP *map)
   return bit_found;
 }
 
-
 void bitmap_clear_bit(MY_BITMAP *map, uint bitmap_bit)
 {
+  DBUG_ASSERT(map->bitmap);
   if (bitmap_bit < map->bitmap_size)
   {
     bitmap_lock(map);
@@ -121,24 +123,184 @@ void bitmap_clear_bit(MY_BITMAP *map, uint bitmap_bit)
   }
 }
 
+void bitmap_set_prefix(MY_BITMAP *map, uint prefix_size)
+{
+  uint l, m;
+
+  DBUG_ASSERT(map->bitmap);
+  bitmap_lock(map);
+  set_if_smaller(prefix_size, map->bitmap_size);
+  if ((l=prefix_size / 8))
+    memset(map->bitmap, 0xff, l);
+  if ((m=prefix_size & 7))
+    map->bitmap[l++]= (1 << m)-1;
+  if (l < (m=(map->bitmap_size+7)/8))
+    bzero(map->bitmap+l, m-l);
+  bitmap_unlock(map);
+}
+
+void bitmap_clear_all(MY_BITMAP *map)
+{
+  bitmap_set_prefix(map, 0);
+}
+
+void bitmap_set_all(MY_BITMAP *map)
+{
+  bitmap_set_prefix(map, map->bitmap_size);
+}
 
-void bitmap_set_all(MY_BITMAP* map)
+my_bool bitmap_is_prefix(MY_BITMAP *map, uint prefix_size)
 {
+  uint l=prefix_size/8, m=prefix_size & 7, i, res=0;
+
+  DBUG_ASSERT(map->bitmap);
+  if (prefix_size > map->bitmap_size)
+    return 0;
+
   bitmap_lock(map);
-  memset(map->bitmap, 0xff, (map->bitmap_size+7)/8);
+  for (i=0; i < l; i++)
+    if (map->bitmap[i] != 0xff)
+      goto ret;
+
+  if (m && map->bitmap[i++] != (1 << m)-1)
+    goto ret;
+
+  for (m=(map->bitmap_size+7)/8; i < m; i++)
+    if (map->bitmap[i] != 0)
+      goto ret;
+
+  res=1;
+ret:
   bitmap_unlock(map);
+  return res;
+}
+
+my_bool bitmap_is_clear_all(MY_BITMAP *map)
+{
+  return bitmap_is_prefix(map, 0);
+}
+
+my_bool bitmap_is_set_all(MY_BITMAP *map)
+{
+  return bitmap_is_prefix(map, map->bitmap_size);
 }
 
-my_bool bitmap_is_set(MY_BITMAP* map, uint bitmap_bit)
+my_bool bitmap_is_set(MY_BITMAP *map, uint bitmap_bit)
 {
+  DBUG_ASSERT(map->bitmap);
   return (bitmap_bit < map->bitmap_size) ?
-    (map->bitmap[bitmap_bit / 8] & (1 << (bitmap_bit & 7))) :
-    0;
+    (map->bitmap[bitmap_bit / 8] & (1 << (bitmap_bit & 7))) : 0;
+}
+
+my_bool bitmap_is_subset(MY_BITMAP *map1, MY_BITMAP *map2)
+{
+  uint l1, l2, i, res=0;
+  uchar *m1=map1->bitmap, *m2=map2->bitmap;
+
+  DBUG_ASSERT(map1->bitmap);
+  DBUG_ASSERT(map2->bitmap);
+  bitmap_lock(map1);
+  bitmap_lock(map2);
+
+  l1=(map1->bitmap_size+7)/8;
+  l2=(map2->bitmap_size+7)/8;
+  set_if_smaller(l2, l1);
+
+  for (i=0; i < l2; i++)
+    if ((*m1++) & ~(*m2++))
+      goto ret;
+
+  for (; i < l1; i++)
+    if (*m1++)
+      goto ret;
+
+  res=1;
+ret:
+  bitmap_unlock(map2);
+  bitmap_unlock(map1);
+  return res;
+}
+
+my_bool bitmap_cmp(MY_BITMAP *map1, MY_BITMAP *map2)
+{
+  uint res;
+
+  DBUG_ASSERT(map1->bitmap);
+  DBUG_ASSERT(map2->bitmap);
+  bitmap_lock(map1);
+  bitmap_lock(map2);
+
+  res= map1->bitmap_size == map2->bitmap_size &&
+       memcmp(map1->bitmap, map2->bitmap, (map1->bitmap_size+7)/8)==0;
+
+  bitmap_unlock(map2);
+  bitmap_unlock(map1);
+  return res;
 }
 
-void bitmap_clear_all(MY_BITMAP* map)
+void bitmap_intersect(MY_BITMAP *map, MY_BITMAP *map2)
 {
+  uint l1, l2, i;
+  uchar *m=map->bitmap, *m2=map2->bitmap;
+
+  DBUG_ASSERT(map->bitmap);
+  DBUG_ASSERT(map2->bitmap);
   bitmap_lock(map);
-  bzero(map->bitmap,(map->bitmap_size+7)/8);
+  bitmap_lock(map2);
+
+  l1=(map->bitmap_size+7)/8;
+  l2=(map2->bitmap_size+7)/8;
+  set_if_smaller(l2, l1);
+
+  for (i=0; i < l2; i++)
+    *m++ &= *m2++;
+
+  if (l1 > l2)
+    bzero(m, l1-l2);
+
+  bitmap_unlock(map2);
   bitmap_unlock(map);
 }
+
+void bitmap_subtract(MY_BITMAP *map, MY_BITMAP *map2)
+{
+  uint l1, l2, i;
+  uchar *m=map->bitmap, *m2=map2->bitmap;
+
+  DBUG_ASSERT(map->bitmap);
+  DBUG_ASSERT(map2->bitmap);
+  bitmap_lock(map);
+  bitmap_lock(map2);
+
+  l1=(map->bitmap_size+7)/8;
+  l2=(map2->bitmap_size+7)/8;
+  set_if_smaller(l2, l1);
+
+  for (i=0; i < l2; i++)
+    *m++ &= ~(*m2++);
+
+  bitmap_unlock(map2);
+  bitmap_unlock(map);
+}
+
+void bitmap_union(MY_BITMAP *map, MY_BITMAP *map2)
+{
+  uint l1, l2, i;
+  uchar *m=map->bitmap, *m2=map2->bitmap;
+
+  DBUG_ASSERT(map->bitmap);
+  DBUG_ASSERT(map2->bitmap);
+  bitmap_lock(map);
+  bitmap_lock(map2);
+
+  l1=(map->bitmap_size+7)/8;
+  l2=(map2->bitmap_size+7)/8;
+  set_if_smaller(l2, l1);
+
+  for (i=0; i < l2; i++)
+    *m++ |= *m2++;
+
+  bitmap_unlock(map2);
+  bitmap_unlock(map);
+}
+
diff --git a/sql/field.cc b/sql/field.cc
index 68c9922e887..bb651835194 100644
--- a/sql/field.cc
+++ b/sql/field.cc
@@ -181,8 +181,7 @@ Field::Field(char *ptr_arg,uint32 length_arg,uchar *null_ptr_arg,
   :ptr(ptr_arg),null_ptr(null_ptr_arg),
    table(table_arg),table_name(table_arg ? table_arg->table_name : 0),
    field_name(field_name_arg),
-   query_id(0),key_start(0),part_of_key(0),part_of_sortkey(0),
-   unireg_check(unireg_check_arg),
+   query_id(0),unireg_check(unireg_check_arg),
    field_length(length_arg),null_bit(null_bit_arg),abs_offset(0)
 {
   flags=null_ptr ? 0: NOT_NULL_FLAG;
diff --git a/sql/field.h b/sql/field.h
index fe5141e9d80..eb0af881121 100644
--- a/sql/field.h
+++ b/sql/field.h
@@ -151,7 +151,9 @@ public:
       if (tmp->table->maybe_null)
 	tmp->flags&= ~NOT_NULL_FLAG;
       tmp->table= new_table;
-      tmp->key_start= tmp->part_of_key= tmp->part_of_sortkey= 0;
+      tmp->key_start.init().clear_all();
+      tmp->part_of_key.init().clear_all();
+      tmp->part_of_sortkey.init().clear_all();
       tmp->unireg_check=Field::NONE;
       tmp->flags&= (NOT_NULL_FLAG | BLOB_FLAG | UNSIGNED_FLAG |
 		    ZEROFILL_FLAG | BINARY_FLAG | ENUM_FLAG | SET_FLAG);
diff --git a/sql/ha_berkeley.cc b/sql/ha_berkeley.cc
index 1b99efeaa43..b2e1ef2fe61 100644
--- a/sql/ha_berkeley.cc
+++ b/sql/ha_berkeley.cc
@@ -843,7 +843,7 @@ int ha_berkeley::write_row(byte * record)
     ulong thd_options = table->in_use ? table->in_use->options : 0;
     for (uint retry=0 ; retry < berkeley_trans_retry ; retry++)
     {
-      key_map changed_keys = 0;
+      key_map changed_keys;
       if (using_ignore && (thd_options & OPTION_INTERNAL_SUBTRANSACTIONS))
       {
 	if ((error=txn_begin(db_env, transaction, &sub_trans, 0))) /* purecov: deadcode */
@@ -854,7 +854,7 @@ int ha_berkeley::write_row(byte * record)
 							key_buff, record),
 			    &row, key_type[primary_key])))
       {
-	changed_keys |= (key_map) 1 << primary_key;
+	changed_keys.set_bit(primary_key);
 	for (uint keynr=0 ; keynr < table->keys ; keynr++)
 	{
 	  if (keynr == primary_key)
@@ -867,7 +867,7 @@ int ha_berkeley::write_row(byte * record)
 	    last_dup_key=keynr;
 	    break;
 	  }
-	  changed_keys |= (key_map) 1 << keynr;
+	  changed_keys.set_bit(keynr);
 	}
       }
       else
@@ -1089,7 +1089,7 @@ int ha_berkeley::update_row(const byte * old_row, byte * new_row)
   sub_trans = transaction;
   for (uint retry=0 ; retry < berkeley_trans_retry ; retry++)
   {
-    key_map changed_keys = 0;
+    key_map changed_keys;
     if (using_ignore &&	(thd_options & OPTION_INTERNAL_SUBTRANSACTIONS))
     {
       if ((error=txn_begin(db_env, transaction, &sub_trans, 0))) /* purecov: deadcode */
@@ -1122,7 +1122,7 @@ int ha_berkeley::update_row(const byte * old_row, byte * new_row)
 	    }
 	    DBUG_RETURN(error);			// Fatal error /* purecov: inspected */
 	  }
-	  changed_keys |= (key_map)1 << keynr;
+	  changed_keys.set_bit(keynr);
 	  if ((error=key_file[keynr]->put(key_file[keynr], sub_trans,
 					  create_key(&key, keynr, key_buff2,
 						     new_row),
@@ -1260,7 +1260,7 @@ int ha_berkeley::delete_row(const byte * record)
     DBUG_RETURN((error)); /* purecov: inspected */
   create_key(&prim_key, primary_key, key_buff, record);
   if (hidden_primary_key)
-    keys|= (key_map) 1 << primary_key;
+    keys.set_bit(primary_key);
 
   /* Subtransactions may be used in order to retry the delete in
      case we get a DB_LOCK_DEADLOCK error. */
diff --git a/sql/ha_berkeley.h b/sql/ha_berkeley.h
index f1669e9b6c7..471145c96bf 100644
--- a/sql/ha_berkeley.h
+++ b/sql/ha_berkeley.h
@@ -107,7 +107,7 @@ class ha_berkeley: public handler
   uint extra_rec_buf_length()	 { return BDB_HIDDEN_PRIMARY_KEY_LENGTH; }
   ha_rows estimate_number_of_rows();
   bool fast_key_read()	   { return 1;}
-  key_map keys_to_use_for_scanning() { return ~(key_map) 0; }
+  const key_map keys_to_use_for_scanning() { return key_map(~0); }
   bool has_transactions()  { return 1;}
 
   int open(const char *name, int mode, uint test_if_locked);
diff --git a/sql/ha_innodb.h b/sql/ha_innodb.h
index 0c89a9d29ce..9ef47a105d6 100644
--- a/sql/ha_innodb.h
+++ b/sql/ha_innodb.h
@@ -125,7 +125,7 @@ class ha_innobase: public handler
   	uint max_key_length() const { return((MAX_KEY_LENGTH <= 3500) ?
 					  MAX_KEY_LENGTH : 3500);}
   	bool fast_key_read()	 { return 1;}
-	key_map keys_to_use_for_scanning() { return ~(key_map) 0; }
+	const key_map& keys_to_use_for_scanning() { return key_map_full; }
   	bool has_transactions()  { return 1;}
 
   	int open(const char *name, int mode, uint test_if_locked);
diff --git a/sql/ha_isam.cc b/sql/ha_isam.cc
index 3acc385d251..8025e5169c8 100644
--- a/sql/ha_isam.cc
+++ b/sql/ha_isam.cc
@@ -202,7 +202,7 @@ void ha_isam::info(uint flag)
     sortkey = info.sortkey;
     block_size=nisam_block_size;
     table->keys	   = min(table->keys,info.keys);
-    table->keys_in_use= set_bits(key_map,table->keys);
+    table->keys_in_use.set_prefix(table->keys);
     table->db_options_in_use= info.options;
     table->db_record_offset=
       (table->db_options_in_use &
diff --git a/sql/ha_myisam.cc b/sql/ha_myisam.cc
index 864ee55a85f..ea356a4f17c 100644
--- a/sql/ha_myisam.cc
+++ b/sql/ha_myisam.cc
@@ -705,20 +705,21 @@ int ha_myisam::preload_keys(THD* thd, HA_CHECK_OPT *check_opt)
 
   DBUG_ENTER("ha_myisam::preload_keys");
 
-  /* Check validity of the index references */ 
+  /* Check validity of the index references */
   if (table_list->use_index)
   {
-    key_map kmap= get_key_map_from_key_list(table, table_list->use_index);
-    if (kmap == ~(key_map) 0)
+    key_map kmap;
+    get_key_map_from_key_list(&kmap, table, table_list->use_index);
+    if (kmap.is_set_all())
     {
       errmsg= thd->net.last_error;
       error= HA_ADMIN_FAILED;
       goto err;
     }
-    if (kmap)
-      map= kmap;
+    if (!kmap.is_clear_all())
+      map= kmap.to_ulonglong();
   }
-  
+
   mi_extra(file, HA_EXTRA_PRELOAD_BUFFER_SIZE,
            (void *) &thd->variables.preload_buff_size);
 
@@ -731,16 +732,16 @@ int ha_myisam::preload_keys(THD* thd, HA_CHECK_OPT *check_opt)
     case HA_ERR_OUT_OF_MEM:
       errmsg= "Failed to allocate buffer";
       break;
-    default: 
+    default:
       char buf[ERRMSGSIZE+20];
-      my_snprintf(buf, ERRMSGSIZE, 
+      my_snprintf(buf, ERRMSGSIZE,
                   "Failed to read from index file (errno: %d)", my_errno);
       errmsg= buf;
     }
     error= HA_ADMIN_FAILED;
     goto err;
   }
-  
+
   DBUG_RETURN(HA_ADMIN_OK);
 
  err:
@@ -1022,9 +1023,9 @@ void ha_myisam::info(uint flag)
     ref_length=info.reflength;
     table->db_options_in_use    = info.options;
     block_size=myisam_block_size;
-    table->keys_in_use= (set_bits(key_map, table->keys) &
-			 (key_map) info.key_map);
-    table->keys_for_keyread= table->keys_in_use & ~table->read_only_keys;
+    table->keys_in_use.set_prefix(table->keys).intersect(info.key_map);
+    table->keys_for_keyread= table->keys_in_use;
+    table->keys_for_keyread.subtract(table->read_only_keys);
     table->db_record_offset=info.record_offset;
     if (table->key_parts)
       memcpy((char*) table->key_info[0].rec_per_key,
diff --git a/sql/ha_myisammrg.cc b/sql/ha_myisammrg.cc
index a0449e83222..42c2ba10808 100644
--- a/sql/ha_myisammrg.cc
+++ b/sql/ha_myisammrg.cc
@@ -228,7 +228,7 @@ void ha_myisammrg::info(uint flag)
 #endif
   data_file_length=info.data_file_length;
   errkey  = info.errkey;
-  table->keys_in_use= set_bits(key_map, table->keys);
+  table->keys_in_use.set_prefix(table->keys);
   table->db_options_in_use    = info.options;
   table->is_view=1;
   mean_rec_length=info.reclength;
diff --git a/sql/handler.h b/sql/handler.h
index b756d9a09fb..5fc63cf30f5 100644
--- a/sql/handler.h
+++ b/sql/handler.h
@@ -241,7 +241,7 @@ public:
   virtual double read_time(uint index, uint ranges, ha_rows rows)
  { return rows2double(ranges+rows); }
   virtual bool fast_key_read() { return 0;}
-  virtual key_map keys_to_use_for_scanning() { return 0; }
+  virtual const key_map& keys_to_use_for_scanning() { return key_map_empty; }
   virtual bool has_transactions(){ return 0;}
   virtual uint extra_rec_buf_length() { return 0; }
   virtual ha_rows estimate_number_of_rows() { return records+EXTRA_RECORDS; }
diff --git a/sql/item.cc b/sql/item.cc
index 4de4951cb51..69082fab4c2 100644
--- a/sql/item.cc
+++ b/sql/item.cc
@@ -799,11 +799,11 @@ bool Item_field::fix_fields(THD *thd, TABLE_LIST *tables, Item **ref)
 	not_found_field)
     {
       /*
-	We can't find table field in table list of current select, 
+	We can't find table field in table list of current select,
 	consequently we have to find it in outer subselect(s).
-	We can't join lists of outer & current select, because of scope 
-	of view rules. For example if both tables (outer & current) have 
-	field 'field' it is not mistake to refer to this field without 
+	We can't join lists of outer & current select, because of scope
+	of view rules. For example if both tables (outer & current) have
+	field 'field' it is not mistake to refer to this field without
 	mention of table name, but if we join tables in one list it will
 	cause error ER_NON_UNIQ_ERROR in find_field_in_tables.
       */
@@ -832,8 +832,8 @@ bool Item_field::fix_fields(THD *thd, TABLE_LIST *tables, Item **ref)
 					 0)) != not_found_field)
 	    break;
 	  if (sl->resolve_mode == SELECT_LEX::SELECT_MODE &&
-	      (refer= find_item_in_list(this, sl->item_list, &counter, 
-					 REPORT_EXCEPT_NOT_FOUND)) != 
+	      (refer= find_item_in_list(this, sl->item_list, &counter,
+					 REPORT_EXCEPT_NOT_FOUND)) !=
 	       (Item **) not_found_item)
 	    break;
 	  if (sl->master_unit()->first_select()->linkage ==
@@ -897,7 +897,7 @@ bool Item_field::fix_fields(THD *thd, TABLE_LIST *tables, Item **ref)
     TABLE *table=field->table;
     field->query_id=thd->query_id;
     table->used_fields++;
-    table->used_keys&=field->part_of_key;
+    table->used_keys.intersect(field->part_of_key);
   }
   fixed= 1;
   return 0;
@@ -906,14 +906,14 @@ bool Item_field::fix_fields(THD *thd, TABLE_LIST *tables, Item **ref)
 
 void Item::init_make_field(Send_field *tmp_field,
 			   enum enum_field_types field_type)
-{  
+{
   char *empty_name= (char*) "";
-  tmp_field->db_name=	 	empty_name;
+  tmp_field->db_name=		empty_name;
   tmp_field->org_table_name=	empty_name;
   tmp_field->org_col_name=	empty_name;
   tmp_field->table_name=	empty_name;
   tmp_field->col_name=		name;
-  tmp_field->charsetnr= 	collation.collation->number;
+  tmp_field->charsetnr=         collation.collation->number;
   tmp_field->flags=maybe_null ? 0 : NOT_NULL_FLAG;
   tmp_field->type=field_type;
   tmp_field->length=max_length;
diff --git a/sql/item_func.cc b/sql/item_func.cc
index bc7c95d8929..af9fa692f8b 100644
--- a/sql/item_func.cc
+++ b/sql/item_func.cc
@@ -2650,7 +2650,7 @@ bool Item_func_match::fix_index()
   for (keynr=0 ; keynr < table->keys ; keynr++)
   {
     if ((table->key_info[keynr].flags & HA_FULLTEXT) &&
-        (table->keys_in_use_for_query & (((key_map)1) << keynr)))
+        (table->keys_in_use_for_query.is_set(keynr)))
     {
       ft_to_key[fts]=keynr;
       ft_cnt[fts]=0;
diff --git a/sql/item_timefunc.cc b/sql/item_timefunc.cc
index 31ce2ad9cdc..9a36f8a60a6 100644
--- a/sql/item_timefunc.cc
+++ b/sql/item_timefunc.cc
@@ -57,13 +57,13 @@ static String day_names[] =
   String("Sunday",	&my_charset_latin1)
 };
 
-enum date_time_format_types 
-{ 
+enum date_time_format_types
+{
   TIME_ONLY= 0, TIME_MICROSECOND,
   DATE_ONLY, DATE_TIME, DATE_TIME_MICROSECOND
 };
 
-typedef struct date_time_format 
+struct date_time_format
 {
   const char* format_str;
   uint length;
diff --git a/sql/mysql_priv.h b/sql/mysql_priv.h
index a1919bf1a0e..05cb026ad66 100644
--- a/sql/mysql_priv.h
+++ b/sql/mysql_priv.h
@@ -30,9 +30,114 @@
 #undef write  /* remove pthread.h macro definition for EMX */
 #endif
 
-typedef ulonglong table_map;		/* Used for table bits in join */
-typedef ulong key_map;			/* Used for finding keys */
-typedef ulong key_part_map;		/* Used for finding key parts */
+template <uint default_width> class Bitmap
+{
+  MY_BITMAP map;
+  uchar buffer[(default_width+7)/8];
+public:
+  Bitmap(uint prefix_to_set=0) { init(); set_prefix(prefix_to_set); }
+  Bitmap& init()
+  {
+    bitmap_init(&map, buffer, default_width, 0);
+    return *this;
+  }
+  uint length() const { return default_width; }
+  Bitmap& operator=(const Bitmap& map2)
+  {
+    init();
+    memcpy(buffer, map2.buffer, sizeof(buffer));
+    return *this;
+  }
+  Bitmap& set_bit(uint n) { bitmap_set_bit(&map, n); return *this; }
+  Bitmap& clear_bit(uint n) { bitmap_clear_bit(&map, n); return *this; }
+  Bitmap& set_prefix(uint n) { bitmap_set_prefix(&map, n); return *this; }
+  Bitmap& set_all() { bitmap_set_all(&map); return *this;}
+  Bitmap& clear_all() { bitmap_clear_all(&map); return *this; }
+  Bitmap& intersect(Bitmap& map2) { bitmap_intersect(&map, &map2.map); return *this; }
+  Bitmap& intersect(ulonglong map2buff)
+  {
+    MY_BITMAP map2;
+    bitmap_init(&map2, (uchar *)&map2buff, sizeof(ulonglong)*8, 0);
+    bitmap_intersect(&map, &map2);
+    return *this;
+  }
+  Bitmap& subtract(Bitmap& map2) { bitmap_subtract(&map, &map2.map); return *this; }
+  Bitmap& merge(Bitmap& map2) { bitmap_union(&map, &map2.map); return *this; }
+  my_bool is_set(uint n) const { return bitmap_is_set((MY_BITMAP*)&map, n); }
+  my_bool is_prefix(uint n) const { return bitmap_is_prefix((MY_BITMAP*)&map, n); }
+  my_bool is_clear_all() const { return bitmap_is_clear_all((MY_BITMAP*)&map); }
+  my_bool is_set_all() const { return bitmap_is_set_all((MY_BITMAP*)&map); }
+  my_bool is_subset(const Bitmap& map2) const { return bitmap_is_subset((MY_BITMAP*)&map, (MY_BITMAP*)&map2.map); }
+  my_bool operator==(const Bitmap& map2) const { return bitmap_cmp((MY_BITMAP*)&map, (MY_BITMAP*)&map2.map); }
+  char *print(char *buf) const
+  {
+    char *s=buf; int i;
+    for (i=sizeof(buffer)-1; i>=0 ; i--)
+    {
+      if ((*s=_dig_vec[buffer[i] >> 4]) != '0')
+        break;
+      if ((*s=_dig_vec[buffer[i] & 15]) != '0')
+        break;
+    }
+    for (s++, i-- ; i>=0 ; i--)
+    {
+      *s++=_dig_vec[buffer[i] >> 4];
+      *s++=_dig_vec[buffer[i] & 15];
+    }
+    *s=0;
+    return buf;
+  }
+  ulonglong to_ulonglong() const
+  {
+    if (sizeof(buffer) >= sizeof(ulonglong))
+      return *(ulonglong*)buffer;
+    ulonglong x=0;
+    memcpy(&x, buffer, sizeof(buffer));
+    return x;
+  }
+};
+
+template <> class Bitmap<64>
+{
+  longlong map;
+public:
+  Bitmap(uint prefix_to_set=0) { set_prefix(prefix_to_set); }
+  Bitmap<64>& init() { return *this; }
+  uint length() const { return 64; }
+  Bitmap<64>& set_bit(uint n) { map|= ((ulonglong)1) << n; return *this; }
+  Bitmap<64>& clear_bit(uint n) { map&= ~(((ulonglong)1) << n); return *this; }
+  Bitmap<64>& set_prefix(uint n)
+  {
+    if (n >= length())
+      set_all();
+    else
+      map= (((ulonglong)1) << n)-1;
+    return *this;
+  }
+  Bitmap<64>& set_all() { map=~(ulonglong)0; return *this;}
+  Bitmap<64>& clear_all() { map=(ulonglong)0; return *this; }
+  Bitmap<64>& intersect(Bitmap<64>& map2) { map&= map2.map; return *this; }
+  Bitmap<64>& intersect(ulonglong map2) { map&= map2; return *this; }
+  Bitmap<64>& subtract(Bitmap<64>& map2) { map&= ~map2.map; return *this; }
+  Bitmap<64>& merge(Bitmap<64>& map2) { map|= map2.map; return *this; }
+  my_bool is_set(uint n) const { return test(map & (((ulonglong)1) << n)); }
+  my_bool is_prefix(uint n) const { return map == (((ulonglong)1) << n)-1; }
+  my_bool is_clear_all() const { return map == (ulonglong)0; }
+  my_bool is_set_all() const { return map == ~(ulonglong)0; }
+  my_bool is_subset(const Bitmap<64>& map2) const { return !(map & ~map2.map); }
+  my_bool operator==(const Bitmap<64>& map2) const { return map == map2.map; }
+  char *print(char *buf) const { longlong2str(map,buf,16); return buf; }
+  ulonglong to_ulonglong() const { return map; }
+};
+
+/* TODO convert all these three maps to Bitmap classes */
+typedef ulonglong table_map;          /* Used for table bits in join */
+typedef Bitmap<64> key_map;           /* Used for finding keys */
+typedef ulong key_part_map;           /* Used for finding key parts */
+
+/* useful constants */
+extern const key_map key_map_empty;
+extern const key_map key_map_full;
 
 #include "mysql_com.h"
 #include <violite.h>
@@ -634,8 +739,8 @@ enum find_item_error_report_type {REPORT_ALL_ERRORS, REPORT_EXCEPT_NOT_FOUND,
 extern const Item **not_found_item;
 Item ** find_item_in_list(Item *item, List<Item> &items, uint *counter,
 			  find_item_error_report_type report_error);
-key_map get_key_map_from_key_list(TABLE *table, 
-				  List<String> *index_list);
+void get_key_map_from_key_list(key_map *map, TABLE *table,
+                               List<String> *index_list);
 bool insert_fields(THD *thd,TABLE_LIST *tables,
 		   const char *db_name, const char *table_name,
 		   List_iterator<Item> *it);
@@ -643,7 +748,7 @@ bool setup_tables(TABLE_LIST *tables);
 int setup_wild(THD *thd, TABLE_LIST *tables, List<Item> &fields,
 	       List<Item> *sum_func_list, uint wild_num);
 int setup_fields(THD *thd, Item** ref_pointer_array, TABLE_LIST *tables,
-		 List<Item> &item, bool set_query_id, 
+		 List<Item> &item, bool set_query_id,
 		 List<Item> *sum_func_list, bool allow_sum_func);
 void unfix_item_list(List<Item> item_list);
 int setup_conds(THD *thd,TABLE_LIST *tables,COND **conds);
diff --git a/sql/mysqld.cc b/sql/mysqld.cc
index 62f2471d34f..1bfb8e8cbf1 100644
--- a/sql/mysqld.cc
+++ b/sql/mysqld.cc
@@ -2114,7 +2114,7 @@ static int init_common_variables(const char *conf_file_name, int argc,
   global_system_variables.character_set_results= default_charset_info;
   global_system_variables.character_set_client= default_charset_info;
 
-  if (use_temp_pool && bitmap_init(&temp_pool,1024,1))
+  if (use_temp_pool && bitmap_init(&temp_pool,0,1024,1))
     return 1;
   return 0;
 }
diff --git a/sql/opt_range.cc b/sql/opt_range.cc
index 24768537e3d..a8ea50beafc 100644
--- a/sql/opt_range.cc
+++ b/sql/opt_range.cc
@@ -304,7 +304,7 @@ static ha_rows check_quick_keys(PARAM *param,uint index,SEL_ARG *key_tree,
 static QUICK_SELECT *get_quick_select(PARAM *param,uint index,
 				      SEL_ARG *key_tree);
 #ifndef DBUG_OFF
-static void print_quick(QUICK_SELECT *quick,key_map needed_reg);
+static void print_quick(QUICK_SELECT *quick,const key_map& needed_reg);
 #endif
 static SEL_TREE *tree_and(PARAM *param,SEL_TREE *tree1,SEL_TREE *tree2);
 static SEL_TREE *tree_or(PARAM *param,SEL_TREE *tree1,SEL_TREE *tree2);
@@ -363,7 +363,6 @@ SQL_SELECT *make_select(TABLE *head, table_map const_tables,
 
 SQL_SELECT::SQL_SELECT() :quick(0),cond(0),free_cond(0)
 {
-  quick_keys=0; needed_reg=0;
   my_b_clear(&file);
 }
 
@@ -584,18 +583,18 @@ int SQL_SELECT::test_quick_select(key_map keys_to_use, table_map prev_tables,
   uint idx;
   double scan_time;
   DBUG_ENTER("test_quick_select");
-  DBUG_PRINT("enter",("keys_to_use: %lu  prev_tables: %lu  const_tables: %lu",
+/*  DBUG_PRINT("enter",("keys_to_use: %lu  prev_tables: %lu  const_tables: %lu",
 		      (ulong) keys_to_use, (ulong) prev_tables,
-		      (ulong) const_tables));
+		      (ulong) const_tables));*/
 
   delete quick;
   quick=0;
-  needed_reg=0; quick_keys=0;
+  needed_reg.clear_all(); quick_keys.clear_all();
   if (!cond || (specialflag & SPECIAL_SAFE_MODE) && ! force_quick_range ||
       !limit)
     DBUG_RETURN(0); /* purecov: inspected */
   if (!((basflag= head->file->table_flags()) & HA_KEYPOS_TO_RNDPOS) &&
-      keys_to_use == (uint) ~0 || !keys_to_use)
+      keys_to_use.is_set_all() || keys_to_use.is_clear_all())
     DBUG_RETURN(0);				/* Not smart database */
   records=head->file->records;
   if (!records)
@@ -611,8 +610,8 @@ int SQL_SELECT::test_quick_select(key_map keys_to_use, table_map prev_tables,
 
   DBUG_PRINT("info",("Time to scan table: %g", read_time));
 
-  keys_to_use&=head->keys_in_use_for_query;
-  if (keys_to_use)
+  keys_to_use.intersect(head->keys_in_use_for_query);
+  if (!keys_to_use.is_clear_all())
   {
     MEM_ROOT *old_root,alloc;
     SEL_TREE *tree;
@@ -645,7 +644,7 @@ int SQL_SELECT::test_quick_select(key_map keys_to_use, table_map prev_tables,
 
     for (idx=0 ; idx < head->keys ; idx++)
     {
-      if (!(keys_to_use & ((key_map) 1L << idx)))
+      if (!keys_to_use.is_set(idx))
 	continue;
       KEY *key_info= &head->key_info[idx];
       if (key_info->flags & HA_FULLTEXT)
@@ -661,7 +660,7 @@ int SQL_SELECT::test_quick_select(key_map keys_to_use, table_map prev_tables,
 	key_parts->null_bit= key_info->key_part[part].null_bit;
 	if (key_parts->field->type() == FIELD_TYPE_BLOB)
 	  key_parts->part_length+=HA_KEY_BLOB_LENGTH;
-        key_parts->image_type = 
+        key_parts->image_type =
           (key_info->flags & HA_SPATIAL) ? Field::itMBR : Field::itRAW;
       }
       param.real_keynr[param.keys++]=idx;
@@ -692,11 +691,11 @@ int SQL_SELECT::test_quick_select(key_map keys_to_use, table_map prev_tables,
 	    uint keynr= param.real_keynr[idx];
 	    if ((*key)->type == SEL_ARG::MAYBE_KEY ||
 		(*key)->maybe_flag)
-	        needed_reg|= (key_map) 1 << keynr;
+	        needed_reg.set_bit(keynr);
 
 	    found_records=check_quick_select(&param, idx, *key);
 	    if (found_records != HA_POS_ERROR && found_records > 2 &&
-		head->used_keys & ((table_map) 1 << keynr) &&
+		head->used_keys.is_set(keynr) &&
 		(head->file->index_flags(keynr) & HA_KEY_READ_ONLY))
 	    {
 	      /*
@@ -2100,7 +2099,7 @@ check_quick_select(PARAM *param,uint idx,SEL_ARG *tree)
   if (records != HA_POS_ERROR)
   {
     uint key=param->real_keynr[idx];
-    param->table->quick_keys|= (key_map) 1 << key;
+    param->table->quick_keys.set_bit(key);
     param->table->quick_rows[key]=records;
     param->table->quick_key_parts[key]=param->max_key_part+1;
   }
@@ -2841,17 +2840,18 @@ print_key(KEY_PART *key_part,const char *key,uint used_length)
   }
 }
 
-static void print_quick(QUICK_SELECT *quick,key_map needed_reg)
+static void print_quick(QUICK_SELECT *quick,const key_map& needed_reg)
 {
   QUICK_RANGE *range;
+  char buf[MAX_KEY/8+1];
   DBUG_ENTER("print_param");
   if (! _db_on_ || !quick)
     DBUG_VOID_RETURN;
 
   List_iterator<QUICK_RANGE> li(quick->ranges);
   DBUG_LOCK_FILE;
-  fprintf(DBUG_FILE,"Used quick_range on key: %d (other_keys: %lu):\n",
-	  quick->index, (ulong) needed_reg);
+  fprintf(DBUG_FILE,"Used quick_range on key: %d (other_keys: %s):\n",
+	  quick->index, needed_reg.print(buf));
   while ((range=li++))
   {
     if (!(range->flag & NO_MIN_RANGE))
diff --git a/sql/opt_range.h b/sql/opt_range.h
index 00736bfc22f..4931f6f007e 100644
--- a/sql/opt_range.h
+++ b/sql/opt_range.h
@@ -128,7 +128,7 @@ class SQL_SELECT :public Sql_alloc {
   SQL_SELECT();
   ~SQL_SELECT();
   bool check_quick(bool force_quick_range=0, ha_rows limit = HA_POS_ERROR)
-  { return test_quick_select(~0L,0,limit, force_quick_range) < 0; }
+  { return test_quick_select(key_map(~0),0,limit, force_quick_range) < 0; }
   inline bool skipp_record() { return cond ? cond->val_int() == 0 : 0; }
   int test_quick_select(key_map keys,table_map prev_tables,ha_rows limit,
 			bool force_quick_range=0);
diff --git a/sql/opt_sum.cc b/sql/opt_sum.cc
index 34cce98d087..932aceebdbb 100644
--- a/sql/opt_sum.cc
+++ b/sql/opt_sum.cc
@@ -683,7 +683,7 @@ static bool find_key_for_maxmin(bool max_fl, TABLE_REF *ref,
             The following test is false when the key in the key tree is
             converted (for example to upper case)
           */
-          if (field->part_of_key & ((key_map) 1 << idx))
+          if (field->part_of_key.is_set(idx))
           {
             table->key_read= 1;
             table->file->extra(HA_EXTRA_KEYREAD);
@@ -696,7 +696,7 @@ static bool find_key_for_maxmin(bool max_fl, TABLE_REF *ref,
   return 0;
 }
 
-        
+
 /*
   Check whether found key is in range specified by conditions
 
@@ -707,7 +707,7 @@ static bool find_key_for_maxmin(bool max_fl, TABLE_REF *ref,
     field       in:     Field used the MIN/MAX expression
     cond        in:     WHERE condition
     range_fl    in:     Says whether there is a condition to to be checked
-    prefix_len  in:     Length of the constant part of the key 
+    prefix_len  in:     Length of the constant part of the key
 
   RETURN
     0        ok
diff --git a/sql/slave.cc b/sql/slave.cc
index 3e98386bbb1..2aea1056ac8 100644
--- a/sql/slave.cc
+++ b/sql/slave.cc
@@ -330,7 +330,7 @@ err:
 void init_slave_skip_errors(const char* arg)
 {
   const char *p;
-  if (bitmap_init(&slave_error_mask,MAX_SLAVE_ERROR,0))
+  if (bitmap_init(&slave_error_mask,0,MAX_SLAVE_ERROR,0))
   {
     fprintf(stderr, "Badly out of memory, please check your system status\n");
     exit(1);
diff --git a/sql/sql_acl.cc b/sql/sql_acl.cc
index 179da6096de..a47a38f2376 100644
--- a/sql/sql_acl.cc
+++ b/sql/sql_acl.cc
@@ -3545,8 +3545,16 @@ int mysql_revoke_all(THD *thd,  List <LEX_USER> &list)
   VOID(pthread_mutex_unlock(&acl_cache->lock));
   rw_unlock(&LOCK_grant);
   close_thread_tables(thd);
+
+  /* XXX this should not be necessary. The error message is already printed
+     by replace_xxx_table. my_error() should be use above instead of
+     sql_print_error(), and print ER_NONEXISTING_GRANT - as other grant
+     commands do */
+  /* when this code is deleted, the error slot (error 1268) can be reused,
+     as this error code was not present in any MySQL release */
   if (result)
     my_error(ER_REVOKE_GRANTS, MYF(0));
+
   DBUG_RETURN(result);
 }
 
diff --git a/sql/sql_base.cc b/sql/sql_base.cc
index a926c6e66fe..b151400db68 100644
--- a/sql/sql_base.cc
+++ b/sql/sql_base.cc
@@ -1675,7 +1675,7 @@ Field *find_field_in_table(THD *thd,TABLE *table,const char *name,uint length,
 	goto found;
     }
   }
-  if (allow_rowid && 
+  if (allow_rowid &&
       !my_strcasecmp(system_charset_info, name, "_rowid") &&
       (field=table->rowid_field))
     goto found;
@@ -1688,7 +1688,7 @@ Field *find_field_in_table(THD *thd,TABLE *table,const char *name,uint length,
     {
       field->query_id=thd->query_id;
       table->used_fields++;
-      table->used_keys&= field->part_of_key;
+      table->used_keys.intersect(field->part_of_key);
     }
     else
       thd->dupp_field=field;
@@ -1717,7 +1717,7 @@ Field *find_field_in_table(THD *thd,TABLE *table,const char *name,uint length,
   RETURN VALUES
     0			Field is not found or field is not unique- error
 			message is reported
-    not_found_field	Function was called with report_error == FALSE and 
+    not_found_field	Function was called with report_error == FALSE and
 			field was not found. no error message reported.
     found field
 */
@@ -2041,21 +2041,21 @@ bool setup_tables(TABLE_LIST *tables)
     table->used_keys= table->keys_for_keyread;
     if (table_list->use_index)
     {
-      key_map map= get_key_map_from_key_list(table,
-					     table_list->use_index);
-      if (map == ~(key_map) 0)
+      key_map map;
+      get_key_map_from_key_list(&map, table, table_list->use_index);
+      if (map.is_set_all())
 	DBUG_RETURN(1);
       table->keys_in_use_for_query=map;
     }
     if (table_list->ignore_index)
     {
-      key_map map= get_key_map_from_key_list(table,
-					     table_list->ignore_index);
-      if (map == ~(key_map) 0)
+      key_map map;
+      get_key_map_from_key_list(&map, table, table_list->ignore_index);
+      if (map.is_set_all())
 	DBUG_RETURN(1);
-      table->keys_in_use_for_query &= ~map;
+      table->keys_in_use_for_query.subtract(map);
     }
-    table->used_keys &= table->keys_in_use_for_query;
+    table->used_keys.intersect(table->keys_in_use_for_query);
     if (table_list->shared  || table->clear_query_id)
     {
       table->clear_query_id= 0;
@@ -2073,24 +2073,26 @@ bool setup_tables(TABLE_LIST *tables)
 }
 
 
-key_map get_key_map_from_key_list(TABLE *table, 
-				  List<String> *index_list)
+void get_key_map_from_key_list(key_map *map, TABLE *table,
+                               List<String> *index_list)
 {
-  key_map map=0;
   List_iterator_fast<String> it(*index_list);
   String *name;
   uint pos;
+
+  map->clear_all();
   while ((name=it++))
   {
     if ((pos=find_type(name->c_ptr(), &table->keynames, 1+2)) <= 0)
     {
       my_error(ER_KEY_COLUMN_DOES_NOT_EXITS, MYF(0), name->c_ptr(),
 	       table->real_name);
-      return (~ (key_map) 0);
+      map->set_all();
+      return;
     }
-    map|= ((key_map) 1) << (pos-1);
+    map->set_bit(pos-1);
   }
-  return map;
+  return;
 }
 
 /****************************************************************************
@@ -2135,7 +2137,7 @@ insert_fields(THD *thd,TABLE_LIST *tables, const char *db_name,
 	if (field->query_id == thd->query_id)
 	  thd->dupp_field=field;
 	field->query_id=thd->query_id;
-	table->used_keys&= field->part_of_key;
+	table->used_keys.intersect(field->part_of_key);
       }
       /* All fields are used */
       table->used_fields=table->fields;
@@ -2226,8 +2228,8 @@ int setup_conds(THD *thd,TABLE_LIST *tables,COND **conds)
 	    /* Mark field used for table cache */
 	    t1->field[i]->query_id=t2->field[j]->query_id=thd->query_id;
 	    cond_and->list.push_back(tmp);
-	    t1->used_keys&= t1->field[i]->part_of_key;
-	    t2->used_keys&= t2->field[j]->part_of_key;
+	    t1->used_keys.intersect(t1->field[i]->part_of_key);
+	    t2->used_keys.intersect(t2->field[j]->part_of_key);
 	    break;
 	  }
 	}
diff --git a/sql/sql_delete.cc b/sql/sql_delete.cc
index 48ef5b4b74c..bd76cbd5f36 100644
--- a/sql/sql_delete.cc
+++ b/sql/sql_delete.cc
@@ -85,7 +85,8 @@ int mysql_delete(THD *thd, TABLE_LIST *table_list, COND *conds, ORDER *order,
     /* Handler didn't support fast delete; Delete rows one by one */
   }
 
-  table->used_keys=table->quick_keys=0;		// Can't use 'only index'
+  table->used_keys.clear_all();
+  table->quick_keys.clear_all();		// Can't use 'only index'
   select=make_select(table,0,0,conds,&error);
   if (error)
     DBUG_RETURN(-1);
@@ -98,7 +99,7 @@ int mysql_delete(THD *thd, TABLE_LIST *table_list, COND *conds, ORDER *order,
   }
 
   /* If running in safe sql mode, don't allow updates without keys */
-  if (!table->quick_keys)
+  if (table->quick_keys.is_clear_all())
   {
     thd->lex.select_lex.options|=QUERY_NO_INDEX_USED;
     if (safe_update && !using_limit)
@@ -292,7 +293,7 @@ multi_delete::initialize_tables(JOIN *join)
       walk=walk->next;
       /* Don't use KEYREAD optimization on this table */
       tbl->no_keyread=1;
-      tbl->used_keys= 0;
+      tbl->used_keys.clear_all();
       if (tbl->file->has_transactions())
 	log_delayed= transactional_tables= 1;
       else if (tbl->tmp_table != NO_TMP_TABLE)
diff --git a/sql/sql_select.cc b/sql/sql_select.cc
index 4bab97d4a46..5bd494c723d 100644
--- a/sql/sql_select.cc
+++ b/sql/sql_select.cc
@@ -35,6 +35,9 @@ const char *join_type_str[]={ "UNKNOWN","system","const","eq_ref","ref",
 			      "ref_or_null","unique_subquery","index_subquery"
 };
 
+const key_map key_map_empty(0);
+const key_map key_map_full(~0);
+
 static void optimize_keyuse(JOIN *join, DYNAMIC_ARRAY *keyuse_array);
 static bool make_join_statistics(JOIN *join,TABLE_LIST *tables,COND *conds,
 				 DYNAMIC_ARRAY *keyuse);
@@ -114,7 +117,7 @@ static int join_read_next_same_or_null(READ_RECORD *info);
 static COND *make_cond_for_table(COND *cond,table_map table,
 				 table_map used_table);
 static Item* part_of_refkey(TABLE *form,Field *field);
-static uint find_shortest_key(TABLE *table, key_map usable_keys);
+static uint find_shortest_key(TABLE *table, const key_map& usable_keys);
 static bool test_if_skip_sort_order(JOIN_TAB *tab,ORDER *order,
 				    ha_rows select_limit, bool no_changes);
 static int create_sort_index(THD *thd, JOIN *join, ORDER *order,
@@ -831,7 +834,7 @@ JOIN::optimize()
 								   conds,
 								   1)));
     }
-	       
+
   }
   /*
     Need to tell Innobase that to play it safe, it should fetch all
@@ -1558,7 +1561,7 @@ err:
     JOIN *curr_join= (join->need_tmp&&join->tmp_join?
 		      (join->tmp_join->error=join->error,join->tmp_join):
 		      join);
-    
+
     thd->proc_info="end";
     err= join->cleanup();
     if (thd->net.report_error)
@@ -1575,7 +1578,7 @@ err:
 *****************************************************************************/
 
 static ha_rows get_quick_record_count(SQL_SELECT *select,TABLE *table,
-				      key_map keys,ha_rows limit)
+				      const key_map& keys,ha_rows limit)
 {
   int error;
   DBUG_ENTER("get_quick_record_count");
@@ -1637,9 +1640,13 @@ make_join_statistics(JOIN *join,TABLE_LIST *tables,COND *conds,
   {
     TABLE *table;
     stat_vector[i]=s;
+    s->keys.init();
+    s->const_keys.init();
+    s->checked_keys.init();
+    s->needed_reg.init();
     table_vector[i]=s->table=table=tables->table;
     table->file->info(HA_STATUS_VARIABLE | HA_STATUS_NO_LOCK);// record count
-    table->quick_keys=0;
+    table->quick_keys.clear_all();
     table->reginfo.join_tab=s;
     table->reginfo.not_exists_optimize=0;
     bzero((char*) table->const_key_parts, sizeof(key_part_map)*table->keys);
@@ -1785,24 +1792,25 @@ make_join_statistics(JOIN *join,TABLE_LIST *tables,COND *conds,
 	{
 	  start_keyuse=keyuse;
 	  key=keyuse->key;
-	  s->keys|= (key_map) 1 << key;		// QQ: remove this ?
+	  s->keys.set_bit(key);               // QQ: remove this ?
 
-	  refs=const_ref=0;
-	  eq_part=0;
+	  refs=0;
+          const_ref.clear_all();
+	  eq_part.clear_all();
 	  do
 	  {
 	    if (keyuse->val->type() != Item::NULL_ITEM && !keyuse->optimize)
 	    {
 	      if (!((~found_const_table_map) & keyuse->used_tables))
-		const_ref|= (key_map) 1 << keyuse->keypart;
+		const_ref.set_bit(keyuse->keypart);
 	      else
 		refs|=keyuse->used_tables;
-	      eq_part|= (key_map) 1 << keyuse->keypart;
+	      eq_part.set_bit(keyuse->keypart);
 	    }
 	    keyuse++;
 	  } while (keyuse->table == table && keyuse->key == key);
 
-	  if (eq_part == PREV_BITS(uint,table->key_info[key].key_parts) &&
+	  if (eq_part.is_prefix(table->key_info[key].key_parts) &&
 	      (table->key_info[key].flags & HA_NOSAME) &&
               !table->fulltext_searched)
 	  {
@@ -1858,7 +1866,7 @@ make_join_statistics(JOIN *join,TABLE_LIST *tables,COND *conds,
     if (s->worst_seeks < 2.0)			// Fix for small tables
       s->worst_seeks=2.0;
 
-    if (s->const_keys)
+    if (! s->const_keys.is_clear_all())
     {
       ha_rows records;
       SQL_SELECT *select;
@@ -2095,9 +2103,10 @@ add_key_field(KEY_FIELD **key_fields,uint and_level,
     else
     {
       JOIN_TAB *stat=field->table->reginfo.join_tab;
-      key_map possible_keys= (field->key_start &
-			      field->table->keys_in_use_for_query);
-      stat[0].keys|= possible_keys;		// Add possible keys
+      key_map possible_keys;
+      possible_keys=field->key_start;
+      possible_keys.intersect(field->table->keys_in_use_for_query);
+      stat[0].keys.merge(possible_keys);             // Add possible keys
 
       /*
 	Save the following cases:
@@ -2116,7 +2125,7 @@ add_key_field(KEY_FIELD **key_fields,uint and_level,
       for (uint i=0; i<num_values; i++)
         is_const&= (*value)->const_item();
       if (is_const)
-        stat[0].const_keys |= possible_keys;
+        stat[0].const_keys.merge(possible_keys);
       /*
 	We can't always use indexes when comparing a string index to a
 	number. cmp_type() is checked to allow compare of dates to numbers.
@@ -2247,14 +2256,13 @@ add_key_fields(JOIN_TAB *stat,KEY_FIELD **key_fields,uint *and_level,
 */
 
 static uint
-max_part_bit(key_map bits)
+max_part_bit(key_part_map bits)
 {
   uint found;
   for (found=0; bits & 1 ; found++,bits>>=1) ;
   return found;
 }
 
-
 static void
 add_key_part(DYNAMIC_ARRAY *keyuse_array,KEY_FIELD *key_field)
 {
@@ -2266,7 +2274,7 @@ add_key_part(DYNAMIC_ARRAY *keyuse_array,KEY_FIELD *key_field)
   {
     for (uint key=0 ; key < form->keys ; key++)
     {
-      if (!(form->keys_in_use_for_query & (((key_map) 1) << key)))
+      if (!(form->keys_in_use_for_query.is_set(key)))
 	continue;
       if (form->key_info[key].flags & HA_FULLTEXT)
 	continue;    // ToDo: ft-keys in non-ft queries.   SerG
@@ -2457,7 +2465,7 @@ update_ref_and_keys(THD *thd, DYNAMIC_ARRAY *keyuse,JOIN_TAB *join_tab,
       /* Save ptr to first use */
       if (!use->table->reginfo.join_tab->keyuse)
 	use->table->reginfo.join_tab->keyuse=save_pos;
-      use->table->reginfo.join_tab->checked_keys|= (key_map) 1 << use->key;
+      use->table->reginfo.join_tab->checked_keys.set_bit(use->key);
       save_pos++;
     }
     i=(uint) (save_pos-(KEYUSE*) keyuse->buffer);
@@ -2598,7 +2606,7 @@ find_best(JOIN *join,table_map rest_tables,uint idx,double record_count,
 	rec= s->records/MATCHING_ROWS_IN_OTHER_TABLE;  // Assumed records/key
 	for (keyuse=s->keyuse ; keyuse->table == table ;)
 	{
-	  key_map found_part=0;
+	  key_part_map found_part=0;
 	  table_map found_ref=0;
 	  uint key=keyuse->key;
 	  KEY *keyinfo=table->key_info+key;
@@ -2667,7 +2675,7 @@ find_best(JOIN *join,table_map rest_tables,uint idx,double record_count,
 	    {
 	      if (!found_ref)
 	      {					// We found a const key
-		if (table->quick_keys & ((key_map) 1 << key))
+		if (table->quick_keys.is_set(key))
 		  records= (double) table->quick_rows[key];
 		else
 		{
@@ -2691,7 +2699,7 @@ find_best(JOIN *join,table_map rest_tables,uint idx,double record_count,
 	      /* Limit the number of matched rows */
 	      tmp= records;
 	      set_if_smaller(tmp, (double) thd->variables.max_seeks_for_key);
-	      if (table->used_keys & ((key_map) 1 << key))
+	      if (table->used_keys.is_set(key))
 	      {
 		/* we can use only index tree */
 		uint keys_per_block= table->file->block_size/2/
@@ -2718,7 +2726,7 @@ find_best(JOIN *join,table_map rest_tables,uint idx,double record_count,
 		Check if quick_range could determinate how many rows we
 		will match
 	      */
-	      if (table->quick_keys & ((key_map) 1 << key) &&
+	      if (table->quick_keys.is_set(key) &&
 		  table->quick_key_parts[key] <= max_key_part)
 		tmp=records= (double) table->quick_rows[key];
 	      else
@@ -2770,7 +2778,7 @@ find_best(JOIN *join,table_map rest_tables,uint idx,double record_count,
 	      }
 	      /* Limit the number of matched rows */
 	      set_if_smaller(tmp, (double) thd->variables.max_seeks_for_key);
-	      if (table->used_keys & ((key_map) 1 << key))
+	      if (table->used_keys.is_set(key))
 	      {
 		/* we can use only index tree */
 		uint keys_per_block= table->file->block_size/2/
@@ -2809,7 +2817,7 @@ find_best(JOIN *join,table_map rest_tables,uint idx,double record_count,
 	  !(s->quick && best_key && s->quick->index == best_key->key &&
 	    best_max_key_part >= s->table->quick_key_parts[best_key->key]) &&
 	  !((s->table->file->table_flags() & HA_TABLE_SCAN_ON_INDEX) &&
-	    s->table->used_keys && best_key) &&
+	    ! s->table->used_keys.is_clear_all() && best_key) &&
 	  !(s->table->force_index && best_key))
       {						// Check full join
         ha_rows rnd_records= s->found_records;
@@ -3023,7 +3031,7 @@ get_best_combination(JOIN *join)
 
     if (j->type == JT_SYSTEM)
       continue;
-    if (!j->keys || !(keyuse= join->best_positions[tablenr].key))
+    if (j->keys.is_clear_all() || !(keyuse= join->best_positions[tablenr].key))
     {
       j->type=JT_ALL;
       if (tablenr != join->const_tables)
@@ -3254,7 +3262,7 @@ make_simple_join(JOIN *join,TABLE *tmp_table)
   join_tab->select_cond=0;
   join_tab->quick=0;
   join_tab->type= JT_ALL;			/* Map through all records */
-  join_tab->keys= (uint) ~0;			/* test everything in quick */
+  join_tab->keys.init().set_all();			/* test everything in quick */
   join_tab->info=0;
   join_tab->on_expr=0;
   join_tab->ref.key = -1;
@@ -3336,13 +3344,13 @@ make_join_select(JOIN *join,SQL_SELECT *select,COND *cond)
 	{
 	  /* Use quick key read if it's a constant and it's not used
 	     with key reading */
-	  if (tab->needed_reg == 0 && tab->type != JT_EQ_REF
+	  if (tab->needed_reg.is_clear_all() && tab->type != JT_EQ_REF
 	      && tab->type != JT_FT && (tab->type != JT_REF ||
 	       (uint) tab->ref.key == tab->quick->index))
 	  {
 	    sel->quick=tab->quick;		// Use value from get_quick_...
-	    sel->quick_keys=0;
-	    sel->needed_reg=0;
+	    sel->quick_keys.clear_all();
+	    sel->needed_reg.clear_all();
 	  }
 	  else
 	  {
@@ -3353,12 +3361,13 @@ make_join_select(JOIN *join,SQL_SELECT *select,COND *cond)
 	uint ref_key=(uint) sel->head->reginfo.join_tab->ref.key+1;
 	if (i == join->const_tables && ref_key)
 	{
-	  if (tab->const_keys && tab->table->reginfo.impossible_range)
+	  if (!tab->const_keys.is_clear_all() &&
+              tab->table->reginfo.impossible_range)
 	    DBUG_RETURN(1);
 	}
 	else if (tab->type == JT_ALL && ! use_quick_range)
 	{
-	  if (tab->const_keys &&
+	  if (!tab->const_keys.is_clear_all() &&
 	      tab->table->reginfo.impossible_range)
 	    DBUG_RETURN(1);				// Impossible range
 	  /*
@@ -3368,9 +3377,9 @@ make_join_select(JOIN *join,SQL_SELECT *select,COND *cond)
 	    the index if we are using limit and this is the first table
 	  */
 
-	  if ((tab->keys & ~ tab->const_keys && i > 0) ||
-	      (tab->const_keys && i == join->const_tables &&
-	       join->unit->select_limit_cnt < 
+	  if ((!tab->keys.is_subset(tab->const_keys) && i > 0) ||
+	      (!tab->const_keys.is_clear_all() && i == join->const_tables &&
+	       join->unit->select_limit_cnt <
 	       join->best_positions[i].records_read &&
 	       !(join->select_options & OPTION_FOUND_ROWS)))
 	  {
@@ -3408,13 +3417,15 @@ make_join_select(JOIN *join,SQL_SELECT *select,COND *cond)
 	  else
 	  {
 	    sel->needed_reg=tab->needed_reg;
-	    sel->quick_keys=0;
+	    sel->quick_keys.clear_all();
 	  }
-	  if ((sel->quick_keys | sel->needed_reg) & ~tab->checked_keys)
+	  if (!sel->quick_keys.is_subset(tab->checked_keys) ||
+              !sel->needed_reg.is_subset(tab->checked_keys))
 	  {
-	    tab->keys=sel->quick_keys | sel->needed_reg;
-	    tab->use_quick= (sel->needed_reg &&
-			     (!select->quick_keys ||
+	    tab->keys=sel->quick_keys;
+            tab->keys.merge(sel->needed_reg);
+	    tab->use_quick= (!sel->needed_reg.is_clear_all() &&
+			     (select->quick_keys.is_clear_all() ||
 			      (select->quick &&
 			       (select->quick->records >= 100L)))) ?
 	      2 : 1;
@@ -3479,7 +3490,7 @@ make_join_readinfo(JOIN *join, uint options)
       table->file->index_init(tab->ref.key);
       tab->read_first_record= join_read_key;
       tab->read_record.read_record= join_no_more_records;
-      if (table->used_keys & ((key_map) 1 << tab->ref.key) &&
+      if (table->used_keys.is_set(tab->ref.key) &&
 	  !table->no_keyread)
       {
 	table->key_read=1;
@@ -3497,7 +3508,7 @@ make_join_readinfo(JOIN *join, uint options)
       delete tab->quick;
       tab->quick=0;
       table->file->index_init(tab->ref.key);
-      if (table->used_keys & ((key_map) 1 << tab->ref.key) &&
+      if (table->used_keys.is_set(tab->ref.key) &&
 	  !table->no_keyread)
       {
 	table->key_read=1;
@@ -3572,12 +3583,12 @@ make_join_readinfo(JOIN *join, uint options)
 	if (!table->no_keyread)
 	{
 	  if (tab->select && tab->select->quick &&
-	      table->used_keys & ((key_map) 1 << tab->select->quick->index))
+	      table->used_keys.is_set(tab->select->quick->index))
 	  {
 	    table->key_read=1;
 	    table->file->extra(HA_EXTRA_KEYREAD);
 	  }
-	  else if (table->used_keys && ! (tab->select && tab->select->quick))
+	  else if (!table->used_keys.is_clear_all() && ! (tab->select && tab->select->quick))
 	  {					// Only read index tree
 	    tab->index=find_shortest_key(table, table->used_keys);
 	    tab->table->file->index_init(tab->index);
@@ -3923,7 +3934,7 @@ return_zero_rows(JOIN *join, select_result *result,TABLE_LIST *tables,
   DBUG_ENTER("return_zero_rows");
 
   if (select_options & SELECT_DESCRIBE)
-  {	
+  {
     select_describe(join, false, false, false, info);
     DBUG_RETURN(0);
   }
@@ -4653,6 +4664,12 @@ create_tmp_table(THD *thd,TMP_TABLE_PARAM *param,List<Item> &fields,
   table->db_low_byte_first=1;			// True for HEAP and MyISAM
   table->temp_pool_slot = temp_pool_slot;
   table->copy_blobs= 1;
+  table->keys_for_keyread.init();
+  table->keys_in_use.init();
+  table->read_only_keys.init();
+  table->quick_keys.init();
+  table->used_keys.init();
+  table->keys_in_use_for_query.init();
 
   /* Calculate which type of fields we will store in the temporary table */
 
@@ -5848,7 +5865,7 @@ join_read_first(JOIN_TAB *tab)
 {
   int error;
   TABLE *table=tab->table;
-  if (!table->key_read && (table->used_keys & ((key_map) 1 << tab->index)) &&
+  if (!table->key_read && table->used_keys.is_set(tab->index) &&
       !table->no_keyread)
   {
     table->key_read=1;
@@ -5885,7 +5902,7 @@ join_read_last(JOIN_TAB *tab)
 {
   TABLE *table=tab->table;
   int error;
-  if (!table->key_read && (table->used_keys & ((key_map) 1 << tab->index)) &&
+  if (!table->key_read && table->used_keys.is_set(tab->index) &&
       !table->no_keyread)
   {
     table->key_read=1;
@@ -6583,18 +6600,21 @@ static int test_if_order_by_key(ORDER *order, TABLE *table, uint idx,
   return reverse;
 }
 
-static uint find_shortest_key(TABLE *table, key_map usable_keys)
+static uint find_shortest_key(TABLE *table, const key_map& usable_keys)
 {
   uint min_length= (uint) ~0;
   uint best= MAX_KEY;
-  for (uint nr=0; usable_keys ; usable_keys>>=1, nr++)
+  if (!usable_keys.is_clear_all())
   {
-    if (usable_keys & 1)
+    for (uint nr=0; nr < usable_keys.length() ; nr++)
     {
-      if (table->key_info[nr].key_length < min_length)
+      if (usable_keys.is_set(nr))
       {
-	min_length=table->key_info[nr].key_length;
-	best=nr;
+        if (table->key_info[nr].key_length < min_length)
+        {
+          min_length=table->key_info[nr].key_length;
+          best=nr;
+        }
       }
     }
   }
@@ -6640,7 +6660,7 @@ is_subkey(KEY_PART_INFO *key_part, KEY_PART_INFO *ref_key_part,
 
 static uint
 test_if_subkey(ORDER *order, TABLE *table, uint ref, uint ref_key_parts,
-	       key_map usable_keys)
+	       const key_map& usable_keys)
 {
   uint nr;
   uint min_length= (uint) ~0;
@@ -6648,10 +6668,10 @@ test_if_subkey(ORDER *order, TABLE *table, uint ref, uint ref_key_parts,
   uint not_used;
   KEY_PART_INFO *ref_key_part= table->key_info[ref].key_part;
   KEY_PART_INFO *ref_key_part_end= ref_key_part + ref_key_parts;
-  
-  for (nr= 0; usable_keys; usable_keys>>= 1, nr++)
+
+  for (nr= 0; nr < usable_keys.length(); nr++)
   {
-    if ((usable_keys & 1) &&
+    if (usable_keys.is_set(nr) &&
 	table->key_info[nr].key_length < min_length &&
 	table->key_info[nr].key_parts >= ref_key_parts &&
 	is_subkey(table->key_info[nr].key_part, ref_key_part,
@@ -6689,16 +6709,17 @@ test_if_skip_sort_order(JOIN_TAB *tab,ORDER *order,ha_rows select_limit,
   LINT_INIT(ref_key_parts);
 
   /* Check which keys can be used to resolve ORDER BY */
-  usable_keys= ~(key_map) 0;
+  usable_keys.set_all();
   for (ORDER *tmp_order=order; tmp_order ; tmp_order=tmp_order->next)
   {
     if ((*tmp_order->item)->type() != Item::FIELD_ITEM)
     {
-      usable_keys=0;
+      usable_keys.clear_all();
       break;
     }
-    if (!(usable_keys&= (((Item_field*) (*tmp_order->item))->field->
-			 part_of_sortkey)))
+    usable_keys.intersect(
+        ((Item_field*) (*tmp_order->item))->field->part_of_sortkey);
+    if (usable_keys.is_clear_all())
       break;					// No usable keys
   }
 
@@ -6724,7 +6745,7 @@ test_if_skip_sort_order(JOIN_TAB *tab,ORDER *order,ha_rows select_limit,
     */
     int order_direction;
     uint used_key_parts;
-    if (!(usable_keys & ((key_map) 1 << ref_key)))
+    if (!usable_keys.is_set(ref_key))
     {
       /*
 	We come here when ref_key is not among usable_keys
@@ -6734,8 +6755,8 @@ test_if_skip_sort_order(JOIN_TAB *tab,ORDER *order,ha_rows select_limit,
 	If using index only read, only consider other possible index only
 	keys
       */
-      if (table->used_keys & (((key_map) 1 << ref_key)))
-	usable_keys|= table->used_keys;
+      if (table->used_keys.is_set(ref_key))
+	usable_keys.merge(table->used_keys);
       if ((new_ref_key= test_if_subkey(order, table, ref_key, ref_key_parts,
 				       usable_keys)) < MAX_KEY)
       {
@@ -6751,10 +6772,10 @@ test_if_skip_sort_order(JOIN_TAB *tab,ORDER *order,ha_rows select_limit,
 	  select->quick->init();
 	}
 	ref_key= new_ref_key;
-      }  
+      }
     }
     /* Check if we get the rows in requested sorted order by using the key */
-    if ((usable_keys & ((key_map) 1 << ref_key)) &&
+    if (usable_keys.is_set(ref_key) &&
 	(order_direction = test_if_order_by_key(order,table,ref_key,
 						&used_key_parts)))
     {
@@ -6805,7 +6826,7 @@ test_if_skip_sort_order(JOIN_TAB *tab,ORDER *order,ha_rows select_limit,
     /* check if we can use a key to resolve the group */
     /* Tables using JT_NEXT are handled here */
     uint nr;
-    key_map keys=usable_keys;
+    key_map keys;
 
     /*
       If not used with LIMIT, only use keys if the whole query can be
@@ -6813,12 +6834,19 @@ test_if_skip_sort_order(JOIN_TAB *tab,ORDER *order,ha_rows select_limit,
       retrieving all rows through an index.
     */
     if (select_limit >= table->file->records)
-      keys&= (table->used_keys | table->file->keys_to_use_for_scanning());
+    {
+      keys=table->file->keys_to_use_for_scanning();
+      keys.merge(table->used_keys);
+    }
+    else
+      keys.set_all();
+
+    keys.intersect(usable_keys);
 
-    for (nr=0; keys ; keys>>=1, nr++)
+    for (nr=0; nr < keys.length() ; nr++)
     {
       uint not_used;
-      if (keys & 1)
+      if (keys.is_set(nr))
       {
 	int flag;
 	if ((flag=test_if_order_by_key(order, table, nr, &not_used)))
@@ -6830,7 +6858,7 @@ test_if_skip_sort_order(JOIN_TAB *tab,ORDER *order,ha_rows select_limit,
 				      join_read_last);
 	    table->file->index_init(nr);
 	    tab->type=JT_NEXT;	// Read with index_first(), index_next()
-	    if (table->used_keys & ((key_map) 1 << nr))
+	    if (table->used_keys.is_set(nr))
 	    {
 	      table->key_read=1;
 	      table->file->extra(HA_EXTRA_KEYREAD);
@@ -6855,7 +6883,7 @@ test_if_skip_sort_order(JOIN_TAB *tab,ORDER *order,ha_rows select_limit,
      order		How table should be sorted
      filesort_limit	Max number of rows that needs to be sorted
      select_limit	Max number of rows in final output
-		        Used to decide if we should use index or not     
+		        Used to decide if we should use index or not
 
 
   IMPLEMENTATION
@@ -8684,7 +8712,7 @@ static void select_describe(JOIN *join, bool need_tmp_table, bool need_order,
   Item *item_null= new Item_null();
   CHARSET_INFO *cs= &my_charset_latin1;
   DBUG_ENTER("select_describe");
-  DBUG_PRINT("info", ("Select 0x%lx, type %s, message %s", 
+  DBUG_PRINT("info", ("Select 0x%lx, type %s, message %s",
 		      (ulong)join->select_lex, join->select_lex->type,
 		      message));
   /* Don't log this into the slow query log */
@@ -8718,7 +8746,7 @@ static void select_describe(JOIN *join, bool need_tmp_table, bool need_order,
       tmp2.length(0);
 
       item_list.empty();
-      item_list.push_back(new Item_int((int32) 
+      item_list.push_back(new Item_int((int32)
 				       join->select_lex->select_number));
       item_list.push_back(new Item_string(join->select_lex->type,
 					  strlen(join->select_lex->type),
@@ -8740,21 +8768,23 @@ static void select_describe(JOIN *join, bool need_tmp_table, bool need_order,
       item_list.push_back(new Item_string(join_type_str[tab->type],
 					  strlen(join_type_str[tab->type]),
 					  cs));
-      key_map bits;
       uint j;
-      for (j=0,bits=tab->keys ; bits ; j++,bits>>=1)
+      if (!tab->keys.is_clear_all())
       {
-	if (bits & 1)
-	{
-	  if (tmp1.length())
-	    tmp1.append(',');
-	  tmp1.append(table->key_info[j].name);
-	}
+        for (j=0 ; j < tab->keys.length() ; j++)
+        {
+          if (tab->keys.is_set(j))
+          {
+            if (tmp1.length())
+              tmp1.append(',');
+            tmp1.append(table->key_info[j].name);
+          }
+        }
       }
       if (tmp1.length())
 	item_list.push_back(new Item_string(tmp1.ptr(),tmp1.length(),cs));
       else
- 	item_list.push_back(item_null);
+	item_list.push_back(item_null);
       if (tab->ref.key_parts)
       {
 	KEY *key_info=table->key_info+ tab->ref.key;
@@ -8797,10 +8827,9 @@ static void select_describe(JOIN *join, bool need_tmp_table, bool need_order,
 				       join->best_positions[i]. records_read,
 				       21));
       my_bool key_read=table->key_read;
-      if (tab->type == JT_NEXT &&
-	  ((table->used_keys & ((key_map) 1 << tab->index))))
+      if (tab->type == JT_NEXT && table->used_keys.is_set(tab->index))
 	key_read=1;
-      
+
       if (tab->info)
 	item_list.push_back(new Item_string(tab->info,strlen(tab->info),cs));
       else
@@ -8809,8 +8838,9 @@ static void select_describe(JOIN *join, bool need_tmp_table, bool need_order,
 	{
 	  if (tab->use_quick == 2)
 	  {
-	    sprintf(buff_ptr,"; Range checked for each record (index map: %u)",
-		    tab->keys);
+            char buf[MAX_KEY/8+1];
+	    sprintf(buff_ptr,"; Range checked for each record (index map: %s)",
+                tab->keys.print(buf));
 	    buff_ptr=strend(buff_ptr);
 	  }
 	  else
diff --git a/sql/sql_select.h b/sql/sql_select.h
index 6c17a646ee6..aa77722546d 100644
--- a/sql/sql_select.h
+++ b/sql/sql_select.h
@@ -29,8 +29,8 @@ typedef struct keyuse_t {
   Item	*val;				/* or value if no field */
   table_map used_tables;
   uint	key, keypart, optimize;
-  key_map   keypart_map;
-  ha_rows   ref_table_rows;
+  key_part_map keypart_map;
+  ha_rows      ref_table_rows;
 } KEYUSE;
 
 class store_key;
@@ -96,9 +96,9 @@ typedef struct st_join_table {
   key_map	const_keys;			/* Keys with constant part */
   key_map	checked_keys;			/* Keys checked in find_best */
   key_map	needed_reg;
+  key_map       keys;                           /* all keys with can be used */
   ha_rows	records,found_records,read_time;
   table_map	dependent,key_dependent;
-  uint		keys;				/* all keys with can be used */
   uint		use_quick,index;
   uint		status;				// Save status for cache
   uint		used_fields,used_fieldlength,used_blobs;
diff --git a/sql/sql_show.cc b/sql/sql_show.cc
index 8550973ff88..a026bd5276d 100644
--- a/sql/sql_show.cc
+++ b/sql/sql_show.cc
@@ -939,7 +939,7 @@ mysqld_show_keys(THD *thd, TABLE_LIST *table_list)
       protocol->store((const char*) pos, system_charset_info);
       protocol->store(table->file->index_type(i), system_charset_info);
       /* Comment */
-      if (!(table->keys_in_use & ((key_map) 1 << i)))
+      if (!table->keys_in_use.is_set(i))
 	protocol->store("disabled",8, system_charset_info);
       else
         protocol->store("", 0, system_charset_info);
diff --git a/sql/sql_test.cc b/sql/sql_test.cc
index f991a09398b..006a324f16d 100644
--- a/sql/sql_test.cc
+++ b/sql/sql_test.cc
@@ -172,10 +172,11 @@ TEST_join(JOIN *join)
 	    tab->ref.key_length);
     if (tab->select)
     {
+      char buf[MAX_KEY/8+1];
       if (tab->use_quick == 2)
 	fprintf(DBUG_FILE,
-		"                  quick select checked for each record (keys: %d)\n",
-		(int) tab->select->quick_keys);
+		"                  quick select checked for each record (keys: %s)\n",
+		tab->select->quick_keys.print(buf));
       else if (tab->select->quick)
 	fprintf(DBUG_FILE,"                  quick select used on key %s, length: %d\n",
 		form->key_info[tab->select->quick->index].name,
diff --git a/sql/sql_update.cc b/sql/sql_update.cc
index 2ecc526a612..4cf5f740d17 100644
--- a/sql/sql_update.cc
+++ b/sql/sql_update.cc
@@ -85,7 +85,7 @@ int mysql_update(THD *thd,
 
   /* Calculate "table->used_keys" based on the WHERE */
   table->used_keys=table->keys_in_use;
-  table->quick_keys=0;
+  table->quick_keys.clear_all();
 #ifndef NO_EMBEDDED_ACCESS_CHECKS
   want_privilege=table->grant.want_privilege;
   table->grant.want_privilege=(SELECT_ACL & ~table->grant.privilege);
@@ -149,7 +149,7 @@ int mysql_update(THD *thd,
   }
 
   // Don't count on usage of 'only index' when calculating which key to use
-  table->used_keys=0;
+  table->used_keys.clear_all();
   select=make_select(table,0,0,conds,&error);
   if (error ||
       (select && select->check_quick(safe_update, limit)) || !limit)
@@ -164,7 +164,7 @@ int mysql_update(THD *thd,
     DBUG_RETURN(0);
   }
   /* If running in safe sql mode, don't allow updates without keys */
-  if (!table->quick_keys)
+  if (table->quick_keys.is_clear_all())
   {
     thd->lex.select_lex.options|=QUERY_NO_INDEX_USED;
     if (safe_update && !using_limit)
@@ -192,7 +192,7 @@ int mysql_update(THD *thd,
       matching rows before updating the table!
     */
     table->file->extra(HA_EXTRA_RETRIEVE_ALL_COLS);
-    if (old_used_keys & ((key_map) 1 << used_index))
+    if (old_used_keys.is_set(used_index))
     {
       table->key_read=1;
       table->file->extra(HA_EXTRA_KEYREAD);
@@ -501,8 +501,7 @@ int multi_update::prepare(List<Item> &not_used_values, SELECT_LEX_UNIT *unit)
 
   if (!tables_to_update)
   {
-    my_error(ER_NOT_SUPPORTED_YET, MYF(0),
-	     "You didn't specify any tables to UPDATE");
+    my_error(ER_NO_TABLES_USED, MYF(0));
     DBUG_RETURN(1);
   }
 
@@ -533,7 +532,7 @@ int multi_update::prepare(List<Item> &not_used_values, SELECT_LEX_UNIT *unit)
       update.link_in_list((byte*) tl, (byte**) &tl->next);
       tl->shared= table_count++;
       table->no_keyread=1;
-      table->used_keys=0;
+      table->used_keys.clear_all();
       table->pos_in_table_list= tl;
     }
   }
diff --git a/sql/table.cc b/sql/table.cc
index c31b68fc2dc..c6da3432aaa 100644
--- a/sql/table.cc
+++ b/sql/table.cc
@@ -137,10 +137,11 @@ int openfrm(const char *name, const char *alias, uint db_stat, uint prgflag,
     outparam->raid_type=   head[41];
     outparam->raid_chunks= head[42];
     outparam->raid_chunksize= uint4korr(head+43);
-    if (!(outparam->table_charset=get_charset((uint) head[38],MYF(0))))
-      outparam->table_charset=default_charset_info; // QQ display error message?
+    outparam->table_charset=get_charset((uint) head[38],MYF(0));
     null_field_first=1;
   }
+  if (!outparam->table_charset) /* unknown charset in head[38] or pre-3.23 frm */
+    outparam->table_charset=default_charset_info;
   outparam->db_record_offset=1;
   if (db_create_options & HA_OPTION_LONG_BLOB_PTR)
     outparam->blob_ptr_size=portable_sizeof_char_ptr;
@@ -156,7 +157,12 @@ int openfrm(const char *name, const char *alias, uint db_stat, uint prgflag,
   if (read_string(file,(gptr*) &disk_buff,key_info_length))
     goto err_not_open; /* purecov: inspected */
   outparam->keys=keys=   disk_buff[0];
-  outparam->keys_for_keyread= outparam->keys_in_use= set_bits(key_map, keys);
+  outparam->keys_for_keyread.init().set_prefix(keys);
+  outparam->keys_in_use.init().set_prefix(keys);
+  outparam->read_only_keys.init().clear_all();
+  outparam->quick_keys.init();
+  outparam->used_keys.init();
+  outparam->keys_in_use_for_query.init();
 
   outparam->key_parts=key_parts=disk_buff[1];
   n_length=keys*sizeof(KEY)+key_parts*sizeof(KEY_PART_INFO);
@@ -484,8 +490,8 @@ int openfrm(const char *name, const char *alias, uint db_stat, uint prgflag,
       index_flags=outparam->file->index_flags(key);
       if (!(index_flags & HA_KEY_READ_ONLY))
       {
-	outparam->read_only_keys|=    ((key_map) 1 << key);
-	outparam->keys_for_keyread&= ~((key_map) 1 << key);
+	outparam->read_only_keys.set_bit(key);
+	outparam->keys_for_keyread.clear_bit(key);
       }
 
       if (primary_key >= MAX_KEY && (keyinfo->flags & HA_NOSAME))
@@ -545,7 +551,7 @@ int openfrm(const char *name, const char *alias, uint db_stat, uint prgflag,
 	       field->key_length() ==
 	       keyinfo->key_length ? UNIQUE_KEY_FLAG : MULTIPLE_KEY_FLAG);
 	  if (i == 0)
-	    field->key_start|= ((key_map) 1 << key);
+	    field->key_start.set_bit(key);
 	  if (field->key_length() == key_part->length &&
 	      !(field->flags & BLOB_FLAG))
 	  {
@@ -553,11 +559,11 @@ int openfrm(const char *name, const char *alias, uint db_stat, uint prgflag,
 		(field->key_type() != HA_KEYTYPE_TEXT ||
 		 (!(ha_option & HA_KEY_READ_WRONG_STR) &&
 		  !(keyinfo->flags & HA_FULLTEXT))))
-	      field->part_of_key|= ((key_map) 1 << key);
+	      field->part_of_key.set_bit(key);
 	    if ((field->key_type() != HA_KEYTYPE_TEXT ||
 		 !(keyinfo->flags & HA_FULLTEXT)) &&
 		!(index_flags & HA_WRONG_ASCII_ORDER))
-	      field->part_of_sortkey|= ((key_map) 1 << key);
+	      field->part_of_sortkey.set_bit(key);
 	  }
 	  if (!(key_part->key_part_flag & HA_REVERSE_SORT) &&
 	      usable_parts == i)
@@ -600,7 +606,7 @@ int openfrm(const char *name, const char *alias, uint db_stat, uint prgflag,
       keyinfo->usable_key_parts=usable_parts; // Filesort
     }
     if (primary_key < MAX_KEY &&
-	(outparam->keys_in_use & ((key_map) 1 << primary_key)))
+	(outparam->keys_in_use.is_set(primary_key)))
     {
       outparam->primary_key=primary_key;
       /*
diff --git a/sql/unireg.cc b/sql/unireg.cc
index 3e634f54b4f..be14448bd1d 100644
--- a/sql/unireg.cc
+++ b/sql/unireg.cc
@@ -33,7 +33,7 @@
 static uchar * pack_screens(List<create_field> &create_fields,
 			    uint *info_length, uint *screens, bool small_file);
 static uint pack_keys(uchar *keybuff,uint key_count, KEY *key_info);
-static bool pack_header(uchar *forminfo, enum db_type table_type,
+static bool pack_header(uchar *forminfo,enum db_type table_type,
 			List<create_field> &create_fields,
 			uint info_length, uint screens, uint table_options,
 			handler *file);