Drizzled Public API Documentation

sum.cc

Go to the documentation of this file.
00001 /* - mode: c; c-basic-offset: 2; indent-tabs-mode: nil; -*-
00002  *  vim:expandtab:shiftwidth=2:tabstop=2:smarttab:
00003  *
00004  *  Copyright (C) 2008-2009 Sun Microsystems, Inc.
00005  *
00006  *  This program is free software; you can redistribute it and/or modify
00007  *  it under the terms of the GNU General Public License as published by
00008  *  the Free Software Foundation; either version 2 of the License, or
00009  *  (at your option) any later version.
00010  *
00011  *  This program is distributed in the hope that it will be useful,
00012  *  but WITHOUT ANY WARRANTY; without even the implied warranty of
00013  *  MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
00014  *  GNU General Public License for more details.
00015  *
00016  *  You should have received a copy of the GNU General Public License
00017  *  along with this program; if not, write to the Free Software
00018  *  Foundation, Inc., 51 Franklin St, Fifth Floor, Boston, MA  02110-1301  USA
00019  */
00020 
00054 #include <config.h>
00055 
00056 #include <drizzled/sql_select.h>
00057 #include <drizzled/item/sum.h>
00058 #include <drizzled/item/cmpfunc.h>
00059 #include <drizzled/optimizer/sum.h>
00060 #include <drizzled/plugin/storage_engine.h>
00061 #include <drizzled/table_list.h>
00062 #include <drizzled/key.h>
00063 
00064 namespace drizzled
00065 {
00066 
00067 static bool find_key_for_maxmin(bool max_fl,
00068                                 table_reference_st *ref,
00069                                 Field* field,
00070                                 COND *cond,
00071                                 uint32_t *range_fl,
00072                                 uint32_t *key_prefix_length);
00073 
00074 static int reckey_in_range(bool max_fl,
00075                            table_reference_st *ref,
00076                            Field* field,
00077                            COND *cond,
00078                            uint32_t range_fl,
00079                            uint32_t prefix_len);
00080 
00081 static int maxmin_in_range(bool max_fl, Field *field, COND *cond);
00082 
00083 
00084 /*
00085   Get exact count of rows in all tables
00086 
00087   SYNOPSIS
00088     get_exact_records()
00089     tables    List of tables
00090 
00091   NOTES
00092     When this is called, we know all table handlers supports HA_HAS_RECORDS
00093     or HA_STATS_RECORDS_IS_EXACT
00094 
00095   RETURN
00096     UINT64_MAX  Error: Could not calculate number of rows
00097     #     Multiplication of number of rows in all tables
00098 */
00099 static uint64_t get_exact_record_count(TableList *tables)
00100 {
00101   uint64_t count= 1;
00102   for (TableList *tl= tables; tl; tl= tl->next_leaf)
00103   {
00104     ha_rows tmp= tl->table->cursor->records();
00105     if ((tmp == HA_POS_ERROR))
00106     {
00107       return UINT64_MAX;
00108     }
00109     count*= tmp;
00110   }
00111   return count;
00112 }
00113 
00114 
00115 int optimizer::sum_query(TableList *tables, List<Item> &all_fields, COND *conds)
00116 {
00117   List<Item>::iterator it(all_fields.begin());
00118   int const_result= 1;
00119   bool recalc_const_item= false;
00120   uint64_t count= 1;
00121   bool is_exact_count= true;
00122   bool maybe_exact_count= true;
00123   table_map removed_tables= 0;
00124   table_map outer_tables= 0;
00125   table_map used_tables= 0;
00126   table_map where_tables= 0;
00127   Item *item= NULL;
00128   int error;
00129 
00130   if (conds)
00131   {
00132     where_tables= conds->used_tables();
00133   }
00134 
00135   /*
00136      Analyze outer join dependencies, and, if possible, compute the number
00137      of returned rows.
00138    */
00139   for (TableList *tl= tables; tl; tl= tl->next_leaf)
00140   {
00141     TableList *embedded= NULL;
00142     for (embedded= tl; embedded; embedded= embedded->getEmbedding())
00143     {
00144       if (embedded->on_expr)
00145         break;
00146     }
00147     if (embedded)
00148       /* Don't replace expression on a table that is part of an outer join */
00149     {
00150       outer_tables|= tl->table->map;
00151 
00152       /*
00153          We can't optimise LEFT JOIN in cases where the WHERE condition
00154          restricts the table that is used, like in:
00155          SELECT MAX(t1.a) FROM t1 LEFT JOIN t2 join-condition
00156          WHERE t2.field IS NULL;
00157        */
00158       if (tl->table->map & where_tables)
00159         return 0;
00160     }
00161     else
00162     {
00163       used_tables|= tl->table->map;
00164     }
00165 
00166     /*
00167        If the storage manager of 'tl' gives exact row count as part of
00168        statistics (cheap), compute the total number of rows. If there are
00169        no outer table dependencies, this count may be used as the real count.
00170        Schema tables are filled after this function is invoked, so we can't
00171        get row count
00172      */
00173     if (! (tl->table->cursor->getEngine()->check_flag(HTON_BIT_STATS_RECORDS_IS_EXACT)))
00174     {
00175       maybe_exact_count&= test(tl->table->cursor->getEngine()->check_flag(HTON_BIT_HAS_RECORDS));
00176       is_exact_count= false;
00177       count= 1; // ensure count != 0
00178     }
00179     else
00180     {
00181       error= tl->table->cursor->info(HA_STATUS_VARIABLE | HA_STATUS_NO_LOCK);
00182       if(error)
00183       {
00184         tl->table->print_error(error, MYF(ME_FATALERROR));
00185         return error;
00186       }
00187       count*= tl->table->cursor->stats.records;
00188     }
00189   }
00190 
00191   /*
00192      Iterate through all items in the SELECT clause and replace
00193      COUNT(), MIN() and MAX() with constants (if possible).
00194    */
00195 
00196   while ((item= it++))
00197   {
00198     if (item->type() == Item::SUM_FUNC_ITEM)
00199     {
00200       Item_sum *item_sum= (((Item_sum*) item));
00201       switch (item_sum->sum_func())
00202       {
00203         case Item_sum::COUNT_FUNC:
00204           /*
00205              If the expr in COUNT(expr) can never be null we can change this
00206              to the number of rows in the tables if this number is exact and
00207              there are no outer joins.
00208            */
00209           if (! conds && ! ((Item_sum_count*) item)->args[0]->maybe_null &&
00210               ! outer_tables && maybe_exact_count)
00211           {
00212             if (! is_exact_count)
00213             {
00214               if ((count= get_exact_record_count(tables)) == UINT64_MAX)
00215               {
00216                 /* Error from handler in counting rows. Don't optimize count() */
00217                 const_result= 0;
00218                 continue;
00219               }
00220               is_exact_count= 1;                  // count is now exact
00221             }
00222             ((Item_sum_count*) item)->make_const_count((int64_t) count);
00223             recalc_const_item= 1;
00224           }
00225           else
00226           {
00227             const_result= 0;
00228           }
00229           break;
00230         case Item_sum::MIN_FUNC:
00231           {
00232             /*
00233                If MIN(expr) is the first part of a key or if all previous
00234                parts of the key is found in the COND, then we can use
00235                indexes to find the key.
00236              */
00237             Item *expr=item_sum->args[0];
00238             if (expr->real_item()->type() == Item::FIELD_ITEM)
00239             {
00240               unsigned char key_buff[MAX_KEY_LENGTH];
00241               table_reference_st ref;
00242               uint32_t range_fl, prefix_len;
00243 
00244               ref.key_buff= key_buff;
00245               Item_field *item_field= (Item_field*) (expr->real_item());
00246               Table *table= item_field->field->getTable();
00247 
00248               /*
00249                  Look for a partial key that can be used for optimization.
00250                  If we succeed, ref.key_length will contain the length of
00251                  this key, while prefix_len will contain the length of
00252                  the beginning of this key without field used in MIN().
00253                  Type of range for the key part for this field will be
00254                  returned in range_fl.
00255                */
00256               if (table->cursor->inited ||
00257                   (outer_tables & table->map) ||
00258                   ! find_key_for_maxmin(0,
00259                                         &ref,
00260                                         item_field->field,
00261                                         conds,
00262                                         &range_fl,
00263                                         &prefix_len))
00264               {
00265                 const_result= 0;
00266                 break;
00267               }
00268               error= table->cursor->startIndexScan(static_cast<uint32_t>(ref.key), 1);
00269               if (error)
00270               {
00271                 if (table->key_read)
00272                 {
00273                   table->key_read= 0;
00274                   table->cursor->extra(HA_EXTRA_NO_KEYREAD);
00275                 }
00276                 table->print_error(error, MYF(0));
00277                 return error;
00278               }
00279 
00280               if (! ref.key_length)
00281               {
00282                 error= table->cursor->index_first(table->record[0]);
00283               }
00284               else
00285               {
00286                 /*
00287                    Use index to replace MIN/MAX functions with their values
00288                    according to the following rules:
00289 
00290                    1) Insert the minimum non-null values where the WHERE clause still
00291                    matches, or
00292                    2) a NULL value if there are only NULL values for key_part_k.
00293                    3) Fail, producing a row of nulls
00294 
00295                    Implementation: Read the smallest value using the search key. If
00296                    the interval is open, read the next value after the search
00297                    key. If read fails, and we're looking for a MIN() value for a
00298                    nullable column, test if there is an exact match for the key.
00299                  */
00300                 if (! (range_fl & NEAR_MIN))
00301                 {
00302                   /*
00303                      Closed interval: Either The MIN argument is non-nullable, or
00304                      we have a >= predicate for the MIN argument.
00305                    */
00306                   error= table->cursor->index_read_map(table->record[0],
00307                                                        ref.key_buff,
00308                                                        make_prev_keypart_map(ref.key_parts),
00309                                                        HA_READ_KEY_OR_NEXT);
00310                 }
00311                 else
00312                 {
00313                   /*
00314                      Open interval: There are two cases:
00315                      1) We have only MIN() and the argument column is nullable, or
00316                      2) there is a > predicate on it, nullability is irrelevant.
00317                      We need to scan the next bigger record first.
00318                    */
00319                   error= table->cursor->index_read_map(table->record[0],
00320                                                        ref.key_buff,
00321                                                        make_prev_keypart_map(ref.key_parts),
00322                                                        HA_READ_AFTER_KEY);
00323                   /*
00324                      If the found record is outside the group formed by the search
00325                      prefix, or there is no such record at all, check if all
00326                      records in that group have NULL in the MIN argument
00327                      column. If that is the case return that NULL.
00328 
00329                      Check if case 1 from above holds. If it does, we should read
00330                      the skipped tuple.
00331                    */
00332                   if (item_field->field->real_maybe_null() &&
00333                       ref.key_buff[prefix_len] == 1 &&
00334                       /*
00335                          Last keypart (i.e. the argument to MIN) is set to NULL by
00336                          find_key_for_maxmin only if all other keyparts are bound
00337                          to constants in a conjunction of equalities. Hence, we
00338                          can detect this by checking only if the last keypart is
00339                          NULL.
00340                        */
00341                       (error == HA_ERR_KEY_NOT_FOUND ||
00342                        key_cmp_if_same(table, ref.key_buff, ref.key, prefix_len)))
00343                   {
00344                     assert(item_field->field->real_maybe_null());
00345                     error= table->cursor->index_read_map(table->record[0],
00346                                                          ref.key_buff,
00347                                                          make_prev_keypart_map(ref.key_parts),
00348                                                          HA_READ_KEY_EXACT);
00349                   }
00350                 }
00351               }
00352               /* Verify that the read tuple indeed matches the search key */
00353               if (! error &&
00354                   reckey_in_range(0,
00355                                   &ref,
00356                                   item_field->field,
00357                                   conds,
00358                                   range_fl,
00359                                   prefix_len))
00360               {
00361                 error= HA_ERR_KEY_NOT_FOUND;
00362               }
00363               if (table->key_read)
00364               {
00365                 table->key_read= 0;
00366                 table->cursor->extra(HA_EXTRA_NO_KEYREAD);
00367               }
00368               table->cursor->endIndexScan();
00369               if (error)
00370               {
00371                 if (error == HA_ERR_KEY_NOT_FOUND || error == HA_ERR_END_OF_FILE)
00372                 {
00373                   return HA_ERR_KEY_NOT_FOUND;        // No rows matching WHERE
00374                 }
00375                 /* HA_ERR_LOCK_DEADLOCK or some other error */
00376                 table->print_error(error, MYF(0));
00377                 return error;
00378               }
00379               removed_tables|= table->map;
00380             }
00381             else if (! expr->const_item() || ! is_exact_count)
00382             {
00383               /*
00384                  The optimization is not applicable in both cases:
00385                  (a) 'expr' is a non-constant expression. Then we can't
00386                  replace 'expr' by a constant.
00387                  (b) 'expr' is a costant. According to ANSI, MIN/MAX must return
00388                  NULL if the query does not return any rows. Thus, if we are not
00389                  able to determine if the query returns any rows, we can't apply
00390                  the optimization and replace MIN/MAX with a constant.
00391                */
00392               const_result= 0;
00393               break;
00394             }
00395             if (! count)
00396             {
00397               /* If count == 0, then we know that is_exact_count == true. */
00398               ((Item_sum_min*) item_sum)->clear(); /* Set to NULL. */
00399             }
00400             else
00401             {
00402               ((Item_sum_min*) item_sum)->reset(); /* Set to the constant value. */
00403             }
00404             ((Item_sum_min*) item_sum)->make_const();
00405             recalc_const_item= 1;
00406             break;
00407           }
00408         case Item_sum::MAX_FUNC:
00409           {
00410             /*
00411                If MAX(expr) is the first part of a key or if all previous
00412                parts of the key is found in the COND, then we can use
00413                indexes to find the key.
00414              */
00415             Item *expr= item_sum->args[0];
00416             if (expr->real_item()->type() == Item::FIELD_ITEM)
00417             {
00418               unsigned char key_buff[MAX_KEY_LENGTH];
00419               table_reference_st ref;
00420               uint32_t range_fl, prefix_len;
00421 
00422               ref.key_buff= key_buff;
00423               Item_field *item_field= (Item_field*) (expr->real_item());
00424               Table *table= item_field->field->getTable();
00425 
00426               /*
00427                  Look for a partial key that can be used for optimization.
00428                  If we succeed, ref.key_length will contain the length of
00429                  this key, while prefix_len will contain the length of
00430                  the beginning of this key without field used in MAX().
00431                  Type of range for the key part for this field will be
00432                  returned in range_fl.
00433                */
00434               if (table->cursor->inited ||
00435                   (outer_tables & table->map) ||
00436                   ! find_key_for_maxmin(1,
00437                                         &ref,
00438                                         item_field->field,
00439                                         conds,
00440                                         &range_fl,
00441                                         &prefix_len))
00442               {
00443                 const_result= 0;
00444                 break;
00445               }
00446               error= table->cursor->startIndexScan(static_cast<uint32_t>(ref.key), 1);
00447 
00448               if (! ref.key_length)
00449               {
00450                 error= table->cursor->index_last(table->record[0]);
00451               }
00452               else
00453               {
00454                 error= table->cursor->index_read_map(table->record[0],
00455                                                      key_buff,
00456                                                      make_prev_keypart_map(ref.key_parts),
00457                                                      range_fl & NEAR_MAX ?
00458                                                      HA_READ_BEFORE_KEY :
00459                                                      HA_READ_PREFIX_LAST_OR_PREV);
00460               }
00461               if (! error &&
00462                   reckey_in_range(1,
00463                                   &ref,
00464                                   item_field->field,
00465                                   conds,
00466                                   range_fl,
00467                                   prefix_len))
00468               {
00469                 error= HA_ERR_KEY_NOT_FOUND;
00470               }
00471               if (table->key_read)
00472               {
00473                 table->key_read= 0;
00474                 table->cursor->extra(HA_EXTRA_NO_KEYREAD);
00475               }
00476               table->cursor->endIndexScan();
00477               if (error)
00478               {
00479                 if (error == HA_ERR_KEY_NOT_FOUND || error == HA_ERR_END_OF_FILE)
00480                 {
00481                   return HA_ERR_KEY_NOT_FOUND;       // No rows matching WHERE
00482                 }
00483                 /* HA_ERR_LOCK_DEADLOCK or some other error */
00484                 table->print_error(error, MYF(ME_FATALERROR));
00485                 return error;
00486               }
00487               removed_tables|= table->map;
00488             }
00489             else if (! expr->const_item() || ! is_exact_count)
00490             {
00491               /*
00492                  The optimization is not applicable in both cases:
00493                  (a) 'expr' is a non-constant expression. Then we can't
00494                  replace 'expr' by a constant.
00495                  (b) 'expr' is a costant. According to ANSI, MIN/MAX must return
00496                  NULL if the query does not return any rows. Thus, if we are not
00497                  able to determine if the query returns any rows, we can't apply
00498                  the optimization and replace MIN/MAX with a constant.
00499                */
00500               const_result= 0;
00501               break;
00502             }
00503             if (! count)
00504             {
00505               /* If count != 1, then we know that is_exact_count == true. */
00506               ((Item_sum_max*) item_sum)->clear(); /* Set to NULL. */
00507             }
00508             else
00509             {
00510               ((Item_sum_max*) item_sum)->reset(); /* Set to the constant value. */
00511             }
00512             ((Item_sum_max*) item_sum)->make_const();
00513             recalc_const_item= 1;
00514             break;
00515           }
00516         default:
00517           const_result= 0;
00518           break;
00519       }
00520     }
00521     else if (const_result)
00522     {
00523       if (recalc_const_item)
00524       {
00525         item->update_used_tables();
00526       }
00527       if (! item->const_item())
00528       {
00529         const_result= 0;
00530       }
00531     }
00532   }
00533   /*
00534      If we have a where clause, we can only ignore searching in the
00535      tables if MIN/MAX optimisation replaced all used tables
00536      We do not use replaced values in case of:
00537      SELECT MIN(key) FROM table_1, empty_table
00538      removed_tables is != 0 if we have used MIN() or MAX().
00539    */
00540   if (removed_tables && used_tables != removed_tables)
00541   {
00542     const_result= 0;                            // We didn't remove all tables
00543   }
00544   return const_result;
00545 }
00546 
00547 
00548 bool optimizer::simple_pred(Item_func *func_item, Item **args, bool &inv_order)
00549 {
00550   Item *item= NULL;
00551   inv_order= false;
00552   switch (func_item->argument_count())
00553   {
00554   case 0:
00555     /* MULT_EQUAL_FUNC */
00556     {
00557       Item_equal *item_equal= (Item_equal *) func_item;
00558       Item_equal_iterator it(item_equal->begin());
00559       args[0]= it++;
00560       if (it++)
00561       {
00562         return 0;
00563       }
00564       if (! (args[1]= item_equal->get_const()))
00565       {
00566         return 0;
00567       }
00568     }
00569     break;
00570   case 1:
00571     /* field IS NULL */
00572     item= func_item->arguments()[0];
00573     if (item->type() != Item::FIELD_ITEM)
00574     {
00575       return 0;
00576     }
00577     args[0]= item;
00578     break;
00579   case 2:
00580     /* 'field op const' or 'const op field' */
00581     item= func_item->arguments()[0];
00582     if (item->type() == Item::FIELD_ITEM)
00583     {
00584       args[0]= item;
00585       item= func_item->arguments()[1];
00586       if (! item->const_item())
00587       {
00588         return 0;
00589       }
00590       args[1]= item;
00591     }
00592     else if (item->const_item())
00593     {
00594       args[1]= item;
00595       item= func_item->arguments()[1];
00596       if (item->type() != Item::FIELD_ITEM)
00597       {
00598         return 0;
00599       }
00600       args[0]= item;
00601       inv_order= true;
00602     }
00603     else
00604     {
00605       return 0;
00606     }
00607     break;
00608   case 3:
00609     /* field BETWEEN const AND const */
00610     item= func_item->arguments()[0];
00611     if (item->type() == Item::FIELD_ITEM)
00612     {
00613       args[0]= item;
00614       for (int i= 1 ; i <= 2; i++)
00615       {
00616         item= func_item->arguments()[i];
00617         if (! item->const_item())
00618         {
00619           return 0;
00620         }
00621         args[i]= item;
00622       }
00623     }
00624     else
00625     {
00626       return 0;
00627     }
00628   }
00629   return 1;
00630 }
00631 
00632 
00662 static bool matching_cond(bool max_fl,
00663                           table_reference_st *ref,
00664                           KeyInfo *keyinfo,
00665                           KeyPartInfo *field_part,
00666                           COND *cond,
00667                           key_part_map *key_part_used,
00668                           uint32_t *range_fl,
00669                           uint32_t *prefix_len)
00670 {
00671   if (! cond)
00672   {
00673     return 1;
00674   }
00675   Field *field= field_part->field;
00676 
00677   field->setWriteSet();
00678 
00679   if (! (cond->used_tables() & field->getTable()->map))
00680   {
00681     /* Condition doesn't restrict the used table */
00682     return 1;
00683   }
00684   if (cond->type() == Item::COND_ITEM)
00685   {
00686     if (((Item_cond*) cond)->functype() == Item_func::COND_OR_FUNC)
00687     {
00688       return 0;
00689     }
00690 
00691     /* AND */
00692     List<Item>::iterator li(((Item_cond*) cond)->argument_list()->begin());
00693     Item *item;
00694     while ((item= li++))
00695     {
00696       if (! matching_cond(max_fl,
00697                           ref,
00698                           keyinfo,
00699                           field_part,
00700                           item,
00701                           key_part_used,
00702                           range_fl,
00703                           prefix_len))
00704       {
00705         return 0;
00706       }
00707     }
00708     return 1;
00709   }
00710 
00711   if (cond->type() != Item::FUNC_ITEM)
00712   {
00713     return 0; // Not operator, can't optimize
00714   }
00715 
00716   bool eq_type= false; // =, <=> or IS NULL
00717   bool noeq_type= false; // < or >
00718   bool less_fl= false; // < or <=
00719   bool is_null= false;
00720   bool between= false;
00721 
00722   switch (((Item_func*) cond)->functype())
00723   {
00724   case Item_func::ISNULL_FUNC:
00725     is_null= 1;     /* fall through */
00726   case Item_func::EQ_FUNC:
00727   case Item_func::EQUAL_FUNC:
00728     eq_type= 1;
00729     break;
00730   case Item_func::LT_FUNC:
00731     noeq_type= 1;   /* fall through */
00732   case Item_func::LE_FUNC:
00733     less_fl= 1;
00734     break;
00735   case Item_func::GT_FUNC:
00736     noeq_type= 1;   /* fall through */
00737   case Item_func::GE_FUNC:
00738     break;
00739   case Item_func::BETWEEN:
00740     between= 1;
00741     break;
00742   case Item_func::MULT_EQUAL_FUNC:
00743     eq_type= 1;
00744     break;
00745   default:
00746     return 0; // Can't optimize function
00747   }
00748 
00749   Item *args[3];
00750   bool inv;
00751 
00752   /* Test if this is a comparison of a field and constant */
00753   if (! optimizer::simple_pred((Item_func*) cond, args, inv))
00754   {
00755     return 0;
00756   }
00757 
00758   if (inv && ! eq_type)
00759   {
00760     less_fl= 1 - less_fl; // Convert '<' -> '>' (etc)
00761   }
00762 
00763   /* Check if field is part of the tested partial key */
00764   unsigned char *key_ptr= ref->key_buff;
00765   KeyPartInfo *part= NULL;
00766   for (part= keyinfo->key_part; ; key_ptr+= part++->store_length)
00767 
00768   {
00769     if (part > field_part)
00770     {
00771       return 0;                     // Field is beyond the tested parts
00772     }
00773     if (part->field->eq(((Item_field*) args[0])->field))
00774     {
00775       break;                        // Found a part of the key for the field
00776     }
00777   }
00778 
00779   bool is_field_part= part == field_part;
00780   if (! (is_field_part || eq_type))
00781   {
00782     return 0;
00783   }
00784 
00785   key_part_map org_key_part_used= *key_part_used;
00786   if (eq_type || between || max_fl == less_fl)
00787   {
00788     uint32_t length= (key_ptr-ref->key_buff)+part->store_length;
00789     if (ref->key_length < length)
00790     {
00791     /* Ultimately ref->key_length will contain the length of the search key */
00792       ref->key_length= length;
00793       ref->key_parts= (part - keyinfo->key_part) + 1;
00794     }
00795     if (! *prefix_len && part + 1 == field_part)
00796     {
00797       *prefix_len= length;
00798     }
00799     if (is_field_part && eq_type)
00800     {
00801       *prefix_len= ref->key_length;
00802     }
00803 
00804     *key_part_used|= (key_part_map) 1 << (part - keyinfo->key_part);
00805   }
00806 
00807   if (org_key_part_used != *key_part_used ||
00808       (is_field_part &&
00809        (between || eq_type || max_fl == less_fl) && ! cond->val_int()))
00810   {
00811     /*
00812       It's the first predicate for this part or a predicate of the
00813       following form  that moves upper/lower bounds for max/min values:
00814       - field BETWEEN const AND const
00815       - field = const
00816       - field {<|<=} const, when searching for MAX
00817       - field {>|>=} const, when searching for MIN
00818     */
00819 
00820     if (is_null)
00821     {
00822       part->field->set_null();
00823       *key_ptr= (unsigned char) 1;
00824     }
00825     else
00826     {
00827       store_val_in_field(part->field, args[between && max_fl ? 2 : 1],
00828                          CHECK_FIELD_IGNORE);
00829       if (part->null_bit)
00830       {
00831         *key_ptr++= (unsigned char) test(part->field->is_null());
00832       }
00833       part->field->get_key_image(key_ptr, part->length);
00834     }
00835     if (is_field_part)
00836     {
00837       if (between || eq_type)
00838       {
00839         *range_fl&= ~(NO_MAX_RANGE | NO_MIN_RANGE);
00840       }
00841       else
00842       {
00843         *range_fl&= ~(max_fl ? NO_MAX_RANGE : NO_MIN_RANGE);
00844         if (noeq_type)
00845         {
00846           *range_fl|=  (max_fl ? NEAR_MAX : NEAR_MIN);
00847         }
00848         else
00849         {
00850           *range_fl&= ~(max_fl ? NEAR_MAX : NEAR_MIN);
00851         }
00852       }
00853     }
00854   }
00855   else if (eq_type)
00856   {
00857     if ((! is_null && !cond->val_int()) ||
00858         (is_null && !test(part->field->is_null())))
00859     {
00860      return 0;                       // Impossible test
00861     }
00862   }
00863   else if (is_field_part)
00864   {
00865     *range_fl&= ~(max_fl ? NO_MIN_RANGE : NO_MAX_RANGE);
00866   }
00867   return 1;
00868 }
00869 
00870 
00912 static bool find_key_for_maxmin(bool max_fl,
00913                                 table_reference_st *ref,
00914                                 Field* field,
00915                                 COND *cond,
00916                                 uint32_t *range_fl,
00917                                 uint32_t *prefix_len)
00918 {
00919   if (! (field->flags & PART_KEY_FLAG))
00920   {
00921     return 0; // Not key field
00922   }
00923 
00924   Table *table= field->getTable();
00925   uint32_t idx= 0;
00926 
00927   KeyInfo *keyinfo,*keyinfo_end= NULL;
00928   for (keyinfo= table->key_info, keyinfo_end= keyinfo+table->getShare()->sizeKeys();
00929        keyinfo != keyinfo_end;
00930        keyinfo++,idx++)
00931   {
00932     KeyPartInfo *part= NULL;
00933     KeyPartInfo *part_end= NULL;
00934     key_part_map key_part_to_use= 0;
00935     /*
00936       Perform a check if index is not disabled by ALTER Table
00937       or IGNORE INDEX.
00938     */
00939     if (! table->keys_in_use_for_query.test(idx))
00940     {
00941       continue;
00942     }
00943     uint32_t jdx= 0;
00944     *prefix_len= 0;
00945     for (part= keyinfo->key_part, part_end= part+keyinfo->key_parts;
00946          part != part_end;
00947          part++, jdx++, key_part_to_use= (key_part_to_use << 1) | 1)
00948     {
00949       if (! (table->index_flags(idx) & HA_READ_ORDER))
00950       {
00951         return 0;
00952       }
00953 
00954       /* Check whether the index component is partial */
00955       Field *part_field= table->getField(part->fieldnr-1);
00956       part_field->setWriteSet();
00957 
00958       if ((part_field->flags & BLOB_FLAG) ||
00959           part->length < part_field->key_length())
00960       {
00961         break;
00962       }
00963 
00964       if (field->eq(part->field))
00965       {
00966         ref->key= idx;
00967         ref->key_length= 0;
00968         ref->key_parts= 0;
00969         key_part_map key_part_used= 0;
00970         *range_fl= NO_MIN_RANGE | NO_MAX_RANGE;
00971         if (matching_cond(max_fl,
00972                           ref,
00973                           keyinfo,
00974                           part,
00975                           cond,
00976                           &key_part_used,
00977                           range_fl,
00978                           prefix_len) &&
00979             ! (key_part_to_use & ~key_part_used))
00980         {
00981           if (! max_fl && key_part_used == key_part_to_use && part->null_bit)
00982           {
00983             /*
00984               The query is on this form:
00985 
00986               SELECT MIN(key_part_k)
00987               FROM t1
00988               WHERE key_part_1 = const and ... and key_part_k-1 = const
00989 
00990               If key_part_k is nullable, we want to find the first matching row
00991               where key_part_k is not null. The key buffer is now {const, ...,
00992               NULL}. This will be passed to the handler along with a flag
00993               indicating open interval. If a tuple is read that does not match
00994               these search criteria, an attempt will be made to read an exact
00995               match for the key buffer.
00996             */
00997             /* Set the first byte of key_part_k to 1, that means NULL */
00998             ref->key_buff[ref->key_length]= 1;
00999             ref->key_length+= part->store_length;
01000             ref->key_parts++;
01001             assert(ref->key_parts == jdx+1);
01002             *range_fl&= ~NO_MIN_RANGE;
01003             *range_fl|= NEAR_MIN; // Open interval
01004           }
01005           /*
01006             The following test is false when the key in the key tree is
01007             converted (for example to upper case)
01008           */
01009           if (field->part_of_key.test(idx))
01010           {
01011             table->key_read= 1;
01012             table->cursor->extra(HA_EXTRA_KEYREAD);
01013           }
01014           return 1;
01015         }
01016       }
01017     }
01018   }
01019   return 0;
01020 }
01021 
01022 
01038 static int reckey_in_range(bool max_fl,
01039                            table_reference_st *ref,
01040                            Field* field,
01041                            COND *cond,
01042                            uint32_t range_fl,
01043                            uint32_t prefix_len)
01044 {
01045   if (key_cmp_if_same(field->getTable(), ref->key_buff, ref->key, prefix_len))
01046   {
01047     return 1;
01048   }
01049   if (! cond || (range_fl & (max_fl ? NO_MIN_RANGE : NO_MAX_RANGE)))
01050   {
01051     return 0;
01052   }
01053   return maxmin_in_range(max_fl, field, cond);
01054 }
01055 
01056 
01069 static int maxmin_in_range(bool max_fl, Field* field, COND *cond)
01070 {
01071   /* If AND/OR condition */
01072   if (cond->type() == Item::COND_ITEM)
01073   {
01074     List<Item>::iterator li(((Item_cond*) cond)->argument_list()->begin());
01075     Item *item;
01076     while ((item= li++))
01077     {
01078       if (maxmin_in_range(max_fl, field, item))
01079       {
01080         return 1;
01081       }
01082     }
01083     return 0;
01084   }
01085 
01086   if (cond->used_tables() != field->getTable()->map)
01087   {
01088     return 0;
01089   }
01090   bool less_fl= false;
01091   switch (((Item_func*) cond)->functype())
01092   {
01093   case Item_func::BETWEEN:
01094     return cond->val_int() == 0;                // Return 1 if WHERE is false
01095   case Item_func::LT_FUNC:
01096   case Item_func::LE_FUNC:
01097     less_fl= 1;
01098   case Item_func::GT_FUNC:
01099   case Item_func::GE_FUNC:
01100   {
01101     Item *item= ((Item_func*) cond)->arguments()[1];
01102     /* In case of 'const op item' we have to swap the operator */
01103     if (! item->const_item())
01104     {
01105       less_fl= 1-less_fl;
01106     }
01107     /*
01108       We only have to check the expression if we are using an expression like
01109       SELECT MAX(b) FROM t1 WHERE a=const AND b>const
01110       not for
01111       SELECT MAX(b) FROM t1 WHERE a=const AND b<const
01112     */
01113     if (max_fl != less_fl)
01114     {
01115       return cond->val_int() == 0;                // Return 1 if WHERE is false
01116     }
01117     return 0;
01118   }
01119   case Item_func::EQ_FUNC:
01120   case Item_func::EQUAL_FUNC:
01121     break;
01122   default:                                        // Keep compiler happy
01123     assert(1);                               // Impossible
01124     break;
01125   }
01126   return 0;
01127 }
01128 
01129 } /* namespace drizzled */
01130