Drizzled Public API Documentation

sql_select.cc

Go to the documentation of this file.
00001 /* Copyright (C) 2000-2006 MySQL AB
00002 
00003    This program is free software; you can redistribute it and/or modify
00004    it under the terms of the GNU General Public License as published by
00005    the Free Software Foundation; version 2 of the License.
00006 
00007    This program is distributed in the hope that it will be useful,
00008    but WITHOUT ANY WARRANTY; without even the implied warranty of
00009    MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
00010    GNU General Public License for more details.
00011 
00012    You should have received a copy of the GNU General Public License
00013    along with this program; if not, write to the Free Software
00014    Foundation, Inc., 51 Franklin St, Fifth Floor, Boston, MA  02110-1301  USA */
00015 
00025 #include <config.h>
00026 
00027 #include <string>
00028 #include <iostream>
00029 #include <algorithm>
00030 #include <vector>
00031 
00032 #include <drizzled/sql_select.h> /* include join.h */
00033 
00034 #include <drizzled/error.h>
00035 #include <drizzled/gettext.h>
00036 #include <drizzled/util/test.h>
00037 #include <drizzled/name_resolution_context_state.h>
00038 #include <drizzled/nested_join.h>
00039 #include <drizzled/probes.h>
00040 #include <drizzled/show.h>
00041 #include <drizzled/item/cache.h>
00042 #include <drizzled/item/cmpfunc.h>
00043 #include <drizzled/item/copy_string.h>
00044 #include <drizzled/item/uint.h>
00045 #include <drizzled/cached_item.h>
00046 #include <drizzled/sql_base.h>
00047 #include <drizzled/field/blob.h>
00048 #include <drizzled/check_stack_overrun.h>
00049 #include <drizzled/lock.h>
00050 #include <drizzled/item/outer_ref.h>
00051 #include <drizzled/index_hint.h>
00052 #include <drizzled/records.h>
00053 #include <drizzled/internal/iocache.h>
00054 #include <drizzled/drizzled.h>
00055 #include <drizzled/plugin/storage_engine.h>
00056 #include <drizzled/sql_union.h>
00057 #include <drizzled/optimizer/key_field.h>
00058 #include <drizzled/optimizer/position.h>
00059 #include <drizzled/optimizer/sargable_param.h>
00060 #include <drizzled/optimizer/key_use.h>
00061 #include <drizzled/optimizer/range.h>
00062 #include <drizzled/optimizer/quick_range_select.h>
00063 #include <drizzled/optimizer/quick_ror_intersect_select.h>
00064 #include <drizzled/filesort.h>
00065 #include <drizzled/sql_lex.h>
00066 #include <drizzled/session.h>
00067 #include <drizzled/sort_field.h>
00068 #include <drizzled/select_result.h>
00069 #include <drizzled/key.h>
00070 #include <drizzled/my_hash.h>
00071 
00072 using namespace std;
00073 
00074 namespace drizzled {
00075 
00076 static int sort_keyuse(optimizer::KeyUse *a, optimizer::KeyUse *b);
00077 static COND *build_equal_items(Session *session, COND *cond,
00078                                COND_EQUAL *inherited,
00079                                List<TableList> *join_list,
00080                                COND_EQUAL **cond_equal_ref);
00081 
00082 static Item* part_of_refkey(Table *form,Field *field);
00083 static bool cmp_buffer_with_ref(JoinTable *tab);
00084 static void change_cond_ref_to_const(Session *session,
00085                                      list<COND_CMP>& save_list,
00086                                      Item *and_father,
00087                                      Item *cond,
00088                                      Item *field,
00089                                      Item *value);
00090 static bool copy_blobs(Field **ptr);
00091 
00092 static bool eval_const_cond(COND *cond)
00093 {
00094     return ((Item_func*) cond)->val_int() ? true : false;
00095 }
00096 
00097 /*
00098   This is used to mark equalities that were made from i-th IN-equality.
00099   We limit semi-join InsideOut optimization to handling max 64 inequalities,
00100   The following variable occupies 64 addresses.
00101 */
00102 const char *subq_sj_cond_name=
00103   "0123456789ABCDEF0123456789abcdef0123456789ABCDEF0123456789abcdef-sj-cond";
00104 
00105 static bool copy_blobs(Field **ptr)
00106 {
00107   for (; *ptr ; ptr++)
00108   {
00109     if ((*ptr)->flags & BLOB_FLAG)
00110       if (((Field_blob *) (*ptr))->copy())
00111   return 1;       // Error
00112   }
00113   return 0;
00114 }
00115 
00119 bool handle_select(Session *session, LEX *lex, select_result *result,
00120                    uint64_t setup_tables_done_option)
00121 {
00122   bool res;
00123   Select_Lex *select_lex= &lex->select_lex;
00124   DRIZZLE_SELECT_START(session->getQueryString()->c_str());
00125 
00126   if (select_lex->master_unit()->is_union() ||
00127       select_lex->master_unit()->fake_select_lex)
00128   {
00129     res= drizzle_union(session, lex, result, &lex->unit,
00130            setup_tables_done_option);
00131   }
00132   else
00133   {
00134     Select_Lex_Unit *unit= &lex->unit;
00135     unit->set_limit(unit->global_parameters);
00136     session->session_marker= 0;
00137     /*
00138       'options' of select_query will be set in JOIN, as far as JOIN for
00139       every PS/SP execution new, we will not need reset this flag if
00140       setup_tables_done_option changed for next rexecution
00141     */
00142     res= select_query(session,
00143                       &select_lex->ref_pointer_array,
00144           (TableList*) select_lex->table_list.first,
00145           select_lex->with_wild,
00146                       select_lex->item_list,
00147           select_lex->where,
00148           select_lex->order_list.size() +
00149           select_lex->group_list.size(),
00150           (Order*) select_lex->order_list.first,
00151           (Order*) select_lex->group_list.first,
00152           select_lex->having,
00153           select_lex->options | session->options |
00154                       setup_tables_done_option,
00155           result, unit, select_lex);
00156   }
00157   res|= session->is_error();
00158   if (unlikely(res))
00159     result->abort();
00160 
00161   DRIZZLE_SELECT_DONE(res, session->limit_found_rows);
00162   return res;
00163 }
00164 
00165 /*
00166   Fix fields referenced from inner selects.
00167 
00168   SYNOPSIS
00169     fix_inner_refs()
00170     session               Thread handle
00171     all_fields        List of all fields used in select
00172     select            Current select
00173     ref_pointer_array Array of references to Items used in current select
00174 
00175   DESCRIPTION
00176     The function serves 3 purposes - adds fields referenced from inner
00177     selects to the current select list, resolves which class to use
00178     to access referenced item (Item_ref of Item_direct_ref) and fixes
00179     references (Item_ref objects) to these fields.
00180 
00181     If a field isn't already in the select list and the ref_pointer_array
00182     is provided then it is added to the all_fields list and the pointer to
00183     it is saved in the ref_pointer_array.
00184 
00185     The class to access the outer field is determined by the following rules:
00186     1. If the outer field isn't used under an aggregate function
00187       then the Item_ref class should be used.
00188     2. If the outer field is used under an aggregate function and this
00189       function is aggregated in the select where the outer field was
00190       resolved or in some more inner select then the Item_direct_ref
00191       class should be used.
00192     The resolution is done here and not at the fix_fields() stage as
00193     it can be done only after sum functions are fixed and pulled up to
00194     selects where they are have to be aggregated.
00195     When the class is chosen it substitutes the original field in the
00196     Item_outer_ref object.
00197 
00198     After this we proceed with fixing references (Item_outer_ref objects) to
00199     this field from inner subqueries.
00200 
00201   RETURN
00202     true  an error occured
00203     false ok
00204 */
00205 bool fix_inner_refs(Session *session,
00206                     List<Item> &all_fields,
00207                     Select_Lex *select,
00208                     Item **ref_pointer_array)
00209 {
00210   Item_outer_ref *ref;
00211   bool res= false;
00212   bool direct_ref= false;
00213 
00214   List<Item_outer_ref>::iterator ref_it(select->inner_refs_list.begin());
00215   while ((ref= ref_it++))
00216   {
00217     Item *item= ref->outer_ref;
00218     Item **item_ref= ref->ref;
00219     Item_ref *new_ref;
00220     /*
00221       @todo this field item already might be present in the select list.
00222       In this case instead of adding new field item we could use an
00223       existing one. The change will lead to less operations for copying fields,
00224       smaller temporary tables and less data passed through filesort.
00225     */
00226     if (ref_pointer_array && !ref->found_in_select_list)
00227     {
00228       int el= all_fields.size();
00229       ref_pointer_array[el]= item;
00230       /* Add the field item to the select list of the current select. */
00231       all_fields.push_front(item);
00232       /*
00233         If it's needed reset each Item_ref item that refers this field with
00234         a new reference taken from ref_pointer_array.
00235       */
00236       item_ref= ref_pointer_array + el;
00237     }
00238 
00239     if (ref->in_sum_func)
00240     {
00241       Item_sum *sum_func;
00242       if (ref->in_sum_func->nest_level > select->nest_level)
00243         direct_ref= true;
00244       else
00245       {
00246         for (sum_func= ref->in_sum_func; sum_func &&
00247              sum_func->aggr_level >= select->nest_level;
00248              sum_func= sum_func->in_sum_func)
00249         {
00250           if (sum_func->aggr_level == select->nest_level)
00251           {
00252             direct_ref= true;
00253             break;
00254           }
00255         }
00256       }
00257     }
00258     new_ref= direct_ref ?
00259               new Item_direct_ref(ref->context, item_ref, ref->table_name,
00260                           ref->field_name, ref->alias_name_used) :
00261               new Item_ref(ref->context, item_ref, ref->table_name,
00262                           ref->field_name, ref->alias_name_used);
00263     if (!new_ref)
00264       return true;
00265     ref->outer_ref= new_ref;
00266     ref->ref= &ref->outer_ref;
00267 
00268     if (!ref->fixed && ref->fix_fields(session, 0))
00269       return true;
00270     session->used_tables|= item->used_tables();
00271   }
00272   return res;
00273 }
00274 
00275 /*****************************************************************************
00276   Check fields, find best join, do the select and output fields.
00277   select_query assumes that all tables are already opened
00278 *****************************************************************************/
00279 
00280 /*
00281   Index lookup-based subquery: save some flags for EXPLAIN output
00282 
00283   SYNOPSIS
00284     save_index_subquery_explain_info()
00285       join_tab  Subquery's join tab (there is only one as index lookup is
00286                 only used for subqueries that are single-table SELECTs)
00287       where     Subquery's WHERE clause
00288 
00289   DESCRIPTION
00290     For index lookup-based subquery (i.e. one executed with
00291     subselect_uniquesubquery_engine or subselect_indexsubquery_engine),
00292     check its EXPLAIN output row should contain
00293       "Using index" (TAB_INFO_FULL_SCAN_ON_NULL)
00294       "Using Where" (TAB_INFO_USING_WHERE)
00295       "Full scan on NULL key" (TAB_INFO_FULL_SCAN_ON_NULL)
00296     and set appropriate flags in join_tab->packed_info.
00297 */
00298 void save_index_subquery_explain_info(JoinTable *join_tab, Item* where)
00299 {
00300   join_tab->packed_info= TAB_INFO_HAVE_VALUE;
00301   if (join_tab->table->covering_keys.test(join_tab->ref.key))
00302     join_tab->packed_info |= TAB_INFO_USING_INDEX;
00303   if (where)
00304     join_tab->packed_info |= TAB_INFO_USING_WHERE;
00305   for (uint32_t i = 0; i < join_tab->ref.key_parts; i++)
00306   {
00307     if (join_tab->ref.cond_guards[i])
00308     {
00309       join_tab->packed_info |= TAB_INFO_FULL_SCAN_ON_NULL;
00310       break;
00311     }
00312   }
00313 }
00314 
00357 bool select_query(Session *session,
00358                   Item ***rref_pointer_array,
00359                   TableList *tables,
00360                   uint32_t wild_num,
00361                   List<Item> &fields,
00362                   COND *conds,
00363                   uint32_t og_num,
00364                   Order *order,
00365                   Order *group,
00366                   Item *having,
00367                   uint64_t select_options,
00368                   select_result *result,
00369                   Select_Lex_Unit *unit,
00370                   Select_Lex *select_lex)
00371 {
00372   bool err;
00373   bool free_join= 1;
00374 
00375   select_lex->context.resolve_in_select_list= true;
00376   Join *join;
00377   if (select_lex->join != 0)
00378   {
00379     join= select_lex->join;
00380     /*
00381       is it single SELECT in derived table, called in derived table
00382       creation
00383     */
00384     if (select_lex->linkage != DERIVED_TABLE_TYPE ||
00385         (select_options & SELECT_DESCRIBE))
00386     {
00387       if (select_lex->linkage != GLOBAL_OPTIONS_TYPE)
00388       {
00389         //here is EXPLAIN of subselect or derived table
00390         if (join->change_result(result))
00391         {
00392           return(true);
00393         }
00394       }
00395       else
00396       {
00397         if ((err= join->prepare(rref_pointer_array, tables, wild_num,
00398                                conds, og_num, order, group, having, select_lex, unit)))
00399         {
00400           goto err;
00401         }
00402       }
00403     }
00404     free_join= 0;
00405     join->select_options= select_options;
00406   }
00407   else
00408   {
00409     if (!(join= new Join(session, fields, select_options, result)))
00410       return(true);
00411     session->set_proc_info("init");
00412     session->used_tables=0;                         // Updated by setup_fields
00413     if ((err= join->prepare(rref_pointer_array, tables, wild_num,
00414                            conds, og_num, order, group, having,
00415                            select_lex, unit)) == true)
00416     {
00417       goto err;
00418     }
00419   }
00420 
00421   err= join->optimize();
00422   if (err)
00423   {
00424     goto err; // 1
00425   }
00426 
00427   if (session->lex().describe & DESCRIBE_EXTENDED)
00428   {
00429     join->conds_history= join->conds;
00430     join->having_history= (join->having?join->having:join->tmp_having);
00431   }
00432 
00433   if (session->is_error())
00434     goto err;
00435 
00436   join->exec();
00437 
00438   if (session->lex().describe & DESCRIBE_EXTENDED)
00439   {
00440     select_lex->where= join->conds_history;
00441     select_lex->having= join->having_history;
00442   }
00443 
00444 err:
00445   if (free_join)
00446   {
00447     session->set_proc_info("end");
00448     err|= select_lex->cleanup();
00449     return(err || session->is_error());
00450   }
00451   return(join->error);
00452 }
00453 
00454 inline Item *and_items(Item* cond, Item *item)
00455 {
00456   return (cond? (new Item_cond_and(cond, item)) : item);
00457 }
00458 
00459 /*****************************************************************************
00460   Create JoinTableS, make a guess about the table types,
00461   Approximate how many records will be used in each table
00462 *****************************************************************************/
00463 ha_rows get_quick_record_count(Session *session, optimizer::SqlSelect *select, Table *table, const key_map *keys,ha_rows limit)
00464 {
00465   int error;
00466   if (check_stack_overrun(session, STACK_MIN_SIZE, NULL))
00467     return(0);                           // Fatal error flag is set
00468   if (select)
00469   {
00470     select->head=table;
00471     table->reginfo.impossible_range=0;
00472     if ((error= select->test_quick_select(session, *(key_map *)keys,(table_map) 0,
00473                                           limit, 0, false)) == 1)
00474       return(select->quick->records);
00475     if (error == -1)
00476     {
00477       table->reginfo.impossible_range=1;
00478       return(0);
00479     }
00480   }
00481   return(HA_POS_ERROR);     /* This shouldn't happend */
00482 }
00483 
00484 /*****************************************************************************
00485   Check with keys are used and with tables references with tables
00486   Updates in stat:
00487     keys       Bitmap of all used keys
00488     const_keys Bitmap of all keys with may be used with quick_select
00489     keyuse     Pointer to possible keys
00490 *****************************************************************************/
00491 
00492 
00498 uint32_t max_part_bit(key_part_map bits)
00499 {
00500   uint32_t found;
00501   for (found=0; bits & 1 ; found++,bits>>=1) ;
00502   return found;
00503 }
00504 
00505 static int sort_keyuse(optimizer::KeyUse *a, optimizer::KeyUse *b)
00506 {
00507   int res;
00508   if (a->getTable()->tablenr != b->getTable()->tablenr)
00509     return static_cast<int>((a->getTable()->tablenr - b->getTable()->tablenr));
00510   if (a->getKey() != b->getKey())
00511     return static_cast<int>((a->getKey() - b->getKey()));
00512   if (a->getKeypart() != b->getKeypart())
00513     return static_cast<int>((a->getKeypart() - b->getKeypart()));
00514   // Place const values before other ones
00515   if ((res= test((a->getUsedTables() & ~OUTER_REF_TABLE_BIT)) -
00516        test((b->getUsedTables() & ~OUTER_REF_TABLE_BIT))))
00517     return res;
00518   /* Place rows that are not 'OPTIMIZE_REF_OR_NULL' first */
00519   return static_cast<int>(((a->getOptimizeFlags() & KEY_OPTIMIZE_REF_OR_NULL) -
00520               (b->getOptimizeFlags() & KEY_OPTIMIZE_REF_OR_NULL)));
00521 }
00522 
00523 
00544 bool update_ref_and_keys(Session *session,
00545                          DYNAMIC_ARRAY *keyuse,
00546                          JoinTable *join_tab,
00547                          uint32_t tables,
00548                          COND *cond,
00549                          COND_EQUAL *,
00550                          table_map normal_tables,
00551                          Select_Lex *select_lex,
00552                          vector<optimizer::SargableParam> &sargables)
00553 {
00554   uint  and_level,found_eq_constant;
00555   optimizer::KeyField *key_fields, *end, *field;
00556   uint32_t sz;
00557   uint32_t m= max(select_lex->max_equal_elems,(uint32_t)1);
00558 
00559   /*
00560     All predicates that are used to fill arrays of KeyField
00561     and SargableParam classes have at most 2 arguments
00562     except BETWEEN predicates that have 3 arguments and
00563     IN predicates.
00564     This any predicate if it's not BETWEEN/IN can be used
00565     directly to fill at most 2 array elements, either of KeyField
00566     or SargableParam type. For a BETWEEN predicate 3 elements
00567     can be filled as this predicate is considered as
00568     saragable with respect to each of its argument.
00569     An IN predicate can require at most 1 element as currently
00570     it is considered as sargable only for its first argument.
00571     Multiple equality can add  elements that are filled after
00572     substitution of field arguments by equal fields. There
00573     can be not more than select_lex->max_equal_elems such
00574     substitutions.
00575   */
00576   sz= sizeof(optimizer::KeyField) *
00577       (((session->lex().current_select->cond_count+1)*2 +
00578   session->lex().current_select->between_count)*m+1);
00579   if (! (key_fields= (optimizer::KeyField*) session->getMemRoot()->allocate(sz)))
00580     return true;
00581   and_level= 0;
00582   field= end= key_fields;
00583 
00584   if (my_init_dynamic_array(keyuse, sizeof(optimizer::KeyUse), 20, 64))
00585     return true;
00586   if (cond)
00587   {
00588     add_key_fields(join_tab->join, &end, &and_level, cond, normal_tables,
00589                    sargables);
00590     for (; field != end; field++)
00591     {
00592       add_key_part(keyuse, field);
00593       /* Mark that we can optimize LEFT JOIN */
00594       if (field->getValue()->type() == Item::NULL_ITEM &&
00595     ! field->getField()->real_maybe_null())
00596       {
00597   field->getField()->getTable()->reginfo.not_exists_optimize= 1;
00598       }
00599     }
00600   }
00601   for (uint32_t i= 0; i < tables; i++)
00602   {
00603     /*
00604       Block the creation of keys for inner tables of outer joins.
00605       Here only the outer joins that can not be converted to
00606       inner joins are left and all nests that can be eliminated
00607       are flattened.
00608       In the future when we introduce conditional accesses
00609       for inner tables in outer joins these keys will be taken
00610       into account as well.
00611     */
00612     if (*join_tab[i].on_expr_ref)
00613       add_key_fields(join_tab->join, &end, &and_level,
00614                      *join_tab[i].on_expr_ref,
00615                      join_tab[i].table->map, sargables);
00616   }
00617 
00618   /* Process ON conditions for the nested joins */
00619   {
00620     List<TableList>::iterator li(join_tab->join->join_list->begin());
00621     TableList *table;
00622     while ((table= li++))
00623     {
00624       if (table->getNestedJoin())
00625         add_key_fields_for_nj(join_tab->join, table, &end, &and_level,
00626                               sargables);
00627     }
00628   }
00629 
00630   /* fill keyuse with found key parts */
00631   for ( ; field != end ; field++)
00632     add_key_part(keyuse,field);
00633 
00634   /*
00635     Sort the array of possible keys and remove the following key parts:
00636     - ref if there is a keypart which is a ref and a const.
00637       (e.g. if there is a key(a,b) and the clause is a=3 and b=7 and b=t2.d,
00638       then we skip the key part corresponding to b=t2.d)
00639     - keyparts without previous keyparts
00640       (e.g. if there is a key(a,b,c) but only b < 5 (or a=2 and c < 3) is
00641       used in the query, we drop the partial key parts from consideration).
00642   */
00643   if (keyuse->size())
00644   {
00645     optimizer::KeyUse key_end,*prev,*save_pos,*use;
00646 
00647     internal::my_qsort(keyuse->buffer,keyuse->size(),sizeof(optimizer::KeyUse),
00648                        (qsort_cmp) sort_keyuse);
00649 
00650     memset(&key_end, 0, sizeof(key_end)); /* Add for easy testing */
00651     keyuse->push_back(&key_end);
00652 
00653     use= save_pos= (optimizer::KeyUse*)keyuse->buffer;
00654     prev= &key_end;
00655     found_eq_constant= 0;
00656     {
00657       uint32_t i;
00658 
00659       for (i= 0; i < keyuse->size()-1; i++, use++)
00660       {
00661         if (! use->getUsedTables() && use->getOptimizeFlags() != KEY_OPTIMIZE_REF_OR_NULL)
00662           use->getTable()->const_key_parts[use->getKey()]|= use->getKeypartMap();
00663         if (use->getKey() == prev->getKey() && use->getTable() == prev->getTable())
00664         {
00665           if (prev->getKeypart() + 1 < use->getKeypart() ||
00666               ((prev->getKeypart() == use->getKeypart()) && found_eq_constant))
00667             continue;       /* remove */
00668         }
00669         else if (use->getKeypart() != 0)    // First found must be 0
00670           continue;
00671 
00672 #ifdef HAVE_VALGRIND
00673         /* Valgrind complains about overlapped memcpy when save_pos==use. */
00674         if (save_pos != use)
00675 #endif
00676           *save_pos= *use;
00677         prev=use;
00678         found_eq_constant= ! use->getUsedTables();
00679         /* Save ptr to first use */
00680         if (! use->getTable()->reginfo.join_tab->keyuse)
00681           use->getTable()->reginfo.join_tab->keyuse= save_pos;
00682         use->getTable()->reginfo.join_tab->checked_keys.set(use->getKey());
00683         save_pos++;
00684       }
00685       i= (uint32_t) (save_pos - (optimizer::KeyUse*) keyuse->buffer);
00686       reinterpret_cast<optimizer::KeyUse*>(keyuse->buffer)[i] = key_end;
00687       keyuse->set_size(i);
00688     }
00689   }
00690   return false;
00691 }
00692 
00696 void optimize_keyuse(Join *join, DYNAMIC_ARRAY *keyuse_array)
00697 {
00698   optimizer::KeyUse* keyuse= (optimizer::KeyUse*)keyuse_array->buffer;
00699   for (optimizer::KeyUse* end= keyuse+ keyuse_array->size() ; keyuse < end ; keyuse++)
00700   {
00701     table_map map;
00702     /*
00703       If we find a ref, assume this table matches a proportional
00704       part of this table.
00705       For example 100 records matching a table with 5000 records
00706       gives 5000/100 = 50 records per key
00707       Constant tables are ignored.
00708       To avoid bad matches, we don't make ref_table_rows less than 100.
00709     */
00710     keyuse->setTableRows(~(ha_rows) 0); // If no ref
00711     if (keyuse->getUsedTables() & (map= (keyuse->getUsedTables() & ~join->const_table_map & ~OUTER_REF_TABLE_BIT)))
00712     {
00713       uint32_t tablenr;
00714       for (tablenr=0 ; ! (map & 1) ; map>>=1, tablenr++) ;
00715       if (map == 1)     // Only one table
00716       {
00717         Table *tmp_table=join->all_tables[tablenr];
00718         keyuse->setTableRows(max(tmp_table->cursor->stats.records, (ha_rows)100));
00719       }
00720     }
00721     /*
00722       Outer reference (external field) is constant for single executing
00723       of subquery
00724     */
00725     if (keyuse->getUsedTables() == OUTER_REF_TABLE_BIT)
00726       keyuse->setTableRows(1);
00727   }
00728 }
00729 
00730 
00748 void add_group_and_distinct_keys(Join *join, JoinTable *join_tab)
00749 {
00750   List<Item_field> indexed_fields;
00751   List<Item_field>::iterator indexed_fields_it(indexed_fields.begin());
00752   Order      *cur_group;
00753   Item_field *cur_item;
00754   key_map possible_keys(0);
00755 
00756   if (join->group_list)
00757   { /* Collect all query fields referenced in the GROUP clause. */
00758     for (cur_group= join->group_list; cur_group; cur_group= cur_group->next)
00759       (*cur_group->item)->walk(&Item::collect_item_field_processor, 0,
00760                                (unsigned char*) &indexed_fields);
00761   }
00762   else if (join->select_distinct)
00763   { /* Collect all query fields referenced in the SELECT clause. */
00764     List<Item> &select_items= join->fields_list;
00765     List<Item>::iterator select_items_it(select_items.begin());
00766     Item *item;
00767     while ((item= select_items_it++))
00768       item->walk(&Item::collect_item_field_processor, 0,
00769                  (unsigned char*) &indexed_fields);
00770   }
00771   else
00772     return;
00773 
00774   if (indexed_fields.size() == 0)
00775     return;
00776 
00777   /* Intersect the keys of all group fields. */
00778   cur_item= indexed_fields_it++;
00779   possible_keys|= cur_item->field->part_of_key;
00780   while ((cur_item= indexed_fields_it++))
00781   {
00782     possible_keys&= cur_item->field->part_of_key;
00783   }
00784 
00785   if (possible_keys.any())
00786     join_tab->const_keys|= possible_keys;
00787 }
00788 
00813 int join_tab_cmp(const void* ptr1, const void* ptr2)
00814 {
00815   JoinTable *jt1= *(JoinTable**) ptr1;
00816   JoinTable *jt2= *(JoinTable**) ptr2;
00817 
00818   if (jt1->dependent & jt2->table->map)
00819     return 1;
00820   if (jt2->dependent & jt1->table->map)
00821     return -1;
00822   if (jt1->found_records > jt2->found_records)
00823     return 1;
00824   if (jt1->found_records < jt2->found_records)
00825     return -1;
00826   return jt1 > jt2 ? 1 : (jt1 < jt2 ? -1 : 0);
00827 }
00828 
00832 int join_tab_cmp_straight(const void* ptr1, const void* ptr2)
00833 {
00834   JoinTable *jt1= *(JoinTable**) ptr1;
00835   JoinTable *jt2= *(JoinTable**) ptr2;
00836 
00837   if (jt1->dependent & jt2->table->map)
00838     return 1;
00839   if (jt2->dependent & jt1->table->map)
00840     return -1;
00841   return jt1 > jt2 ? 1 : (jt1 < jt2 ? -1 : 0);
00842 }
00843 
00847 void calc_used_field_length(Session *, JoinTable *join_tab)
00848 {
00849   uint32_t null_fields,blobs,fields,rec_length;
00850   Field **f_ptr,*field;
00851 
00852   null_fields= blobs= fields= rec_length=0;
00853   for (f_ptr=join_tab->table->getFields() ; (field= *f_ptr) ; f_ptr++)
00854   {
00855     if (field->isReadSet())
00856     {
00857       uint32_t flags=field->flags;
00858       fields++;
00859       rec_length+=field->pack_length();
00860       if (flags & BLOB_FLAG)
00861         blobs++;
00862       if (!(flags & NOT_NULL_FLAG))
00863         null_fields++;
00864     }
00865   }
00866   if (null_fields)
00867     rec_length+=(join_tab->table->getNullFields() + 7)/8;
00868   if (join_tab->table->maybe_null)
00869     rec_length+=sizeof(bool);
00870   if (blobs)
00871   {
00872     uint32_t blob_length=(uint32_t) (join_tab->table->cursor->stats.mean_rec_length-
00873                                      (join_tab->table->getRecordLength()- rec_length));
00874     rec_length+= max((uint32_t)4,blob_length);
00875   }
00876   join_tab->used_fields= fields;
00877   join_tab->used_fieldlength= rec_length;
00878   join_tab->used_blobs= blobs;
00879 }
00880 
00881 StoredKey *get_store_key(Session *session,
00882                          optimizer::KeyUse *keyuse,
00883                          table_map used_tables,
00884                    KeyPartInfo *key_part,
00885                          unsigned char *key_buff,
00886                          uint32_t maybe_null)
00887 {
00888   Item_ref *key_use_val= static_cast<Item_ref *>(keyuse->getVal());
00889   if (! ((~used_tables) & keyuse->getUsedTables())) // if const item
00890   {
00891     return new store_key_const_item(session,
00892             key_part->field,
00893             key_buff + maybe_null,
00894             maybe_null ? key_buff : 0,
00895             key_part->length,
00896             key_use_val);
00897   }
00898   else if (key_use_val->type() == Item::FIELD_ITEM ||
00899            (key_use_val->type() == Item::REF_ITEM &&
00900             key_use_val->ref_type() == Item_ref::OUTER_REF &&
00901             (*(Item_ref**)((Item_ref*)key_use_val)->ref)->ref_type() == Item_ref::DIRECT_REF &&
00902             key_use_val->real_item()->type() == Item::FIELD_ITEM))
00903   {
00904     return new store_key_field(session,
00905              key_part->field,
00906              key_buff + maybe_null,
00907              maybe_null ? key_buff : 0,
00908              key_part->length,
00909              ((Item_field*) key_use_val->real_item())->field,
00910              key_use_val->full_name());
00911   }
00912   return new store_key_item(session,
00913           key_part->field,
00914           key_buff + maybe_null,
00915           maybe_null ? key_buff : 0,
00916           key_part->length,
00917           key_use_val);
00918 }
00919 
00926 bool store_val_in_field(Field *field, Item *item, enum_check_fields check_flag)
00927 {
00928   bool error;
00929   Table *table= field->getTable();
00930   Session *session= table->in_use;
00931   ha_rows cuted_fields=session->cuted_fields;
00932 
00933   /*
00934     we should restore old value of count_cuted_fields because
00935     store_val_in_field can be called from insert_query
00936     with select_insert, which make count_cuted_fields= 1
00937    */
00938   enum_check_fields old_count_cuted_fields= session->count_cuted_fields;
00939   session->count_cuted_fields= check_flag;
00940   error= item->save_in_field(field, 1);
00941   session->count_cuted_fields= old_count_cuted_fields;
00942   return error || cuted_fields != session->cuted_fields;
00943 }
00944 
00945 inline void add_cond_and_fix(Item **e1, Item *e2)
00946 {
00947   if (*e1)
00948   {
00949     Item *res;
00950     if ((res= new Item_cond_and(*e1, e2)))
00951     {
00952       *e1= res;
00953       res->quick_fix_field();
00954     }
00955   }
00956   else
00957     *e1= e2;
00958 }
00959 
00960 bool create_ref_for_key(Join *join,
00961                         JoinTable *j,
00962                         optimizer::KeyUse *org_keyuse,
00963                         table_map used_tables)
00964 {
00965   optimizer::KeyUse *keyuse= org_keyuse;
00966   Session  *session= join->session;
00967   uint32_t keyparts;
00968   uint32_t length;
00969   uint32_t key;
00970   Table *table= NULL;
00971   KeyInfo *keyinfo= NULL;
00972 
00973   /*  Use best key from find_best */
00974   table= j->table;
00975   key= keyuse->getKey();
00976   keyinfo= table->key_info + key;
00977 
00978   {
00979     keyparts= length= 0;
00980     uint32_t found_part_ref_or_null= 0;
00981     /*
00982       Calculate length for the used key
00983       Stop if there is a missing key part or when we find second key_part
00984       with KEY_OPTIMIZE_REF_OR_NULL
00985     */
00986     do
00987     {
00988       if (! (~used_tables & keyuse->getUsedTables()))
00989       {
00990         if (keyparts == keyuse->getKeypart() &&
00991             ! (found_part_ref_or_null & keyuse->getOptimizeFlags()))
00992         {
00993           keyparts++;
00994           length+= keyinfo->key_part[keyuse->getKeypart()].store_length;
00995           found_part_ref_or_null|= keyuse->getOptimizeFlags();
00996         }
00997       }
00998       keyuse++;
00999     } while (keyuse->getTable() == table && keyuse->getKey() == key);
01000   }
01001 
01002   /* set up fieldref */
01003   keyinfo=table->key_info+key;
01004   j->ref.key_parts=keyparts;
01005   j->ref.key_length=length;
01006   j->ref.key=(int) key;
01007   if (!(j->ref.key_buff= (unsigned char*) session->calloc(ALIGN_SIZE(length)*2)) ||
01008       !(j->ref.key_copy= (StoredKey**) session->getMemRoot()->allocate((sizeof(StoredKey*) *
01009                (keyparts+1)))) ||
01010       !(j->ref.items=    (Item**) session->getMemRoot()->allocate(sizeof(Item*)*keyparts)) ||
01011       !(j->ref.cond_guards= (bool**) session->getMemRoot()->allocate(sizeof(uint*)*keyparts)))
01012   {
01013     return(true);
01014   }
01015   j->ref.key_buff2=j->ref.key_buff+ALIGN_SIZE(length);
01016   j->ref.key_err=1;
01017   j->ref.null_rejecting= 0;
01018   j->ref.disable_cache= false;
01019   keyuse=org_keyuse;
01020 
01021   StoredKey **ref_key= j->ref.key_copy;
01022   unsigned char *key_buff= j->ref.key_buff, *null_ref_key= 0;
01023   bool keyuse_uses_no_tables= true;
01024   {
01025     for (uint32_t i= 0; i < keyparts; keyuse++, i++)
01026     {
01027       while (keyuse->getKeypart() != i ||
01028              ((~used_tables) & keyuse->getUsedTables()))
01029         keyuse++;       /* Skip other parts */
01030 
01031       uint32_t maybe_null= test(keyinfo->key_part[i].null_bit);
01032       j->ref.items[i]= keyuse->getVal();    // Save for cond removal
01033       j->ref.cond_guards[i]= keyuse->getConditionalGuard();
01034       if (keyuse->isNullRejected())
01035         j->ref.null_rejecting |= 1 << i;
01036       keyuse_uses_no_tables= keyuse_uses_no_tables && ! keyuse->getUsedTables();
01037       if (! keyuse->getUsedTables() &&  !(join->select_options & SELECT_DESCRIBE))
01038       {         // Compare against constant
01039         store_key_item tmp(session, keyinfo->key_part[i].field,
01040                            key_buff + maybe_null,
01041                            maybe_null ?  key_buff : 0,
01042                            keyinfo->key_part[i].length, keyuse->getVal());
01043         if (session->is_fatal_error)
01044           return(true);
01045         tmp.copy();
01046       }
01047       else
01048         *ref_key++= get_store_key(session,
01049           keyuse,join->const_table_map,
01050           &keyinfo->key_part[i],
01051           key_buff, maybe_null);
01052       /*
01053         Remember if we are going to use REF_OR_NULL
01054         But only if field _really_ can be null i.e. we force AM_REF
01055         instead of AM_REF_OR_NULL in case if field can't be null
01056       */
01057       if ((keyuse->getOptimizeFlags() & KEY_OPTIMIZE_REF_OR_NULL) && maybe_null)
01058         null_ref_key= key_buff;
01059       key_buff+=keyinfo->key_part[i].store_length;
01060     }
01061   }
01062   *ref_key= 0;       // end_marker
01063   if (j->type == AM_CONST)
01064     j->table->const_table= 1;
01065   else if (((keyinfo->flags & (HA_NOSAME | HA_NULL_PART_KEY)) != HA_NOSAME) ||
01066            keyparts != keyinfo->key_parts || null_ref_key)
01067   {
01068     /* Must read with repeat */
01069     j->type= null_ref_key ? AM_REF_OR_NULL : AM_REF;
01070     j->ref.null_ref_key= null_ref_key;
01071   }
01072   else if (keyuse_uses_no_tables)
01073   {
01074     /*
01075       This happen if we are using a constant expression in the ON part
01076       of an LEFT JOIN.
01077       SELECT * FROM a LEFT JOIN b ON b.key=30
01078       Here we should not mark the table as a 'const' as a field may
01079       have a 'normal' value or a NULL value.
01080     */
01081     j->type= AM_CONST;
01082   }
01083   else
01084     j->type= AM_EQ_REF;
01085   return 0;
01086 }
01087 
01138 void add_not_null_conds(Join *join)
01139 {
01140   for (uint32_t i= join->const_tables; i < join->tables; i++)
01141   {
01142     JoinTable *tab=join->join_tab+i;
01143     if ((tab->type == AM_REF || tab->type == AM_EQ_REF ||
01144          tab->type == AM_REF_OR_NULL) &&
01145         !tab->table->maybe_null)
01146     {
01147       for (uint32_t keypart= 0; keypart < tab->ref.key_parts; keypart++)
01148       {
01149         if (tab->ref.null_rejecting & (1 << keypart))
01150         {
01151           Item *item= tab->ref.items[keypart];
01152           Item *notnull;
01153           assert(item->type() == Item::FIELD_ITEM);
01154           Item_field *not_null_item= (Item_field*)item;
01155           JoinTable *referred_tab= not_null_item->field->getTable()->reginfo.join_tab;
01156           /*
01157             For UPDATE queries such as:
01158             UPDATE t1 SET t1.f2=(SELECT MAX(t2.f4) FROM t2 WHERE t2.f3=t1.f1);
01159             not_null_item is the t1.f1, but it's referred_tab is 0.
01160           */
01161           if (!referred_tab || referred_tab->join != join)
01162             continue;
01163           if (!(notnull= new Item_func_isnotnull(not_null_item)))
01164             return;
01165           /*
01166             We need to do full fix_fields() call here in order to have correct
01167             notnull->const_item(). This is needed e.g. by test_quick_select
01168             when it is called from make_join_select after this function is
01169             called.
01170           */
01171           if (notnull->fix_fields(join->session, &notnull))
01172             return;
01173           add_cond_and_fix(&referred_tab->select_cond, notnull);
01174         }
01175       }
01176     }
01177   }
01178   return;
01179 }
01180 
01196 COND *add_found_match_trig_cond(JoinTable *tab, COND *cond, JoinTable *root_tab)
01197 {
01198   COND *tmp;
01199   assert(cond != 0);
01200   if (tab == root_tab)
01201     return cond;
01202   if ((tmp= add_found_match_trig_cond(tab->first_upper, cond, root_tab)))
01203     tmp= new Item_func_trig_cond(tmp, &tab->found);
01204   if (tmp)
01205   {
01206     tmp->quick_fix_field();
01207     tmp->update_used_tables();
01208   }
01209   return tmp;
01210 }
01211 
01212 #define ICP_COND_USES_INDEX_ONLY 10
01213 
01214 
01218 void JoinTable::cleanup()
01219 {
01220   safe_delete(select);
01221   safe_delete(quick);
01222 
01223   if (cache.buff)
01224   {
01225     size_t size= cache.end - cache.buff;
01226     global_join_buffer.sub(size);
01227     free(cache.buff);
01228   }
01229   cache.buff= 0;
01230   limit= 0;
01231   if (table)
01232   {
01233     if (table->key_read)
01234     {
01235       table->key_read= 0;
01236       table->cursor->extra(HA_EXTRA_NO_KEYREAD);
01237     }
01238     table->cursor->ha_index_or_rnd_end();
01239     /*
01240       We need to reset this for next select
01241       (Tested in part_of_refkey)
01242     */
01243     table->reginfo.join_tab= 0;
01244   }
01245   read_record.end_read_record();
01246 }
01247 
01248 bool only_eq_ref_tables(Join *join,Order *order,table_map tables)
01249 {
01250   for (JoinTable **tab=join->map2table ; tables ; tab++, tables>>=1)
01251   {
01252     if (tables & 1 && !eq_ref_table(join, order, *tab))
01253       return 0;
01254   }
01255   return 1;
01256 }
01257 
01277 bool eq_ref_table(Join *join, Order *start_order, JoinTable *tab)
01278 {
01279   if (tab->cached_eq_ref_table)     // If cached
01280     return tab->eq_ref_table;
01281   tab->cached_eq_ref_table=1;
01282   /* We can skip const tables only if not an outer table */
01283   if (tab->type == AM_CONST && !tab->first_inner)
01284     return (tab->eq_ref_table=1);
01285   if (tab->type != AM_EQ_REF || tab->table->maybe_null)
01286     return (tab->eq_ref_table=0);   // We must use this
01287   Item **ref_item=tab->ref.items;
01288   Item **end=ref_item+tab->ref.key_parts;
01289   uint32_t found=0;
01290   table_map map=tab->table->map;
01291 
01292   for (; ref_item != end ; ref_item++)
01293   {
01294     if (! (*ref_item)->const_item())
01295     {           // Not a const ref
01296       Order *order;
01297       for (order=start_order ; order ; order=order->next)
01298       {
01299         if ((*ref_item)->eq(order->item[0],0))
01300           break;
01301       }
01302       if (order)
01303       {
01304         found++;
01305         assert(!(order->used & map));
01306         order->used|=map;
01307         continue;       // Used in order_st BY
01308       }
01309       if (!only_eq_ref_tables(join,start_order, (*ref_item)->used_tables()))
01310         return (tab->eq_ref_table= 0);
01311     }
01312   }
01313   /* Check that there was no reference to table before sort order */
01314   for (; found && start_order ; start_order=start_order->next)
01315   {
01316     if (start_order->used & map)
01317     {
01318       found--;
01319       continue;
01320     }
01321     if (start_order->depend_map & map)
01322       return (tab->eq_ref_table= 0);
01323   }
01324   return tab->eq_ref_table= 1;
01325 }
01326 
01345 static Item_equal *find_item_equal(COND_EQUAL *cond_equal, Field *field, bool *inherited_fl)
01346 {
01347   Item_equal *item= 0;
01348   bool in_upper_level= false;
01349   while (cond_equal)
01350   {
01351     List<Item_equal>::iterator li(cond_equal->current_level.begin());
01352     while ((item= li++))
01353     {
01354       if (item->contains(field))
01355         goto finish;
01356     }
01357     in_upper_level= true;
01358     cond_equal= cond_equal->upper_levels;
01359   }
01360   in_upper_level= false;
01361 finish:
01362   *inherited_fl= in_upper_level;
01363   return item;
01364 }
01365 
01447 static bool check_simple_equality(Item *left_item,
01448                                   Item *right_item,
01449                                   Item *item,
01450                                   COND_EQUAL *cond_equal)
01451 {
01452   if (left_item->type() == Item::FIELD_ITEM &&
01453       right_item->type() == Item::FIELD_ITEM &&
01454       !((Item_field*)left_item)->depended_from &&
01455       !((Item_field*)right_item)->depended_from)
01456   {
01457     /* The predicate the form field1=field2 is processed */
01458 
01459     Field *left_field= ((Item_field*) left_item)->field;
01460     Field *right_field= ((Item_field*) right_item)->field;
01461 
01462     if (!left_field->eq_def(right_field))
01463       return false;
01464 
01465     /* Search for multiple equalities containing field1 and/or field2 */
01466     bool left_copyfl, right_copyfl;
01467     Item_equal *left_item_equal=
01468                find_item_equal(cond_equal, left_field, &left_copyfl);
01469     Item_equal *right_item_equal=
01470                find_item_equal(cond_equal, right_field, &right_copyfl);
01471 
01472     /* As (NULL=NULL) != true we can't just remove the predicate f=f */
01473     if (left_field->eq(right_field)) /* f = f */
01474       return (!(left_field->maybe_null() && !left_item_equal));
01475 
01476     if (left_item_equal && left_item_equal == right_item_equal)
01477     {
01478       /*
01479         The equality predicate is inference of one of the existing
01480         multiple equalities, i.e the condition is already covered
01481         by upper level equalities
01482       */
01483        return true;
01484     }
01485 
01486     bool copy_item_name= test(item && item->name >= subq_sj_cond_name &&
01487                               item->name < subq_sj_cond_name + 64);
01488     /* Copy the found multiple equalities at the current level if needed */
01489     if (left_copyfl)
01490     {
01491       /* left_item_equal of an upper level contains left_item */
01492       left_item_equal= new Item_equal(left_item_equal);
01493       cond_equal->current_level.push_back(left_item_equal);
01494       if (copy_item_name)
01495         left_item_equal->name = item->name;
01496     }
01497     if (right_copyfl)
01498     {
01499       /* right_item_equal of an upper level contains right_item */
01500       right_item_equal= new Item_equal(right_item_equal);
01501       cond_equal->current_level.push_back(right_item_equal);
01502       if (copy_item_name)
01503         right_item_equal->name = item->name;
01504     }
01505 
01506     if (left_item_equal)
01507     {
01508       /* left item was found in the current or one of the upper levels */
01509       if (! right_item_equal)
01510         left_item_equal->add((Item_field *) right_item);
01511       else
01512       {
01513         /* Merge two multiple equalities forming a new one */
01514         left_item_equal->merge(right_item_equal);
01515         /* Remove the merged multiple equality from the list */
01516         List<Item_equal>::iterator li(cond_equal->current_level.begin());
01517         while ((li++) != right_item_equal) {};
01518         li.remove();
01519       }
01520     }
01521     else
01522     {
01523       /* left item was not found neither the current nor in upper levels  */
01524       if (right_item_equal)
01525       {
01526         right_item_equal->add((Item_field *) left_item);
01527         if (copy_item_name)
01528           right_item_equal->name = item->name;
01529       }
01530       else
01531       {
01532         /* None of the fields was found in multiple equalities */
01533         Item_equal *item_equal= new Item_equal((Item_field *) left_item,
01534                                                (Item_field *) right_item);
01535         cond_equal->current_level.push_back(item_equal);
01536         if (copy_item_name)
01537           item_equal->name = item->name;
01538       }
01539     }
01540     return true;
01541   }
01542 
01543   {
01544     /* The predicate of the form field=const/const=field is processed */
01545     Item *const_item= 0;
01546     Item_field *field_item= 0;
01547     if (left_item->type() == Item::FIELD_ITEM &&
01548         !((Item_field*)left_item)->depended_from &&
01549         right_item->const_item())
01550     {
01551       field_item= (Item_field*) left_item;
01552       const_item= right_item;
01553     }
01554     else if (right_item->type() == Item::FIELD_ITEM &&
01555              !((Item_field*)right_item)->depended_from &&
01556              left_item->const_item())
01557     {
01558       field_item= (Item_field*) right_item;
01559       const_item= left_item;
01560     }
01561 
01562     if (const_item &&
01563         field_item->result_type() == const_item->result_type())
01564     {
01565       bool copyfl;
01566 
01567       if (field_item->result_type() == STRING_RESULT)
01568       {
01569         const CHARSET_INFO * const cs= ((Field_str*) field_item->field)->charset();
01570         if (!item)
01571         {
01572           Item_func_eq *eq_item;
01573           if ((eq_item= new Item_func_eq(left_item, right_item)))
01574             return false;
01575           eq_item->set_cmp_func();
01576           eq_item->quick_fix_field();
01577           item= eq_item;
01578         }
01579         if ((cs != ((Item_func *) item)->compare_collation()) ||
01580             !cs->coll->propagate(cs, 0, 0))
01581           return false;
01582       }
01583 
01584       Item_equal *item_equal = find_item_equal(cond_equal,
01585                                                field_item->field, &copyfl);
01586       if (copyfl)
01587       {
01588         item_equal= new Item_equal(item_equal);
01589         cond_equal->current_level.push_back(item_equal);
01590       }
01591       if (item_equal)
01592       {
01593         /*
01594           The flag cond_false will be set to 1 after this, if item_equal
01595           already contains a constant and its value is  not equal to
01596           the value of const_item.
01597         */
01598         item_equal->add(const_item);
01599       }
01600       else
01601       {
01602         item_equal= new Item_equal(const_item, field_item);
01603         cond_equal->current_level.push_back(item_equal);
01604       }
01605       return true;
01606     }
01607   }
01608   return false;
01609 }
01610 
01636 static bool check_row_equality(Session *session,
01637                                Item *left_row,
01638                                Item_row *right_row,
01639                                COND_EQUAL *cond_equal,
01640                                List<Item>* eq_list)
01641 {
01642   uint32_t n= left_row->cols();
01643   for (uint32_t i= 0 ; i < n; i++)
01644   {
01645     bool is_converted;
01646     Item *left_item= left_row->element_index(i);
01647     Item *right_item= right_row->element_index(i);
01648     if (left_item->type() == Item::ROW_ITEM &&
01649         right_item->type() == Item::ROW_ITEM)
01650     {
01651       is_converted= check_row_equality(session,
01652                                        (Item_row *) left_item,
01653                                        (Item_row *) right_item,
01654                      cond_equal, eq_list);
01655       if (!is_converted)
01656         session->lex().current_select->cond_count++;
01657     }
01658     else
01659     {
01660       is_converted= check_simple_equality(left_item, right_item, 0, cond_equal);
01661       session->lex().current_select->cond_count++;
01662     }
01663 
01664     if (!is_converted)
01665     {
01666       Item_func_eq *eq_item;
01667       if (!(eq_item= new Item_func_eq(left_item, right_item)))
01668         return false;
01669       eq_item->set_cmp_func();
01670       eq_item->quick_fix_field();
01671       eq_list->push_back(eq_item);
01672     }
01673   }
01674   return true;
01675 }
01676 
01706 static bool check_equality(Session *session, Item *item, COND_EQUAL *cond_equal, List<Item> *eq_list)
01707 {
01708   if (item->type() == Item::FUNC_ITEM &&
01709          ((Item_func*) item)->functype() == Item_func::EQ_FUNC)
01710   {
01711     Item *left_item= ((Item_func*) item)->arguments()[0];
01712     Item *right_item= ((Item_func*) item)->arguments()[1];
01713 
01714     if (left_item->type() == Item::ROW_ITEM &&
01715         right_item->type() == Item::ROW_ITEM)
01716     {
01717       session->lex().current_select->cond_count--;
01718       return check_row_equality(session,
01719                                 (Item_row *) left_item,
01720                                 (Item_row *) right_item,
01721                                 cond_equal, eq_list);
01722     }
01723     else
01724       return check_simple_equality(left_item, right_item, item, cond_equal);
01725   }
01726   return false;
01727 }
01728 
01792 static COND *build_equal_items_for_cond(Session *session, COND *cond, COND_EQUAL *inherited)
01793 {
01794   Item_equal *item_equal;
01795   COND_EQUAL cond_equal;
01796   cond_equal.upper_levels= inherited;
01797 
01798   if (cond->type() == Item::COND_ITEM)
01799   {
01800     List<Item> eq_list;
01801     bool and_level= ((Item_cond*) cond)->functype() ==
01802       Item_func::COND_AND_FUNC;
01803     List<Item> *args= ((Item_cond*) cond)->argument_list();
01804 
01805     List<Item>::iterator li(args->begin());
01806     Item *item;
01807 
01808     if (and_level)
01809     {
01810       /*
01811          Retrieve all conjucts of this level detecting the equality
01812          that are subject to substitution by multiple equality items and
01813          removing each such predicate from the conjunction after having
01814          found/created a multiple equality whose inference the predicate is.
01815      */
01816       while ((item= li++))
01817       {
01818         /*
01819           PS/SP note: we can safely remove a node from AND-OR
01820           structure here because it's restored before each
01821           re-execution of any prepared statement/stored procedure.
01822         */
01823         if (check_equality(session, item, &cond_equal, &eq_list))
01824           li.remove();
01825       }
01826 
01827       List<Item_equal>::iterator it(cond_equal.current_level.begin());
01828       while ((item_equal= it++))
01829       {
01830         item_equal->fix_length_and_dec();
01831         item_equal->update_used_tables();
01832         set_if_bigger(session->lex().current_select->max_equal_elems,
01833                       item_equal->members());
01834       }
01835 
01836       ((Item_cond_and*)cond)->cond_equal= cond_equal;
01837       inherited= &(((Item_cond_and*)cond)->cond_equal);
01838     }
01839     /*
01840        Make replacement of equality predicates for lower levels
01841        of the condition expression.
01842     */
01843     li= args->begin();
01844     while ((item= li++))
01845     {
01846       Item *new_item;
01847       if ((new_item= build_equal_items_for_cond(session, item, inherited)) != item)
01848       {
01849         /* This replacement happens only for standalone equalities */
01850         /*
01851           This is ok with PS/SP as the replacement is done for
01852           arguments of an AND/OR item, which are restored for each
01853           execution of PS/SP.
01854         */
01855         li.replace(new_item);
01856       }
01857     }
01858     if (and_level)
01859     {
01860       args->concat(&eq_list);
01861       args->concat((List<Item> *)&cond_equal.current_level);
01862     }
01863   }
01864   else if (cond->type() == Item::FUNC_ITEM)
01865   {
01866     List<Item> eq_list;
01867     /*
01868       If an equality predicate forms the whole and level,
01869       we call it standalone equality and it's processed here.
01870       E.g. in the following where condition
01871       WHERE a=5 AND (b=5 or a=c)
01872       (b=5) and (a=c) are standalone equalities.
01873       In general we can't leave alone standalone eqalities:
01874       for WHERE a=b AND c=d AND (b=c OR d=5)
01875       b=c is replaced by =(a,b,c,d).
01876      */
01877     if (check_equality(session, cond, &cond_equal, &eq_list))
01878     {
01879       int n= cond_equal.current_level.size() + eq_list.size();
01880       if (n == 0)
01881         return new Item_int((int64_t) 1,1);
01882       else if (n == 1)
01883       {
01884         if ((item_equal= cond_equal.current_level.pop()))
01885         {
01886           item_equal->fix_length_and_dec();
01887           item_equal->update_used_tables();
01888         }
01889         else
01890           item_equal= (Item_equal *) eq_list.pop();
01891         set_if_bigger(session->lex().current_select->max_equal_elems,
01892                       item_equal->members());
01893         return item_equal;
01894       }
01895       else
01896       {
01897         /*
01898           Here a new AND level must be created. It can happen only
01899           when a row equality is processed as a standalone predicate.
01900         */
01901         Item_cond_and *and_cond= new Item_cond_and(eq_list);
01902         and_cond->quick_fix_field();
01903         List<Item> *args= and_cond->argument_list();
01904         List<Item_equal>::iterator it(cond_equal.current_level.begin());
01905         while ((item_equal= it++))
01906         {
01907           item_equal->fix_length_and_dec();
01908           item_equal->update_used_tables();
01909           set_if_bigger(session->lex().current_select->max_equal_elems,
01910                         item_equal->members());
01911         }
01912         and_cond->cond_equal= cond_equal;
01913         args->concat((List<Item> *)&cond_equal.current_level);
01914 
01915         return and_cond;
01916       }
01917     }
01918     /*
01919       For each field reference in cond, not from equal item predicates,
01920       set a pointer to the multiple equality it belongs to (if there is any)
01921       as soon the field is not of a string type or the field reference is
01922       an argument of a comparison predicate.
01923     */
01924     unsigned char *is_subst_valid= (unsigned char *) 1;
01925     cond= cond->compile(&Item::subst_argument_checker,
01926                         &is_subst_valid,
01927                         &Item::equal_fields_propagator,
01928                         (unsigned char *) inherited);
01929     cond->update_used_tables();
01930   }
01931   return cond;
01932 }
01933 
01999 static COND *build_equal_items(Session *session, COND *cond,
02000                                COND_EQUAL *inherited,
02001                                List<TableList> *join_list,
02002                                COND_EQUAL **cond_equal_ref)
02003 {
02004   COND_EQUAL *cond_equal= 0;
02005 
02006   if (cond)
02007   {
02008     cond= build_equal_items_for_cond(session, cond, inherited);
02009     cond->update_used_tables();
02010     if (cond->type() == Item::COND_ITEM &&
02011         ((Item_cond*) cond)->functype() == Item_func::COND_AND_FUNC)
02012       cond_equal= &((Item_cond_and*) cond)->cond_equal;
02013     else if (cond->type() == Item::FUNC_ITEM &&
02014              ((Item_cond*) cond)->functype() == Item_func::MULT_EQUAL_FUNC)
02015     {
02016       cond_equal= new COND_EQUAL;
02017       cond_equal->current_level.push_back((Item_equal *) cond);
02018     }
02019   }
02020   if (cond_equal)
02021   {
02022     cond_equal->upper_levels= inherited;
02023     inherited= cond_equal;
02024   }
02025   *cond_equal_ref= cond_equal;
02026 
02027   if (join_list)
02028   {
02029     TableList *table;
02030     List<TableList>::iterator li(join_list->begin());
02031 
02032     while ((table= li++))
02033     {
02034       if (table->on_expr)
02035       {
02036         List<TableList> *nested_join_list= table->getNestedJoin() ?
02037           &table->getNestedJoin()->join_list : NULL;
02038         /*
02039           We can modify table->on_expr because its old value will
02040           be restored before re-execution of PS/SP.
02041         */
02042         table->on_expr= build_equal_items(session, table->on_expr, inherited,
02043                                           nested_join_list,
02044                                           &table->cond_equal);
02045       }
02046     }
02047   }
02048 
02049   return cond;
02050 }
02051 
02071 static int compare_fields_by_table_order(Item_field *field1,
02072                                          Item_field *field2,
02073                                          void *table_join_idx)
02074 {
02075   int cmp= 0;
02076   bool outer_ref= 0;
02077   if (field2->used_tables() & OUTER_REF_TABLE_BIT)
02078   {
02079     outer_ref= 1;
02080     cmp= -1;
02081   }
02082   if (field2->used_tables() & OUTER_REF_TABLE_BIT)
02083   {
02084     outer_ref= 1;
02085     cmp++;
02086   }
02087   if (outer_ref)
02088     return cmp;
02089   JoinTable **idx= (JoinTable **) table_join_idx;
02090   cmp= idx[field2->field->getTable()->tablenr]-idx[field1->field->getTable()->tablenr];
02091   return cmp < 0 ? -1 : (cmp ? 1 : 0);
02092 }
02093 
02133 static Item *eliminate_item_equal(COND *cond, COND_EQUAL *upper_levels, Item_equal *item_equal)
02134 {
02135   List<Item> eq_list;
02136   Item_func_eq *eq_item= 0;
02137   if (((Item *) item_equal)->const_item() && !item_equal->val_int())
02138     return new Item_int((int64_t) 0,1);
02139   Item *item_const= item_equal->get_const();
02140   Item_equal_iterator it(item_equal->begin());
02141   Item *head;
02142   if (item_const)
02143     head= item_const;
02144   else
02145   {
02146     head= item_equal->get_first();
02147     it++;
02148   }
02149   Item_field *item_field;
02150   while ((item_field= it++))
02151   {
02152     Item_equal *upper= item_field->find_item_equal(upper_levels);
02153     Item_field *item= item_field;
02154     if (upper)
02155     {
02156       if (item_const && upper->get_const())
02157         item= 0;
02158       else
02159       {
02160         Item_equal_iterator li(item_equal->begin());
02161         while ((item= li++) != item_field)
02162         {
02163           if (item->find_item_equal(upper_levels) == upper)
02164             break;
02165         }
02166       }
02167     }
02168     if (item == item_field)
02169     {
02170       if (eq_item)
02171         eq_list.push_back(eq_item);
02172       eq_item= new Item_func_eq(item_field, head);
02173       if (!eq_item)
02174         return 0;
02175       eq_item->set_cmp_func();
02176       eq_item->quick_fix_field();
02177    }
02178   }
02179 
02180   if (!cond && !&eq_list.front())
02181   {
02182     if (!eq_item)
02183       return new Item_int((int64_t) 1,1);
02184     return eq_item;
02185   }
02186 
02187   if (eq_item)
02188     eq_list.push_back(eq_item);
02189   if (!cond)
02190     cond= new Item_cond_and(eq_list);
02191   else
02192   {
02193     assert(cond->type() == Item::COND_ITEM);
02194     ((Item_cond *) cond)->add_at_head(&eq_list);
02195   }
02196 
02197   cond->quick_fix_field();
02198   cond->update_used_tables();
02199 
02200   return cond;
02201 }
02202 
02230 COND* substitute_for_best_equal_field(COND *cond, COND_EQUAL *cond_equal, void *table_join_idx)
02231 {
02232   Item_equal *item_equal;
02233 
02234   if (cond->type() == Item::COND_ITEM)
02235   {
02236     List<Item> *cond_list= ((Item_cond*) cond)->argument_list();
02237 
02238     bool and_level= ((Item_cond*) cond)->functype() ==
02239                       Item_func::COND_AND_FUNC;
02240     if (and_level)
02241     {
02242       cond_equal= &((Item_cond_and *) cond)->cond_equal;
02243       cond_list->disjoin((List<Item> *) &cond_equal->current_level);
02244 
02245       List<Item_equal>::iterator it(cond_equal->current_level.begin());
02246       while ((item_equal= it++))
02247       {
02248         item_equal->sort(&compare_fields_by_table_order, table_join_idx);
02249       }
02250     }
02251 
02252     List<Item>::iterator li(cond_list->begin());
02253     Item *item;
02254     while ((item= li++))
02255     {
02256       Item *new_item =substitute_for_best_equal_field(item, cond_equal,
02257                                                       table_join_idx);
02258       /*
02259         This works OK with PS/SP re-execution as changes are made to
02260         the arguments of AND/OR items only
02261       */
02262       if (new_item != item)
02263         li.replace(new_item);
02264     }
02265 
02266     if (and_level)
02267     {
02268       List<Item_equal>::iterator it(cond_equal->current_level.begin());
02269       while ((item_equal= it++))
02270       {
02271         cond= eliminate_item_equal(cond, cond_equal->upper_levels, item_equal);
02272         // This occurs when eliminate_item_equal() founds that cond is
02273         // always false and substitutes it with Item_int 0.
02274         // Due to this, value of item_equal will be 0, so just return it.
02275         if (cond->type() != Item::COND_ITEM)
02276           break;
02277       }
02278     }
02279     if (cond->type() == Item::COND_ITEM &&
02280         !((Item_cond*)cond)->argument_list()->size())
02281       cond= new Item_int((int32_t)cond->val_bool());
02282 
02283   }
02284   else if (cond->type() == Item::FUNC_ITEM &&
02285            ((Item_cond*) cond)->functype() == Item_func::MULT_EQUAL_FUNC)
02286   {
02287     item_equal= (Item_equal *) cond;
02288     item_equal->sort(&compare_fields_by_table_order, table_join_idx);
02289     if (cond_equal && &cond_equal->current_level.front() == item_equal)
02290       cond_equal= 0;
02291     return eliminate_item_equal(0, cond_equal, item_equal);
02292   }
02293   else
02294     cond->transform(&Item::replace_equal_field, 0);
02295   return cond;
02296 }
02297 
02310 void update_const_equal_items(COND *cond, JoinTable *tab)
02311 {
02312   if (!(cond->used_tables() & tab->table->map))
02313     return;
02314 
02315   if (cond->type() == Item::COND_ITEM)
02316   {
02317     List<Item> *cond_list= ((Item_cond*) cond)->argument_list();
02318     List<Item>::iterator li(cond_list->begin());
02319     Item *item;
02320     while ((item= li++))
02321       update_const_equal_items(item, tab);
02322   }
02323   else if (cond->type() == Item::FUNC_ITEM &&
02324            ((Item_cond*) cond)->functype() == Item_func::MULT_EQUAL_FUNC)
02325   {
02326     Item_equal *item_equal= (Item_equal *) cond;
02327     bool contained_const= item_equal->get_const() != NULL;
02328     item_equal->update_const();
02329     if (!contained_const && item_equal->get_const())
02330     {
02331       /* Update keys for range analysis */
02332       Item_equal_iterator it(item_equal->begin());
02333       Item_field *item_field;
02334       while ((item_field= it++))
02335       {
02336         Field *field= item_field->field;
02337         JoinTable *stat= field->getTable()->reginfo.join_tab;
02338         key_map possible_keys= field->key_start;
02339         possible_keys&= field->getTable()->keys_in_use_for_query;
02340         stat[0].const_keys|= possible_keys;
02341 
02342         /*
02343           For each field in the multiple equality (for which we know that it
02344           is a constant) we have to find its corresponding key part, and set
02345           that key part in const_key_parts.
02346         */
02347         if (possible_keys.any())
02348         {
02349           Table *field_tab= field->getTable();
02350           optimizer::KeyUse *use;
02351           for (use= stat->keyuse; use && use->getTable() == field_tab; use++)
02352             if (possible_keys.test(use->getKey()) &&
02353                 field_tab->key_info[use->getKey()].key_part[use->getKeypart()].field ==
02354                 field)
02355               field_tab->const_key_parts[use->getKey()]|= use->getKeypartMap();
02356         }
02357       }
02358     }
02359   }
02360 }
02361 
02362 /*
02363   change field = field to field = const for each found field = const in the
02364   and_level
02365 */
02366 static void change_cond_ref_to_const(Session *session,
02367                                      list<COND_CMP>& save_list,
02368                                      Item *and_father,
02369                                      Item *cond,
02370                                      Item *field,
02371                                      Item *value)
02372 {
02373   if (cond->type() == Item::COND_ITEM)
02374   {
02375     bool and_level= ((Item_cond*) cond)->functype() == Item_func::COND_AND_FUNC;
02376     List<Item>::iterator li(((Item_cond*) cond)->argument_list()->begin());
02377     Item *item;
02378     while ((item=li++))
02379       change_cond_ref_to_const(session, save_list, and_level ? cond : item, item, field, value);
02380 
02381     return;
02382   }
02383   if (cond->eq_cmp_result() == Item::COND_OK)
02384     return;         // Not a boolean function
02385 
02386   Item_bool_func2 *func=  (Item_bool_func2*) cond;
02387   Item **args= func->arguments();
02388   Item *left_item=  args[0];
02389   Item *right_item= args[1];
02390   Item_func::Functype functype=  func->functype();
02391 
02392   if (right_item->eq(field,0) && left_item != value &&
02393       right_item->cmp_context == field->cmp_context &&
02394       (left_item->result_type() != STRING_RESULT ||
02395        value->result_type() != STRING_RESULT ||
02396        left_item->collation.collation == value->collation.collation))
02397   {
02398     Item *tmp=value->clone_item();
02399     if (tmp)
02400     {
02401       tmp->collation.set(right_item->collation);
02402       args[1]= tmp;
02403       func->update_used_tables();
02404       if ((functype == Item_func::EQ_FUNC || functype == Item_func::EQUAL_FUNC) &&
02405           and_father != cond &&
02406           ! left_item->const_item())
02407       {
02408         cond->marker=1;
02409         save_list.push_back( COND_CMP(and_father, func) );
02410       }
02411       func->set_cmp_func();
02412     }
02413   }
02414   else if (left_item->eq(field,0) && right_item != value &&
02415            left_item->cmp_context == field->cmp_context &&
02416            (right_item->result_type() != STRING_RESULT ||
02417             value->result_type() != STRING_RESULT ||
02418             right_item->collation.collation == value->collation.collation))
02419   {
02420     Item *tmp= value->clone_item();
02421     if (tmp)
02422     {
02423       tmp->collation.set(left_item->collation);
02424       *args= tmp;
02425       value= tmp;
02426       func->update_used_tables();
02427       if ((functype == Item_func::EQ_FUNC || functype == Item_func::EQUAL_FUNC) &&
02428           and_father != cond &&
02429           ! right_item->const_item())
02430       {
02431         args[0]= args[1];                       // For easy check
02432         args[1]= value;
02433         cond->marker=1;
02434         save_list.push_back( COND_CMP(and_father, func) );
02435       }
02436       func->set_cmp_func();
02437     }
02438   }
02439 }
02440 
02449 Item *remove_additional_cond(Item* conds)
02450 {
02451   if (conds->name == in_additional_cond)
02452     return 0;
02453   if (conds->type() == Item::COND_ITEM)
02454   {
02455     Item_cond *cnd= (Item_cond*) conds;
02456     List<Item>::iterator li(cnd->argument_list()->begin());
02457     Item *item;
02458     while ((item= li++))
02459     {
02460       if (item->name == in_additional_cond)
02461       {
02462   li.remove();
02463   if (cnd->argument_list()->size() == 1)
02464     return &cnd->argument_list()->front();
02465   return conds;
02466       }
02467     }
02468   }
02469   return conds;
02470 }
02471 
02472 static void propagate_cond_constants(Session *session,
02473                                      list<COND_CMP>& save_list,
02474                                      COND *and_father,
02475                                      COND *cond)
02476 {
02477   if (cond->type() == Item::COND_ITEM)
02478   {
02479     bool and_level= ((Item_cond*) cond)->functype() == Item_func::COND_AND_FUNC;
02480     List<Item>::iterator li(((Item_cond*) cond)->argument_list()->begin());
02481     Item *item;
02482     list<COND_CMP> save;
02483     while ((item=li++))
02484     {
02485       propagate_cond_constants(session, save, and_level ? cond : item, item);
02486     }
02487     if (and_level)
02488     {
02489       // Handle other found items
02490       for (list<COND_CMP>::iterator iter= save.begin(); iter != save.end(); ++iter)
02491       {
02492         Item **args= iter->second->arguments();
02493         if (not args[0]->const_item())
02494         {
02495           change_cond_ref_to_const(session, save, iter->first,
02496                                    iter->first, args[0], args[1] );
02497         }
02498       }
02499     }
02500   }
02501   else if (and_father != cond && !cond->marker)   // In a AND group
02502   {
02503     if (cond->type() == Item::FUNC_ITEM &&
02504         (((Item_func*) cond)->functype() == Item_func::EQ_FUNC ||
02505         ((Item_func*) cond)->functype() == Item_func::EQUAL_FUNC))
02506     {
02507       Item_func_eq *func=(Item_func_eq*) cond;
02508       Item **args= func->arguments();
02509       bool left_const= args[0]->const_item();
02510       bool right_const= args[1]->const_item();
02511       if (!(left_const && right_const) &&
02512           args[0]->result_type() == args[1]->result_type())
02513       {
02514         if (right_const)
02515         {
02516                 resolve_const_item(session, &args[1], args[0]);
02517           func->update_used_tables();
02518                 change_cond_ref_to_const(session, save_list, and_father, and_father,
02519                                         args[0], args[1]);
02520         }
02521         else if (left_const)
02522         {
02523                 resolve_const_item(session, &args[0], args[1]);
02524           func->update_used_tables();
02525                 change_cond_ref_to_const(session, save_list, and_father, and_father,
02526                                         args[1], args[0]);
02527         }
02528       }
02529     }
02530   }
02531 }
02532 
02623 bool check_interleaving_with_nj(JoinTable *next_tab)
02624 {
02625   TableList *next_emb= next_tab->table->pos_in_table_list->getEmbedding();
02626   Join *join= next_tab->join;
02627 
02628   if ((join->cur_embedding_map & ~next_tab->embedding_map).any())
02629   {
02630     /*
02631       next_tab is outside of the "pair of brackets" we're currently in.
02632       Cannot add it.
02633     */
02634     return true;
02635   }
02636 
02637   /*
02638     Do update counters for "pairs of brackets" that we've left (marked as
02639     X,Y,Z in the above picture)
02640   */
02641   for (;next_emb; next_emb= next_emb->getEmbedding())
02642   {
02643     next_emb->getNestedJoin()->counter_++;
02644     if (next_emb->getNestedJoin()->counter_ == 1)
02645     {
02646       /*
02647         next_emb is the first table inside a nested join we've "entered". In
02648         the picture above, we're looking at the 'X' bracket. Don't exit yet as
02649         X bracket might have Y pair bracket.
02650       */
02651       join->cur_embedding_map |= next_emb->getNestedJoin()->nj_map;
02652     }
02653 
02654     if (next_emb->getNestedJoin()->join_list.size() !=
02655         next_emb->getNestedJoin()->counter_)
02656       break;
02657 
02658     /*
02659       We're currently at Y or Z-bracket as depicted in the above picture.
02660       Mark that we've left it and continue walking up the brackets hierarchy.
02661     */
02662     join->cur_embedding_map &= ~next_emb->getNestedJoin()->nj_map;
02663   }
02664   return false;
02665 }
02666 
02667 COND *optimize_cond(Join *join, COND *conds, List<TableList> *join_list, Item::cond_result *cond_value)
02668 {
02669   Session *session= join->session;
02670 
02671   if (!conds)
02672     *cond_value= Item::COND_TRUE;
02673   else
02674   {
02675     /*
02676       Build all multiple equality predicates and eliminate equality
02677       predicates that can be inferred from these multiple equalities.
02678       For each reference of a field included into a multiple equality
02679       that occurs in a function set a pointer to the multiple equality
02680       predicate. Substitute a constant instead of this field if the
02681       multiple equality contains a constant.
02682     */
02683     conds= build_equal_items(join->session, conds, NULL, join_list,
02684                              &join->cond_equal);
02685 
02686     /* change field = field to field = const for each found field = const */
02687     list<COND_CMP> temp;
02688     propagate_cond_constants(session, temp, conds, conds);
02689     /*
02690       Remove all instances of item == item
02691       Remove all and-levels where CONST item != CONST item
02692     */
02693     conds= remove_eq_conds(session, conds, cond_value) ;
02694   }
02695   return(conds);
02696 }
02697 
02708 COND *remove_eq_conds(Session *session, COND *cond, Item::cond_result *cond_value)
02709 {
02710   if (cond->type() == Item::COND_ITEM)
02711   {
02712     bool and_level= (((Item_cond*) cond)->functype() == Item_func::COND_AND_FUNC);
02713 
02714     List<Item>::iterator li(((Item_cond*) cond)->argument_list()->begin());
02715     Item::cond_result tmp_cond_value;
02716     bool should_fix_fields= false;
02717 
02718     *cond_value= Item::COND_UNDEF;
02719     Item *item;
02720     while ((item= li++))
02721     {
02722       Item *new_item= remove_eq_conds(session, item, &tmp_cond_value);
02723       if (! new_item)
02724         li.remove();
02725       else if (item != new_item)
02726       {
02727         li.replace(new_item);
02728         should_fix_fields= true;
02729       }
02730       if (*cond_value == Item::COND_UNDEF)
02731         *cond_value= tmp_cond_value;
02732 
02733       switch (tmp_cond_value)
02734       {
02735         case Item::COND_OK:     /* Not true or false */
02736           if (and_level || (*cond_value == Item::COND_FALSE))
02737             *cond_value= tmp_cond_value;
02738           break;
02739         case Item::COND_FALSE:
02740           if (and_level)
02741           {
02742             *cond_value= tmp_cond_value;
02743             return (COND *) NULL;     /* Always false */
02744           }
02745           break;
02746         case Item::COND_TRUE:
02747           if (! and_level)
02748           {
02749             *cond_value= tmp_cond_value;
02750             return (COND *) NULL;     /* Always true */
02751           }
02752           break;
02753         case Item::COND_UNDEF:      /* Impossible */
02754           break;
02755       }
02756     }
02757 
02758     if (should_fix_fields)
02759       cond->update_used_tables();
02760 
02761     if (! ((Item_cond*) cond)->argument_list()->size() || *cond_value != Item::COND_OK)
02762       return (COND*) NULL;
02763 
02764     if (((Item_cond*) cond)->argument_list()->size() == 1)
02765     {
02766       /* Argument list contains only one element, so reduce it so a single item, then remove list */
02767       item= &((Item_cond*) cond)->argument_list()->front();
02768       ((Item_cond*) cond)->argument_list()->clear();
02769       return item;
02770     }
02771   }
02772   else if (cond->type() == Item::FUNC_ITEM && ((Item_func*) cond)->functype() == Item_func::ISNULL_FUNC)
02773   {
02774     /*
02775       Handles this special case for some ODBC applications:
02776       The are requesting the row that was just updated with a auto_increment
02777       value with this construct:
02778 
02779       SELECT * from table_name where auto_increment_column IS NULL
02780       This will be changed to:
02781       SELECT * from table_name where auto_increment_column = LAST_INSERT_ID
02782     */
02783 
02784     Item_func_isnull *func= (Item_func_isnull*) cond;
02785     Item **args= func->arguments();
02786     if (args[0]->type() == Item::FIELD_ITEM)
02787     {
02788       Field *field= ((Item_field*) args[0])->field;
02789       if (field->flags & AUTO_INCREMENT_FLAG
02790           && ! field->getTable()->maybe_null
02791           && session->options & OPTION_AUTO_IS_NULL
02792           && (
02793             session->first_successful_insert_id_in_prev_stmt > 0
02794             && session->substitute_null_with_insert_id
02795             )
02796           )
02797       {
02798         COND *new_cond;
02799         if ((new_cond= new Item_func_eq(args[0], new Item_int("last_insert_id()",
02800                                                           session->read_first_successful_insert_id_in_prev_stmt(),
02801                                                           MY_INT64_NUM_DECIMAL_DIGITS))))
02802         {
02803           cond= new_cond;
02804           /*
02805             Item_func_eq can't be fixed after creation so we do not check
02806             cond->fixed, also it do not need tables so we use 0 as second
02807             argument.
02808           */
02809           cond->fix_fields(session, &cond);
02810         }
02811         /*
02812           IS NULL should be mapped to LAST_INSERT_ID only for first row, so
02813           clear for next row
02814         */
02815         session->substitute_null_with_insert_id= false;
02816       }
02817 #ifdef NOTDEFINED
02818       /* fix to replace 'NULL' dates with '0' (shreeve@uci.edu) */
02819       else if (
02820           ((field->type() == DRIZZLE_TYPE_DATE) || (field->type() == DRIZZLE_TYPE_DATETIME))
02821           && (field->flags & NOT_NULL_FLAG)
02822           && ! field->table->maybe_null)
02823       {
02824         COND *new_cond;
02825         if ((new_cond= new Item_func_eq(args[0],new Item_int("0", 0, 2))))
02826         {
02827           cond= new_cond;
02828           /*
02829             Item_func_eq can't be fixed after creation so we do not check
02830             cond->fixed, also it do not need tables so we use 0 as second
02831             argument.
02832           */
02833           cond->fix_fields(session, &cond);
02834         }
02835       }
02836 #endif /* NOTDEFINED */
02837     }
02838     if (cond->const_item())
02839     {
02840       *cond_value= eval_const_cond(cond) ? Item::COND_TRUE : Item::COND_FALSE;
02841       return (COND *) NULL;
02842     }
02843   }
02844   else if (cond->const_item() && !cond->is_expensive())
02845   /*
02846     @todo
02847     Excluding all expensive functions is too restritive we should exclude only
02848     materialized IN subquery predicates because they can't yet be evaluated
02849     here (they need additional initialization that is done later on).
02850 
02851     The proper way to exclude the subqueries would be to walk the cond tree and
02852     check for materialized subqueries there.
02853 
02854   */
02855   {
02856     *cond_value= eval_const_cond(cond) ? Item::COND_TRUE : Item::COND_FALSE;
02857     return (COND *) NULL;
02858   }
02859   else if ((*cond_value= cond->eq_cmp_result()) != Item::COND_OK)
02860   {
02861     /* boolan compare function */
02862     Item *left_item=  ((Item_func*) cond)->arguments()[0];
02863     Item *right_item= ((Item_func*) cond)->arguments()[1];
02864     if (left_item->eq(right_item,1))
02865     {
02866       if (!left_item->maybe_null || ((Item_func*) cond)->functype() == Item_func::EQUAL_FUNC)
02867         return (COND*) NULL;      /* Comparison of identical items */
02868     }
02869   }
02870   *cond_value= Item::COND_OK;
02871   return cond;          /* Point at next and return into recursion */
02872 }
02873 
02874 /*
02875   Check if equality can be used in removing components of GROUP BY/DISTINCT
02876 
02877   SYNOPSIS
02878     test_if_equality_guarantees_uniqueness()
02879       l          the left comparison argument (a field if any)
02880       r          the right comparison argument (a const of any)
02881 
02882   DESCRIPTION
02883     Checks if an equality predicate can be used to take away
02884     DISTINCT/GROUP BY because it is known to be true for exactly one
02885     distinct value (e.g. <expr> == <const>).
02886     Arguments must be of the same type because e.g.
02887     <string_field> = <int_const> may match more than 1 distinct value from
02888     the column.
02889     We must take into consideration and the optimization done for various
02890     string constants when compared to dates etc (see Item_int_with_ref) as
02891     well as the collation of the arguments.
02892 
02893   RETURN VALUE
02894     true    can be used
02895     false   cannot be used
02896 */
02897 static bool test_if_equality_guarantees_uniqueness(Item *l, Item *r)
02898 {
02899   return r->const_item() &&
02900     /* elements must be compared as dates */
02901      (Arg_comparator::can_compare_as_dates(l, r, 0) ||
02902       /* or of the same result type */
02903       (r->result_type() == l->result_type() &&
02904        /* and must have the same collation if compared as strings */
02905        (l->result_type() != STRING_RESULT ||
02906         l->collation.collation == r->collation.collation)));
02907 }
02908 
02912 bool const_expression_in_where(COND *cond, Item *comp_item, Item **const_item)
02913 {
02914   if (cond->type() == Item::COND_ITEM)
02915   {
02916     bool and_level= (((Item_cond*) cond)->functype()
02917          == Item_func::COND_AND_FUNC);
02918     List<Item>::iterator li(((Item_cond*) cond)->argument_list()->begin());
02919     Item *item;
02920     while ((item=li++))
02921     {
02922       bool res=const_expression_in_where(item, comp_item, const_item);
02923       if (res)          // Is a const value
02924       {
02925         if (and_level)
02926           return 1;
02927       }
02928       else if (!and_level)
02929         return 0;
02930     }
02931     return and_level ? 0 : 1;
02932   }
02933   else if (cond->eq_cmp_result() != Item::COND_OK)
02934   {           // boolan compare function
02935     Item_func* func= (Item_func*) cond;
02936     if (func->functype() != Item_func::EQUAL_FUNC &&
02937         func->functype() != Item_func::EQ_FUNC)
02938       return 0;
02939     Item *left_item=  ((Item_func*) cond)->arguments()[0];
02940     Item *right_item= ((Item_func*) cond)->arguments()[1];
02941     if (left_item->eq(comp_item,1))
02942     {
02943       if (test_if_equality_guarantees_uniqueness (left_item, right_item))
02944       {
02945         if (*const_item)
02946           return right_item->eq(*const_item, 1);
02947         *const_item=right_item;
02948         return 1;
02949       }
02950     }
02951     else if (right_item->eq(comp_item,1))
02952     {
02953       if (test_if_equality_guarantees_uniqueness (right_item, left_item))
02954       {
02955         if (*const_item)
02956           return left_item->eq(*const_item, 1);
02957         *const_item=left_item;
02958         return 1;
02959       }
02960     }
02961   }
02962   return 0;
02963 }
02964 
02976 Next_select_func setup_end_select_func(Join *join)
02977 {
02978   Table *table= join->tmp_table;
02979   Tmp_Table_Param *tmp_tbl= &join->tmp_table_param;
02980   Next_select_func end_select;
02981 
02982   /* Set up select_end */
02983   if (table)
02984   {
02985     if (table->group && tmp_tbl->sum_func_count &&
02986         !tmp_tbl->precomputed_group_by)
02987     {
02988       if (table->getShare()->sizeKeys())
02989       {
02990         end_select= end_update;
02991       }
02992       else
02993       {
02994         end_select= end_unique_update;
02995       }
02996     }
02997     else if (join->sort_and_group && !tmp_tbl->precomputed_group_by)
02998     {
02999       end_select= end_write_group;
03000     }
03001     else
03002     {
03003       end_select= end_write;
03004       if (tmp_tbl->precomputed_group_by)
03005       {
03006         /*
03007           A preceding call to create_tmp_table in the case when loose
03008           index scan is used guarantees that
03009           Tmp_Table_Param::items_to_copy has enough space for the group
03010           by functions. It is OK here to use memcpy since we copy
03011           Item_sum pointers into an array of Item pointers.
03012         */
03013         memcpy(tmp_tbl->items_to_copy + tmp_tbl->func_count,
03014                join->sum_funcs,
03015                sizeof(Item*)*tmp_tbl->sum_func_count);
03016         tmp_tbl->items_to_copy[tmp_tbl->func_count+tmp_tbl->sum_func_count]= 0;
03017       }
03018     }
03019   }
03020   else
03021   {
03022     if ((join->sort_and_group) &&
03023         !tmp_tbl->precomputed_group_by)
03024       end_select= end_send_group;
03025     else
03026       end_select= end_send;
03027   }
03028   return end_select;
03029 }
03030 
03041 int do_select(Join *join, List<Item> *fields, Table *table)
03042 {
03043   int rc= 0;
03044   enum_nested_loop_state error= NESTED_LOOP_OK;
03045   JoinTable *join_tab= NULL;
03046 
03047   join->tmp_table= table;     /* Save for easy recursion */
03048   join->fields= fields;
03049 
03050   if (table)
03051   {
03052     table->cursor->extra(HA_EXTRA_WRITE_CACHE);
03053     table->emptyRecord();
03054     if (table->group && join->tmp_table_param.sum_func_count &&
03055         table->getShare()->sizeKeys() && !table->cursor->inited)
03056     {
03057       int tmp_error;
03058       tmp_error= table->cursor->startIndexScan(0, 0);
03059       if (tmp_error != 0)
03060       {
03061         table->print_error(tmp_error, MYF(0));
03062         return -1;
03063       }
03064     }
03065   }
03066   /* Set up select_end */
03067   Next_select_func end_select= setup_end_select_func(join);
03068   if (join->tables)
03069   {
03070     join->join_tab[join->tables-1].next_select= end_select;
03071 
03072     join_tab=join->join_tab+join->const_tables;
03073   }
03074   join->send_records=0;
03075   if (join->tables == join->const_tables)
03076   {
03077     /*
03078       HAVING will be checked after processing aggregate functions,
03079       But WHERE should checkd here (we alredy have read tables)
03080     */
03081     if (!join->conds || join->conds->val_int())
03082     {
03083       error= (*end_select)(join, 0, 0);
03084       if (error == NESTED_LOOP_OK || error == NESTED_LOOP_QUERY_LIMIT)
03085         error= (*end_select)(join, 0, 1);
03086 
03087       /*
03088         If we don't go through evaluate_join_record(), do the counting
03089         here.  join->send_records is increased on success in end_send(),
03090         so we don't touch it here.
03091       */
03092       join->examined_rows++;
03093       join->session->row_count++;
03094       assert(join->examined_rows <= 1);
03095     }
03096     else if (join->send_row_on_empty_set())
03097     {
03098       List<Item> *columns_list= fields;
03099       rc= join->result->send_data(*columns_list);
03100     }
03101   }
03102   else
03103   {
03104     assert(join->tables);
03105     error= sub_select(join,join_tab,0);
03106     if (error == NESTED_LOOP_OK || error == NESTED_LOOP_NO_MORE_ROWS)
03107       error= sub_select(join,join_tab,1);
03108     if (error == NESTED_LOOP_QUERY_LIMIT)
03109       error= NESTED_LOOP_OK;                    /* select_limit used */
03110   }
03111   if (error == NESTED_LOOP_NO_MORE_ROWS)
03112     error= NESTED_LOOP_OK;
03113 
03114   if (error == NESTED_LOOP_OK)
03115   {
03116     /*
03117       Sic: this branch works even if rc != 0, e.g. when
03118       send_data above returns an error.
03119     */
03120     if (!table)         // If sending data to client
03121     {
03122       /*
03123         The following will unlock all cursors if the command wasn't an
03124         update command
03125       */
03126       join->join_free();      // Unlock all cursors
03127       if (join->result->send_eof())
03128         rc= 1;                                  // Don't send error
03129     }
03130   }
03131   else
03132     rc= -1;
03133   if (table)
03134   {
03135     int tmp, new_errno= 0;
03136     if ((tmp=table->cursor->extra(HA_EXTRA_NO_CACHE)))
03137     {
03138       new_errno= tmp;
03139     }
03140     if ((tmp=table->cursor->ha_index_or_rnd_end()))
03141     {
03142       new_errno= tmp;
03143     }
03144     if (new_errno)
03145       table->print_error(new_errno,MYF(0));
03146   }
03147   return(join->session->is_error() ? -1 : rc);
03148 }
03149 
03150 enum_nested_loop_state sub_select_cache(Join *join, JoinTable *join_tab, bool end_of_records)
03151 {
03152   enum_nested_loop_state rc;
03153 
03154   if (end_of_records)
03155   {
03156     rc= flush_cached_records(join,join_tab,false);
03157     if (rc == NESTED_LOOP_OK || rc == NESTED_LOOP_NO_MORE_ROWS)
03158       rc= sub_select(join,join_tab,end_of_records);
03159     return rc;
03160   }
03161   if (join->session->getKilled())   // If aborted by user
03162   {
03163     join->session->send_kill_message();
03164     return NESTED_LOOP_KILLED;
03165   }
03166   if (join_tab->use_quick != 2 || test_if_quick_select(join_tab) <= 0)
03167   {
03168     if (! join_tab->cache.store_record_in_cache())
03169       return NESTED_LOOP_OK;                     // There is more room in cache
03170     return flush_cached_records(join,join_tab,false);
03171   }
03172   rc= flush_cached_records(join, join_tab, true);
03173   if (rc == NESTED_LOOP_OK || rc == NESTED_LOOP_NO_MORE_ROWS)
03174     rc= sub_select(join, join_tab, end_of_records);
03175   return rc;
03176 }
03177 
03297 enum_nested_loop_state sub_select(Join *join, JoinTable *join_tab, bool end_of_records)
03298 {
03299   join_tab->table->null_row=0;
03300   if (end_of_records)
03301     return (*join_tab->next_select)(join,join_tab+1,end_of_records);
03302 
03303   int error;
03304   enum_nested_loop_state rc;
03305   ReadRecord *info= &join_tab->read_record;
03306 
03307   if (join->resume_nested_loop)
03308   {
03309     /* If not the last table, plunge down the nested loop */
03310     if (join_tab < join->join_tab + join->tables - 1)
03311       rc= (*join_tab->next_select)(join, join_tab + 1, 0);
03312     else
03313     {
03314       join->resume_nested_loop= false;
03315       rc= NESTED_LOOP_OK;
03316     }
03317   }
03318   else
03319   {
03320     join->return_tab= join_tab;
03321 
03322     if (join_tab->last_inner)
03323     {
03324       /* join_tab is the first inner table for an outer join operation. */
03325 
03326       /* Set initial state of guard variables for this table.*/
03327       join_tab->found=0;
03328       join_tab->not_null_compl= 1;
03329 
03330       /* Set first_unmatched for the last inner table of this group */
03331       join_tab->last_inner->first_unmatched= join_tab;
03332     }
03333     join->session->row_count= 0;
03334 
03335     error= (*join_tab->read_first_record)(join_tab);
03336     rc= evaluate_join_record(join, join_tab, error);
03337   }
03338 
03339   /*
03340     Note: psergey has added the 2nd part of the following condition; the
03341     change should probably be made in 5.1, too.
03342   */
03343   while (rc == NESTED_LOOP_OK && join->return_tab >= join_tab)
03344   {
03345     error= info->read_record(info);
03346     rc= evaluate_join_record(join, join_tab, error);
03347   }
03348 
03349   if (rc == NESTED_LOOP_NO_MORE_ROWS &&
03350       join_tab->last_inner && !join_tab->found)
03351     rc= evaluate_null_complemented_join_record(join, join_tab);
03352 
03353   if (rc == NESTED_LOOP_NO_MORE_ROWS)
03354     rc= NESTED_LOOP_OK;
03355   return rc;
03356 }
03357 
03358 int safe_index_read(JoinTable *tab)
03359 {
03360   int error;
03361   Table *table= tab->table;
03362   if ((error=table->cursor->index_read_map(table->getInsertRecord(),
03363                                          tab->ref.key_buff,
03364                                          make_prev_keypart_map(tab->ref.key_parts),
03365                                          HA_READ_KEY_EXACT)))
03366     return table->report_error(error);
03367   return 0;
03368 }
03369 
03382 int join_read_const(JoinTable *tab)
03383 {
03384   int error;
03385   Table *table= tab->table;
03386   if (table->status & STATUS_GARBAGE)   // If first read
03387   {
03388     table->status= 0;
03389     if (cp_buffer_from_ref(tab->join->session, &tab->ref))
03390       error= HA_ERR_KEY_NOT_FOUND;
03391     else
03392     {
03393       error=table->cursor->index_read_idx_map(table->getInsertRecord(),tab->ref.key,
03394                                             (unsigned char*) tab->ref.key_buff,
03395                                             make_prev_keypart_map(tab->ref.key_parts),
03396                                             HA_READ_KEY_EXACT);
03397     }
03398     if (error)
03399     {
03400       table->status= STATUS_NOT_FOUND;
03401       tab->table->mark_as_null_row();
03402       table->emptyRecord();
03403       if (error != HA_ERR_KEY_NOT_FOUND && error != HA_ERR_END_OF_FILE)
03404         return table->report_error(error);
03405       return -1;
03406     }
03407     table->storeRecord();
03408   }
03409   else if (!(table->status & ~STATUS_NULL_ROW)) // Only happens with left join
03410   {
03411     table->status=0;
03412     table->restoreRecord();     // restore old record
03413   }
03414   table->null_row=0;
03415   return table->status ? -1 : 0;
03416 }
03417 
03418 /*
03419   eq_ref access method implementation: "read_first" function
03420 
03421   SYNOPSIS
03422     join_read_key()
03423       tab  JoinTable of the accessed table
03424 
03425   DESCRIPTION
03426     This is "read_fist" function for the "ref" access method. The difference
03427     from "ref" is that it has a one-element "cache" (see cmp_buffer_with_ref)
03428 
03429   RETURN
03430     0  - Ok
03431    -1  - Row not found
03432     1  - Error
03433 */
03434 int join_read_key(JoinTable *tab)
03435 {
03436   int error;
03437   Table *table= tab->table;
03438 
03439   if (!table->cursor->inited)
03440   {
03441     error= table->cursor->startIndexScan(tab->ref.key, tab->sorted);
03442     if (error != 0)
03443     {
03444       table->print_error(error, MYF(0));
03445     }
03446   }
03447 
03448   /* @todo Why don't we do "Late NULLs Filtering" here? */
03449   if (cmp_buffer_with_ref(tab) ||
03450       (table->status & (STATUS_GARBAGE | STATUS_NO_PARENT | STATUS_NULL_ROW)))
03451   {
03452     if (tab->ref.key_err)
03453     {
03454       table->status=STATUS_NOT_FOUND;
03455       return -1;
03456     }
03457     error=table->cursor->index_read_map(table->getInsertRecord(),
03458                                       tab->ref.key_buff,
03459                                       make_prev_keypart_map(tab->ref.key_parts),
03460                                       HA_READ_KEY_EXACT);
03461     if (error && error != HA_ERR_KEY_NOT_FOUND && error != HA_ERR_END_OF_FILE)
03462       return table->report_error(error);
03463   }
03464   table->null_row=0;
03465   return table->status ? -1 : 0;
03466 }
03467 
03468 /*
03469   ref access method implementation: "read_first" function
03470 
03471   SYNOPSIS
03472     join_read_always_key()
03473       tab  JoinTable of the accessed table
03474 
03475   DESCRIPTION
03476     This is "read_first" function for the "ref" access method.
03477 
03478     The functon must leave the index initialized when it returns.
03479     ref_or_null access implementation depends on that.
03480 
03481   RETURN
03482     0  - Ok
03483    -1  - Row not found
03484     1  - Error
03485 */
03486 int join_read_always_key(JoinTable *tab)
03487 {
03488   int error;
03489   Table *table= tab->table;
03490 
03491   /* Initialize the index first */
03492   if (!table->cursor->inited)
03493   {
03494     error= table->cursor->startIndexScan(tab->ref.key, tab->sorted);
03495     if (error != 0)
03496       return table->report_error(error);
03497   }
03498 
03499   /* Perform "Late NULLs Filtering" (see internals manual for explanations) */
03500   for (uint32_t i= 0 ; i < tab->ref.key_parts ; i++)
03501   {
03502     if ((tab->ref.null_rejecting & 1 << i) && tab->ref.items[i]->is_null())
03503         return -1;
03504   }
03505 
03506   if (cp_buffer_from_ref(tab->join->session, &tab->ref))
03507     return -1;
03508   if ((error=table->cursor->index_read_map(table->getInsertRecord(),
03509                                          tab->ref.key_buff,
03510                                          make_prev_keypart_map(tab->ref.key_parts),
03511                                          HA_READ_KEY_EXACT)))
03512   {
03513     if (error != HA_ERR_KEY_NOT_FOUND && error != HA_ERR_END_OF_FILE)
03514       return table->report_error(error);
03515     return -1;
03516   }
03517 
03518   return 0;
03519 }
03520 
03525 int join_read_last_key(JoinTable *tab)
03526 {
03527   int error;
03528   Table *table= tab->table;
03529 
03530   if (!table->cursor->inited)
03531   {
03532     error= table->cursor->startIndexScan(tab->ref.key, tab->sorted);
03533     if (error != 0)
03534       return table->report_error(error);
03535   }
03536   if (cp_buffer_from_ref(tab->join->session, &tab->ref))
03537     return -1;
03538   if ((error=table->cursor->index_read_last_map(table->getInsertRecord(),
03539                                               tab->ref.key_buff,
03540                                               make_prev_keypart_map(tab->ref.key_parts))))
03541   {
03542     if (error != HA_ERR_KEY_NOT_FOUND && error != HA_ERR_END_OF_FILE)
03543       return table->report_error(error);
03544     return -1;
03545   }
03546   return 0;
03547 }
03548 
03549 int join_no_more_records(ReadRecord *)
03550 {
03551   return -1;
03552 }
03553 
03554 int join_read_next_same_diff(ReadRecord *info)
03555 {
03556   Table *table= info->table;
03557   JoinTable *tab=table->reginfo.join_tab;
03558   if (tab->insideout_match_tab->found_match)
03559   {
03560     KeyInfo *key= tab->table->key_info + tab->index;
03561     do
03562     {
03563       int error;
03564       /* Save index tuple from record to the buffer */
03565       key_copy(tab->insideout_buf, info->record, key, 0);
03566 
03567       if ((error=table->cursor->index_next_same(table->getInsertRecord(),
03568                                               tab->ref.key_buff,
03569                                               tab->ref.key_length)))
03570       {
03571         if (error != HA_ERR_END_OF_FILE)
03572           return table->report_error(error);
03573         table->status= STATUS_GARBAGE;
03574         return -1;
03575       }
03576     } while (!key_cmp(tab->table->key_info[tab->index].key_part,
03577                       tab->insideout_buf, key->key_length));
03578     tab->insideout_match_tab->found_match= 0;
03579     return 0;
03580   }
03581   else
03582     return join_read_next_same(info);
03583 }
03584 
03585 int join_read_next_same(ReadRecord *info)
03586 {
03587   int error;
03588   Table *table= info->table;
03589   JoinTable *tab=table->reginfo.join_tab;
03590 
03591   if ((error=table->cursor->index_next_same(table->getInsertRecord(),
03592             tab->ref.key_buff,
03593             tab->ref.key_length)))
03594   {
03595     if (error != HA_ERR_END_OF_FILE)
03596       return table->report_error(error);
03597     table->status= STATUS_GARBAGE;
03598     return -1;
03599   }
03600 
03601   return 0;
03602 }
03603 
03604 int join_read_prev_same(ReadRecord *info)
03605 {
03606   int error;
03607   Table *table= info->table;
03608   JoinTable *tab=table->reginfo.join_tab;
03609 
03610   if ((error=table->cursor->index_prev(table->getInsertRecord())))
03611     return table->report_error(error);
03612   if (key_cmp_if_same(table, tab->ref.key_buff, tab->ref.key,
03613                       tab->ref.key_length))
03614   {
03615     table->status=STATUS_NOT_FOUND;
03616     error= -1;
03617   }
03618   return error;
03619 }
03620 
03621 int join_init_quick_read_record(JoinTable *tab)
03622 {
03623   if (test_if_quick_select(tab) == -1)
03624     return -1;          /* No possible records */
03625   return join_init_read_record(tab);
03626 }
03627 
03628 int init_read_record_seq(JoinTable *tab)
03629 {
03630   tab->read_record.init_reard_record_sequential();
03631 
03632   if (tab->read_record.cursor->startTableScan(1))
03633     return 1;
03634   return (*tab->read_record.read_record)(&tab->read_record);
03635 }
03636 
03637 int test_if_quick_select(JoinTable *tab)
03638 {
03639   safe_delete(tab->select->quick);
03640 
03641   return tab->select->test_quick_select(tab->join->session, tab->keys,
03642           (table_map) 0, HA_POS_ERROR, 0, false);
03643 }
03644 
03645 int join_init_read_record(JoinTable *tab)
03646 {
03647   if (tab->select && tab->select->quick && tab->select->quick->reset())
03648     return 1;
03649 
03650   if (tab->read_record.init_read_record(tab->join->session, tab->table, tab->select, 1, true))
03651     return 1;
03652 
03653   return (*tab->read_record.read_record)(&tab->read_record);
03654 }
03655 
03656 int join_read_first(JoinTable *tab)
03657 {
03658   int error;
03659   Table *table=tab->table;
03660   if (!table->key_read && table->covering_keys.test(tab->index) &&
03661       !table->no_keyread)
03662   {
03663     table->key_read= 1;
03664     table->cursor->extra(HA_EXTRA_KEYREAD);
03665   }
03666   tab->table->status= 0;
03667   tab->read_record.table=table;
03668   tab->read_record.cursor=table->cursor;
03669   tab->read_record.index=tab->index;
03670   tab->read_record.record=table->getInsertRecord();
03671   if (tab->insideout_match_tab)
03672   {
03673     tab->read_record.do_insideout_scan= tab;
03674     tab->read_record.read_record=join_read_next_different;
03675     tab->insideout_match_tab->found_match= 0;
03676   }
03677   else
03678   {
03679     tab->read_record.read_record=join_read_next;
03680     tab->read_record.do_insideout_scan= 0;
03681   }
03682 
03683   if (!table->cursor->inited)
03684   {
03685     error= table->cursor->startIndexScan(tab->index, tab->sorted);
03686     if (error != 0)
03687     {
03688       table->report_error(error);
03689       return -1;
03690     }
03691   }
03692   if ((error=tab->table->cursor->index_first(tab->table->getInsertRecord())))
03693   {
03694     if (error != HA_ERR_KEY_NOT_FOUND && error != HA_ERR_END_OF_FILE)
03695       table->report_error(error);
03696     return -1;
03697   }
03698 
03699   return 0;
03700 }
03701 
03702 int join_read_next_different(ReadRecord *info)
03703 {
03704   JoinTable *tab= info->do_insideout_scan;
03705   if (tab->insideout_match_tab->found_match)
03706   {
03707     KeyInfo *key= tab->table->key_info + tab->index;
03708     do
03709     {
03710       int error;
03711       /* Save index tuple from record to the buffer */
03712       key_copy(tab->insideout_buf, info->record, key, 0);
03713 
03714       if ((error=info->cursor->index_next(info->record)))
03715         return info->table->report_error(error);
03716     } while (!key_cmp(tab->table->key_info[tab->index].key_part,
03717                       tab->insideout_buf, key->key_length));
03718     tab->insideout_match_tab->found_match= 0;
03719     return 0;
03720   }
03721   else
03722     return join_read_next(info);
03723 }
03724 
03725 int join_read_next(ReadRecord *info)
03726 {
03727   int error;
03728   if ((error=info->cursor->index_next(info->record)))
03729     return info->table->report_error(error);
03730   return 0;
03731 }
03732 
03733 int join_read_last(JoinTable *tab)
03734 {
03735   Table *table=tab->table;
03736   int error;
03737   if (!table->key_read && table->covering_keys.test(tab->index) &&
03738       !table->no_keyread)
03739   {
03740     table->key_read=1;
03741     table->cursor->extra(HA_EXTRA_KEYREAD);
03742   }
03743   tab->table->status=0;
03744   tab->read_record.read_record=join_read_prev;
03745   tab->read_record.table=table;
03746   tab->read_record.cursor=table->cursor;
03747   tab->read_record.index=tab->index;
03748   tab->read_record.record=table->getInsertRecord();
03749   if (!table->cursor->inited)
03750   {
03751     error= table->cursor->startIndexScan(tab->index, 1);
03752     if (error != 0)
03753       return table->report_error(error);
03754   }
03755   if ((error= tab->table->cursor->index_last(tab->table->getInsertRecord())))
03756     return table->report_error(error);
03757 
03758   return 0;
03759 }
03760 
03761 int join_read_prev(ReadRecord *info)
03762 {
03763   int error;
03764   if ((error= info->cursor->index_prev(info->record)))
03765     return info->table->report_error(error);
03766 
03767   return 0;
03768 }
03769 
03773 int join_read_always_key_or_null(JoinTable *tab)
03774 {
03775   int res;
03776 
03777   /* First read according to key which is NOT NULL */
03778   *tab->ref.null_ref_key= 0;      // Clear null byte
03779   if ((res= join_read_always_key(tab)) >= 0)
03780     return res;
03781 
03782   /* Then read key with null value */
03783   *tab->ref.null_ref_key= 1;      // Set null byte
03784   return safe_index_read(tab);
03785 }
03786 
03787 int join_read_next_same_or_null(ReadRecord *info)
03788 {
03789   int error;
03790   if ((error= join_read_next_same(info)) >= 0)
03791     return error;
03792   JoinTable *tab= info->table->reginfo.join_tab;
03793 
03794   /* Test if we have already done a read after null key */
03795   if (*tab->ref.null_ref_key)
03796     return -1;          // All keys read
03797   *tab->ref.null_ref_key= 1;      // Set null byte
03798   return safe_index_read(tab);      // then read null keys
03799 }
03800 
03801 enum_nested_loop_state end_send_group(Join *join, JoinTable *, bool end_of_records)
03802 {
03803   int idx= -1;
03804   enum_nested_loop_state ok_code= NESTED_LOOP_OK;
03805 
03806   if (!join->first_record || end_of_records ||
03807       (idx=test_if_item_cache_changed(join->group_fields)) >= 0)
03808   {
03809     if (join->first_record ||
03810         (end_of_records && !join->group && !join->group_optimized_away))
03811     {
03812       if (idx < (int) join->send_group_parts)
03813       {
03814         int error=0;
03815         {
03816           if (!join->first_record)
03817           {
03818                   List<Item>::iterator it(join->fields->begin());
03819                   Item *item;
03820             /* No matching rows for group function */
03821             join->clear();
03822 
03823             while ((item= it++))
03824               item->no_rows_in_result();
03825           }
03826           if (join->having && join->having->val_int() == 0)
03827             error= -1;        // Didn't satisfy having
03828           else
03829           {
03830             if (join->do_send_rows)
03831               error=join->result->send_data(*join->fields) ? 1 : 0;
03832             join->send_records++;
03833           }
03834           if (join->rollup.getState() != Rollup::STATE_NONE && error <= 0)
03835           {
03836             if (join->rollup_send_data((uint32_t) (idx+1)))
03837               error= 1;
03838           }
03839         }
03840         if (error > 0)
03841           return(NESTED_LOOP_ERROR);
03842         if (end_of_records)
03843           return(NESTED_LOOP_OK);
03844         if (join->send_records >= join->unit->select_limit_cnt &&
03845             join->do_send_rows)
03846         {
03847           if (!(join->select_options & OPTION_FOUND_ROWS))
03848             return(NESTED_LOOP_QUERY_LIMIT); // Abort nicely
03849           join->do_send_rows=0;
03850           join->unit->select_limit_cnt = HA_POS_ERROR;
03851         }
03852         else if (join->send_records >= join->fetch_limit)
03853         {
03854           /*
03855             There is a server side cursor and all rows
03856             for this fetch request are sent.
03857           */
03858           /*
03859             Preventing code duplication. When finished with the group reset
03860             the group functions and copy_fields. We fall through. bug #11904
03861           */
03862           ok_code= NESTED_LOOP_CURSOR_LIMIT;
03863         }
03864       }
03865     }
03866     else
03867     {
03868       if (end_of_records)
03869         return(NESTED_LOOP_OK);
03870       join->first_record=1;
03871       test_if_item_cache_changed(join->group_fields);
03872     }
03873     if (idx < (int) join->send_group_parts)
03874     {
03875       /*
03876         This branch is executed also for cursors which have finished their
03877         fetch limit - the reason for ok_code.
03878       */
03879       copy_fields(&join->tmp_table_param);
03880       if (init_sum_functions(join->sum_funcs, join->sum_funcs_end[idx+1]))
03881         return(NESTED_LOOP_ERROR);
03882       return(ok_code);
03883     }
03884   }
03885   if (update_sum_func(join->sum_funcs))
03886     return(NESTED_LOOP_ERROR);
03887   return(NESTED_LOOP_OK);
03888 }
03889 
03890 enum_nested_loop_state end_write_group(Join *join, JoinTable *, bool end_of_records)
03891 {
03892   Table *table=join->tmp_table;
03893   int   idx= -1;
03894 
03895   if (join->session->getKilled())
03896   {           // Aborted by user
03897     join->session->send_kill_message();
03898     return NESTED_LOOP_KILLED;
03899   }
03900   if (!join->first_record || end_of_records ||
03901       (idx=test_if_item_cache_changed(join->group_fields)) >= 0)
03902   {
03903     if (join->first_record || (end_of_records && !join->group))
03904     {
03905       int send_group_parts= join->send_group_parts;
03906       if (idx < send_group_parts)
03907       {
03908         if (!join->first_record)
03909         {
03910           /* No matching rows for group function */
03911           join->clear();
03912         }
03913         copy_sum_funcs(join->sum_funcs, join->sum_funcs_end[send_group_parts]);
03914         if (!join->having || join->having->val_int())
03915         {
03916           int error= table->cursor->insertRecord(table->getInsertRecord());
03917 
03918           if (error)
03919           {
03920             my_error(ER_USE_SQL_BIG_RESULT, MYF(0));
03921             return NESTED_LOOP_ERROR;
03922           }
03923         }
03924         if (join->rollup.getState() != Rollup::STATE_NONE)
03925         {
03926           if (join->rollup_write_data((uint32_t) (idx+1), table))
03927             return NESTED_LOOP_ERROR;
03928         }
03929         if (end_of_records)
03930           return NESTED_LOOP_OK;
03931       }
03932     }
03933     else
03934     {
03935       if (end_of_records)
03936         return NESTED_LOOP_OK;
03937       join->first_record=1;
03938       test_if_item_cache_changed(join->group_fields);
03939     }
03940     if (idx < (int) join->send_group_parts)
03941     {
03942       copy_fields(&join->tmp_table_param);
03943       if (copy_funcs(join->tmp_table_param.items_to_copy, join->session))
03944         return NESTED_LOOP_ERROR;
03945       if (init_sum_functions(join->sum_funcs, join->sum_funcs_end[idx+1]))
03946         return NESTED_LOOP_ERROR;
03947       return NESTED_LOOP_OK;
03948     }
03949   }
03950   if (update_sum_func(join->sum_funcs))
03951     return NESTED_LOOP_ERROR;
03952   return NESTED_LOOP_OK;
03953 }
03954 
03955 /*****************************************************************************
03956   Remove calculation with tables that aren't yet read. Remove also tests
03957   against fields that are read through key where the table is not a
03958   outer join table.
03959   We can't remove tests that are made against columns which are stored
03960   in sorted order.
03961   @return
03962     1 if right_item used is a removable reference key on left_item
03963     0 otherwise.
03964 ****************************************************************************/
03965 bool test_if_ref(Item_field *left_item,Item *right_item)
03966 {
03967   Field *field=left_item->field;
03968   // No need to change const test. We also have to keep tests on LEFT JOIN
03969   if (not field->getTable()->const_table && !field->getTable()->maybe_null)
03970   {
03971     Item *ref_item=part_of_refkey(field->getTable(),field);
03972     if (ref_item && ref_item->eq(right_item,1))
03973     {
03974       right_item= right_item->real_item();
03975       if (right_item->type() == Item::FIELD_ITEM)
03976         return (field->eq_def(((Item_field *) right_item)->field));
03977       /* remove equalities injected by IN->EXISTS transformation */
03978       else if (right_item->type() == Item::CACHE_ITEM)
03979         return ((Item_cache *)right_item)->eq_def (field);
03980       if (right_item->const_item() && !(right_item->is_null()))
03981       {
03982         /*
03983           We can remove binary fields and numerical fields except float,
03984           as float comparison isn't 100 % secure
03985           We have to keep normal strings to be able to check for end spaces
03986 
03987                 sergefp: the above seems to be too restrictive. Counterexample:
03988                   create table t100 (v varchar(10), key(v)) default charset=latin1;
03989                   insert into t100 values ('a'),('a ');
03990                   explain select * from t100 where v='a';
03991                 The EXPLAIN shows 'using Where'. Running the query returns both
03992                 rows, so it seems there are no problems with endspace in the most
03993                 frequent case?
03994         */
03995         if (field->binary() &&
03996             field->real_type() != DRIZZLE_TYPE_VARCHAR &&
03997             field->decimals() == 0)
03998         {
03999           return ! store_val_in_field(field, right_item, CHECK_FIELD_WARN);
04000         }
04001       }
04002     }
04003   }
04004   return 0;
04005 }
04006 
04007 /*
04008   Extract a condition that can be checked after reading given table
04009 
04010   SYNOPSIS
04011     make_cond_for_table()
04012       cond         Condition to analyze
04013       tables       Tables for which "current field values" are available
04014       used_table   Table that we're extracting the condition for (may
04015                    also include PSEUDO_TABLE_BITS
04016 
04017   DESCRIPTION
04018     Extract the condition that can be checked after reading the table
04019     specified in 'used_table', given that current-field values for tables
04020     specified in 'tables' bitmap are available.
04021 
04022     The function assumes that
04023       - Constant parts of the condition has already been checked.
04024       - Condition that could be checked for tables in 'tables' has already
04025         been checked.
04026 
04027     The function takes into account that some parts of the condition are
04028     guaranteed to be true by employed 'ref' access methods (the code that
04029     does this is located at the end, search down for "EQ_FUNC").
04030 
04031 
04032   SEE ALSO
04033     make_cond_for_info_schema uses similar algorithm
04034 
04035   RETURN
04036     Extracted condition
04037 */
04038 COND *make_cond_for_table(COND *cond, table_map tables, table_map used_table, bool exclude_expensive_cond)
04039 {
04040   if (used_table && !(cond->used_tables() & used_table) &&
04041     /*
04042       Exclude constant conditions not checked at optimization time if
04043       the table we are pushing conditions to is the first one.
04044       As a result, such conditions are not considered as already checked
04045       and will be checked at execution time, attached to the first table.
04046     */
04047     !((used_table & 1) && cond->is_expensive()))
04048     return (COND*) 0;       // Already checked
04049   if (cond->type() == Item::COND_ITEM)
04050   {
04051     if (((Item_cond*) cond)->functype() == Item_func::COND_AND_FUNC)
04052     {
04053       /* Create new top level AND item */
04054       Item_cond_and *new_cond=new Item_cond_and;
04055       if (!new_cond)
04056         return (COND*) 0;
04057       List<Item>::iterator li(((Item_cond*) cond)->argument_list()->begin());
04058       Item *item;
04059       while ((item=li++))
04060       {
04061         Item *fix= make_cond_for_table(item,tables,used_table,
04062                                             exclude_expensive_cond);
04063         if (fix)
04064           new_cond->argument_list()->push_back(fix);
04065       }
04066       switch (new_cond->argument_list()->size())
04067       {
04068         case 0:
04069           return (COND*) 0;     // Always true
04070         case 1:
04071           return &new_cond->argument_list()->front();
04072         default:
04073           /*
04074             Item_cond_and do not need fix_fields for execution, its parameters
04075             are fixed or do not need fix_fields, too
04076           */
04077           new_cond->quick_fix_field();
04078           new_cond->used_tables_cache= ((Item_cond_and*) cond)->used_tables_cache & tables;
04079           return new_cond;
04080       }
04081     }
04082     else
04083     {           // Or list
04084       Item_cond_or *new_cond=new Item_cond_or;
04085       if (!new_cond)
04086         return (COND*) 0;
04087       List<Item>::iterator li(((Item_cond*) cond)->argument_list()->begin());
04088       Item *item;
04089       while ((item=li++))
04090       {
04091         Item *fix= make_cond_for_table(item,tables,0L, exclude_expensive_cond);
04092         if (!fix)
04093           return (COND*) 0;     // Always true
04094         new_cond->argument_list()->push_back(fix);
04095       }
04096       /*
04097         Item_cond_and do not need fix_fields for execution, its parameters
04098         are fixed or do not need fix_fields, too
04099       */
04100       new_cond->quick_fix_field();
04101       new_cond->used_tables_cache= ((Item_cond_or*) cond)->used_tables_cache;
04102       new_cond->top_level_item();
04103       return new_cond;
04104     }
04105   }
04106 
04107   /*
04108     Because the following test takes a while and it can be done
04109     table_count times, we mark each item that we have examined with the result
04110     of the test
04111   */
04112 
04113   if (cond->marker == 3 || (cond->used_tables() & ~tables) ||
04114       /*
04115         When extracting constant conditions, treat expensive conditions as
04116         non-constant, so that they are not evaluated at optimization time.
04117       */
04118       (!used_table && exclude_expensive_cond && cond->is_expensive()))
04119     return (COND*) 0;       // Can't check this yet
04120   if (cond->marker == 2 || cond->eq_cmp_result() == Item::COND_OK)
04121     return cond;        // Not boolean op
04122 
04123   /*
04124     Remove equalities that are guaranteed to be true by use of 'ref' access
04125     method
04126   */
04127   if (((Item_func*) cond)->functype() == Item_func::EQ_FUNC)
04128   {
04129     Item *left_item=  ((Item_func*) cond)->arguments()[0];
04130     Item *right_item= ((Item_func*) cond)->arguments()[1];
04131     if (left_item->type() == Item::FIELD_ITEM && test_if_ref((Item_field*) left_item,right_item))
04132     {
04133       cond->marker=3;     // Checked when read
04134       return (COND*) 0;
04135     }
04136     if (right_item->type() == Item::FIELD_ITEM && test_if_ref((Item_field*) right_item,left_item))
04137     {
04138       cond->marker=3;     // Checked when read
04139       return (COND*) 0;
04140     }
04141   }
04142   cond->marker=2;
04143   return cond;
04144 }
04145 
04146 static Item *part_of_refkey(Table *table,Field *field)
04147 {
04148   if (!table->reginfo.join_tab)
04149     return (Item*) 0;             // field from outer non-select (UPDATE,...)
04150 
04151   uint32_t ref_parts=table->reginfo.join_tab->ref.key_parts;
04152   if (ref_parts)
04153   {
04154     KeyPartInfo *key_part=
04155       table->key_info[table->reginfo.join_tab->ref.key].key_part;
04156     uint32_t part;
04157 
04158     for (part=0 ; part < ref_parts ; part++)
04159     {
04160       if (table->reginfo.join_tab->ref.cond_guards[part])
04161         return 0;
04162     }
04163 
04164     for (part=0 ; part < ref_parts ; part++,key_part++)
04165     {
04166       if (field->eq(key_part->field) &&
04167     !(key_part->key_part_flag & HA_PART_KEY_SEG) &&
04168           //If field can be NULL, we should not remove this predicate, as
04169           //it may lead to non-rejection of NULL values.
04170           !(field->real_maybe_null()))
04171       {
04172   return table->reginfo.join_tab->ref.items[part];
04173       }
04174     }
04175   }
04176   return (Item*) 0;
04177 }
04178 
04199 static int test_if_order_by_key(Order *order, Table *table, uint32_t idx, uint32_t *used_key_parts)
04200 {
04201   KeyPartInfo *key_part= NULL;
04202   KeyPartInfo *key_part_end= NULL;
04203   key_part= table->key_info[idx].key_part;
04204   key_part_end= key_part + table->key_info[idx].key_parts;
04205   key_part_map const_key_parts=table->const_key_parts[idx];
04206   int reverse= 0;
04207   bool on_primary_key= false;
04208 
04209   for (; order ; order=order->next, const_key_parts>>=1)
04210   {
04211     Field *field=((Item_field*) (*order->item)->real_item())->field;
04212     int flag;
04213 
04214     /*
04215       Skip key parts that are constants in the WHERE clause.
04216       These are already skipped in the ORDER BY by const_expression_in_where()
04217     */
04218     for (; const_key_parts & 1 ; const_key_parts>>= 1)
04219       key_part++;
04220 
04221     if (key_part == key_part_end)
04222     {
04223       /*
04224         We are at the end of the key. Check if the engine has the primary
04225         key as a suffix to the secondary keys. If it has continue to check
04226         the primary key as a suffix.
04227       */
04228       if (!on_primary_key &&
04229           (table->cursor->getEngine()->check_flag(HTON_BIT_PRIMARY_KEY_IN_READ_INDEX)) &&
04230           table->getShare()->hasPrimaryKey())
04231       {
04232         on_primary_key= true;
04233         key_part= table->key_info[table->getShare()->getPrimaryKey()].key_part;
04234         key_part_end=key_part+table->key_info[table->getShare()->getPrimaryKey()].key_parts;
04235         const_key_parts=table->const_key_parts[table->getShare()->getPrimaryKey()];
04236 
04237         for (; const_key_parts & 1 ; const_key_parts>>= 1)
04238           key_part++;
04239         /*
04240          The primary and secondary key parts were all const (i.e. there's
04241          one row).  The sorting doesn't matter.
04242         */
04243         if (key_part == key_part_end && reverse == 0)
04244           return(1);
04245       }
04246       else
04247         return(0);
04248     }
04249 
04250     if (key_part->field != field)
04251       return(0);
04252 
04253     /* set flag to 1 if we can use read-next on key, else to -1 */
04254     flag= ((order->asc == !(key_part->key_part_flag & HA_REVERSE_SORT)) ?
04255            1 : -1);
04256     if (reverse && flag != reverse)
04257       return(0);
04258     reverse=flag;       // Remember if reverse
04259     key_part++;
04260   }
04261   *used_key_parts= on_primary_key ? table->key_info[idx].key_parts :
04262     (uint32_t) (key_part - table->key_info[idx].key_part);
04263   if (reverse == -1 && !(table->index_flags(idx) &
04264                          HA_READ_PREV))
04265     reverse= 0;                                 // Index can't be used
04266   return(reverse);
04267 }
04268 
04284 inline bool is_subkey(KeyPartInfo *key_part,
04285                       KeyPartInfo *ref_key_part,
04286                 KeyPartInfo *ref_key_part_end)
04287 {
04288   for (; ref_key_part < ref_key_part_end; key_part++, ref_key_part++)
04289     if (! key_part->field->eq(ref_key_part->field))
04290       return 0;
04291   return 1;
04292 }
04293 
04305 static uint32_t test_if_subkey(Order *order,
04306                                Table *table,
04307                                uint32_t ref,
04308                                uint32_t ref_key_parts,
04309                          const key_map *usable_keys)
04310 {
04311   uint32_t nr;
04312   uint32_t min_length= UINT32_MAX;
04313   uint32_t best= MAX_KEY;
04314   uint32_t not_used;
04315   KeyPartInfo *ref_key_part= table->key_info[ref].key_part;
04316   KeyPartInfo *ref_key_part_end= ref_key_part + ref_key_parts;
04317 
04318   for (nr= 0 ; nr < table->getShare()->sizeKeys() ; nr++)
04319   {
04320     if (usable_keys->test(nr) &&
04321   table->key_info[nr].key_length < min_length &&
04322   table->key_info[nr].key_parts >= ref_key_parts &&
04323   is_subkey(table->key_info[nr].key_part, ref_key_part,
04324       ref_key_part_end) &&
04325   test_if_order_by_key(order, table, nr, &not_used))
04326     {
04327       min_length= table->key_info[nr].key_length;
04328       best= nr;
04329     }
04330   }
04331   return best;
04332 }
04333 
04365 bool list_contains_unique_index(Table *table, bool (*find_func) (Field *, void *), void *data)
04366 {
04367   for (uint32_t keynr= 0; keynr < table->getShare()->sizeKeys(); keynr++)
04368   {
04369     if (keynr == table->getShare()->getPrimaryKey() ||
04370          (table->key_info[keynr].flags & HA_NOSAME))
04371     {
04372       KeyInfo *keyinfo= table->key_info + keynr;
04373       KeyPartInfo *key_part= NULL;
04374       KeyPartInfo *key_part_end= NULL;
04375 
04376       for (key_part=keyinfo->key_part,
04377            key_part_end=key_part+ keyinfo->key_parts;
04378            key_part < key_part_end;
04379            key_part++)
04380       {
04381         if (key_part->field->maybe_null() ||
04382             ! find_func(key_part->field, data))
04383           break;
04384       }
04385       if (key_part == key_part_end)
04386         return 1;
04387     }
04388   }
04389   return 0;
04390 }
04391 
04405 bool find_field_in_order_list (Field *field, void *data)
04406 {
04407   Order *group= (Order *) data;
04408   bool part_found= 0;
04409   for (Order *tmp_group= group; tmp_group; tmp_group=tmp_group->next)
04410   {
04411     Item *item= (*tmp_group->item)->real_item();
04412     if (item->type() == Item::FIELD_ITEM &&
04413         ((Item_field*) item)->field->eq(field))
04414     {
04415       part_found= 1;
04416       break;
04417     }
04418   }
04419   return part_found;
04420 }
04421 
04435 bool find_field_in_item_list (Field *field, void *data)
04436 {
04437   List<Item> *fields= (List<Item> *) data;
04438   bool part_found= 0;
04439   List<Item>::iterator li(fields->begin());
04440   Item *item;
04441 
04442   while ((item= li++))
04443   {
04444     if (item->type() == Item::FIELD_ITEM &&
04445         ((Item_field*) item)->field->eq(field))
04446     {
04447       part_found= 1;
04448       break;
04449     }
04450   }
04451   return part_found;
04452 }
04453 
04479 bool test_if_skip_sort_order(JoinTable *tab, Order *order, ha_rows select_limit, bool no_changes, const key_map *map)
04480 {
04481   int32_t ref_key;
04482   uint32_t ref_key_parts;
04483   int order_direction;
04484   uint32_t used_key_parts;
04485   Table *table=tab->table;
04486   optimizer::SqlSelect *select= tab->select;
04487   key_map usable_keys;
04488   optimizer::QuickSelectInterface *save_quick= NULL;
04489 
04490   /*
04491     Keys disabled by ALTER Table ... DISABLE KEYS should have already
04492     been taken into account.
04493   */
04494   usable_keys= *map;
04495 
04496   for (Order *tmp_order=order; tmp_order ; tmp_order=tmp_order->next)
04497   {
04498     Item *item= (*tmp_order->item)->real_item();
04499     if (item->type() != Item::FIELD_ITEM)
04500     {
04501       usable_keys.reset();
04502       return(0);
04503     }
04504     usable_keys&= ((Item_field*) item)->field->part_of_sortkey;
04505     if (usable_keys.none())
04506       return(0);          // No usable keys
04507   }
04508 
04509   ref_key= -1;
04510   /* Test if constant range in WHERE */
04511   if (tab->ref.key >= 0 && tab->ref.key_parts)
04512   {
04513     ref_key=     tab->ref.key;
04514     ref_key_parts= tab->ref.key_parts;
04515     if (tab->type == AM_REF_OR_NULL)
04516       return(0);
04517   }
04518   else if (select && select->quick)   // Range found by optimizer/range
04519   {
04520     int quick_type= select->quick->get_type();
04521     save_quick= select->quick;
04522     /*
04523       assume results are not ordered when index merge is used
04524       @todo sergeyp: Results of all index merge selects actually are ordered
04525       by clustered PK values.
04526     */
04527 
04528     if (quick_type == optimizer::QuickSelectInterface::QS_TYPE_INDEX_MERGE ||
04529         quick_type == optimizer::QuickSelectInterface::QS_TYPE_ROR_UNION ||
04530         quick_type == optimizer::QuickSelectInterface::QS_TYPE_ROR_INTERSECT)
04531       return(0);
04532     ref_key=     select->quick->index;
04533     ref_key_parts= select->quick->used_key_parts;
04534   }
04535 
04536   if (ref_key >= 0)
04537   {
04538     /*
04539       We come here when there is a REF key.
04540     */
04541     if (! usable_keys.test(ref_key))
04542     {
04543       /*
04544         We come here when ref_key is not among usable_keys
04545       */
04546       uint32_t new_ref_key;
04547       /*
04548         If using index only read, only consider other possible index only
04549         keys
04550       */
04551       if (table->covering_keys.test(ref_key))
04552         usable_keys&= table->covering_keys;
04553       if (tab->pre_idx_push_select_cond)
04554         tab->select_cond= tab->select->cond= tab->pre_idx_push_select_cond;
04555       if ((new_ref_key= test_if_subkey(order, table, ref_key, ref_key_parts,
04556                &usable_keys)) < MAX_KEY)
04557       {
04558         /* Found key that can be used to retrieve data in sorted order */
04559         if (tab->ref.key >= 0)
04560         {
04561           /*
04562             We'll use ref access method on key new_ref_key. In general case
04563             the index search tuple for new_ref_key will be different (e.g.
04564             when one index is defined as (part1, part2, ...) and another as
04565             (part1, part2(N), ...) and the WHERE clause contains
04566             "part1 = const1 AND part2=const2".
04567             So we build tab->ref from scratch here.
04568           */
04569           optimizer::KeyUse *keyuse= tab->keyuse;
04570           while (keyuse->getKey() != new_ref_key && keyuse->getTable() == tab->table)
04571             keyuse++;
04572 
04573           if (create_ref_for_key(tab->join, tab, keyuse,
04574                                  tab->join->const_table_map))
04575             return(0);
04576         }
04577         else
04578         {
04579           /*
04580             The range optimizer constructed QuickRange for ref_key, and
04581             we want to use instead new_ref_key as the index. We can't
04582             just change the index of the quick select, because this may
04583             result in an incosistent QUICK_SELECT object. Below we
04584             create a new QUICK_SELECT from scratch so that all its
04585             parameres are set correctly by the range optimizer.
04586            */
04587           key_map new_ref_key_map;
04588           new_ref_key_map.reset();  // Force the creation of quick select
04589           new_ref_key_map.set(new_ref_key); // only for new_ref_key.
04590 
04591           if (select->test_quick_select(tab->join->session, new_ref_key_map, 0,
04592                                         (tab->join->select_options &
04593                                          OPTION_FOUND_ROWS) ?
04594                                         HA_POS_ERROR :
04595                                         tab->join->unit->select_limit_cnt,0,
04596                                         true) <=
04597               0)
04598             return(0);
04599         }
04600         ref_key= new_ref_key;
04601       }
04602     }
04603     /* Check if we get the rows in requested sorted order by using the key */
04604     if (usable_keys.test(ref_key) &&
04605         (order_direction= test_if_order_by_key(order,table,ref_key,
04606                  &used_key_parts)))
04607       goto check_reverse_order;
04608   }
04609   {
04610     /*
04611       Check whether there is an index compatible with the given order
04612       usage of which is cheaper than usage of the ref_key index (ref_key>=0)
04613       or a table scan.
04614       It may be the case if order_st/GROUP BY is used with LIMIT.
04615     */
04616     uint32_t nr;
04617     key_map keys;
04618     uint32_t best_key_parts= 0;
04619     int best_key_direction= 0;
04620     ha_rows best_records= 0;
04621     double read_time;
04622     int best_key= -1;
04623     bool is_best_covering= false;
04624     double fanout= 1;
04625     Join *join= tab->join;
04626     uint32_t tablenr= tab - join->join_tab;
04627     ha_rows table_records= table->cursor->stats.records;
04628     bool group= join->group && order == join->group_list;
04629     optimizer::Position cur_pos;
04630 
04631     /*
04632       If not used with LIMIT, only use keys if the whole query can be
04633       resolved with a key;  This is because filesort() is usually faster than
04634       retrieving all rows through an index.
04635     */
04636     if (select_limit >= table_records)
04637     {
04638       /*
04639         filesort() and join cache are usually faster than reading in
04640         index order and not using join cache
04641         */
04642       if (tab->type == AM_ALL && tab->join->tables > tab->join->const_tables + 1)
04643         return(0);
04644       keys= *table->cursor->keys_to_use_for_scanning();
04645       keys|= table->covering_keys;
04646 
04647       /*
04648         We are adding here also the index specified in FORCE INDEX clause,
04649         if any.
04650         This is to allow users to use index in order_st BY.
04651       */
04652       if (table->force_index)
04653         keys|= (group ? table->keys_in_use_for_group_by :
04654                                 table->keys_in_use_for_order_by);
04655       keys&= usable_keys;
04656     }
04657     else
04658       keys= usable_keys;
04659 
04660     cur_pos= join->getPosFromOptimalPlan(tablenr);
04661     read_time= cur_pos.getCost();
04662     for (uint32_t i= tablenr+1; i < join->tables; i++)
04663     {
04664       cur_pos= join->getPosFromOptimalPlan(i);
04665       fanout*= cur_pos.getFanout(); // fanout is always >= 1
04666     }
04667 
04668     for (nr=0; nr < table->getShare()->sizeKeys() ; nr++)
04669     {
04670       int direction;
04671       if (keys.test(nr) &&
04672           (direction= test_if_order_by_key(order, table, nr, &used_key_parts)))
04673       {
04674         bool is_covering= table->covering_keys.test(nr) || (nr == table->getShare()->getPrimaryKey() && table->cursor->primary_key_is_clustered());
04675 
04676         /*
04677           Don't use an index scan with ORDER BY without limit.
04678           For GROUP BY without limit always use index scan
04679           if there is a suitable index.
04680           Why we hold to this asymmetry hardly can be explained
04681           rationally. It's easy to demonstrate that using
04682           temporary table + filesort could be cheaper for grouping
04683           queries too.
04684         */
04685         if (is_covering ||
04686             select_limit != HA_POS_ERROR ||
04687             (ref_key < 0 && (group || table->force_index)))
04688         {
04689           double rec_per_key;
04690           double index_scan_time;
04691           KeyInfo *keyinfo= tab->table->key_info+nr;
04692           if (select_limit == HA_POS_ERROR)
04693             select_limit= table_records;
04694           if (group)
04695           {
04696             rec_per_key= keyinfo->rec_per_key[used_key_parts-1];
04697             set_if_bigger(rec_per_key, 1.0);
04698             /*
04699               With a grouping query each group containing on average
04700               rec_per_key records produces only one row that will
04701               be included into the result set.
04702             */
04703             if (select_limit > table_records/rec_per_key)
04704                 select_limit= table_records;
04705             else
04706               select_limit= (ha_rows) (select_limit*rec_per_key);
04707           }
04708           /*
04709             If tab=tk is not the last joined table tn then to get first
04710             L records from the result set we can expect to retrieve
04711             only L/fanout(tk,tn) where fanout(tk,tn) says how many
04712             rows in the record set on average will match each row tk.
04713             Usually our estimates for fanouts are too pessimistic.
04714             So the estimate for L/fanout(tk,tn) will be too optimistic
04715             and as result we'll choose an index scan when using ref/range
04716             access + filesort will be cheaper.
04717           */
04718           select_limit= (ha_rows) (select_limit < fanout ?
04719                                    1 : select_limit/fanout);
04720           /*
04721             We assume that each of the tested indexes is not correlated
04722             with ref_key. Thus, to select first N records we have to scan
04723             N/selectivity(ref_key) index entries.
04724             selectivity(ref_key) = #scanned_records/#table_records =
04725             table->quick_condition_rows/table_records.
04726             In any case we can't select more than #table_records.
04727             N/(table->quick_condition_rows/table_records) > table_records
04728             <=> N > table->quick_condition_rows.
04729           */
04730           if (select_limit > table->quick_condition_rows)
04731             select_limit= table_records;
04732           else
04733             select_limit= (ha_rows) (select_limit *
04734                                      (double) table_records /
04735                                       table->quick_condition_rows);
04736           rec_per_key= keyinfo->rec_per_key[keyinfo->key_parts-1];
04737           set_if_bigger(rec_per_key, 1.0);
04738           /*
04739             Here we take into account the fact that rows are
04740             accessed in sequences rec_per_key records in each.
04741             Rows in such a sequence are supposed to be ordered
04742             by rowid/primary key. When reading the data
04743             in a sequence we'll touch not more pages than the
04744             table cursor contains.
04745             TODO. Use the formula for a disk sweep sequential access
04746             to calculate the cost of accessing data rows for one
04747             index entry.
04748           */
04749           index_scan_time= select_limit/rec_per_key *
04750                            min(rec_per_key, table->cursor->scan_time());
04751           if (is_covering || (ref_key < 0 && (group || table->force_index)) ||
04752               index_scan_time < read_time)
04753           {
04754             ha_rows quick_records= table_records;
04755             if (is_best_covering && !is_covering)
04756               continue;
04757             if (table->quick_keys.test(nr))
04758               quick_records= table->quick_rows[nr];
04759             if (best_key < 0 ||
04760                 (select_limit <= min(quick_records,best_records) ?
04761                  keyinfo->key_parts < best_key_parts :
04762                  quick_records < best_records))
04763             {
04764               best_key= nr;
04765               best_key_parts= keyinfo->key_parts;
04766               best_records= quick_records;
04767               is_best_covering= is_covering;
04768               best_key_direction= direction;
04769             }
04770           }
04771         }
04772       }
04773     }
04774     if (best_key >= 0)
04775     {
04776       bool quick_created= false;
04777       if (table->quick_keys.test(best_key) && best_key != ref_key)
04778       {
04779         key_map test_map;
04780         test_map.reset();       // Force the creation of quick select
04781         test_map.set(best_key); // only best_key.
04782         quick_created=
04783           select->test_quick_select(join->session, test_map, 0,
04784                                     join->select_options & OPTION_FOUND_ROWS ?
04785                                     HA_POS_ERROR :
04786                                     join->unit->select_limit_cnt,
04787                                     true, false) > 0;
04788       }
04789       if (!no_changes)
04790       {
04791         if (!quick_created)
04792         {
04793           tab->index= best_key;
04794           tab->read_first_record= best_key_direction > 0 ?
04795                                   join_read_first:join_read_last;
04796           tab->type= AM_NEXT;           // Read with index_first(), index_next()
04797           if (select && select->quick)
04798           {
04799             safe_delete(select->quick);
04800           }
04801           if (table->covering_keys.test(best_key))
04802           {
04803             table->key_read=1;
04804             table->cursor->extra(HA_EXTRA_KEYREAD);
04805           }
04806           table->cursor->ha_index_or_rnd_end();
04807           if (join->select_options & SELECT_DESCRIBE)
04808           {
04809             tab->ref.key= -1;
04810             tab->ref.key_parts= 0;
04811             if (select_limit < table_records)
04812               tab->limit= select_limit;
04813           }
04814         }
04815         else if (tab->type != AM_ALL)
04816         {
04817           /*
04818             We're about to use a quick access to the table.
04819             We need to change the access method so as the quick access
04820             method is actually used.
04821           */
04822           assert(tab->select->quick);
04823           tab->type= AM_ALL;
04824           tab->use_quick=1;
04825           tab->ref.key= -1;
04826           tab->ref.key_parts=0;   // Don't use ref key.
04827           tab->read_first_record= join_init_read_record;
04828         }
04829       }
04830       used_key_parts= best_key_parts;
04831       order_direction= best_key_direction;
04832     }
04833     else
04834       return(0);
04835   }
04836 
04837 check_reverse_order:
04838   if (order_direction == -1)    // If ORDER BY ... DESC
04839   {
04840     if (select && select->quick)
04841     {
04842       /*
04843         Don't reverse the sort order, if it's already done.
04844         (In some cases test_if_order_by_key() can be called multiple times
04845       */
04846       if (! select->quick->reverse_sorted())
04847       {
04848         optimizer::QuickSelectDescending *tmp= NULL;
04849         bool error= false;
04850         int quick_type= select->quick->get_type();
04851         if (quick_type == optimizer::QuickSelectInterface::QS_TYPE_INDEX_MERGE ||
04852             quick_type == optimizer::QuickSelectInterface::QS_TYPE_ROR_INTERSECT ||
04853             quick_type == optimizer::QuickSelectInterface::QS_TYPE_ROR_UNION ||
04854             quick_type == optimizer::QuickSelectInterface::QS_TYPE_GROUP_MIN_MAX)
04855         {
04856           tab->limit= 0;
04857           select->quick= save_quick;
04858           return 0; // Use filesort
04859         }
04860 
04861         /* ORDER BY range_key DESC */
04862         tmp= new optimizer::QuickSelectDescending((optimizer::QuickRangeSelect*)(select->quick),
04863                                                   used_key_parts,
04864                                                   &error);
04865         if (! tmp || error)
04866         {
04867           delete tmp;
04868           select->quick= save_quick;
04869           tab->limit= 0;
04870           return 0; // Reverse sort not supported
04871         }
04872         select->quick= tmp;
04873       }
04874     }
04875     else if (tab->type != AM_NEXT &&
04876              tab->ref.key >= 0 && tab->ref.key_parts <= used_key_parts)
04877     {
04878       /*
04879         SELECT * FROM t1 WHERE a=1 ORDER BY a DESC,b DESC
04880 
04881         Use a traversal function that starts by reading the last row
04882         with key part (A) and then traverse the index backwards.
04883       */
04884       tab->read_first_record= join_read_last_key;
04885       tab->read_record.read_record= join_read_prev_same;
04886     }
04887   }
04888   else if (select && select->quick)
04889     select->quick->sorted= 1;
04890   return 1;
04891 }
04892 
04893 /*
04894   If not selecting by given key, create an index how records should be read
04895 
04896   SYNOPSIS
04897    create_sort_index()
04898      session    Thread Cursor
04899      tab    Table to sort (in join structure)
04900      order    How table should be sorted
04901      filesort_limit Max number of rows that needs to be sorted
04902      select_limit Max number of rows in final output
04903             Used to decide if we should use index or not
04904      is_order_by        true if we are sorting on order_st BY, false if GROUP BY
04905                         Used to decide if we should use index or not
04906 
04907 
04908   IMPLEMENTATION
04909    - If there is an index that can be used, 'tab' is modified to use
04910      this index.
04911    - If no index, create with filesort() an index cursor that can be used to
04912      retrieve rows in order (should be done with 'read_record').
04913      The sorted data is stored in tab->table and will be freed when calling
04914      tab->table->free_io_cache().
04915 
04916   RETURN VALUES
04917     0   ok
04918     -1    Some fatal error
04919     1   No records
04920 */
04921 int create_sort_index(Session *session, Join *join, Order *order, ha_rows filesort_limit, ha_rows select_limit, bool is_order_by)
04922 {
04923   uint32_t length= 0;
04924   ha_rows examined_rows;
04925   Table *table;
04926   optimizer::SqlSelect *select= NULL;
04927   JoinTable *tab;
04928 
04929   if (join->tables == join->const_tables)
04930     return(0);        // One row, no need to sort
04931   tab=    join->join_tab + join->const_tables;
04932   table=  tab->table;
04933   select= tab->select;
04934 
04935   /*
04936     When there is SQL_BIG_RESULT do not sort using index for GROUP BY,
04937     and thus force sorting on disk unless a group min-max optimization
04938     is going to be used as it is applied now only for one table queries
04939     with covering indexes.
04940   */
04941   if ((order != join->group_list ||
04942        !(join->select_options & SELECT_BIG_RESULT) ||
04943        (select && select->quick && (select->quick->get_type() == optimizer::QuickSelectInterface::QS_TYPE_GROUP_MIN_MAX))) &&
04944       test_if_skip_sort_order(tab,order,select_limit,0,
04945                               is_order_by ?  &table->keys_in_use_for_order_by :
04946                               &table->keys_in_use_for_group_by))
04947     return(0);
04948   for (Order *ord= join->order; ord; ord= ord->next)
04949     length++;
04950   if (!(join->sortorder= make_unireg_sortorder(order, &length, join->sortorder)))
04951   {
04952     return(-1);
04953   }
04954 
04955   table->sort.io_cache= new internal::IO_CACHE;
04956   table->status=0;        // May be wrong if quick_select
04957 
04958   // If table has a range, move it to select
04959   if (select && !select->quick && tab->ref.key >= 0)
04960   {
04961     if (tab->quick)
04962     {
04963       select->quick=tab->quick;
04964       tab->quick=0;
04965       /*
04966         We can only use 'Only index' if quick key is same as ref_key
04967         and in index_merge 'Only index' cannot be used
04968       */
04969       if (table->key_read && ((uint32_t) tab->ref.key != select->quick->index))
04970       {
04971         table->key_read=0;
04972         table->cursor->extra(HA_EXTRA_NO_KEYREAD);
04973       }
04974     }
04975     else
04976     {
04977       /*
04978         We have a ref on a const;  Change this to a range that filesort
04979         can use.
04980         For impossible ranges (like when doing a lookup on NULL on a NOT NULL
04981         field, quick will contain an empty record set.
04982       */
04983       if (! (select->quick= (optimizer::get_quick_select_for_ref(session,
04984                                                                  table,
04985                                                                  &tab->ref,
04986                                                                  tab->found_records))))
04987       {
04988   return(-1);
04989       }
04990     }
04991   }
04992 
04993   if (table->getShare()->getType())
04994     table->cursor->info(HA_STATUS_VARIABLE);  // Get record count
04995 
04996   FileSort filesort(*session);
04997   table->sort.found_records=filesort.run(table,join->sortorder, length,
04998            select, filesort_limit, 0,
04999            examined_rows);
05000   tab->records= table->sort.found_records;  // For SQL_CALC_ROWS
05001   if (select)
05002   {
05003     select->cleanup();        // filesort did select
05004     tab->select= 0;
05005   }
05006   tab->select_cond=0;
05007   tab->last_inner= 0;
05008   tab->first_unmatched= 0;
05009   tab->type= AM_ALL;        // Read with normal read_record
05010   tab->read_first_record= join_init_read_record;
05011   tab->join->examined_rows+=examined_rows;
05012   if (table->key_read)        // Restore if we used indexes
05013   {
05014     table->key_read=0;
05015     table->cursor->extra(HA_EXTRA_NO_KEYREAD);
05016   }
05017 
05018   return(table->sort.found_records == HA_POS_ERROR);
05019 }
05020 
05021 int remove_dup_with_compare(Session *session, Table *table, Field **first_field, uint32_t offset, Item *having)
05022 {
05023   Cursor *cursor=table->cursor;
05024   char *org_record,*new_record;
05025   unsigned char *record;
05026   int error;
05027   uint32_t reclength= table->getShare()->getRecordLength() - offset;
05028 
05029   org_record=(char*) (record=table->getInsertRecord())+offset;
05030   new_record=(char*) table->getUpdateRecord()+offset;
05031 
05032   if ((error= cursor->startTableScan(1)))
05033     goto err;
05034 
05035   error=cursor->rnd_next(record);
05036   for (;;)
05037   {
05038     if (session->getKilled())
05039     {
05040       session->send_kill_message();
05041       error=0;
05042       goto err;
05043     }
05044     if (error)
05045     {
05046       if (error == HA_ERR_RECORD_DELETED)
05047         continue;
05048       if (error == HA_ERR_END_OF_FILE)
05049         break;
05050       goto err;
05051     }
05052     if (having && !having->val_int())
05053     {
05054       if ((error=cursor->deleteRecord(record)))
05055         goto err;
05056       error=cursor->rnd_next(record);
05057       continue;
05058     }
05059     if (copy_blobs(first_field))
05060     {
05061       my_message(ER_OUTOFMEMORY, ER(ER_OUTOFMEMORY), MYF(0));
05062       error=0;
05063       goto err;
05064     }
05065     memcpy(new_record,org_record,reclength);
05066 
05067     /* Read through rest of cursor and mark duplicated rows deleted */
05068     bool found=0;
05069     for (;;)
05070     {
05071       if ((error=cursor->rnd_next(record)))
05072       {
05073         if (error == HA_ERR_RECORD_DELETED)
05074           continue;
05075         if (error == HA_ERR_END_OF_FILE)
05076           break;
05077         goto err;
05078       }
05079       if (table->compare_record(first_field) == 0)
05080       {
05081         if ((error=cursor->deleteRecord(record)))
05082           goto err;
05083       }
05084       else if (!found)
05085       {
05086         found= 1;
05087         cursor->position(record); // Remember position
05088       }
05089     }
05090     if (!found)
05091       break;          // End of cursor
05092     /* Move current position to the next row */
05093     error= cursor->rnd_pos(record, cursor->ref);
05094   }
05095 
05096   cursor->extra(HA_EXTRA_NO_CACHE);
05097   return(0);
05098 err:
05099   cursor->extra(HA_EXTRA_NO_CACHE);
05100   if (error)
05101     table->print_error(error,MYF(0));
05102   return(1);
05103 }
05104 
05111 int remove_dup_with_hash_index(Session *session,
05112                                Table *table,
05113                                uint32_t field_count,
05114                                Field **first_field,
05115                                uint32_t key_length,
05116                                Item *having)
05117 {
05118   unsigned char *key_pos, *record=table->getInsertRecord();
05119   int error;
05120   Cursor &cursor= *table->cursor;
05121   uint32_t extra_length= ALIGN_SIZE(key_length)-key_length;
05122   uint32_t *field_length;
05123   HASH hash;
05124   std::vector<unsigned char> key_buffer((key_length + extra_length) * (long) cursor.stats.records);
05125   std::vector<uint32_t> field_lengths(field_count);
05126 
05127   {
05128     Field **ptr;
05129     uint32_t total_length= 0;
05130 
05131     for (ptr= first_field, field_length= &field_lengths[0] ; *ptr ; ptr++)
05132     {
05133       uint32_t length= (*ptr)->sort_length();
05134       (*field_length++)= length;
05135       total_length+= length;
05136     }
05137     assert(total_length <= key_length);
05138     key_length= total_length;
05139     extra_length= ALIGN_SIZE(key_length)-key_length;
05140   }
05141 
05142   if (hash_init(&hash, &my_charset_bin, (uint32_t) cursor.stats.records, 0, key_length, (hash_get_key) 0, 0, 0))
05143     return 1;
05144 
05145   if ((error= cursor.startTableScan(1)))
05146     goto err;
05147 
05148   key_pos= &key_buffer[0];
05149   for (;;)
05150   {
05151     if (session->getKilled())
05152     {
05153       session->send_kill_message();
05154       error=0;
05155       goto err;
05156     }
05157     if ((error=cursor.rnd_next(record)))
05158     {
05159       if (error == HA_ERR_RECORD_DELETED)
05160         continue;
05161       if (error == HA_ERR_END_OF_FILE)
05162         break;
05163       goto err;
05164     }
05165     if (having && !having->val_int())
05166     {
05167       if ((error=cursor.deleteRecord(record)))
05168         goto err;
05169       continue;
05170     }
05171 
05172     /* copy fields to key buffer */
05173     unsigned char* org_key_pos= key_pos;
05174     field_length= &field_lengths[0];
05175     for (Field **ptr= first_field ; *ptr ; ptr++)
05176     {
05177       (*ptr)->sort_string(key_pos,*field_length);
05178       key_pos+= *field_length++;
05179     }
05180     /* Check if it exists before */
05181     if (hash_search(&hash, org_key_pos, key_length))
05182     {
05183       /* Duplicated found ; Remove the row */
05184       if ((error=cursor.deleteRecord(record)))
05185         goto err;
05186     }
05187     else
05188       (void) my_hash_insert(&hash, org_key_pos);
05189     key_pos+=extra_length;
05190   }
05191   hash_free(&hash);
05192   cursor.extra(HA_EXTRA_NO_CACHE);
05193   (void) cursor.endTableScan();
05194   return 0;
05195 
05196 err:
05197   hash_free(&hash);
05198   cursor.extra(HA_EXTRA_NO_CACHE);
05199   (void) cursor.endTableScan();
05200   if (error)
05201     table->print_error(error,MYF(0));
05202   return 1;
05203 }
05204 
05205 SortField *make_unireg_sortorder(Order *order, uint32_t *length, SortField *sortorder)
05206 {
05207   uint32_t count;
05208   SortField *sort,*pos;
05209 
05210   count=0;
05211   for (Order *tmp = order; tmp; tmp=tmp->next)
05212     count++;
05213   if (!sortorder)
05214     sortorder= (SortField*) memory::sql_alloc(sizeof(SortField) *
05215                                        (max(count, *length) + 1));
05216   pos= sort= sortorder;
05217 
05218   if (!pos)
05219     return 0;
05220 
05221   for (;order;order=order->next,pos++)
05222   {
05223     Item *item= order->item[0]->real_item();
05224     pos->field= 0; pos->item= 0;
05225     if (item->type() == Item::FIELD_ITEM)
05226       pos->field= ((Item_field*) item)->field;
05227     else if (item->type() == Item::SUM_FUNC_ITEM && !item->const_item())
05228       pos->field= ((Item_sum*) item)->get_tmp_table_field();
05229     else if (item->type() == Item::COPY_STR_ITEM)
05230     {           // Blob patch
05231       pos->item= ((Item_copy_string*) item)->item;
05232     }
05233     else
05234       pos->item= *order->item;
05235     pos->reverse=! order->asc;
05236   }
05237   *length=count;
05238   return(sort);
05239 }
05240 
05241 /*
05242   eq_ref: Create the lookup key and check if it is the same as saved key
05243 
05244   SYNOPSIS
05245     cmp_buffer_with_ref()
05246       tab  Join tab of the accessed table
05247 
05248   DESCRIPTION
05249     Used by eq_ref access method: create the index lookup key and check if
05250     we've used this key at previous lookup (If yes, we don't need to repeat
05251     the lookup - the record has been already fetched)
05252 
05253   RETURN
05254     true   No cached record for the key, or failed to create the key (due to
05255            out-of-domain error)
05256     false  The created key is the same as the previous one (and the record
05257            is already in table->record)
05258 */
05259 static bool cmp_buffer_with_ref(JoinTable *tab)
05260 {
05261   bool no_prev_key;
05262   if (!tab->ref.disable_cache)
05263   {
05264     if (!(no_prev_key= tab->ref.key_err))
05265     {
05266       /* Previous access found a row. Copy its key */
05267       memcpy(tab->ref.key_buff2, tab->ref.key_buff, tab->ref.key_length);
05268     }
05269   }
05270   else
05271     no_prev_key= true;
05272   if ((tab->ref.key_err= cp_buffer_from_ref(tab->join->session, &tab->ref)) ||
05273       no_prev_key)
05274     return 1;
05275   return memcmp(tab->ref.key_buff2, tab->ref.key_buff, tab->ref.key_length)
05276     != 0;
05277 }
05278 
05279 bool cp_buffer_from_ref(Session *session, table_reference_st *ref)
05280 {
05281   enum enum_check_fields save_count_cuted_fields= session->count_cuted_fields;
05282   session->count_cuted_fields= CHECK_FIELD_IGNORE;
05283   bool result= 0;
05284 
05285   for (StoredKey **copy=ref->key_copy ; *copy ; copy++)
05286   {
05287     if ((*copy)->copy() & 1)
05288     {
05289       result= 1;
05290       break;
05291     }
05292   }
05293   session->count_cuted_fields= save_count_cuted_fields;
05294   return result;
05295 }
05296 
05297 /*****************************************************************************
05298   Group and order functions
05299 *****************************************************************************/
05300 
05333 static bool find_order_in_list(Session *session,
05334                                Item **ref_pointer_array,
05335                                TableList *tables,
05336                                Order *order,
05337                                List<Item> &fields,
05338                                List<Item> &all_fields,
05339                                bool is_group_field)
05340 {
05341   Item *order_item= *order->item; /* The item from the GROUP/order_st caluse. */
05342   Item::Type order_item_type;
05343   Item **select_item; /* The corresponding item from the SELECT clause. */
05344   Field *from_field;  /* The corresponding field from the FROM clause. */
05345   uint32_t counter;
05346   enum_resolution_type resolution;
05347 
05348   /*
05349     Local SP variables may be int but are expressions, not positions.
05350     (And they can't be used before fix_fields is called for them).
05351   */
05352   if (order_item->type() == Item::INT_ITEM && order_item->basic_const_item())
05353   {           /* Order by position */
05354     uint32_t count= (uint32_t) order_item->val_int();
05355     if (!count || count > fields.size())
05356     {
05357       my_error(ER_BAD_FIELD_ERROR, MYF(0),
05358                order_item->full_name(), session->where());
05359       return true;
05360     }
05361     order->item= ref_pointer_array + count - 1;
05362     order->in_field_list= 1;
05363     order->counter= count;
05364     order->counter_used= 1;
05365     return false;
05366   }
05367   /* Lookup the current GROUP/order_st field in the SELECT clause. */
05368   select_item= find_item_in_list(session, order_item, fields, &counter,
05369                                  REPORT_EXCEPT_NOT_FOUND, &resolution);
05370   if (!select_item)
05371     return true; /* The item is not unique, or some other error occured. */
05372 
05373 
05374   /* Check whether the resolved field is not ambiguos. */
05375   if (select_item != not_found_item)
05376   {
05377     Item *view_ref= NULL;
05378     /*
05379       If we have found field not by its alias in select list but by its
05380       original field name, we should additionaly check if we have conflict
05381       for this name (in case if we would perform lookup in all tables).
05382     */
05383     if (resolution == RESOLVED_BEHIND_ALIAS && !order_item->fixed &&
05384         order_item->fix_fields(session, order->item))
05385       return true;
05386 
05387     /* Lookup the current GROUP field in the FROM clause. */
05388     order_item_type= order_item->type();
05389     from_field= (Field*) not_found_field;
05390     if ((is_group_field && order_item_type == Item::FIELD_ITEM) ||
05391         order_item_type == Item::REF_ITEM)
05392     {
05393       from_field= find_field_in_tables(session, (Item_ident*) order_item, tables,
05394                                        NULL, &view_ref, IGNORE_ERRORS, false);
05395       if (!from_field)
05396         from_field= (Field*) not_found_field;
05397     }
05398 
05399     if (from_field == not_found_field ||
05400         (from_field != view_ref_found ?
05401          /* it is field of base table => check that fields are same */
05402          ((*select_item)->type() == Item::FIELD_ITEM &&
05403           ((Item_field*) (*select_item))->field->eq(from_field)) :
05404          /*
05405            in is field of view table => check that references on translation
05406            table are same
05407          */
05408          ((*select_item)->type() == Item::REF_ITEM &&
05409           view_ref->type() == Item::REF_ITEM &&
05410           ((Item_ref *) (*select_item))->ref ==
05411           ((Item_ref *) view_ref)->ref)))
05412     {
05413       /*
05414         If there is no such field in the FROM clause, or it is the same field
05415         as the one found in the SELECT clause, then use the Item created for
05416         the SELECT field. As a result if there was a derived field that
05417         'shadowed' a table field with the same name, the table field will be
05418         chosen over the derived field.
05419       */
05420       order->item= ref_pointer_array + counter;
05421       order->in_field_list=1;
05422       return false;
05423     }
05424     else
05425     {
05426       /*
05427         There is a field with the same name in the FROM clause. This
05428         is the field that will be chosen. In this case we issue a
05429         warning so the user knows that the field from the FROM clause
05430         overshadows the column reference from the SELECT list.
05431       */
05432       push_warning_printf(session, DRIZZLE_ERROR::WARN_LEVEL_WARN, ER_NON_UNIQ_ERROR,
05433                           ER(ER_NON_UNIQ_ERROR),
05434                           ((Item_ident*) order_item)->field_name,
05435                           session->where());
05436     }
05437   }
05438 
05439   order->in_field_list=0;
05440   /*
05441     The call to order_item->fix_fields() means that here we resolve
05442     'order_item' to a column from a table in the list 'tables', or to
05443     a column in some outer query. Exactly because of the second case
05444     we come to this point even if (select_item == not_found_item),
05445     inspite of that fix_fields() calls find_item_in_list() one more
05446     time.
05447 
05448     We check order_item->fixed because Item_func_group_concat can put
05449     arguments for which fix_fields already was called.
05450   */
05451   if (!order_item->fixed &&
05452       (order_item->fix_fields(session, order->item) ||
05453        (order_item= *order->item)->check_cols(1) ||
05454        session->is_fatal_error))
05455     return true; /* Wrong field. */
05456 
05457   uint32_t el= all_fields.size();
05458   all_fields.push_front(order_item); /* Add new field to field list. */
05459   ref_pointer_array[el]= order_item;
05460   order->item= ref_pointer_array + el;
05461   return false;
05462 }
05463 
05470 int setup_order(Session *session,
05471                 Item **ref_pointer_array,
05472                 TableList *tables,
05473                 List<Item> &fields,
05474                 List<Item> &all_fields,
05475                 Order *order)
05476 {
05477   session->setWhere("order clause");
05478   for (; order; order=order->next)
05479   {
05480     if (find_order_in_list(session, ref_pointer_array, tables, order, fields,
05481          all_fields, false))
05482       return 1;
05483   }
05484   return 0;
05485 }
05486 
05512 int setup_group(Session *session,
05513                 Item **ref_pointer_array,
05514                 TableList *tables,
05515                 List<Item> &fields,
05516                 List<Item> &all_fields,
05517                 Order *order,
05518                 bool *hidden_group_fields)
05519 {
05520   *hidden_group_fields=0;
05521   Order *ord;
05522 
05523   if (!order)
05524     return 0;       /* Everything is ok */
05525 
05526   uint32_t org_fields=all_fields.size();
05527 
05528   session->setWhere("group statement");
05529   for (ord= order; ord; ord= ord->next)
05530   {
05531     if (find_order_in_list(session, ref_pointer_array, tables, ord, fields,
05532          all_fields, true))
05533       return 1;
05534     (*ord->item)->marker= UNDEF_POS;    /* Mark found */
05535     if ((*ord->item)->with_sum_func)
05536     {
05537       my_error(ER_WRONG_GROUP_FIELD, MYF(0), (*ord->item)->full_name());
05538       return 1;
05539     }
05540   }
05541   /* MODE_ONLY_FULL_GROUP_BY */
05542   {
05543     /*
05544       Don't allow one to use fields that is not used in GROUP BY
05545       For each select a list of field references that aren't under an
05546       aggregate function is created. Each field in this list keeps the
05547       position of the select list expression which it belongs to.
05548 
05549       First we check an expression from the select list against the GROUP BY
05550       list. If it's found there then it's ok. It's also ok if this expression
05551       is a constant or an aggregate function. Otherwise we scan the list
05552       of non-aggregated fields and if we'll find at least one field reference
05553       that belongs to this expression and doesn't occur in the GROUP BY list
05554       we throw an error. If there are no fields in the created list for a
05555       select list expression this means that all fields in it are used under
05556       aggregate functions.
05557     */
05558     Item *item;
05559     Item_field *field;
05560     int cur_pos_in_select_list= 0;
05561     List<Item>::iterator li(fields.begin());
05562     List<Item_field>::iterator naf_it(session->lex().current_select->non_agg_fields.begin());
05563 
05564     field= naf_it++;
05565     while (field && (item=li++))
05566     {
05567       if (item->type() != Item::SUM_FUNC_ITEM && item->marker >= 0 &&
05568           !item->const_item() &&
05569           !(item->real_item()->type() == Item::FIELD_ITEM &&
05570             item->used_tables() & OUTER_REF_TABLE_BIT))
05571       {
05572         while (field)
05573         {
05574           /* Skip fields from previous expressions. */
05575           if (field->marker < cur_pos_in_select_list)
05576             goto next_field;
05577           /* Found a field from the next expression. */
05578           if (field->marker > cur_pos_in_select_list)
05579             break;
05580           /*
05581             Check whether the field occur in the GROUP BY list.
05582             Throw the error later if the field isn't found.
05583           */
05584           for (ord= order; ord; ord= ord->next)
05585             if ((*ord->item)->eq((Item*)field, 0))
05586               goto next_field;
05587           /*
05588             @todo change ER_WRONG_FIELD_WITH_GROUP to more detailed ER_NON_GROUPING_FIELD_USED
05589           */
05590           my_error(ER_WRONG_FIELD_WITH_GROUP, MYF(0), field->full_name());
05591           return 1;
05592 next_field:
05593           field= naf_it++;
05594         }
05595       }
05596       cur_pos_in_select_list++;
05597     }
05598   }
05599   if (org_fields != all_fields.size())
05600     *hidden_group_fields=1;     // group fields is not used
05601   return 0;
05602 }
05603 
05610 Order *create_distinct_group(Session *session,
05611                                 Item **ref_pointer_array,
05612                                 Order *order_list,
05613                                 List<Item> &fields,
05614                                 List<Item> &,
05615                                 bool *all_order_by_fields_used)
05616 {
05617   List<Item>::iterator li(fields.begin());
05618   Item *item;
05619   Order *order,*group,**prev;
05620 
05621   *all_order_by_fields_used= 1;
05622   while ((item=li++))
05623     item->marker=0;     /* Marker that field is not used */
05624 
05625   prev= &group;  group=0;
05626   for (order=order_list ; order; order=order->next)
05627   {
05628     if (order->in_field_list)
05629     {
05630       Order *ord=(Order*) session->getMemRoot()->duplicate((char*) order,sizeof(Order));
05631       if (!ord)
05632         return 0;
05633       *prev=ord;
05634       prev= &ord->next;
05635       (*ord->item)->marker=1;
05636     }
05637     else
05638       *all_order_by_fields_used= 0;
05639   }
05640 
05641   li= fields.begin();
05642   while ((item=li++))
05643   {
05644     if (!item->const_item() && !item->with_sum_func && !item->marker)
05645     {
05646       /*
05647         Don't put duplicate columns from the SELECT list into the
05648         GROUP BY list.
05649       */
05650       Order *ord_iter;
05651       for (ord_iter= group; ord_iter; ord_iter= ord_iter->next)
05652         if ((*ord_iter->item)->eq(item, 1))
05653           goto next_item;
05654 
05655       Order *ord=(Order*) session->calloc(sizeof(Order));
05656       if (!ord)
05657         return 0;
05658 
05659       /*
05660         We have here only field_list (not all_field_list), so we can use
05661         simple indexing of ref_pointer_array (order in the array and in the
05662         list are same)
05663       */
05664       ord->item= ref_pointer_array;
05665       ord->asc=1;
05666       *prev=ord;
05667       prev= &ord->next;
05668     }
05669 next_item:
05670     ref_pointer_array++;
05671   }
05672   *prev=0;
05673   return group;
05674 }
05675 
05679 void count_field_types(Select_Lex *select_lex, Tmp_Table_Param *param, List<Item> &fields, bool reset_with_sum_func)
05680 {
05681   List<Item>::iterator li(fields.begin());
05682   Item *field;
05683 
05684   param->field_count=param->sum_func_count=param->func_count=
05685     param->hidden_field_count=0;
05686   param->quick_group=1;
05687   while ((field=li++))
05688   {
05689     Item::Type real_type= field->real_item()->type();
05690     if (real_type == Item::FIELD_ITEM)
05691       param->field_count++;
05692     else if (real_type == Item::SUM_FUNC_ITEM)
05693     {
05694       if (! field->const_item())
05695       {
05696         Item_sum *sum_item=(Item_sum*) field->real_item();
05697         if (!sum_item->depended_from() ||
05698             sum_item->depended_from() == select_lex)
05699         {
05700           if (!sum_item->quick_group)
05701             param->quick_group=0;     // UDF SUM function
05702           param->sum_func_count++;
05703 
05704           for (uint32_t i=0 ; i < sum_item->arg_count ; i++)
05705           {
05706             if (sum_item->args[0]->real_item()->type() == Item::FIELD_ITEM)
05707               param->field_count++;
05708             else
05709               param->func_count++;
05710           }
05711         }
05712         param->func_count++;
05713       }
05714     }
05715     else
05716     {
05717       param->func_count++;
05718       if (reset_with_sum_func)
05719         field->with_sum_func=0;
05720     }
05721   }
05722 }
05723 
05724 /*
05725   Test if a single-row cache of items changed, and update the cache.
05726 
05727   @details Test if a list of items that typically represents a result
05728   row has changed. If the value of some item changed, update the cached
05729   value for this item.
05730 
05731   @param list list of <item, cached_value> pairs stored as Cached_item.
05732 
05733   @return -1 if no item changed
05734   @return index of the first item that changed
05735 */
05736 int test_if_item_cache_changed(List<Cached_item> &list)
05737 {
05738   List<Cached_item>::iterator li(list.begin());
05739   int idx= -1,i;
05740   Cached_item *buff;
05741 
05742   for (i=(int) list.size()-1 ; (buff=li++) ; i--)
05743   {
05744     if (buff->cmp())
05745       idx=i;
05746   }
05747   return(idx);
05748 }
05749 
05778 bool setup_copy_fields(Session *session,
05779                        Tmp_Table_Param *param,
05780                        Item **ref_pointer_array,
05781                        List<Item> &res_selected_fields,
05782                        List<Item> &res_all_fields,
05783                        uint32_t elements,
05784                        List<Item> &all_fields)
05785 {
05786   Item *pos;
05787   List<Item>::iterator li(all_fields.begin());
05788   CopyField *copy= NULL;
05789   res_selected_fields.clear();
05790   res_all_fields.clear();
05791   List<Item>::iterator itr(res_all_fields.begin());
05792   List<Item> extra_funcs;
05793   uint32_t i, border= all_fields.size() - elements;
05794 
05795   if (param->field_count &&
05796       !(copy=param->copy_field= new CopyField[param->field_count]))
05797     goto err2;
05798 
05799   param->copy_funcs.clear();
05800   for (i= 0; (pos= li++); i++)
05801   {
05802     Field *field;
05803     unsigned char *tmp;
05804     Item *real_pos= pos->real_item();
05805     if (real_pos->type() == Item::FIELD_ITEM)
05806     {
05807       Item_field *item;
05808       if (!(item= new Item_field(session, ((Item_field*) real_pos))))
05809         goto err;
05810       if (pos->type() == Item::REF_ITEM)
05811       {
05812         /* preserve the names of the ref when dereferncing */
05813         Item_ref *ref= (Item_ref *) pos;
05814         item->db_name= ref->db_name;
05815         item->table_name= ref->table_name;
05816         item->name= ref->name;
05817       }
05818       pos= item;
05819       if (item->field->flags & BLOB_FLAG)
05820       {
05821         if (!(pos= new Item_copy_string(pos)))
05822           goto err;
05823             /*
05824               Item_copy_string::copy for function can call
05825               Item_copy_string::val_int for blob via Item_ref.
05826               But if Item_copy_string::copy for blob isn't called before,
05827               it's value will be wrong
05828               so let's insert Item_copy_string for blobs in the beginning of
05829               copy_funcs
05830               (to see full test case look at having.test, BUG #4358)
05831             */
05832         if (param->copy_funcs.push_front(pos))
05833           goto err;
05834       }
05835       else
05836       {
05837         /*
05838           set up save buffer and change result_field to point at
05839           saved value
05840         */
05841         field= item->field;
05842         item->result_field=field->new_field(session->mem_root,field->getTable(), 1);
05843               /*
05844                 We need to allocate one extra byte for null handling and
05845                 another extra byte to not get warnings from purify in
05846                 Field_varstring::val_int
05847               */
05848         if (!(tmp= (unsigned char*) memory::sql_alloc(field->pack_length()+2)))
05849           goto err;
05850         if (copy)
05851         {
05852           copy->set(tmp, item->result_field);
05853           item->result_field->move_field(copy->to_ptr,copy->to_null_ptr,1);
05854 #ifdef HAVE_VALGRIND
05855           copy->to_ptr[copy->from_length]= 0;
05856 #endif
05857           copy++;
05858         }
05859       }
05860     }
05861     else if ((real_pos->type() == Item::FUNC_ITEM ||
05862         real_pos->type() == Item::SUBSELECT_ITEM ||
05863         real_pos->type() == Item::CACHE_ITEM ||
05864         real_pos->type() == Item::COND_ITEM) &&
05865        !real_pos->with_sum_func)
05866     {           // Save for send fields
05867       pos= real_pos;
05868       /*
05869         @todo In most cases this result will be sent to the user.
05870         This should be changed to use copy_int or copy_real depending
05871         on how the value is to be used: In some cases this may be an
05872         argument in a group function, like: IF(ISNULL(col),0,COUNT(*))
05873       */
05874       if (!(pos=new Item_copy_string(pos)))
05875         goto err;
05876       if (i < border)                           // HAVING, order_st and GROUP BY
05877       {
05878         if (extra_funcs.push_back(pos))
05879           goto err;
05880       }
05881       else if (param->copy_funcs.push_back(pos))
05882         goto err;
05883     }
05884     res_all_fields.push_back(pos);
05885     ref_pointer_array[((i < border)? all_fields.size()-i-1 : i-border)]=
05886       pos;
05887   }
05888   param->copy_field_end= copy;
05889 
05890   for (i= 0; i < border; i++)
05891     itr++;
05892   itr.sublist(res_selected_fields, elements);
05893   /*
05894     Put elements from HAVING, ORDER BY and GROUP BY last to ensure that any
05895     reference used in these will resolve to a item that is already calculated
05896   */
05897   param->copy_funcs.concat(&extra_funcs);
05898 
05899   return(0);
05900 
05901 err:
05902   if (copy)
05903     delete [] param->copy_field;      // This is never 0
05904   param->copy_field=0;
05905 err2:
05906   return(true);
05907 }
05908 
05915 void copy_fields(Tmp_Table_Param *param)
05916 {
05917   CopyField *ptr= param->copy_field;
05918   CopyField *end= param->copy_field_end;
05919 
05920   for (; ptr != end; ptr++)
05921     (*ptr->do_copy)(ptr);
05922 
05923   List<Item>::iterator it(param->copy_funcs.begin());
05924   Item_copy_string *item;
05925   while ((item = (Item_copy_string*) it++))
05926     item->copy();
05927 }
05928 
05945 bool change_to_use_tmp_fields(Session *session,
05946                               Item **ref_pointer_array,
05947                               List<Item> &res_selected_fields,
05948                               List<Item> &res_all_fields,
05949                               uint32_t elements,
05950                               List<Item> &all_fields)
05951 {
05952   List<Item>::iterator it(all_fields.begin());
05953   Item *item_field,*item;
05954 
05955   res_selected_fields.clear();
05956   res_all_fields.clear();
05957 
05958   uint32_t i, border= all_fields.size() - elements;
05959   for (i= 0; (item= it++); i++)
05960   {
05961     Field *field;
05962 
05963     if ((item->with_sum_func && item->type() != Item::SUM_FUNC_ITEM) ||
05964         (item->type() == Item::FUNC_ITEM &&
05965          ((Item_func*)item)->functype() == Item_func::SUSERVAR_FUNC))
05966       item_field= item;
05967     else
05968     {
05969       if (item->type() == Item::FIELD_ITEM)
05970       {
05971         item_field= item->get_tmp_table_item(session);
05972       }
05973       else if ((field= item->get_tmp_table_field()))
05974       {
05975         if (item->type() == Item::SUM_FUNC_ITEM && field->getTable()->group)
05976           item_field= ((Item_sum*) item)->result_item(field);
05977         else
05978           item_field= (Item*) new Item_field(field);
05979         if (!item_field)
05980           return(true);                    // Fatal error
05981 
05982         if (item->real_item()->type() != Item::FIELD_ITEM)
05983           field->orig_table= 0;
05984         item_field->name= item->name;
05985         if (item->type() == Item::REF_ITEM)
05986         {
05987           Item_field *ifield= (Item_field *) item_field;
05988           Item_ref *iref= (Item_ref *) item;
05989           ifield->table_name= iref->table_name;
05990           ifield->db_name= iref->db_name;
05991         }
05992       }
05993       else
05994         item_field= item;
05995     }
05996     res_all_fields.push_back(item_field);
05997     ref_pointer_array[((i < border)? all_fields.size()-i-1 : i-border)]=
05998       item_field;
05999   }
06000 
06001   List<Item>::iterator itr(res_all_fields.begin());
06002   for (i= 0; i < border; i++)
06003     itr++;
06004   itr.sublist(res_selected_fields, elements);
06005   return(false);
06006 }
06007 
06024 bool change_refs_to_tmp_fields(Session *session,
06025                                Item **ref_pointer_array,
06026                                List<Item> &res_selected_fields,
06027                                List<Item> &res_all_fields,
06028                                uint32_t elements,
06029                                List<Item> &all_fields)
06030 {
06031   List<Item>::iterator it(all_fields.begin());
06032   Item *item, *new_item;
06033   res_selected_fields.clear();
06034   res_all_fields.clear();
06035 
06036   uint32_t i, border= all_fields.size() - elements;
06037   for (i= 0; (item= it++); i++)
06038   {
06039     res_all_fields.push_back(new_item= item->get_tmp_table_item(session));
06040     ref_pointer_array[((i < border)? all_fields.size()-i-1 : i-border)]=
06041       new_item;
06042   }
06043 
06044   List<Item>::iterator itr(res_all_fields.begin());
06045   for (i= 0; i < border; i++)
06046     itr++;
06047   itr.sublist(res_selected_fields, elements);
06048 
06049   return session->is_fatal_error;
06050 }
06051 
06052 /******************************************************************************
06053   Code for calculating functions
06054 ******************************************************************************/
06055 
06067 bool setup_sum_funcs(Session *session, Item_sum **func_ptr)
06068 {
06069   Item_sum *func;
06070   while ((func= *(func_ptr++)))
06071   {
06072     if (func->setup(session))
06073       return(true);
06074   }
06075   return(false);
06076 }
06077 
06078 void init_tmptable_sum_functions(Item_sum **func_ptr)
06079 {
06080   Item_sum *func;
06081   while ((func= *(func_ptr++)))
06082     func->reset_field();
06083 }
06084 
06086 void update_tmptable_sum_func(Item_sum **func_ptr, Table *)
06087 {
06088   Item_sum *func;
06089   while ((func= *(func_ptr++)))
06090     func->update_field();
06091 }
06092 
06094 void copy_sum_funcs(Item_sum **func_ptr, Item_sum **end_ptr)
06095 {
06096   for (; func_ptr != end_ptr ; func_ptr++)
06097     (void) (*func_ptr)->save_in_result_field(1);
06098   return;
06099 }
06100 
06101 bool init_sum_functions(Item_sum **func_ptr, Item_sum **end_ptr)
06102 {
06103   for (; func_ptr != end_ptr ;func_ptr++)
06104   {
06105     if ((*func_ptr)->reset())
06106       return 1;
06107   }
06108   /* If rollup, calculate the upper sum levels */
06109   for ( ; *func_ptr ; func_ptr++)
06110   {
06111     if ((*func_ptr)->add())
06112       return 1;
06113   }
06114   return 0;
06115 }
06116 
06117 bool update_sum_func(Item_sum **func_ptr)
06118 {
06119   Item_sum *func;
06120   for (; (func= (Item_sum*) *func_ptr) ; func_ptr++)
06121     if (func->add())
06122       return 1;
06123   return 0;
06124 }
06125 
06127 bool copy_funcs(Item **func_ptr, const Session *session)
06128 {
06129   Item *func;
06130   for (; (func = *func_ptr) ; func_ptr++)
06131   {
06132     func->save_in_result_field(1);
06133     /*
06134       Need to check the THD error state because Item::val_xxx() don't
06135       return error code, but can generate errors
06136       @todo change it for a real status check when Item::val_xxx()
06137       are extended to return status code.
06138     */
06139     if (session->is_error())
06140       return true;
06141   }
06142   return false;
06143 }
06144 
06151 void free_underlaid_joins(Session *, Select_Lex *select)
06152 {
06153   for (Select_Lex_Unit *unit= select->first_inner_unit();
06154        unit;
06155        unit= unit->next_unit())
06156     unit->cleanup();
06157 }
06158 
06159 /****************************************************************************
06160   ROLLUP handling
06161 ****************************************************************************/
06162 
06202 bool change_group_ref(Session *session, Item_func *expr, Order *group_list, bool *changed)
06203 {
06204   if (expr->arg_count)
06205   {
06206     Name_resolution_context *context= &session->lex().current_select->context;
06207     Item **arg,**arg_end;
06208     bool arg_changed= false;
06209     for (arg= expr->arguments(),
06210          arg_end= expr->arguments()+expr->arg_count;
06211          arg != arg_end; arg++)
06212     {
06213       Item *item= *arg;
06214       if (item->type() == Item::FIELD_ITEM || item->type() == Item::REF_ITEM)
06215       {
06216         Order *group_tmp;
06217         for (group_tmp= group_list; group_tmp; group_tmp= group_tmp->next)
06218         {
06219           if (item->eq(*group_tmp->item,0))
06220           {
06221             Item *new_item;
06222             if (!(new_item= new Item_ref(context, group_tmp->item, 0,
06223                                         item->name)))
06224               return 1;                                 // fatal_error is set
06225             *arg= new_item;
06226             arg_changed= true;
06227           }
06228         }
06229       }
06230       else if (item->type() == Item::FUNC_ITEM)
06231       {
06232         if (change_group_ref(session, (Item_func *) item, group_list, &arg_changed))
06233           return 1;
06234       }
06235     }
06236     if (arg_changed)
06237     {
06238       expr->maybe_null= 1;
06239       *changed= true;
06240     }
06241   }
06242   return 0;
06243 }
06244 
06245 
06246 static void print_table_array(Session *session, String *str, TableList **table,
06247                               TableList **end)
06248 {
06249   (*table)->print(session, str);
06250 
06251   for (TableList **tbl= table + 1; tbl < end; tbl++)
06252   {
06253     TableList *curr= *tbl;
06254     if (curr->outer_join)
06255     {
06256       /* MySQL converts right to left joins */
06257       str->append(STRING_WITH_LEN(" left join "));
06258     }
06259     else if (curr->straight)
06260       str->append(STRING_WITH_LEN(" straight_join "));
06261     else
06262       str->append(STRING_WITH_LEN(" join "));
06263     curr->print(session, str);
06264     if (curr->on_expr)
06265     {
06266       str->append(STRING_WITH_LEN(" on("));
06267       curr->on_expr->print(str);
06268       str->append(')');
06269     }
06270   }
06271 }
06272 
06279 void print_join(Session *session, String *str,
06280                 List<TableList> *tables)
06281 {
06282   /* List is reversed => we should reverse it before using */
06283   List<TableList>::iterator ti(tables->begin());
06284   TableList **table= (TableList **)session->getMemRoot()->allocate(sizeof(TableList*) *
06285                                                 tables->size());
06286   if (table == 0)
06287     return;  // out of memory
06288 
06289   for (TableList **t= table + (tables->size() - 1); t >= table; t--)
06290     *t= ti++;
06291   assert(tables->size() >= 1);
06292   print_table_array(session, str, table, table + tables->size());
06293 }
06294 
06295 void Select_Lex::print(Session *session, String *str)
06296 {
06297   /* QQ: session may not be set for sub queries, but this should be fixed */
06298   if(not session)
06299     session= current_session;
06300 
06301 
06302   str->append(STRING_WITH_LEN("select "));
06303 
06304   /* First add options */
06305   if (options & SELECT_STRAIGHT_JOIN)
06306     str->append(STRING_WITH_LEN("straight_join "));
06307   if (options & SELECT_DISTINCT)
06308     str->append(STRING_WITH_LEN("distinct "));
06309   if (options & SELECT_SMALL_RESULT)
06310     str->append(STRING_WITH_LEN("sql_small_result "));
06311   if (options & SELECT_BIG_RESULT)
06312     str->append(STRING_WITH_LEN("sql_big_result "));
06313   if (options & OPTION_BUFFER_RESULT)
06314     str->append(STRING_WITH_LEN("sql_buffer_result "));
06315   if (options & OPTION_FOUND_ROWS)
06316     str->append(STRING_WITH_LEN("sql_calc_found_rows "));
06317 
06318   //Item List
06319   bool first= 1;
06320   List<Item>::iterator it(item_list.begin());
06321   Item *item;
06322   while ((item= it++))
06323   {
06324     if (first)
06325       first= 0;
06326     else
06327       str->append(',');
06328     item->print_item_w_name(str);
06329   }
06330 
06331   /*
06332     from clause
06333     @todo support USING/FORCE/IGNORE index
06334   */
06335   if (table_list.size())
06336   {
06337     str->append(STRING_WITH_LEN(" from "));
06338     /* go through join tree */
06339     print_join(session, str, &top_join_list);
06340   }
06341   else if (where)
06342   {
06343     /*
06344       "SELECT 1 FROM DUAL WHERE 2" should not be printed as
06345       "SELECT 1 WHERE 2": the 1st syntax is valid, but the 2nd is not.
06346     */
06347     str->append(STRING_WITH_LEN(" from DUAL "));
06348   }
06349 
06350   // Where
06351   Item *cur_where= where;
06352   if (join)
06353     cur_where= join->conds;
06354   if (cur_where || cond_value != Item::COND_UNDEF)
06355   {
06356     str->append(STRING_WITH_LEN(" where "));
06357     if (cur_where)
06358       cur_where->print(str);
06359     else
06360       str->append(cond_value != Item::COND_FALSE ? "1" : "0");
06361   }
06362 
06363   // group by & olap
06364   if (group_list.size())
06365   {
06366     str->append(STRING_WITH_LEN(" group by "));
06367     print_order(str, (Order *) group_list.first);
06368     switch (olap)
06369     {
06370       case CUBE_TYPE:
06371   str->append(STRING_WITH_LEN(" with cube"));
06372   break;
06373       case ROLLUP_TYPE:
06374   str->append(STRING_WITH_LEN(" with rollup"));
06375   break;
06376       default:
06377   ;  //satisfy compiler
06378     }
06379   }
06380 
06381   // having
06382   Item *cur_having= having;
06383   if (join)
06384     cur_having= join->having;
06385 
06386   if (cur_having || having_value != Item::COND_UNDEF)
06387   {
06388     str->append(STRING_WITH_LEN(" having "));
06389     if (cur_having)
06390       cur_having->print(str);
06391     else
06392       str->append(having_value != Item::COND_FALSE ? "1" : "0");
06393   }
06394 
06395   if (order_list.size())
06396   {
06397     str->append(STRING_WITH_LEN(" order by "));
06398     print_order(str, (Order *) order_list.first);
06399   }
06400 
06401   // limit
06402   print_limit(session, str);
06403 
06404   // PROCEDURE unsupported here
06405 }
06406 
06411 } /* namespace drizzled */