Added support of null keys in HEAP tables

Added ORDER BY optimization


Docs/manual.texi:
  Added ORDER BY optimisation section
heap/_check.c:
  Cleanup
heap/heapdef.h:
  Added support of null keys in HEAP tables
heap/hp_hash.c:
  Added support of null keys in HEAP tables
heap/hp_open.c:
  Added support of null keys in HEAP tables
heap/hp_test2.c:
  Added support of null keys in HEAP tables
heap/hp_write.c:
  Added support of null keys in HEAP tables
include/heap.h:
  Added support of null keys in HEAP tables
include/my_base.h:
  Support for hash algoritm
isam/static.c:
  Cleanup
myisam/mi_static.c:
  Cleanup
sql/Makefile.am:
  Rename innobase -> innodb
sql/ha_berkeley.cc:
  Added ORDER BY optimization
sql/ha_berkeley.h:
  Added ORDER BY optimization
sql/ha_heap.cc:
  Added support for NULL keys
sql/ha_heap.h:
  Added support for NULL keys
sql/ha_isam.cc:
  Added ORDER BY optimization
sql/ha_isam.h:
  Added ORDER BY optimization
sql/ha_isammrg.h:
  Added ORDER BY optimization
sql/ha_myisam.cc:
  Added ORDER BY optimization
sql/ha_myisam.h:
  Added ORDER BY optimization
sql/ha_myisammrg.cc:
  Added ORDER BY optimization
sql/ha_myisammrg.h:
  Added ORDER BY optimization
sql/handler.cc:
  Rename innobase -> innodb
sql/handler.h:
  Rename innobase -> innodb
sql/ha_innodb.cc:
  Rename innobase -> innodb
sql/ha_innodb.h:
  Rename innobase -> innodb
sql/mysqld.cc:
  Rename innobase -> innodb
sql/sql_delete.cc:
  Rename innobase -> innodb
sql/sql_select.cc:
  Added ORDER BY optimization
sql/sql_select.h:
  Added ORDER BY optimization

20 files changed, 269 insertions, 84 deletions

diff --git a/sql/Makefile.am b/sql/Makefile.am
index 88306098107..e1ed9ad8915 100644
--- a/sql/Makefile.am
+++ b/sql/Makefile.am
@@ -51,7 +51,7 @@ noinst_HEADERS =	item.h item_func.h item_sum.h item_cmpfunc.h \
 			sql_manager.h sql_map.h sql_string.h unireg.h \
 			field.h handler.h \
 			ha_isammrg.h ha_isam.h ha_myisammrg.h\
-			ha_heap.h ha_myisam.h ha_berkeley.h ha_innobase.h \
+			ha_heap.h ha_myisam.h ha_berkeley.h ha_innodb.h \
 			opt_range.h opt_ft.h \
 			sql_select.h structs.h table.h sql_udf.h hash_filo.h\
 			lex.h lex_symbol.h sql_acl.h sql_crypt.h  \
@@ -74,7 +74,7 @@ mysqld_SOURCES =	sql_lex.cc sql_handler.cc \
 			time.cc opt_range.cc opt_sum.cc opt_ft.cc \
 		   	records.cc filesort.cc handler.cc \
 		        ha_heap.cc ha_myisam.cc ha_myisammrg.cc \
-	                ha_berkeley.cc ha_innobase.cc \
+	                ha_berkeley.cc ha_innodb.cc \
 			ha_isam.cc ha_isammrg.cc \
 			sql_db.cc sql_table.cc sql_rename.cc sql_crypt.cc \
 			sql_load.cc mf_iocache.cc field_conv.cc sql_show.cc \
diff --git a/sql/ha_berkeley.cc b/sql/ha_berkeley.cc
index e0a802b499a..6a9187a7cb2 100644
--- a/sql/ha_berkeley.cc
+++ b/sql/ha_berkeley.cc
@@ -1454,6 +1454,37 @@ int ha_berkeley::index_read(byte * buf, const byte * key,
   DBUG_RETURN(error);
 }
 
+/*
+  Read last key is solved by reading the next key and then reading
+  the previous key
+*/
+
+int ha_berkeley::index_read_last(byte * buf, const byte * key, uint key_len)
+{
+  DBT row;
+  int error;
+  KEY *key_info= &table->key_info[active_index];
+  DBUG_ENTER("ha_berkeley::index_read");
+
+  statistic_increment(ha_read_key_count,&LOCK_status);
+  bzero((char*) &row,sizeof(row));
+
+  /* read of partial key */
+  pack_key(&last_key, active_index, key_buff, key, key_len);
+  /* Store for compare */
+  memcpy(key_buff2, key_buff, (key_len=last_key.size));
+  key_info->handler.bdb_return_if_eq= 1;
+  error=read_row(cursor->c_get(cursor, &last_key, &row, DB_SET_RANGE),
+		 (char*) buf, active_index, &row, (DBT*) 0, 0);
+  key_info->handler.bdb_return_if_eq= 0;
+  bzero((char*) &row,sizeof(row));
+  if (read_row(cursor->c_get(cursor, &last_key, &row, DB_PREV),
+	       (char*) buf, active_index, &row, &last_key, 1) ||
+      berkeley_key_cmp(table, key_info, key_buff2, key_len))
+    error=HA_ERR_KEY_NOT_FOUND;
+  DBUG_RETURN(error);
+}
+
 
 int ha_berkeley::index_next(byte * buf)
 {
diff --git a/sql/ha_berkeley.h b/sql/ha_berkeley.h
index fbc858b5996..587d70265fa 100644
--- a/sql/ha_berkeley.h
+++ b/sql/ha_berkeley.h
@@ -89,7 +89,7 @@ class ha_berkeley: public handler
     int_option_flag(HA_READ_NEXT | HA_READ_PREV |
 		    HA_REC_NOT_IN_SEQ |
 		    HA_KEYPOS_TO_RNDPOS | HA_READ_ORDER | HA_LASTKEY_ORDER |
-		    HA_LONGLONG_KEYS | HA_NULL_KEY | HA_HAVE_KEY_READ_ONLY |
+		    HA_NULL_KEY | HA_HAVE_KEY_READ_ONLY |
 		    HA_BLOB_KEY | HA_NOT_EXACT_COUNT |
 		    HA_PRIMARY_KEY_IN_READ_INDEX | HA_DROP_BEFORE_CREATE |
 		    HA_AUTO_PART_KEY),
@@ -123,6 +123,7 @@ class ha_berkeley: public handler
 		 uint key_len, enum ha_rkey_function find_flag);
   int index_read_idx(byte * buf, uint index, const byte * key,
 		     uint key_len, enum ha_rkey_function find_flag);
+  int index_read_last(byte * buf, const byte * key, uint key_len);
   int index_next(byte * buf);
   int index_next_same(byte * buf, const byte *key, uint keylen);
   int index_prev(byte * buf);
diff --git a/sql/ha_heap.cc b/sql/ha_heap.cc
index 079fba05f0a..518a9c38d82 100644
--- a/sql/ha_heap.cc
+++ b/sql/ha_heap.cc
@@ -57,6 +57,7 @@ int ha_heap::open(const char *name, int mode, uint test_if_locked)
     for (part=0 ; part < pos->key_parts ; part++)
     {
       uint flag=pos->key_part[part].key_type;
+      Field *field=pos->key_part[part].field;
       if (!f_is_packed(flag) &&
 	  f_packtype(flag) == (int) FIELD_TYPE_DECIMAL &&
 	  !(flag & FIELDFLAG_BINARY))
@@ -65,7 +66,17 @@ int ha_heap::open(const char *name, int mode, uint test_if_locked)
 	seg->type= (int) HA_KEYTYPE_BINARY;
       seg->start=(uint) pos->key_part[part].offset;
       seg->length=(uint) pos->key_part[part].length;
-      seg++;
+      if (field->null_ptr)
+      {
+	seg->null_bit=field->null_bit;
+	seg->null_pos= (uint) (field->null_ptr-
+			       (uchar*) table->record[0]);
+      }
+      else
+      {
+	seg->null_bit=0;
+	seg->null_pos=0;
+      }
     }
   }
   mem_per_row += MY_ALIGN(table->reclength+1, sizeof(char*));
diff --git a/sql/ha_heap.h b/sql/ha_heap.h
index fa077cef60a..c8f29dea53c 100644
--- a/sql/ha_heap.h
+++ b/sql/ha_heap.h
@@ -36,7 +36,7 @@ class ha_heap: public handler
   ulong option_flag() const
   { return (HA_READ_RND_SAME | HA_NO_INDEX | HA_ONLY_WHOLE_INDEX |
 	    HA_WRONG_ASCII_ORDER | HA_KEYPOS_TO_RNDPOS | HA_NO_BLOBS |
-	    HA_REC_NOT_IN_SEQ); }
+	    HA_NULL_KEY | HA_REC_NOT_IN_SEQ | HA_NOT_READ_PREFIX_LAST); }
   uint max_record_length() const { return HA_MAX_REC_LENGTH; }
   uint max_keys()          const { return MAX_KEY; }
   uint max_key_parts()     const { return MAX_REF_PARTS; }
diff --git a/sql/ha_innobase.cc b/sql/ha_innodb.cc
index 683e76a19ad..8941481a95f 100644
--- a/sql/ha_innobase.cc
+++ b/sql/ha_innodb.cc
@@ -35,7 +35,7 @@ InnoDB */
 
 #define MAX_ULONG_BIT ((ulong) 1 << (sizeof(ulong)*8-1))
 
-#include "ha_innobase.h"
+#include "ha_innodb.h"
 
 /* We must declare this here because we undef SAFE_MUTEX below */
 pthread_mutex_t innobase_mutex;
@@ -2008,6 +2008,24 @@ ha_innobase::index_read(
 	DBUG_RETURN(error);
 }
 
+
+/*
+  The following functions works like index_read, but it find the last
+  row with the current index prefix.
+  This code is disabled until Heikki has verified that InnoDB support the
+  HA_READ_PREFIX_LAST flag and removed the HA_NOT_READ_PREFIX_LAST
+  flag from ha_innodb.h
+*/
+
+int
+ha_innobase::index_read_last(mysql_byte *buf,
+			     const mysql_byte *key_ptr,
+			     uint key_len)
+{
+  return index_read(buf, key_ptr, key_len, HA_READ_PREFIX_LAST);
+}
+
+
 /************************************************************************
 Changes the active index of a handle. */
 
diff --git a/sql/ha_innobase.h b/sql/ha_innodb.h
index 3c3025c39c1..fb10975f30a 100644
--- a/sql/ha_innobase.h
+++ b/sql/ha_innodb.h
@@ -1,7 +1,4 @@
-/* Copyright (C) 2000 MySQL AB & MySQL Finland AB & TCX DataKonsult AB
-   && Innobase Oy
-
-   -This file is modified from ha_berkeley.h of MySQL distribution-
+/* Copyright (C) 2000 MySQL AB && Innobase Oy
 
    This program is free software; you can redistribute it and/or modify
    it under the terms of the GNU General Public License as published by
@@ -17,13 +14,17 @@
    along with this program; if not, write to the Free Software
    Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA  02111-1307  USA */
 
+/*
+  This file is based on ha_berkeley.h of MySQL distribution
+
+  This file defines the Innodb handler: the interface between MySQL and
+  Innodb
+*/
+
 #ifdef __GNUC__
 #pragma interface			/* gcc class implementation */
 #endif
 
-/* This file defines the Innobase handler: the interface between MySQL and
-Innobase */
-
 typedef struct st_innobase_share {
   THR_LOCK lock;
   pthread_mutex_t mutex;
@@ -32,11 +33,11 @@ typedef struct st_innobase_share {
 } INNOBASE_SHARE;
 
 
-/* The class defining a handle to an Innobase table */
+/* The class defining a handle to an Innodb table */
 class ha_innobase: public handler
 {
 	void*	innobase_prebuilt;	/* (row_prebuilt_t*) prebuilt
-					struct in Innobase, used to save
+					struct in Innodb, used to save
 					CPU */
 	THD*		user_thd;	/* the thread handle of the user
 					currently using the handle; this is
@@ -50,7 +51,7 @@ class ha_innobase: public handler
   	byte*		upd_buff;	/* buffer used in updates */
   	byte*		key_val_buff;	/* buffer used in converting
   					search key values from MySQL format
-  					to Innobase format */
+  					to Innodb format */
 	uint		ref_stored_len;	/* length of the key value stored to
 					'ref' buffer of the handle, if any */
   	ulong 		int_option_flag;
@@ -78,11 +79,11 @@ class ha_innobase: public handler
 			  HA_REC_NOT_IN_SEQ |
 			  HA_KEYPOS_TO_RNDPOS | HA_LASTKEY_ORDER |
 			  HA_HAVE_KEY_READ_ONLY | HA_READ_NOT_EXACT_KEY |
-			  HA_LONGLONG_KEYS | HA_NULL_KEY |
+			  HA_NULL_KEY |
 			  HA_NOT_EXACT_COUNT |
 			  HA_NO_WRITE_DELAYED |
 			  HA_PRIMARY_KEY_IN_READ_INDEX |
-			  HA_DROP_BEFORE_CREATE |
+			  HA_DROP_BEFORE_CREATE | HA_NOT_READ_PREFIX_LAST |
 			  HA_NO_PREFIX_CHAR_KEYS),
 	  last_dup_key((uint) -1),
 	  start_of_scan(0)
@@ -122,9 +123,10 @@ class ha_innobase: public handler
   	int index_init(uint index);
   	int index_end();
   	int index_read(byte * buf, const byte * key,
-		 	uint key_len, enum ha_rkey_function find_flag);
+		       uint key_len, enum ha_rkey_function find_flag);
   	int index_read_idx(byte * buf, uint index, const byte * key,
-		     	uint key_len, enum ha_rkey_function find_flag);
+			   uint key_len, enum ha_rkey_function find_flag);
+	int index_read_last(byte * buf, const byte * key, uint key_len);
   	int index_next(byte * buf);
   	int index_next_same(byte * buf, const byte *key, uint keylen);
   	int index_prev(byte * buf);
diff --git a/sql/ha_isam.cc b/sql/ha_isam.cc
index a96f42c202f..4b8c40f8fe6 100644
--- a/sql/ha_isam.cc
+++ b/sql/ha_isam.cc
@@ -109,6 +109,15 @@ int ha_isam::index_read_idx(byte * buf, uint index, const byte * key,
   return !error ? 0 : my_errno ? my_errno : -1;
 }
 
+int ha_isam::index_read_last(byte * buf, const byte * key, uint key_len)
+{
+  statistic_increment(ha_read_key_count,&LOCK_status);
+  int error=nisam_rkey(file, buf, active_index, key, key_len,
+		       HA_READ_PREFIX_LAST);
+  table->status=error ? STATUS_NOT_FOUND: 0;
+  return !error ? 0 : my_errno ? my_errno : -1;
+}
+
 int ha_isam::index_next(byte * buf)
 {
   statistic_increment(ha_read_next_count,&LOCK_status);
diff --git a/sql/ha_isam.h b/sql/ha_isam.h
index e878f0fe697..4194632ddbe 100644
--- a/sql/ha_isam.h
+++ b/sql/ha_isam.h
@@ -33,7 +33,7 @@ class ha_isam: public handler
     int_option_flag(HA_READ_NEXT | HA_READ_PREV | HA_READ_RND_SAME |
 		    HA_KEYPOS_TO_RNDPOS | HA_READ_ORDER | HA_LASTKEY_ORDER |
 		    HA_HAVE_KEY_READ_ONLY | HA_READ_NOT_EXACT_KEY |
-		    HA_LONGLONG_KEYS | HA_KEY_READ_WRONG_STR | HA_DUPP_POS |
+		    HA_KEY_READ_WRONG_STR | HA_DUPP_POS |
 		    HA_NOT_DELETE_WITH_CACHE)
     {}
   ~ha_isam() {}
@@ -57,6 +57,7 @@ class ha_isam: public handler
 		 uint key_len, enum ha_rkey_function find_flag);
   int index_read_idx(byte * buf, uint idx, const byte * key,
 		     uint key_len, enum ha_rkey_function find_flag);
+  int index_read_last(byte * buf, const byte * key, uint key_len);
   int index_next(byte * buf);
   int index_prev(byte * buf);
   int index_first(byte * buf);
diff --git a/sql/ha_isammrg.h b/sql/ha_isammrg.h
index 888ecf0ca37..1ee0b0e2547 100644
--- a/sql/ha_isammrg.h
+++ b/sql/ha_isammrg.h
@@ -32,8 +32,9 @@ class ha_isammrg: public handler
   ~ha_isammrg() {}
   const char *table_type() const { return "MRG_ISAM"; }
   const char **bas_ext() const;
-  ulong option_flag() const { return HA_READ_RND_SAME | HA_KEYPOS_TO_RNDPOS
-                                                      | HA_REC_NOT_IN_SEQ;}
+  ulong option_flag() const { return (HA_READ_RND_SAME | HA_KEYPOS_TO_RNDPOS |
+				      HA_NOT_READ_PREFIX_LAST |
+				      HA_REC_NOT_IN_SEQ); }
   uint max_record_length() const { return HA_MAX_REC_LENGTH; }
   uint max_keys()          const { return 0; }
   uint max_key_parts()     const { return 0; }
diff --git a/sql/ha_myisam.cc b/sql/ha_myisam.cc
index 77d541bfdfb..78ac9f3b309 100644
--- a/sql/ha_myisam.cc
+++ b/sql/ha_myisam.cc
@@ -777,6 +777,14 @@ int ha_myisam::index_read_idx(byte * buf, uint index, const byte * key,
   return error;
 }
 
+int ha_myisam::index_read_last(byte * buf, const byte * key, uint key_len)
+{
+  statistic_increment(ha_read_key_count,&LOCK_status);
+  int error=mi_rkey(file,buf,active_index, key, key_len, HA_READ_PREFIX_LAST);
+  table->status=error ? STATUS_NOT_FOUND: 0;
+  return error;
+}
+
 int ha_myisam::index_next(byte * buf)
 {
   statistic_increment(ha_read_next_count,&LOCK_status);
@@ -973,7 +981,7 @@ void ha_myisam::update_create_info(HA_CREATE_INFO *create_info)
 }
 
 
-int ha_myisam::create(const char *name, register TABLE *form,
+int ha_myisam::create(const char *name, register TABLE *table,
 		      HA_CREATE_INFO *info)
 {
   int error;
@@ -985,20 +993,20 @@ int ha_myisam::create(const char *name, register TABLE *form,
   MI_KEYDEF *keydef;
   MI_COLUMNDEF *recinfo,*recinfo_pos;
   MI_KEYSEG *keyseg;
-  uint options=form->db_options_in_use;
+  uint options=table->db_options_in_use;
   DBUG_ENTER("ha_myisam::create");
 
   type=HA_KEYTYPE_BINARY;				// Keep compiler happy
   if (!(my_multi_malloc(MYF(MY_WME),
-			&recinfo,(form->fields*2+2)*sizeof(MI_COLUMNDEF),
-			&keydef, form->keys*sizeof(MI_KEYDEF),
+			&recinfo,(table->fields*2+2)*sizeof(MI_COLUMNDEF),
+			&keydef, table->keys*sizeof(MI_KEYDEF),
 			&keyseg,
-			((form->key_parts + form->keys) * sizeof(MI_KEYSEG)),
+			((table->key_parts + table->keys) * sizeof(MI_KEYSEG)),
 			0)))
     DBUG_RETURN(1);
 
-  pos=form->key_info;
-  for (i=0; i < form->keys ; i++, pos++)
+  pos=table->key_info;
+  for (i=0; i < table->keys ; i++, pos++)
   {
     keydef[i].flag= (pos->flags & (HA_NOSAME | HA_FULLTEXT));
     keydef[i].seg=keyseg;
@@ -1041,7 +1049,7 @@ int ha_myisam::create(const char *name, register TABLE *form,
       {
 	keydef[i].seg[j].null_bit=field->null_bit;
 	keydef[i].seg[j].null_pos= (uint) (field->null_ptr-
-					   (uchar*) form->record[0]);
+					   (uchar*) table->record[0]);
       }
       else
       {
@@ -1059,19 +1067,19 @@ int ha_myisam::create(const char *name, register TABLE *form,
 	keydef[i].seg[j].flag|=HA_BLOB_PART;
 	/* save number of bytes used to pack length */
 	keydef[i].seg[j].bit_start= (uint) (field->pack_length() -
-					    form->blob_ptr_size);
+					    table->blob_ptr_size);
       }
     }
     keyseg+=pos->key_parts;
   }
 
   recpos=0; recinfo_pos=recinfo;
-  while (recpos < (uint) form->reclength)
+  while (recpos < (uint) table->reclength)
   {
     Field **field,*found=0;
-    minpos=form->reclength; length=0;
+    minpos=table->reclength; length=0;
 
-    for (field=form->field ; *field ; field++)
+    for (field=table->field ; *field ; field++)
     {
       if ((fieldpos=(*field)->offset()) >= recpos &&
 	  fieldpos <= minpos)
@@ -1117,7 +1125,7 @@ int ha_myisam::create(const char *name, register TABLE *form,
     {
       recinfo_pos->null_bit=found->null_bit;
       recinfo_pos->null_pos= (uint) (found->null_ptr-
-				  (uchar*) form->record[0]);
+				  (uchar*) table->record[0]);
     }
     else
     {
@@ -1132,20 +1140,23 @@ int ha_myisam::create(const char *name, register TABLE *form,
   }
   MI_CREATE_INFO create_info;
   bzero((char*) &create_info,sizeof(create_info));
-  create_info.max_rows=form->max_rows;
-  create_info.reloc_rows=form->min_rows;
+  create_info.max_rows=table->max_rows;
+  create_info.reloc_rows=table->min_rows;
   create_info.auto_increment=(info->auto_increment_value ?
 			      info->auto_increment_value -1 :
 			      (ulonglong) 0);
-  create_info.data_file_length=(ulonglong) form->max_rows*form->avg_row_length;
+  create_info.data_file_length= ((ulonglong) table->max_rows *
+				 table->avg_row_length);
   create_info.raid_type=info->raid_type;
-  create_info.raid_chunks=info->raid_chunks ? info->raid_chunks : RAID_DEFAULT_CHUNKS;
-  create_info.raid_chunksize=info->raid_chunksize ? info->raid_chunksize : RAID_DEFAULT_CHUNKSIZE;
+  create_info.raid_chunks= (info->raid_chunks ? info->raid_chunks :
+			    RAID_DEFAULT_CHUNKS);
+  create_info.raid_chunksize=(info->raid_chunksize ? info->raid_chunksize :
+			      RAID_DEFAULT_CHUNKSIZE);
   create_info.data_file_name= info->data_file_name;
   create_info.index_file_name=info->index_file_name;
 
   error=mi_create(fn_format(buff,name,"","",2+4),
-		  form->keys,keydef,
+		  table->keys,keydef,
 		  (uint) (recinfo_pos-recinfo), recinfo,
 		  0, (MI_UNIQUEDEF*) 0,
 		  &create_info,
diff --git a/sql/ha_myisam.h b/sql/ha_myisam.h
index e2044dfe1e2..75655a2b505 100644
--- a/sql/ha_myisam.h
+++ b/sql/ha_myisam.h
@@ -47,7 +47,7 @@ class ha_myisam: public handler
     int_option_flag(HA_READ_NEXT | HA_READ_PREV | HA_READ_RND_SAME |
 		    HA_KEYPOS_TO_RNDPOS | HA_READ_ORDER | HA_LASTKEY_ORDER |
 		    HA_HAVE_KEY_READ_ONLY | HA_READ_NOT_EXACT_KEY |
-		    HA_LONGLONG_KEYS | HA_NULL_KEY |
+		    HA_NULL_KEY |
                     HA_CAN_FULLTEXT | HA_CAN_SQL_HANDLER |
 		    HA_DUPP_POS | HA_BLOB_KEY | HA_AUTO_PART_KEY),
     enable_activate_all_index(1)
@@ -71,6 +71,7 @@ class ha_myisam: public handler
 		 uint key_len, enum ha_rkey_function find_flag);
   int index_read_idx(byte * buf, uint idx, const byte * key,
 		     uint key_len, enum ha_rkey_function find_flag);
+  int index_read_last(byte * buf, const byte * key, uint key_len);
   int index_next(byte * buf);
   int index_prev(byte * buf);
   int index_first(byte * buf);
@@ -78,9 +79,15 @@ class ha_myisam: public handler
   int index_next_same(byte *buf, const byte *key, uint keylen);
   int index_end() { ft_handler=NULL; return 0; }
   int ft_init()
-         { if(!ft_handler) return 1; ft_handler->please->reinit_search(ft_handler); return 0; }
-  FT_INFO *ft_init_ext(uint mode, uint inx,const byte *key, uint keylen, bool presort)
-         { return ft_init_search(mode, file,inx,(byte*) key,keylen,presort); }
+  {
+    if (!ft_handler)
+      return 1;
+    ft_handler->please->reinit_search(ft_handler);
+    return 0;
+  }
+  FT_INFO *ft_init_ext(uint mode, uint inx,const byte *key, uint keylen,
+		       bool presort)
+  { return ft_init_search(mode, file,inx,(byte*) key,keylen,presort); }
   int ft_read(byte *buf);
   int rnd_init(bool scan=1);
   int rnd_next(byte *buf);
diff --git a/sql/ha_myisammrg.cc b/sql/ha_myisammrg.cc
index 999d9fe33ef..63a23fb708f 100644
--- a/sql/ha_myisammrg.cc
+++ b/sql/ha_myisammrg.cc
@@ -112,6 +112,15 @@ int ha_myisammrg::index_read_idx(byte * buf, uint index, const byte * key,
   return error;
 }
 
+int ha_myisammrg::index_read_last(byte * buf, const byte * key, uint key_len)
+{
+  statistic_increment(ha_read_key_count,&LOCK_status);
+  int error=myrg_rkey(file,buf,active_index, key, key_len,
+		      HA_READ_PREFIX_LAST);
+  table->status=error ? STATUS_NOT_FOUND: 0;
+  return error;
+}
+
 int ha_myisammrg::index_next(byte * buf)
 {
   statistic_increment(ha_read_next_count,&LOCK_status);
diff --git a/sql/ha_myisammrg.h b/sql/ha_myisammrg.h
index e18c520c803..2ab3a807543 100644
--- a/sql/ha_myisammrg.h
+++ b/sql/ha_myisammrg.h
@@ -38,7 +38,7 @@ class ha_myisammrg: public handler
 	      HA_HAVE_KEY_READ_ONLY |
 	      HA_KEYPOS_TO_RNDPOS | HA_READ_ORDER |
 	      HA_LASTKEY_ORDER | HA_READ_NOT_EXACT_KEY |
-	      HA_LONGLONG_KEYS | HA_NULL_KEY | HA_BLOB_KEY); }
+	      HA_NULL_KEY | HA_BLOB_KEY); }
   uint max_record_length() const { return HA_MAX_REC_LENGTH; }
   uint max_keys()          const { return MI_MAX_KEY; }
   uint max_key_parts()     const { return MAX_REF_PARTS; }
@@ -55,6 +55,7 @@ class ha_myisammrg: public handler
 		 uint key_len, enum ha_rkey_function find_flag);
   int index_read_idx(byte * buf, uint idx, const byte * key,
 		     uint key_len, enum ha_rkey_function find_flag);
+  int index_read_last(byte * buf, const byte * key, uint key_len);
   int index_next(byte * buf);
   int index_prev(byte * buf);
   int index_first(byte * buf);
diff --git a/sql/handler.cc b/sql/handler.cc
index f097e501a8b..52d65edf0d4 100644
--- a/sql/handler.cc
+++ b/sql/handler.cc
@@ -33,7 +33,7 @@
 #include "ha_berkeley.h"
 #endif
 #ifdef HAVE_INNOBASE_DB
-#include "ha_innobase.h"
+#include "ha_innodb.h"
 #endif
 #include <myisampack.h>
 #include <errno.h>
diff --git a/sql/handler.h b/sql/handler.h
index 33cfa965363..aa809b333b4 100644
--- a/sql/handler.h
+++ b/sql/handler.h
@@ -55,12 +55,11 @@
 #define HA_REC_NOT_IN_SEQ	64	/* ha_info don't return recnumber;
 					   It returns a position to ha_r_rnd */
 #define HA_ONLY_WHOLE_INDEX	128	/* Can't use part key searches */
-#define HA_RSAME_NO_INDEX	256	/* RSAME can't restore index */
+#define HA_NOT_READ_PREFIX_LAST	256	/* RSAME can't restore index */
 #define HA_WRONG_ASCII_ORDER	512	/* Can't use sorting through key */
 #define HA_HAVE_KEY_READ_ONLY	1024	/* Can read only keys (no record) */
 #define HA_READ_NOT_EXACT_KEY	2048	/* Can read record after/before key */
 #define HA_NO_INDEX		4096	/* No index needed for next/prev */
-#define HA_LONGLONG_KEYS	8192	/* Can have longlong as key */
 #define HA_KEY_READ_WRONG_STR	16384	/* keyread returns converted strings */
 #define HA_NULL_KEY		32768	/* One can have keys with NULL */
 #define HA_DUPP_POS		65536	/* ha_position() gives dupp row */
@@ -256,6 +255,10 @@ public:
   virtual int index_first(byte * buf)=0;
   virtual int index_last(byte * buf)=0;
   virtual int index_next_same(byte *buf, const byte *key, uint keylen);
+  virtual int index_read_last(byte * buf, const byte * key, uint key_len)
+  {
+    return (my_errno=HA_ERR_WRONG_COMMAND);
+  }
   virtual int ft_init()
     { return -1; }
   virtual FT_INFO *ft_init_ext(uint mode,uint inx,const byte *key, uint keylen,
diff --git a/sql/mysqld.cc b/sql/mysqld.cc
index 8e9ff17387c..a82e07fec6a 100644
--- a/sql/mysqld.cc
+++ b/sql/mysqld.cc
@@ -27,7 +27,7 @@
 #include "ha_berkeley.h"
 #endif
 #ifdef HAVE_INNOBASE_DB
-#include "ha_innobase.h"
+#include "ha_innodb.h"
 #endif
 #include "ha_myisam.h"
 #include <nisam.h>
diff --git a/sql/sql_delete.cc b/sql/sql_delete.cc
index eed6e4e5f81..ba46251078b 100644
--- a/sql/sql_delete.cc
+++ b/sql/sql_delete.cc
@@ -24,7 +24,7 @@
 
 
 #include "mysql_priv.h"
-#include "ha_innobase.h"
+#include "ha_innodb.h"
 #include "sql_select.h"
 
 int mysql_delete(THD *thd, TABLE_LIST *table_list, COND *conds, ORDER *order,
diff --git a/sql/sql_select.cc b/sql/sql_select.cc
index 46c1dc80762..144b76407ab 100644
--- a/sql/sql_select.cc
+++ b/sql/sql_select.cc
@@ -89,15 +89,18 @@ static int join_read_system(JOIN_TAB *tab);
 static int join_read_const(JOIN_TAB *tab);
 static int join_read_key(JOIN_TAB *tab);
 static int join_read_always_key(JOIN_TAB *tab);
+static int join_read_last_key(JOIN_TAB *tab);
 static int join_no_more_records(READ_RECORD *info);
 static int join_read_next(READ_RECORD *info);
 static int join_init_quick_read_record(JOIN_TAB *tab);
 static int test_if_quick_select(JOIN_TAB *tab);
 static int join_init_read_record(JOIN_TAB *tab);
-static int join_init_read_first_with_key(JOIN_TAB *tab);
-static int join_init_read_next_with_key(READ_RECORD *info);
-static int join_init_read_last_with_key(JOIN_TAB *tab);
-static int join_init_read_prev_with_key(READ_RECORD *info);
+static int join_read_first(JOIN_TAB *tab);
+static int join_read_next(READ_RECORD *info);
+static int join_read_next_same(READ_RECORD *info);
+static int join_read_last(JOIN_TAB *tab);
+static int join_read_prev_same(READ_RECORD *info);
+static int join_read_prev(READ_RECORD *info);
 static int join_ft_read_first(JOIN_TAB *tab);
 static int join_ft_read_next(READ_RECORD *info);
 static COND *make_cond_for_table(COND *cond,table_map table,
@@ -2510,7 +2513,7 @@ make_join_readinfo(JOIN *join,uint options)
       tab->quick=0;
       table->file->index_init(tab->ref.key);
       tab->read_first_record= join_read_always_key;
-      tab->read_record.read_record= join_read_next;
+      tab->read_record.read_record= join_read_next_same;
       if (table->used_keys & ((key_map) 1 << tab->ref.key) &&
 	  !table->no_keyread)
       {
@@ -2585,7 +2588,7 @@ make_join_readinfo(JOIN *join,uint options)
 	  {					// Only read index tree
 	    tab->index=find_shortest_key(table, table->used_keys);
 	    tab->table->file->index_init(tab->index);
-	    tab->read_first_record= join_init_read_first_with_key;
+	    tab->read_first_record= join_read_first;
 	    tab->type=JT_NEXT;		// Read with index_first / index_next
 	  }
 	}
@@ -3641,6 +3644,10 @@ create_tmp_table(THD *thd,TMP_TABLE_PARAM *param,List<Item> &fields,
     {
       if (field->flags & GROUP_FLAG && !using_unique_constraint)
       {
+	/*
+	  We have to reserve one byte here for NULL bits,
+	  as this is updated by 'end_update()'
+	*/
 	*pos++=0;				// Null is stored here
 	recinfo->length=1;
 	recinfo->type=FIELD_NORMAL;
@@ -3730,11 +3737,11 @@ create_tmp_table(THD *thd,TMP_TABLE_PARAM *param,List<Item> &fields,
 	{
 	  /*
 	    To be able to group on NULL, we move the null bit to be
-	     just before the column and extend the key to cover the null bit
+	    just before the column.
+	    The null byte is updated by 'end_update()' 
 	  */
-	  *group_buff= 0;			// Init null byte
-	  key_part_info->offset--;
-	  key_part_info->length++;
+	  key_part_info->null_bit=1;
+	  key_part_info->null_offset= key_part_info->offset-1;
 	  group->field->move_field((char*) group_buff+1, (uchar*) group_buff,
 				   1);
 	}
@@ -4497,6 +4504,35 @@ join_read_always_key(JOIN_TAB *tab)
   return 0;
 }
 
+/*
+  This function is used when optimizing away ORDER BY in 
+  SELECT * FROM t1 WHERE a=1 ORDER BY a DESC,b DESC
+*/
+  
+static int
+join_read_last_key(JOIN_TAB *tab)
+{
+  int error;
+  TABLE *table= tab->table;
+
+  if (cp_buffer_from_ref(&tab->ref))
+    return -1;
+  if ((error=table->file->index_read_last(table->record[0],
+					  tab->ref.key_buff,
+					  tab->ref.key_length)))
+  {
+    if (error != HA_ERR_KEY_NOT_FOUND)
+    {
+      sql_print_error("read_const: Got error %d when reading table %s",error,
+		      table->path);
+      table->file->print_error(error,MYF(0));
+      return 1;
+    }
+    return -1; /* purecov: inspected */
+  }
+  return 0;
+}
+
 
 	/* ARGSUSED */
 static int
@@ -4507,7 +4543,7 @@ join_no_more_records(READ_RECORD *info __attribute__((unused)))
 
 
 static int
-join_read_next(READ_RECORD *info)
+join_read_next_same(READ_RECORD *info)
 {
   int error;
   TABLE *table= info->table;
@@ -4530,6 +4566,37 @@ join_read_next(READ_RECORD *info)
   return 0;
 }
 
+static int
+join_read_prev_same(READ_RECORD *info)
+{
+  int error;
+  TABLE *table= info->table;
+  JOIN_TAB *tab=table->reginfo.join_tab;
+
+  if ((error=table->file->index_prev(table->record[0])))
+  {
+    if (error != HA_ERR_END_OF_FILE)
+    {
+      sql_print_error("read_next: Got error %d when reading table %s",error,
+		      table->path);
+      table->file->print_error(error,MYF(0));
+      error= 1;
+    }
+    else
+    {
+      table->status= STATUS_GARBAGE;
+      error= -1;
+    }
+  }
+  else if (key_cmp(table, tab->ref.key_buff, tab->ref.key,
+		   tab->ref.key_length))
+  {
+    table->status=STATUS_NOT_FOUND;
+    error= 1;
+  }
+  return error;
+}
+
 
 static int
 join_init_quick_read_record(JOIN_TAB *tab)
@@ -4560,7 +4627,7 @@ join_init_read_record(JOIN_TAB *tab)
 }
 
 static int
-join_init_read_first_with_key(JOIN_TAB *tab)
+join_read_first(JOIN_TAB *tab)
 {
   int error;
   TABLE *table=tab->table;
@@ -4571,7 +4638,7 @@ join_init_read_first_with_key(JOIN_TAB *tab)
     table->file->extra(HA_EXTRA_KEYREAD);
   }
   tab->table->status=0;
-  tab->read_record.read_record=join_init_read_next_with_key;
+  tab->read_record.read_record=join_read_next;
   tab->read_record.table=table;
   tab->read_record.file=table->file;
   tab->read_record.index=tab->index;
@@ -4591,8 +4658,9 @@ join_init_read_first_with_key(JOIN_TAB *tab)
   return 0;
 }
 
+
 static int
-join_init_read_next_with_key(READ_RECORD *info)
+join_read_next(READ_RECORD *info)
 {
   int error=info->file->index_next(info->record);
   if (error)
@@ -4609,9 +4677,8 @@ join_init_read_next_with_key(READ_RECORD *info)
   return 0;
 }
 
-
 static int
-join_init_read_last_with_key(JOIN_TAB *tab)
+join_read_last(JOIN_TAB *tab)
 {
   TABLE *table=tab->table;
   int error;
@@ -4621,7 +4688,7 @@ join_init_read_last_with_key(JOIN_TAB *tab)
     table->file->extra(HA_EXTRA_KEYREAD);
   }
   tab->table->status=0;
-  tab->read_record.read_record=join_init_read_prev_with_key;
+  tab->read_record.read_record=join_read_prev;
   tab->read_record.table=table;
   tab->read_record.file=table->file;
   tab->read_record.index=tab->index;
@@ -4641,8 +4708,9 @@ join_init_read_last_with_key(JOIN_TAB *tab)
   return 0;
 }
 
+
 static int
-join_init_read_prev_with_key(READ_RECORD *info)
+join_read_prev(READ_RECORD *info)
 {
   int error=info->file->index_prev(info->record);
   if (error)
@@ -4659,6 +4727,7 @@ join_init_read_prev_with_key(READ_RECORD *info)
   return 0;
 }
 
+
 static int
 join_ft_read_first(JOIN_TAB *tab)
 {
@@ -4734,7 +4803,8 @@ end_send(JOIN *join, JOIN_TAB *join_tab __attribute__((unused)),
       if (join->select_options & OPTION_FOUND_ROWS)
       {
 	JOIN_TAB *jt=join->join_tab;
-	if ((join->tables == 1) && !join->tmp_table && !join->sort_and_group && !join->send_group_parts && !join->having && !jt->select_cond )
+	if ((join->tables == 1) && !join->tmp_table && !join->sort_and_group
+	    && !join->send_group_parts && !join->having && !jt->select_cond)
 	{
 	  join->select_options ^= OPTION_FOUND_ROWS;
 	  join->send_records = jt->records;
@@ -5315,6 +5385,9 @@ test_if_skip_sort_order(JOIN_TAB *tab,ORDER *order,ha_rows select_limit,
 
   if (ref_key >= 0)
   {
+    /*
+      We come here when there is a REF key.
+    */
     int order_direction;
     uint used_key_parts;
     /* Check if we get the rows in requested sorted order by using the key */
@@ -5322,11 +5395,11 @@ test_if_skip_sort_order(JOIN_TAB *tab,ORDER *order,ha_rows select_limit,
 	(order_direction = test_if_order_by_key(order,table,ref_key,
 						&used_key_parts)))
     {
-      if (order_direction == -1)
+      if (order_direction == -1)		// If ORDER BY ... DESC
       {
 	if (select && select->quick)
 	{
-	  // ORDER BY ref_key DESC
+	  // ORDER BY range_key DESC
 	  QUICK_SELECT_DESC *tmp=new QUICK_SELECT_DESC(select->quick,
 						       used_key_parts);
 	  if (!tmp || tmp->error)
@@ -5341,11 +5414,15 @@ test_if_skip_sort_order(JOIN_TAB *tab,ORDER *order,ha_rows select_limit,
 	{
 	  /*
 	    SELECT * FROM t1 WHERE a=1 ORDER BY a DESC,b DESC
-	    TODO:
-	    Add a new traversal function to read last matching row and
-	    traverse backwards.
+
+	    Use a traversal function that starts by reading the last row
+	    with key part (A) and then traverse the index backwards.
 	  */
-	  DBUG_RETURN(0);
+	  if (table->file->option_flag() & HA_NOT_READ_PREFIX_LAST)
+	    DBUG_RETURN(1);
+	  tab->read_first_record=       join_read_last_key;
+	  tab->read_record.read_record= join_read_prev_same;
+	  /* fall through */
 	}
       }
       DBUG_RETURN(1);			/* No need to sort */
@@ -5377,8 +5454,8 @@ test_if_skip_sort_order(JOIN_TAB *tab,ORDER *order,ha_rows select_limit,
 	  if (!no_changes)
 	  {
 	    tab->index=nr;
-	    tab->read_first_record=  (flag > 0 ? join_init_read_first_with_key:
-				      join_init_read_last_with_key);
+	    tab->read_first_record=  (flag > 0 ? join_read_first:
+				      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))
@@ -6369,7 +6446,8 @@ get_sort_by_table(ORDER *a,ORDER *b,TABLE_LIST *tables)
 static void
 calc_group_buffer(JOIN *join,ORDER *group)
 {
-  uint key_length=0,parts=0;
+  uint key_length=0, parts=0, null_parts=0;
+
   if (group)
     join->group= 1;
   for (; group ; group=group->next)
@@ -6390,10 +6468,11 @@ calc_group_buffer(JOIN *join,ORDER *group)
       key_length+=(*group->item)->max_length;
     parts++;
     if ((*group->item)->maybe_null)
-      key_length++;
+      null_parts++;
   }
-  join->tmp_table_param.group_length=key_length;
+  join->tmp_table_param.group_length=key_length+null_parts;
   join->tmp_table_param.group_parts=parts;
+  join->tmp_table_param.group_null_parts=null_parts;
 }
 
 
diff --git a/sql/sql_select.h b/sql/sql_select.h
index dc8c97736a5..9eb287c8845 100644
--- a/sql/sql_select.h
+++ b/sql/sql_select.h
@@ -127,12 +127,13 @@ class TMP_TABLE_PARAM {
   ha_rows end_write_records;
   uint	field_count,sum_func_count,func_count;
   uint  hidden_field_count;
-  uint	group_parts,group_length;
+  uint	group_parts,group_length,group_null_parts;
   uint	quick_group;
   bool  using_indirect_summary_function;
 
   TMP_TABLE_PARAM()
-    :copy_funcs_it(copy_funcs), copy_field(0), group_parts(0), group_length(0)
+    :copy_funcs_it(copy_funcs), copy_field(0), group_parts(0),
+    group_length(0), group_null_parts(0)
   {}
   ~TMP_TABLE_PARAM()
   {