BTREE-indexes in HEAP tables can now be used to optimize ORDER BY

Don't read character set files if we are using only the default charset. In most cases the user will not anymore get a warning about missing character set files
Compare strings with space extend instead of space strip. Now the following comparisons holds:  "a" == "a " and "a\t" < "a". (Bug #3152).
Note: Because of the above fix, one has to do a REPAIR on any table that has an ascii character < 32 last in a CHAR/VARCHAR/TEXT columns.


heap/hp_hash.c:
  Comments and DBUG information
include/my_handler.h:
  Updated prototype for mi_compare_text
myisam/ft_boolean_search.c:
  Updated calls to mi_compare_text
myisam/ft_nlq_search.c:
  Updated calls to mi_compare_text
myisam/ft_parser.c:
  Updated calls to mi_compare_text
myisam/ft_stopwords.c:
  Updated calls to mi_compare_text
myisam/ft_update.c:
  Updated calls to mi_compare_text
myisam/mi_check.c:
  Updated calls to mi_compare_text
myisam/mi_search.c:
  Changed all string comparisons that removed end space to instead extend the shorter string with space
myisam/mi_unique.c:
  Updated calls to mi_compare_text
myisam/mi_write.c:
  Updated calls to mi_compare_text
myisam/myisam_ftdump.c:
  Removed compiler warning
mysql-test/r/ctype_collate.result:
  Fixed wrong result
mysql-test/r/heap_btree.result:
  More tests
mysql-test/t/heap_btree.test:
  more tests
mysys/charset.c:
  Don't read charsets if we are only using default charset
  Don't require 'init_available_charsets' to succeed.
mysys/my_handler.c:
  Compare strings with space extend instead of space strip
mysys/tree.c:
  Fixed code to get better results for range optimzier
sql/field.cc:
  Compare strings with space extend instead of space strip
sql/filesort.cc:
  Compare strings with space extend instead of space strip
sql/ha_heap.cc:
  Created bit map for keys that are using BTREE. This allows the optimzer to use BTREE's for sorting
sql/ha_heap.h:
  Created bit map for keys that are using BTREE. This allows the optimzer to use BTREE's for sorting
strings/ctype-big5.c:
  Compare strings with space extend instead of space strip
strings/ctype-czech.c:
  Indentation cleanup. Should be fixed to use space extend
strings/ctype-gbk.c:
  Compare strings with space extend instead of space strip
strings/ctype-latin1.c:
  Compare strings with space extend instead of space strip
  Added missing my_hash_sort_latin1_de function
strings/ctype-mb.c:
  For binary strings, don't remove end space when comparing
strings/ctype-simple.c:
  Compare strings with space extend instead of space strip
strings/ctype-sjis.c:
  Compare strings with space extend instead of space strip
strings/ctype-tis620.c:
  Added comments that we should fix end space handling
strings/ctype-ucs2.c:
  indentation fixes
strings/ctype-utf8.c:
  Added comments that we should fix end space handling
strings/ctype-win1250ch.c:
  Added comments that we should fix end space handling

3 files changed, 62 insertions, 39 deletions

diff --git a/mysys/charset.c b/mysys/charset.c
index c422ead89c0..80f62b06a3e 100644
--- a/mysys/charset.c
+++ b/mysys/charset.c
@@ -459,7 +459,9 @@ static my_bool init_available_charsets(myf myflags)
     init_compiled_charsets(myflags);
     
     /* Copy compiled charsets */
-    for (cs=all_charsets; cs < all_charsets+255 ; cs++)
+    for (cs=all_charsets;
+	 cs < all_charsets+array_elements(all_charsets)-1 ;
+	 cs++)
     {
       if (*cs)
       {
@@ -486,10 +488,11 @@ void free_charsets(void)
 uint get_collation_number(const char *name)
 {
   CHARSET_INFO **cs;
-  if (init_available_charsets(MYF(0)))	/* If it isn't initialized */
-    return 0;
+  init_available_charsets(MYF(0));
   
-  for (cs= all_charsets; cs < all_charsets+255; ++cs)
+  for (cs= all_charsets;
+       cs < all_charsets+array_elements(all_charsets)-1 ;
+       cs++)
   {
     if ( cs[0] && cs[0]->name && 
          !my_strcasecmp(&my_charset_latin1, cs[0]->name, name))
@@ -498,13 +501,15 @@ uint get_collation_number(const char *name)
   return 0;   /* this mimics find_type() */
 }
 
+
 uint get_charset_number(const char *charset_name, uint cs_flags)
 {
   CHARSET_INFO **cs;
-  if (init_available_charsets(MYF(0)))	/* If it isn't initialized */
-    return 0;
+  init_available_charsets(MYF(0));
   
-  for (cs= all_charsets; cs < all_charsets+255; ++cs)
+  for (cs= all_charsets;
+       cs < all_charsets+array_elements(all_charsets)-1 ;
+       cs++)
   {
     if ( cs[0] && cs[0]->csname && (cs[0]->state & cs_flags) &&
          !my_strcasecmp(&my_charset_latin1, cs[0]->csname, charset_name))
@@ -517,8 +522,7 @@ uint get_charset_number(const char *charset_name, uint cs_flags)
 const char *get_charset_name(uint charset_number)
 {
   CHARSET_INFO *cs;
-  if (init_available_charsets(MYF(0)))	/* If it isn't initialized */
-    return "?";
+  init_available_charsets(MYF(0));
 
   cs=all_charsets[charset_number];
   if (cs && (cs->number == charset_number) && cs->name )
@@ -554,9 +558,12 @@ static CHARSET_INFO *get_internal_charset(uint cs_number, myf flags)
 CHARSET_INFO *get_charset(uint cs_number, myf flags)
 {
   CHARSET_INFO *cs;
+  if (cs_number == default_charset_info->number)
+    return default_charset_info;
+
   (void) init_available_charsets(MYF(0));	/* If it isn't initialized */
   
-  if (!cs_number)
+  if (!cs_number || cs_number >= array_elements(all_charsets)-1)
     return NULL;
   
   cs=get_internal_charset(cs_number, flags);
diff --git a/mysys/my_handler.c b/mysys/my_handler.c
index 190c279aadf..35f620ccbcb 100644
--- a/mysys/my_handler.c
+++ b/mysys/my_handler.c
@@ -18,15 +18,21 @@
 #include "my_handler.h"
 
 int mi_compare_text(CHARSET_INFO *charset_info, uchar *a, uint a_length,
-		    uchar *b, uint b_length, my_bool part_key)
+		    uchar *b, uint b_length, my_bool part_key,
+		    my_bool skip_end_space)
 {
   if (part_key && b_length < a_length)
     a_length=b_length;
-  return my_strnncoll(charset_info, a, a_length, b, b_length);
+  if (skip_end_space)
+    return charset_info->coll->strnncollsp(charset_info, a, a_length,
+					   b, b_length);
+  return charset_info->coll->strnncoll(charset_info, a, a_length,
+				       b, b_length);
 }
 
+
 static int compare_bin(uchar *a, uint a_length, uchar *b, uint b_length,
-                       my_bool part_key)
+                       my_bool part_key, my_bool skip_end_space)
 {
   uint length= min(a_length,b_length);
   uchar *end= a+ length;
@@ -37,6 +43,31 @@ static int compare_bin(uchar *a, uint a_length, uchar *b, uint b_length,
       return flag;
   if (part_key && b_length < a_length)
     return 0;
+  if (skip_end_space && a_length != b_length)
+  {
+    int swap= 0;
+    /*
+      We are using space compression. We have to check if longer key
+      has next character < ' ', in which case it's less than the shorter
+      key that has an implicite space afterwards.
+
+      This code is identical to the one in
+      strings/ctype-simple.c:my_strnncollsp_simple
+    */
+    if (a_length < b_length)
+    {
+      /* put shorter key in a */
+      a_length= b_length;
+      a= b;
+      swap= -1;					/* swap sign of result */
+    }
+    for (end= a + a_length-length; a < end ; a++)
+    {
+      if (*a != ' ')
+	return ((int) *a - (int) ' ') ^ swap;
+    }
+    return 0;
+  }
   return (int) (a_length-b_length);
 }
 
@@ -128,7 +159,8 @@ int ha_key_cmp(register HA_KEYSEG *keyseg, register uchar *a,
         if (piks &&
             (flag=mi_compare_text(keyseg->charset,a,a_length,b,b_length,
 				  (my_bool) ((nextflag & SEARCH_PREFIX) &&
-					     next_key_length <= 0))))
+					     next_key_length <= 0),
+				  !(nextflag & SEARCH_PREFIX))))
           return ((keyseg->flag & HA_REVERSE_SORT) ? -flag : flag);
         a+=a_length;
         b+=b_length;
@@ -137,17 +169,11 @@ int ha_key_cmp(register HA_KEYSEG *keyseg, register uchar *a,
       else
       {
 	uint length=(uint) (end-a), a_length=length, b_length=length;
-	if (!(nextflag & SEARCH_PREFIX))
-	{
-	  while (a_length && a[a_length-1] == ' ')
-	    a_length--;
-	  while (b_length && b[b_length-1] == ' ')
-	    b_length--;
-	}
         if (piks &&
             (flag= mi_compare_text(keyseg->charset, a, a_length, b, b_length,
 				   (my_bool) ((nextflag & SEARCH_PREFIX) &&
-					      next_key_length <= 0))))
+					      next_key_length <= 0),
+				   !(nextflag & SEARCH_PREFIX))))
           return ((keyseg->flag & HA_REVERSE_SORT) ? -flag : flag);
         a=end;
         b+=length;
@@ -164,7 +190,7 @@ int ha_key_cmp(register HA_KEYSEG *keyseg, register uchar *a,
         if (piks &&
 	    (flag=compare_bin(a,a_length,b,b_length,
                               (my_bool) ((nextflag & SEARCH_PREFIX) &&
-                                         next_key_length <= 0))))
+                                         next_key_length <= 0),1)))
           return ((keyseg->flag & HA_REVERSE_SORT) ? -flag : flag);
         a+=a_length;
         b+=b_length;
@@ -176,7 +202,7 @@ int ha_key_cmp(register HA_KEYSEG *keyseg, register uchar *a,
         if (piks &&
 	    (flag=compare_bin(a,length,b,length,
                               (my_bool) ((nextflag & SEARCH_PREFIX) &&
-                                         next_key_length <= 0))))
+                                         next_key_length <= 0),0)))
           return ((keyseg->flag & HA_REVERSE_SORT) ? -flag : flag);
         a+=length;
         b+=length;
@@ -191,18 +217,13 @@ int ha_key_cmp(register HA_KEYSEG *keyseg, register uchar *a,
         full_b_length= b_length;
         next_key_length=key_length-b_length-pack_length;
 
-	if ((nextflag & (SEARCH_FIND | SEARCH_UPDATE)) == SEARCH_FIND)
-	{
-	  while (a_length && a[a_length-1] == ' ')
-	    a_length--;
-	  while (b_length && b[b_length-1] == ' ')
-	    b_length--;
-	}
-
         if (piks &&
 	    (flag= mi_compare_text(keyseg->charset,a,a_length,b,b_length,
                                    (my_bool) ((nextflag & SEARCH_PREFIX) &&
-                                              next_key_length <= 0))))
+                                              next_key_length <= 0),
+				   (my_bool) ((nextflag & (SEARCH_FIND |
+							   SEARCH_UPDATE)) ==
+					      SEARCH_FIND))))
           return ((keyseg->flag & HA_REVERSE_SORT) ? -flag : flag);
         a+= full_a_length;
         b+= full_b_length;
@@ -219,7 +240,7 @@ int ha_key_cmp(register HA_KEYSEG *keyseg, register uchar *a,
         if (piks &&
 	    (flag=compare_bin(a,a_length,b,b_length,
                               (my_bool) ((nextflag & SEARCH_PREFIX) &&
-                                         next_key_length <= 0))))
+                                         next_key_length <= 0), 0)))
           return ((keyseg->flag & HA_REVERSE_SORT) ? -flag : flag);
         a+=a_length;
         b+=b_length;
diff --git a/mysys/tree.c b/mysys/tree.c
index 0b30ffa4971..063c8739e58 100644
--- a/mysys/tree.c
+++ b/mysys/tree.c
@@ -481,7 +481,6 @@ ha_rows tree_record_pos(TREE *tree, const void *key,
   TREE_ELEMENT *element= tree->root;
   double left= 1;
   double right= tree->elements_in_tree;
-  ha_rows last_equal_pos= HA_POS_ERROR;
 
   while (element != &tree->null_element)
   {
@@ -490,9 +489,6 @@ ha_rows tree_record_pos(TREE *tree, const void *key,
     {
       switch (flag) {
       case HA_READ_KEY_EXACT:
-        last_equal_pos= (ha_rows) ((left + right) / 2);
-        cmp= 1;
-        break;
       case HA_READ_BEFORE_KEY:
         cmp= 1;
         break;
@@ -516,7 +512,6 @@ ha_rows tree_record_pos(TREE *tree, const void *key,
   }
   switch (flag) {
   case HA_READ_KEY_EXACT:
-    return last_equal_pos;
   case HA_READ_BEFORE_KEY:
     return (ha_rows) right;
   case HA_READ_AFTER_KEY: