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

6 files changed, 126 insertions, 16 deletions

diff --git a/heap/_check.c b/heap/_check.c
index 404cf22a542..03fb664cba9 100644
--- a/heap/_check.c
+++ b/heap/_check.c
@@ -79,9 +79,11 @@ static int check_one_key(HP_KEYDEF *keydef, uint keynr, ulong records,
   }
   DBUG_PRINT("info",
 	     ("records: %ld   seeks: %d   max links: %d   hitrate: %.2f",
-	      records,seek,max_links,(float) seek / (float) (records ? records : 1)));
+	      records,seek,max_links,
+	      (float) seek / (float) (records ? records : 1)));
   if (print_status)
     printf("Key: %d  records: %ld   seeks: %d   max links: %d   hitrate: %.2f\n",
-	   keynr, records, seek, max_links, (float) seek / (float) records);
+	   keynr, records, seek, max_links,
+	   (float) seek / (float) (records ? records : 1));
   return error;
 }
diff --git a/heap/heapdef.h b/heap/heapdef.h
index 40985336791..bdd7de45370 100644
--- a/heap/heapdef.h
+++ b/heap/heapdef.h
@@ -70,6 +70,7 @@ extern int _hp_rec_key_cmp(HP_KEYDEF *keydef,const byte *rec1,
 extern int _hp_key_cmp(HP_KEYDEF *keydef,const byte *rec,
 			   const byte *key);
 extern void _hp_make_key(HP_KEYDEF *keydef,byte *key,const byte *rec);
+extern my_bool hp_if_null_in_key(HP_KEYDEF *keyinfo, const byte *record);
 extern int _hp_close(register HP_INFO *info);
 extern void _hp_clear(HP_SHARE *info);
 
diff --git a/heap/hp_hash.c b/heap/hp_hash.c
index 0adbe64a070..e29e51d2b75 100644
--- a/heap/hp_hash.c
+++ b/heap/hp_hash.c
@@ -158,11 +158,22 @@ ulong _hp_hashnr(register HP_KEYDEF *keydef, register const byte *key)
   {
     uchar *pos=(uchar*) key;
     key+=seg->length;
+    if (seg->null_bit)
+    {
+      key++;					/* Skipp null byte */
+      if (*pos)					/* Found null */
+      {
+	nr^= (nr << 1) | 1;
+	continue;
+      }
+      pos++;
+    }
     if (seg->type == HA_KEYTYPE_TEXT)
     {
       for (; pos < (uchar*) key ; pos++)
       {
-	nr^=(ulong) ((((uint) nr & 63)+nr2)*((uint) my_sort_order[(uint) *pos]))+ (nr << 8);
+	nr^=(ulong) ((((uint) nr & 63)+nr2) * 
+		     ((uint) my_sort_order[(uint) *pos])) + (nr << 8);
 	nr2+=3;
       }
     }
@@ -170,7 +181,7 @@ ulong _hp_hashnr(register HP_KEYDEF *keydef, register const byte *key)
     {
       for (; pos < (uchar*) key ; pos++)
       {
-	nr^=(ulong) ((((uint) nr & 63)+nr2)*((uint) *pos))+ (nr << 8);
+	nr^=(ulong) ((((uint) nr & 63)+nr2)*((uint) *pos)) + (nr << 8);
 	nr2+=3;
       }
     }
@@ -188,11 +199,20 @@ ulong _hp_rec_hashnr(register HP_KEYDEF *keydef, register const byte *rec)
   for (seg=keydef->seg,endseg=seg+keydef->keysegs ; seg < endseg ; seg++)
   {
     uchar *pos=(uchar*) rec+seg->start,*end=pos+seg->length;
+    if (seg->null_bit)
+    {
+      if (rec[seg->null_pos] & seg->null_bit)
+      {
+	nr^= (nr << 1) | 1;
+	continue;
+      }
+    }
     if (seg->type == HA_KEYTYPE_TEXT)
     {
       for (; pos < end ; pos++)
       {
-	nr^=(ulong) ((((uint) nr & 63)+nr2)*((uint) my_sort_order[(uint) *pos]))+ (nr << 8);
+	nr^=(ulong) ((((uint) nr & 63)+nr2)*
+		     ((uint) my_sort_order[(uint) *pos]))+ (nr << 8);
 	nr2+=3;
       }
     }
@@ -234,6 +254,16 @@ ulong _hp_hashnr(register HP_KEYDEF *keydef, register const byte *key)
   {
     uchar *pos=(uchar*) key;
     key+=seg->length;
+    if (seg->null_bit)
+    {
+      key++;
+      if (*pos)
+      {
+	nr^= (nr << 1) | 1;
+	continue;
+      }
+      pos++;
+    }
     if (seg->type == HA_KEYTYPE_TEXT)
     {
       for (; pos < (uchar*) key ; pos++)
@@ -264,6 +294,14 @@ ulong _hp_rec_hashnr(register HP_KEYDEF *keydef, register const byte *rec)
   for (seg=keydef->seg,endseg=seg+keydef->keysegs ; seg < endseg ; seg++)
   {
     uchar *pos=(uchar*) rec+seg->start,*end=pos+seg->length;
+    if (seg->null_bit)
+    {
+      if (rec[seg->null_pos] & seg->null_bit)
+      {
+	nr^= (nr << 1) | 1;
+	continue;
+      }
+    }
     if (seg->type == HA_KEYTYPE_TEXT)
     {
       for ( ; pos < end ; pos++)
@@ -295,6 +333,14 @@ int _hp_rec_key_cmp(HP_KEYDEF *keydef, const byte *rec1, const byte *rec2)
 
   for (seg=keydef->seg,endseg=seg+keydef->keysegs ; seg < endseg ; seg++)
   {
+    if (seg->null_bit)
+    {
+      if ((rec1[seg->null_pos] & seg->null_bit) !=
+	  (rec2[seg->null_pos] & seg->null_bit))
+	return 1;
+      if (rec1[seg->null_pos] & seg->null_bit)
+	continue;
+    }
     if (seg->type == HA_KEYTYPE_TEXT)
     {
       if (my_sortcmp(rec1+seg->start,rec2+seg->start,seg->length))
@@ -309,14 +355,24 @@ int _hp_rec_key_cmp(HP_KEYDEF *keydef, const byte *rec1, const byte *rec2)
   return 0;
 }
 
-	/* Compare a key in a record to a hole key */
+	/* Compare a key in a record to a whole key */
 
 int _hp_key_cmp(HP_KEYDEF *keydef, const byte *rec, const byte *key)
 {
   HP_KEYSEG *seg,*endseg;
 
-  for (seg=keydef->seg,endseg=seg+keydef->keysegs ; seg < endseg ; seg++)
+  for (seg=keydef->seg,endseg=seg+keydef->keysegs ;
+       seg < endseg ;
+       key+= (seg++)->length)
   {
+    if (seg->null_bit)
+    {
+      int found_null=test(rec[seg->null_pos] & seg->null_bit);
+      if (found_null != (int) *key++)
+	return 1;
+      if (found_null)
+	continue;
+    }
     if (seg->type == HA_KEYTYPE_TEXT)
     {
       if (my_sortcmp(rec+seg->start,key,seg->length))
@@ -327,7 +383,6 @@ int _hp_key_cmp(HP_KEYDEF *keydef, const byte *rec, const byte *key)
       if (bcmp(rec+seg->start,key,seg->length))
 	return 1;
     }
-    key+=seg->length;
   }
   return 0;
 }
@@ -341,7 +396,28 @@ void _hp_make_key(HP_KEYDEF *keydef, byte *key, const byte *rec)
 
   for (seg=keydef->seg,endseg=seg+keydef->keysegs ; seg < endseg ; seg++)
   {
+    if (seg->null_bit)
+      *key++= test(rec[seg->null_pos] & seg->null_bit);
     memcpy(key,rec+seg->start,(size_t) seg->length);
     key+=seg->length;
   }
 }
+
+
+/*
+  Test if any of the key parts are NULL.
+  Return:
+    1 if any of the key parts was NULL
+    0 otherwise
+*/
+
+my_bool hp_if_null_in_key(HP_KEYDEF *keydef, const byte *record)
+{
+  HP_KEYSEG *seg,*endseg;
+  for (seg=keydef->seg,endseg=seg+keydef->keysegs ; seg < endseg ; seg++)
+  {
+    if (seg->null_bit && (record[seg->null_pos] & seg->null_bit))
+      return 1;
+  }
+  return 0;
+}
diff --git a/heap/hp_open.c b/heap/hp_open.c
index 511a63e95da..69e02945253 100644
--- a/heap/hp_open.c
+++ b/heap/hp_open.c
@@ -44,7 +44,11 @@ HP_INFO *heap_open(const char *name, int mode, uint keys, HP_KEYDEF *keydef,
       key_segs+= keydef[i].keysegs;
       bzero((char*) &keydef[i].block,sizeof(keydef[i].block));
       for (j=length=0 ; j < keydef[i].keysegs; j++)
+      {
 	length+=keydef[i].seg[j].length;
+	if (keydef[i].seg[j].null_bit)
+	  keydef[i].flag |= HA_NULL_PART_KEY;
+      }
       keydef[i].length=length;
       if (length > max_length)
 	max_length=length;
diff --git a/heap/hp_test2.c b/heap/hp_test2.c
index 458d933016f..e2570893519 100644
--- a/heap/hp_test2.c
+++ b/heap/hp_test2.c
@@ -30,7 +30,7 @@
 #include <signal.h>
 
 #define MAX_RECORDS 100000
-#define MAX_KEYS 3
+#define MAX_KEYS 4
 
 static int get_options(int argc, char *argv[]);
 static int rnd(int max_value);
@@ -40,16 +40,20 @@ static uint flag=0,verbose=0,testflag=0,recant=10000,silent=0;
 static uint keys=MAX_KEYS;
 static uint16 key1[1001];
 static my_bool key3[MAX_RECORDS];
+static int reclength=39;
+
 
 static int calc_check(byte *buf,uint length);
+static void make_record(char *record, uint n1, uint n2, uint n3,
+			const char *mark, uint count);
 
-		/* Huvudprogrammet */
+/* Main program */
 
 int main(int argc, char *argv[])
 {
   register uint i,j;
   uint ant,n1,n2,n3;
-  uint reclength,write_count,update,opt_delete,check2,dupp_keys,found_key;
+  uint write_count,update,opt_delete,check2,dupp_keys,found_key;
   int error;
   ulong pos;
   unsigned long key_check;
@@ -66,7 +70,6 @@ int main(int argc, char *argv[])
   filename2= "test2_2";
   file=file2=0;
   get_options(argc,argv);
-  reclength=37;
 
   write_count=update=opt_delete=0;
   key_check=0;
@@ -77,21 +80,33 @@ int main(int argc, char *argv[])
   keyinfo[0].seg[0].type=HA_KEYTYPE_BINARY;
   keyinfo[0].seg[0].start=0;
   keyinfo[0].seg[0].length=6;
+  keyinfo[0].seg[0].null_bit=0;
   keyinfo[1].seg=keyseg+1;
   keyinfo[1].keysegs=2;
   keyinfo[1].flag=0;
   keyinfo[1].seg[0].type=HA_KEYTYPE_BINARY;
   keyinfo[1].seg[0].start=7;
   keyinfo[1].seg[0].length=6;
+  keyinfo[1].seg[0].null_bit=0;
   keyinfo[1].seg[1].type=HA_KEYTYPE_TEXT;
-  keyinfo[1].seg[1].start=0;			/* Tv}delad nyckel */
+  keyinfo[1].seg[1].start=0;			/* key in two parts */
   keyinfo[1].seg[1].length=6;
+  keyinfo[1].seg[1].null_bit=0;
   keyinfo[2].seg=keyseg+3;
   keyinfo[2].keysegs=1;
   keyinfo[2].flag=HA_NOSAME;
   keyinfo[2].seg[0].type=HA_KEYTYPE_BINARY;
   keyinfo[2].seg[0].start=12;
   keyinfo[2].seg[0].length=8;
+  keyinfo[2].seg[0].null_bit=0;
+  keyinfo[3].keysegs=1;
+  keyinfo[3].flag=HA_NOSAME;
+  keyinfo[3].seg=keyseg+4;
+  keyinfo[3].seg[0].type=HA_KEYTYPE_BINARY;
+  keyinfo[3].seg[0].start=37;
+  keyinfo[3].seg[0].length=1;
+  keyinfo[3].seg[0].null_bit=1;
+  keyinfo[3].seg[0].null_pos=38;
 
   bzero((char*) key1,sizeof(key1));
   bzero((char*) key3,sizeof(key3));
@@ -110,7 +125,7 @@ int main(int argc, char *argv[])
   for (i=0 ; i < recant ; i++)
   {
     n1=rnd(1000); n2=rnd(100); n3=rnd(min(recant*5,MAX_RECORDS));
-    sprintf(record,"%6d:%4d:%8d:Pos: %4d          ",n1,n2,n3,write_count);
+    make_record(record,n1,n2,n3,"Pos",write_count);
 
     if (heap_write(file,record))
     {
@@ -191,7 +206,7 @@ int main(int argc, char *argv[])
   for (i=0 ; i < write_count/10 ; i++)
   {
     n1=rnd(1000); n2=rnd(100); n3=rnd(min(recant*2,MAX_RECORDS));
-    sprintf(record2,"%6d:%4d:%8d:XXX: %4d          ",n1,n2,n3,update);
+    make_record(record2, n1, n2, n3, "XXX", update);
     if (rnd(2) == 1)
     {
       if (heap_scan_init(file))
@@ -654,3 +669,13 @@ static int calc_check(byte *buf, uint length)
     check+= (int) (uchar) *(buf++);
   return check;
 }
+
+static void make_record(char *record, uint n1, uint n2, uint n3,
+			const char *mark, uint count)
+{
+  bfill(record,reclength,' ');
+  sprintf(record,"%6d:%4d:%8d:%3.3s: %4d",
+	  n1,n2,n3,mark,count);
+  record[37]='A';				/* Store A in null key */
+  record[38]=1;					/* set as null */
+}
diff --git a/heap/hp_write.c b/heap/hp_write.c
index 0d68bb96580..a219c8be23a 100644
--- a/heap/hp_write.c
+++ b/heap/hp_write.c
@@ -239,7 +239,9 @@ int _hp_write_key(register HP_SHARE *info, HP_KEYDEF *keyinfo,
     }
 
     /* Check if dupplicated keys */
-    if ((keyinfo->flag & HA_NOSAME) && pos == gpos)
+    if ((keyinfo->flag & HA_NOSAME) && pos == gpos &&
+	(!(keyinfo->flag & HA_NULL_PART_KEY) ||
+	 !hp_if_null_in_key(keyinfo, record)))
     {
       pos=empty;
       do