Drizzled Public API Documentation

join.cc
Go to the documentation of this file.
00001 /* - mode: c; c-basic-offset: 2; indent-tabs-mode: nil; -*-
00002  *  vim:expandtab:shiftwidth=2:tabstop=2:smarttab:
00003  *
00004  *  Copyright (C) 2008-2009 Sun Microsystems, Inc.
00005  *
00006  *  This program is free software; you can redistribute it and/or modify
00007  *  it under the terms of the GNU General Public License as published by
00008  *  the Free Software Foundation; either version 2 of the License, or
00009  *  (at your option) any later version.
00010  *
00011  *  This program is distributed in the hope that it will be useful,
00012  *  but WITHOUT ANY WARRANTY; without even the implied warranty of
00013  *  MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
00014  *  GNU General Public License for more details.
00015  *
00016  *  You should have received a copy of the GNU General Public License
00017  *  along with this program; if not, write to the Free Software
00018  *  Foundation, Inc., 51 Franklin St, Fifth Floor, Boston, MA  02110-1301  USA
00019  */
00020 
00030 #include <config.h>
00031 
00032 #include <float.h>
00033 #include <math.h>
00034 
00035 #include <drizzled/item/cache.h>
00036 #include <drizzled/item/cmpfunc.h>
00037 #include <drizzled/item/copy_string.h>
00038 #include <drizzled/item/uint.h>
00039 #include <drizzled/cached_item.h>
00040 #include <drizzled/sql_base.h>
00041 #include <drizzled/sql_select.h> /* include join.h */
00042 #include <drizzled/lock.h>
00043 #include <drizzled/nested_join.h>
00044 #include <drizzled/join.h>
00045 #include <drizzled/join_cache.h>
00046 #include <drizzled/show.h>
00047 #include <drizzled/field/blob.h>
00048 #include <drizzled/optimizer/position.h>
00049 #include <drizzled/optimizer/sargable_param.h>
00050 #include <drizzled/optimizer/key_use.h>
00051 #include <drizzled/optimizer/range.h>
00052 #include <drizzled/optimizer/sum.h>
00053 #include <drizzled/optimizer/explain_plan.h>
00054 #include <drizzled/optimizer/access_method_factory.h>
00055 #include <drizzled/optimizer/access_method.h>
00056 #include <drizzled/records.h>
00057 #include <drizzled/probes.h>
00058 #include <drizzled/internal/my_bit.h>
00059 #include <drizzled/internal/my_sys.h>
00060 #include <drizzled/internal/iocache.h>
00061 #include <drizzled/plugin/storage_engine.h>
00062 #include <drizzled/session.h>
00063 #include <drizzled/select_result.h>
00064 #include <drizzled/debug.h>
00065 #include <drizzled/item/subselect.h>
00066 #include <drizzled/my_hash.h>
00067 #include <drizzled/sql_lex.h>
00068 #include <algorithm>
00069 
00070 using namespace std;
00071 
00072 namespace drizzled {
00073 
00074 extern plugin::StorageEngine *heap_engine;
00075 
00077 static bool make_group_fields(Join *main_join, Join *curr_join);
00078 static void calc_group_buffer(Join *join, Order *group);
00079 static bool alloc_group_fields(Join *join, Order *group);
00080 static uint32_t cache_record_length(Join *join, uint32_t index);
00081 static double prev_record_reads(Join *join, uint32_t idx, table_map found_ref);
00082 static bool get_best_combination(Join *join);
00083 static void set_position(Join *join,
00084                          uint32_t index,
00085                          JoinTable *table,
00086                          optimizer::KeyUse *key);
00087 static bool choose_plan(Join *join,table_map join_tables);
00088 static void best_access_path(Join *join, JoinTable *s,
00089                              Session *session,
00090                              table_map remaining_tables,
00091                              uint32_t idx,
00092                              double record_count,
00093                              double read_time);
00094 static void optimize_straight_join(Join *join, table_map join_tables);
00095 static bool greedy_search(Join *join, table_map remaining_tables, uint32_t depth, uint32_t prune_level);
00096 static bool best_extension_by_limited_search(Join *join,
00097                                              table_map remaining_tables,
00098                                              uint32_t idx,
00099                                              double record_count,
00100                                              double read_time,
00101                                              uint32_t depth,
00102                                              uint32_t prune_level);
00103 static uint32_t determine_search_depth(Join* join);
00104 static bool make_simple_join(Join *join,Table *tmp_table);
00105 static void make_outerjoin_info(Join *join);
00106 static bool make_join_select(Join *join, optimizer::SqlSelect *select,COND *item);
00107 static bool make_join_readinfo(Join *join);
00108 static void update_depend_map(Join *join);
00109 static void update_depend_map(Join *join, Order *order);
00110 static Order *remove_constants(Join *join,Order *first_order,COND *cond, bool change_list, bool *simple_order);
00111 static int return_zero_rows(Join *join,
00112                             select_result *res,
00113                             TableList *tables,
00114                             List<Item> &fields,
00115                             bool send_row,
00116                             uint64_t select_options,
00117                             const char *info,
00118                             Item *having);
00119 static COND *simplify_joins(Join *join, List<TableList> *join_list, COND *conds, bool top);
00120 static int remove_duplicates(Join *join,Table *entry,List<Item> &fields, Item *having);
00121 static int setup_without_group(Session *session, 
00122                                Item **ref_pointer_array,
00123                                TableList *tables,
00124                                TableList *,
00125                                List<Item> &fields,
00126                                List<Item> &all_fields,
00127                                COND **conds,
00128                                Order *order,
00129                                Order *group,
00130                                bool *hidden_group_fields);
00131 static bool make_join_statistics(Join *join, TableList *leaves, COND *conds, DYNAMIC_ARRAY *keyuse);
00132 static uint32_t build_bitmap_for_nested_joins(List<TableList> *join_list, uint32_t first_unused);
00133 static Table *get_sort_by_table(Order *a, Order *b,TableList *tables);
00134 static void reset_nj_counters(List<TableList> *join_list);
00135 static bool test_if_subpart(Order *a,Order *b);
00136 static void restore_prev_nj_state(JoinTable *last);
00137 static bool add_ref_to_table_cond(Session *session, JoinTable *join_tab);
00138 static void free_blobs(Field **ptr); /* Rename this method...conflicts with another in global namespace... */
00139 
00140 Join::Join(Session *session_arg, 
00141            List<Item> &fields_arg, 
00142            uint64_t select_options_arg,
00143            select_result *result_arg) :
00144   join_tab(NULL),
00145   best_ref(NULL),
00146   map2table(NULL),
00147   join_tab_save(NULL),
00148   table(NULL),
00149   all_tables(NULL),
00150   sort_by_table(NULL),
00151   tables(0),
00152   outer_tables(0),
00153   const_tables(0),
00154   send_group_parts(0),
00155   sort_and_group(false),
00156   first_record(false),
00157   full_join(false),
00158   group(false),
00159   no_field_update(false),
00160   do_send_rows(true),
00161   resume_nested_loop(false),
00162   no_const_tables(false),
00163   select_distinct(false),
00164   group_optimized_away(false),
00165   simple_order(false),
00166   simple_group(false),
00167   no_order(false),
00168   skip_sort_order(false),
00169   union_part(false),
00170   optimized(false),
00171   need_tmp(false),
00172   hidden_group_fields(false),
00173   const_table_map(0),
00174   found_const_table_map(0),
00175   outer_join(0),
00176   send_records(0),
00177   found_records(0),
00178   examined_rows(0),
00179   row_limit(0),
00180   select_limit(0),
00181   fetch_limit(HA_POS_ERROR),
00182   session(session_arg),
00183   fields_list(fields_arg), 
00184   join_list(NULL),
00185   unit(NULL),
00186   select_lex(NULL),
00187   select(NULL),
00188   exec_tmp_table1(NULL),
00189   exec_tmp_table2(NULL),
00190   sum_funcs(NULL),
00191   sum_funcs2(NULL),
00192   having(NULL),
00193   tmp_having(NULL),
00194   having_history(NULL),
00195   select_options(select_options_arg),
00196   result(result_arg),
00197   lock(session_arg->lock),
00198   tmp_join(NULL),
00199   all_fields(fields_arg),
00200   error(0),
00201   cond_equal(NULL),
00202   return_tab(NULL),
00203   ref_pointer_array(NULL),
00204   items0(NULL),
00205   items1(NULL),
00206   items2(NULL),
00207   items3(NULL),
00208   ref_pointer_array_size(0),
00209   zero_result_cause(NULL),
00210   sortorder(NULL),
00211   table_reexec(NULL),
00212   join_tab_reexec(NULL)
00213 {
00214   select_distinct= test(select_options & SELECT_DISTINCT);
00215   if (&fields_list != &fields_arg) /* only copy if not same*/
00216     fields_list= fields_arg;
00217   memset(&keyuse, 0, sizeof(keyuse));
00218   tmp_table_param.init();
00219   tmp_table_param.end_write_records= HA_POS_ERROR;
00220   rollup.setState(Rollup::STATE_NONE);
00221 }
00222 
00229 void Join::reset(Session *session_arg, 
00230                  List<Item> &fields_arg, 
00231                  uint64_t select_options_arg,
00232                  select_result *result_arg)
00233 {
00234   join_tab= NULL;
00235   best_ref= NULL;
00236   map2table= NULL;
00237   join_tab_save= NULL;
00238   table= NULL;
00239   all_tables= NULL;
00240   sort_by_table= NULL;
00241   tables= 0;
00242   outer_tables= 0;
00243   const_tables= 0;
00244   send_group_parts= 0;
00245   sort_and_group= false;
00246   first_record= false;
00247   full_join= false;
00248   group= false;
00249   no_field_update= false;
00250   do_send_rows= true;
00251   resume_nested_loop= false;
00252   no_const_tables= false;
00253   select_distinct= false;
00254   group_optimized_away= false;
00255   simple_order= false;
00256   simple_group= false;
00257   no_order= false;
00258   skip_sort_order= false;
00259   union_part= false;
00260   optimized= false;
00261   need_tmp= false;
00262   hidden_group_fields= false;
00263   const_table_map= 0;
00264   found_const_table_map= 0;
00265   outer_join= 0;
00266   send_records= 0;
00267   found_records= 0;
00268   examined_rows= 0;
00269   row_limit= 0;
00270   select_limit= 0;
00271   fetch_limit= HA_POS_ERROR;
00272   session= session_arg;
00273   fields_list= fields_arg; 
00274   join_list= NULL;
00275   unit= NULL;
00276   select_lex= NULL;
00277   select= NULL;
00278   exec_tmp_table1= NULL;
00279   exec_tmp_table2= NULL;
00280   sum_funcs= NULL;
00281   sum_funcs2= NULL;
00282   having= NULL;
00283   tmp_having= NULL;
00284   having_history= NULL;
00285   select_options= select_options_arg;
00286   result= result_arg;
00287   lock= session_arg->lock;
00288   tmp_join= NULL;
00289   all_fields= fields_arg;
00290   error= 0;
00291   cond_equal= NULL;
00292   return_tab= NULL;
00293   ref_pointer_array= NULL;
00294   items0= NULL;
00295   items1= NULL;
00296   items2= NULL;
00297   items3= NULL;
00298   ref_pointer_array_size= 0;
00299   zero_result_cause= NULL;
00300   sortorder= NULL;
00301   table_reexec= NULL;
00302   join_tab_reexec= NULL;
00303   select_distinct= test(select_options & SELECT_DISTINCT);
00304   if (&fields_list != &fields_arg) /* only copy if not same*/
00305     fields_list= fields_arg;
00306   memset(&keyuse, 0, sizeof(keyuse));
00307   tmp_table_param.init();
00308   tmp_table_param.end_write_records= HA_POS_ERROR;
00309   rollup.setState(Rollup::STATE_NONE);
00310 }
00311 
00312 bool Join::is_top_level_join() const
00313 {
00314   return (unit == &session->lex().unit && (unit->fake_select_lex == 0 ||
00315                                           select_lex == unit->fake_select_lex));
00316 }
00317 
00330 int Join::prepare(Item ***rref_pointer_array,
00331                   TableList *tables_init,
00332                   uint32_t wild_num,
00333                   COND *conds_init,
00334                   uint32_t og_num,
00335                   Order *order_init,
00336                   Order *group_init,
00337                   Item *having_init,
00338                   Select_Lex *select_lex_arg,
00339                   Select_Lex_Unit *unit_arg)
00340 {
00341   // to prevent double initialization on EXPLAIN
00342   if (optimized)
00343     return 0;
00344 
00345   conds= conds_init;
00346   order= order_init;
00347   group_list= group_init;
00348   having= having_init;
00349   tables_list= tables_init;
00350   select_lex= select_lex_arg;
00351   select_lex->join= this;
00352   join_list= &select_lex->top_join_list;
00353   union_part= unit_arg->is_union();
00354 
00355   session->lex().current_select->is_item_list_lookup= 1;
00356   /*
00357     If we have already executed SELECT, then it have not sense to prevent
00358     its table from update (see unique_table())
00359   */
00360   if (session->derived_tables_processing)
00361     select_lex->exclude_from_table_unique_test= true;
00362 
00363   /* Check that all tables, fields, conds and order are ok */
00364 
00365   if (!(select_options & OPTION_SETUP_TABLES_DONE) &&
00366       setup_tables_and_check_access(session, &select_lex->context, join_list,
00367                                     tables_list, &select_lex->leaf_tables,
00368                                     false))
00369   {
00370       return(-1);
00371   }
00372 
00373   TableList *table_ptr;
00374   for (table_ptr= select_lex->leaf_tables;
00375        table_ptr;
00376        table_ptr= table_ptr->next_leaf)
00377   {
00378     tables++;
00379   }
00380 
00381 
00382   if (setup_wild(session, fields_list, &all_fields, wild_num) ||
00383       select_lex->setup_ref_array(session, og_num) ||
00384       setup_fields(session, (*rref_pointer_array), fields_list, MARK_COLUMNS_READ,
00385        &all_fields, 1) ||
00386       setup_without_group(session, (*rref_pointer_array), tables_list,
00387         select_lex->leaf_tables, fields_list,
00388         all_fields, &conds, order, group_list,
00389         &hidden_group_fields))
00390     return(-1);
00391 
00392   ref_pointer_array= *rref_pointer_array;
00393 
00394   if (having)
00395   {
00396     nesting_map save_allow_sum_func= session->lex().allow_sum_func;
00397     session->setWhere("having clause");
00398     session->lex().allow_sum_func|= 1 << select_lex_arg->nest_level;
00399     select_lex->having_fix_field= 1;
00400     bool having_fix_rc= (!having->fixed &&
00401        (having->fix_fields(session, &having) ||
00402         having->check_cols(1)));
00403     select_lex->having_fix_field= 0;
00404     if (having_fix_rc || session->is_error())
00405       return(-1);
00406     session->lex().allow_sum_func= save_allow_sum_func;
00407   }
00408 
00409   {
00410     Item_subselect *subselect;
00411     Item_in_subselect *in_subs= NULL;
00412     /*
00413       Are we in a subquery predicate?
00414       TODO: the block below will be executed for every PS execution without need.
00415     */
00416     if ((subselect= select_lex->master_unit()->item))
00417     {
00418       if (subselect->substype() == Item_subselect::IN_SUBS)
00419         in_subs= (Item_in_subselect*)subselect;
00420 
00421       {
00422         bool do_materialize= true;
00423         /*
00424           Check if the subquery predicate can be executed via materialization.
00425           The required conditions are:
00426           1. Subquery predicate is an IN/=ANY subq predicate
00427           2. Subquery is a single SELECT (not a UNION)
00428           3. Subquery is not a table-less query. In this case there is no
00429              point in materializing.
00430           4. Subquery predicate is a top-level predicate
00431              (this implies it is not negated)
00432              TODO: this is a limitation that should be lifeted once we
00433              implement correct NULL semantics (WL#3830)
00434           5. Subquery is non-correlated
00435              TODO:
00436              This is an overly restrictive condition. It can be extended to:
00437              (Subquery is non-correlated ||
00438               Subquery is correlated to any query outer to IN predicate ||
00439               (Subquery is correlated to the immediate outer query &&
00440                Subquery !contains {GROUP BY, ORDER BY [LIMIT],
00441                aggregate functions) && subquery predicate is not under "NOT IN"))
00442           6. No execution method was already chosen (by a prepared statement).
00443 
00444           (*) The subquery must be part of a SELECT statement. The current
00445                condition also excludes multi-table update statements.
00446 
00447           We have to determine whether we will perform subquery materialization
00448           before calling the IN=>EXISTS transformation, so that we know whether to
00449           perform the whole transformation or only that part of it which wraps
00450           Item_in_subselect in an Item_in_optimizer.
00451         */
00452         if (do_materialize &&
00453             in_subs  &&                                                   // 1
00454             !select_lex->master_unit()->first_select()->next_select() &&  // 2
00455             select_lex->master_unit()->first_select()->leaf_tables &&     // 3
00456             session->lex().sql_command == SQLCOM_SELECT)                       // *
00457         {
00458           if (in_subs->is_top_level_item() &&                             // 4
00459               !in_subs->is_correlated &&                                  // 5
00460               in_subs->exec_method == Item_in_subselect::NOT_TRANSFORMED) // 6
00461             in_subs->exec_method= Item_in_subselect::MATERIALIZATION;
00462         }
00463 
00464         Item_subselect::trans_res trans_res;
00465         if ((trans_res= subselect->select_transformer(this)) !=
00466             Item_subselect::RES_OK)
00467         {
00468           return((trans_res == Item_subselect::RES_ERROR));
00469         }
00470       }
00471     }
00472   }
00473 
00474   if (order)
00475   {
00476     Order *ord;
00477     for (ord= order; ord; ord= ord->next)
00478     {
00479       Item *item= *ord->item;
00480       if (item->with_sum_func && item->type() != Item::SUM_FUNC_ITEM)
00481         item->split_sum_func(session, ref_pointer_array, all_fields);
00482     }
00483   }
00484 
00485   if (having && having->with_sum_func)
00486     having->split_sum_func(session, ref_pointer_array, all_fields,
00487                            &having, true);
00488   if (select_lex->inner_sum_func_list)
00489   {
00490     Item_sum *end=select_lex->inner_sum_func_list;
00491     Item_sum *item_sum= end;
00492     do
00493     {
00494       item_sum= item_sum->next;
00495       item_sum->split_sum_func(session, ref_pointer_array,
00496                                all_fields, item_sum->ref_by, false);
00497     } while (item_sum != end);
00498   }
00499 
00500   if (select_lex->inner_refs_list.size() &&
00501       fix_inner_refs(session, all_fields, select_lex, ref_pointer_array))
00502     return(-1);
00503 
00504   /*
00505     Check if there are references to un-aggregated columns when computing
00506     aggregate functions with implicit grouping (there is no GROUP BY).
00507 
00508     MODE_ONLY_FULL_GROUP_BY is enabled here by default
00509   */
00510   if (! group_list && 
00511       select_lex->full_group_by_flag.test(NON_AGG_FIELD_USED) &&
00512       select_lex->full_group_by_flag.test(SUM_FUNC_USED))
00513   {
00514     my_message(ER_MIX_OF_GROUP_FUNC_AND_FIELDS,
00515                ER(ER_MIX_OF_GROUP_FUNC_AND_FIELDS), MYF(0));
00516     return(-1);
00517   }
00518   {
00519     /* Caclulate the number of groups */
00520     send_group_parts= 0;
00521     for (Order *group_tmp= group_list ; group_tmp ; group_tmp= group_tmp->next)
00522       send_group_parts++;
00523   }
00524 
00525   if (error)
00526     return(-1);
00527 
00528   /* 
00529    * The below will create the new table for
00530    * CREATE TABLE ... SELECT
00531    *
00532    * @see create_table_from_items() in drizzled/sql_insert.cc
00533    */
00534   if (result && result->prepare(fields_list, unit_arg))
00535     return(-1);
00536 
00537   /* Init join struct */
00538   count_field_types(select_lex, &tmp_table_param, all_fields, 0);
00539   ref_pointer_array_size= all_fields.size() * sizeof(Item*);
00540   this->group= group_list != 0;
00541   unit= unit_arg;
00542 
00543 #ifdef RESTRICTED_GROUP
00544   if (sum_func_count && !group_list && (func_count || field_count))
00545   {
00546     my_message(ER_WRONG_SUM_SELECT,ER(ER_WRONG_SUM_SELECT),MYF(0));
00547     return(-1);
00548   }
00549 #endif
00550   if (select_lex->olap == ROLLUP_TYPE && rollup_init())
00551     return(-1);
00552 
00553   if (alloc_func_list())
00554     return(-1);
00555 
00556   return 0; // All OK
00557 }
00558 
00559 /*
00560   Remove the predicates pushed down into the subquery
00561 
00562   SYNOPSIS
00563     Join::remove_subq_pushed_predicates()
00564       where   IN  Must be NULL
00565               OUT The remaining WHERE condition, or NULL
00566 
00567   DESCRIPTION
00568     Given that this join will be executed using (unique|index)_subquery,
00569     without "checking NULL", remove the predicates that were pushed down
00570     into the subquery.
00571 
00572     If the subquery compares scalar values, we can remove the condition that
00573     was wrapped into trig_cond (it will be checked when needed by the subquery
00574     engine)
00575 
00576     If the subquery compares row values, we need to keep the wrapped
00577     equalities in the WHERE clause: when the left (outer) tuple has both NULL
00578     and non-NULL values, we'll do a full table scan and will rely on the
00579     equalities corresponding to non-NULL parts of left tuple to filter out
00580     non-matching records.
00581 
00582     TODO: We can remove the equalities that will be guaranteed to be true by the
00583     fact that subquery engine will be using index lookup. This must be done only
00584     for cases where there are no conversion errors of significance, e.g. 257
00585     that is searched in a byte. But this requires homogenization of the return
00586     codes of all Field*::store() methods.
00587 */
00588 void Join::remove_subq_pushed_predicates(Item **where)
00589 {
00590   if (conds->type() == Item::FUNC_ITEM &&
00591       ((Item_func *)this->conds)->functype() == Item_func::EQ_FUNC &&
00592       ((Item_func *)conds)->arguments()[0]->type() == Item::REF_ITEM &&
00593       ((Item_func *)conds)->arguments()[1]->type() == Item::FIELD_ITEM &&
00594       test_if_ref ((Item_field *)((Item_func *)conds)->arguments()[1],
00595                    ((Item_func *)conds)->arguments()[0]))
00596   {
00597     *where= 0;
00598     return;
00599   }
00600 }
00601 
00613 int Join::optimize()
00614 {
00615   // to prevent double initialization on EXPLAIN
00616   if (optimized)
00617     return 0;
00618   optimized= 1;
00619 
00620   session->set_proc_info("optimizing");
00621   row_limit= ((select_distinct || order || group_list) ? HA_POS_ERROR :
00622         unit->select_limit_cnt);
00623   /* select_limit is used to decide if we are likely to scan the whole table */
00624   select_limit= unit->select_limit_cnt;
00625   if (having || (select_options & OPTION_FOUND_ROWS))
00626     select_limit= HA_POS_ERROR;
00627   do_send_rows = (unit->select_limit_cnt) ? 1 : 0;
00628   // Ignore errors of execution if option IGNORE present
00629   if (session->lex().ignore)
00630     session->lex().current_select->no_error= 1;
00631 
00632 #ifdef HAVE_REF_TO_FIELDS     // Not done yet
00633   /* Add HAVING to WHERE if possible */
00634   if (having && !group_list && !sum_func_count)
00635   {
00636     if (!conds)
00637     {
00638       conds= having;
00639       having= 0;
00640     }
00641     else if ((conds=new Item_cond_and(conds,having)))
00642     {
00643       /*
00644         Item_cond_and can't be fixed after creation, so we do not check
00645         conds->fixed
00646       */
00647       conds->fix_fields(session, &conds);
00648       conds->change_ref_to_fields(session, tables_list);
00649       conds->top_level_item();
00650       having= 0;
00651     }
00652   }
00653 #endif
00654 
00655   /* Convert all outer joins to inner joins if possible */
00656   conds= simplify_joins(this, join_list, conds, true);
00657   build_bitmap_for_nested_joins(join_list, 0);
00658 
00659   conds= optimize_cond(this, conds, join_list, &cond_value);
00660   if (session->is_error())
00661   {
00662     error= 1;
00663     return 1;
00664   }
00665 
00666   {
00667     having= optimize_cond(this, having, join_list, &having_value);
00668     if (session->is_error())
00669     {
00670       error= 1;
00671       return 1;
00672     }
00673     if (select_lex->where)
00674       select_lex->cond_value= cond_value;
00675     if (select_lex->having)
00676       select_lex->having_value= having_value;
00677 
00678     if (cond_value == Item::COND_FALSE || having_value == Item::COND_FALSE ||
00679         (!unit->select_limit_cnt && !(select_options & OPTION_FOUND_ROWS)))
00680     {           /* Impossible cond */
00681       zero_result_cause=  having_value == Item::COND_FALSE ?
00682                            "Impossible HAVING" : "Impossible WHERE";
00683       tables = 0;
00684       goto setup_subq_exit;
00685     }
00686   }
00687 
00688   /* Optimize count(*), cmin() and cmax() */
00689   if (tables_list && tmp_table_param.sum_func_count && ! group_list)
00690   {
00691     int res;
00692     /*
00693       optimizer::sum_query() returns HA_ERR_KEY_NOT_FOUND if no rows match
00694       to the WHERE conditions,
00695       or 1 if all items were resolved,
00696       or 0, or an error number HA_ERR_...
00697     */
00698     if ((res= optimizer::sum_query(select_lex->leaf_tables, all_fields, conds)))
00699     {
00700       if (res == HA_ERR_KEY_NOT_FOUND)
00701       {
00702         zero_result_cause= "No matching min/max row";
00703         tables = 0;
00704         goto setup_subq_exit;
00705       }
00706       if (res > 1)
00707       {
00708         error= res;
00709         return 1;
00710       }
00711       if (res < 0)
00712       {
00713         zero_result_cause= "No matching min/max row";
00714         tables = 0;
00715         goto setup_subq_exit;
00716       }
00717       zero_result_cause= "Select tables optimized away";
00718       tables_list= 0;       // All tables resolved
00719       const_tables= tables;
00720       /*
00721         Extract all table-independent conditions and replace the WHERE
00722         clause with them. All other conditions were computed by optimizer::sum_query
00723         and the MIN/MAX/COUNT function(s) have been replaced by constants,
00724         so there is no need to compute the whole WHERE clause again.
00725         Notice that make_cond_for_table() will always succeed to remove all
00726         computed conditions, because optimizer::sum_query() is applicable only to
00727         conjunctions.
00728         Preserve conditions for EXPLAIN.
00729       */
00730       if (conds && !(session->lex().describe & DESCRIBE_EXTENDED))
00731       {
00732         COND *table_independent_conds= make_cond_for_table(conds, PSEUDO_TABLE_BITS, 0, 0);
00733         conds= table_independent_conds;
00734       }
00735       goto setup_subq_exit;
00736     }
00737   }
00738   if (!tables_list)
00739   {
00740     error= 0;
00741     return(0);
00742   }
00743   error= -1;          // Error is sent to client
00744   sort_by_table= get_sort_by_table(order, group_list, select_lex->leaf_tables);
00745 
00746   /* Calculate how to do the join */
00747   session->set_proc_info("statistics");
00748   if (make_join_statistics(this, select_lex->leaf_tables, conds, &keyuse) ||
00749       session->is_fatal_error)
00750   {
00751     return 1;
00752   }
00753 
00754   /* Remove distinct if only const tables */
00755   select_distinct= select_distinct && (const_tables != tables);
00756   session->set_proc_info("preparing");
00757   if (result->initialize_tables(this))
00758   {
00759     return 1;        // error == -1
00760   }
00761   if (const_table_map != found_const_table_map &&
00762       !(select_options & SELECT_DESCRIBE) &&
00763       (!conds ||
00764        !(conds->used_tables() & RAND_TABLE_BIT) ||
00765        select_lex->master_unit() == &session->lex().unit)) // upper level SELECT
00766   {
00767     zero_result_cause= "no matching row in const table";
00768     goto setup_subq_exit;
00769   }
00770   if (!(session->options & OPTION_BIG_SELECTS) &&
00771       best_read > (double) session->variables.max_join_size &&
00772       !(select_options & SELECT_DESCRIBE))
00773   {
00774     my_message(ER_TOO_BIG_SELECT, ER(ER_TOO_BIG_SELECT), MYF(0));
00775     error= -1;
00776     return 1;
00777   }
00778   if (const_tables && !(select_options & SELECT_NO_UNLOCK))
00779     session->unlockSomeTables(table, const_tables);
00780   if (!conds && outer_join)
00781   {
00782     /* Handle the case where we have an OUTER JOIN without a WHERE */
00783     conds=new Item_int((int64_t) 1,1);  // Always true
00784   }
00785   select= optimizer::make_select(*table, const_table_map,
00786                                  const_table_map, conds, 1, &error);
00787   if (error)
00788   {
00789     error= -1;
00790     return 1;
00791   }
00792 
00793   reset_nj_counters(join_list);
00794   make_outerjoin_info(this);
00795 
00796   /*
00797     Among the equal fields belonging to the same multiple equality
00798     choose the one that is to be retrieved first and substitute
00799     all references to these in where condition for a reference for
00800     the selected field.
00801   */
00802   if (conds)
00803   {
00804     conds= substitute_for_best_equal_field(conds, cond_equal, map2table);
00805     conds->update_used_tables();
00806   }
00807 
00808   /*
00809     Permorm the the optimization on fields evaluation mentioned above
00810     for all on expressions.
00811   */
00812   for (JoinTable *tab= join_tab + const_tables; tab < join_tab + tables ; tab++)
00813   {
00814     if (*tab->on_expr_ref)
00815     {
00816       *tab->on_expr_ref= substitute_for_best_equal_field(*tab->on_expr_ref,
00817                                                          tab->cond_equal,
00818                                                          map2table);
00819       (*tab->on_expr_ref)->update_used_tables();
00820     }
00821   }
00822 
00823   if (conds &&!outer_join && const_table_map != found_const_table_map &&
00824       (select_options & SELECT_DESCRIBE) &&
00825       select_lex->master_unit() == &session->lex().unit) // upper level SELECT
00826   {
00827     conds=new Item_int(0, 1);  // Always false
00828   }
00829 
00830   if (make_join_select(this, select, conds))
00831   {
00832     zero_result_cause=
00833       "Impossible WHERE noticed after reading const tables";
00834     goto setup_subq_exit;
00835   }
00836 
00837   error= -1;          /* if goto err */
00838 
00839   /* Optimize distinct away if possible */
00840   {
00841     Order *org_order= order;
00842     order= remove_constants(this, order,conds,1, &simple_order);
00843     if (session->is_error())
00844     {
00845       error= 1;
00846       return 1;
00847     }
00848 
00849     /*
00850       If we are using ORDER BY NULL or ORDER BY const_expression,
00851       return result in any order (even if we are using a GROUP BY)
00852     */
00853     if (!order && org_order)
00854       skip_sort_order= 1;
00855   }
00856   /*
00857      Check if we can optimize away GROUP BY/DISTINCT.
00858      We can do that if there are no aggregate functions, the
00859      fields in DISTINCT clause (if present) and/or columns in GROUP BY
00860      (if present) contain direct references to all key parts of
00861      an unique index (in whatever order) and if the key parts of the
00862      unique index cannot contain NULLs.
00863      Note that the unique keys for DISTINCT and GROUP BY should not
00864      be the same (as long as they are unique).
00865 
00866      The FROM clause must contain a single non-constant table.
00867   */
00868   if (tables - const_tables == 1 && (group_list || select_distinct) &&
00869       ! tmp_table_param.sum_func_count &&
00870       (! join_tab[const_tables].select ||
00871        ! join_tab[const_tables].select->quick ||
00872        join_tab[const_tables].select->quick->get_type() !=
00873        optimizer::QuickSelectInterface::QS_TYPE_GROUP_MIN_MAX))
00874   {
00875     if (group_list && list_contains_unique_index(join_tab[const_tables].table, find_field_in_order_list, (void *) group_list))
00876     {
00877       /*
00878         We have found that grouping can be removed since groups correspond to
00879         only one row anyway, but we still have to guarantee correct result
00880         order. The line below effectively rewrites the query from GROUP BY
00881         <fields> to ORDER BY <fields>. There are two exceptions:
00882         - if skip_sort_order is set (see above), then we can simply skip
00883           GROUP BY;
00884         - we can only rewrite ORDER BY if the ORDER BY fields are 'compatible'
00885           with the GROUP BY ones, i.e. either one is a prefix of another.
00886           We only check if the ORDER BY is a prefix of GROUP BY. In this case
00887           test_if_subpart() copies the ASC/DESC attributes from the original
00888           ORDER BY fields.
00889           If GROUP BY is a prefix of order_st BY, then it is safe to leave
00890           'order' as is.
00891        */
00892       if (! order || test_if_subpart(group_list, order))
00893           order= skip_sort_order ? 0 : group_list;
00894       /*
00895         If we have an IGNORE INDEX FOR GROUP BY(fields) clause, this must be
00896         rewritten to IGNORE INDEX FOR order_st BY(fields).
00897       */
00898       join_tab->table->keys_in_use_for_order_by=
00899         join_tab->table->keys_in_use_for_group_by;
00900       group_list= 0;
00901       group= 0;
00902     }
00903     if (select_distinct &&
00904        list_contains_unique_index(join_tab[const_tables].table,
00905                                  find_field_in_item_list,
00906                                  (void *) &fields_list))
00907     {
00908       select_distinct= 0;
00909     }
00910   }
00911   if (group_list || tmp_table_param.sum_func_count)
00912   {
00913     if (! hidden_group_fields && rollup.getState() == Rollup::STATE_NONE)
00914       select_distinct=0;
00915   }
00916   else if (select_distinct && tables - const_tables == 1)
00917   {
00918     /*
00919       We are only using one table. In this case we change DISTINCT to a
00920       GROUP BY query if:
00921       - The GROUP BY can be done through indexes (no sort) and the order_st
00922         BY only uses selected fields.
00923         (In this case we can later optimize away GROUP BY and order_st BY)
00924       - We are scanning the whole table without LIMIT
00925         This can happen if:
00926         - We are using CALC_FOUND_ROWS
00927         - We are using an ORDER BY that can't be optimized away.
00928 
00929       We don't want to use this optimization when we are using LIMIT
00930       because in this case we can just create a temporary table that
00931       holds LIMIT rows and stop when this table is full.
00932     */
00933     JoinTable *tab= &join_tab[const_tables];
00934     bool all_order_fields_used;
00935     if (order)
00936       skip_sort_order= test_if_skip_sort_order(tab, order, select_limit, 1,
00937         &tab->table->keys_in_use_for_order_by);
00938     if ((group_list=create_distinct_group(session, select_lex->ref_pointer_array,
00939                                           order, fields_list, all_fields,
00940                   &all_order_fields_used)))
00941     {
00942       bool skip_group= (skip_sort_order &&
00943         test_if_skip_sort_order(tab, group_list, select_limit, 1,
00944                                 &tab->table->keys_in_use_for_group_by) != 0);
00945       count_field_types(select_lex, &tmp_table_param, all_fields, 0);
00946       if ((skip_group && all_order_fields_used) ||
00947           select_limit == HA_POS_ERROR ||
00948           (order && !skip_sort_order))
00949       {
00950         /*  Change DISTINCT to GROUP BY */
00951         select_distinct= 0;
00952         no_order= !order;
00953         if (all_order_fields_used)
00954         {
00955           if (order && skip_sort_order)
00956           {
00957             /*
00958               Force MySQL to read the table in sorted order to get result in
00959               ORDER BY order.
00960             */
00961             tmp_table_param.quick_group=0;
00962           }
00963           order=0;
00964         }
00965         group=1;        // For end_write_group
00966       }
00967       else
00968         group_list= 0;
00969     }
00970     else if (session->is_fatal_error)     // End of memory
00971       return 1;
00972   }
00973   simple_group= 0;
00974   {
00975     Order *old_group_list;
00976     group_list= remove_constants(this, (old_group_list= group_list), conds,
00977                                  rollup.getState() == Rollup::STATE_NONE,
00978                                  &simple_group);
00979     if (session->is_error())
00980     {
00981       error= 1;
00982       return 1;
00983     }
00984     if (old_group_list && !group_list)
00985       select_distinct= 0;
00986   }
00987   if (!group_list && group)
00988   {
00989     order=0;          // The output has only one row
00990     simple_order=1;
00991     select_distinct= 0;                       // No need in distinct for 1 row
00992     group_optimized_away= 1;
00993   }
00994 
00995   calc_group_buffer(this, group_list);
00996   send_group_parts= tmp_table_param.group_parts; /* Save org parts */
00997 
00998   if (test_if_subpart(group_list, order) ||
00999       (!group_list && tmp_table_param.sum_func_count))
01000     order=0;
01001 
01002   // Can't use sort on head table if using row cache
01003   if (full_join)
01004   {
01005     if (group_list)
01006       simple_group=0;
01007     if (order)
01008       simple_order=0;
01009   }
01010 
01011   /*
01012     Check if we need to create a temporary table.
01013     This has to be done if all tables are not already read (const tables)
01014     and one of the following conditions holds:
01015     - We are using DISTINCT (simple distinct's are already optimized away)
01016     - We are using an ORDER BY or GROUP BY on fields not in the first table
01017     - We are using different ORDER BY and GROUP BY orders
01018     - The user wants us to buffer the result.
01019   */
01020   need_tmp= (const_tables != tables &&
01021        ((select_distinct || !simple_order || !simple_group) ||
01022         (group_list && order) ||
01023         test(select_options & OPTION_BUFFER_RESULT)));
01024 
01025   // No cache for MATCH == 'Don't use join buffering when we use MATCH'.
01026   if (make_join_readinfo(this))
01027     return 1;
01028 
01029   /* Create all structures needed for materialized subquery execution. */
01030   if (setup_subquery_materialization())
01031     return 1;
01032 
01033   /* Cache constant expressions in WHERE, HAVING, ON clauses. */
01034   cache_const_exprs();
01035 
01036   /*
01037     is this simple IN subquery?
01038   */
01039   if (!group_list && !order &&
01040       unit->item && unit->item->substype() == Item_subselect::IN_SUBS &&
01041       tables == 1 && conds &&
01042       !unit->is_union())
01043   {
01044     if (!having)
01045     {
01046       Item *where= conds;
01047       if (join_tab[0].type == AM_EQ_REF && join_tab[0].ref.items[0]->name == in_left_expr_name)
01048       {
01049         remove_subq_pushed_predicates(&where);
01050         save_index_subquery_explain_info(join_tab, where);
01051         join_tab[0].type= AM_UNIQUE_SUBQUERY;
01052         error= 0;
01053         return(unit->item->change_engine(new subselect_uniquesubquery_engine(session, join_tab, unit->item, where)));
01054       }
01055       else if (join_tab[0].type == AM_REF &&
01056          join_tab[0].ref.items[0]->name == in_left_expr_name)
01057       {
01058         remove_subq_pushed_predicates(&where);
01059         save_index_subquery_explain_info(join_tab, where);
01060         join_tab[0].type= AM_INDEX_SUBQUERY;
01061         error= 0;
01062         return(unit->item->change_engine(new subselect_indexsubquery_engine(session, join_tab, unit->item, where, NULL, 0)));
01063       }
01064     } 
01065     else if (join_tab[0].type == AM_REF_OR_NULL &&
01066          join_tab[0].ref.items[0]->name == in_left_expr_name &&
01067                having->name == in_having_cond)
01068     {
01069       join_tab[0].type= AM_INDEX_SUBQUERY;
01070       error= 0;
01071       conds= remove_additional_cond(conds);
01072       save_index_subquery_explain_info(join_tab, conds);
01073       return(unit->item->change_engine(new subselect_indexsubquery_engine(session, join_tab, unit->item, conds, having, 1)));
01074     }
01075 
01076   }
01077   /*
01078     Need to tell handlers that to play it safe, it should fetch all
01079     columns of the primary key of the tables: this is because MySQL may
01080     build row pointers for the rows, and for all columns of the primary key
01081     the read set has not necessarily been set by the server code.
01082   */
01083   if (need_tmp || select_distinct || group_list || order)
01084   {
01085     for (uint32_t i = const_tables; i < tables; i++)
01086       join_tab[i].table->prepare_for_position();
01087   }
01088 
01089   if (const_tables != tables)
01090   {
01091     /*
01092       Because filesort always does a full table scan or a quick range scan
01093       we must add the removed reference to the select for the table.
01094       We only need to do this when we have a simple_order or simple_group
01095       as in other cases the join is done before the sort.
01096     */
01097     if ((order || group_list) &&
01098         (join_tab[const_tables].type != AM_ALL) &&
01099         (join_tab[const_tables].type != AM_REF_OR_NULL) &&
01100         ((order && simple_order) || (group_list && simple_group)))
01101     {
01102       if (add_ref_to_table_cond(session,&join_tab[const_tables])) {
01103         return 1;
01104       }
01105     }
01106 
01107     if (!(select_options & SELECT_BIG_RESULT) &&
01108         ((group_list &&
01109           (!simple_group ||
01110            !test_if_skip_sort_order(&join_tab[const_tables], group_list,
01111                                     unit->select_limit_cnt, 0,
01112                                     &join_tab[const_tables].table->
01113                                     keys_in_use_for_group_by))) ||
01114          select_distinct) &&
01115         tmp_table_param.quick_group)
01116     {
01117       need_tmp=1; simple_order=simple_group=0;  // Force tmp table without sort
01118     }
01119     if (order)
01120     {
01121       /*
01122         Force using of tmp table if sorting by a SP or UDF function due to
01123         their expensive and probably non-deterministic nature.
01124       */
01125       for (Order *tmp_order= order; tmp_order ; tmp_order=tmp_order->next)
01126       {
01127         Item *item= *tmp_order->item;
01128         if (item->is_expensive())
01129         {
01130           /* Force tmp table without sort */
01131           need_tmp=1; simple_order=simple_group=0;
01132           break;
01133         }
01134       }
01135     }
01136   }
01137 
01138   tmp_having= having;
01139   if (select_options & SELECT_DESCRIBE)
01140   {
01141     error= 0;
01142     return(0);
01143   }
01144   having= 0;
01145 
01146   /*
01147     The loose index scan access method guarantees that all grouping or
01148     duplicate row elimination (for distinct) is already performed
01149     during data retrieval, and that all MIN/MAX functions are already
01150     computed for each group. Thus all MIN/MAX functions should be
01151     treated as regular functions, and there is no need to perform
01152     grouping in the main execution loop.
01153     Notice that currently loose index scan is applicable only for
01154     single table queries, thus it is sufficient to test only the first
01155     join_tab element of the plan for its access method.
01156   */
01157   if (join_tab->is_using_loose_index_scan())
01158     tmp_table_param.precomputed_group_by= true;
01159 
01160   /* Create a tmp table if distinct or if the sort is too complicated */
01161   if (need_tmp)
01162   {
01163     session->set_proc_info("Creating tmp table");
01164 
01165     init_items_ref_array();
01166 
01167     tmp_table_param.hidden_field_count= all_fields.size() - fields_list.size();
01168     Order *tmp_group= (((not simple_group) or not (getDebug().test(debug::NO_KEY_GROUP))) ? group_list : NULL);
01169 
01170     /*
01171       Pushing LIMIT to the temporary table creation is not applicable
01172       when there is ORDER BY or GROUP BY or there is no GROUP BY, but
01173       there are aggregate functions, because in all these cases we need
01174       all result rows.
01175     */
01176     ha_rows tmp_rows_limit= ((order == 0 || skip_sort_order) &&
01177                              !tmp_group &&
01178                              !session->lex().current_select->with_sum_func) ?
01179                             select_limit : HA_POS_ERROR;
01180 
01181     if (!(exec_tmp_table1=
01182           create_tmp_table(session, &tmp_table_param, all_fields,
01183                            tmp_group,
01184                            group_list ? 0 : select_distinct,
01185                            group_list && simple_group,
01186                            select_options,
01187                            tmp_rows_limit,
01188                            (char *) "")))
01189     {
01190       return 1;
01191     }
01192 
01193     /*
01194       We don't have to store rows in temp table that doesn't match HAVING if:
01195       - we are sorting the table and writing complete group rows to the
01196         temp table.
01197       - We are using DISTINCT without resolving the distinct as a GROUP BY
01198         on all columns.
01199 
01200       If having is not handled here, it will be checked before the row
01201       is sent to the client.
01202     */
01203     if (tmp_having && (sort_and_group || (exec_tmp_table1->distinct && !group_list)))
01204       having= tmp_having;
01205 
01206     /* if group or order on first table, sort first */
01207     if (group_list && simple_group)
01208     {
01209       session->set_proc_info("Sorting for group");
01210       if (create_sort_index(session, this, group_list,
01211           HA_POS_ERROR, HA_POS_ERROR, false) ||
01212           alloc_group_fields(this, group_list) ||
01213           make_sum_func_list(all_fields, fields_list, 1) ||
01214           setup_sum_funcs(session, sum_funcs))
01215       {
01216         return 1;
01217       }
01218       group_list=0;
01219     }
01220     else
01221     {
01222       if (make_sum_func_list(all_fields, fields_list, 0) ||
01223           setup_sum_funcs(session, sum_funcs))
01224       {
01225         return 1;
01226       }
01227 
01228       if (!group_list && ! exec_tmp_table1->distinct && order && simple_order)
01229       {
01230         session->set_proc_info("Sorting for order");
01231         if (create_sort_index(session, this, order,
01232                               HA_POS_ERROR, HA_POS_ERROR, true))
01233         {
01234           return 1;
01235         }
01236         order=0;
01237       }
01238     }
01239 
01240     /*
01241       Optimize distinct when used on some of the tables
01242       SELECT DISTINCT t1.a FROM t1,t2 WHERE t1.b=t2.b
01243       In this case we can stop scanning t2 when we have found one t1.a
01244     */
01245 
01246     if (exec_tmp_table1->distinct)
01247     {
01248       table_map used_tables= session->used_tables;
01249       JoinTable *last_join_tab= join_tab+tables-1;
01250       do
01251       {
01252         if (used_tables & last_join_tab->table->map)
01253           break;
01254         last_join_tab->not_used_in_distinct=1;
01255       } while (last_join_tab-- != join_tab);
01256       /* Optimize "select distinct b from t1 order by key_part_1 limit #" */
01257       if (order && skip_sort_order)
01258       {
01259         /* Should always succeed */
01260         if (test_if_skip_sort_order(&join_tab[const_tables],
01261                   order, unit->select_limit_cnt, 0,
01262                                           &join_tab[const_tables].table->
01263                                             keys_in_use_for_order_by))
01264           order= 0;
01265       }
01266     }
01267 
01268     /*
01269       If this join belongs to an uncacheable subquery save
01270       the original join
01271     */
01272     if (select_lex->uncacheable.any() && 
01273         ! is_top_level_join() &&
01274         init_save_join_tab())
01275     {
01276       return -1;
01277     }
01278   }
01279 
01280   error= 0;
01281   return 0;
01282 
01283 setup_subq_exit:
01284   /* Even with zero matching rows, subqueries in the HAVING clause
01285      may need to be evaluated if there are aggregate functions in the query.
01286   */
01287   if (setup_subquery_materialization())
01288     return 1;
01289   error= 0;
01290   return 0;
01291 }
01292 
01296 void Join::restore_tmp()
01297 {
01298   memcpy(tmp_join, this, (size_t) sizeof(Join));
01299 }
01300 
01301 int Join::reinit()
01302 {
01303   unit->offset_limit_cnt= (ha_rows)(select_lex->offset_limit ?
01304                                     select_lex->offset_limit->val_uint() :
01305                                     0UL);
01306 
01307   first_record= 0;
01308 
01309   if (exec_tmp_table1)
01310   {
01311     exec_tmp_table1->cursor->extra(HA_EXTRA_RESET_STATE);
01312     exec_tmp_table1->cursor->ha_delete_all_rows();
01313     exec_tmp_table1->free_io_cache();
01314     exec_tmp_table1->filesort_free_buffers();
01315   }
01316   if (exec_tmp_table2)
01317   {
01318     exec_tmp_table2->cursor->extra(HA_EXTRA_RESET_STATE);
01319     exec_tmp_table2->cursor->ha_delete_all_rows();
01320     exec_tmp_table2->free_io_cache();
01321     exec_tmp_table2->filesort_free_buffers();
01322   }
01323   if (items0)
01324     set_items_ref_array(items0);
01325 
01326   if (join_tab_save)
01327     memcpy(join_tab, join_tab_save, sizeof(JoinTable) * tables);
01328 
01329   if (tmp_join)
01330     restore_tmp();
01331 
01332   /* Reset of sum functions */
01333   if (sum_funcs)
01334   {
01335     Item_sum *func, **func_ptr= sum_funcs;
01336     while ((func= *(func_ptr++)))
01337       func->clear();
01338   }
01339 
01340   return(0);
01341 }
01342 
01353 bool Join::init_save_join_tab()
01354 {
01355   if (!(tmp_join= (Join*)session->getMemRoot()->allocate(sizeof(Join))))
01356     return 1;
01357 
01358   error= 0;              // Ensure that tmp_join.error= 0
01359   restore_tmp();
01360 
01361   return 0;
01362 }
01363 
01364 bool Join::save_join_tab()
01365 {
01366   if (! join_tab_save && select_lex->master_unit()->uncacheable.any())
01367   {
01368     if (!(join_tab_save= (JoinTable*)session->getMemRoot()->duplicate((unsigned char*) join_tab,
01369             sizeof(JoinTable) * tables)))
01370       return 1;
01371   }
01372   return 0;
01373 }
01374 
01386 void Join::exec()
01387 {
01388   List<Item> *columns_list= &fields_list;
01389   int      tmp_error;
01390 
01391   session->set_proc_info("executing");
01392   error= 0;
01393 
01394   if (!tables_list && (tables || !select_lex->with_sum_func))
01395   {                                           
01396     /* Only test of functions */
01397     if (select_options & SELECT_DESCRIBE)
01398     {
01399       optimizer::ExplainPlan planner(this, 
01400                                      false,
01401                                      false,
01402                                      false,
01403                                      (zero_result_cause ? zero_result_cause : "No tables used"));
01404       planner.printPlan();
01405     }
01406     else
01407     {
01408       result->send_fields(*columns_list);
01409       /*
01410         We have to test for 'conds' here as the WHERE may not be constant
01411         even if we don't have any tables for prepared statements or if
01412         conds uses something like 'rand()'.
01413       */
01414       if (cond_value != Item::COND_FALSE &&
01415           (!conds || conds->val_int()) &&
01416           (!having || having->val_int()))
01417       {
01418         if (do_send_rows && result->send_data(fields_list))
01419           error= 1;
01420         else
01421         {
01422           error= (int) result->send_eof();
01423           send_records= ((select_options & OPTION_FOUND_ROWS) ? 1 : session->sent_row_count);
01424         }
01425       }
01426       else
01427       {
01428         error= (int) result->send_eof();
01429         send_records= 0;
01430       }
01431     }
01432     /* Single select (without union) always returns 0 or 1 row */
01433     session->limit_found_rows= send_records;
01434     session->examined_row_count= 0;
01435     return;
01436   }
01437   /*
01438     Don't reset the found rows count if there're no tables as
01439     FOUND_ROWS() may be called. Never reset the examined row count here.
01440     It must be accumulated from all join iterations of all join parts.
01441   */
01442   if (tables)
01443     session->limit_found_rows= 0;
01444 
01445   if (zero_result_cause)
01446   {
01447     (void) return_zero_rows(this, result, select_lex->leaf_tables,
01448                             *columns_list,
01449           send_row_on_empty_set(),
01450           select_options,
01451           zero_result_cause,
01452           having);
01453     return;
01454   }
01455 
01456   if (select_options & SELECT_DESCRIBE)
01457   {
01458     /*
01459       Check if we managed to optimize ORDER BY away and don't use temporary
01460       table to resolve order_st BY: in that case, we only may need to do
01461       filesort for GROUP BY.
01462     */
01463     if (!order && !no_order && (!skip_sort_order || !need_tmp))
01464     {
01465       /* Reset 'order' to 'group_list' and reinit variables describing 'order' */
01466       order= group_list;
01467       simple_order= simple_group;
01468       skip_sort_order= 0;
01469     }
01470     if (order && (order != group_list || !(select_options & SELECT_BIG_RESULT)))
01471     {
01472       if (const_tables == tables 
01473         || ((simple_order || skip_sort_order) 
01474           && test_if_skip_sort_order(&join_tab[const_tables], order, select_limit, 0, &join_tab[const_tables].table->keys_in_use_for_query)))
01475       order= 0;
01476     }
01477     having= tmp_having;
01478     optimizer::ExplainPlan planner(this,
01479                                    need_tmp,
01480                                    order != 0 && ! skip_sort_order,
01481                                    select_distinct,
01482                                    ! tables ? "No tables used" : NULL);
01483     planner.printPlan();
01484     return;
01485   }
01486 
01487   Join *curr_join= this;
01488   List<Item> *curr_all_fields= &all_fields;
01489   List<Item> *curr_fields_list= &fields_list;
01490   Table *curr_tmp_table= 0;
01491   /*
01492     Initialize examined rows here because the values from all join parts
01493     must be accumulated in examined_row_count. Hence every join
01494     iteration must count from zero.
01495   */
01496   curr_join->examined_rows= 0;
01497 
01498   /* Create a tmp table if distinct or if the sort is too complicated */
01499   if (need_tmp)
01500   {
01501     if (tmp_join)
01502     {
01503       /*
01504         We are in a non cacheable sub query. Get the saved join structure
01505         after optimization.
01506         (curr_join may have been modified during last exection and we need
01507         to reset it)
01508       */
01509       curr_join= tmp_join;
01510     }
01511     curr_tmp_table= exec_tmp_table1;
01512 
01513     /* Copy data to the temporary table */
01514     session->set_proc_info("Copying to tmp table");
01515     if (! curr_join->sort_and_group && curr_join->const_tables != curr_join->tables)
01516       curr_join->join_tab[curr_join->const_tables].sorted= 0;
01517     if ((tmp_error= do_select(curr_join, NULL, curr_tmp_table)))
01518     {
01519       error= tmp_error;
01520       return;
01521     }
01522     curr_tmp_table->cursor->info(HA_STATUS_VARIABLE);
01523 
01524     if (curr_join->having)
01525       curr_join->having= curr_join->tmp_having= 0; // Allready done
01526 
01527     /* Change sum_fields reference to calculated fields in tmp_table */
01528     curr_join->all_fields= *curr_all_fields;
01529     if (!items1)
01530     {
01531       items1= items0 + all_fields.size();
01532       if (sort_and_group || curr_tmp_table->group)
01533       {
01534         if (change_to_use_tmp_fields(session, items1,
01535                   tmp_fields_list1, tmp_all_fields1,
01536                   fields_list.size(), all_fields))
01537           return;
01538       }
01539       else
01540       {
01541         if (change_refs_to_tmp_fields(session, items1,
01542                     tmp_fields_list1, tmp_all_fields1,
01543                     fields_list.size(), all_fields))
01544           return;
01545       }
01546       curr_join->tmp_all_fields1= tmp_all_fields1;
01547       curr_join->tmp_fields_list1= tmp_fields_list1;
01548       curr_join->items1= items1;
01549     }
01550     curr_all_fields= &tmp_all_fields1;
01551     curr_fields_list= &tmp_fields_list1;
01552     curr_join->set_items_ref_array(items1);
01553 
01554     if (sort_and_group || curr_tmp_table->group)
01555     {
01556       curr_join->tmp_table_param.field_count+= curr_join->tmp_table_param.sum_func_count
01557                                              + curr_join->tmp_table_param.func_count;
01558       curr_join->tmp_table_param.sum_func_count= 0;
01559       curr_join->tmp_table_param.func_count= 0;
01560     }
01561     else
01562     {
01563       curr_join->tmp_table_param.field_count+= curr_join->tmp_table_param.func_count;
01564       curr_join->tmp_table_param.func_count= 0;
01565     }
01566 
01567     if (curr_tmp_table->group)
01568     {           // Already grouped
01569       if (!curr_join->order && !curr_join->no_order && !skip_sort_order)
01570         curr_join->order= curr_join->group_list;  /* order by group */
01571       curr_join->group_list= 0;
01572     }
01573 
01574     /*
01575       If we have different sort & group then we must sort the data by group
01576       and copy it to another tmp table
01577       This code is also used if we are using distinct something
01578       we haven't been able to store in the temporary table yet
01579       like SEC_TO_TIME(SUM(...)).
01580     */
01581 
01582     if ((curr_join->group_list && (!test_if_subpart(curr_join->group_list, curr_join->order) || curr_join->select_distinct)) 
01583         || (curr_join->select_distinct && curr_join->tmp_table_param.using_indirect_summary_function))
01584     {         /* Must copy to another table */
01585       /* Free first data from old join */
01586       curr_join->join_free();
01587       if (make_simple_join(curr_join, curr_tmp_table))
01588         return;
01589       calc_group_buffer(curr_join, group_list);
01590       count_field_types(select_lex, &curr_join->tmp_table_param,
01591       curr_join->tmp_all_fields1,
01592       curr_join->select_distinct && !curr_join->group_list);
01593       curr_join->tmp_table_param.hidden_field_count= curr_join->tmp_all_fields1.size()
01594                                                    - curr_join->tmp_fields_list1.size();
01595 
01596       if (exec_tmp_table2)
01597       {
01598         curr_tmp_table= exec_tmp_table2;
01599       }
01600       else
01601       {
01602         /* group data to new table */
01603 
01604         /*
01605           If the access method is loose index scan then all MIN/MAX
01606           functions are precomputed, and should be treated as regular
01607           functions. See extended comment in Join::exec.
01608         */
01609         if (curr_join->join_tab->is_using_loose_index_scan())
01610           curr_join->tmp_table_param.precomputed_group_by= true;
01611 
01612         if (!(curr_tmp_table=
01613               exec_tmp_table2= create_tmp_table(session,
01614                                                 &curr_join->tmp_table_param,
01615                                                 *curr_all_fields,
01616                                                 NULL,
01617                                                 curr_join->select_distinct &&
01618                                                 !curr_join->group_list,
01619                                                 1, curr_join->select_options,
01620                                                 HA_POS_ERROR,
01621                                                 (char *) "")))
01622         {
01623           return;
01624         }
01625 
01626         curr_join->exec_tmp_table2= exec_tmp_table2;
01627       }
01628       if (curr_join->group_list)
01629       {
01630         session->set_proc_info("Creating sort index");
01631         if (curr_join->join_tab == join_tab && save_join_tab())
01632         {
01633           return;
01634         }
01635         if (create_sort_index(session, curr_join, curr_join->group_list,
01636                   HA_POS_ERROR, HA_POS_ERROR, false) ||
01637             make_group_fields(this, curr_join))
01638         {
01639           return;
01640         }
01641         sortorder= curr_join->sortorder;
01642       }
01643 
01644       session->set_proc_info("Copying to group table");
01645       tmp_error= -1;
01646       if (curr_join != this)
01647       {
01648         if (sum_funcs2)
01649         {
01650           curr_join->sum_funcs= sum_funcs2;
01651           curr_join->sum_funcs_end= sum_funcs_end2;
01652         }
01653         else
01654         {
01655           curr_join->alloc_func_list();
01656           sum_funcs2= curr_join->sum_funcs;
01657           sum_funcs_end2= curr_join->sum_funcs_end;
01658         }
01659       }
01660       if (curr_join->make_sum_func_list(*curr_all_fields, *curr_fields_list, 1, true))
01661         return;
01662       curr_join->group_list= 0;
01663 
01664       if (!curr_join->sort_and_group && (curr_join->const_tables != curr_join->tables))
01665         curr_join->join_tab[curr_join->const_tables].sorted= 0;
01666       
01667       if (setup_sum_funcs(curr_join->session, curr_join->sum_funcs) 
01668         || (tmp_error= do_select(curr_join, NULL, curr_tmp_table)))
01669       {
01670         error= tmp_error;
01671         return;
01672       }
01673       curr_join->join_tab->read_record.end_read_record();
01674       curr_join->const_tables= curr_join->tables; // Mark free for cleanup()
01675       curr_join->join_tab[0].table= 0;           // Table is freed
01676 
01677       // No sum funcs anymore
01678       if (!items2)
01679       {
01680         items2= items1 + all_fields.size();
01681         if (change_to_use_tmp_fields(session, items2,
01682                   tmp_fields_list2, tmp_all_fields2,
01683                   fields_list.size(), tmp_all_fields1))
01684           return;
01685         curr_join->tmp_fields_list2= tmp_fields_list2;
01686         curr_join->tmp_all_fields2= tmp_all_fields2;
01687       }
01688       curr_fields_list= &curr_join->tmp_fields_list2;
01689       curr_all_fields= &curr_join->tmp_all_fields2;
01690       curr_join->set_items_ref_array(items2);
01691       curr_join->tmp_table_param.field_count+= curr_join->tmp_table_param.sum_func_count;
01692       curr_join->tmp_table_param.sum_func_count= 0;
01693     }
01694     if (curr_tmp_table->distinct)
01695       curr_join->select_distinct=0;   /* Each row is unique */
01696 
01697     curr_join->join_free();     /* Free quick selects */
01698     if (curr_join->select_distinct && ! curr_join->group_list)
01699     {
01700       session->set_proc_info("Removing duplicates");
01701       if (curr_join->tmp_having)
01702         curr_join->tmp_having->update_used_tables();
01703 
01704       if (remove_duplicates(curr_join, curr_tmp_table,
01705           *curr_fields_list, curr_join->tmp_having))
01706         return;
01707       
01708       curr_join->tmp_having=0;
01709       curr_join->select_distinct=0;
01710     }
01711     curr_tmp_table->reginfo.lock_type= TL_UNLOCK;
01712     if (make_simple_join(curr_join, curr_tmp_table))
01713       return;
01714     calc_group_buffer(curr_join, curr_join->group_list);
01715     count_field_types(select_lex, &curr_join->tmp_table_param, *curr_all_fields, 0);
01716 
01717   }
01718 
01719   if (curr_join->group || curr_join->tmp_table_param.sum_func_count)
01720   {
01721     if (make_group_fields(this, curr_join))
01722       return;
01723 
01724     if (! items3)
01725     {
01726       if (! items0)
01727         init_items_ref_array();
01728       items3= ref_pointer_array + (all_fields.size() * 4);
01729       setup_copy_fields(session, &curr_join->tmp_table_param,
01730       items3, tmp_fields_list3, tmp_all_fields3,
01731       curr_fields_list->size(), *curr_all_fields);
01732       tmp_table_param.save_copy_funcs= curr_join->tmp_table_param.copy_funcs;
01733       tmp_table_param.save_copy_field= curr_join->tmp_table_param.copy_field;
01734       tmp_table_param.save_copy_field_end= curr_join->tmp_table_param.copy_field_end;
01735       curr_join->tmp_all_fields3= tmp_all_fields3;
01736       curr_join->tmp_fields_list3= tmp_fields_list3;
01737     }
01738     else
01739     {
01740       curr_join->tmp_table_param.copy_funcs= tmp_table_param.save_copy_funcs;
01741       curr_join->tmp_table_param.copy_field= tmp_table_param.save_copy_field;
01742       curr_join->tmp_table_param.copy_field_end= tmp_table_param.save_copy_field_end;
01743     }
01744     curr_fields_list= &tmp_fields_list3;
01745     curr_all_fields= &tmp_all_fields3;
01746     curr_join->set_items_ref_array(items3);
01747 
01748     if (curr_join->make_sum_func_list(*curr_all_fields, *curr_fields_list,
01749               1, true) ||
01750         setup_sum_funcs(curr_join->session, curr_join->sum_funcs) ||
01751         session->is_fatal_error)
01752       return;
01753   }
01754   if (curr_join->group_list || curr_join->order)
01755   {
01756     session->set_proc_info("Sorting result");
01757     /* If we have already done the group, add HAVING to sorted table */
01758     if (curr_join->tmp_having && ! curr_join->group_list && ! curr_join->sort_and_group)
01759     {
01760       // Some tables may have been const
01761       curr_join->tmp_having->update_used_tables();
01762       JoinTable *curr_table= &curr_join->join_tab[curr_join->const_tables];
01763       table_map used_tables= (curr_join->const_table_map |
01764             curr_table->table->map);
01765 
01766       Item* sort_table_cond= make_cond_for_table(curr_join->tmp_having, used_tables, used_tables, 0);
01767       if (sort_table_cond)
01768       {
01769         if (!curr_table->select)
01770           if (!(curr_table->select= new optimizer::SqlSelect()))
01771             return;
01772         if (!curr_table->select->cond)
01773           curr_table->select->cond= sort_table_cond;
01774         else          // This should never happen
01775         {
01776           if (!(curr_table->select->cond=
01777           new Item_cond_and(curr_table->select->cond,
01778                 sort_table_cond)))
01779             return;
01780           /*
01781             Item_cond_and do not need fix_fields for execution, its parameters
01782             are fixed or do not need fix_fields, too
01783           */
01784           curr_table->select->cond->quick_fix_field();
01785         }
01786         curr_table->select_cond= curr_table->select->cond;
01787         curr_table->select_cond->top_level_item();
01788         curr_join->tmp_having= make_cond_for_table(curr_join->tmp_having,
01789                     ~ (table_map) 0,
01790                     ~used_tables, 0);
01791       }
01792     }
01793     {
01794       if (group)
01795         curr_join->select_limit= HA_POS_ERROR;
01796       else
01797       {
01798         /*
01799           We can abort sorting after session->select_limit rows if we there is no
01800           WHERE clause for any tables after the sorted one.
01801         */
01802         JoinTable *curr_table= &curr_join->join_tab[curr_join->const_tables+1];
01803         JoinTable *end_table= &curr_join->join_tab[curr_join->tables];
01804         for (; curr_table < end_table ; curr_table++)
01805         {
01806           /*
01807             table->keyuse is set in the case there was an original WHERE clause
01808             on the table that was optimized away.
01809           */
01810           if (curr_table->select_cond ||
01811               (curr_table->keyuse && !curr_table->first_inner))
01812           {
01813             /* We have to sort all rows */
01814             curr_join->select_limit= HA_POS_ERROR;
01815             break;
01816           }
01817         }
01818       }
01819       if (curr_join->join_tab == join_tab && save_join_tab())
01820         return;
01821       /*
01822         Here we sort rows for order_st BY/GROUP BY clause, if the optimiser
01823         chose FILESORT to be faster than INDEX SCAN or there is no
01824         suitable index present.
01825         Note, that create_sort_index calls test_if_skip_sort_order and may
01826         finally replace sorting with index scan if there is a LIMIT clause in
01827         the query. XXX: it's never shown in EXPLAIN!
01828         OPTION_FOUND_ROWS supersedes LIMIT and is taken into account.
01829       */
01830       if (create_sort_index(session, curr_join,
01831           curr_join->group_list ?
01832           curr_join->group_list : curr_join->order,
01833           curr_join->select_limit,
01834           (select_options & OPTION_FOUND_ROWS ?
01835            HA_POS_ERROR : unit->select_limit_cnt),
01836                             curr_join->group_list ? true : false))
01837         return;
01838 
01839       sortorder= curr_join->sortorder;
01840       if (curr_join->const_tables != curr_join->tables &&
01841           !curr_join->join_tab[curr_join->const_tables].table->sort.io_cache)
01842       {
01843         /*
01844           If no IO cache exists for the first table then we are using an
01845           INDEX SCAN and no filesort. Thus we should not remove the sorted
01846           attribute on the INDEX SCAN.
01847         */
01848         skip_sort_order= 1;
01849       }
01850     }
01851   }
01852   /* XXX: When can we have here session->is_error() not zero? */
01853   if (session->is_error())
01854   {
01855     error= session->is_error();
01856     return;
01857   }
01858   curr_join->having= curr_join->tmp_having;
01859   curr_join->fields= curr_fields_list;
01860 
01861   session->set_proc_info("Sending data");
01862   result->send_fields(*curr_fields_list);
01863   error= do_select(curr_join, curr_fields_list, NULL);
01864   session->limit_found_rows= curr_join->send_records;
01865 
01866   /* Accumulate the counts from all join iterations of all join parts. */
01867   session->examined_row_count+= curr_join->examined_rows;
01868 
01869   /*
01870     With EXPLAIN EXTENDED we have to restore original ref_array
01871     for a derived table which is always materialized.
01872     Otherwise we would not be able to print the query  correctly.
01873   */
01874   if (items0 && (session->lex().describe & DESCRIBE_EXTENDED) && select_lex->linkage == DERIVED_TABLE_TYPE)
01875     set_items_ref_array(items0);
01876 
01877   return;
01878 }
01879 
01886 int Join::destroy()
01887 {
01888   select_lex->join= 0;
01889 
01890   if (tmp_join)
01891   {
01892     if (join_tab != tmp_join->join_tab)
01893     {
01894       JoinTable *tab, *end;
01895       for (tab= join_tab, end= tab+tables ; tab != end ; tab++)
01896         tab->cleanup();
01897     }
01898     tmp_join->tmp_join= 0;
01899     tmp_table_param.copy_field=0;
01900     return(tmp_join->destroy());
01901   }
01902   cond_equal= 0;
01903 
01904   cleanup(1);
01905   exec_tmp_table1= NULL;
01906   exec_tmp_table2= NULL;
01907   delete select;
01908   delete_dynamic(&keyuse);
01909 
01910   return(error);
01911 }
01912 
01935 bool Join::setup_subquery_materialization()
01936 {
01937   for (Select_Lex_Unit *un= select_lex->first_inner_unit(); un;
01938        un= un->next_unit())
01939   {
01940     for (Select_Lex *sl= un->first_select(); sl; sl= sl->next_select())
01941     {
01942       Item_subselect *subquery_predicate= sl->master_unit()->item;
01943       if (subquery_predicate &&
01944           subquery_predicate->substype() == Item_subselect::IN_SUBS)
01945       {
01946         Item_in_subselect *in_subs= (Item_in_subselect*) subquery_predicate;
01947         if (in_subs->exec_method == Item_in_subselect::MATERIALIZATION &&
01948             in_subs->setup_engine())
01949           return true;
01950       }
01951     }
01952   }
01953   return false;
01954 }
01955 
01998 void Join::join_free()
01999 {
02000   Select_Lex_Unit *tmp_unit;
02001   Select_Lex *sl;
02002   /*
02003     Optimization: if not EXPLAIN and we are done with the Join,
02004     free all tables.
02005   */
02006   bool full= (select_lex->uncacheable.none() && ! session->lex().describe);
02007   bool can_unlock= full;
02008 
02009   cleanup(full);
02010 
02011   for (tmp_unit= select_lex->first_inner_unit();
02012        tmp_unit;
02013        tmp_unit= tmp_unit->next_unit())
02014     for (sl= tmp_unit->first_select(); sl; sl= sl->next_select())
02015     {
02016       Item_subselect *subselect= sl->master_unit()->item;
02017       bool full_local= full && (!subselect || 
02018                                 (subselect->is_evaluated() &&
02019                                 !subselect->is_uncacheable()));
02020       /*
02021         If this join is evaluated, we can fully clean it up and clean up all
02022         its underlying joins even if they are correlated -- they will not be
02023         used any more anyway.
02024         If this join is not yet evaluated, we still must clean it up to
02025         close its table cursors -- it may never get evaluated, as in case of
02026         ... HAVING false OR a IN (SELECT ...))
02027         but all table cursors must be closed before the unlock.
02028       */
02029       sl->cleanup_all_joins(full_local);
02030       /* Can't unlock if at least one Join is still needed */
02031       can_unlock= can_unlock && full_local;
02032     }
02033 
02034   /*
02035     We are not using tables anymore
02036     Unlock all tables. We may be in an INSERT .... SELECT statement.
02037   */
02038   if (can_unlock && lock && session->lock &&
02039       !(select_options & SELECT_NO_UNLOCK) &&
02040       !select_lex->subquery_in_having &&
02041       (select_lex == (session->lex().unit.fake_select_lex ?
02042                       session->lex().unit.fake_select_lex : &session->lex().select_lex)))
02043   {
02044     /*
02045       TODO: unlock tables even if the join isn't top level select in the
02046       tree.
02047     */
02048     session->unlockReadTables(lock);           // Don't free join->lock
02049     lock= 0;
02050   }
02051 
02052   return;
02053 }
02054 
02055 
02067 void Join::cleanup(bool full)
02068 {
02069   if (table)
02070   {
02071     /*
02072       Only a sorted table may be cached.  This sorted table is always the
02073       first non const table in join->table
02074     */
02075     if (tables > const_tables) // Test for not-const tables
02076     {
02077       table[const_tables]->free_io_cache();
02078       table[const_tables]->filesort_free_buffers(full);
02079     }
02080   }
02081 
02082   if (join_tab)
02083   {
02084     JoinTable *tab,*end;
02085 
02086     if (full)
02087     {
02088       for (tab= join_tab, end= tab+tables; tab != end; tab++)
02089         tab->cleanup();
02090       table= 0;
02091     }
02092     else
02093     {
02094       for (tab= join_tab, end= tab+tables; tab != end; tab++)
02095       {
02096         if (tab->table)
02097           tab->table->cursor->ha_index_or_rnd_end();
02098       }
02099     }
02100   }
02101 
02102   /*
02103     We are not using tables anymore
02104     Unlock all tables. We may be in an INSERT .... SELECT statement.
02105   */
02106   if (full)
02107   {
02108     if (tmp_join)
02109       tmp_table_param.copy_field= 0;
02110     group_fields.delete_elements();
02111     /*
02112       We can't call delete_elements() on copy_funcs as this will cause
02113       problems in free_elements() as some of the elements are then deleted.
02114     */
02115     tmp_table_param.copy_funcs.clear();
02116     /*
02117       If we have tmp_join and 'this' Join is not tmp_join and
02118       tmp_table_param.copy_field's  of them are equal then we have to remove
02119       pointer to  tmp_table_param.copy_field from tmp_join, because it qill
02120       be removed in tmp_table_param.cleanup().
02121     */
02122     if (tmp_join &&
02123         tmp_join != this &&
02124         tmp_join->tmp_table_param.copy_field ==
02125         tmp_table_param.copy_field)
02126     {
02127       tmp_join->tmp_table_param.copy_field=
02128         tmp_join->tmp_table_param.save_copy_field= 0;
02129     }
02130     tmp_table_param.cleanup();
02131   }
02132   return;
02133 }
02134 
02135 /*
02136   used only in Join::clear
02137 */
02138 static void clear_tables(Join *join)
02139 {
02140   /*
02141     must clear only the non-const tables, as const tables
02142     are not re-calculated.
02143   */
02144   for (uint32_t i= join->const_tables; i < join->tables; i++)
02145   {
02146     join->table[i]->mark_as_null_row();   // All fields are NULL
02147   }
02148 }
02149 
02159 bool Join::alloc_func_list()
02160 {
02161   uint32_t func_count, group_parts;
02162 
02163   func_count= tmp_table_param.sum_func_count;
02164   /*
02165     If we are using rollup, we need a copy of the summary functions for
02166     each level
02167   */
02168   if (rollup.getState() != Rollup::STATE_NONE)
02169     func_count*= (send_group_parts+1);
02170 
02171   group_parts= send_group_parts;
02172   /*
02173     If distinct, reserve memory for possible
02174     disctinct->group_by optimization
02175   */
02176   if (select_distinct)
02177   {
02178     group_parts+= fields_list.size();
02179     /*
02180       If the order_st clause is specified then it's possible that
02181       it also will be optimized, so reserve space for it too
02182     */
02183     if (order)
02184     {
02185       Order *ord;
02186       for (ord= order; ord; ord= ord->next)
02187         group_parts++;
02188     }
02189   }
02190 
02191   /* This must use calloc() as rollup_make_fields depends on this */
02192   sum_funcs= (Item_sum**) session->calloc(sizeof(Item_sum**) * (func_count+1) +
02193               sizeof(Item_sum***) * (group_parts+1));
02194   sum_funcs_end= (Item_sum***) (sum_funcs+func_count+1);
02195   return(sum_funcs == 0);
02196 }
02197 
02211 bool Join::make_sum_func_list(List<Item> &field_list, 
02212                               List<Item> &send_fields,
02213                               bool before_group_by, 
02214                               bool recompute)
02215 {
02216   List<Item>::iterator it(field_list.begin());
02217   Item_sum **func;
02218   Item *item;
02219 
02220   if (*sum_funcs && !recompute)
02221     return(false); /* We have already initialized sum_funcs. */
02222 
02223   func= sum_funcs;
02224   while ((item=it++))
02225   {
02226     if (item->type() == Item::SUM_FUNC_ITEM && !item->const_item() &&
02227         (!((Item_sum*) item)->depended_from() ||
02228          ((Item_sum *)item)->depended_from() == select_lex))
02229       *func++= (Item_sum*) item;
02230   }
02231   if (before_group_by && rollup.getState() == Rollup::STATE_INITED)
02232   {
02233     rollup.setState(Rollup::STATE_READY);
02234     if (rollup_make_fields(field_list, send_fields, &func))
02235       return true;     // Should never happen
02236   }
02237   else if (rollup.getState() == Rollup::STATE_NONE)
02238   {
02239     for (uint32_t i=0 ; i <= send_group_parts ;i++)
02240       sum_funcs_end[i]= func;
02241   }
02242   else if (rollup.getState() == Rollup::STATE_READY)
02243     return(false);                         // Don't put end marker
02244   *func=0;          // End marker
02245   return(false);
02246 }
02247 
02249 bool Join::rollup_init()
02250 {
02251   Item **ref_array;
02252 
02253   tmp_table_param.quick_group= 0; // Can't create groups in tmp table
02254   rollup.setState(Rollup::STATE_INITED);
02255 
02256   /*
02257     Create pointers to the different sum function groups
02258     These are updated by rollup_make_fields()
02259   */
02260   tmp_table_param.group_parts= send_group_parts;
02261 
02262   rollup.setNullItems((Item_null_result**) session->getMemRoot()->allocate((sizeof(Item*) +
02263                                                                 sizeof(Item**) +
02264                                                                 sizeof(List<Item>) +
02265                                                                 ref_pointer_array_size)
02266                                                                * send_group_parts ));
02267   if (! rollup.getNullItems())
02268   {
02269     return 1;
02270   }
02271 
02272   rollup.setFields((List<Item>*) (rollup.getNullItems() + send_group_parts));
02273   rollup.setRefPointerArrays((Item***) (rollup.getFields() + send_group_parts));
02274   ref_array= (Item**) (rollup.getRefPointerArrays()+send_group_parts);
02275 
02276   /*
02277     Prepare space for field list for the different levels
02278     These will be filled up in rollup_make_fields()
02279   */
02280   for (uint32_t i= 0 ; i < send_group_parts ; i++)
02281   {
02282     rollup.getNullItems()[i]= new (session->mem_root) Item_null_result();
02283     List<Item> *rollup_fields= &rollup.getFields()[i];
02284     rollup_fields->clear();
02285     rollup.getRefPointerArrays()[i]= ref_array;
02286     ref_array+= all_fields.size();
02287   }
02288 
02289   for (uint32_t i= 0 ; i < send_group_parts; i++)
02290   {
02291     for (uint32_t j= 0 ; j < fields_list.size() ; j++)
02292     {
02293       rollup.getFields()[i].push_back(rollup.getNullItems()[i]);
02294     }
02295   }
02296 
02297   List<Item>::iterator it(all_fields.begin());
02298   Item *item;
02299   while ((item= it++))
02300   {
02301     Order *group_tmp;
02302     bool found_in_group= 0;
02303 
02304     for (group_tmp= group_list; group_tmp; group_tmp= group_tmp->next)
02305     {
02306       if (*group_tmp->item == item)
02307       {
02308         item->maybe_null= 1;
02309         found_in_group= 1;
02310         if (item->const_item())
02311         {
02312           /*
02313             For ROLLUP queries each constant item referenced in GROUP BY list
02314             is wrapped up into an Item_func object yielding the same value
02315             as the constant item. The objects of the wrapper class are never
02316             considered as constant items and besides they inherit all
02317             properties of the Item_result_field class.
02318             This wrapping allows us to ensure writing constant items
02319             into temporary tables whenever the result of the ROLLUP
02320             operation has to be written into a temporary table, e.g. when
02321             ROLLUP is used together with DISTINCT in the SELECT list.
02322             Usually when creating temporary tables for a intermidiate
02323             result we do not include fields for constant expressions.
02324           */
02325           Item* new_item= new Item_func_rollup_const(item);
02326           if (!new_item)
02327             return 1;
02328           new_item->fix_fields(session, NULL);
02329           *it.ref()= new_item;
02330           for (Order *tmp= group_tmp; tmp; tmp= tmp->next)
02331           {
02332             if (*tmp->item == item)
02333               *tmp->item= new_item;
02334           }
02335         }
02336       }
02337     }
02338     if (item->type() == Item::FUNC_ITEM && !found_in_group)
02339     {
02340       bool changed= false;
02341       if (change_group_ref(session, (Item_func *) item, group_list, &changed))
02342         return 1;
02343       /*
02344         We have to prevent creation of a field in a temporary table for
02345         an expression that contains GROUP BY attributes.
02346         Marking the expression item as 'with_sum_func' will ensure this.
02347       */
02348       if (changed)
02349         item->with_sum_func= 1;
02350     }
02351   }
02352   return 0;
02353 }
02354 
02370 bool Join::rollup_make_fields(List<Item> &fields_arg, List<Item> &sel_fields, Item_sum ***func)
02371 {
02372   List<Item>::iterator it(fields_arg.begin());
02373   Item *first_field= &sel_fields.front();
02374   uint32_t level;
02375 
02376   /*
02377     Create field lists for the different levels
02378 
02379     The idea here is to have a separate field list for each rollup level to
02380     avoid all runtime checks of which columns should be NULL.
02381 
02382     The list is stored in reverse order to get sum function in such an order
02383     in func that it makes it easy to reset them with init_sum_functions()
02384 
02385     Assuming:  SELECT a, b, c SUM(b) FROM t1 GROUP BY a,b WITH ROLLUP
02386 
02387     rollup.fields[0] will contain list where a,b,c is NULL
02388     rollup.fields[1] will contain list where b,c is NULL
02389     ...
02390     rollup.ref_pointer_array[#] points to fields for rollup.fields[#]
02391     ...
02392     sum_funcs_end[0] points to all sum functions
02393     sum_funcs_end[1] points to all sum functions, except grand totals
02394     ...
02395   */
02396 
02397   for (level=0 ; level < send_group_parts ; level++)
02398   {
02399     uint32_t i;
02400     uint32_t pos= send_group_parts - level -1;
02401     bool real_fields= 0;
02402     Item *item;
02403     List<Item>::iterator new_it(rollup.getFields()[pos].begin());
02404     Item **ref_array_start= rollup.getRefPointerArrays()[pos];
02405     Order *start_group;
02406 
02407     /* Point to first hidden field */
02408     Item **ref_array= ref_array_start + fields_arg.size()-1;
02409 
02410     /* Remember where the sum functions ends for the previous level */
02411     sum_funcs_end[pos+1]= *func;
02412 
02413     /* Find the start of the group for this level */
02414     for (i= 0, start_group= group_list ;i++ < pos ;start_group= start_group->next)
02415     {}
02416 
02417     it= fields_arg.begin();
02418     while ((item= it++))
02419     {
02420       if (item == first_field)
02421       {
02422         real_fields= 1;       // End of hidden fields
02423         ref_array= ref_array_start;
02424       }
02425 
02426       if (item->type() == Item::SUM_FUNC_ITEM && !item->const_item() &&
02427           (!((Item_sum*) item)->depended_from() ||
02428            ((Item_sum *)item)->depended_from() == select_lex))
02429 
02430       {
02431         /*
02432           This is a top level summary function that must be replaced with
02433           a sum function that is reset for this level.
02434 
02435           NOTE: This code creates an object which is not that nice in a
02436           sub select.  Fortunately it's not common to have rollup in
02437           sub selects.
02438         */
02439         item= item->copy_or_same(session);
02440         ((Item_sum*) item)->make_unique();
02441         *(*func)= (Item_sum*) item;
02442         (*func)++;
02443       }
02444       else
02445       {
02446         /* Check if this is something that is part of this group by */
02447         Order *group_tmp;
02448         for (group_tmp= start_group, i= pos ;
02449                   group_tmp ; group_tmp= group_tmp->next, i++)
02450         {
02451                 if (*group_tmp->item == item)
02452           {
02453             /*
02454               This is an element that is used by the GROUP BY and should be
02455               set to NULL in this level
02456             */
02457                   Item_null_result *null_item= new (session->mem_root) Item_null_result();
02458                   if (!null_item)
02459                     return 1;
02460             item->maybe_null= 1;    // Value will be null sometimes
02461                   null_item->result_field= item->get_tmp_table_field();
02462                   item= null_item;
02463             break;
02464           }
02465         }
02466       }
02467       *ref_array= item;
02468       if (real_fields)
02469       {
02470   (void) new_it++;      // Point to next item
02471   new_it.replace(item);     // Replace previous
02472   ref_array++;
02473       }
02474       else
02475   ref_array--;
02476     }
02477   }
02478   sum_funcs_end[0]= *func;      // Point to last function
02479   return 0;
02480 }
02481 
02500 int Join::rollup_send_data(uint32_t idx)
02501 {
02502   for (uint32_t i= send_group_parts ; i-- > idx ; )
02503   {
02504     /* Get reference pointers to sum functions in place */
02505     memcpy(ref_pointer_array, rollup.getRefPointerArrays()[i], ref_pointer_array_size);
02506 
02507     if ((!having || having->val_int()))
02508     {
02509       if (send_records < unit->select_limit_cnt && do_send_rows && result->send_data(rollup.getFields()[i]))
02510       {
02511         return 1;
02512       }
02513       send_records++;
02514     }
02515   }
02516   /* Restore ref_pointer_array */
02517   set_items_ref_array(current_ref_pointer_array);
02518 
02519   return 0;
02520 }
02521 
02541 int Join::rollup_write_data(uint32_t idx, Table *table_arg)
02542 {
02543   for (uint32_t i= send_group_parts ; i-- > idx ; )
02544   {
02545     /* Get reference pointers to sum functions in place */
02546     memcpy(ref_pointer_array, rollup.getRefPointerArrays()[i],
02547            ref_pointer_array_size);
02548     if ((!having || having->val_int()))
02549     {
02550       int write_error;
02551       Item *item;
02552       List<Item>::iterator it(rollup.getFields()[i].begin());
02553       while ((item= it++))
02554       {
02555         if (item->type() == Item::NULL_ITEM && item->is_result_field())
02556           item->save_in_result_field(1);
02557       }
02558       copy_sum_funcs(sum_funcs_end[i+1], sum_funcs_end[i]);
02559       if ((write_error= table_arg->cursor->insertRecord(table_arg->getInsertRecord())))
02560       {
02561         my_error(ER_USE_SQL_BIG_RESULT, MYF(0));
02562         return 1;
02563       }
02564     }
02565   }
02566   /* Restore ref_pointer_array */
02567   set_items_ref_array(current_ref_pointer_array);
02568 
02569   return 0;
02570 }
02571 
02576 void Join::clear()
02577 {
02578   clear_tables(this);
02579   copy_fields(&tmp_table_param);
02580 
02581   if (sum_funcs)
02582   {
02583     Item_sum *func, **func_ptr= sum_funcs;
02584     while ((func= *(func_ptr++)))
02585       func->clear();
02586   }
02587 }
02588 
02599 bool Join::change_result(select_result *res)
02600 {
02601   result= res;
02602   if (result->prepare(fields_list, select_lex->master_unit()))
02603   {
02604     return(true);
02605   }
02606   return(false);
02607 }
02608 
02613 void Join::cache_const_exprs()
02614 {
02615   bool cache_flag= false;
02616   bool *analyzer_arg= &cache_flag;
02617 
02618   /* No need in cache if all tables are constant. */
02619   if (const_tables == tables)
02620     return;
02621 
02622   if (conds)
02623     conds->compile(&Item::cache_const_expr_analyzer, (unsigned char **)&analyzer_arg,
02624                   &Item::cache_const_expr_transformer, (unsigned char *)&cache_flag);
02625   cache_flag= false;
02626   if (having)
02627     having->compile(&Item::cache_const_expr_analyzer, (unsigned char **)&analyzer_arg,
02628                     &Item::cache_const_expr_transformer, (unsigned char *)&cache_flag);
02629 
02630   for (JoinTable *tab= join_tab + const_tables; tab < join_tab + tables ; tab++)
02631   {
02632     if (*tab->on_expr_ref)
02633     {
02634       cache_flag= false;
02635       (*tab->on_expr_ref)->compile(&Item::cache_const_expr_analyzer,
02636                                  (unsigned char **)&analyzer_arg,
02637                                  &Item::cache_const_expr_transformer,
02638                                  (unsigned char *)&cache_flag);
02639     }
02640   }
02641 }
02642 
02654 enum_nested_loop_state evaluate_join_record(Join *join, JoinTable *join_tab, int error)
02655 {
02656   bool not_used_in_distinct= join_tab->not_used_in_distinct;
02657   ha_rows found_records= join->found_records;
02658   COND *select_cond= join_tab->select_cond;
02659 
02660   if (error > 0 || (join->session->is_error()))     // Fatal error
02661     return NESTED_LOOP_ERROR;
02662   if (error < 0)
02663     return NESTED_LOOP_NO_MORE_ROWS;
02664   if (join->session->getKilled())     // Aborted by user
02665   {
02666     join->session->send_kill_message();
02667     return NESTED_LOOP_KILLED;
02668   }
02669   if (!select_cond || select_cond->val_int())
02670   {
02671     /*
02672       There is no select condition or the attached pushed down
02673       condition is true => a match is found.
02674     */
02675     bool found= 1;
02676     while (join_tab->first_unmatched && found)
02677     {
02678       /*
02679         The while condition is always false if join_tab is not
02680         the last inner join table of an outer join operation.
02681       */
02682       JoinTable *first_unmatched= join_tab->first_unmatched;
02683       /*
02684         Mark that a match for current outer table is found.
02685         This activates push down conditional predicates attached
02686         to the all inner tables of the outer join.
02687       */
02688       first_unmatched->found= 1;
02689       for (JoinTable *tab= first_unmatched; tab <= join_tab; tab++)
02690       {
02691         if (tab->table->reginfo.not_exists_optimize)
02692           return NESTED_LOOP_NO_MORE_ROWS;
02693         /* Check all predicates that has just been activated. */
02694         /*
02695           Actually all predicates non-guarded by first_unmatched->found
02696           will be re-evaluated again. It could be fixed, but, probably,
02697           it's not worth doing now.
02698         */
02699         if (tab->select_cond && !tab->select_cond->val_int())
02700         {
02701           /* The condition attached to table tab is false */
02702           if (tab == join_tab)
02703             found= 0;
02704           else
02705           {
02706             /*
02707               Set a return point if rejected predicate is attached
02708               not to the last table of the current nest level.
02709             */
02710             join->return_tab= tab;
02711             return NESTED_LOOP_OK;
02712           }
02713         }
02714       }
02715       /*
02716         Check whether join_tab is not the last inner table
02717         for another embedding outer join.
02718       */
02719       if ((first_unmatched= first_unmatched->first_upper) &&
02720           first_unmatched->last_inner != join_tab)
02721         first_unmatched= 0;
02722       join_tab->first_unmatched= first_unmatched;
02723     }
02724 
02725     JoinTable *return_tab= join->return_tab;
02726     join_tab->found_match= true;
02727 
02728     /*
02729       It was not just a return to lower loop level when one
02730       of the newly activated predicates is evaluated as false
02731       (See above join->return_tab= tab).
02732     */
02733     join->examined_rows++;
02734     join->session->row_count++;
02735 
02736     if (found)
02737     {
02738       enum enum_nested_loop_state rc;
02739       /* A match from join_tab is found for the current partial join. */
02740       rc= (*join_tab->next_select)(join, join_tab+1, 0);
02741       if (rc != NESTED_LOOP_OK && rc != NESTED_LOOP_NO_MORE_ROWS)
02742         return rc;
02743       if (return_tab < join->return_tab)
02744         join->return_tab= return_tab;
02745 
02746       if (join->return_tab < join_tab)
02747         return NESTED_LOOP_OK;
02748       /*
02749         Test if this was a SELECT DISTINCT query on a table that
02750         was not in the field list;  In this case we can abort if
02751         we found a row, as no new rows can be added to the result.
02752       */
02753       if (not_used_in_distinct && found_records != join->found_records)
02754         return NESTED_LOOP_NO_MORE_ROWS;
02755     }
02756     else
02757       join_tab->read_record.cursor->unlock_row();
02758   }
02759   else
02760   {
02761     /*
02762       The condition pushed down to the table join_tab rejects all rows
02763       with the beginning coinciding with the current partial join.
02764     */
02765     join->examined_rows++;
02766     join->session->row_count++;
02767     join_tab->read_record.cursor->unlock_row();
02768   }
02769   return NESTED_LOOP_OK;
02770 }
02771 
02778 enum_nested_loop_state evaluate_null_complemented_join_record(Join *join, JoinTable *join_tab)
02779 {
02780   /*
02781     The table join_tab is the first inner table of a outer join operation
02782     and no matches has been found for the current outer row.
02783   */
02784   JoinTable *last_inner_tab= join_tab->last_inner;
02785   /* Cache variables for faster loop */
02786   COND *select_cond;
02787   for ( ; join_tab <= last_inner_tab ; join_tab++)
02788   {
02789     /* Change the the values of guard predicate variables. */
02790     join_tab->found= 1;
02791     join_tab->not_null_compl= 0;
02792     /* The outer row is complemented by nulls for each inner tables */
02793     join_tab->table->restoreRecordAsDefault();  // Make empty record
02794     join_tab->table->mark_as_null_row();       // For group by without error
02795     select_cond= join_tab->select_cond;
02796     /* Check all attached conditions for inner table rows. */
02797     if (select_cond && !select_cond->val_int())
02798       return NESTED_LOOP_OK;
02799   }
02800   join_tab--;
02801   /*
02802     The row complemented by nulls might be the first row
02803     of embedding outer joins.
02804     If so, perform the same actions as in the code
02805     for the first regular outer join row above.
02806   */
02807   for ( ; ; )
02808   {
02809     JoinTable *first_unmatched= join_tab->first_unmatched;
02810     if ((first_unmatched= first_unmatched->first_upper) && first_unmatched->last_inner != join_tab)
02811       first_unmatched= 0;
02812     join_tab->first_unmatched= first_unmatched;
02813     if (! first_unmatched)
02814       break;
02815     first_unmatched->found= 1;
02816     for (JoinTable *tab= first_unmatched; tab <= join_tab; tab++)
02817     {
02818       if (tab->select_cond && !tab->select_cond->val_int())
02819       {
02820         join->return_tab= tab;
02821         return NESTED_LOOP_OK;
02822       }
02823     }
02824   }
02825   /*
02826     The row complemented by nulls satisfies all conditions
02827     attached to inner tables.
02828     Send the row complemented by nulls to be joined with the
02829     remaining tables.
02830   */
02831   return (*join_tab->next_select)(join, join_tab+1, 0);
02832 }
02833 
02834 enum_nested_loop_state flush_cached_records(Join *join, JoinTable *join_tab, bool skip_last)
02835 {
02836   enum_nested_loop_state rc= NESTED_LOOP_OK;
02837   int error;
02838   ReadRecord *info;
02839 
02840   join_tab->table->null_row= 0;
02841   if (!join_tab->cache.records)
02842   {
02843     return NESTED_LOOP_OK;                      /* Nothing to do */
02844   }
02845 
02846   if (skip_last)
02847   {
02848     (void) join_tab->cache.store_record_in_cache(); // Must save this for later
02849   }
02850 
02851 
02852   if (join_tab->use_quick == 2)
02853   {
02854     if (join_tab->select->quick)
02855     {         /* Used quick select last. reset it */
02856       delete join_tab->select->quick;
02857       join_tab->select->quick=0;
02858     }
02859   }
02860   /* read through all records */
02861   if ((error=join_init_read_record(join_tab)))
02862   {
02863     join_tab->cache.reset_cache_write();
02864     return error < 0 ? NESTED_LOOP_NO_MORE_ROWS: NESTED_LOOP_ERROR;
02865   }
02866 
02867   for (JoinTable *tmp=join->join_tab; tmp != join_tab ; tmp++)
02868   {
02869     tmp->status=tmp->table->status;
02870     tmp->table->status=0;
02871   }
02872 
02873   info= &join_tab->read_record;
02874   do
02875   {
02876     if (join->session->getKilled())
02877     {
02878       join->session->send_kill_message();
02879       return NESTED_LOOP_KILLED;
02880     }
02881     optimizer::SqlSelect *select= join_tab->select;
02882     if (rc == NESTED_LOOP_OK &&
02883         (!join_tab->cache.select || !join_tab->cache.select->skip_record()))
02884     {
02885       uint32_t i;
02886       join_tab->cache.reset_cache_read();
02887       for (i=(join_tab->cache.records- (skip_last ? 1 : 0)) ; i-- > 0 ;)
02888       {
02889         join_tab->readCachedRecord();
02890         if (!select || !select->skip_record())
02891         {
02892           int res= 0;
02893 
02894           rc= (join_tab->next_select)(join,join_tab+1,0);
02895           if (rc != NESTED_LOOP_OK && rc != NESTED_LOOP_NO_MORE_ROWS)
02896           {
02897             join_tab->cache.reset_cache_write();
02898             return rc;
02899           }
02900 
02901           if (res == -1)
02902             return NESTED_LOOP_ERROR;
02903         }
02904       }
02905     }
02906   } while (!(error=info->read_record(info)));
02907 
02908   if (skip_last)
02909     join_tab->readCachedRecord();   // Restore current record
02910   join_tab->cache.reset_cache_write();
02911   if (error > 0)        // Fatal error
02912     return NESTED_LOOP_ERROR;
02913   for (JoinTable *tmp2=join->join_tab; tmp2 != join_tab ; tmp2++)
02914     tmp2->table->status=tmp2->status;
02915   return NESTED_LOOP_OK;
02916 }
02917 
02918 /*****************************************************************************
02919   DESCRIPTION
02920     Functions that end one nested loop iteration. Different functions
02921     are used to support GROUP BY clause and to redirect records
02922     to a table (e.g. in case of SELECT into a temporary table) or to the
02923     network client.
02924 
02925   RETURN VALUES
02926     NESTED_LOOP_OK           - the record has been successfully handled
02927     NESTED_LOOP_ERROR        - a fatal error (like table corruption)
02928                                was detected
02929     NESTED_LOOP_KILLED       - thread shutdown was requested while processing
02930                                the record
02931     NESTED_LOOP_QUERY_LIMIT  - the record has been successfully handled;
02932                                additionally, the nested loop produced the
02933                                number of rows specified in the LIMIT clause
02934                                for the query
02935     NESTED_LOOP_CURSOR_LIMIT - the record has been successfully handled;
02936                                additionally, there is a cursor and the nested
02937                                loop algorithm produced the number of rows
02938                                that is specified for current cursor fetch
02939                                operation.
02940    All return values except NESTED_LOOP_OK abort the nested loop.
02941 *****************************************************************************/
02942 enum_nested_loop_state end_send(Join *join, JoinTable *, bool end_of_records)
02943 {
02944   if (! end_of_records)
02945   {
02946     int error;
02947     if (join->having && join->having->val_int() == 0)
02948       return NESTED_LOOP_OK;               // Didn't match having
02949     error= 0;
02950     if (join->do_send_rows)
02951       error=join->result->send_data(*join->fields);
02952     if (error)
02953       return NESTED_LOOP_ERROR;
02954     if (++join->send_records >= join->unit->select_limit_cnt && join->do_send_rows)
02955     {
02956       if (join->select_options & OPTION_FOUND_ROWS)
02957       {
02958         JoinTable *jt=join->join_tab;
02959         if ((join->tables == 1) && !join->tmp_table && !join->sort_and_group
02960             && !join->send_group_parts && !join->having && !jt->select_cond &&
02961             !(jt->select && jt->select->quick) &&
02962             (jt->table->cursor->getEngine()->check_flag(HTON_BIT_STATS_RECORDS_IS_EXACT)) &&
02963                   (jt->ref.key < 0))
02964         {
02965           /* Join over all rows in table;  Return number of found rows */
02966           Table *table= jt->table;
02967 
02968           join->select_options^= OPTION_FOUND_ROWS;
02969           if (table->sort.record_pointers ||
02970               (table->sort.io_cache && my_b_inited(table->sort.io_cache)))
02971           {
02972             /* Using filesort */
02973             join->send_records= table->sort.found_records;
02974           }
02975           else
02976           {
02977             table->cursor->info(HA_STATUS_VARIABLE);
02978             join->send_records= table->cursor->stats.records;
02979           }
02980         }
02981         else
02982         {
02983           join->do_send_rows= 0;
02984           if (join->unit->fake_select_lex)
02985             join->unit->fake_select_lex->select_limit= 0;
02986           return NESTED_LOOP_OK;
02987         }
02988       }
02989       return NESTED_LOOP_QUERY_LIMIT;      // Abort nicely
02990     }
02991     else if (join->send_records >= join->fetch_limit)
02992     {
02993       /*
02994         There is a server side cursor and all rows for
02995         this fetch request are sent.
02996       */
02997       return NESTED_LOOP_CURSOR_LIMIT;
02998     }
02999   }
03000 
03001   return NESTED_LOOP_OK;
03002 }
03003 
03004 enum_nested_loop_state end_write(Join *join, JoinTable *, bool end_of_records)
03005 {
03006   Table *table= join->tmp_table;
03007 
03008   if (join->session->getKilled())     // Aborted by user
03009   {
03010     join->session->send_kill_message();
03011     return NESTED_LOOP_KILLED;
03012   }
03013   if (!end_of_records)
03014   {
03015     copy_fields(&join->tmp_table_param);
03016     if (copy_funcs(join->tmp_table_param.items_to_copy, join->session))
03017       return NESTED_LOOP_ERROR;
03018     if (!join->having || join->having->val_int())
03019     {
03020       int error;
03021       join->found_records++;
03022       if ((error=table->cursor->insertRecord(table->getInsertRecord())))
03023       {
03024         if (!table->cursor->is_fatal_error(error, HA_CHECK_DUP))
03025         {
03026           return NESTED_LOOP_OK;
03027         }
03028 
03029         my_error(ER_USE_SQL_BIG_RESULT, MYF(0));
03030         return NESTED_LOOP_ERROR;        // Table is_full error
03031       }
03032       if (++join->send_records >= join->tmp_table_param.end_write_records && join->do_send_rows)
03033       {
03034         if (!(join->select_options & OPTION_FOUND_ROWS))
03035           return NESTED_LOOP_QUERY_LIMIT;
03036         join->do_send_rows= 0;
03037         join->unit->select_limit_cnt= HA_POS_ERROR;
03038         return NESTED_LOOP_OK;
03039       }
03040     }
03041   }
03042 
03043   return NESTED_LOOP_OK;
03044 }
03045 
03047 enum_nested_loop_state end_update(Join *join, JoinTable *, bool end_of_records)
03048 {
03049   Table *table= join->tmp_table;
03050   Order *group;
03051   int error;
03052 
03053   if (end_of_records)
03054     return NESTED_LOOP_OK;
03055   if (join->session->getKilled())     // Aborted by user
03056   {
03057     join->session->send_kill_message();
03058     return NESTED_LOOP_KILLED;
03059   }
03060 
03061   join->found_records++;
03062   copy_fields(&join->tmp_table_param);    // Groups are copied twice.
03063   /* Make a key of group index */
03064   for (group=table->group ; group ; group=group->next)
03065   {
03066     Item *item= *group->item;
03067     item->save_org_in_field(group->field);
03068     /* Store in the used key if the field was 0 */
03069     if (item->maybe_null)
03070       group->buff[-1]= (char) group->field->is_null();
03071   }
03072   if (!table->cursor->index_read_map(table->getUpdateRecord(),
03073                                    join->tmp_table_param.group_buff,
03074                                    HA_WHOLE_KEY,
03075                                    HA_READ_KEY_EXACT))
03076   {           /* Update old record */
03077     table->restoreRecord();
03078     update_tmptable_sum_func(join->sum_funcs,table);
03079     if ((error= table->cursor->updateRecord(table->getUpdateRecord(),
03080                                           table->getInsertRecord())))
03081     {
03082       table->print_error(error,MYF(0));
03083       return NESTED_LOOP_ERROR;
03084     }
03085     return NESTED_LOOP_OK;
03086   }
03087 
03088   /*
03089     Copy null bits from group key to table
03090     We can't copy all data as the key may have different format
03091     as the row data (for example as with VARCHAR keys)
03092   */
03093   KeyPartInfo *key_part;
03094   for (group=table->group,key_part=table->key_info[0].key_part;
03095        group ;
03096        group=group->next,key_part++)
03097   {
03098     if (key_part->null_bit)
03099       memcpy(table->getInsertRecord()+key_part->offset, group->buff, 1);
03100   }
03101   init_tmptable_sum_functions(join->sum_funcs);
03102   if (copy_funcs(join->tmp_table_param.items_to_copy, join->session))
03103     return NESTED_LOOP_ERROR;
03104   if ((error=table->cursor->insertRecord(table->getInsertRecord())))
03105   {
03106     my_error(ER_USE_SQL_BIG_RESULT, MYF(0));
03107     return NESTED_LOOP_ERROR;        // Table is_full error
03108   }
03109   join->send_records++;
03110   return NESTED_LOOP_OK;
03111 }
03112 
03114 enum_nested_loop_state end_unique_update(Join *join, JoinTable *, bool end_of_records)
03115 {
03116   Table *table= join->tmp_table;
03117   int error;
03118 
03119   if (end_of_records)
03120     return NESTED_LOOP_OK;
03121   if (join->session->getKilled())     // Aborted by user
03122   {
03123     join->session->send_kill_message();
03124     return NESTED_LOOP_KILLED;
03125   }
03126 
03127   init_tmptable_sum_functions(join->sum_funcs);
03128   copy_fields(&join->tmp_table_param);    // Groups are copied twice.
03129   if (copy_funcs(join->tmp_table_param.items_to_copy, join->session))
03130     return NESTED_LOOP_ERROR;
03131 
03132   if (!(error= table->cursor->insertRecord(table->getInsertRecord())))
03133     join->send_records++;     // New group
03134   else
03135   {
03136     if ((int) table->get_dup_key(error) < 0)
03137     {
03138       table->print_error(error,MYF(0));
03139       return NESTED_LOOP_ERROR;
03140     }
03141     if (table->cursor->rnd_pos(table->getUpdateRecord(),table->cursor->dup_ref))
03142     {
03143       table->print_error(error,MYF(0));
03144       return NESTED_LOOP_ERROR;
03145     }
03146     table->restoreRecord();
03147     update_tmptable_sum_func(join->sum_funcs,table);
03148     if ((error= table->cursor->updateRecord(table->getUpdateRecord(),
03149                                           table->getInsertRecord())))
03150     {
03151       table->print_error(error,MYF(0));
03152       return NESTED_LOOP_ERROR;
03153     }
03154   }
03155   return NESTED_LOOP_OK;
03156 }
03157 
03170 static bool make_group_fields(Join *main_join, Join *curr_join)
03171 {
03172   if (main_join->group_fields_cache.size())
03173   {
03174     curr_join->group_fields= main_join->group_fields_cache;
03175     curr_join->sort_and_group= 1;
03176   }
03177   else
03178   {
03179     if (alloc_group_fields(curr_join, curr_join->group_list))
03180       return 1;
03181     main_join->group_fields_cache= curr_join->group_fields;
03182   }
03183   return (0);
03184 }
03185 
03189 static void calc_group_buffer(Join *join, Order *group)
03190 {
03191   uint32_t key_length=0, parts=0, null_parts=0;
03192 
03193   if (group)
03194     join->group= 1;
03195   for (; group ; group=group->next)
03196   {
03197     Item *group_item= *group->item;
03198     Field *field= group_item->get_tmp_table_field();
03199     if (field)
03200     {
03201       enum_field_types type;
03202       if ((type= field->type()) == DRIZZLE_TYPE_BLOB)
03203         key_length+=MAX_BLOB_WIDTH;   // Can't be used as a key
03204       else if (type == DRIZZLE_TYPE_VARCHAR)
03205         key_length+= field->field_length + HA_KEY_BLOB_LENGTH;
03206       else
03207         key_length+= field->pack_length();
03208     }
03209     else
03210     {
03211       switch (group_item->result_type()) {
03212       case REAL_RESULT:
03213         key_length+= sizeof(double);
03214         break;
03215 
03216       case INT_RESULT:
03217         key_length+= sizeof(int64_t);
03218         break;
03219 
03220       case DECIMAL_RESULT:
03221         key_length+= class_decimal_get_binary_size(group_item->max_length -
03222                                                 (group_item->decimals ? 1 : 0),
03223                                                 group_item->decimals);
03224         break;
03225 
03226       case STRING_RESULT:
03227         {
03228           enum enum_field_types type= group_item->field_type();
03229           /*
03230             As items represented as DATE/TIME fields in the group buffer
03231             have STRING_RESULT result type, we increase the length
03232             by 8 as maximum pack length of such fields.
03233           */
03234           if (field::isDateTime(type))
03235           {
03236             key_length+= 8;
03237           }
03238           else
03239           {
03240             /*
03241               Group strings are taken as varstrings and require an length field.
03242               A field is not yet created by create_tmp_field()
03243               and the sizes should match up.
03244             */
03245             key_length+= group_item->max_length + HA_KEY_BLOB_LENGTH;
03246           }
03247 
03248           break;
03249         }
03250 
03251       case ROW_RESULT:
03252         /* This case should never be choosen */
03253         assert(0);
03254         my_error(ER_OUT_OF_RESOURCES, MYF(ME_FATALERROR));
03255       }
03256     }
03257 
03258     parts++;
03259 
03260     if (group_item->maybe_null)
03261       null_parts++;
03262   }
03263 
03264   join->tmp_table_param.group_length=key_length+null_parts;
03265   join->tmp_table_param.group_parts=parts;
03266   join->tmp_table_param.group_null_parts=null_parts;
03267 }
03268 
03274 static bool alloc_group_fields(Join *join, Order *group)
03275 {
03276   if (group)
03277   {
03278     for (; group ; group=group->next)
03279     {
03280       Cached_item *tmp= new_Cached_item(join->session, *group->item);
03281       if (!tmp || join->group_fields.push_front(tmp))
03282         return true;
03283     }
03284   }
03285   join->sort_and_group=1;     /* Mark for do_select */
03286   return false;
03287 }
03288 
03289 static uint32_t cache_record_length(Join *join,uint32_t idx)
03290 {
03291   uint32_t length=0;
03292   JoinTable **pos,**end;
03293   Session *session=join->session;
03294 
03295   for (pos=join->best_ref+join->const_tables,end=join->best_ref+idx ;
03296        pos != end ;
03297        pos++)
03298   {
03299     JoinTable *join_tab= *pos;
03300     if (!join_tab->used_fieldlength)    /* Not calced yet */
03301       calc_used_field_length(session, join_tab);
03302     length+=join_tab->used_fieldlength;
03303   }
03304   return length;
03305 }
03306 
03307 /*
03308   Get the number of different row combinations for subset of partial join
03309 
03310   SYNOPSIS
03311     prev_record_reads()
03312       join       The join structure
03313       idx        Number of tables in the partial join order (i.e. the
03314                  partial join order is in join->positions[0..idx-1])
03315       found_ref  Bitmap of tables for which we need to find # of distinct
03316                  row combinations.
03317 
03318   DESCRIPTION
03319     Given a partial join order (in join->positions[0..idx-1]) and a subset of
03320     tables within that join order (specified in found_ref), find out how many
03321     distinct row combinations of subset tables will be in the result of the
03322     partial join order.
03323 
03324     This is used as follows: Suppose we have a table accessed with a ref-based
03325     method. The ref access depends on current rows of tables in found_ref.
03326     We want to count # of different ref accesses. We assume two ref accesses
03327     will be different if at least one of access parameters is different.
03328     Example: consider a query
03329 
03330     SELECT * FROM t1, t2, t3 WHERE t1.key=c1 AND t2.key=c2 AND t3.key=t1.field
03331 
03332     and a join order:
03333       t1,  ref access on t1.key=c1
03334       t2,  ref access on t2.key=c2
03335       t3,  ref access on t3.key=t1.field
03336 
03337     For t1: n_ref_scans = 1, n_distinct_ref_scans = 1
03338     For t2: n_ref_scans = records_read(t1), n_distinct_ref_scans=1
03339     For t3: n_ref_scans = records_read(t1)*records_read(t2)
03340             n_distinct_ref_scans = #records_read(t1)
03341 
03342     The reason for having this function (at least the latest version of it)
03343     is that we need to account for buffering in join execution.
03344 
03345     An edge-case example: if we have a non-first table in join accessed via
03346     ref(const) or ref(param) where there is a small number of different
03347     values of param, then the access will likely hit the disk cache and will
03348     not require any disk seeks.
03349 
03350     The proper solution would be to assume an LRU disk cache of some size,
03351     calculate probability of cache hits, etc. For now we just count
03352     identical ref accesses as one.
03353 
03354   RETURN
03355     Expected number of row combinations
03356 */
03357 static double prev_record_reads(Join *join, uint32_t idx, table_map found_ref)
03358 {
03359   double found=1.0;
03360   optimizer::Position *pos_end= join->getSpecificPosInPartialPlan(-1);
03361   for (optimizer::Position *pos= join->getSpecificPosInPartialPlan(idx - 1); 
03362        pos != pos_end; 
03363        pos--)
03364   {
03365     if (pos->examinePosition(found_ref))
03366     {
03367       found_ref|= pos->getRefDependMap();
03368       /*
03369         For the case of "t1 LEFT Join t2 ON ..." where t2 is a const table
03370         with no matching row we will get position[t2].records_read==0.
03371         Actually the size of output is one null-complemented row, therefore
03372         we will use value of 1 whenever we get records_read==0.
03373 
03374         Note
03375         - the above case can't occur if inner part of outer join has more
03376           than one table: table with no matches will not be marked as const.
03377 
03378         - Ideally we should add 1 to records_read for every possible null-
03379           complemented row. We're not doing it because: 1. it will require
03380           non-trivial code and add overhead. 2. The value of records_read
03381           is an inprecise estimate and adding 1 (or, in the worst case,
03382           #max_nested_outer_joins=64-1) will not make it any more precise.
03383       */
03384       if (pos->getFanout() > DBL_EPSILON)
03385         found*= pos->getFanout();
03386     }
03387   }
03388   return found;
03389 }
03390 
03394 static bool get_best_combination(Join *join)
03395 {
03396   uint32_t i,tablenr;
03397   table_map used_tables;
03398   JoinTable *join_tab,*j;
03399   optimizer::KeyUse *keyuse;
03400   uint32_t table_count;
03401   Session *session=join->session;
03402   optimizer::Position cur_pos;
03403 
03404   table_count=join->tables;
03405   if (!(join->join_tab=join_tab=
03406   (JoinTable*) session->getMemRoot()->allocate(sizeof(JoinTable)*table_count)))
03407     return(true);
03408 
03409   for (i= 0; i < table_count; i++)
03410     new (join_tab+i) JoinTable();
03411 
03412   join->full_join=0;
03413 
03414   used_tables= OUTER_REF_TABLE_BIT;   // Outer row is already read
03415   for (j=join_tab, tablenr=0 ; tablenr < table_count ; tablenr++,j++)
03416   {
03417     Table *form;
03418     cur_pos= join->getPosFromOptimalPlan(tablenr);
03419     *j= *cur_pos.getJoinTable();
03420     form=join->table[tablenr]=j->table;
03421     used_tables|= form->map;
03422     form->reginfo.join_tab=j;
03423     if (!*j->on_expr_ref)
03424       form->reginfo.not_exists_optimize=0;  // Only with LEFT Join
03425     if (j->type == AM_CONST)
03426       continue;         // Handled in make_join_stat..
03427 
03428     j->ref.key = -1;
03429     j->ref.key_parts=0;
03430 
03431     if (j->type == AM_SYSTEM)
03432       continue;
03433     if (j->keys.none() || ! (keyuse= cur_pos.getKeyUse()))
03434     {
03435       j->type= AM_ALL;
03436       if (tablenr != join->const_tables)
03437         join->full_join=1;
03438     }
03439     else if (create_ref_for_key(join, j, keyuse, used_tables))
03440       return(true);                        // Something went wrong
03441   }
03442 
03443   for (i=0 ; i < table_count ; i++)
03444     join->map2table[join->join_tab[i].table->tablenr]=join->join_tab+i;
03445   update_depend_map(join);
03446   return(0);
03447 }
03448 
03450 static void set_position(Join *join,
03451                          uint32_t idx,
03452                          JoinTable *table,
03453                          optimizer::KeyUse *key)
03454 {
03455   optimizer::Position tmp_pos(1.0, /* This is a const table */
03456                               0.0,
03457                               table,
03458                               key,
03459                               0);
03460   join->setPosInPartialPlan(idx, tmp_pos);
03461 
03462   /* Move the const table as down as possible in best_ref */
03463   JoinTable **pos=join->best_ref+idx+1;
03464   JoinTable *next=join->best_ref[idx];
03465   for (;next != table ; pos++)
03466   {
03467     JoinTable *tmp=pos[0];
03468     pos[0]=next;
03469     next=tmp;
03470   }
03471   join->best_ref[idx]=table;
03472 }
03473 
03492 static bool choose_plan(Join *join, table_map join_tables)
03493 {
03494   uint32_t search_depth= join->session->variables.optimizer_search_depth;
03495   uint32_t prune_level=  join->session->variables.optimizer_prune_level;
03496   bool straight_join= test(join->select_options & SELECT_STRAIGHT_JOIN);
03497 
03498   join->cur_embedding_map.reset();
03499   reset_nj_counters(join->join_list);
03500   /*
03501     if (SELECT_STRAIGHT_JOIN option is set)
03502       reorder tables so dependent tables come after tables they depend
03503       on, otherwise keep tables in the order they were specified in the query
03504     else
03505       Apply heuristic: pre-sort all access plans with respect to the number of
03506       records accessed.
03507   */
03508   internal::my_qsort(join->best_ref + join->const_tables,
03509                      join->tables - join->const_tables, sizeof(JoinTable*),
03510                      straight_join ? join_tab_cmp_straight : join_tab_cmp);
03511   if (straight_join)
03512   {
03513     optimize_straight_join(join, join_tables);
03514   }
03515   else
03516   {
03517     if (search_depth == 0)
03518       /* Automatically determine a reasonable value for 'search_depth' */
03519       search_depth= determine_search_depth(join);
03520     if (greedy_search(join, join_tables, search_depth, prune_level))
03521       return true;
03522   }
03523 
03524   /*
03525     Store the cost of this query into a user variable
03526     Don't update last_query_cost for statements that are not "flat joins" :
03527     i.e. they have subqueries, unions or call stored procedures.
03528     TODO: calculate a correct cost for a query with subqueries and UNIONs.
03529   */
03530   if (join->session->lex().is_single_level_stmt())
03531     join->session->status_var.last_query_cost= join->best_read;
03532   return(false);
03533 }
03534 
03559 static void best_access_path(Join *join,
03560                              JoinTable *s,
03561                              Session *session,
03562                              table_map remaining_tables,
03563                              uint32_t idx,
03564                              double record_count,
03565                              double)
03566 {
03567   optimizer::KeyUse *best_key= NULL;
03568   uint32_t best_max_key_part= 0;
03569   bool found_constraint= 0;
03570   double best= DBL_MAX;
03571   double best_time= DBL_MAX;
03572   double records= DBL_MAX;
03573   table_map best_ref_depends_map= 0;
03574   double tmp;
03575   ha_rows rec;
03576 
03577   if (s->keyuse)
03578   {                                            /* Use key if possible */
03579     Table *table= s->table;
03580     optimizer::KeyUse *keyuse= NULL;
03581     optimizer::KeyUse *start_key= NULL;
03582     double best_records= DBL_MAX;
03583     uint32_t max_key_part=0;
03584 
03585     /* Test how we can use keys */
03586     rec= s->records/MATCHING_ROWS_IN_OTHER_TABLE;  // Assumed records/key
03587     for (keyuse= s->keyuse; keyuse->getTable() == table; )
03588     {
03589       key_part_map found_part= 0;
03590       table_map found_ref= 0;
03591       uint32_t key= keyuse->getKey();
03592       KeyInfo *keyinfo= table->key_info + key;
03593       /* Bitmap of keyparts where the ref access is over 'keypart=const': */
03594       key_part_map const_part= 0;
03595       /* The or-null keypart in ref-or-null access: */
03596       key_part_map ref_or_null_part= 0;
03597 
03598       /* Calculate how many key segments of the current key we can use */
03599       start_key= keyuse;
03600 
03601       do /* For each keypart */
03602       {
03603         uint32_t keypart= keyuse->getKeypart();
03604         table_map best_part_found_ref= 0;
03605         double best_prev_record_reads= DBL_MAX;
03606 
03607         do /* For each way to access the keypart */
03608         {
03609 
03610           /*
03611             if 1. expression doesn't refer to forward tables
03612                2. we won't get two ref-or-null's
03613           */
03614           if (! (remaining_tables & keyuse->getUsedTables()) &&
03615               ! (ref_or_null_part && (keyuse->getOptimizeFlags() &
03616                                       KEY_OPTIMIZE_REF_OR_NULL)))
03617           {
03618             found_part|= keyuse->getKeypartMap();
03619             if (! (keyuse->getUsedTables() & ~join->const_table_map))
03620               const_part|= keyuse->getKeypartMap();
03621 
03622             double tmp2= prev_record_reads(join, idx, (found_ref |
03623                                                        keyuse->getUsedTables()));
03624             if (tmp2 < best_prev_record_reads)
03625             {
03626               best_part_found_ref= keyuse->getUsedTables() & ~join->const_table_map;
03627               best_prev_record_reads= tmp2;
03628             }
03629             if (rec > keyuse->getTableRows())
03630               rec= keyuse->getTableRows();
03631       /*
03632         If there is one 'key_column IS NULL' expression, we can
03633         use this ref_or_null optimisation of this field
03634       */
03635             if (keyuse->getOptimizeFlags() & KEY_OPTIMIZE_REF_OR_NULL)
03636               ref_or_null_part|= keyuse->getKeypartMap();
03637           }
03638 
03639           keyuse++;
03640         } while (keyuse->getTable() == table && keyuse->getKey() == key &&
03641                  keyuse->getKeypart() == keypart);
03642         found_ref|= best_part_found_ref;
03643       } while (keyuse->getTable() == table && keyuse->getKey() == key);
03644 
03645       /*
03646         Assume that that each key matches a proportional part of table.
03647       */
03648       if (!found_part)
03649         continue;                               // Nothing usable found
03650 
03651       if (rec < MATCHING_ROWS_IN_OTHER_TABLE)
03652         rec= MATCHING_ROWS_IN_OTHER_TABLE;      // Fix for small tables
03653 
03654       {
03655         found_constraint= 1;
03656 
03657         /*
03658           Check if we found full key
03659         */
03660         if (found_part == PREV_BITS(uint,keyinfo->key_parts) &&
03661             !ref_or_null_part)
03662         {                                         /* use eq key */
03663           max_key_part= UINT32_MAX;
03664           if ((keyinfo->flags & (HA_NOSAME | HA_NULL_PART_KEY)) == HA_NOSAME)
03665           {
03666             tmp = prev_record_reads(join, idx, found_ref);
03667             records=1.0;
03668           }
03669           else
03670           {
03671             if (!found_ref)
03672             {                                     /* We found a const key */
03673               /*
03674                 ReuseRangeEstimateForRef-1:
03675                 We get here if we've found a ref(const) (c_i are constants):
03676                   "(keypart1=c1) AND ... AND (keypartN=cN)"   [ref_const_cond]
03677 
03678                 If range optimizer was able to construct a "range"
03679                 access on this index, then its condition "quick_cond" was
03680                 eqivalent to ref_const_cond (*), and we can re-use E(#rows)
03681                 from the range optimizer.
03682 
03683                 Proof of (*): By properties of range and ref optimizers
03684                 quick_cond will be equal or tighther than ref_const_cond.
03685                 ref_const_cond already covers "smallest" possible interval -
03686                 a singlepoint interval over all keyparts. Therefore,
03687                 quick_cond is equivalent to ref_const_cond (if it was an
03688                 empty interval we wouldn't have got here).
03689               */
03690               if (table->quick_keys.test(key))
03691                 records= (double) table->quick_rows[key];
03692               else
03693               {
03694                 /* quick_range couldn't use key! */
03695                 records= (double) s->records/rec;
03696               }
03697             }
03698             else
03699             {
03700               if (!(records=keyinfo->rec_per_key[keyinfo->key_parts-1]))
03701               {                                   /* Prefer longer keys */
03702                 records=
03703                   ((double) s->records / (double) rec *
03704                    (1.0 +
03705                     ((double) (table->getShare()->max_key_length-keyinfo->key_length) /
03706                      (double) table->getShare()->max_key_length)));
03707                 if (records < 2.0)
03708                   records=2.0;               /* Can't be as good as a unique */
03709               }
03710               /*
03711                 ReuseRangeEstimateForRef-2:  We get here if we could not reuse
03712                 E(#rows) from range optimizer. Make another try:
03713 
03714                 If range optimizer produced E(#rows) for a prefix of the ref
03715                 access we're considering, and that E(#rows) is lower then our
03716                 current estimate, make an adjustment. The criteria of when we
03717                 can make an adjustment is a special case of the criteria used
03718                 in ReuseRangeEstimateForRef-3.
03719               */
03720               if (table->quick_keys.test(key) &&
03721                   const_part & (1 << table->quick_key_parts[key]) &&
03722                   table->quick_n_ranges[key] == 1 &&
03723                   records > (double) table->quick_rows[key])
03724               {
03725                 records= (double) table->quick_rows[key];
03726               }
03727             }
03728             /* Limit the number of matched rows */
03729             tmp= records;
03730             set_if_smaller(tmp, (double) session->variables.max_seeks_for_key);
03731             if (table->covering_keys.test(key))
03732             {
03733               /* we can use only index tree */
03734               tmp= record_count * table->cursor->index_only_read_time(key, tmp);
03735             }
03736             else
03737               tmp= record_count * min(tmp,s->worst_seeks);
03738           }
03739         }
03740         else
03741         {
03742           /*
03743             Use as much key-parts as possible and a uniq key is better
03744             than a not unique key
03745             Set tmp to (previous record count) * (records / combination)
03746           */
03747           if ((found_part & 1) &&
03748               (!(table->index_flags(key) & HA_ONLY_WHOLE_INDEX) ||
03749                found_part == PREV_BITS(uint, keyinfo->key_parts)))
03750           {
03751             max_key_part= max_part_bit(found_part);
03752             /*
03753               ReuseRangeEstimateForRef-3:
03754               We're now considering a ref[or_null] access via
03755               (t.keypart1=e1 AND ... AND t.keypartK=eK) [ OR
03756               (same-as-above but with one cond replaced
03757                with "t.keypart_i IS NULL")]  (**)
03758 
03759               Try re-using E(#rows) from "range" optimizer:
03760               We can do so if "range" optimizer used the same intervals as
03761               in (**). The intervals used by range optimizer may be not
03762               available at this point (as "range" access might have choosen to
03763               create quick select over another index), so we can't compare
03764               them to (**). We'll make indirect judgements instead.
03765               The sufficient conditions for re-use are:
03766               (C1) All e_i in (**) are constants, i.e. found_ref==false. (if
03767                    this is not satisfied we have no way to know which ranges
03768                    will be actually scanned by 'ref' until we execute the
03769                    join)
03770               (C2) max #key parts in 'range' access == K == max_key_part (this
03771                    is apparently a necessary requirement)
03772 
03773               We also have a property that "range optimizer produces equal or
03774               tighter set of scan intervals than ref(const) optimizer". Each
03775               of the intervals in (**) are "tightest possible" intervals when
03776               one limits itself to using keyparts 1..K (which we do in #2).
03777               From here it follows that range access used either one, or
03778               both of the (I1) and (I2) intervals:
03779 
03780                (t.keypart1=c1 AND ... AND t.keypartK=eK)  (I1)
03781                (same-as-above but with one cond replaced
03782                 with "t.keypart_i IS NULL")               (I2)
03783 
03784               The remaining part is to exclude the situation where range
03785               optimizer used one interval while we're considering
03786               ref-or-null and looking for estimate for two intervals. This
03787               is done by last limitation:
03788 
03789               (C3) "range optimizer used (have ref_or_null?2:1) intervals"
03790             */
03791             if (table->quick_keys.test(key) && !found_ref &&          //(C1)
03792                 table->quick_key_parts[key] == max_key_part &&          //(C2)
03793                 table->quick_n_ranges[key] == 1+((ref_or_null_part)?1:0)) //(C3)
03794             {
03795               tmp= records= (double) table->quick_rows[key];
03796             }
03797             else
03798             {
03799               /* Check if we have statistic about the distribution */
03800               if ((records= keyinfo->rec_per_key[max_key_part-1]))
03801               {
03802                 /*
03803                   Fix for the case where the index statistics is too
03804                   optimistic: If
03805                   (1) We're considering ref(const) and there is quick select
03806                       on the same index,
03807                   (2) and that quick select uses more keyparts (i.e. it will
03808                       scan equal/smaller interval then this ref(const))
03809                   (3) and E(#rows) for quick select is higher then our
03810                       estimate,
03811                   Then
03812                     We'll use E(#rows) from quick select.
03813 
03814                   Q: Why do we choose to use 'ref'? Won't quick select be
03815                   cheaper in some cases ?
03816                   TODO: figure this out and adjust the plan choice if needed.
03817                 */
03818                 if (!found_ref && table->quick_keys.test(key) &&    // (1)
03819                     table->quick_key_parts[key] > max_key_part &&     // (2)
03820                     records < (double)table->quick_rows[key])         // (3)
03821                   records= (double)table->quick_rows[key];
03822 
03823                 tmp= records;
03824               }
03825               else
03826               {
03827                 /*
03828                   Assume that the first key part matches 1% of the cursor
03829                   and that the whole key matches 10 (duplicates) or 1
03830                   (unique) records.
03831                   Assume also that more key matches proportionally more
03832                   records
03833                   This gives the formula:
03834                   records = (x * (b-a) + a*c-b)/(c-1)
03835 
03836                   b = records matched by whole key
03837                   a = records matched by first key part (1% of all records?)
03838                   c = number of key parts in key
03839                   x = used key parts (1 <= x <= c)
03840                 */
03841                 double rec_per_key;
03842                 if (!(rec_per_key=(double)
03843                       keyinfo->rec_per_key[keyinfo->key_parts-1]))
03844                   rec_per_key=(double) s->records/rec+1;
03845 
03846                 if (!s->records)
03847                   tmp = 0;
03848                 else if (rec_per_key/(double) s->records >= 0.01)
03849                   tmp = rec_per_key;
03850                 else
03851                 {
03852                   double a=s->records*0.01;
03853                   if (keyinfo->key_parts > 1)
03854                     tmp= (max_key_part * (rec_per_key - a) +
03855                           a*keyinfo->key_parts - rec_per_key)/
03856                          (keyinfo->key_parts-1);
03857                   else
03858                     tmp= a;
03859                   set_if_bigger(tmp,1.0);
03860                 }
03861                 records = (uint32_t) tmp;
03862               }
03863 
03864               if (ref_or_null_part)
03865               {
03866                 /* We need to do two key searches to find key */
03867                 tmp *= 2.0;
03868                 records *= 2.0;
03869               }
03870 
03871               /*
03872                 ReuseRangeEstimateForRef-4:  We get here if we could not reuse
03873                 E(#rows) from range optimizer. Make another try:
03874 
03875                 If range optimizer produced E(#rows) for a prefix of the ref
03876                 access we're considering, and that E(#rows) is lower then our
03877                 current estimate, make the adjustment.
03878 
03879                 The decision whether we can re-use the estimate from the range
03880                 optimizer is the same as in ReuseRangeEstimateForRef-3,
03881                 applied to first table->quick_key_parts[key] key parts.
03882               */
03883               if (table->quick_keys.test(key) &&
03884                   table->quick_key_parts[key] <= max_key_part &&
03885                   const_part & (1 << table->quick_key_parts[key]) &&
03886                   table->quick_n_ranges[key] == 1 + ((ref_or_null_part &
03887                                                      const_part) ? 1 : 0) &&
03888                   records > (double) table->quick_rows[key])
03889               {
03890                 tmp= records= (double) table->quick_rows[key];
03891               }
03892             }
03893 
03894             /* Limit the number of matched rows */
03895             set_if_smaller(tmp, (double) session->variables.max_seeks_for_key);
03896             if (table->covering_keys.test(key))
03897             {
03898               /* we can use only index tree */
03899               tmp= record_count * table->cursor->index_only_read_time(key, tmp);
03900             }
03901             else
03902               tmp= record_count * min(tmp,s->worst_seeks);
03903           }
03904           else
03905             tmp= best_time;                    // Do nothing
03906         }
03907 
03908       }
03909       if (tmp < best_time - records/(double) TIME_FOR_COMPARE)
03910       {
03911         best_time= tmp + records/(double) TIME_FOR_COMPARE;
03912         best= tmp;
03913         best_records= records;
03914         best_key= start_key;
03915         best_max_key_part= max_key_part;
03916         best_ref_depends_map= found_ref;
03917       }
03918     }
03919     records= best_records;
03920   }
03921 
03922   /*
03923     Don't test table scan if it can't be better.
03924     Prefer key lookup if we would use the same key for scanning.
03925 
03926     Don't do a table scan on InnoDB tables, if we can read the used
03927     parts of the row from any of the used index.
03928     This is because table scans uses index and we would not win
03929     anything by using a table scan.
03930 
03931     A word for word translation of the below if-statement in sergefp's
03932     understanding: we check if we should use table scan if:
03933     (1) The found 'ref' access produces more records than a table scan
03934         (or index scan, or quick select), or 'ref' is more expensive than
03935         any of them.
03936     (2) This doesn't hold: the best way to perform table scan is to to perform
03937         'range' access using index IDX, and the best way to perform 'ref'
03938         access is to use the same index IDX, with the same or more key parts.
03939         (note: it is not clear how this rule is/should be extended to
03940         index_merge quick selects)
03941     (3) See above note about InnoDB.
03942     (4) NOT ("FORCE INDEX(...)" is used for table and there is 'ref' access
03943              path, but there is no quick select)
03944         If the condition in the above brackets holds, then the only possible
03945         "table scan" access method is ALL/index (there is no quick select).
03946         Since we have a 'ref' access path, and FORCE INDEX instructs us to
03947         choose it over ALL/index, there is no need to consider a full table
03948         scan.
03949   */
03950   if ((records >= s->found_records || best > s->read_time) &&            // (1)
03951       ! (s->quick && best_key && s->quick->index == best_key->getKey() &&      // (2)
03952         best_max_key_part >= s->table->quick_key_parts[best_key->getKey()]) &&// (2)
03953       ! ((s->table->cursor->getEngine()->check_flag(HTON_BIT_TABLE_SCAN_ON_INDEX)) &&   // (3)
03954         ! s->table->covering_keys.none() && best_key && !s->quick) && // (3)
03955       ! (s->table->force_index && best_key && !s->quick))                 // (4)
03956   {                                             // Check full join
03957     ha_rows rnd_records= s->found_records;
03958     /*
03959       If there is a filtering condition on the table (i.e. ref analyzer found
03960       at least one "table.keyXpartY= exprZ", where exprZ refers only to tables
03961       preceding this table in the join order we're now considering), then
03962       assume that 25% of the rows will be filtered out by this condition.
03963 
03964       This heuristic is supposed to force tables used in exprZ to be before
03965       this table in join order.
03966     */
03967     if (found_constraint)
03968       rnd_records-= rnd_records/4;
03969 
03970     /*
03971       If applicable, get a more accurate estimate. Don't use the two
03972       heuristics at once.
03973     */
03974     if (s->table->quick_condition_rows != s->found_records)
03975       rnd_records= s->table->quick_condition_rows;
03976 
03977     /*
03978       Range optimizer never proposes a RANGE if it isn't better
03979       than FULL: so if RANGE is present, it's always preferred to FULL.
03980       Here we estimate its cost.
03981     */
03982     if (s->quick)
03983     {
03984       /*
03985         For each record we:
03986         - read record range through 'quick'
03987         - skip rows which does not satisfy WHERE constraints
03988         TODO:
03989         We take into account possible use of join cache for ALL/index
03990         access (see first else-branch below), but we don't take it into
03991         account here for range/index_merge access. Find out why this is so.
03992       */
03993       tmp= record_count *
03994         (s->quick->read_time +
03995          (s->found_records - rnd_records)/(double) TIME_FOR_COMPARE);
03996     }
03997     else
03998     {
03999       /* Estimate cost of reading table. */
04000       tmp= s->table->cursor->scan_time();
04001       if (s->table->map & join->outer_join)     // Can't use join cache
04002       {
04003         /*
04004           For each record we have to:
04005           - read the whole table record
04006           - skip rows which does not satisfy join condition
04007         */
04008         tmp= record_count *
04009           (tmp +
04010            (s->records - rnd_records)/(double) TIME_FOR_COMPARE);
04011       }
04012       else
04013       {
04014         /* We read the table as many times as join buffer becomes full. */
04015         tmp*= (1.0 + floor((double) cache_record_length(join,idx) *
04016                            record_count /
04017                            (double) session->variables.join_buff_size));
04018         /*
04019             We don't make full cartesian product between rows in the scanned
04020            table and existing records because we skip all rows from the
04021            scanned table, which does not satisfy join condition when
04022            we read the table (see flush_cached_records for details). Here we
04023            take into account cost to read and skip these records.
04024         */
04025         tmp+= (s->records - rnd_records)/(double) TIME_FOR_COMPARE;
04026       }
04027     }
04028 
04029     /*
04030       We estimate the cost of evaluating WHERE clause for found records
04031       as record_count * rnd_records / TIME_FOR_COMPARE. This cost plus
04032       tmp give us total cost of using Table SCAN
04033     */
04034     if (best == DBL_MAX ||
04035         (tmp  + record_count/(double) TIME_FOR_COMPARE*rnd_records <
04036          best + record_count/(double) TIME_FOR_COMPARE*records))
04037     {
04038       /*
04039         If the table has a range (s->quick is set) make_join_select()
04040         will ensure that this will be used
04041       */
04042       best= tmp;
04043       records= rnd_records;
04044       best_key= 0;
04045       /* range/index_merge/ALL/index access method are "independent", so: */
04046       best_ref_depends_map= 0;
04047     }
04048   }
04049 
04050   /* Update the cost information for the current partial plan */
04051   optimizer::Position tmp_pos(records,
04052                               best,
04053                               s,
04054                               best_key,
04055                               best_ref_depends_map);
04056   join->setPosInPartialPlan(idx, tmp_pos);
04057 
04058   if (!best_key &&
04059       idx == join->const_tables &&
04060       s->table == join->sort_by_table &&
04061       join->unit->select_limit_cnt >= records)
04062     join->sort_by_table= (Table*) 1;  // Must use temporary table
04063 
04064   return;
04065 }
04066 
04089 static void optimize_straight_join(Join *join, table_map join_tables)
04090 {
04091   JoinTable *s;
04092   optimizer::Position partial_pos;
04093   uint32_t idx= join->const_tables;
04094   double    record_count= 1.0;
04095   double    read_time=    0.0;
04096 
04097   for (JoinTable **pos= join->best_ref + idx ; (s= *pos) ; pos++)
04098   {
04099     /* Find the best access method from 's' to the current partial plan */
04100     best_access_path(join, s, join->session, join_tables, idx,
04101                      record_count, read_time);
04102     /* compute the cost of the new plan extended with 's' */
04103     partial_pos= join->getPosFromPartialPlan(idx);
04104     record_count*= partial_pos.getFanout();
04105     read_time+=    partial_pos.getCost();
04106     join_tables&= ~(s->table->map);
04107     ++idx;
04108   }
04109 
04110   read_time+= record_count / (double) TIME_FOR_COMPARE;
04111   partial_pos= join->getPosFromPartialPlan(join->const_tables);
04112   if (join->sort_by_table &&
04113       partial_pos.hasTableForSorting(join->sort_by_table))
04114     read_time+= record_count;  // We have to make a temp table
04115   join->copyPartialPlanIntoOptimalPlan(idx);
04116   join->best_read= read_time;
04117 }
04118 
04199 static bool greedy_search(Join      *join,
04200               table_map remaining_tables,
04201               uint32_t      search_depth,
04202               uint32_t      prune_level)
04203 {
04204   double    record_count= 1.0;
04205   double    read_time=    0.0;
04206   uint32_t      idx= join->const_tables; // index into 'join->best_ref'
04207   uint32_t      best_idx;
04208   uint32_t      size_remain;    // cardinality of remaining_tables
04209   optimizer::Position best_pos;
04210   JoinTable  *best_table; // the next plan node to be added to the curr QEP
04211 
04212   /* number of tables that remain to be optimized */
04213   size_remain= internal::my_count_bits(remaining_tables);
04214 
04215   do {
04216     /* Find the extension of the current QEP with the lowest cost */
04217     join->best_read= DBL_MAX;
04218     if (best_extension_by_limited_search(join, remaining_tables, idx, record_count,
04219                                          read_time, search_depth, prune_level))
04220       return(true);
04221 
04222     if (size_remain <= search_depth)
04223     {
04224       /*
04225         'join->best_positions' contains a complete optimal extension of the
04226         current partial QEP.
04227       */
04228       return(false);
04229     }
04230 
04231     /* select the first table in the optimal extension as most promising */
04232     best_pos= join->getPosFromOptimalPlan(idx);
04233     best_table= best_pos.getJoinTable();
04234     /*
04235       Each subsequent loop of 'best_extension_by_limited_search' uses
04236       'join->positions' for cost estimates, therefore we have to update its
04237       value.
04238     */
04239     join->setPosInPartialPlan(idx, best_pos);
04240 
04241     /*
04242       We need to make best_extension_by_limited_search aware of the fact
04243       that it's not starting from top level, but from a rather specific
04244       position in the list of nested joins.
04245     */
04246     check_interleaving_with_nj (best_table);
04247     
04248       
04249 
04250     /* find the position of 'best_table' in 'join->best_ref' */
04251     best_idx= idx;
04252     JoinTable *pos= join->best_ref[best_idx];
04253     while (pos && best_table != pos)
04254       pos= join->best_ref[++best_idx];
04255     assert((pos != NULL)); // should always find 'best_table'
04256     /* move 'best_table' at the first free position in the array of joins */
04257     std::swap(join->best_ref[idx], join->best_ref[best_idx]);
04258 
04259     /* compute the cost of the new plan extended with 'best_table' */
04260     optimizer::Position partial_pos= join->getPosFromPartialPlan(idx);
04261     record_count*= partial_pos.getFanout();
04262     read_time+=    partial_pos.getCost();
04263 
04264     remaining_tables&= ~(best_table->table->map);
04265     --size_remain;
04266     ++idx;
04267   } while (true);
04268 }
04269 
04270 
04387 static bool best_extension_by_limited_search(Join *join,
04388                                              table_map remaining_tables,
04389                                              uint32_t idx,
04390                                              double record_count,
04391                                              double read_time,
04392                                              uint32_t search_depth,
04393                                              uint32_t prune_level)
04394 {
04395   Session *session= join->session;
04396   if (session->getKilled())  // Abort
04397     return(true);
04398 
04399   /*
04400      'join' is a partial plan with lower cost than the best plan so far,
04401      so continue expanding it further with the tables in 'remaining_tables'.
04402   */
04403   JoinTable *s;
04404   double best_record_count= DBL_MAX;
04405   double best_read_time=    DBL_MAX;
04406   optimizer::Position partial_pos;
04407 
04408   for (JoinTable **pos= join->best_ref + idx ; (s= *pos) ; pos++)
04409   {
04410     table_map real_table_bit= s->table->map;
04411     if ((remaining_tables & real_table_bit) &&
04412         ! (remaining_tables & s->dependent) &&
04413         (! idx || ! check_interleaving_with_nj(s)))
04414     {
04415       double current_record_count, current_read_time;
04416 
04417       /*
04418         psergey-insideout-todo:
04419           when best_access_path() detects it could do an InsideOut scan or
04420           some other scan, have it return an insideout scan and a flag that
04421           requests to "fork" this loop iteration. (Q: how does that behave
04422           when the depth is insufficient??)
04423       */
04424       /* Find the best access method from 's' to the current partial plan */
04425       best_access_path(join, s, session, remaining_tables, idx,
04426                        record_count, read_time);
04427       /* Compute the cost of extending the plan with 's' */
04428       partial_pos= join->getPosFromPartialPlan(idx);
04429       current_record_count= record_count * partial_pos.getFanout();
04430       current_read_time=    read_time + partial_pos.getCost();
04431 
04432       /* Expand only partial plans with lower cost than the best QEP so far */
04433       if ((current_read_time +
04434            current_record_count / (double) TIME_FOR_COMPARE) >= join->best_read)
04435       {
04436         restore_prev_nj_state(s);
04437         continue;
04438       }
04439 
04440       /*
04441         Prune some less promising partial plans. This heuristic may miss
04442         the optimal QEPs, thus it results in a non-exhaustive search.
04443       */
04444       if (prune_level == 1)
04445       {
04446         if (best_record_count > current_record_count ||
04447             best_read_time > current_read_time ||
04448             (idx == join->const_tables && s->table == join->sort_by_table)) // 's' is the first table in the QEP
04449         {
04450           if (best_record_count >= current_record_count &&
04451               best_read_time >= current_read_time &&
04452               /* TODO: What is the reasoning behind this condition? */
04453               (! (s->key_dependent & remaining_tables) ||
04454                partial_pos.isConstTable()))
04455           {
04456             best_record_count= current_record_count;
04457             best_read_time=    current_read_time;
04458           }
04459         }
04460         else
04461         {
04462           restore_prev_nj_state(s);
04463           continue;
04464         }
04465       }
04466 
04467       if ( (search_depth > 1) && (remaining_tables & ~real_table_bit) )
04468       { /* Recursively expand the current partial plan */
04469         std::swap(join->best_ref[idx], *pos);
04470         if (best_extension_by_limited_search(join,
04471                                              remaining_tables & ~real_table_bit,
04472                                              idx + 1,
04473                                              current_record_count,
04474                                              current_read_time,
04475                                              search_depth - 1,
04476                                              prune_level))
04477           return(true);
04478         std::swap(join->best_ref[idx], *pos);
04479       }
04480       else
04481       { /*
04482           'join' is either the best partial QEP with 'search_depth' relations,
04483           or the best complete QEP so far, whichever is smaller.
04484         */
04485         partial_pos= join->getPosFromPartialPlan(join->const_tables);
04486         current_read_time+= current_record_count / (double) TIME_FOR_COMPARE;
04487         if (join->sort_by_table &&
04488             partial_pos.hasTableForSorting(join->sort_by_table))
04489           /* We have to make a temp table */
04490           current_read_time+= current_record_count;
04491         if ((search_depth == 1) || (current_read_time < join->best_read))
04492         {
04493           join->copyPartialPlanIntoOptimalPlan(idx + 1);
04494           join->best_read= current_read_time - 0.001;
04495         }
04496       }
04497       restore_prev_nj_state(s);
04498     }
04499   }
04500   return(false);
04501 }
04502 
04534 static uint32_t determine_search_depth(Join *join)
04535 {
04536   uint32_t table_count=  join->tables - join->const_tables;
04537   uint32_t search_depth;
04538   /* TODO: this value should be determined dynamically, based on statistics: */
04539   uint32_t max_tables_for_exhaustive_opt= 7;
04540 
04541   if (table_count <= max_tables_for_exhaustive_opt)
04542     search_depth= table_count+1; // use exhaustive for small number of tables
04543   else
04544     /*
04545       TODO: this value could be determined by some mapping of the form:
04546       depth : table_count -> [max_tables_for_exhaustive_opt..MAX_EXHAUSTIVE]
04547     */
04548     search_depth= max_tables_for_exhaustive_opt; // use greedy search
04549 
04550   return search_depth;
04551 }
04552 
04553 static bool make_simple_join(Join *join,Table *tmp_table)
04554 {
04555   Table **tableptr;
04556   JoinTable *join_tab;
04557 
04558   /*
04559     Reuse Table * and JoinTable if already allocated by a previous call
04560     to this function through Join::exec (may happen for sub-queries).
04561   */
04562   if (!join->table_reexec)
04563   {
04564     if (!(join->table_reexec= (Table**) join->session->getMemRoot()->allocate(sizeof(Table*))))
04565       return(true);
04566     if (join->tmp_join)
04567       join->tmp_join->table_reexec= join->table_reexec;
04568   }
04569   if (!join->join_tab_reexec)
04570   {
04571     if (!(join->join_tab_reexec=
04572           (JoinTable*) join->session->getMemRoot()->allocate(sizeof(JoinTable))))
04573       return(true);
04574     new (join->join_tab_reexec) JoinTable();
04575     if (join->tmp_join)
04576       join->tmp_join->join_tab_reexec= join->join_tab_reexec;
04577   }
04578   tableptr= join->table_reexec;
04579   join_tab= join->join_tab_reexec;
04580 
04581   join->join_tab=join_tab;
04582   join->table=tableptr; tableptr[0]=tmp_table;
04583   join->tables=1;
04584   join->const_tables=0;
04585   join->const_table_map=0;
04586   join->tmp_table_param.field_count= join->tmp_table_param.sum_func_count=
04587     join->tmp_table_param.func_count=0;
04588   join->tmp_table_param.copy_field=join->tmp_table_param.copy_field_end=0;
04589   join->first_record=join->sort_and_group=0;
04590   join->send_records=(ha_rows) 0;
04591   join->group=0;
04592   join->row_limit=join->unit->select_limit_cnt;
04593   join->do_send_rows = (join->row_limit) ? 1 : 0;
04594 
04595   join_tab->table=tmp_table;
04596   join_tab->select=0;
04597   join_tab->select_cond=0;
04598   join_tab->quick=0;
04599   join_tab->type= AM_ALL;     /* Map through all records */
04600   join_tab->keys.set();                     /* test everything in quick */
04601   join_tab->info=0;
04602   join_tab->on_expr_ref=0;
04603   join_tab->last_inner= 0;
04604   join_tab->first_unmatched= 0;
04605   join_tab->ref.key = -1;
04606   join_tab->not_used_in_distinct=0;
04607   join_tab->read_first_record= join_init_read_record;
04608   join_tab->join=join;
04609   join_tab->ref.key_parts= 0;
04610   join_tab->read_record.init();
04611   tmp_table->status=0;
04612   tmp_table->null_row=0;
04613 
04614   return false;
04615 }
04616 
04658 static void make_outerjoin_info(Join *join)
04659 {
04660   for (uint32_t i=join->const_tables ; i < join->tables ; i++)
04661   {
04662     JoinTable *tab=join->join_tab+i;
04663     Table *table=tab->table;
04664     TableList *tbl= table->pos_in_table_list;
04665     TableList *embedding= tbl->getEmbedding();
04666 
04667     if (tbl->outer_join)
04668     {
04669       /*
04670         Table tab is the only one inner table for outer join.
04671         (Like table t4 for the table reference t3 LEFT JOIN t4 ON t3.a=t4.a
04672         is in the query above.)
04673       */
04674       tab->last_inner= tab->first_inner= tab;
04675       tab->on_expr_ref= &tbl->on_expr;
04676       tab->cond_equal= tbl->cond_equal;
04677       if (embedding)
04678         tab->first_upper= embedding->getNestedJoin()->first_nested;
04679     }
04680     for ( ; embedding ; embedding= embedding->getEmbedding())
04681     {
04682       /* Ignore sj-nests: */
04683       if (!embedding->on_expr)
04684         continue;
04685       NestedJoin *nested_join= embedding->getNestedJoin();
04686       if (!nested_join->counter_)
04687       {
04688         /*
04689           Table tab is the first inner table for nested_join.
04690           Save reference to it in the nested join structure.
04691         */
04692         nested_join->first_nested= tab;
04693         tab->on_expr_ref= &embedding->on_expr;
04694         tab->cond_equal= tbl->cond_equal;
04695         if (embedding->getEmbedding())
04696           tab->first_upper= embedding->getEmbedding()->getNestedJoin()->first_nested;
04697       }
04698       if (!tab->first_inner)
04699         tab->first_inner= nested_join->first_nested;
04700       if (++nested_join->counter_ < nested_join->join_list.size())
04701         break;
04702       /* Table tab is the last inner table for nested join. */
04703       nested_join->first_nested->last_inner= tab;
04704     }
04705   }
04706   return;
04707 }
04708 
04709 static bool make_join_select(Join *join,
04710                              optimizer::SqlSelect *select,
04711                              COND *cond)
04712 {
04713   Session *session= join->session;
04714   optimizer::Position cur_pos;
04715   if (select)
04716   {
04717     add_not_null_conds(join);
04718     table_map used_tables;
04719     if (cond)                /* Because of QUICK_GROUP_MIN_MAX_SELECT */
04720     {                        /* there may be a select without a cond. */
04721       if (join->tables > 1)
04722         cond->update_used_tables();   // Tablenr may have changed
04723       if (join->const_tables == join->tables &&
04724           session->lex().current_select->master_unit() ==
04725           &session->lex().unit)   // not upper level SELECT
04726         join->const_table_map|=RAND_TABLE_BIT;
04727       {           // Check const tables
04728         COND *const_cond=
04729           make_cond_for_table(cond,
04730               join->const_table_map,
04731               0, 1);
04732         for (JoinTable *tab= join->join_tab+join->const_tables;
04733             tab < join->join_tab+join->tables ; tab++)
04734         {
04735           if (*tab->on_expr_ref)
04736           {
04737             JoinTable *cond_tab= tab->first_inner;
04738             COND *tmp= make_cond_for_table(*tab->on_expr_ref,
04739                 join->const_table_map,
04740                 (  table_map) 0, 0);
04741             if (!tmp)
04742               continue;
04743             tmp= new Item_func_trig_cond(tmp, &cond_tab->not_null_compl);
04744             if (! tmp)
04745               return 1;
04746             tmp->quick_fix_field();
04747             cond_tab->select_cond= !cond_tab->select_cond ? tmp :
04748               new Item_cond_and(cond_tab->select_cond,
04749                   tmp);
04750             if (! cond_tab->select_cond)
04751               return 1;
04752             cond_tab->select_cond->quick_fix_field();
04753           }
04754         }
04755         if (const_cond && ! const_cond->val_int())
04756         {
04757           return 1;  // Impossible const condition
04758         }
04759       }
04760     }
04761     used_tables=((select->const_tables=join->const_table_map) |
04762         OUTER_REF_TABLE_BIT | RAND_TABLE_BIT);
04763     for (uint32_t i=join->const_tables ; i < join->tables ; i++)
04764     {
04765       JoinTable *tab=join->join_tab+i;
04766       /*
04767          first_inner is the X in queries like:
04768          SELECT * FROM t1 LEFT OUTER JOIN (t2 JOIN t3) ON X
04769        */
04770       JoinTable *first_inner_tab= tab->first_inner;
04771       table_map current_map= tab->table->map;
04772       bool use_quick_range=0;
04773       COND *tmp;
04774 
04775       /*
04776          Following force including random expression in last table condition.
04777          It solve problem with select like SELECT * FROM t1 WHERE rand() > 0.5
04778        */
04779       if (i == join->tables-1)
04780         current_map|= OUTER_REF_TABLE_BIT | RAND_TABLE_BIT;
04781       used_tables|=current_map;
04782 
04783       if (tab->type == AM_REF && tab->quick &&
04784           (uint32_t) tab->ref.key == tab->quick->index &&
04785           tab->ref.key_length < tab->quick->max_used_key_length)
04786       {
04787         /* Range uses longer key;  Use this instead of ref on key */
04788         tab->type= AM_ALL;
04789         use_quick_range= 1;
04790         tab->use_quick= 1;
04791         tab->ref.key= -1;
04792         tab->ref.key_parts= 0;    // Don't use ref key.
04793         cur_pos= join->getPosFromOptimalPlan(i);
04794         cur_pos.setFanout(tab->quick->records);
04795         /*
04796            We will use join cache here : prevent sorting of the first
04797            table only and sort at the end.
04798          */
04799         if (i != join->const_tables && join->tables > join->const_tables + 1)
04800           join->full_join= 1;
04801       }
04802 
04803       if (join->full_join and not session->lex().current_select->is_cross and not cond)
04804       {
04805         my_error(ER_CARTESIAN_JOIN_ATTEMPTED, MYF(0));
04806         return 1;
04807       }
04808 
04809       tmp= NULL;
04810       if (cond)
04811         tmp= make_cond_for_table(cond,used_tables,current_map, 0);
04812       if (cond && !tmp && tab->quick)
04813       {           // Outer join
04814         if (tab->type != AM_ALL)
04815         {
04816           /*
04817              Don't use the quick method
04818              We come here in the case where we have 'key=constant' and
04819              the test is removed by make_cond_for_table()
04820            */
04821           delete tab->quick;
04822           tab->quick= 0;
04823         }
04824         else
04825         {
04826           /*
04827              Hack to handle the case where we only refer to a table
04828              in the ON part of an OUTER JOIN. In this case we want the code
04829              below to check if we should use 'quick' instead.
04830            */
04831           tmp= new Item_int((int64_t) 1,1); // Always true
04832         }
04833 
04834       }
04835       if (tmp || !cond || tab->type == AM_REF || tab->type == AM_REF_OR_NULL ||
04836           tab->type == AM_EQ_REF)
04837       {
04838         optimizer::SqlSelect *sel= tab->select= ((optimizer::SqlSelect*)
04839             session->getMemRoot()->duplicate((unsigned char*) select,
04840               sizeof(*select)));
04841         if (! sel)
04842           return 1;     // End of memory
04843         /*
04844            If tab is an inner table of an outer join operation,
04845            add a match guard to the pushed down predicate.
04846            The guard will turn the predicate on only after
04847            the first match for outer tables is encountered.
04848          */
04849         if (cond && tmp)
04850         {
04851           /*
04852              Because of QUICK_GROUP_MIN_MAX_SELECT there may be a select without
04853              a cond, so neutralize the hack above.
04854            */
04855           if (! (tmp= add_found_match_trig_cond(first_inner_tab, tmp, 0)))
04856             return 1;
04857           tab->select_cond=sel->cond=tmp;
04858         }
04859         else
04860           tab->select_cond= sel->cond= NULL;
04861 
04862         sel->head=tab->table;
04863         if (tab->quick)
04864         {
04865           /* Use quick key read if it's a constant and it's not used
04866              with key reading */
04867           if (tab->needed_reg.none() && tab->type != AM_EQ_REF
04868               && (tab->type != AM_REF || (uint32_t) tab->ref.key == tab->quick->index))
04869           {
04870             sel->quick=tab->quick;    // Use value from get_quick_...
04871             sel->quick_keys.reset();
04872             sel->needed_reg.reset();
04873           }
04874           else
04875           {
04876             delete tab->quick;
04877           }
04878           tab->quick= 0;
04879         }
04880         uint32_t ref_key= static_cast<uint32_t>(sel->head->reginfo.join_tab->ref.key + 1);
04881         if (i == join->const_tables && ref_key)
04882         {
04883           if (tab->const_keys.any() &&
04884               tab->table->reginfo.impossible_range)
04885             return 1;
04886         }
04887         else if (tab->type == AM_ALL && ! use_quick_range)
04888         {
04889           if (tab->const_keys.any() &&
04890               tab->table->reginfo.impossible_range)
04891             return 1;       // Impossible range
04892           /*
04893              We plan to scan all rows.
04894              Check again if we should use an index.
04895              We could have used an column from a previous table in
04896              the index if we are using limit and this is the first table
04897            */
04898 
04899           cur_pos= join->getPosFromOptimalPlan(i);
04900           if ((cond && (! ((tab->keys & tab->const_keys) == tab->keys) && i > 0)) ||
04901               (! tab->const_keys.none() && (i == join->const_tables) &&
04902               (join->unit->select_limit_cnt < cur_pos.getFanout()) && ((join->select_options & OPTION_FOUND_ROWS) == false)))
04903           {
04904             /* Join with outer join condition */
04905             COND *orig_cond= sel->cond;
04906             sel->cond= and_conds(sel->cond, *tab->on_expr_ref);
04907 
04908             /*
04909                We can't call sel->cond->fix_fields,
04910                as it will break tab->on_expr if it's AND condition
04911                (fix_fields currently removes extra AND/OR levels).
04912                Yet attributes of the just built condition are not needed.
04913                Thus we call sel->cond->quick_fix_field for safety.
04914              */
04915             if (sel->cond && ! sel->cond->fixed)
04916               sel->cond->quick_fix_field();
04917 
04918             if (sel->test_quick_select(session, tab->keys,
04919                   used_tables & ~ current_map,
04920                   (join->select_options &
04921                    OPTION_FOUND_ROWS ?
04922                    HA_POS_ERROR :
04923                    join->unit->select_limit_cnt), 0,
04924                   false) < 0)
04925             {
04926               /*
04927                  Before reporting "Impossible WHERE" for the whole query
04928                  we have to check isn't it only "impossible ON" instead
04929                */
04930               sel->cond=orig_cond;
04931               if (! *tab->on_expr_ref ||
04932                   sel->test_quick_select(session, tab->keys,
04933                     used_tables & ~ current_map,
04934                     (join->select_options &
04935                      OPTION_FOUND_ROWS ?
04936                      HA_POS_ERROR :
04937                      join->unit->select_limit_cnt),0,
04938                     false) < 0)
04939                 return 1;     // Impossible WHERE
04940             }
04941             else
04942               sel->cond=orig_cond;
04943 
04944             /* Fix for EXPLAIN */
04945             if (sel->quick)
04946             {
04947               cur_pos= join->getPosFromOptimalPlan(i);
04948               cur_pos.setFanout(static_cast<double>(sel->quick->records));
04949             }
04950           }
04951           else
04952           {
04953             sel->needed_reg= tab->needed_reg;
04954             sel->quick_keys.reset();
04955           }
04956           if (!((tab->checked_keys & sel->quick_keys) == sel->quick_keys) ||
04957               !((tab->checked_keys & sel->needed_reg) == sel->needed_reg))
04958           {
04959             tab->keys= sel->quick_keys;
04960             tab->keys|= sel->needed_reg;
04961             tab->use_quick= (!sel->needed_reg.none() &&
04962                 (select->quick_keys.none() ||
04963                  (select->quick &&
04964                   (select->quick->records >= 100L)))) ?
04965               2 : 1;
04966             sel->read_tables= used_tables & ~current_map;
04967           }
04968           if (i != join->const_tables && tab->use_quick != 2)
04969           {         /* Read with cache */
04970             if (cond &&
04971                 (tmp=make_cond_for_table(cond,
04972                                          join->const_table_map |
04973                                          current_map,
04974                                          current_map, 0)))
04975             {
04976               tab->cache.select= (optimizer::SqlSelect*)
04977                 session->getMemRoot()->duplicate((unsigned char*) sel, sizeof(optimizer::SqlSelect));
04978               tab->cache.select->cond= tmp;
04979               tab->cache.select->read_tables= join->const_table_map;
04980             }
04981           }
04982         }
04983       }
04984 
04985       /*
04986          Push down conditions from all on expressions.
04987          Each of these conditions are guarded by a variable
04988          that turns if off just before null complemented row for
04989          outer joins is formed. Thus, the condition from an
04990          'on expression' are guaranteed not to be checked for
04991          the null complemented row.
04992        */
04993 
04994       /* First push down constant conditions from on expressions */
04995       for (JoinTable *join_tab= join->join_tab+join->const_tables;
04996           join_tab < join->join_tab+join->tables ; join_tab++)
04997       {
04998         if (*join_tab->on_expr_ref)
04999         {
05000           JoinTable *cond_tab= join_tab->first_inner;
05001           tmp= make_cond_for_table(*join_tab->on_expr_ref,
05002               join->const_table_map,
05003               (table_map) 0, 0);
05004           if (!tmp)
05005             continue;
05006           tmp= new Item_func_trig_cond(tmp, &cond_tab->not_null_compl);
05007           if (! tmp)
05008             return 1;
05009           tmp->quick_fix_field();
05010           cond_tab->select_cond= !cond_tab->select_cond ? tmp :
05011             new Item_cond_and(cond_tab->select_cond,tmp);
05012           if (! cond_tab->select_cond)
05013             return 1;
05014           cond_tab->select_cond->quick_fix_field();
05015         }
05016       }
05017 
05018       /* Push down non-constant conditions from on expressions */
05019       JoinTable *last_tab= tab;
05020       while (first_inner_tab && first_inner_tab->last_inner == last_tab)
05021       {
05022         /*
05023            Table tab is the last inner table of an outer join.
05024            An on expression is always attached to it.
05025          */
05026         COND *on_expr= *first_inner_tab->on_expr_ref;
05027 
05028         table_map used_tables2= (join->const_table_map |
05029             OUTER_REF_TABLE_BIT | RAND_TABLE_BIT);
05030         for (tab= join->join_tab+join->const_tables; tab <= last_tab ; tab++)
05031         {
05032           current_map= tab->table->map;
05033           used_tables2|= current_map;
05034           COND *tmp_cond= make_cond_for_table(on_expr, used_tables2,
05035               current_map, 0);
05036           if (tmp_cond)
05037           {
05038             JoinTable *cond_tab= tab < first_inner_tab ? first_inner_tab : tab;
05039             /*
05040                First add the guards for match variables of
05041                all embedding outer join operations.
05042              */
05043             if (!(tmp_cond= add_found_match_trig_cond(cond_tab->first_inner,
05044                                                       tmp_cond,
05045                                                       first_inner_tab)))
05046               return 1;
05047             /*
05048                Now add the guard turning the predicate off for
05049                the null complemented row.
05050              */
05051             tmp_cond= new Item_func_trig_cond(tmp_cond,
05052                 &first_inner_tab->
05053                 not_null_compl);
05054             if (tmp_cond)
05055               tmp_cond->quick_fix_field();
05056             /* Add the predicate to other pushed down predicates */
05057             cond_tab->select_cond= !cond_tab->select_cond ? tmp_cond :
05058               new Item_cond_and(cond_tab->select_cond,
05059                                 tmp_cond);
05060             if (! cond_tab->select_cond)
05061               return 1;
05062             cond_tab->select_cond->quick_fix_field();
05063           }
05064         }
05065         first_inner_tab= first_inner_tab->first_upper;
05066       }
05067     }
05068   }
05069   return(0);
05070 }
05071 
05072 /*
05073   Plan refinement stage: do various set ups for the executioner
05074 
05075   SYNOPSIS
05076     make_join_readinfo()
05077       join           Join being processed
05078       options        Join's options (checking for SELECT_DESCRIBE,
05079                      SELECT_NO_JOIN_CACHE)
05080       no_jbuf_after  Don't use join buffering after table with this number.
05081 
05082   DESCRIPTION
05083     Plan refinement stage: do various set ups for the executioner
05084       - set up use of join buffering
05085       - push index conditions
05086       - increment counters
05087       - etc
05088 
05089   RETURN
05090     false - OK
05091     true  - Out of memory
05092 */
05093 static bool make_join_readinfo(Join *join)
05094 {
05095   bool sorted= true;
05096 
05097   for (uint32_t i= join->const_tables ; i < join->tables ; i++)
05098   {
05099     JoinTable *tab=join->join_tab+i;
05100     Table *table=tab->table;
05101     tab->read_record.table= table;
05102     tab->read_record.cursor= table->cursor;
05103     tab->next_select=sub_select;    /* normal select */
05104     /*
05105       TODO: don't always instruct first table's ref/range access method to
05106       produce sorted output.
05107     */
05108     tab->sorted= sorted;
05109     sorted= false; // only first must be sorted
05110 
05111     if (tab->insideout_match_tab)
05112     {
05113       if (! (tab->insideout_buf= (unsigned char*) join->session->getMemRoot()->allocate(tab->table->key_info
05114                                                                        [tab->index].
05115                                                                        key_length)))
05116         return true;
05117     }
05118 
05119     optimizer::AccessMethodFactory &factory= optimizer::AccessMethodFactory::singleton();
05120     boost::shared_ptr<optimizer::AccessMethod> access_method(factory.createAccessMethod(tab->type));
05121 
05122     if (! access_method)
05123     {
05129       abort();
05130     }
05131 
05132     access_method->getStats(table, tab);
05133   }
05134 
05135   join->join_tab[join->tables-1].next_select= NULL; /* Set by do_select */
05136 
05137   return false;
05138 }
05139 
05141 static void update_depend_map(Join *join)
05142 {
05143   JoinTable *join_tab=join->join_tab, *end=join_tab+join->tables;
05144 
05145   for (; join_tab != end ; join_tab++)
05146   {
05147     table_reference_st *ref= &join_tab->ref;
05148     table_map depend_map= 0;
05149     Item **item=ref->items;
05150     uint32_t i;
05151     for (i=0 ; i < ref->key_parts ; i++,item++)
05152       depend_map|=(*item)->used_tables();
05153     ref->depend_map=depend_map & ~OUTER_REF_TABLE_BIT;
05154     depend_map&= ~OUTER_REF_TABLE_BIT;
05155     for (JoinTable **tab=join->map2table; depend_map; tab++,depend_map>>=1 )
05156     {
05157       if (depend_map & 1)
05158         ref->depend_map|=(*tab)->ref.depend_map;
05159     }
05160   }
05161 }
05162 
05164 static void update_depend_map(Join *join, Order *order)
05165 {
05166   for (; order ; order=order->next)
05167   {
05168     table_map depend_map;
05169     order->item[0]->update_used_tables();
05170     order->depend_map=depend_map=order->item[0]->used_tables();
05171     // Not item_sum(), RAND() and no reference to table outside of sub select
05172     if (!(order->depend_map & (OUTER_REF_TABLE_BIT | RAND_TABLE_BIT))
05173         && !order->item[0]->with_sum_func)
05174     {
05175       for (JoinTable **tab=join->map2table; depend_map; tab++, depend_map>>=1)
05176       {
05177         if (depend_map & 1)
05178           order->depend_map|=(*tab)->ref.depend_map;
05179       }
05180     }
05181   }
05182 }
05183 
05202 static Order *remove_constants(Join *join,Order *first_order, COND *cond, bool change_list, bool *simple_order)
05203 {
05204   if (join->tables == join->const_tables)
05205     return change_list ? 0 : first_order;   // No need to sort
05206 
05207   Order *order,**prev_ptr;
05208   table_map first_table= join->join_tab[join->const_tables].table->map;
05209   table_map not_const_tables= ~join->const_table_map;
05210   table_map ref;
05211 
05212   prev_ptr= &first_order;
05213   *simple_order= *join->join_tab[join->const_tables].on_expr_ref ? 0 : 1;
05214 
05215   /* NOTE: A variable of not_const_tables ^ first_table; breaks gcc 2.7 */
05216 
05217   update_depend_map(join, first_order);
05218   for (order=first_order; order ; order=order->next)
05219   {
05220     table_map order_tables=order->item[0]->used_tables();
05221     if (order->item[0]->with_sum_func)
05222       *simple_order=0;        // Must do a temp table to sort
05223     else if (!(order_tables & not_const_tables))
05224     {
05225       if (order->item[0]->with_subselect)
05226         order->item[0]->val_str(&order->item[0]->str_value);
05227       continue;         // skip const item
05228     }
05229     else
05230     {
05231       if (order_tables & (RAND_TABLE_BIT | OUTER_REF_TABLE_BIT))
05232         *simple_order=0;
05233       else
05234       {
05235         Item *comp_item=0;
05236         if (cond && const_expression_in_where(cond,order->item[0], &comp_item))
05237         {
05238           continue;
05239         }
05240         if ((ref=order_tables & (not_const_tables ^ first_table)))
05241         {
05242           if (!(order_tables & first_table) &&
05243                     only_eq_ref_tables(join,first_order, ref))
05244           {
05245             continue;
05246           }
05247           *simple_order=0;      // Must do a temp table to sort
05248         }
05249       }
05250     }
05251     if (change_list)
05252       *prev_ptr= order;       // use this entry
05253     prev_ptr= &order->next;
05254   }
05255   if (change_list)
05256     *prev_ptr=0;
05257   if (prev_ptr == &first_order)     // Nothing to sort/group
05258     *simple_order=1;
05259   return(first_order);
05260 }
05261 
05262 static int return_zero_rows(Join *join,
05263                             select_result *result,
05264                             TableList *tables,
05265                             List<Item> &fields,
05266                             bool send_row,
05267                             uint64_t select_options,
05268                             const char *info,
05269                             Item *having)
05270 {
05271   if (select_options & SELECT_DESCRIBE)
05272   {
05273     optimizer::ExplainPlan planner(join,
05274                                    false,
05275                                    false,
05276                                    false,
05277                                    info);
05278     planner.printPlan();
05279     return 0;
05280   }
05281 
05282   join->join_free();
05283 
05284   if (send_row)
05285   {
05286     for (TableList *table= tables; table; table= table->next_leaf)
05287       table->table->mark_as_null_row();   // All fields are NULL
05288     if (having && having->val_int() == 0)
05289       send_row=0;
05290   }
05291   if (! (result->send_fields(fields)))
05292   {
05293     if (send_row)
05294     {
05295       List<Item>::iterator it(fields.begin());
05296       Item *item;
05297       while ((item= it++))
05298         item->no_rows_in_result();
05299       result->send_data(fields);
05300     }
05301     result->send_eof();       // Should be safe
05302   }
05303   /* Update results for FOUND_ROWS */
05304   join->session->limit_found_rows= join->session->examined_row_count= 0;
05305   return(0);
05306 }
05307 
05428 static COND *simplify_joins(Join *join, List<TableList> *join_list, COND *conds, bool top)
05429 {
05430   TableList *table;
05431   NestedJoin *nested_join;
05432   TableList *prev_table= 0;
05433   List<TableList>::iterator li(join_list->begin());
05434 
05435   /*
05436     Try to simplify join operations from join_list.
05437     The most outer join operation is checked for conversion first.
05438   */
05439   while ((table= li++))
05440   {
05441     table_map used_tables;
05442     table_map not_null_tables= (table_map) 0;
05443 
05444     if ((nested_join= table->getNestedJoin()))
05445     {
05446       /*
05447          If the element of join_list is a nested join apply
05448          the procedure to its nested join list first.
05449       */
05450       if (table->on_expr)
05451       {
05452         Item *expr= table->on_expr;
05453         /*
05454            If an on expression E is attached to the table,
05455            check all null rejected predicates in this expression.
05456            If such a predicate over an attribute belonging to
05457            an inner table of an embedded outer join is found,
05458            the outer join is converted to an inner join and
05459            the corresponding on expression is added to E.
05460         */
05461         expr= simplify_joins(join, &nested_join->join_list, expr, false);
05462 
05463         if (!table->prep_on_expr || expr != table->on_expr)
05464         {
05465           assert(expr);
05466 
05467           table->on_expr= expr;
05468           table->prep_on_expr= expr->copy_andor_structure(join->session);
05469         }
05470       }
05471       nested_join->used_tables= (table_map) 0;
05472       nested_join->not_null_tables=(table_map) 0;
05473       conds= simplify_joins(join, &nested_join->join_list, conds, top);
05474       used_tables= nested_join->used_tables;
05475       not_null_tables= nested_join->not_null_tables;
05476     }
05477     else
05478     {
05479       if (!table->prep_on_expr)
05480         table->prep_on_expr= table->on_expr;
05481       used_tables= table->table->map;
05482       if (conds)
05483         not_null_tables= conds->not_null_tables();
05484     }
05485 
05486     if (table->getEmbedding())
05487     {
05488       table->getEmbedding()->getNestedJoin()->used_tables|= used_tables;
05489       table->getEmbedding()->getNestedJoin()->not_null_tables|= not_null_tables;
05490     }
05491 
05492     if (!table->outer_join || (used_tables & not_null_tables))
05493     {
05494       /*
05495         For some of the inner tables there are conjunctive predicates
05496         that reject nulls => the outer join can be replaced by an inner join.
05497       */
05498       table->outer_join= 0;
05499       if (table->on_expr)
05500       {
05501         /* Add ON expression to the WHERE or upper-level ON condition. */
05502         if (conds)
05503         {
05504           conds= and_conds(conds, table->on_expr);
05505           conds->top_level_item();
05506           /* conds is always a new item as both cond and on_expr existed */
05507           assert(!conds->fixed);
05508           conds->fix_fields(join->session, &conds);
05509         }
05510         else
05511           conds= table->on_expr;
05512         table->prep_on_expr= table->on_expr= 0;
05513       }
05514     }
05515 
05516     if (!top)
05517       continue;
05518 
05519     /*
05520       Only inner tables of non-convertible outer joins
05521       remain with on_expr.
05522     */
05523     if (table->on_expr)
05524     {
05525       table->setDepTables(table->getDepTables() | table->on_expr->used_tables());
05526       if (table->getEmbedding())
05527       {
05528         table->setDepTables(table->getDepTables() & ~table->getEmbedding()->getNestedJoin()->used_tables);
05529         /*
05530            Embedding table depends on tables used
05531            in embedded on expressions.
05532         */
05533         table->getEmbedding()->setOnExprDepTables(table->getEmbedding()->getOnExprDepTables() & table->on_expr->used_tables());
05534       }
05535       else
05536         table->setDepTables(table->getDepTables() & ~table->table->map);
05537     }
05538 
05539     if (prev_table)
05540     {
05541       //If this is straight join, set prev table to be dependent on all tables
05542       //from this nested join, so that correct join order is selected.
05543       if ((test(join->select_options & SELECT_STRAIGHT_JOIN)) ||
05544           prev_table->straight)
05545         prev_table->setDepTables(prev_table->getDepTables() | used_tables);
05546       if (prev_table->on_expr)
05547       {
05548         prev_table->setDepTables(prev_table->getDepTables() | table->getOnExprDepTables());
05549         table_map prev_used_tables= prev_table->getNestedJoin() ?
05550                               prev_table->getNestedJoin()->used_tables :
05551                               prev_table->table->map;
05552         /*
05553           If on expression contains only references to inner tables
05554           we still make the inner tables dependent on the outer tables.
05555           It would be enough to set dependency only on one outer table
05556           for them. Yet this is really a rare case.
05557         */
05558         if (!(prev_table->on_expr->used_tables() & ~prev_used_tables))
05559           prev_table->setDepTables(prev_table->getDepTables() | used_tables);
05560       }
05561     }
05562     prev_table= table;
05563   }
05564 
05565   /*
05566     Flatten nested joins that can be flattened.
05567     no ON expression and not a semi-join => can be flattened.
05568   */
05569   li= join_list->begin();
05570   while ((table= li++))
05571   {
05572     nested_join= table->getNestedJoin();
05573     if (nested_join && !table->on_expr)
05574     {
05575       TableList *tbl;
05576       List<TableList>::iterator it(nested_join->join_list.begin());
05577       while ((tbl= it++))
05578       {
05579         tbl->setEmbedding(table->getEmbedding());
05580         tbl->setJoinList(table->getJoinList());
05581       }
05582       li.replace(nested_join->join_list);
05583     }
05584   }
05585   return(conds);
05586 }
05587 
05588 static int remove_duplicates(Join *join, Table *entry,List<Item> &fields, Item *having)
05589 {
05590   int error;
05591   uint32_t reclength,offset;
05592   uint32_t field_count;
05593   Session *session= join->session;
05594 
05595   entry->reginfo.lock_type=TL_WRITE;
05596 
05597   /* Calculate how many saved fields there is in list */
05598   field_count=0;
05599   List<Item>::iterator it(fields.begin());
05600   Item *item;
05601   while ((item=it++))
05602   {
05603     if (item->get_tmp_table_field() && ! item->const_item())
05604       field_count++;
05605   }
05606 
05607   if (!field_count && !(join->select_options & OPTION_FOUND_ROWS) && !having)
05608   {                    // only const items with no OPTION_FOUND_ROWS
05609     join->unit->select_limit_cnt= 1;    // Only send first row
05610     return(0);
05611   }
05612   Field **first_field=entry->getFields() + entry->getShare()->sizeFields() - field_count;
05613   offset= (field_count ?
05614            entry->getField(entry->getShare()->sizeFields() - field_count)->offset(entry->getInsertRecord()) : 0);
05615   reclength= entry->getShare()->getRecordLength() - offset;
05616 
05617   entry->free_io_cache();       // Safety
05618   entry->cursor->info(HA_STATUS_VARIABLE);
05619   if (entry->getShare()->db_type() == heap_engine ||
05620       (!entry->getShare()->blob_fields &&
05621        ((ALIGN_SIZE(reclength) + HASH_OVERHEAD) * entry->cursor->stats.records <
05622         session->variables.sortbuff_size)))
05623   {
05624     error= remove_dup_with_hash_index(join->session, entry,
05625                                       field_count, first_field,
05626                                       reclength, having);
05627   }
05628   else
05629   {
05630     error= remove_dup_with_compare(join->session, entry, first_field, offset, having);
05631   }
05632 
05633   free_blobs(first_field);
05634 
05635   return(error);
05636 }
05637 
05641 static int setup_without_group(Session *session, 
05642                                Item **ref_pointer_array,
05643                                TableList *tables,
05644                                TableList *,
05645                                List<Item> &fields,
05646                                List<Item> &all_fields,
05647                                COND **conds,
05648                                Order *order,
05649                                Order *group,
05650                                bool *hidden_group_fields)
05651 {
05652   int res;
05653   nesting_map save_allow_sum_func=session->lex().allow_sum_func ;
05654 
05655   session->lex().allow_sum_func&= ~(1 << session->lex().current_select->nest_level);
05656   res= session->setup_conds(tables, conds);
05657 
05658   session->lex().allow_sum_func|= 1 << session->lex().current_select->nest_level;
05659   res= res || setup_order(session, ref_pointer_array, tables, fields, all_fields,
05660                           order);
05661   session->lex().allow_sum_func&= ~(1 << session->lex().current_select->nest_level);
05662   res= res || setup_group(session, ref_pointer_array, tables, fields, all_fields,
05663                           group, hidden_group_fields);
05664   session->lex().allow_sum_func= save_allow_sum_func;
05665   return(res);
05666 }
05667 
05676 static bool make_join_statistics(Join *join, TableList *tables, COND *conds, DYNAMIC_ARRAY *keyuse_array)
05677 {
05678   int error;
05679   Table *table;
05680   uint32_t i;
05681   uint32_t table_count;
05682   uint32_t const_count;
05683   uint32_t key;
05684   table_map found_const_table_map;
05685   table_map all_table_map;
05686   table_map found_ref;
05687   table_map refs;
05688   key_map const_ref;
05689   key_map eq_part;
05690   Table **table_vector= NULL;
05691   JoinTable *stat= NULL;
05692   JoinTable *stat_end= NULL;
05693   JoinTable *s= NULL;
05694   JoinTable **stat_ref= NULL;
05695   optimizer::KeyUse *keyuse= NULL;
05696   optimizer::KeyUse *start_keyuse= NULL;
05697   table_map outer_join= 0;
05698   vector<optimizer::SargableParam> sargables;
05699   JoinTable *stat_vector[MAX_TABLES+1];
05700   optimizer::Position *partial_pos;
05701 
05702   table_count= join->tables;
05703   stat= (JoinTable*) join->session->calloc(sizeof(JoinTable)*table_count);
05704   stat_ref= (JoinTable**) join->session->getMemRoot()->allocate(sizeof(JoinTable*)*MAX_TABLES);
05705   table_vector= (Table**) join->session->getMemRoot()->allocate(sizeof(Table*)*(table_count*2));
05706   if (! stat || ! stat_ref || ! table_vector)
05707     return 1;
05708 
05709   join->best_ref=stat_vector;
05710 
05711   stat_end=stat+table_count;
05712   found_const_table_map= all_table_map=0;
05713   const_count=0;
05714 
05715   for (s= stat, i= 0;
05716        tables;
05717        s++, tables= tables->next_leaf, i++)
05718   {
05719     TableList *embedding= tables->getEmbedding();
05720     stat_vector[i]=s;
05721     s->keys.reset();
05722     s->const_keys.reset();
05723     s->checked_keys.reset();
05724     s->needed_reg.reset();
05725     table_vector[i]=s->table=table=tables->table;
05726     table->pos_in_table_list= tables;
05727     assert(table->cursor);
05728     error= table->cursor->info(HA_STATUS_VARIABLE | HA_STATUS_NO_LOCK);
05729     if (error)
05730     {
05731         table->print_error(error, MYF(0));
05732         return 1;
05733     }
05734     table->quick_keys.reset();
05735     table->reginfo.join_tab=s;
05736     table->reginfo.not_exists_optimize=0;
05737     memset(table->const_key_parts, 0,
05738            sizeof(key_part_map)*table->getShare()->sizeKeys());
05739     all_table_map|= table->map;
05740     s->join=join;
05741     s->info=0;          // For describe
05742 
05743     s->dependent= tables->getDepTables();
05744     s->key_dependent= 0;
05745     table->quick_condition_rows= table->cursor->stats.records;
05746 
05747     s->on_expr_ref= &tables->on_expr;
05748     if (*s->on_expr_ref)
05749     {
05750       /* s is the only inner table of an outer join */
05751       if (!table->cursor->stats.records && !embedding)
05752       {           // Empty table
05753         s->dependent= 0;                        // Ignore LEFT JOIN depend.
05754         set_position(join, const_count++, s, NULL);
05755         continue;
05756       }
05757       outer_join|= table->map;
05758       s->embedding_map.reset();
05759       for (;embedding; embedding= embedding->getEmbedding())
05760         s->embedding_map|= embedding->getNestedJoin()->nj_map;
05761       continue;
05762     }
05763     if (embedding && !(false && ! embedding->getEmbedding()))
05764     {
05765       /* s belongs to a nested join, maybe to several embedded joins */
05766       s->embedding_map.reset();
05767       do
05768       {
05769         NestedJoin *nested_join= embedding->getNestedJoin();
05770         s->embedding_map|= nested_join->nj_map;
05771         s->dependent|= embedding->getDepTables();
05772         embedding= embedding->getEmbedding();
05773         outer_join|= nested_join->used_tables;
05774       }
05775       while (embedding);
05776       continue;
05777     }
05778     if ((table->cursor->stats.records <= 1) && !s->dependent &&
05779         (table->cursor->getEngine()->check_flag(HTON_BIT_STATS_RECORDS_IS_EXACT)) &&
05780         !join->no_const_tables)
05781     {
05782       set_position(join, const_count++, s, NULL);
05783     }
05784   }
05785   stat_vector[i]=0;
05786   join->outer_join=outer_join;
05787 
05788   if (join->outer_join)
05789   {
05790     /*
05791        Build transitive closure for relation 'to be dependent on'.
05792        This will speed up the plan search for many cases with outer joins,
05793        as well as allow us to catch illegal cross references/
05794        Warshall's algorithm is used to build the transitive closure.
05795        As we use bitmaps to represent the relation the complexity
05796        of the algorithm is O((number of tables)^2).
05797     */
05798     for (i= 0; i < table_count; i++)
05799     {
05800       uint32_t j;
05801       table= stat[i].table;
05802 
05803       if (!table->reginfo.join_tab->dependent)
05804         continue;
05805 
05806       for (j= 0, s= stat; j < table_count; j++, s++)
05807       {
05808         if (s->dependent & table->map)
05809         {
05810           table_map was_dependent= s->dependent;
05811           s->dependent |= table->reginfo.join_tab->dependent;
05812           if (i > j && s->dependent != was_dependent)
05813           {
05814             i= j= 1;
05815             break;
05816           }
05817         }
05818       }
05819     }
05820     /* Catch illegal cross references for outer joins */
05821     for (i= 0, s= stat ; i < table_count ; i++, s++)
05822     {
05823       if (s->dependent & s->table->map)
05824       {
05825         join->tables=0;     // Don't use join->table
05826         my_message(ER_WRONG_OUTER_JOIN, ER(ER_WRONG_OUTER_JOIN), MYF(0));
05827         return 1;
05828       }
05829       if (outer_join & s->table->map)
05830         s->table->maybe_null= 1;
05831 
05832       s->key_dependent= s->dependent;
05833     }
05834   }
05835 
05836   if (conds || outer_join)
05837     if (update_ref_and_keys(join->session, keyuse_array, stat, join->tables,
05838                             conds, join->cond_equal,
05839                             ~outer_join, join->select_lex, sargables))
05840       return 1;
05841 
05842   /* Read tables with 0 or 1 rows (system tables) */
05843   join->const_table_map= 0;
05844 
05845   optimizer::Position *p_pos= join->getFirstPosInPartialPlan();
05846   optimizer::Position *p_end= join->getSpecificPosInPartialPlan(const_count);
05847   while (p_pos < p_end)
05848   {
05849     int tmp;
05850     s= p_pos->getJoinTable();
05851     s->type= AM_SYSTEM;
05852     join->const_table_map|=s->table->map;
05853     if ((tmp= s->joinReadConstTable(p_pos)))
05854     {
05855       if (tmp > 0)
05856         return 1;     // Fatal error
05857     }
05858     else
05859       found_const_table_map|= s->table->map;
05860     p_pos++;
05861   }
05862 
05863   /* loop until no more const tables are found */
05864   int ref_changed;
05865   do
05866   {
05867   more_const_tables_found:
05868     ref_changed = 0;
05869     found_ref=0;
05870 
05871     /*
05872       We only have to loop from stat_vector + const_count as
05873       set_position() will move all const_tables first in stat_vector
05874     */
05875 
05876     for (JoinTable **pos= stat_vector+const_count; (s= *pos); pos++)
05877     {
05878       table= s->table;
05879 
05880       /*
05881         If equi-join condition by a key is null rejecting and after a
05882         substitution of a const table the key value happens to be null
05883         then we can state that there are no matches for this equi-join.
05884       */
05885       if ((keyuse= s->keyuse) && *s->on_expr_ref && s->embedding_map.none())
05886       {
05887         /*
05888           When performing an outer join operation if there are no matching rows
05889           for the single row of the outer table all the inner tables are to be
05890           null complemented and thus considered as constant tables.
05891           Here we apply this consideration to the case of outer join operations
05892           with a single inner table only because the case with nested tables
05893           would require a more thorough analysis.
05894           TODO. Apply single row substitution to null complemented inner tables
05895           for nested outer join operations.
05896         */
05897         while (keyuse->getTable() == table)
05898         {
05899           if (! (keyuse->getVal()->used_tables() & ~join->const_table_map) &&
05900               keyuse->getVal()->is_null() && keyuse->isNullRejected())
05901           {
05902             s->type= AM_CONST;
05903             table->mark_as_null_row();
05904             found_const_table_map|= table->map;
05905             join->const_table_map|= table->map;
05906             set_position(join, const_count++, s, NULL);
05907             goto more_const_tables_found;
05908            }
05909           keyuse++;
05910         }
05911       }
05912 
05913       if (s->dependent)       // If dependent on some table
05914       {
05915         // All dep. must be constants
05916         if (s->dependent & ~(found_const_table_map))
05917           continue;
05918         if (table->cursor->stats.records <= 1L &&
05919             (table->cursor->getEngine()->check_flag(HTON_BIT_STATS_RECORDS_IS_EXACT)) &&
05920                   !table->pos_in_table_list->getEmbedding())
05921         {         // system table
05922           int tmp= 0;
05923           s->type= AM_SYSTEM;
05924           join->const_table_map|=table->map;
05925           set_position(join, const_count++, s, NULL);
05926           partial_pos= join->getSpecificPosInPartialPlan(const_count - 1);
05927           if ((tmp= s->joinReadConstTable(partial_pos)))
05928           {
05929             if (tmp > 0)
05930               return 1;     // Fatal error
05931           }
05932           else
05933             found_const_table_map|= table->map;
05934           continue;
05935         }
05936       }
05937       /* check if table can be read by key or table only uses const refs */
05938       if ((keyuse=s->keyuse))
05939       {
05940         s->type= AM_REF;
05941         while (keyuse->getTable() == table)
05942         {
05943           start_keyuse= keyuse;
05944           key= keyuse->getKey();
05945           s->keys.set(key);               // QQ: remove this ?
05946 
05947           refs= 0;
05948           const_ref.reset();
05949           eq_part.reset();
05950           do
05951           {
05952             if (keyuse->getVal()->type() != Item::NULL_ITEM && 
05953                 ! keyuse->getOptimizeFlags())
05954             {
05955               if (! ((~found_const_table_map) & keyuse->getUsedTables()))
05956                 const_ref.set(keyuse->getKeypart());
05957               else
05958                 refs|= keyuse->getUsedTables();
05959               eq_part.set(keyuse->getKeypart());
05960             }
05961             keyuse++;
05962           } while (keyuse->getTable() == table && keyuse->getKey() == key);
05963 
05964           if (is_keymap_prefix(eq_part, table->key_info[key].key_parts) &&
05965               ! table->pos_in_table_list->getEmbedding())
05966           {
05967             if ((table->key_info[key].flags & (HA_NOSAME)) == HA_NOSAME)
05968             {
05969               if (const_ref == eq_part)
05970               {         // Found everything for ref.
05971                 int tmp;
05972                 ref_changed = 1;
05973                 s->type= AM_CONST;
05974                 join->const_table_map|= table->map;
05975                 set_position(join, const_count++, s, start_keyuse);
05976                 if (create_ref_for_key(join, s, start_keyuse, found_const_table_map))
05977                   return 1;
05978                 partial_pos= join->getSpecificPosInPartialPlan(const_count - 1);
05979                 if ((tmp=s->joinReadConstTable(partial_pos)))
05980                 {
05981                   if (tmp > 0)
05982                     return 1;     // Fatal error
05983                 }
05984                 else
05985                   found_const_table_map|= table->map;
05986                 break;
05987               }
05988               else
05989                 found_ref|= refs;      // Table is const if all refs are const
05990             }
05991             else if (const_ref == eq_part)
05992               s->const_keys.set(key);
05993           }
05994         }
05995       }
05996     }
05997   } while (join->const_table_map & found_ref && ref_changed);
05998 
05999   /*
06000     Update info on indexes that can be used for search lookups as
06001     reading const tables may has added new sargable predicates.
06002   */
06003   if (const_count && ! sargables.empty())
06004   {
06005     vector<optimizer::SargableParam>::iterator iter= sargables.begin();
06006     while (iter != sargables.end())
06007     {
06008       Field *field= iter->getField();
06009       JoinTable *join_tab= field->getTable()->reginfo.join_tab;
06010       key_map possible_keys= field->key_start;
06011       possible_keys&= field->getTable()->keys_in_use_for_query;
06012       bool is_const= true;
06013       for (uint32_t j= 0; j < iter->getNumValues(); j++)
06014         is_const&= iter->isConstItem(j);
06015       if (is_const)
06016         join_tab[0].const_keys|= possible_keys;
06017       ++iter;
06018     }
06019   }
06020 
06021   /* Calc how many (possible) matched records in each table */
06022 
06023   for (s=stat ; s < stat_end ; s++)
06024   {
06025     if (s->type == AM_SYSTEM || s->type == AM_CONST)
06026     {
06027       /* Only one matching row */
06028       s->found_records=s->records=s->read_time=1; s->worst_seeks=1.0;
06029       continue;
06030     }
06031     /* Approximate found rows and time to read them */
06032     s->found_records=s->records=s->table->cursor->stats.records;
06033     s->read_time=(ha_rows) s->table->cursor->scan_time();
06034 
06035     /*
06036       Set a max range of how many seeks we can expect when using keys
06037       This is can't be to high as otherwise we are likely to use
06038       table scan.
06039     */
06040     s->worst_seeks= min((double) s->found_records / 10,
06041                         (double) s->read_time*3);
06042     if (s->worst_seeks < 2.0)     // Fix for small tables
06043       s->worst_seeks=2.0;
06044 
06045     /*
06046       Add to stat->const_keys those indexes for which all group fields or
06047       all select distinct fields participate in one index.
06048     */
06049     add_group_and_distinct_keys(join, s);
06050 
06051     if (s->const_keys.any() &&
06052         !s->table->pos_in_table_list->getEmbedding())
06053     {
06054       ha_rows records;
06055       optimizer::SqlSelect *select= NULL;
06056       select= optimizer::make_select(s->table, found_const_table_map, found_const_table_map, *s->on_expr_ref ? *s->on_expr_ref : conds, 1, &error);
06057       if (! select)
06058         return 1;
06059       records= get_quick_record_count(join->session, select, s->table, &s->const_keys, join->row_limit);
06060       s->quick=select->quick;
06061       s->needed_reg=select->needed_reg;
06062       select->quick=0;
06063 
06064       if (records == 0 && s->table->reginfo.impossible_range)
06065       {
06066         /*
06067           Impossible WHERE or ON expression
06068           In case of ON, we mark that the we match one empty NULL row.
06069           In case of WHERE, don't set found_const_table_map to get the
06070           caller to abort with a zero row result.
06071         */
06072         join->const_table_map|= s->table->map;
06073         set_position(join, const_count++, s, NULL);
06074         s->type= AM_CONST;
06075         if (*s->on_expr_ref)
06076         {
06077           /* Generate empty row */
06078           s->info= "Impossible ON condition";
06079           found_const_table_map|= s->table->map;
06080           s->type= AM_CONST;
06081           s->table->mark_as_null_row();   // All fields are NULL
06082         }
06083       }
06084       if (records != HA_POS_ERROR)
06085       {
06086         s->found_records=records;
06087         s->read_time= (ha_rows) (s->quick ? s->quick->read_time : 0.0);
06088       }
06089       delete select;
06090     }
06091   }
06092 
06093   join->join_tab=stat;
06094   join->map2table=stat_ref;
06095   join->table= join->all_tables=table_vector;
06096   join->const_tables=const_count;
06097   join->found_const_table_map=found_const_table_map;
06098 
06099   /* Find an optimal join order of the non-constant tables. */
06100   if (join->const_tables != join->tables)
06101   {
06102     optimize_keyuse(join, keyuse_array);
06103     // @note c_str() is not likely to be valid here if dtrace expects it to
06104     // exist for any period of time.
06105     DRIZZLE_QUERY_OPT_CHOOSE_PLAN_START(join->session->getQueryString()->c_str(), join->session->thread_id);
06106     bool res= choose_plan(join, all_table_map & ~join->const_table_map);
06107     DRIZZLE_QUERY_OPT_CHOOSE_PLAN_DONE(res ? 1 : 0);
06108     if (res)
06109       return true;
06110   }
06111   else
06112   {
06113     join->copyPartialPlanIntoOptimalPlan(join->const_tables);
06114     join->best_read= 1.0;
06115   }
06116   /* Generate an execution plan from the found optimal join order. */
06117   return (join->session->getKilled() || get_best_combination(join));
06118 }
06119 
06139 static uint32_t build_bitmap_for_nested_joins(List<TableList> *join_list, uint32_t first_unused)
06140 {
06141   List<TableList>::iterator li(join_list->begin());
06142   TableList *table;
06143   while ((table= li++))
06144   {
06145     NestedJoin *nested_join;
06146     if ((nested_join= table->getNestedJoin()))
06147     {
06148       /*
06149         It is guaranteed by simplify_joins() function that a nested join
06150         that has only one child is either
06151          - a single-table view (the child is the underlying table), or
06152          - a single-table semi-join nest
06153 
06154         We don't assign bits to such sj-nests because
06155         1. it is redundant (a "sequence" of one table cannot be interleaved
06156             with anything)
06157         2. we could run out of bits in the nested join bitset otherwise.
06158       */
06159       if (nested_join->join_list.size() != 1)
06160       {
06161         /* Don't assign bits to sj-nests */
06162         if (table->on_expr)
06163           nested_join->nj_map.set(first_unused++);
06164         first_unused= build_bitmap_for_nested_joins(&nested_join->join_list,
06165                                                     first_unused);
06166       }
06167     }
06168   }
06169   return(first_unused);
06170 }
06171 
06172 
06177 static Table *get_sort_by_table(Order *a, Order *b,TableList *tables)
06178 {
06179   table_map map= 0;
06180 
06181   if (!a)
06182     a= b;         // Only one need to be given
06183   else if (!b)
06184     b= a;
06185 
06186   for (; a && b; a=a->next,b=b->next)
06187   {
06188     if (!(*a->item)->eq(*b->item,1))
06189       return (Table *) NULL;
06190     map|= a->item[0]->used_tables();
06191   }
06192   if (!map || (map & (RAND_TABLE_BIT | OUTER_REF_TABLE_BIT)))
06193     return (Table *) NULL;
06194 
06195   for (; !(map & tables->table->map); tables= tables->next_leaf) {};
06196   if (map != tables->table->map)
06197     return (Table *) NULL;        // More than one table
06198   return tables->table;
06199 }
06200 
06210 static void reset_nj_counters(List<TableList> *join_list)
06211 {
06212   List<TableList>::iterator li(join_list->begin());
06213   TableList *table;
06214   while ((table= li++))
06215   {
06216     NestedJoin *nested_join;
06217     if ((nested_join= table->getNestedJoin()))
06218     {
06219       nested_join->counter_= 0;
06220       reset_nj_counters(&nested_join->join_list);
06221     }
06222   }
06223   return;
06224 }
06225 
06232 static bool test_if_subpart(Order *a, Order *b)
06233 {
06234   for (; a && b; a=a->next,b=b->next)
06235   {
06236     if ((*a->item)->eq(*b->item,1))
06237       a->asc=b->asc;
06238     else
06239       return 0;
06240   }
06241   return test(!b);
06242 }
06243 
06296 static void restore_prev_nj_state(JoinTable *last)
06297 {
06298   TableList *last_emb= last->table->pos_in_table_list->getEmbedding();
06299   Join *join= last->join;
06300   for (;last_emb != NULL; last_emb= last_emb->getEmbedding())
06301   {
06302     NestedJoin *nest= last_emb->getNestedJoin();
06303     
06304     bool was_fully_covered= nest->is_fully_covered();
06305     
06306     if (--nest->counter_ == 0)
06307       join->cur_embedding_map&= ~nest->nj_map;
06308     
06309     if (!was_fully_covered)
06310       break;
06311     
06312     join->cur_embedding_map|= nest->nj_map;
06313   }
06314 }
06315 
06320 static bool add_ref_to_table_cond(Session *session, JoinTable *join_tab)
06321 {
06322   if (!join_tab->ref.key_parts)
06323     return(false);
06324 
06325   Item_cond_and *cond=new Item_cond_and();
06326   Table *table=join_tab->table;
06327   int error;
06328   if (!cond)
06329     return(true);
06330 
06331   for (uint32_t i=0 ; i < join_tab->ref.key_parts ; i++)
06332   {
06333     Field *field=table->getField(table->key_info[join_tab->ref.key].key_part[i].fieldnr - 1);
06334     Item *value=join_tab->ref.items[i];
06335     cond->add(new Item_func_equal(new Item_field(field), value));
06336   }
06337   if (session->is_fatal_error)
06338     return(true);
06339 
06340   if (!cond->fixed)
06341     cond->fix_fields(session, (Item**)&cond);
06342   if (join_tab->select)
06343   {
06344     error=(int) cond->add(join_tab->select->cond);
06345     join_tab->select_cond=join_tab->select->cond=cond;
06346   }
06347   else if ((join_tab->select= optimizer::make_select(join_tab->table, 0, 0, cond, 0,
06348                                                      &error)))
06349     join_tab->select_cond=cond;
06350 
06351   return(error ? true : false);
06352 }
06353 
06354 static void free_blobs(Field **ptr)
06355 {
06356   for (; *ptr ; ptr++)
06357   {
06358     if ((*ptr)->flags & BLOB_FLAG)
06359       ((Field_blob *) (*ptr))->free();
06360   }
06361 }
06362 
06367 } /* namespace drizzled */