func_group.result, func_group.test:

  Added tests for extended max/min optimization
opt_sum.cc:
  Extended min/max optimization


sql/opt_sum.cc:
  Extended min/max optimization
mysql-test/t/func_group.test:
  Added tests for extended max/min optimization
mysql-test/r/func_group.result:
  Added tests for extended max/min optimization

1 files changed, 615 insertions, 285 deletions

diff --git a/sql/opt_sum.cc b/sql/opt_sum.cc
index 03dcfbeda28..110509b78ef 100644
--- a/sql/opt_sum.cc
+++ b/sql/opt_sum.cc
@@ -15,27 +15,59 @@
    Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA  02111-1307  USA */
 
 
-/* Optimizing of many different type of queries with GROUP functions */
+/*
+  Optimising of MIN(), MAX() and COUNT(*) queries without 'group by' clause
+  by replacing the aggregate expression with a constant.  
+
+  Given a table with a compound key on columns (a,b,c), the following
+  types of queries are optimised (assuming the table handler supports
+  the required methods)
+
+  SELECT COUNT(*) FROM t1[,t2,t3,...]
+  SELECT MIN(b) FROM t1 WHERE a=const
+  SELECT MAX(c) FROM t1 WHERE a=const AND b=const
+  SELECT MAX(b) FROM t1 WHERE a=const AND b<const
+  SELECT MIN(b) FROM t1 WHERE a=const AND b>const
+  SELECT MIN(b) FROM t1 WHERE a=const AND b BETWEEN const AND const
+  SELECT MAX(b) FROM t1 WHERE a=const AND b BETWEEN const AND const
+
+  Instead of '<' one can use '<=', '>', '>=' and '=' as well.
+  Instead of 'a=const' the condition 'a IS NULL' can be used.
+
+  If all selected fields are replaced then we will also remove all
+  involved tables and return the answer without any join. Thus, the
+  following query will be replaced with a row of two constants:
+  SELECT MAX(b), MIN(d) FROM t1,t2 
+    WHERE a=const AND b<const AND d>const
+  (assuming a index for column d of table t2 is defined)
+
+*/
 
 #include "mysql_priv.h"
 #include "sql_select.h"
 
-static bool find_range_key(TABLE_REF *ref, Field* field,COND *cond);
+static bool find_key_for_maxmin(bool max_fl, TABLE_REF *ref,
+                                Field* field, COND *cond,
+                                uint *range_fl, uint *key_prefix_length);
+static int reckey_in_range(bool max_fl, TABLE_REF *ref, Field* field,
+                            COND *cond, uint range_fl, uint prefix_len);
+static int maxmin_in_range(bool max_fl, Field* field, COND *cond);
+
 
 /*
   Substitutes constants for some COUNT(), MIN() and MAX() functions.
 
   SYNOPSIS
     opt_sum_query()
-    tables		Tables in query
-    all_fields		All fields to be returned
-    conds		WHERE clause
+    tables                Tables in query
+    all_fields                All fields to be returned
+    conds                WHERE clause
 
   NOTE:
     This function is only called for queries with sum functions and no
     GROUP BY part.
 
- RETURN VALUES
+  RETURN VALUES
     0 No errors
     1 if all items was resolved
    -1 on impossible  conditions
@@ -62,13 +94,13 @@ int opt_sum_query(TABLE_LIST *tables, List<Item> &all_fields,COND *conds)
       outer_tables|= tl->table->map;
 
       /*
-	We can't optimise LEFT JOIN in cases where the WHERE condition
-	restricts the table that is used, like in:
+        We can't optimise LEFT JOIN in cases where the WHERE condition
+        restricts the table that is used, like in:
           SELECT MAX(t1.a) FROM t1 LEFT JOIN t2 join-condition
-	  WHERE t2.field IS NULL;
+          WHERE t2.field IS NULL;
       */
       if (tl->table->map & where_tables)
-	return 0;
+        return 0;
     }
     else
       used_tables|= tl->table->map;
@@ -86,350 +118,648 @@ int opt_sum_query(TABLE_LIST *tables, List<Item> &all_fields,COND *conds)
       Item_sum *item_sum= (((Item_sum*) item));
       switch (item_sum->sum_func()) {
       case Item_sum::COUNT_FUNC:
-	/*
-	  If the expr in count(expr) can never be null we can change this
-	  to the number of rows in the tables
-	*/
-	if (!conds && !((Item_sum_count*) item)->args[0]->maybe_null)
-	{
-	  longlong count=1;
-	  TABLE_LIST *table;
-	  for (table=tables; table ; table=table->next)
-	  {
-	    if (outer_tables || (table->table->file->table_flags() &
-				 HA_NOT_EXACT_COUNT))
-	    {
-	      const_result=0;			// Can't optimize left join
-	      break;
-	    }
-	    tables->table->file->info(HA_STATUS_VARIABLE | HA_STATUS_NO_LOCK);
-	    count*= table->table->file->records;
-	  }
-	  if (!table)
-	  {
-	    ((Item_sum_count*) item)->make_const(count);
-	    recalc_const_item=1;
-	  }
-	}
-	else
-	  const_result=0;
-	break;
+        /*
+          If the expr in count(expr) can never be null we can change this
+          to the number of rows in the tables
+        */
+        if (!conds && !((Item_sum_count*) item)->args[0]->maybe_null)
+        {
+          longlong count= 1;
+          TABLE_LIST *table;
+          for (table=tables ; table ; table=table->next)
+          {
+            if (outer_tables || (table->table->file->table_flags() &
+                                 HA_NOT_EXACT_COUNT))
+            {
+              const_result= 0;                        // Can't optimize left join
+              break;
+            }
+            tables->table->file->info(HA_STATUS_VARIABLE | HA_STATUS_NO_LOCK);
+            count*= table->table->file->records;
+          }
+          if (!table)
+          {
+            ((Item_sum_count*) item)->make_const(count);
+            recalc_const_item= 1;
+          }
+        }
+        else
+          const_result= 0;
+        break;
       case Item_sum::MIN_FUNC:
       {
-	/*
-	  If MIN(expr) is the first part of a key or if all previous
-	  parts of the key is found in the COND, then we can use
-	  indexes to find the key.
-	*/
-	Item *expr=item_sum->args[0];
-	if (expr->type() == Item::FIELD_ITEM)
-	{
-	  byte key_buff[MAX_KEY_LENGTH];
-	  TABLE_REF ref;
-	  ref.key_buff=key_buff;
-	  Item_field *item_field= ((Item_field*) expr);
-	  TABLE *table= item_field->field->table;
-
-	  if ((outer_tables & table->map) ||
-	      (!find_range_key(&ref, item_field->field,conds)))
-	  {
-	    const_result=0;
-	    break;
-	  }
-	  bool error= table->file->index_init((uint) ref.key);
-	  enum ha_rkey_function find_flag= HA_READ_KEY_OR_NEXT; 
-	  uint prefix_len= ref.key_length;
-	  /*
-	    If we are doing MIN() on a column with NULL fields
-	    we must read the key after the NULL column
-	  */
-	  if (item_field->field->null_bit)
-	  {
-	    ref.key_buff[ref.key_length++]=1;
-	    find_flag= HA_READ_AFTER_KEY;
-	  }
-
-	  if (!ref.key_length)
-	    error=table->file->index_first(table->record[0]) !=0;
-	  else
-	    error=table->file->index_read(table->record[0],key_buff,
-					  ref.key_length,
-					  find_flag) ||
-	      key_cmp(table, key_buff, ref.key, prefix_len);
-	  if (table->key_read)
-	  {
-	    table->key_read=0;
-	    table->file->extra(HA_EXTRA_NO_KEYREAD);
-	  }
-	  table->file->index_end();
-	  if (error)
-	    return -1;				// No rows matching where
-	  removed_tables|= table->map;
-	}
-	else if (!expr->const_item())		// This is VERY seldom false
-	{
-	  const_result=0;
-	  break;
-	}
-	((Item_sum_min*) item_sum)->reset();
-	((Item_sum_min*) item_sum)->make_const();
-	recalc_const_item=1;
-	break;
+        /*
+          If MIN(expr) is the first part of a key or if all previous
+          parts of the key is found in the COND, then we can use
+          indexes to find the key.
+        */
+        Item *expr=item_sum->args[0];
+        if (expr->type() == Item::FIELD_ITEM)
+        {
+          byte key_buff[MAX_KEY_LENGTH];
+          TABLE_REF ref;
+          uint range_fl, prefix_len;
+
+          ref.key_buff= key_buff;
+          Item_field *item_field= ((Item_field*) expr);
+          TABLE *table= item_field->field->table;
+
+          /* 
+            Look for a partial key that can be used for optimization.
+            If we succeed, ref.key_length will contain the length of
+            this key, while prefix_len will contain the length of 
+            the beginning of this key without field used in MIN() 
+          */
+          if ((outer_tables & table->map) ||
+              !find_key_for_maxmin(0, &ref, item_field->field, conds,
+                                   &range_fl, &prefix_len))
+          {
+            const_result= 0;
+            break;
+          }
+          bool error= table->file->index_init((uint) ref.key);
+          enum ha_rkey_function find_flag= range_fl & NEAR_MIN ?
+                              HA_READ_AFTER_KEY : HA_READ_KEY_OR_NEXT; 
+          /*
+            If we are doing MIN() on a column with NULL fields
+            we must read the key after the NULL column
+          */
+          if (item_field->field->null_bit)
+          {
+            ref.key_buff[ref.key_length++]= 1;
+            find_flag= HA_READ_AFTER_KEY;
+          }
+
+          if (!ref.key_length)
+            error= table->file->index_first(table->record[0]) != 0;
+          else
+            error= table->file->index_read(table->record[0], key_buff,
+                                          ref.key_length,
+                                          find_flag) ||
+                   reckey_in_range(0, &ref, item_field->field, 
+                                   conds, range_fl, prefix_len); 
+          if (table->key_read)
+          {
+            table->key_read= 0;
+            table->file->extra(HA_EXTRA_NO_KEYREAD);
+          }
+          table->file->index_end();
+          if (error)
+            return -1;                                // No rows matching where
+          removed_tables|= table->map;
+        }
+        else if (!expr->const_item())                // This is VERY seldom false
+        {
+          const_result= 0;
+          break;
+        }
+        ((Item_sum_min*) item_sum)->reset();
+        ((Item_sum_min*) item_sum)->make_const();
+        recalc_const_item= 1;
+        break;
       }
       case Item_sum::MAX_FUNC:
       {
-	/*
-	  If MAX(expr) is the first part of a key or if all previous
-	  parts of the key is found in the COND, then we can use
-	  indexes to find the key.
-	*/
-	Item *expr=item_sum->args[0];
-	if (expr->type() == Item::FIELD_ITEM)
-	{
-	  byte key_buff[MAX_KEY_LENGTH];
-	  TABLE_REF ref;
-	  ref.key_buff=key_buff;
-	  TABLE *table=((Item_field*) expr)->field->table;
-
-	  if ((outer_tables & table->map) ||
-	      !find_range_key(&ref, ((Item_field*) expr)->field,conds))
-	  {
-	    const_result=0;
-	    break;
-	  }
-	  if ((table->file->table_flags() & HA_NOT_READ_AFTER_KEY))
-	  {
-	    const_result=0;
-	    break;
-	  }
-	  bool error=table->file->index_init((uint) ref.key);
-
-	  if (!ref.key_length)
-	    error=table->file->index_last(table->record[0]) !=0;
-	  else
-	  {
-	    error = table->file->index_read(table->record[0], key_buff,
-					  ref.key_length,
-					  HA_READ_PREFIX_LAST) ||
-	      key_cmp(table,key_buff,ref.key,ref.key_length);
-	  }
-	  if (table->key_read)
-	  {
-	    table->key_read=0;
-	    table->file->extra(HA_EXTRA_NO_KEYREAD);
-	  }
-	  table->file->index_end();
-	  if (error)
-	    return -1;				// Impossible query
-	  removed_tables|= table->map;
-	}
-	else if (!expr->const_item())		// This is VERY seldom false
-	{
-	  const_result=0;
-	  break;
-	}
-	((Item_sum_min*) item_sum)->reset();
-	((Item_sum_min*) item_sum)->make_const();
-	recalc_const_item=1;
-	break;
+        /*
+          If MAX(expr) is the first part of a key or if all previous
+          parts of the key is found in the COND, then we can use
+          indexes to find the key.
+        */
+        Item *expr=item_sum->args[0];
+        if (expr->type() == Item::FIELD_ITEM)
+        {
+          byte key_buff[MAX_KEY_LENGTH];
+          TABLE_REF ref;
+	      uint range_fl, prefix_len;
+
+          ref.key_buff= key_buff;
+	      Item_field *item_field= ((Item_field*) expr);
+          TABLE *table= item_field->field->table;
+
+          /* 
+            Look for a partial key that can be used for optimization.
+            If we succeed, ref.key_length will contain the length of
+            this key, while prefix_len will contain the length of 
+            the beginning of this key without field used in MAX() 
+          */
+          if ((outer_tables & table->map) ||
+	          !find_key_for_maxmin(1, &ref, item_field->field, conds,
+				                   &range_fl, &prefix_len))
+          {
+            const_result= 0;
+            break;
+          }
+          if ((table->file->table_flags() & HA_NOT_READ_AFTER_KEY))
+          {
+            const_result= 0;
+            break;
+          }
+          bool error= table->file->index_init((uint) ref.key);
+
+          if (!ref.key_length)
+            error=table->file->index_last(table->record[0]) != 0;
+          else
+	        error= table->file->index_read(table->record[0], key_buff,
+					                       ref.key_length,
+					                       range_fl & NEAR_MAX ?
+					                       HA_READ_BEFORE_KEY :
+					                       HA_READ_PREFIX_LAST_OR_PREV) ||
+                   reckey_in_range(1, &ref, item_field->field, 
+                                   conds, range_fl, prefix_len); 
+          if (table->key_read)
+          {
+            table->key_read=0;
+            table->file->extra(HA_EXTRA_NO_KEYREAD);
+          }
+          table->file->index_end();
+          if (error)
+            return -1;                                // Impossible query
+          removed_tables|= table->map;
+        }
+        else if (!expr->const_item())                // This is VERY seldom false
+        {
+          const_result= 0;
+          break;
+        }
+        ((Item_sum_min*) item_sum)->reset();
+        ((Item_sum_min*) item_sum)->make_const();
+        recalc_const_item= 1;
+        break;
       }
       default:
-	const_result=0;
-	break;
+        const_result= 0;
+        break;
       }
     }
     else if (const_result)
     {
       if (recalc_const_item)
-	item->update_used_tables();
+        item->update_used_tables();
       if (!item->const_item())
-	const_result=0;
+        const_result= 0;
     }
   }
   /*
     If we have a where clause, we can only ignore searching in the
     tables if MIN/MAX optimisation replaced all used tables
-    This is to not to use replaced values in case of:
+    We do not use replaced values in case of:
     SELECT MIN(key) FROM table_1, empty_table
     removed_tables is != 0 if we have used MIN() or MAX().
   */
   if (removed_tables && used_tables != removed_tables)
-    const_result= 0;				// We didn't remove all tables
+    const_result= 0;                                // We didn't remove all tables
   return const_result;
 }
 
-/* Count in how many times table is used (up to MAX_KEY_PARTS+1) */
 
-uint count_table_entries(COND *cond,TABLE *table)
-{
-  if (cond->type() == Item::COND_ITEM)
-  {
-    if (((Item_cond*) cond)->functype() == Item_func::COND_OR_FUNC)
-      return (cond->used_tables() & table->map) ? MAX_REF_PARTS+1 : 0;
+/*
+  Test if the predicate compares a field with constants
 
-    List_iterator_fast<Item> li(*((Item_cond*) cond)->argument_list());
-    Item *item;
-    uint count=0;
-    while ((item=li++))
+  SYNOPSIS
+    simple_pred()
+    func_item   in:  Predicate item
+    args        out: Here we store the field followed by constants
+    inv_order   out: Is set to 1 if the predicate is of the form 'const op field' 
+
+  RETURN
+    0        func_item is a simple predicate: a field is compared with constants
+    1        Otherwise
+*/
+
+static bool simple_pred(Item_func *func_item, Item **args, bool *inv_order)
+{
+  Item *item;
+  *inv_order= 0;
+  switch (func_item->argument_count()) {
+  case 1:
+    /* field IS NULL */
+    item= func_item->arguments()[0];
+    if (item->type() != Item::FIELD_ITEM)
+      return 0;
+    args[0]= item;
+    break;
+  case 2:
+    /* 'field op const' or 'const op field' */
+    item= func_item->arguments()[0];
+    if (item->type() == Item::FIELD_ITEM)
     {
-      if ((count+=count_table_entries(item,table)) > MAX_REF_PARTS)
-	return MAX_REF_PARTS+1;
+      args[0]= item;
+      item= func_item->arguments()[1];
+      if (!item->const_item())
+        return 0;
+      args[1]= item;
     }
-    return count;
-  }
-  if (cond->type() == Item::FUNC_ITEM &&
-      (((Item_func*) cond)->functype() == Item_func::EQ_FUNC ||
-       (((Item_func*) cond)->functype() == Item_func::EQUAL_FUNC)) &&
-      cond->used_tables() == table->map)
-  {
-    Item *left_item=	((Item_func*) cond)->arguments()[0];
-    Item *right_item= ((Item_func*) cond)->arguments()[1];
-    if (left_item->type() == Item::FIELD_ITEM)
+    else if (item->const_item())
     {
-      if (!(((Item_field*) left_item)->field->flags & PART_KEY_FLAG) ||
-	  !right_item->const_item())
-	return MAX_REF_PARTS+1;
-      return 1;
+      args[1]= item;
+      item= func_item->arguments()[1];
+      if (item->type() != Item::FIELD_ITEM)
+        return 0;
+      args[0]= item;
+      *inv_order= 1;
     }
-    if (right_item->type() == Item::FIELD_ITEM)
+    else
+      return 0;
+    break;
+  case 3:
+    /* field BETWEEN const AND const */
+    item= func_item->arguments()[0];
+    if (item->type() == Item::FIELD_ITEM)
     {
-      if (!(((Item_field*) right_item)->field->flags & PART_KEY_FLAG) ||
-	  !left_item->const_item())
-	return MAX_REF_PARTS+1;
-      return 1;
+      args[0]= item;
+      for (int i= 1 ; i <= 2; i++)
+      {
+        item= func_item->arguments()[i];
+        if (!item->const_item())
+          return 0;
+        args[i]= item;
+      }
     }
+    else
+      return 0;
   }
-  return (cond->used_tables() & table->map) ? MAX_REF_PARTS+1 : 0;
+  return 1;
 }
 
 
-/* check that the field is usable as key part */
+/* 
+   Check whether a condition matches a key to get {MAX|MIN}(field):
+
+   SYNOPSIS
+     matching_cond()
+     max_fl         in:     Set to 1 if we are optimising MAX()              
+     ref            in/out: Reference to the structure we store the key value
+     keyinfo        in      Reference to the key info
+     field_part     in:     Pointer to the key part for the field
+     cond           in      WHERE condition
+     key_part_used  in/out: Map of matchings parts
+     range_fl       in/out: Says whether including key will be used
+     prefix_len     out:    Length of common key part for the range
+                            where MAX/MIN is searched for
+
+   DESCRIPTION
+     For the index specified by the keyinfo parameter, index that
+     contains field as its component (field_part), the function
+     checks whether the condition cond is a conjunction and all its
+     conjuncts referring to the columns of the same table as column
+     field are one of the following forms:
+     - f_i= const_i or const_i= f_i or f_i is null,
+       where f_i is part of the index
+     - field {<|<=|>=|>|=} const or const {<|<=|>=|>|=} field
+     - field between const1 and const2
+
+  RETURN
+    0        Index can't be used.
+    1        We can use index to get MIN/MAX value
+*/
 
-bool part_of_cond(COND *cond,Field *field)
+static bool matching_cond(bool max_fl, TABLE_REF *ref, KEY *keyinfo, 
+                          KEY_PART_INFO *field_part, COND *cond,
+                          key_part_map *key_part_used, uint *range_fl,
+                          uint *prefix_len)
 {
+  if (!cond)
+    return 1;
+  Field *field= field_part->field;
+  if (!(cond->used_tables() & field->table->map))
+  {
+    /* Condition doesn't restrict the used table */
+    return 1;
+  }
   if (cond->type() == Item::COND_ITEM)
   {
     if (((Item_cond*) cond)->functype() == Item_func::COND_OR_FUNC)
-      return 0;					// Already checked
+      return 0;
 
+    /* AND */
     List_iterator_fast<Item> li(*((Item_cond*) cond)->argument_list());
     Item *item;
-    while ((item=li++))
+    while ((item= li++))
     {
-      if (part_of_cond(item,field))
-	return 1;
+      if (!matching_cond(max_fl, ref, keyinfo, field_part, item,
+                         key_part_used, range_fl, prefix_len))
+        return 0;
     }
+    return 1;
+  }
+
+  if (cond->type() != Item::FUNC_ITEM)
+    return 0;                                 // Not operator, can't optimize
+
+  bool eq_type= 0;                            // =, <=> or IS NULL
+  bool noeq_type= 0;                          // < or >  
+  bool less_fl= 0;                            // < or <= 
+  bool is_null= 0;
+  bool between= 0;
+
+  switch (((Item_func*) cond)->functype()) {
+  case Item_func::ISNULL_FUNC:
+    is_null= 1;     /* fall through */
+  case Item_func::EQ_FUNC:
+  case Item_func::EQUAL_FUNC:
+    eq_type= 1;
+    break;
+  case Item_func::LT_FUNC:
+    noeq_type= 1;   /* fall through */
+  case Item_func::LE_FUNC:
+    less_fl= 1;      
+    break;
+  case Item_func::GT_FUNC:
+    noeq_type= 1;   /* fall through */
+  case Item_func::GE_FUNC:
+    break;
+  case Item_func::BETWEEN:
+    between= 1;
+    break;
+  default:
+    return 0;                                        // Can't optimize function
+  }
+  
+  Item *args[3];
+  bool inv;
+
+  /* Test if this is a comparison of a field and constant */
+  if (!simple_pred((Item_func*) cond, args, &inv))
+    return 0;
+
+  if (inv && !eq_type)
+    less_fl= 1-less_fl;                         // Convert '<' -> '>' (etc)
+
+  /* Check if field is part of the tested partial key */
+  byte *key_ptr= ref->key_buff;
+  KEY_PART_INFO *part;
+  for (part= keyinfo->key_part;
+       ;
+       key_ptr+= part++->store_length)
+
+  {
+    if (part > field_part)
+      return 0;                     // Field is beyond the tested parts
+    if (part->field->eq(((Item_field*) args[0])->field))
+      break;                        // Found a part od the key for the field
+  }
+
+  bool is_field_part= part == field_part;
+  if (!(is_field_part || eq_type))
     return 0;
+
+  key_part_map org_key_part_used= *key_part_used;
+  if (eq_type || between || max_fl == less_fl)
+  {
+    uint length= (key_ptr-ref->key_buff)+part->store_length;
+    if (ref->key_length < length)
+    /* Ultimately ref->key_length will contain the length of the search key */
+      ref->key_length= length;      
+    if (!*prefix_len && part+1 == field_part)       
+      *prefix_len= length;
+    if (is_field_part && eq_type)
+      *prefix_len= ref->key_length;
+  
+    *key_part_used|= (key_part_map) 1 << (part - keyinfo->key_part);
   }
-  if (cond->type() == Item::FUNC_ITEM &&
-      (((Item_func*) cond)->functype() == Item_func::EQ_FUNC ||
-       ((Item_func*) cond)->functype() == Item_func::EQUAL_FUNC) &&
-      cond->used_tables() == field->table->map)
+
+  if (org_key_part_used != *key_part_used ||
+      (is_field_part && 
+       (between || max_fl == less_fl) && !cond->val_int()))
   {
-    Item *left_item=	((Item_func*) cond)->arguments()[0];
-    Item *right_item= ((Item_func*) cond)->arguments()[1];
-    if (left_item->type() == Item::FIELD_ITEM)
+    /*
+      It's the first predicate for this part or a predicate of the
+      following form  that moves upper/lower bounds for max/min values:
+      - field BETWEEN const AND const
+      - field {<|<=} const, when searching for MAX
+      - field {>|>=} const, when searching for MIN
+    */
+
+    if (is_null)
     {
-      if (((Item_field*) left_item)->field != field ||
-	  !right_item->const_item())
-	return 0;
+      part->field->set_null();
+      *key_ptr= (byte) 1;
     }
-    else if (right_item->type() == Item::FIELD_ITEM)
+    else
     {
-      if (((Item_field*) right_item)->field != field ||
-	  !left_item->const_item())
-	return 0;
-      right_item=left_item;			// const item in right
+      store_val_in_field(part->field, args[between && max_fl ? 2 : 1]);
+      if (part->null_bit) 
+        *key_ptr++= (byte) test(part->field->is_null());
+      part->field->get_key_image((char*) key_ptr, part->length,
+                                 part->field->charset(), Field::itRAW);
+    }
+    if (is_field_part)
+    {
+      if (between)
+        *range_fl&= ~(NO_MAX_RANGE | NO_MIN_RANGE);
+      else
+      {
+        *range_fl&= ~(max_fl ? NO_MAX_RANGE : NO_MIN_RANGE);
+        if (noeq_type)
+          *range_fl|=  (max_fl ? NEAR_MAX : NEAR_MIN);
+        else
+          *range_fl&= ~(max_fl ? NEAR_MAX : NEAR_MIN);
+      }
     }
-    store_val_in_field(field,right_item);
-    return 1;
   }
-  return 0;
+  else if (eq_type)
+  {
+    if (!is_null && !cond->val_int() ||
+        is_null && !test(part->field->is_null()))  
+     return 0;                       // Impossible test
+  }
+  else if (is_field_part)
+    *range_fl&= ~(max_fl ? NO_MIN_RANGE : NO_MAX_RANGE);
+  return 1;  
 }
 
 
-/* Check if we can get value for field by using a key */
+/*
+  Check whether we can get value for {max|min}(field) by using a key.
 
-static bool find_range_key(TABLE_REF *ref, Field* field, COND *cond)
+  SYNOPSIS
+    find_key_for_maxmin()
+    max_fl      in:     0 for MIN(field) / 1 for MAX(field)
+    ref         in/out  Reference to the structure we store the key value
+    field       in:     Field used inside MIN() / MAX()
+    cond        in:     WHERE condition
+    range_fl    in/out  Bit flags for how to search if key is ok
+    prefix_len  out:    Length of prefix for the search range
+
+  DESCRIPTION
+    If where condition is not a conjunction of 0 or more conjuct the
+    function returns false, otherwise it checks whether there is an
+    index including field as its k-th component/part such that:
+
+     1. for each previous component f_i there is one and only one conjunct
+        of the form: f_i= const_i or const_i= f_i or f_i is null
+     2. references to field occur only in conjucts of the form:
+        field {<|<=|>=|>|=} const or const {<|<=|>=|>|=} field or 
+        field BETWEEN const1 AND const2
+     3. all references to the columns from the same table as column field
+        occur only in conjucts mentioned above.
+
+     If such an index exists the function through the ref parameter
+     returns the key value to find max/min for the field using the index,
+     the length of first (k-1) components of the key and flags saying
+     how to apply the key for the search max/min value.
+     (if we have a condition field = const, prefix_len contains the length
+      of the whole search key)
+
+  RETURN
+    0   Index can not be used to optimize MIN(field)/MAX(field)
+    1   Can use key to optimize MIN()/MAX()
+        In this case ref, range_fl and prefix_len are updated
+*/ 
+      
+static bool find_key_for_maxmin(bool max_fl, TABLE_REF *ref,
+                                Field* field, COND *cond,
+                                uint *range_fl, uint *prefix_len)
 {
   if (!(field->flags & PART_KEY_FLAG))
-    return 0;				// Not part of a key. Skip it
+    return 0;                                        // Not key field
+  *prefix_len= 0;
+  
+  TABLE *table= field->table;
+  uint idx= 0;
 
-  TABLE *table=field->table;
-  uint idx=0;
-
-  /* Check if some key has field as first key part */
-  if ((field->key_start & field->table->keys_in_use_for_query) &&
-      (! cond || ! (cond->used_tables() & table->map)))
-  {
-    for (key_map key=field->key_start ;;) 
-    {
-      for (; !(key & 1) ; idx++)
-	key>>=1;
-      if (!(table->file->index_flags(idx) & HA_WRONG_ASCII_ORDER))
-	break;					// Key is ok
-      /* Can't use this key, for looking up min() or max(), end if last one */
-      if (key == 1)
-	return 0;
-    }
-    ref->key_length=0;
-    ref->key=idx;
-    if (field->part_of_key & ((key_map) 1 << idx))
+  KEY *keyinfo,*keyinfo_end;
+  for (keyinfo= table->key_info, keyinfo_end= keyinfo+table->keys ;
+       keyinfo != keyinfo_end;
+       keyinfo++,idx++)
+  {      
+    if (table->file->index_flags(idx) & HA_WRONG_ASCII_ORDER)
+      break;
+
+    KEY_PART_INFO *part,*part_end;
+    key_part_map key_part_to_use= 0;
+    for (part= keyinfo->key_part, part_end= part+keyinfo->key_parts ;
+         part != part_end ;
+         part++, key_part_to_use= (key_part_to_use << 1) | 1)
     {
-      table->key_read=1;
-      table->file->extra(HA_EXTRA_KEYREAD);
+      if (field->eq(part->field))
+      {
+        ref->key= idx;
+        ref->key_length= 0;
+        key_part_map key_part_used= 0;
+        *range_fl= NO_MIN_RANGE | NO_MAX_RANGE;
+        if (matching_cond(max_fl, ref, keyinfo, part, cond,
+                          &key_part_used, range_fl, prefix_len) &&
+            !(key_part_to_use & ~key_part_used))
+        {
+          if (!max_fl && key_part_used == key_part_to_use && part->null_bit)
+          {
+            /*
+              SELECT MIN(key_part2) FROM t1 WHERE key_part1=const
+              If key_part2 may be NULL, then we want to find the first row
+              that is not null
+            */
+            ref->key_buff[ref->key_length++]= 1;
+            *range_fl&= ~NO_MIN_RANGE;
+            *range_fl|= NEAR_MIN;                // > NULL
+          }
+          /*
+            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))
+          {
+            table->key_read= 1;
+            table->file->extra(HA_EXTRA_KEYREAD);
+          }
+          return 1;
+        }
+      }
     }
-    return 1;					// Ok to use key
   }
-  /*
-  ** Check if WHERE consist of exactly the previous key parts for some key
-  */
-  if (!cond)
-    return 0;
-  uint table_entries= count_table_entries(cond,table);
-  if (!table_entries || table_entries > MAX_REF_PARTS)
+  return 0;
+}
+
+        
+/*
+  Check whether found key is in range specified by conditions
+
+  SYNOPSIS
+    reckey_in_range()
+    max_fl      in:     0 for MIN(field) / 1 for MAX(field)
+    ref         in:     Reference to the key value and info
+    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 
+
+  RETURN
+    0        ok
+    1        WHERE was not true for the found row
+*/
+
+static int reckey_in_range(bool max_fl, TABLE_REF *ref, Field* field,
+                            COND *cond, uint range_fl, uint prefix_len)
+{
+  if (key_cmp(field->table, ref->key_buff, ref->key, prefix_len))
+    return 1;
+  if (!cond || (range_fl & (max_fl ? NO_MIN_RANGE : NO_MAX_RANGE)))
     return 0;
+  return maxmin_in_range(max_fl, field, cond);
+}
 
-  KEY *keyinfo,*keyinfo_end;
-  idx=0;
-  for (keyinfo=table->key_info, keyinfo_end=keyinfo+table->keys ;
-       keyinfo != keyinfo_end;
-       keyinfo++,idx++)
+
+/*
+  Check whether {MAX|MIN}(field) is in range specified by conditions
+  SYNOPSIS
+    maxmin_in_range()
+    max_fl      in:     0 for MIN(field) / 1 for MAX(field)
+    field       in:     Field used the MIN/MAX expression
+    cond        in:     WHERE condition
+
+  RETURN
+    0        ok
+    1        WHERE was not true for the found row
+*/
+
+static int maxmin_in_range(bool max_fl, Field* field, COND *cond)
+{
+  /* If AND/OR condition */
+  if (cond->type() == Item::COND_ITEM)
   {
-    if (table_entries < keyinfo->key_parts)
+    List_iterator_fast<Item> li(*((Item_cond*) cond)->argument_list());
+    Item *item;
+    while ((item= li++))
     {
-      byte *key_ptr=ref->key_buff;
-      KEY_PART_INFO *part,*part_end;
-      int left_length=MAX_KEY_LENGTH;
-
-      for (part=keyinfo->key_part, part_end=part+table_entries ;
-	   part != part_end ;
-	   part++)
-      {
-	if (!part_of_cond(cond,part->field) ||
-	    left_length < part->store_length ||
-	    (table->file->index_flags(idx) & HA_WRONG_ASCII_ORDER))
-	  break;
-	// Save found constant
-	if (part->null_bit)
-	  *key_ptr++= (byte) test(part->field->is_null());
-        part->field->get_key_image((char*) key_ptr,part->length, 
-				   part->field->charset(), Field::itRAW);
-	key_ptr+=part->store_length - test(part->null_bit);
-	left_length-=part->store_length;
-      }
-      if (part == part_end && part->field == field)
-      {
-	ref->key_length= (uint) (key_ptr-ref->key_buff);
-	ref->key=idx;
-	if (field->part_of_key & ((key_map) 1 << idx))
-	{
-	  table->key_read=1;
-	  table->file->extra(HA_EXTRA_KEYREAD);
-	}
-	return 1;				// Ok to use key
-      }
+      if (maxmin_in_range(max_fl, field, item))
+        return 1;
     }
+    return 0;
   }
-  return 0;					// No possible key
+
+  if (cond->used_tables() != field->table->map)
+    return 0;
+  bool less_fl= 0;
+  switch (((Item_func*) cond)->functype()) {
+  case Item_func::BETWEEN:
+    return cond->val_int() == 0;                // Return 1 if WHERE is false
+  case Item_func::LT_FUNC:
+  case Item_func::LE_FUNC:
+    less_fl= 1;
+  case Item_func::GT_FUNC:
+  case Item_func::GE_FUNC:
+  {
+     Item *item= ((Item_func*) cond)->arguments()[1];
+     /* In case of 'const op item' we have to swap the operator */
+     if (!item->const_item())
+       less_fl= 1-less_fl;
+     /*
+       We only have to check the expression if we are using an expression like
+       SELECT MAX(b) FROM t1 WHERE a=const AND b>const
+       not for
+       SELECT MAX(b) FROM t1 WHERE a=const AND b<const
+     */
+     if (max_fl != less_fl)
+      return cond->val_int() == 0;                // Return 1 if WHERE is false
+    return 0;
+  }
+  case Item_func::EQ_FUNC:
+  case Item_func::EQUAL_FUNC:
+    break;
+  default:                                        // Keep compiler happy
+    DBUG_ASSERT(1);                               // Impossible
+    break;
+  }
+  return 0;
 }
+