key_map with more that 64 bits width

sql/field.cc:
  typedef Bitmap<64> key_map
  all tests pass
sql/ha_berkeley.cc:
  typedef Bitmap<64> key_map
  all tests pass
sql/ha_berkeley.h:
  typedef Bitmap<64> key_map
  all tests pass
sql/item.cc:
  typedef Bitmap<64> key_map
  all tests pass
sql/item_func.cc:
  typedef Bitmap<64> key_map
  all tests pass
sql/opt_sum.cc:
  typedef Bitmap<64> key_map
  all tests pass
sql/sql_delete.cc:
  typedef Bitmap<64> key_map
  all tests pass
sql/sql_show.cc:
  typedef Bitmap<64> key_map
  all tests pass
sql/sql_test.cc:
  typedef Bitmap<64> key_map
  all tests pass
sql/sql_update.cc:
  typedef Bitmap<64> key_map
  all tests pass
include/my_bitmap.h:
  more bitmap methods
mysys/my_bitmap.c:
  more bitmap methods
sql/field.h:
  init bitmaps
sql/ha_innodb.h:
  optimization
sql/ha_isam.cc:
  optimization
sql/ha_myisam.cc:
  optimization
sql/ha_myisammrg.cc:
  optimization
sql/handler.h:
  optimization
sql/mysqld.cc:
  bitmap_init() interface changed
sql/opt_range.cc:
  optimization
sql/opt_range.h:
  optimization
sql/slave.cc:
  bitmap_init() interface changed
sql/sql_base.cc:
  optimization
sql/sql_select.cc:
  init bitmaps
  using const for bitmaps whenever possible
sql/sql_select.h:
  cleanup
sql/table.cc:
  always init bitmaps
BitKeeper/etc/ignore:
  Added sql/udf_example.so to the ignore list
sql/mysql_priv.h:
  use Bitmap over ulonglong by default

28 files changed, 533 insertions, 216 deletions

diff --git a/.bzrignore b/.bzrignore
index c2e7d0878e4..630cca684c7 100644
--- a/.bzrignore
+++ b/.bzrignore
@@ -636,3 +636,4 @@ vio/test-ssl
 vio/test-sslclient
 vio/test-sslserver
 vio/viotest-ssl
+sql/udf_example.so
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/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 34915a6020c..ffec47c73e5 100644
--- a/sql/ha_berkeley.cc
+++ b/sql/ha_berkeley.cc
@@ -841,7 +841,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 */
@@ -852,7 +852,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)
@@ -865,7 +865,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
@@ -1087,7 +1087,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 */
@@ -1120,7 +1120,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),
@@ -1258,7 +1258,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 13337f466bf..45990c479ab 100644
--- a/sql/ha_innodb.h
+++ b/sql/ha_innodb.h
@@ -124,7 +124,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 cec1aefa2d5..9fa99dc26d5 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 b74e06c6edf..e7ca17c8185 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 9d34f299a07..30c4e465544 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 125f87aecec..ff0a1df2e79 100644
--- a/sql/item_func.cc
+++ b/sql/item_func.cc
@@ -2561,7 +2561,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/mysql_priv.h b/sql/mysql_priv.h
index 1d7dd3aa5bb..da65418620c 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>
@@ -617,8 +722,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);
@@ -626,7 +731,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);
 int setup_conds(THD *thd,TABLE_LIST *tables,COND **conds);
 int setup_ftfuncs(SELECT_LEX* select);
diff --git a/sql/mysqld.cc b/sql/mysqld.cc
index 854fae4f15f..5e90c41b07f 100644
--- a/sql/mysqld.cc
+++ b/sql/mysqld.cc
@@ -2100,7 +2100,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 5b1e2c98001..7b1894f42d8 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 641707aab2f..896d11361d7 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_base.cc b/sql/sql_base.cc
index 1e44aa6e46d..d417e9a50db 100644
--- a/sql/sql_base.cc
+++ b/sql/sql_base.cc
@@ -1678,7 +1678,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;
@@ -1691,7 +1691,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;
@@ -1718,7 +1718,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
 */
@@ -2027,21 +2027,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;
@@ -2059,24 +2059,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;
 }
 
 /****************************************************************************
@@ -2120,7 +2122,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;
@@ -2211,8 +2213,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 ff41e9fd067..1ba2f52c318 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,
@@ -820,7 +823,7 @@ JOIN::optimize()
 								   conds,
 								   1)));
     }
-	       
+
   }
   /*
     Need to tell Innobase that to play it safe, it should fetch all
@@ -1547,7 +1550,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)
@@ -1564,7 +1567,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");
@@ -1626,9 +1629,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);
@@ -1774,24 +1781,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)
 	  {
@@ -1847,7 +1855,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;
@@ -2084,9 +2092,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:
@@ -2105,7 +2114,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.
@@ -2236,14 +2245,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)
 {
@@ -2255,7 +2263,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
@@ -2446,7 +2454,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);
@@ -2587,7 +2595,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;
@@ -2656,7 +2664,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
 		{
@@ -2680,7 +2688,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/
@@ -2707,7 +2715,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
@@ -2759,7 +2767,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/
@@ -2798,7 +2806,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;
@@ -2991,7 +2999,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)
@@ -3222,7 +3230,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;
@@ -3304,13 +3312,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
 	  {
@@ -3321,12 +3329,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
 	  /*
@@ -3336,9 +3345,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)))
 	  {
@@ -3376,13 +3385,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;
@@ -3447,7 +3458,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;
@@ -3465,7 +3476,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;
@@ -3540,12 +3551,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);
@@ -3891,7 +3902,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);
   }
@@ -4619,6 +4630,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 */
 
@@ -5812,7 +5829,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;
@@ -5849,7 +5866,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;
@@ -6547,18 +6564,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;
+        }
       }
     }
   }
@@ -6604,7 +6624,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;
@@ -6612,10 +6632,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,
@@ -6653,15 +6673,16 @@ 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;
     }
-    usable_keys&=((Item_field*) (*tmp_order->item))->field->part_of_sortkey;
+    usable_keys.intersect(
+        ((Item_field*) (*tmp_order->item))->field->part_of_sortkey);
   }
 
   ref_key= -1;
@@ -6686,7 +6707,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
@@ -6696,8 +6717,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)
       {
@@ -6713,10 +6734,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)))
     {
@@ -6767,7 +6788,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
@@ -6775,12 +6796,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)))
@@ -6792,7 +6820,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);
@@ -6817,7 +6845,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
@@ -8646,7 +8674,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 */
@@ -8680,7 +8708,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),
@@ -8702,21 +8730,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;
@@ -8759,10 +8789,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
@@ -8771,8 +8800,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 8ea78e702e5..01178afa0b0 100644
--- a/sql/sql_show.cc
+++ b/sql/sql_show.cc
@@ -930,7 +930,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 d2f97640010..37f7942f0e5 100644
--- a/sql/sql_test.cc
+++ b/sql/sql_test.cc
@@ -174,10 +174,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 b322957b20b..3942e783a64 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();
   want_privilege=table->grant.want_privilege;
   table->grant.want_privilege=(SELECT_ACL & ~table->grant.privilege);
 
@@ -143,7 +143,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)
@@ -158,7 +158,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)
@@ -186,7 +186,7 @@ int mysql_update(THD *thd,
       matching rows before updating the table!
     */
     table->file->extra(HA_EXTRA_DONT_USE_CURSOR_TO_UPDATE);
-    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);
@@ -524,7 +524,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 986a82cf9d2..a2518ce6a91 100644
--- a/sql/table.cc
+++ b/sql/table.cc
@@ -157,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);
@@ -486,8 +491,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))
@@ -547,7 +552,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))
 	  {
@@ -555,11 +560,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)
@@ -602,7 +607,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;
       /*