tritonn-1.0.10-mysql-5.0.51a/sql/sql_select.cc

/* Copyright (C) 2000-2006 MySQL AB

   This program is free software; you can redistribute it and/or modify
   it under the terms of the GNU General Public License as published by
   the Free Software Foundation; version 2 of the License.

   This program is distributed in the hope that it will be useful,
   but WITHOUT ANY WARRANTY; without even the implied warranty of
   MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
   GNU General Public License for more details.

   You should have received a copy of the GNU General Public License
   along with this program; if not, write to the Free Software
   Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA  02111-1307  USA */


/* mysql_select and join optimization */

#ifdef USE_PRAGMA_IMPLEMENTATION
#pragma implementation                          // gcc: Class implementation
#endif

#include "mysql_priv.h"
#include "sql_select.h"
#include "sql_cursor.h"

#include <m_ctype.h>
#include <hash.h>
#include <ft_global.h>

const char *join_type_str[]={ "UNKNOWN","system","const","eq_ref","ref",
                              "MAYBE_REF","ALL","range","index","fulltext",
                              "ref_or_null","unique_subquery","index_subquery",
                              "index_merge"
};

struct st_sargable_param;

static void optimize_keyuse(JOIN *join, DYNAMIC_ARRAY *keyuse_array);
static bool make_join_statistics(JOIN *join, TABLE_LIST *leaves, COND *conds,
                                 DYNAMIC_ARRAY *keyuse);
static bool update_ref_and_keys(THD *thd, DYNAMIC_ARRAY *keyuse,
                                JOIN_TAB *join_tab,
                                uint tables, COND *conds,
                                COND_EQUAL *cond_equal,
                                table_map table_map, SELECT_LEX *select_lex,
                                st_sargable_param **sargables);
static int sort_keyuse(KEYUSE *a,KEYUSE *b);
static void set_position(JOIN *join,uint index,JOIN_TAB *table,KEYUSE *key);
static bool create_ref_for_key(JOIN *join, JOIN_TAB *j, KEYUSE *org_keyuse,
                               table_map used_tables);
static bool choose_plan(JOIN *join,table_map join_tables);

static void best_access_path(JOIN *join, JOIN_TAB *s, THD *thd,
                             table_map remaining_tables, uint idx,
                             double record_count, double read_time);
static void optimize_straight_join(JOIN *join, table_map join_tables);
static bool greedy_search(JOIN *join, table_map remaining_tables,
                             uint depth, uint prune_level);
static bool best_extension_by_limited_search(JOIN *join,
                                             table_map remaining_tables,
                                             uint idx, double record_count,
                                             double read_time, uint depth,
                                             uint prune_level);
static uint determine_search_depth(JOIN* join);
static int join_tab_cmp(const void* ptr1, const void* ptr2);
static int join_tab_cmp_straight(const void* ptr1, const void* ptr2);
/*
  TODO: 'find_best' is here only temporarily until 'greedy_search' is
  tested and approved.
*/
static bool find_best(JOIN *join,table_map rest_tables,uint index,
                      double record_count,double read_time);
static uint cache_record_length(JOIN *join,uint index);
static double prev_record_reads(JOIN *join,table_map found_ref);
static bool get_best_combination(JOIN *join);
static store_key *get_store_key(THD *thd,
                                KEYUSE *keyuse, table_map used_tables,
                                KEY_PART_INFO *key_part, char *key_buff,
                                uint maybe_null);
static bool make_simple_join(JOIN *join,TABLE *tmp_table);
static void make_outerjoin_info(JOIN *join);
static bool make_join_select(JOIN *join,SQL_SELECT *select,COND *item);
static void make_join_readinfo(JOIN *join, ulonglong options);
static bool only_eq_ref_tables(JOIN *join, ORDER *order, table_map tables);
static void update_depend_map(JOIN *join);
static void update_depend_map(JOIN *join, ORDER *order);
static ORDER *remove_const(JOIN *join,ORDER *first_order,COND *cond,
                           bool change_list, bool *simple_order);
static int return_zero_rows(JOIN *join, select_result *res,TABLE_LIST *tables,
                            List<Item> &fields, bool send_row,
                            ulonglong select_options, const char *info,
                            Item *having);
static COND *build_equal_items(THD *thd, COND *cond,
                               COND_EQUAL *inherited,
                               List<TABLE_LIST> *join_list,
                               COND_EQUAL **cond_equal_ref);
static COND* substitute_for_best_equal_field(COND *cond,
                                             COND_EQUAL *cond_equal,
                                             void *table_join_idx);
static COND *simplify_joins(JOIN *join, List<TABLE_LIST> *join_list,
                            COND *conds, bool top);
static bool check_interleaving_with_nj(JOIN_TAB *last, JOIN_TAB *next);
static void restore_prev_nj_state(JOIN_TAB *last);
static void reset_nj_counters(List<TABLE_LIST> *join_list);
static uint build_bitmap_for_nested_joins(List<TABLE_LIST> *join_list,
                                          uint first_unused);

static COND *optimize_cond(JOIN *join, COND *conds,
                           List<TABLE_LIST> *join_list,
                           Item::cond_result *cond_value);
static bool const_expression_in_where(COND *conds,Item *item, Item **comp_item);
static bool open_tmp_table(TABLE *table);
static bool create_myisam_tmp_table(TABLE *table,TMP_TABLE_PARAM *param,
                                    ulonglong options);
static int do_select(JOIN *join,List<Item> *fields,TABLE *tmp_table,
                     Procedure *proc);

static enum_nested_loop_state
evaluate_join_record(JOIN *join, JOIN_TAB *join_tab,
                     int error, my_bool *report_error);
static enum_nested_loop_state
evaluate_null_complemented_join_record(JOIN *join, JOIN_TAB *join_tab);
static enum_nested_loop_state
flush_cached_records(JOIN *join, JOIN_TAB *join_tab, bool skip_last);
static enum_nested_loop_state
end_send(JOIN *join, JOIN_TAB *join_tab, bool end_of_records);
static enum_nested_loop_state
end_send_group(JOIN *join, JOIN_TAB *join_tab, bool end_of_records);
static enum_nested_loop_state
end_write(JOIN *join, JOIN_TAB *join_tab, bool end_of_records);
static enum_nested_loop_state
end_update(JOIN *join, JOIN_TAB *join_tab, bool end_of_records);
static enum_nested_loop_state
end_unique_update(JOIN *join, JOIN_TAB *join_tab, bool end_of_records);
static enum_nested_loop_state
end_write_group(JOIN *join, JOIN_TAB *join_tab, bool end_of_records);

static int test_if_group_changed(List<Cached_item> &list);
static int join_read_const_table(JOIN_TAB *tab, POSITION *pos);
static int join_read_system(JOIN_TAB *tab);
static int join_read_const(JOIN_TAB *tab);
static int join_read_key(JOIN_TAB *tab);
static int join_read_always_key(JOIN_TAB *tab);
static int join_read_last_key(JOIN_TAB *tab);
static int join_no_more_records(READ_RECORD *info);
static int join_read_next(READ_RECORD *info);
static int join_init_quick_read_record(JOIN_TAB *tab);
static int test_if_quick_select(JOIN_TAB *tab);
static int join_init_read_record(JOIN_TAB *tab);
static int join_read_first(JOIN_TAB *tab);
static int join_read_next(READ_RECORD *info);
static int join_read_next_same(READ_RECORD *info);
static int join_read_last(JOIN_TAB *tab);
static int join_read_prev_same(READ_RECORD *info);
static int join_read_prev(READ_RECORD *info);
static int join_ft_read_first(JOIN_TAB *tab);
static int join_ft_read_next(READ_RECORD *info);
int join_read_always_key_or_null(JOIN_TAB *tab);
int join_read_next_same_or_null(READ_RECORD *info);
static COND *make_cond_for_table(COND *cond,table_map table,
                                 table_map used_table);
static Item* part_of_refkey(TABLE *form,Field *field);
uint find_shortest_key(TABLE *table, const key_map *usable_keys);
static bool test_if_skip_sort_order(JOIN_TAB *tab,ORDER *order,
                                    ha_rows select_limit, bool no_changes);
static bool list_contains_unique_index(TABLE *table,
                          bool (*find_func) (Field *, void *), void *data);
static bool find_field_in_item_list (Field *field, void *data);
static bool find_field_in_order_list (Field *field, void *data);
static int create_sort_index(THD *thd, JOIN *join, ORDER *order,
                             ha_rows filesort_limit, ha_rows select_limit);
static int remove_duplicates(JOIN *join,TABLE *entry,List<Item> &fields,
                             Item *having);
static int remove_dup_with_compare(THD *thd, TABLE *entry, Field **field,
                                   ulong offset,Item *having);
static int remove_dup_with_hash_index(THD *thd,TABLE *table,
                                      uint field_count, Field **first_field,

                                      ulong key_length,Item *having);
static int join_init_cache(THD *thd,JOIN_TAB *tables,uint table_count);
static ulong used_blob_length(CACHE_FIELD **ptr);
static bool store_record_in_cache(JOIN_CACHE *cache);
static void reset_cache_read(JOIN_CACHE *cache);
static void reset_cache_write(JOIN_CACHE *cache);
static void read_cached_record(JOIN_TAB *tab);
static bool cmp_buffer_with_ref(JOIN_TAB *tab);
static bool setup_new_fields(THD *thd, List<Item> &fields,
                             List<Item> &all_fields, ORDER *new_order);
static ORDER *create_distinct_group(THD *thd, Item **ref_pointer_array,
                                    ORDER *order, List<Item> &fields,
                                    List<Item> &all_fields,
                                    bool *all_order_by_fields_used);
static bool test_if_subpart(ORDER *a,ORDER *b);
static TABLE *get_sort_by_table(ORDER *a,ORDER *b,TABLE_LIST *tables);
static void calc_group_buffer(JOIN *join,ORDER *group);
static bool make_group_fields(JOIN *main_join, JOIN *curr_join);
static bool alloc_group_fields(JOIN *join,ORDER *group);
// Create list for using with tempory table
static bool change_to_use_tmp_fields(THD *thd, Item **ref_pointer_array,
                                     List<Item> &new_list1,
                                     List<Item> &new_list2,
                                     uint elements, List<Item> &items);
// Create list for using with tempory table
static bool change_refs_to_tmp_fields(THD *thd, Item **ref_pointer_array,
                                      List<Item> &new_list1,
                                      List<Item> &new_list2,
                                      uint elements, List<Item> &items);
static void init_tmptable_sum_functions(Item_sum **func);
static void update_tmptable_sum_func(Item_sum **func,TABLE *tmp_table);
static void copy_sum_funcs(Item_sum **func_ptr, Item_sum **end);
static bool add_ref_to_table_cond(THD *thd, JOIN_TAB *join_tab);
static bool setup_sum_funcs(THD *thd, Item_sum **func_ptr);
static bool init_sum_functions(Item_sum **func, Item_sum **end);
static bool update_sum_func(Item_sum **func);
static void select_describe(JOIN *join, bool need_tmp_table,bool need_order,
                            bool distinct, const char *message=NullS);
static Item *remove_additional_cond(Item* conds);
static void add_group_and_distinct_keys(JOIN *join, JOIN_TAB *join_tab);


/*
  This handles SELECT with and without UNION
*/

bool handle_select(THD *thd, LEX *lex, select_result *result,
                   ulong setup_tables_done_option)
{
  bool res;
  register SELECT_LEX *select_lex = &lex->select_lex;
  DBUG_ENTER("handle_select");

  if (select_lex->next_select() || select_lex->master_unit()->fake_select_lex)
    res= mysql_union(thd, lex, result, &lex->unit, setup_tables_done_option);
  else
  {
    SELECT_LEX_UNIT *unit= &lex->unit;
    unit->set_limit(unit->global_parameters);
    /*
      'options' of mysql_select will be set in JOIN, as far as JOIN for
      every PS/SP execution new, we will not need reset this flag if 
      setup_tables_done_option changed for next rexecution
    */
    res= mysql_select(thd, &select_lex->ref_pointer_array,
                      (TABLE_LIST*) select_lex->table_list.first,
                      select_lex->with_wild, select_lex->item_list,
                      select_lex->where,
                      select_lex->order_list.elements +
                      select_lex->group_list.elements,
                      (ORDER*) select_lex->order_list.first,
                      (ORDER*) select_lex->group_list.first,
                      select_lex->having,
                      (ORDER*) lex->proc_list.first,
                      select_lex->options | thd->options |
                      setup_tables_done_option,
                      result, unit, select_lex);
  }
  DBUG_PRINT("info",("res: %d  report_error: %d", res,
                     thd->net.report_error));
  res|= thd->net.report_error;
  if (unlikely(res))
    result->abort();

  DBUG_RETURN(res);
}


/*
  Fix fields referenced from inner selects.

  SYNOPSIS
    fix_inner_refs()
    thd               Thread handle
    all_fields        List of all fields used in select
    select            Current select
    ref_pointer_array Array of references to Items used in current select

  DESCRIPTION
    The function serves 3 purposes - adds fields referenced from inner
    selects to the current select list, resolves which class to use
    to access referenced item (Item_ref of Item_direct_ref) and fixes
    references (Item_ref objects) to these fields.

    If a field isn't already in the select list and the ref_pointer_array
    is provided then it is added to the all_fields list and the pointer to
    it is saved in the ref_pointer_array.

    The class to access the outer field is determined by the following rules:
    1. If the outer field isn't used under an aggregate function
      then the Item_ref class should be used.
    2. If the outer field is used under an aggregate function and this
      function is aggregated in the select where the outer field was
      resolved or in some more inner select then the Item_direct_ref
      class should be used.
    The resolution is done here and not at the fix_fields() stage as
    it can be done only after sum functions are fixed and pulled up to
    selects where they are have to be aggregated.
    When the class is chosen it substitutes the original field in the
    Item_outer_ref object.

    After this we proceed with fixing references (Item_outer_ref objects) to
    this field from inner subqueries.

  RETURN
    TRUE  an error occured
    FALSE ok
*/

bool
fix_inner_refs(THD *thd, List<Item> &all_fields, SELECT_LEX *select,
                 Item **ref_pointer_array)
{
  Item_outer_ref *ref;
  bool res= FALSE;
  bool direct_ref= FALSE;

  List_iterator<Item_outer_ref> ref_it(select->inner_refs_list);
  while ((ref= ref_it++))
  {
    Item *item= ref->outer_ref;
    Item **item_ref= ref->ref;
    Item_ref *new_ref;
    /*
      TODO: this field item already might be present in the select list.
      In this case instead of adding new field item we could use an
      existing one. The change will lead to less operations for copying fields,
      smaller temporary tables and less data passed through filesort.
    */
    if (ref_pointer_array && !ref->found_in_select_list)
    {
      int el= all_fields.elements;
      ref_pointer_array[el]= item;
      /* Add the field item to the select list of the current select. */
      all_fields.push_front(item);
      /*
        If it's needed reset each Item_ref item that refers this field with
        a new reference taken from ref_pointer_array.
      */
      item_ref= ref_pointer_array + el;
    }

    if (ref->in_sum_func)
    {
      Item_sum *sum_func;
      if (ref->in_sum_func->nest_level > select->nest_level)
        direct_ref= TRUE;
      else
      {
        for (sum_func= ref->in_sum_func; sum_func &&
             sum_func->aggr_level >= select->nest_level;
             sum_func= sum_func->in_sum_func)
        {
          if (sum_func->aggr_level == select->nest_level)
          {
            direct_ref= TRUE;
            break;
          }
        }
      }
    }
    new_ref= direct_ref ?
              new Item_direct_ref(ref->context, item_ref, ref->field_name,
                          ref->table_name, ref->alias_name_used) :
              new Item_ref(ref->context, item_ref, ref->field_name,
                          ref->table_name, ref->alias_name_used);
    if (!new_ref)
      return TRUE;
    ref->outer_ref= new_ref;
    ref->ref= &ref->outer_ref;

    if (!ref->fixed && ref->fix_fields(thd, 0))
      return TRUE;
    thd->used_tables|= item->used_tables();
  }
  return res;
}

/*
  Function to setup clauses without sum functions
*/
inline int setup_without_group(THD *thd, Item **ref_pointer_array,
                               TABLE_LIST *tables,
                               TABLE_LIST *leaves,
                               List<Item> &fields,
                               List<Item> &all_fields,
                               COND **conds,
                               ORDER *order,
                               ORDER *group, bool *hidden_group_fields)
{
  int res;
  nesting_map save_allow_sum_func=thd->lex->allow_sum_func ;
  DBUG_ENTER("setup_without_group");

  thd->lex->allow_sum_func&= ~(1 << thd->lex->current_select->nest_level);
  res= setup_conds(thd, tables, leaves, conds);

  thd->lex->allow_sum_func|= 1 << thd->lex->current_select->nest_level;
  res= res || setup_order(thd, ref_pointer_array, tables, fields, all_fields,
                          order);
  thd->lex->allow_sum_func&= ~(1 << thd->lex->current_select->nest_level);
  res= res || setup_group(thd, ref_pointer_array, tables, fields, all_fields,
                          group, hidden_group_fields);
  thd->lex->allow_sum_func= save_allow_sum_func;
  DBUG_RETURN(res);
}

/*****************************************************************************
  Check fields, find best join, do the select and output fields.
  mysql_select assumes that all tables are already opened
*****************************************************************************/

/*
  Prepare of whole select (including sub queries in future).
  return -1 on error
          0 on success
*/
int
JOIN::prepare(Item ***rref_pointer_array,
              TABLE_LIST *tables_init,
              uint wild_num, COND *conds_init, uint og_num,
              ORDER *order_init, ORDER *group_init,
              Item *having_init,
              ORDER *proc_param_init, SELECT_LEX *select_lex_arg,
              SELECT_LEX_UNIT *unit_arg)
{
  DBUG_ENTER("JOIN::prepare");

  // to prevent double initialization on EXPLAIN
  if (optimized)
    DBUG_RETURN(0);

  conds= conds_init;
  order= order_init;
  group_list= group_init;
  having= having_init;
  proc_param= proc_param_init;
  tables_list= tables_init;
  select_lex= select_lex_arg;
  select_lex->join= this;
  join_list= &select_lex->top_join_list;
  union_part= (unit_arg->first_select()->next_select() != 0);

  thd->lex->current_select->is_item_list_lookup= 1;
  /*
    If we have already executed SELECT, then it have not sense to prevent
    its table from update (see unique_table())
  */
  if (thd->derived_tables_processing)
    select_lex->exclude_from_table_unique_test= TRUE;

  /* Check that all tables, fields, conds and order are ok */

  if (!(select_options & OPTION_SETUP_TABLES_DONE) &&
      setup_tables_and_check_access(thd, &select_lex->context, join_list,
                                    tables_list, &conds, 
                                    &select_lex->leaf_tables, FALSE, 
                                    SELECT_ACL, SELECT_ACL))
      DBUG_RETURN(-1);
 
  TABLE_LIST *table_ptr;
  for (table_ptr= select_lex->leaf_tables;
       table_ptr;
       table_ptr= table_ptr->next_leaf)
    tables++;

  if (setup_wild(thd, tables_list, fields_list, &all_fields, wild_num) ||
      select_lex->setup_ref_array(thd, og_num) ||
      setup_fields(thd, (*rref_pointer_array), fields_list, 1,
                   &all_fields, 1) ||
      setup_without_group(thd, (*rref_pointer_array), tables_list,
                          select_lex->leaf_tables, fields_list,
                          all_fields, &conds, order, group_list,
                          &hidden_group_fields))
    DBUG_RETURN(-1);                            /* purecov: inspected */

  ref_pointer_array= *rref_pointer_array;
  
  if (having)
  {
    nesting_map save_allow_sum_func= thd->lex->allow_sum_func;
    thd->where="having clause";
    thd->lex->allow_sum_func|= 1 << select_lex_arg->nest_level;
    select_lex->having_fix_field= 1;
    bool having_fix_rc= (!having->fixed &&
                         (having->fix_fields(thd, &having) ||
                          having->check_cols(1)));
    select_lex->having_fix_field= 0;
    if (having_fix_rc || thd->net.report_error)
      DBUG_RETURN(-1);                          /* purecov: inspected */
    thd->lex->allow_sum_func= save_allow_sum_func;
  }

  if (!thd->lex->view_prepare_mode)
  {
    Item_subselect *subselect;
    /* Is it subselect? */
    if ((subselect= select_lex->master_unit()->item))
    {
      Item_subselect::trans_res res;
      if ((res= subselect->select_transformer(this)) !=
          Item_subselect::RES_OK)
      {
        select_lex->fix_prepare_information(thd, &conds, &having);
        DBUG_RETURN((res == Item_subselect::RES_ERROR));
      }
    }
  }

  select_lex->fix_prepare_information(thd, &conds, &having);

  if (order)
  {
    ORDER *ord;
    for (ord= order; ord; ord= ord->next)
    {
      Item *item= *ord->item;
      if (item->with_sum_func && item->type() != Item::SUM_FUNC_ITEM)
        item->split_sum_func(thd, ref_pointer_array, all_fields);
    }
  }

  if (having && having->with_sum_func)
    having->split_sum_func2(thd, ref_pointer_array, all_fields,
                            &having, TRUE);
  if (select_lex->inner_sum_func_list)
  {
    Item_sum *end=select_lex->inner_sum_func_list;
    Item_sum *item_sum= end;  
    do
    { 
      item_sum= item_sum->next;
      item_sum->split_sum_func2(thd, ref_pointer_array,
                                all_fields, item_sum->ref_by, FALSE);
    } while (item_sum != end);
  }

  if (select_lex->inner_refs_list.elements &&
      fix_inner_refs(thd, all_fields, select_lex, ref_pointer_array))
    DBUG_RETURN(-1);

  if (group_list)
  {
    /*
      Because HEAP tables can't index BIT fields we need to use an
      additional hidden field for grouping because later it will be
      converted to a LONG field. Original field will remain of the
      BIT type and will be returned to a client.
    */
    for (ORDER *ord= group_list; ord; ord= ord->next)
    {
      if ((*ord->item)->type() == Item::FIELD_ITEM &&
          (*ord->item)->field_type() == MYSQL_TYPE_BIT)
      {
        Item_field *field= new Item_field(thd, *(Item_field**)ord->item);
        int el= all_fields.elements;
        ref_pointer_array[el]= field;
        all_fields.push_front(field);
        ord->item= ref_pointer_array + el;
      }
    }
  }

  if (setup_ftfuncs(select_lex)) /* should be after having->fix_fields */
    DBUG_RETURN(-1);
  

  /*
    Check if one one uses a not constant column with group functions
    and no GROUP BY.
    TODO:  Add check of calculation of GROUP functions and fields:
           SELECT COUNT(*)+table.col1 from table1;
  */
  {
    if (!group_list)
    {
      uint flag=0;
      List_iterator_fast<Item> it(fields_list);
      Item *item;
      while ((item= it++))
      {
        if (item->with_sum_func)
          flag|=1;
        else if (!(flag & 2) && !item->const_during_execution())
          flag|=2;
      }
      if (flag == 3)
      {
        my_message(ER_MIX_OF_GROUP_FUNC_AND_FIELDS,
                   ER(ER_MIX_OF_GROUP_FUNC_AND_FIELDS), MYF(0));
        DBUG_RETURN(-1);
      }
    }
  }
  {
    /* Caclulate the number of groups */
    send_group_parts= 0;
    for (ORDER *group_tmp= group_list ; group_tmp ; group_tmp= group_tmp->next)
      send_group_parts++;
  }
  
  procedure= setup_procedure(thd, proc_param, result, fields_list, &error);
  if (error)
    goto err;                                   /* purecov: inspected */
  if (procedure)
  {
    if (setup_new_fields(thd, fields_list, all_fields,
                         procedure->param_fields))
        goto err;                               /* purecov: inspected */
    if (procedure->group)
    {
      if (!test_if_subpart(procedure->group,group_list))
      {                                         /* purecov: inspected */
        my_message(ER_DIFF_GROUPS_PROC, ER(ER_DIFF_GROUPS_PROC),
                   MYF(0));                     /* purecov: inspected */
        goto err;                               /* purecov: inspected */
      }
    }
#ifdef NOT_NEEDED
    else if (!group_list && procedure->flags & PROC_GROUP)
    {
      my_message(ER_NO_GROUP_FOR_PROC, MYF(0));
      goto err;
    }
#endif
    if (order && (procedure->flags & PROC_NO_SORT))
    {                                           /* purecov: inspected */
      my_message(ER_ORDER_WITH_PROC, ER(ER_ORDER_WITH_PROC),
                 MYF(0));                       /* purecov: inspected */
      goto err;                                 /* purecov: inspected */
    }
  }

  if (!procedure && result && result->prepare(fields_list, unit_arg))
    goto err;                                   /* purecov: inspected */

  /* Init join struct */
  count_field_types(select_lex, &tmp_table_param, all_fields, 0);
  ref_pointer_array_size= all_fields.elements*sizeof(Item*);
  this->group= group_list != 0;
  unit= unit_arg;

#ifdef RESTRICTED_GROUP
  if (sum_func_count && !group_list && (func_count || field_count))
  {
    my_message(ER_WRONG_SUM_SELECT,ER(ER_WRONG_SUM_SELECT),MYF(0));
    goto err;
  }
#endif
  if (select_lex->olap == ROLLUP_TYPE && rollup_init())
    goto err;
  if (alloc_func_list())
    goto err;

  DBUG_RETURN(0); // All OK

err:
  delete procedure;                             /* purecov: inspected */
  procedure= 0;
  DBUG_RETURN(-1);                              /* purecov: inspected */
}


/*
  Remove the predicates pushed down into the subquery

  SYNOPSIS
    JOIN::remove_subq_pushed_predicates()
      where   IN  Must be NULL
              OUT The remaining WHERE condition, or NULL

  DESCRIPTION
    Given that this join will be executed using (unique|index)_subquery,
    without "checking NULL", remove the predicates that were pushed down
    into the subquery.

    We can remove the equalities that will be guaranteed to be true by the
    fact that subquery engine will be using index lookup.

    If the subquery compares scalar values, we can remove the condition that
    was wrapped into trig_cond (it will be checked when needed by the subquery
    engine)

    If the subquery compares row values, we need to keep the wrapped
    equalities in the WHERE clause: when the left (outer) tuple has both NULL
    and non-NULL values, we'll do a full table scan and will rely on the
    equalities corresponding to non-NULL parts of left tuple to filter out
    non-matching records.
*/

void JOIN::remove_subq_pushed_predicates(Item **where)
{
  if (conds->type() == Item::FUNC_ITEM &&
      ((Item_func *)this->conds)->functype() == Item_func::EQ_FUNC &&
      ((Item_func *)conds)->arguments()[0]->type() == Item::REF_ITEM &&
      ((Item_func *)conds)->arguments()[1]->type() == Item::FIELD_ITEM)
  {
    *where= 0;
    return;
  }
  if (conds->type() == Item::COND_ITEM &&
      ((class Item_func *)this->conds)->functype() ==
      Item_func::COND_AND_FUNC)
  {
    *where= remove_additional_cond(conds);
  }
}


/*
  Index lookup-based subquery: save some flags for EXPLAIN output

  SYNOPSIS
    save_index_subquery_explain_info()
      join_tab  Subquery's join tab (there is only one as index lookup is
                only used for subqueries that are single-table SELECTs)
      where     Subquery's WHERE clause

  DESCRIPTION
    For index lookup-based subquery (i.e. one executed with
    subselect_uniquesubquery_engine or subselect_indexsubquery_engine),
    check its EXPLAIN output row should contain 
      "Using index" (TAB_INFO_FULL_SCAN_ON_NULL) 
      "Using Where" (TAB_INFO_USING_WHERE)
      "Full scan on NULL key" (TAB_INFO_FULL_SCAN_ON_NULL)
    and set appropriate flags in join_tab->packed_info.
*/

static void save_index_subquery_explain_info(JOIN_TAB *join_tab, Item* where)
{
  join_tab->packed_info= TAB_INFO_HAVE_VALUE;
  if (join_tab->table->used_keys.is_set(join_tab->ref.key))
    join_tab->packed_info |= TAB_INFO_USING_INDEX;
  if (where)
    join_tab->packed_info |= TAB_INFO_USING_WHERE;
  for (uint i = 0; i < join_tab->ref.key_parts; i++)
  {
    if (join_tab->ref.cond_guards[i])
    {
      join_tab->packed_info |= TAB_INFO_FULL_SCAN_ON_NULL;
      break;
    }
  }
}


/*
  global select optimisation.
  return 0 - success
         1 - error
  error code saved in field 'error'
*/

int
JOIN::optimize()
{
  DBUG_ENTER("JOIN::optimize");
  // to prevent double initialization on EXPLAIN
  if (optimized)
    DBUG_RETURN(0);
  optimized= 1;

  if (thd->lex->orig_sql_command != SQLCOM_SHOW_STATUS)
    thd->status_var.last_query_cost= 0.0;

  thd_proc_info(thd, "optimizing");
  row_limit= ((select_distinct || order || group_list) ? HA_POS_ERROR :
              unit->select_limit_cnt);
  /* select_limit is used to decide if we are likely to scan the whole table */
  select_limit= unit->select_limit_cnt;
  if (having || (select_options & OPTION_FOUND_ROWS))
    select_limit= HA_POS_ERROR;
  do_send_rows = (unit->select_limit_cnt) ? 1 : 0;
  // Ignore errors of execution if option IGNORE present
  if (thd->lex->ignore)
    thd->lex->current_select->no_error= 1;
#ifdef HAVE_REF_TO_FIELDS                       // Not done yet
  /* Add HAVING to WHERE if possible */
  if (having && !group_list && !sum_func_count)
  {
    if (!conds)
    {
      conds= having;
      having= 0;
    }
    else if ((conds=new Item_cond_and(conds,having)))
    {
      /*
        Item_cond_and can't be fixed after creation, so we do not check
        conds->fixed
      */
      conds->fix_fields(thd, &conds);
      conds->change_ref_to_fields(thd, tables_list);
      conds->top_level_item();
      having= 0;
    }
  }
#endif
  SELECT_LEX *sel= thd->lex->current_select;
  if (sel->first_cond_optimization)
  {
    /*
      The following code will allocate the new items in a permanent
      MEMROOT for prepared statements and stored procedures.
    */

    Query_arena *arena= thd->stmt_arena, backup;
    if (arena->is_conventional())
      arena= 0;                                   // For easier test
    else
      thd->set_n_backup_active_arena(arena, &backup);

    sel->first_cond_optimization= 0;

    /* Convert all outer joins to inner joins if possible */
    conds= simplify_joins(this, join_list, conds, TRUE);
    build_bitmap_for_nested_joins(join_list, 0);

    sel->prep_where= conds ? conds->copy_andor_structure(thd) : 0;

    if (arena)
      thd->restore_active_arena(arena, &backup);
  }

  conds= optimize_cond(this, conds, join_list, &cond_value);   
  if (thd->net.report_error)
  {
    error= 1;
    DBUG_PRINT("error",("Error from optimize_cond"));
    DBUG_RETURN(1);
  }

  {
    having= optimize_cond(this, having, join_list, &having_value);
    if (thd->net.report_error)
    {
      error= 1;
      DBUG_PRINT("error",("Error from optimize_cond"));
      DBUG_RETURN(1);
    }
    if (select_lex->where)
      select_lex->cond_value= cond_value;
    if (select_lex->having)
      select_lex->having_value= having_value;

    if (cond_value == Item::COND_FALSE || having_value == Item::COND_FALSE || 
        (!unit->select_limit_cnt && !(select_options & OPTION_FOUND_ROWS)))
    {                                           /* Impossible cond */
      DBUG_PRINT("info", (having_value == Item::COND_FALSE ? 
                            "Impossible HAVING" : "Impossible WHERE"));
      zero_result_cause=  having_value == Item::COND_FALSE ?
                           "Impossible HAVING" : "Impossible WHERE";
      error= 0;
      DBUG_RETURN(0);
    }
  }

  /* Optimize count(*), min() and max() */
  if (tables_list && tmp_table_param.sum_func_count && ! group_list)
  {
    int res;
    /*
      opt_sum_query() returns HA_ERR_KEY_NOT_FOUND if no rows match
      to the WHERE conditions,
      or 1 if all items were resolved,
      or 0, or an error number HA_ERR_...
    */
    if ((res=opt_sum_query(select_lex->leaf_tables, all_fields, conds)))
    {
      if (res == HA_ERR_KEY_NOT_FOUND)
      {
        DBUG_PRINT("info",("No matching min/max row"));
        zero_result_cause= "No matching min/max row";
        error=0;
        DBUG_RETURN(0);
      }
      if (res > 1)
      {
        thd->fatal_error();
        error= res;
        DBUG_PRINT("error",("Error from opt_sum_query"));
        DBUG_RETURN(1);
      }
      if (res < 0)
      {
        DBUG_PRINT("info",("No matching min/max row"));
        zero_result_cause= "No matching min/max row";
        error=0;
        DBUG_RETURN(0);
      }
      DBUG_PRINT("info",("Select tables optimized away"));
      zero_result_cause= "Select tables optimized away";
      tables_list= 0;                           // All tables resolved
      /*
        Extract all table-independent conditions and replace the WHERE
        clause with them. All other conditions were computed by opt_sum_query
        and the MIN/MAX/COUNT function(s) have been replaced by constants,
        so there is no need to compute the whole WHERE clause again.
        Notice that make_cond_for_table() will always succeed to remove all
        computed conditions, because opt_sum_query() is applicable only to
        conjunctions.
        Preserve conditions for EXPLAIN.
      */
      if (conds && !(thd->lex->describe & DESCRIBE_EXTENDED))
      {
        COND *table_independent_conds=
          make_cond_for_table(conds, PSEUDO_TABLE_BITS, 0);
        DBUG_EXECUTE("where",
                     print_where(table_independent_conds,
                                 "where after opt_sum_query()"););
        conds= table_independent_conds;
      }
    }
  }
  if (!tables_list)
  {
    DBUG_PRINT("info",("No tables"));
    error= 0;
    DBUG_RETURN(0);
  }
  error= -1;                                    // Error is sent to client
  sort_by_table= get_sort_by_table(order, group_list, select_lex->leaf_tables);

  /* Calculate how to do the join */
  thd_proc_info(thd, "statistics");
  if (make_join_statistics(this, select_lex->leaf_tables, conds, &keyuse) ||
      thd->is_fatal_error)
  {
    DBUG_PRINT("error",("Error: make_join_statistics() failed"));
    DBUG_RETURN(1);
  }

  /* Remove distinct if only const tables */
  select_distinct= select_distinct && (const_tables != tables);
  thd_proc_info(thd, "preparing");
  if (result->initialize_tables(this))
  {
    DBUG_PRINT("error",("Error: initialize_tables() failed"));
    DBUG_RETURN(1);                             // error == -1
  }
  if (const_table_map != found_const_table_map &&
      !(select_options & SELECT_DESCRIBE) &&
      (!conds ||
       !(conds->used_tables() & RAND_TABLE_BIT) ||
       select_lex->master_unit() == &thd->lex->unit)) // upper level SELECT
  {
    zero_result_cause= "no matching row in const table";
    DBUG_PRINT("error",("Error: %s", zero_result_cause));
    error= 0;
    DBUG_RETURN(0);
  }
  if (!(thd->options & OPTION_BIG_SELECTS) &&
      best_read > (double) thd->variables.max_join_size &&
      !(select_options & SELECT_DESCRIBE))
  {                                             /* purecov: inspected */
    my_message(ER_TOO_BIG_SELECT, ER(ER_TOO_BIG_SELECT), MYF(0));
    error= -1;
    DBUG_RETURN(1);
  }
  if (const_tables && !thd->locked_tables &&
      !(select_options & SELECT_NO_UNLOCK))
    mysql_unlock_some_tables(thd, table, const_tables);
  if (!conds && outer_join)
  {
    /* Handle the case where we have an OUTER JOIN without a WHERE */
    conds=new Item_int((longlong) 1,1); // Always true
  }
  select= make_select(*table, const_table_map,
                      const_table_map, conds, 1, &error);
  if (error)
  {                                             /* purecov: inspected */
    error= -1;                                  /* purecov: inspected */
    DBUG_PRINT("error",("Error: make_select() failed"));
    DBUG_RETURN(1);
  }
  
  reset_nj_counters(join_list);
  make_outerjoin_info(this);

  /*
    Among the equal fields belonging to the same multiple equality
    choose the one that is to be retrieved first and substitute
    all references to these in where condition for a reference for
    the selected field.
  */
  if (conds)
  {
    conds= substitute_for_best_equal_field(conds, cond_equal, map2table);
    conds->update_used_tables();
    DBUG_EXECUTE("where", print_where(conds, "after substitute_best_equal"););
  }

  /*
    Permorm the the optimization on fields evaluation mentioned above
    for all on expressions.
  */ 
  for (JOIN_TAB *tab= join_tab + const_tables; tab < join_tab + tables ; tab++)
  {
    if (*tab->on_expr_ref)
    {
      *tab->on_expr_ref= substitute_for_best_equal_field(*tab->on_expr_ref,
                                                         tab->cond_equal,
                                                         map2table);
      (*tab->on_expr_ref)->update_used_tables();
    }
  }

  if (conds &&!outer_join && const_table_map != found_const_table_map && 
      (select_options & SELECT_DESCRIBE) &&
      select_lex->master_unit() == &thd->lex->unit) // upper level SELECT
  {
    conds=new Item_int((longlong) 0,1); // Always false
  }
  if (make_join_select(this, select, conds))
  {
    zero_result_cause=
      "Impossible WHERE noticed after reading const tables";
    DBUG_RETURN(0);                             // error == 0
  }

  error= -1;                                    /* if goto err */

  /* Optimize distinct away if possible */
  {
    ORDER *org_order= order;
    order=remove_const(this, order,conds,1, &simple_order);
    if (thd->net.report_error)
    {
      error= 1;
      DBUG_PRINT("error",("Error from remove_const"));
      DBUG_RETURN(1);
    }

    /*
      If we are using ORDER BY NULL or ORDER BY const_expression,
      return result in any order (even if we are using a GROUP BY)
    */
    if (!order && org_order)
      skip_sort_order= 1;
  }
  /*
     Check if we can optimize away GROUP BY/DISTINCT.
     We can do that if there are no aggregate functions, the
     fields in DISTINCT clause (if present) and/or columns in GROUP BY
     (if present) contain direct references to all key parts of
     an unique index (in whatever order) and if the key parts of the
     unique index cannot contain NULLs.
     Note that the unique keys for DISTINCT and GROUP BY should not
     be the same (as long as they are unique).

     The FROM clause must contain a single non-constant table.
  */
  if (tables - const_tables == 1 && (group_list || select_distinct) &&
      !tmp_table_param.sum_func_count &&
      (!join_tab[const_tables].select ||
       !join_tab[const_tables].select->quick ||
       join_tab[const_tables].select->quick->get_type() != 
       QUICK_SELECT_I::QS_TYPE_GROUP_MIN_MAX))
  {
    if (group_list &&
       list_contains_unique_index(join_tab[const_tables].table,
                                 find_field_in_order_list,
                                 (void *) group_list))
    {
      /*
        We have found that grouping can be removed since groups correspond to
        only one row anyway, but we still have to guarantee correct result
        order. The line below effectively rewrites the query from GROUP BY
        <fields> to ORDER BY <fields>. One exception is if skip_sort_order is
        set (see above), then we can simply skip GROUP BY.
       */
      order= skip_sort_order ? 0 : group_list;
      group_list= 0;
      group= 0;
    }
    if (select_distinct &&
       list_contains_unique_index(join_tab[const_tables].table,
                                 find_field_in_item_list,
                                 (void *) &fields_list))
    {
      select_distinct= 0;
    }
  }
  if (group_list || tmp_table_param.sum_func_count)
  {
    if (! hidden_group_fields && rollup.state == ROLLUP::STATE_NONE)
      select_distinct=0;
  }
  else if (select_distinct && tables - const_tables == 1)
  {
    /*
      We are only using one table. In this case we change DISTINCT to a
      GROUP BY query if:
      - The GROUP BY can be done through indexes (no sort) and the ORDER
        BY only uses selected fields.
        (In this case we can later optimize away GROUP BY and ORDER BY)
      - We are scanning the whole table without LIMIT
        This can happen if:
        - We are using CALC_FOUND_ROWS
        - We are using an ORDER BY that can't be optimized away.

      We don't want to use this optimization when we are using LIMIT
      because in this case we can just create a temporary table that
      holds LIMIT rows and stop when this table is full.
    */
    JOIN_TAB *tab= &join_tab[const_tables];
    bool all_order_fields_used;
    if (order)
      skip_sort_order= test_if_skip_sort_order(tab, order, select_limit, 1);
    if ((group_list=create_distinct_group(thd, select_lex->ref_pointer_array,
                                          order, fields_list, all_fields,
                                          &all_order_fields_used)))
    {
      bool skip_group= (skip_sort_order &&
                        test_if_skip_sort_order(tab, group_list, select_limit,
                                                1) != 0);
      count_field_types(select_lex, &tmp_table_param, all_fields, 0);
      if ((skip_group && all_order_fields_used) ||
          select_limit == HA_POS_ERROR ||
          (order && !skip_sort_order))
      {
        /*  Change DISTINCT to GROUP BY */
        select_distinct= 0;
        no_order= !order;
        if (all_order_fields_used)
        {
          if (order && skip_sort_order)
          {
            /*
              Force MySQL to read the table in sorted order to get result in
              ORDER BY order.
            */
            tmp_table_param.quick_group=0;
          }
          order=0;
        }
        group=1;                                // For end_write_group
      }
      else
        group_list= 0;
    }
    else if (thd->is_fatal_error)                       // End of memory
      DBUG_RETURN(1);
  }
  simple_group= 0;
  {
    ORDER *old_group_list;
    group_list= remove_const(this, (old_group_list= group_list), conds,
                             rollup.state == ROLLUP::STATE_NONE,
                             &simple_group);
    if (thd->net.report_error)
    {
      error= 1;
      DBUG_PRINT("error",("Error from remove_const"));
      DBUG_RETURN(1);
    }
    if (old_group_list && !group_list)
      select_distinct= 0;
  }
  if (!group_list && group)
  {
    order=0;                                    // The output has only one row
    simple_order=1;
    select_distinct= 0;                       // No need in distinct for 1 row
    group_optimized_away= 1;
  }

  calc_group_buffer(this, group_list);
  send_group_parts= tmp_table_param.group_parts; /* Save org parts */
  if (procedure && procedure->group)
  {
    group_list= procedure->group= remove_const(this, procedure->group, conds,
                                               1, &simple_group);
    if (thd->net.report_error)
    {
      error= 1;
      DBUG_PRINT("error",("Error from remove_const"));
      DBUG_RETURN(1);
    }   
    calc_group_buffer(this, group_list);
  }

  if (test_if_subpart(group_list, order) ||
      (!group_list && tmp_table_param.sum_func_count))
    order=0;

  // Can't use sort on head table if using row cache
  if (full_join)
  {
    if (group_list)
      simple_group=0;
    if (order)
      simple_order=0;
  }

  /*
    Check if we need to create a temporary table.
    This has to be done if all tables are not already read (const tables)
    and one of the following conditions holds:
    - We are using DISTINCT (simple distinct's are already optimized away)
    - We are using an ORDER BY or GROUP BY on fields not in the first table
    - We are using different ORDER BY and GROUP BY orders
    - The user wants us to buffer the result.
  */
  need_tmp= (const_tables != tables &&
             ((select_distinct || !simple_order || !simple_group) ||
              (group_list && order) ||
              test(select_options & OPTION_BUFFER_RESULT)));

  // No cache for MATCH
  make_join_readinfo(this,
                     (select_options & (SELECT_DESCRIBE |
                                        SELECT_NO_JOIN_CACHE)) |
                     (select_lex->ftfunc_list->elements ?
                      SELECT_NO_JOIN_CACHE : 0));

  /* Perform FULLTEXT search before all regular searches */
  if (!(select_options & SELECT_DESCRIBE))
    init_ftfuncs(thd, select_lex, test(order));

  /*
    is this simple IN subquery?
  */
  if (!group_list && !order &&
      unit->item && unit->item->substype() == Item_subselect::IN_SUBS &&
      tables == 1 && conds &&
      !unit->first_select()->next_select())
  {
    if (!having)
    {
      Item *where= 0;
      if (join_tab[0].type == JT_EQ_REF &&
          join_tab[0].ref.items[0]->name == in_left_expr_name)
      {
        remove_subq_pushed_predicates(&where);
        save_index_subquery_explain_info(join_tab, where);
        join_tab[0].type= JT_UNIQUE_SUBQUERY;
        error= 0;
        DBUG_RETURN(unit->item->
                    change_engine(new
                                  subselect_uniquesubquery_engine(thd,
                                                                  join_tab,
                                                                  unit->item,
                                                                  where)));
      }
      else if (join_tab[0].type == JT_REF &&
               join_tab[0].ref.items[0]->name == in_left_expr_name)
      {
        remove_subq_pushed_predicates(&where);
        save_index_subquery_explain_info(join_tab, where);
        join_tab[0].type= JT_INDEX_SUBQUERY;
        error= 0;
        DBUG_RETURN(unit->item->
                    change_engine(new
                                  subselect_indexsubquery_engine(thd,
                                                                 join_tab,
                                                                 unit->item,
                                                                 where,
                                                                 NULL,
                                                                 0)));
      }
    } else if (join_tab[0].type == JT_REF_OR_NULL &&
               join_tab[0].ref.items[0]->name == in_left_expr_name &&
               having->name == in_having_cond)
    {
      join_tab[0].type= JT_INDEX_SUBQUERY;
      error= 0;
      conds= remove_additional_cond(conds);
      save_index_subquery_explain_info(join_tab, conds);
      DBUG_RETURN(unit->item->
                  change_engine(new subselect_indexsubquery_engine(thd,
                                                                   join_tab,
                                                                   unit->item,
                                                                   conds,
                                                                   having,
                                                                   1)));
    }

  }
  /*
    Need to tell Innobase that to play it safe, it should fetch all
    columns of the tables: this is because MySQL may build row
    pointers for the rows, and for all columns of the primary key the
    field->query_id has not necessarily been set to thd->query_id by
    MySQL.
  */

#ifdef HAVE_INNOBASE_DB
  if (need_tmp || select_distinct || group_list || order)
  {
    for (uint i_h = const_tables; i_h < tables; i_h++)
    {
      TABLE* table_h = join_tab[i_h].table;
      table_h->file->extra(HA_EXTRA_RETRIEVE_PRIMARY_KEY);
    }
  }
#endif

  DBUG_EXECUTE("info",TEST_join(this););

  if (const_tables != tables)
  {
    /*
      Because filesort always does a full table scan or a quick range scan
      we must add the removed reference to the select for the table.
      We only need to do this when we have a simple_order or simple_group
      as in other cases the join is done before the sort.
    */
    if ((order || group_list) &&
        join_tab[const_tables].type != JT_ALL &&
        join_tab[const_tables].type != JT_FT &&
        join_tab[const_tables].type != JT_REF_OR_NULL &&
        (order && simple_order || group_list && simple_group))
    {
      if (add_ref_to_table_cond(thd,&join_tab[const_tables])) {
        DBUG_RETURN(1);
      }
    }
    
    if (!(select_options & SELECT_BIG_RESULT) &&
        ((group_list &&
          (!simple_group ||
           !test_if_skip_sort_order(&join_tab[const_tables], group_list,
                                    unit->select_limit_cnt, 0))) ||
         select_distinct) &&
        tmp_table_param.quick_group && !procedure)
    {
      need_tmp=1; simple_order=simple_group=0;  // Force tmp table without sort
    }
    if (order)
    {
      /*
        Force using of tmp table if sorting by a SP or UDF function due to
        their expensive and probably non-deterministic nature.
      */
      for (ORDER *tmp_order= order; tmp_order ; tmp_order=tmp_order->next)
      {
        Item *item= *tmp_order->item;
        if (item->walk(&Item::is_expensive_processor,(byte*)0))
        {
          /* Force tmp table without sort */
          need_tmp=1; simple_order=simple_group=0;
          break;
        }
      }
    }
  }

  tmp_having= having;
  if (select_options & SELECT_DESCRIBE)
  {
    error= 0;
    DBUG_RETURN(0);
  }
  having= 0;

  /*
    The loose index scan access method guarantees that all grouping or
    duplicate row elimination (for distinct) is already performed
    during data retrieval, and that all MIN/MAX functions are already
    computed for each group. Thus all MIN/MAX functions should be
    treated as regular functions, and there is no need to perform
    grouping in the main execution loop.
    Notice that currently loose index scan is applicable only for
    single table queries, thus it is sufficient to test only the first
    join_tab element of the plan for its access method.
  */
  if (join_tab->is_using_loose_index_scan())
    tmp_table_param.precomputed_group_by= TRUE;

  /* Create a tmp table if distinct or if the sort is too complicated */
  if (need_tmp)
  {
    DBUG_PRINT("info",("Creating tmp table"));
    thd_proc_info(thd, "Creating tmp table");

    init_items_ref_array();

    tmp_table_param.hidden_field_count= (all_fields.elements -
                                         fields_list.elements);
    ORDER *tmp_group= ((!simple_group && !procedure &&
                        !(test_flags & TEST_NO_KEY_GROUP)) ? group_list :
                                                             (ORDER*) 0);
    /*
      Pushing LIMIT to the temporary table creation is not applicable
      when there is ORDER BY or GROUP BY or there is no GROUP BY, but
      there are aggregate functions, because in all these cases we need
      all result rows.
    */
    ha_rows tmp_rows_limit= ((order == 0 || skip_sort_order) &&
                             !tmp_group &&
                             !thd->lex->current_select->with_sum_func) ?
                            select_limit : HA_POS_ERROR;

    if (!(exec_tmp_table1 =
          create_tmp_table(thd, &tmp_table_param, all_fields,
                           tmp_group,
                           group_list ? 0 : select_distinct,
                           group_list && simple_group,
                           select_options,
                           tmp_rows_limit,
                           (char *) "")))
                {
      DBUG_RETURN(1);
    }

    /*
      We don't have to store rows in temp table that doesn't match HAVING if:
      - we are sorting the table and writing complete group rows to the
        temp table.
      - We are using DISTINCT without resolving the distinct as a GROUP BY
        on all columns.
      
      If having is not handled here, it will be checked before the row
      is sent to the client.
    */    
    if (tmp_having && 
        (sort_and_group || (exec_tmp_table1->distinct && !group_list)))
      having= tmp_having;

    /* if group or order on first table, sort first */
    if (group_list && simple_group)
    {
      DBUG_PRINT("info",("Sorting for group"));
      thd_proc_info(thd, "Sorting for group");
      if (create_sort_index(thd, this, group_list,
                            HA_POS_ERROR, HA_POS_ERROR) ||
          alloc_group_fields(this, group_list) ||
          make_sum_func_list(all_fields, fields_list, 1) ||
          setup_sum_funcs(thd, sum_funcs))
      {
        DBUG_RETURN(1);
      }
      group_list=0;
    }
    else
    {
      if (make_sum_func_list(all_fields, fields_list, 0) ||
          setup_sum_funcs(thd, sum_funcs))
      {
        DBUG_RETURN(1);
      }

      if (!group_list && ! exec_tmp_table1->distinct && order && simple_order)
      {
        thd_proc_info(thd, "Sorting for order");
        if (create_sort_index(thd, this, order,
                              HA_POS_ERROR, HA_POS_ERROR))
        {
          DBUG_RETURN(1);
        }
        order=0;
      }
    }
    
    /*
      Optimize distinct when used on some of the tables
      SELECT DISTINCT t1.a FROM t1,t2 WHERE t1.b=t2.b
      In this case we can stop scanning t2 when we have found one t1.a
    */

    if (exec_tmp_table1->distinct)
    {
      table_map used_tables= thd->used_tables;
      JOIN_TAB *last_join_tab= join_tab+tables-1;
      do
      {
        if (used_tables & last_join_tab->table->map)
          break;
        last_join_tab->not_used_in_distinct=1;
      } while (last_join_tab-- != join_tab);
      /* Optimize "select distinct b from t1 order by key_part_1 limit #" */
      if (order && skip_sort_order)
      {
        /* Should always succeed */
        if (test_if_skip_sort_order(&join_tab[const_tables],
                                    order, unit->select_limit_cnt, 0))
          order=0;
      }
    }

    /* 
      If this join belongs to an uncacheable subquery save 
      the original join 
    */
    if (select_lex->uncacheable && !is_top_level_join() &&
        init_save_join_tab())
      DBUG_RETURN(-1);                         /* purecov: inspected */
  }

#ifdef ENABLE_SENNA
  if (my_thread_var->sen_flags & SENNA_USE_2IND)
    DEBUG_2IND(my_thread_var->sen_flags |= SENNA_FIRST_CALL);
#endif /* ENABLE_SENNA */

  error= 0;
  DBUG_RETURN(0);
}


/*
  Restore values in temporary join
*/
void JOIN::restore_tmp()
{
  memcpy(tmp_join, this, (size_t) sizeof(JOIN));
}


int
JOIN::reinit()
{
  DBUG_ENTER("JOIN::reinit");

  unit->offset_limit_cnt= (ha_rows)(select_lex->offset_limit ?
                                    select_lex->offset_limit->val_uint() :
                                    ULL(0));

  first_record= 0;

  if (exec_tmp_table1)
  {
    exec_tmp_table1->file->extra(HA_EXTRA_RESET_STATE);
    exec_tmp_table1->file->delete_all_rows();
    free_io_cache(exec_tmp_table1);
    filesort_free_buffers(exec_tmp_table1,0);
  }
  if (exec_tmp_table2)
  {
    exec_tmp_table2->file->extra(HA_EXTRA_RESET_STATE);
    exec_tmp_table2->file->delete_all_rows();
    free_io_cache(exec_tmp_table2);
    filesort_free_buffers(exec_tmp_table2,0);
  }
  if (items0)
    set_items_ref_array(items0);

  if (join_tab_save)
    memcpy(join_tab, join_tab_save, sizeof(JOIN_TAB) * tables);

  if (tmp_join)
    restore_tmp();

  /* Reset of sum functions */
  if (sum_funcs)
  {
    Item_sum *func, **func_ptr= sum_funcs;
    while ((func= *(func_ptr++)))
      func->clear();
  }

  DBUG_RETURN(0);
}

/**
   @brief Save the original join layout
      
   @details Saves the original join layout so it can be reused in 
   re-execution and for EXPLAIN.
             
   @return Operation status
   @retval 0      success.
   @retval 1      error occurred.
*/

bool
JOIN::init_save_join_tab()
{
  if (!(tmp_join= (JOIN*)thd->alloc(sizeof(JOIN))))
    return 1;                                  /* purecov: inspected */
  error= 0;                                    // Ensure that tmp_join.error= 0
  restore_tmp();
  return 0;
}


bool
JOIN::save_join_tab()
{
  if (!join_tab_save && select_lex->master_unit()->uncacheable)
  {
    if (!(join_tab_save= (JOIN_TAB*)thd->memdup((gptr) join_tab,
                                                sizeof(JOIN_TAB) * tables)))
      return 1;
  }
  return 0;
}


/*
  Exec select
*/
void
JOIN::exec()
{
  List<Item> *columns_list= &fields_list;
  int      tmp_error;
  DBUG_ENTER("JOIN::exec");

  thd_proc_info(thd, "executing");
  error= 0;
  if (procedure)
  {
    procedure_fields_list= fields_list;
    if (procedure->change_columns(procedure_fields_list) ||
        result->prepare(procedure_fields_list, unit))
    {
      thd->limit_found_rows= thd->examined_row_count= 0;
      DBUG_VOID_RETURN;
    }
    columns_list= &procedure_fields_list;
  }
  (void) result->prepare2(); // Currently, this cannot fail.

  if (!tables_list && (tables || !select_lex->with_sum_func))
  {                                           // Only test of functions
    if (select_options & SELECT_DESCRIBE)
      select_describe(this, FALSE, FALSE, FALSE,
                      (zero_result_cause?zero_result_cause:"No tables used"));
    else
    {
      result->send_fields(*columns_list,
                          Protocol::SEND_NUM_ROWS | Protocol::SEND_EOF);
      /*
        We have to test for 'conds' here as the WHERE may not be constant
        even if we don't have any tables for prepared statements or if
        conds uses something like 'rand()'.
      */
      if (cond_value != Item::COND_FALSE &&
          (!conds || conds->val_int()) &&
          (!having || having->val_int()))
      {
        if (do_send_rows &&
            (procedure ? (procedure->send_row(procedure_fields_list) ||
             procedure->end_of_records()) : result->send_data(fields_list)))
          error= 1;
        else
        {
          error= (int) result->send_eof();
          send_records= ((select_options & OPTION_FOUND_ROWS) ? 1 :
                         thd->sent_row_count);
        }
      }
      else
      {
        error=(int) result->send_eof();
        send_records= 0;
      }
    }
    /* Single select (without union) always returns 0 or 1 row */
    thd->limit_found_rows= send_records;
    thd->examined_row_count= 0;
    DBUG_VOID_RETURN;
  }
  /*
    Don't reset the found rows count if there're no tables as
    FOUND_ROWS() may be called. Never reset the examined row count here.
    It must be accumulated from all join iterations of all join parts.
  */
  if (tables)
    thd->limit_found_rows= 0;

  if (zero_result_cause)
  {
    (void) return_zero_rows(this, result, select_lex->leaf_tables,
                            *columns_list,
                            send_row_on_empty_set(),
                            select_options,
                            zero_result_cause,
                            having);
    DBUG_VOID_RETURN;
  }

  if (select_options & SELECT_DESCRIBE)
  {
    /*
      Check if we managed to optimize ORDER BY away and don't use temporary
      table to resolve ORDER BY: in that case, we only may need to do
      filesort for GROUP BY.
    */
    if (!order && !no_order && (!skip_sort_order || !need_tmp))
    {
      /*
        Reset 'order' to 'group_list' and reinit variables describing
        'order'
      */
      order= group_list;
      simple_order= simple_group;
      skip_sort_order= 0;
    }
    if (order && 
        (order != group_list || !(select_options & SELECT_BIG_RESULT)) &&
        (const_tables == tables ||
         ((simple_order || skip_sort_order) &&
          test_if_skip_sort_order(&join_tab[const_tables], order,
                                  select_limit, 0))))
      order=0;
    having= tmp_having;
    select_describe(this, need_tmp,
                    order != 0 && !skip_sort_order,
                    select_distinct,
                    !tables ? "No tables used" : NullS);
    DBUG_VOID_RETURN;
  }

  JOIN *curr_join= this;
  List<Item> *curr_all_fields= &all_fields;
  List<Item> *curr_fields_list= &fields_list;
  TABLE *curr_tmp_table= 0;
  /*
    Initialize examined rows here because the values from all join parts
    must be accumulated in examined_row_count. Hence every join
    iteration must count from zero.
  */
  curr_join->examined_rows= 0;

  if ((curr_join->select_lex->options & OPTION_SCHEMA_TABLE) &&
      !thd->lex->describe &&
      get_schema_tables_result(curr_join, PROCESSED_BY_JOIN_EXEC))
  {
    DBUG_VOID_RETURN;
  }

  /* Create a tmp table if distinct or if the sort is too complicated */
  if (need_tmp)
  {
    if (tmp_join)
    {
      /*
        We are in a non cacheable sub query. Get the saved join structure
        after optimization.
        (curr_join may have been modified during last exection and we need
        to reset it)
      */
      curr_join= tmp_join;
    }
    curr_tmp_table= exec_tmp_table1;

    /* Copy data to the temporary table */
    thd_proc_info(thd, "Copying to tmp table");
    DBUG_PRINT("info", ("%s", thd->proc_info));
    if ((tmp_error= do_select(curr_join, (List<Item> *) 0, curr_tmp_table, 0)))
    {
      error= tmp_error;
      DBUG_VOID_RETURN;
    }
    curr_tmp_table->file->info(HA_STATUS_VARIABLE);
    
    if (curr_join->having)
      curr_join->having= curr_join->tmp_having= 0; // Allready done
    
    /* Change sum_fields reference to calculated fields in tmp_table */
    curr_join->all_fields= *curr_all_fields;
    if (!items1)
    {
      items1= items0 + all_fields.elements;
      if (sort_and_group || curr_tmp_table->group)
      {
        if (change_to_use_tmp_fields(thd, items1,
                                     tmp_fields_list1, tmp_all_fields1,
                                     fields_list.elements, all_fields))
          DBUG_VOID_RETURN;
      }
      else
      {
        if (change_refs_to_tmp_fields(thd, items1,
                                      tmp_fields_list1, tmp_all_fields1,
                                      fields_list.elements, all_fields))
          DBUG_VOID_RETURN;
      }
      curr_join->tmp_all_fields1= tmp_all_fields1;
      curr_join->tmp_fields_list1= tmp_fields_list1;
      curr_join->items1= items1;
    }
    curr_all_fields= &tmp_all_fields1;
    curr_fields_list= &tmp_fields_list1;
    curr_join->set_items_ref_array(items1);
    
    if (sort_and_group || curr_tmp_table->group)
    {
      curr_join->tmp_table_param.field_count+= 
        curr_join->tmp_table_param.sum_func_count+
        curr_join->tmp_table_param.func_count;
      curr_join->tmp_table_param.sum_func_count= 
        curr_join->tmp_table_param.func_count= 0;
    }
    else
    {
      curr_join->tmp_table_param.field_count+= 
        curr_join->tmp_table_param.func_count;
      curr_join->tmp_table_param.func_count= 0;
    }
    
    // procedure can't be used inside subselect => we do nothing special for it
    if (procedure)
      procedure->update_refs();
    
    if (curr_tmp_table->group)
    {                                           // Already grouped
      if (!curr_join->order && !curr_join->no_order && !skip_sort_order)
        curr_join->order= curr_join->group_list;  /* order by group */
      curr_join->group_list= 0;
    }
    
    /*
      If we have different sort & group then we must sort the data by group
      and copy it to another tmp table
      This code is also used if we are using distinct something
      we haven't been able to store in the temporary table yet
      like SEC_TO_TIME(SUM(...)).
    */

    if (curr_join->group_list && (!test_if_subpart(curr_join->group_list,
                                                   curr_join->order) || 
                                  curr_join->select_distinct) ||
        (curr_join->select_distinct &&
         curr_join->tmp_table_param.using_indirect_summary_function))
    {                                   /* Must copy to another table */
      DBUG_PRINT("info",("Creating group table"));
      
      /* Free first data from old join */
      curr_join->join_free();
      if (make_simple_join(curr_join, curr_tmp_table))
        DBUG_VOID_RETURN;
      calc_group_buffer(curr_join, group_list);
      count_field_types(select_lex, &curr_join->tmp_table_param,
                        curr_join->tmp_all_fields1,
                        curr_join->select_distinct && !curr_join->group_list);
      curr_join->tmp_table_param.hidden_field_count= 
        (curr_join->tmp_all_fields1.elements-
         curr_join->tmp_fields_list1.elements);
      
      
      if (exec_tmp_table2)
        curr_tmp_table= exec_tmp_table2;
      else
      {
        /* group data to new table */

        /*
          If the access method is loose index scan then all MIN/MAX
          functions are precomputed, and should be treated as regular
          functions. See extended comment in JOIN::exec.
        */
        if (curr_join->join_tab->is_using_loose_index_scan())
          curr_join->tmp_table_param.precomputed_group_by= TRUE;

        if (!(curr_tmp_table=
              exec_tmp_table2= create_tmp_table(thd,
                                                &curr_join->tmp_table_param,
                                                *curr_all_fields,
                                                (ORDER*) 0,
                                                curr_join->select_distinct && 
                                                !curr_join->group_list,
                                                1, curr_join->select_options,
                                                HA_POS_ERROR,
                                                (char *) "")))
          DBUG_VOID_RETURN;
        curr_join->exec_tmp_table2= exec_tmp_table2;
      }
      if (curr_join->group_list)
      {
        thd_proc_info(thd, "Creating sort index");
        if (curr_join->join_tab == join_tab && save_join_tab())
        {
          DBUG_VOID_RETURN;
        }
        if (create_sort_index(thd, curr_join, curr_join->group_list,
                              HA_POS_ERROR, HA_POS_ERROR) ||
            make_group_fields(this, curr_join))
        {
          DBUG_VOID_RETURN;
        }
        sortorder= curr_join->sortorder;
      }
      
      thd_proc_info(thd, "Copying to group table");
      DBUG_PRINT("info", ("%s", thd->proc_info));
      tmp_error= -1;
      if (curr_join != this)
      {
        if (sum_funcs2)
        {
          curr_join->sum_funcs= sum_funcs2;
          curr_join->sum_funcs_end= sum_funcs_end2; 
        }
        else
        {
          curr_join->alloc_func_list();
          sum_funcs2= curr_join->sum_funcs;
          sum_funcs_end2= curr_join->sum_funcs_end;
        }
      }
      if (curr_join->make_sum_func_list(*curr_all_fields, *curr_fields_list,
                                        1, TRUE))
        DBUG_VOID_RETURN;
      curr_join->group_list= 0;
      if (setup_sum_funcs(curr_join->thd, curr_join->sum_funcs) ||
          (tmp_error= do_select(curr_join, (List<Item> *) 0, curr_tmp_table,
                                0)))
      {
        error= tmp_error;
        DBUG_VOID_RETURN;
      }
      end_read_record(&curr_join->join_tab->read_record);
      curr_join->const_tables= curr_join->tables; // Mark free for cleanup()
      curr_join->join_tab[0].table= 0;           // Table is freed
      
      // No sum funcs anymore
      if (!items2)
      {
        items2= items1 + all_fields.elements;
        if (change_to_use_tmp_fields(thd, items2,
                                     tmp_fields_list2, tmp_all_fields2, 
                                     fields_list.elements, tmp_all_fields1))
          DBUG_VOID_RETURN;
        curr_join->tmp_fields_list2= tmp_fields_list2;
        curr_join->tmp_all_fields2= tmp_all_fields2;
      }
      curr_fields_list= &curr_join->tmp_fields_list2;
      curr_all_fields= &curr_join->tmp_all_fields2;
      curr_join->set_items_ref_array(items2);
      curr_join->tmp_table_param.field_count+= 
        curr_join->tmp_table_param.sum_func_count;
      curr_join->tmp_table_param.sum_func_count= 0;
    }
    if (curr_tmp_table->distinct)
      curr_join->select_distinct=0;             /* Each row is unique */
    
    curr_join->join_free();                     /* Free quick selects */
    if (curr_join->select_distinct && ! curr_join->group_list)
    {
      thd_proc_info(thd, "Removing duplicates");
      if (curr_join->tmp_having)
        curr_join->tmp_having->update_used_tables();
      if (remove_duplicates(curr_join, curr_tmp_table,
                            *curr_fields_list, curr_join->tmp_having))
        DBUG_VOID_RETURN;
      curr_join->tmp_having=0;
      curr_join->select_distinct=0;
    }
    curr_tmp_table->reginfo.lock_type= TL_UNLOCK;
    if (make_simple_join(curr_join, curr_tmp_table))
      DBUG_VOID_RETURN;
    calc_group_buffer(curr_join, curr_join->group_list);
    count_field_types(select_lex, &curr_join->tmp_table_param, 
                      *curr_all_fields, 0);
    
  }
  if (procedure)
    count_field_types(select_lex, &curr_join->tmp_table_param, 
                      *curr_all_fields, 0);
  
  if (curr_join->group || curr_join->tmp_table_param.sum_func_count ||
      (procedure && (procedure->flags & PROC_GROUP)))
  {
    if (make_group_fields(this, curr_join))
    {
      DBUG_VOID_RETURN;
    }
    if (!items3)
    {
      if (!items0)
        init_items_ref_array();
      items3= ref_pointer_array + (all_fields.elements*4);
      setup_copy_fields(thd, &curr_join->tmp_table_param,
                        items3, tmp_fields_list3, tmp_all_fields3,
                        curr_fields_list->elements, *curr_all_fields);
      tmp_table_param.save_copy_funcs= curr_join->tmp_table_param.copy_funcs;
      tmp_table_param.save_copy_field= curr_join->tmp_table_param.copy_field;
      tmp_table_param.save_copy_field_end=
        curr_join->tmp_table_param.copy_field_end;
      curr_join->tmp_all_fields3= tmp_all_fields3;
      curr_join->tmp_fields_list3= tmp_fields_list3;
    }
    else
    {
      curr_join->tmp_table_param.copy_funcs= tmp_table_param.save_copy_funcs;
      curr_join->tmp_table_param.copy_field= tmp_table_param.save_copy_field;
      curr_join->tmp_table_param.copy_field_end=
        tmp_table_param.save_copy_field_end;
    }
    curr_fields_list= &tmp_fields_list3;
    curr_all_fields= &tmp_all_fields3;
    curr_join->set_items_ref_array(items3);

    if (curr_join->make_sum_func_list(*curr_all_fields, *curr_fields_list,
                                      1, TRUE) || 
        setup_sum_funcs(curr_join->thd, curr_join->sum_funcs) ||
        thd->is_fatal_error)
      DBUG_VOID_RETURN;
  }
  if (curr_join->group_list || curr_join->order)
  {
    DBUG_PRINT("info",("Sorting for send_fields"));
    thd_proc_info(thd, "Sorting result");
    /* If we have already done the group, add HAVING to sorted table */
    if (curr_join->tmp_having && ! curr_join->group_list && 
        ! curr_join->sort_and_group)
    {
      // Some tables may have been const
      curr_join->tmp_having->update_used_tables();
      JOIN_TAB *curr_table= &curr_join->join_tab[curr_join->const_tables];
      table_map used_tables= (curr_join->const_table_map |
                              curr_table->table->map);

      Item* sort_table_cond= make_cond_for_table(curr_join->tmp_having,
                                                 used_tables,
                                                 used_tables);
      if (sort_table_cond)
      {
        if (!curr_table->select)
          if (!(curr_table->select= new SQL_SELECT))
            DBUG_VOID_RETURN;
        if (!curr_table->select->cond)
          curr_table->select->cond= sort_table_cond;
        else                                    // This should never happen
        {
          if (!(curr_table->select->cond=
                new Item_cond_and(curr_table->select->cond,
                                  sort_table_cond)))
            DBUG_VOID_RETURN;
          /*
            Item_cond_and do not need fix_fields for execution, its parameters
            are fixed or do not need fix_fields, too
          */
          curr_table->select->cond->quick_fix_field();
        }
        curr_table->select_cond= curr_table->select->cond;
        curr_table->select_cond->top_level_item();
        DBUG_EXECUTE("where",print_where(curr_table->select->cond,
                                         "select and having"););
        curr_join->tmp_having= make_cond_for_table(curr_join->tmp_having,
                                                   ~ (table_map) 0,
                                                   ~used_tables);
        DBUG_EXECUTE("where",print_where(curr_join->tmp_having,
                                         "having after sort"););
      }
    }
    {
      if (group)
        curr_join->select_limit= HA_POS_ERROR;
      else
      {
        /*
          We can abort sorting after thd->select_limit rows if we there is no
          WHERE clause for any tables after the sorted one.
        */
        JOIN_TAB *curr_table= &curr_join->join_tab[curr_join->const_tables+1];
        JOIN_TAB *end_table= &curr_join->join_tab[curr_join->tables];
        for (; curr_table < end_table ; curr_table++)
        {
          /*
            table->keyuse is set in the case there was an original WHERE clause
            on the table that was optimized away.
          */
          if (curr_table->select_cond ||
              (curr_table->keyuse && !curr_table->first_inner))
          {
            /* We have to sort all rows */
            curr_join->select_limit= HA_POS_ERROR;
            break;
          }
        }
      }
      if (curr_join->join_tab == join_tab && save_join_tab())
      {
        DBUG_VOID_RETURN;
      }
      /*
        Here we sort rows for ORDER BY/GROUP BY clause, if the optimiser
        chose FILESORT to be faster than INDEX SCAN or there is no 
        suitable index present.
        Note, that create_sort_index calls test_if_skip_sort_order and may
        finally replace sorting with index scan if there is a LIMIT clause in
        the query. XXX: it's never shown in EXPLAIN!
        OPTION_FOUND_ROWS supersedes LIMIT and is taken into account.
      */
      if (create_sort_index(thd, curr_join,
                            curr_join->group_list ? 
                            curr_join->group_list : curr_join->order,
                            curr_join->select_limit,
                            (select_options & OPTION_FOUND_ROWS ?
                             HA_POS_ERROR : unit->select_limit_cnt)))
        DBUG_VOID_RETURN;
      sortorder= curr_join->sortorder;
    }
  }
  /* XXX: When can we have here thd->net.report_error not zero? */
  if (thd->net.report_error)
  {
    error= thd->net.report_error;
    DBUG_VOID_RETURN;
  }
  curr_join->having= curr_join->tmp_having;
  curr_join->fields= curr_fields_list;
  curr_join->procedure= procedure;

#ifdef ENABLE_SENNA
  if (my_thread_var->sen_flags & SENNA_USE_2IND)
    DEBUG_2IND(my_thread_var->sen_flags &= ~SENNA_FIRST_CALL);
#endif /* ENABLE_SENNA */

  if (is_top_level_join() && thd->cursor && tables != const_tables)
  {
    /*
      We are here if this is JOIN::exec for the last select of the main unit
      and the client requested to open a cursor.
      We check that not all tables are constant because this case is not
      handled by do_select() separately, and this case is not implemented
      for cursors yet.
    */
    DBUG_ASSERT(error == 0);
    /*
      curr_join is used only for reusable joins - that is, 
      to perform SELECT for each outer row (like in subselects).
      This join is main, so we know for sure that curr_join == join.
    */
    DBUG_ASSERT(curr_join == this);
    /* Open cursor for the last join sweep */
    error= thd->cursor->open(this);
  }
  else
  {
    thd_proc_info(thd, "Sending data");
    DBUG_PRINT("info", ("%s", thd->proc_info));
    result->send_fields((procedure ? curr_join->procedure_fields_list :
                         *curr_fields_list),
                        Protocol::SEND_NUM_ROWS | Protocol::SEND_EOF);
    error= do_select(curr_join, curr_fields_list, NULL, procedure);
    thd->limit_found_rows= curr_join->send_records;
  }

  /* Accumulate the counts from all join iterations of all join parts. */
  thd->examined_row_count+= curr_join->examined_rows;
  DBUG_PRINT("counts", ("thd->examined_row_count: %lu",
                        (ulong) thd->examined_row_count));

  /* 
    With EXPLAIN EXTENDED we have to restore original ref_array
    for a derived table which is always materialized.
    Otherwise we would not be able to print the query  correctly.
  */ 
  if (items0 &&
      (thd->lex->describe & DESCRIBE_EXTENDED) &&
      select_lex->linkage == DERIVED_TABLE_TYPE)      
    set_items_ref_array(items0);

  DBUG_VOID_RETURN;
}


/*
  Clean up join. Return error that hold JOIN.
*/

int
JOIN::destroy()
{
  DBUG_ENTER("JOIN::destroy");
  select_lex->join= 0;

  if (tmp_join)
  {
    if (join_tab != tmp_join->join_tab)
    {
      JOIN_TAB *tab, *end;
      for (tab= join_tab, end= tab+tables ; tab != end ; tab++)
      {
        tab->cleanup();
      }
    }
    tmp_join->tmp_join= 0;
    tmp_table_param.copy_field=0;
    DBUG_RETURN(tmp_join->destroy());
  }
  cond_equal= 0;

  cleanup(1);
  if (exec_tmp_table1)
    free_tmp_table(thd, exec_tmp_table1);
  if (exec_tmp_table2)
    free_tmp_table(thd, exec_tmp_table2);
  delete select;
  delete_dynamic(&keyuse);
  delete procedure;
  DBUG_RETURN(error);
}

/*
  An entry point to single-unit select (a select without UNION).

  SYNOPSIS
    mysql_select()

    thd                  thread handler
    rref_pointer_array   a reference to ref_pointer_array of
                         the top-level select_lex for this query
    tables               list of all tables used in this query.
                         The tables have been pre-opened.
    wild_num             number of wildcards used in the top level 
                         select of this query.
                         For example statement
                         SELECT *, t1.*, catalog.t2.* FROM t0, t1, t2;
                         has 3 wildcards.
    fields               list of items in SELECT list of the top-level
                         select
                         e.g. SELECT a, b, c FROM t1 will have Item_field
                         for a, b and c in this list.
    conds                top level item of an expression representing
                         WHERE clause of the top level select
    og_num               total number of ORDER BY and GROUP BY clauses
                         arguments
    order                linked list of ORDER BY agruments
    group                linked list of GROUP BY arguments
    having               top level item of HAVING expression
    proc_param           list of PROCEDUREs
    select_options       select options (BIG_RESULT, etc)
    result               an instance of result set handling class.
                         This object is responsible for send result
                         set rows to the client or inserting them
                         into a table.
    select_lex           the only SELECT_LEX of this query
    unit                 top-level UNIT of this query
                         UNIT is an artificial object created by the parser
                         for every SELECT clause.
                         e.g. SELECT * FROM t1 WHERE a1 IN (SELECT * FROM t2)
                         has 2 unions.

  RETURN VALUE
   FALSE  success
   TRUE   an error
*/

bool
mysql_select(THD *thd, Item ***rref_pointer_array,
             TABLE_LIST *tables, uint wild_num, List<Item> &fields,
             COND *conds, uint og_num,  ORDER *order, ORDER *group,
             Item *having, ORDER *proc_param, ulonglong select_options,
             select_result *result, SELECT_LEX_UNIT *unit,
             SELECT_LEX *select_lex)
{
  bool err;
  bool free_join= 1;
  DBUG_ENTER("mysql_select");

  select_lex->context.resolve_in_select_list= TRUE;
  JOIN *join;
  if (select_lex->join != 0)
  {
    join= select_lex->join;
    /*
      is it single SELECT in derived table, called in derived table
      creation
    */
    if (select_lex->linkage != DERIVED_TABLE_TYPE ||
        (select_options & SELECT_DESCRIBE))
    {
      if (select_lex->linkage != GLOBAL_OPTIONS_TYPE)
      {
        //here is EXPLAIN of subselect or derived table
        if (join->change_result(result))
        {
          DBUG_RETURN(TRUE);
        }
      }
      else
      {
        if (err= join->prepare(rref_pointer_array, tables, wild_num,
                               conds, og_num, order, group, having, proc_param,
                               select_lex, unit))
        {
          goto err;
        }
      }
    }
    free_join= 0;
    join->select_options= select_options;
  }
  else
  {
    if (!(join= new JOIN(thd, fields, select_options, result)))
        DBUG_RETURN(TRUE);
    thd_proc_info(thd, "init");
    thd->used_tables=0;                         // Updated by setup_fields
    if (err= join->prepare(rref_pointer_array, tables, wild_num,
                           conds, og_num, order, group, having, proc_param,
                           select_lex, unit))
    {
      goto err;
    }
  }
#ifdef ENABLE_SENNA
  if (my_thread_var->sen_flags & SENNA_USE_2IND) {
    if (select_lex->ftfunc_list->elements) {
      DEBUG_2IND(my_thread_var->sen_flags |= SENNA_MATCH);
    }
    if (join->select_distinct) {
      DEBUG_2IND(my_thread_var->sen_flags |= SENNA_DISTINCT);
    }
  }
#endif /* ENABLE_SENNA */
  if ((err= join->optimize()))
  {
    goto err;                                   // 1
  }

  if (thd->lex->describe & DESCRIBE_EXTENDED)
  {
    join->conds_history= join->conds;
    join->having_history= (join->having?join->having:join->tmp_having);
  }

  if (thd->net.report_error)
    goto err;

  join->exec();

  if (thd->cursor && thd->cursor->is_open())
  {
    /*
      A cursor was opened for the last sweep in exec().
      We are here only if this is mysql_select for top-level SELECT_LEX_UNIT
      and there were no error.
    */
    free_join= 0;
  }

  if (thd->lex->describe & DESCRIBE_EXTENDED)
  {
    select_lex->where= join->conds_history;
    select_lex->having= join->having_history;
  }

err:
#ifdef ENABLE_SENNA
  DEBUG_2IND(my_thread_var->sen_flags &= SENNA_USE_2IND);
#endif
  if (free_join)
  {
    thd_proc_info(thd, "end");
    err|= select_lex->cleanup();
    thd_proc_info(thd, "end");
    DBUG_RETURN(err || thd->net.report_error);
  }
  DBUG_RETURN(join->error);
}

/*****************************************************************************
  Create JOIN_TABS, make a guess about the table types,
  Approximate how many records will be used in each table
*****************************************************************************/

static ha_rows get_quick_record_count(THD *thd, SQL_SELECT *select,
                                      TABLE *table,
                                      const key_map *keys,ha_rows limit)
{
  int error;
  DBUG_ENTER("get_quick_record_count");
  if (select)
  {
    select->head=table;
    table->reginfo.impossible_range=0;
    if ((error= select->test_quick_select(thd, *(key_map *)keys,(table_map) 0,
                                          limit, 0)) == 1)
      DBUG_RETURN(select->quick->records);
    if (error == -1)
    {
      table->reginfo.impossible_range=1;
      DBUG_RETURN(0);
    }
    DBUG_PRINT("warning",("Couldn't use record count on const keypart"));
  }
  DBUG_RETURN(HA_POS_ERROR);                    /* This shouldn't happend */
}

/*
   This structure is used to collect info on potentially sargable
   predicates in order to check whether they become sargable after
   reading const tables.
   We form a bitmap of indexes that can be used for sargable predicates.
   Only such indexes are involved in range analysis.
*/
typedef struct st_sargable_param
{
  Field *field;              /* field against which to check sargability */
  Item **arg_value;          /* values of potential keys for lookups     */
  uint num_values;           /* number of values in the above array      */
} SARGABLE_PARAM;  

/*
  Calculate the best possible join and initialize the join structure

  RETURN VALUES
  0     ok
  1     Fatal error
*/

static bool
make_join_statistics(JOIN *join, TABLE_LIST *tables, COND *conds,
                     DYNAMIC_ARRAY *keyuse_array)
{
  int error;
  TABLE *table;
  uint i,table_count,const_count,key;
  table_map found_const_table_map, all_table_map, found_ref, refs;
  key_map const_ref, eq_part;
  TABLE **table_vector;
  JOIN_TAB *stat,*stat_end,*s,**stat_ref;
  KEYUSE *keyuse,*start_keyuse;
  table_map outer_join=0;
  SARGABLE_PARAM *sargables= 0;
  JOIN_TAB *stat_vector[MAX_TABLES+1];
  DBUG_ENTER("make_join_statistics");

  table_count=join->tables;
  stat=(JOIN_TAB*) join->thd->calloc(sizeof(JOIN_TAB)*table_count);
  stat_ref=(JOIN_TAB**) join->thd->alloc(sizeof(JOIN_TAB*)*MAX_TABLES);
  table_vector=(TABLE**) join->thd->alloc(sizeof(TABLE*)*(table_count*2));
  if (!stat || !stat_ref || !table_vector)
    DBUG_RETURN(1);                             // Eom /* purecov: inspected */

  join->best_ref=stat_vector;

  stat_end=stat+table_count;
  found_const_table_map= all_table_map=0;
  const_count=0;

  for (s= stat, i= 0;
       tables;
       s++, tables= tables->next_leaf, i++)
  {
    TABLE_LIST *embedding= tables->embedding;
    stat_vector[i]=s;
    s->keys.init();
    s->const_keys.init();
    s->checked_keys.init();
    s->needed_reg.init();
    table_vector[i]=s->table=table=tables->table;
    table->pos_in_table_list= tables;
    error= table->file->info(HA_STATUS_VARIABLE | HA_STATUS_NO_LOCK);
    if(error)
    {
        table->file->print_error(error, MYF(0));
        DBUG_RETURN(1);
    }
    table->quick_keys.clear_all();
    table->reginfo.join_tab=s;
    table->reginfo.not_exists_optimize=0;
    bzero((char*) table->const_key_parts, sizeof(key_part_map)*table->s->keys);
    all_table_map|= table->map;
    s->join=join;
    s->info=0;                                  // For describe

    s->dependent= tables->dep_tables;
    s->key_dependent= 0;
    if (tables->schema_table)
      table->file->records= 2;

    s->on_expr_ref= &tables->on_expr;
    if (*s->on_expr_ref)
    {
      /* s is the only inner table of an outer join */
      if (!table->file->records && !embedding)
      {                                         // Empty table
        s->dependent= 0;                        // Ignore LEFT JOIN depend.
        set_position(join,const_count++,s,(KEYUSE*) 0);
        continue;
      }
      outer_join|= table->map;
      s->embedding_map= 0;
      for (;embedding; embedding= embedding->embedding)
        s->embedding_map|= embedding->nested_join->nj_map;
      continue;
    }
    if (embedding)
    {
      /* s belongs to a nested join, maybe to several embedded joins */
      s->embedding_map= 0;
      do
      {
        NESTED_JOIN *nested_join= embedding->nested_join;
        s->embedding_map|=nested_join->nj_map;
        s->dependent|= embedding->dep_tables;
        embedding= embedding->embedding;
        outer_join|= nested_join->used_tables;
      }
      while (embedding);
      continue;
    }

    if ((table->s->system || table->file->records <= 1) && ! s->dependent &&
        !(table->file->table_flags() & HA_NOT_EXACT_COUNT) &&
        !table->fulltext_searched && !join->no_const_tables)
    {
      set_position(join,const_count++,s,(KEYUSE*) 0);
    }
  }
  stat_vector[i]=0;
  join->outer_join=outer_join;

  if (join->outer_join)
  {
    /* 
       Build transitive closure for relation 'to be dependent on'.
       This will speed up the plan search for many cases with outer joins,
       as well as allow us to catch illegal cross references/
       Warshall's algorithm is used to build the transitive closure.
       As we use bitmaps to represent the relation the complexity
       of the algorithm is O((number of tables)^2). 
    */
    for (i= 0, s= stat ; i < table_count ; i++, s++)
    {
      for (uint j= 0 ; j < table_count ; j++)
      {
        table= stat[j].table;
        if (s->dependent & table->map)
          s->dependent |= table->reginfo.join_tab->dependent;
      }
      if (s->dependent)
        s->table->maybe_null= 1;
    }
    /* Catch illegal cross references for outer joins */
    for (i= 0, s= stat ; i < table_count ; i++, s++)
    {
      if (s->dependent & s->table->map)
      {
        join->tables=0;                 // Don't use join->table
        my_message(ER_WRONG_OUTER_JOIN, ER(ER_WRONG_OUTER_JOIN), MYF(0));
        DBUG_RETURN(1);
      }
      s->key_dependent= s->dependent;
    }
  }

  if (conds || outer_join)
    if (update_ref_and_keys(join->thd, keyuse_array, stat, join->tables,
                            conds, join->cond_equal,
                            ~outer_join, join->select_lex, &sargables))
      DBUG_RETURN(1);

  /* Read tables with 0 or 1 rows (system tables) */
  join->const_table_map= 0;

  for (POSITION *p_pos=join->positions, *p_end=p_pos+const_count;
       p_pos < p_end ;
       p_pos++)
  {
    int tmp;
    s= p_pos->table;
    s->type=JT_SYSTEM;
    join->const_table_map|=s->table->map;
    if ((tmp=join_read_const_table(s, p_pos)))
    {
      if (tmp > 0)
        DBUG_RETURN(1);                 // Fatal error
    }
    else
      found_const_table_map|= s->table->map;
  }

  /* loop until no more const tables are found */
  int ref_changed;
  do
  {
  more_const_tables_found:
    ref_changed = 0;
    found_ref=0;

    /*
      We only have to loop from stat_vector + const_count as
      set_position() will move all const_tables first in stat_vector
    */

    for (JOIN_TAB **pos=stat_vector+const_count ; (s= *pos) ; pos++)
    {
      table=s->table;

      /* 
        If equi-join condition by a key is null rejecting and after a
        substitution of a const table the key value happens to be null
        then we can state that there are no matches for this equi-join.
      */  
      if ((keyuse= s->keyuse) && *s->on_expr_ref && !s->embedding_map)
      {
        /* 
          When performing an outer join operation if there are no matching rows
          for the single row of the outer table all the inner tables are to be
          null complemented and thus considered as constant tables.
          Here we apply this consideration to the case of outer join operations 
          with a single inner table only because the case with nested tables
          would require a more thorough analysis.
          TODO. Apply single row substitution to null complemented inner tables
          for nested outer join operations. 
        */              
        while (keyuse->table == table)
        {
          if (!(keyuse->val->used_tables() & ~join->const_table_map) &&
              keyuse->val->is_null() && keyuse->null_rejecting)
          {
            s->type= JT_CONST;
            mark_as_null_row(table);
            found_const_table_map|= table->map;
            join->const_table_map|= table->map;
            set_position(join,const_count++,s,(KEYUSE*) 0);
            goto more_const_tables_found;
           }
          keyuse++;
        }
      }

      if (s->dependent)                         // If dependent on some table
      {
        // All dep. must be constants
        if (s->dependent & ~(found_const_table_map))
          continue;
        if (table->file->records <= 1L &&
            !(table->file->table_flags() & HA_NOT_EXACT_COUNT) &&
            !table->pos_in_table_list->embedding)
        {                                       // system table
          int tmp= 0;
          s->type=JT_SYSTEM;
          join->const_table_map|=table->map;
          set_position(join,const_count++,s,(KEYUSE*) 0);
          if ((tmp= join_read_const_table(s, join->positions+const_count-1)))
          {
            if (tmp > 0)
              DBUG_RETURN(1);                   // Fatal error
          }
          else
            found_const_table_map|= table->map;
          continue;
        }
      }
      /* check if table can be read by key or table only uses const refs */
      if ((keyuse=s->keyuse))
      {
        s->type= JT_REF;
        while (keyuse->table == table)
        {
          start_keyuse=keyuse;
          key=keyuse->key;
          s->keys.set_bit(key);               // QQ: remove this ?

          refs=0;
          const_ref.clear_all();
          eq_part.clear_all();
          do
          {
            if (keyuse->val->type() != Item::NULL_ITEM && !keyuse->optimize)
            {
              if (!((~found_const_table_map) & keyuse->used_tables))
                const_ref.set_bit(keyuse->keypart);
              else
                refs|=keyuse->used_tables;
              eq_part.set_bit(keyuse->keypart);
            }
            keyuse++;
          } while (keyuse->table == table && keyuse->key == key);

          if (eq_part.is_prefix(table->key_info[key].key_parts) &&
              !table->fulltext_searched && 
              !table->pos_in_table_list->embedding)
          {
            if ((table->key_info[key].flags & (HA_NOSAME | HA_END_SPACE_KEY))
                 == HA_NOSAME)
            {
              if (const_ref == eq_part)
              {                                 // Found everything for ref.
                int tmp;
                ref_changed = 1;
                s->type= JT_CONST;
                join->const_table_map|=table->map;
                set_position(join,const_count++,s,start_keyuse);
                if (create_ref_for_key(join, s, start_keyuse,
                                       found_const_table_map))
                  DBUG_RETURN(1);
                if ((tmp=join_read_const_table(s,
                                               join->positions+const_count-1)))
                {
                  if (tmp > 0)
                    DBUG_RETURN(1);                     // Fatal error
                }
                else
                  found_const_table_map|= table->map;
                break;
              }
              else
                found_ref|= refs;      // Table is const if all refs are const
            }
            else if (const_ref == eq_part)
              s->const_keys.set_bit(key);
          }
        }
      }
    }
  } while (join->const_table_map & found_ref && ref_changed);

  /* 
    Update info on indexes that can be used for search lookups as
    reading const tables may has added new sargable predicates. 
  */
  if (const_count && sargables)
  {
    for( ; sargables->field ; sargables++)
    {
      Field *field= sargables->field;
      JOIN_TAB *join_tab= field->table->reginfo.join_tab;
      key_map possible_keys= field->key_start;
      possible_keys.intersect(field->table->keys_in_use_for_query);
      bool is_const= 1;
      for (uint j=0; j < sargables->num_values; j++)
        is_const&= sargables->arg_value[j]->const_item();
      if (is_const)
        join_tab[0].const_keys.merge(possible_keys);
    }
  }

  /* Calc how many (possible) matched records in each table */

  for (s=stat ; s < stat_end ; s++)
  {
    if (s->type == JT_SYSTEM || s->type == JT_CONST)
    {
      /* Only one matching row */
      s->found_records=s->records=s->read_time=1; s->worst_seeks=1.0;
      continue;
    }
    /* Approximate found rows and time to read them */
    s->found_records=s->records=s->table->file->records;
    s->read_time=(ha_rows) s->table->file->scan_time();

    /*
      Set a max range of how many seeks we can expect when using keys
      This is can't be to high as otherwise we are likely to use
      table scan.
    */
    s->worst_seeks= min((double) s->found_records / 10,
                        (double) s->read_time*3);
    if (s->worst_seeks < 2.0)                   // Fix for small tables
      s->worst_seeks=2.0;

    /*
      Add to stat->const_keys those indexes for which all group fields or
      all select distinct fields participate in one index.
    */
    add_group_and_distinct_keys(join, s);

    if (!s->const_keys.is_clear_all() &&
        !s->table->pos_in_table_list->embedding)
    {
      ha_rows records;
      SQL_SELECT *select;
      select= make_select(s->table, found_const_table_map,
                          found_const_table_map,
                          *s->on_expr_ref ? *s->on_expr_ref : conds,
                          1, &error);
      if (!select)
        DBUG_RETURN(1);
      records= get_quick_record_count(join->thd, select, s->table,
                                      &s->const_keys, join->row_limit);
      s->quick=select->quick;
      s->needed_reg=select->needed_reg;
      select->quick=0;
      if (records == 0 && s->table->reginfo.impossible_range)
      {
        /*
          Impossible WHERE or ON expression
          In case of ON, we mark that the we match one empty NULL row.
          In case of WHERE, don't set found_const_table_map to get the
          caller to abort with a zero row result.
        */
        join->const_table_map|= s->table->map;
        set_position(join,const_count++,s,(KEYUSE*) 0);
        s->type= JT_CONST;
        if (*s->on_expr_ref)
        {
          /* Generate empty row */
          s->info= "Impossible ON condition";
          found_const_table_map|= s->table->map;
          s->type= JT_CONST;
          mark_as_null_row(s->table);           // All fields are NULL
        }
      }
      if (records != HA_POS_ERROR)
      {
        s->found_records=records;
        s->read_time= (ha_rows) (s->quick ? s->quick->read_time : 0.0);
      }
      delete select;
    }
  }

  join->join_tab=stat;
  join->map2table=stat_ref;
  join->table= join->all_tables=table_vector;
  join->const_tables=const_count;
  join->found_const_table_map=found_const_table_map;

  /* Find an optimal join order of the non-constant tables. */
  if (join->const_tables != join->tables)
  {
    optimize_keyuse(join, keyuse_array);
    if (choose_plan(join, all_table_map & ~join->const_table_map))
      DBUG_RETURN(TRUE);
  }
  else
  {
    memcpy((gptr) join->best_positions,(gptr) join->positions,
           sizeof(POSITION)*join->const_tables);
    join->best_read=1.0;
  }
  /* Generate an execution plan from the found optimal join order. */
  DBUG_RETURN(join->thd->killed || get_best_combination(join));
}


/*****************************************************************************
  Check with keys are used and with tables references with tables
  Updates in stat:
          keys       Bitmap of all used keys
          const_keys Bitmap of all keys with may be used with quick_select
          keyuse     Pointer to possible keys
*****************************************************************************/

typedef struct key_field_t {            // Used when finding key fields
  Field         *field;
  Item          *val;                   // May be empty if diff constant
  uint          level;
  uint          optimize;
  bool          eq_func;
  /*
    If true, the condition this struct represents will not be satisfied
    when val IS NULL.
  */
  bool          null_rejecting; 
  bool         *cond_guard; /* See KEYUSE::cond_guard */
} KEY_FIELD;

/* Values in optimize */
#define KEY_OPTIMIZE_EXISTS             1
#define KEY_OPTIMIZE_REF_OR_NULL        2

/*
  Merge new key definitions to old ones, remove those not used in both

  This is called for OR between different levels

  To be able to do 'ref_or_null' we merge a comparison of a column
  and 'column IS NULL' to one test.  This is useful for sub select queries
  that are internally transformed to something like:

  SELECT * FROM t1 WHERE t1.key=outer_ref_field or t1.key IS NULL 

  KEY_FIELD::null_rejecting is processed as follows:
  result has null_rejecting=true if it is set for both ORed references.
  for example:
    (t2.key = t1.field OR t2.key  =  t1.field) -> null_rejecting=true
    (t2.key = t1.field OR t2.key <=> t1.field) -> null_rejecting=false
*/

static KEY_FIELD *
merge_key_fields(KEY_FIELD *start,KEY_FIELD *new_fields,KEY_FIELD *end,
                 uint and_level)
{
  if (start == new_fields)
    return start;                               // Impossible or
  if (new_fields == end)
    return start;                               // No new fields, skip all

  KEY_FIELD *first_free=new_fields;

  /* Mark all found fields in old array */
  for (; new_fields != end ; new_fields++)
  {
    for (KEY_FIELD *old=start ; old != first_free ; old++)
    {
      if (old->field == new_fields->field)
      {
        /*
          NOTE: below const_item() call really works as "!used_tables()", i.e.
          it can return FALSE where it is feasible to make it return TRUE.
          
          The cause is as follows: Some of the tables are already known to be
          const tables (the detection code is in make_join_statistics(),
          above the update_ref_and_keys() call), but we didn't propagate 
          information about this: TABLE::const_table is not set to TRUE, and
          Item::update_used_tables() hasn't been called for each item.
          The result of this is that we're missing some 'ref' accesses.
          TODO: OptimizerTeam: Fix this
        */
        if (!new_fields->val->const_item())
        {
          /*
            If the value matches, we can use the key reference.
            If not, we keep it until we have examined all new values
          */
          if (old->val->eq(new_fields->val, old->field->binary()))
          {
            old->level= and_level;
            old->optimize= ((old->optimize & new_fields->optimize &
                             KEY_OPTIMIZE_EXISTS) |
                            ((old->optimize | new_fields->optimize) &
                             KEY_OPTIMIZE_REF_OR_NULL));
            old->null_rejecting= (old->null_rejecting &&
                                  new_fields->null_rejecting);
          }
        }
        else if (old->eq_func && new_fields->eq_func &&
                 old->val->eq(new_fields->val, old->field->binary()))

        {
          old->level= and_level;
          old->optimize= ((old->optimize & new_fields->optimize &
                           KEY_OPTIMIZE_EXISTS) |
                          ((old->optimize | new_fields->optimize) &
                           KEY_OPTIMIZE_REF_OR_NULL));
          old->null_rejecting= (old->null_rejecting &&
                                new_fields->null_rejecting);
        }
        else if (old->eq_func && new_fields->eq_func &&
                 ((old->val->const_item() && old->val->is_null()) || 
                  new_fields->val->is_null()))
        {
          /* field = expression OR field IS NULL */
          old->level= and_level;
          old->optimize= KEY_OPTIMIZE_REF_OR_NULL;
          /*
            Remember the NOT NULL value unless the value does not depend
            on other tables.
          */
          if (!old->val->used_tables() && old->val->is_null())
            old->val= new_fields->val;
          /* The referred expression can be NULL: */ 
          old->null_rejecting= 0;
        }
        else
        {
          /*
            We are comparing two different const.  In this case we can't
            use a key-lookup on this so it's better to remove the value
            and let the range optimzier handle it
          */
          if (old == --first_free)              // If last item
            break;
          *old= *first_free;                    // Remove old value
          old--;                                // Retry this value
        }
      }
    }
  }
  /* Remove all not used items */
  for (KEY_FIELD *old=start ; old != first_free ;)
  {
    if (old->level != and_level)
    {                                           // Not used in all levels
      if (old == --first_free)
        break;
      *old= *first_free;                        // Remove old value
      continue;
    }
    old++;
  }
  return first_free;
}


/*
  Add a possible key to array of possible keys if it's usable as a key

  SYNPOSIS
    add_key_field()
    key_fields                  Pointer to add key, if usable
    and_level                   And level, to be stored in KEY_FIELD
    cond                        Condition predicate
    field                       Field used in comparision
    eq_func                     True if we used =, <=> or IS NULL
    value                       Value used for comparison with field
    usable_tables               Tables which can be used for key optimization
    sargables            IN/OUT Array of found sargable candidates

  NOTES
    If we are doing a NOT NULL comparison on a NOT NULL field in a outer join
    table, we store this to be able to do not exists optimization later.

  RETURN
    *key_fields is incremented if we stored a key in the array
*/

static void
add_key_field(KEY_FIELD **key_fields,uint and_level, Item_func *cond,
              Field *field, bool eq_func, Item **value, uint num_values,
              table_map usable_tables, SARGABLE_PARAM **sargables)
{
  uint exists_optimize= 0;
  if (!(field->flags & PART_KEY_FLAG))
  {
    // Don't remove column IS NULL on a LEFT JOIN table
    if (!eq_func || (*value)->type() != Item::NULL_ITEM ||
        !field->table->maybe_null || field->null_ptr)
      return;                                   // Not a key. Skip it
    exists_optimize= KEY_OPTIMIZE_EXISTS;
    DBUG_ASSERT(num_values == 1);
  }
  else
  {
    table_map used_tables=0;
    bool optimizable=0;
    for (uint i=0; i<num_values; i++)
    {
      used_tables|=(value[i])->used_tables();
      if (!((value[i])->used_tables() & (field->table->map | RAND_TABLE_BIT)))
        optimizable=1;
    }
    if (!optimizable)
      return;
    if (!(usable_tables & field->table->map))
    {
      if (!eq_func || (*value)->type() != Item::NULL_ITEM ||
          !field->table->maybe_null || field->null_ptr)
        return;                                 // Can't use left join optimize
      exists_optimize= KEY_OPTIMIZE_EXISTS;
    }
    else
    {
      JOIN_TAB *stat=field->table->reginfo.join_tab;
      key_map possible_keys=field->key_start;
      possible_keys.intersect(field->table->keys_in_use_for_query);
      stat[0].keys.merge(possible_keys);             // Add possible keys

      /*
        Save the following cases:
        Field op constant
        Field LIKE constant where constant doesn't start with a wildcard
        Field = field2 where field2 is in a different table
        Field op formula
        Field IS NULL
        Field IS NOT NULL
         Field BETWEEN ...
         Field IN ...
      */
      stat[0].key_dependent|=used_tables;

      bool is_const=1;
      for (uint i=0; i<num_values; i++)
        is_const&= value[i]->const_item();
      if (is_const)
        stat[0].const_keys.merge(possible_keys);
      else if (!eq_func)
      {
        /* 
          Save info to be able check whether this predicate can be 
          considered as sargable for range analisis after reading const tables.
          We do not save info about equalities as update_const_equal_items
          will take care of updating info on keys from sargable equalities. 
        */
        (*sargables)--;
        (*sargables)->field= field;
        (*sargables)->arg_value= value;
        (*sargables)->num_values= num_values;
      }
      /*
        We can't always use indexes when comparing a string index to a
        number. cmp_type() is checked to allow compare of dates to numbers.
        eq_func is NEVER true when num_values > 1
       */
      if (!eq_func)
      {
        /* 
          Additional optimization: if we're processing
          "t.key BETWEEN c1 AND c1" then proceed as if we were processing
          "t.key = c1".
          TODO: This is a very limited fix. A more generic fix is possible. 
          There are 2 options:
          A) Make equality propagation code be able to handle BETWEEN
             (including cases like t1.key BETWEEN t2.key AND t3.key)
          B) Make range optimizer to infer additional "t.key = c" equalities
             and use them in equality propagation process (see details in
             OptimizerKBAndTodo)
        */
        if ((cond->functype() != Item_func::BETWEEN) ||
            ((Item_func_between*) cond)->negated ||
            !value[0]->eq(value[1], field->binary()))
          return;
        eq_func= TRUE;
      }

      if (field->result_type() == STRING_RESULT)
      {
        if ((*value)->result_type() != STRING_RESULT)
        {
          if (field->cmp_type() != (*value)->result_type())
            return;
        }
        else
        {
          /*
            We can't use indexes if the effective collation
            of the operation differ from the field collation.
          */
          if (field->cmp_type() == STRING_RESULT &&
              ((Field_str*)field)->charset() != cond->compare_collation())
            return;
        }
      }
    }
  }
  /*
    For the moment eq_func is always true. This slot is reserved for future
    extensions where we want to remembers other things than just eq comparisons
  */
  DBUG_ASSERT(eq_func);
  /* Store possible eq field */
  (*key_fields)->field=         field;
  (*key_fields)->eq_func=       eq_func;
  (*key_fields)->val=           *value;
  (*key_fields)->level=         and_level;
  (*key_fields)->optimize=      exists_optimize;
  /*
    If the condition has form "tbl.keypart = othertbl.field" and 
    othertbl.field can be NULL, there will be no matches if othertbl.field 
    has NULL value.
    We use null_rejecting in add_not_null_conds() to add
    'othertbl.field IS NOT NULL' to tab->select_cond.
  */
  (*key_fields)->null_rejecting= ((cond->functype() == Item_func::EQ_FUNC ||
                                   cond->functype() == Item_func::MULT_EQUAL_FUNC) &&
                                  ((*value)->type() == Item::FIELD_ITEM) &&
                                  ((Item_field*)*value)->field->maybe_null());
  (*key_fields)->cond_guard= NULL;
  (*key_fields)++;
}

/*
  Add possible keys to array of possible keys originated from a simple predicate

  SYNPOSIS
    add_key_equal_fields()
    key_fields                  Pointer to add key, if usable
    and_level                   And level, to be stored in KEY_FIELD
    cond                        Condition predicate
    field                       Field used in comparision
    eq_func                     True if we used =, <=> or IS NULL
    value                       Value used for comparison with field
                                Is NULL for BETWEEN and IN    
    usable_tables               Tables which can be used for key optimization
    sargables            IN/OUT Array of found sargable candidates

  NOTES
    If field items f1 and f2 belong to the same multiple equality and
    a key is added for f1, the the same key is added for f2.

  RETURN
    *key_fields is incremented if we stored a key in the array
*/

static void
add_key_equal_fields(KEY_FIELD **key_fields, uint and_level,
                     Item_func *cond, Item_field *field_item,
                     bool eq_func, Item **val,
                     uint num_values, table_map usable_tables,
                     SARGABLE_PARAM **sargables)
{
  Field *field= field_item->field;
  add_key_field(key_fields, and_level, cond, field,
                eq_func, val, num_values, usable_tables, sargables);
  Item_equal *item_equal= field_item->item_equal;
  if (item_equal)
  { 
    /*
      Add to the set of possible key values every substitution of
      the field for an equal field included into item_equal
    */
    Item_equal_iterator it(*item_equal);
    Item_field *item;
    while ((item= it++))
    {
      if (!field->eq(item->field))
      {
        add_key_field(key_fields, and_level, cond, item->field,
                      eq_func, val, num_values, usable_tables,
                      sargables);
      }
    }
  }
}

static void
add_key_fields(JOIN *join, KEY_FIELD **key_fields, uint *and_level,
               COND *cond, table_map usable_tables,
               SARGABLE_PARAM **sargables)
{
  if (cond->type() == Item_func::COND_ITEM)
  {
    List_iterator_fast<Item> li(*((Item_cond*) cond)->argument_list());
    KEY_FIELD *org_key_fields= *key_fields;

    if (((Item_cond*) cond)->functype() == Item_func::COND_AND_FUNC)
    {
      Item *item;
      while ((item=li++))
        add_key_fields(join, key_fields, and_level, item, usable_tables,
                       sargables);
      for (; org_key_fields != *key_fields ; org_key_fields++)
        org_key_fields->level= *and_level;
    }
    else
    {
      (*and_level)++;
      add_key_fields(join, key_fields, and_level, li++, usable_tables,
                     sargables);
      Item *item;
      while ((item=li++))
      {
        KEY_FIELD *start_key_fields= *key_fields;
        (*and_level)++;
        add_key_fields(join, key_fields, and_level, item, usable_tables,
                       sargables);
        *key_fields=merge_key_fields(org_key_fields,start_key_fields,
                                     *key_fields,++(*and_level));
      }
    }
    return;
  }

  /* 
    Subquery optimization: Conditions that are pushed down into subqueries
    are wrapped into Item_func_trig_cond. We process the wrapped condition
    but need to set cond_guard for KEYUSE elements generated from it.
  */
  {
    if (cond->type() == Item::FUNC_ITEM &&
        ((Item_func*)cond)->functype() == Item_func::TRIG_COND_FUNC)
    {
      Item *cond_arg= ((Item_func*)cond)->arguments()[0];
      if (!join->group_list && !join->order &&
          join->unit->item && 
          join->unit->item->substype() == Item_subselect::IN_SUBS &&
          !join->unit->first_select()->next_select())
      {
        KEY_FIELD *save= *key_fields;
        add_key_fields(join, key_fields, and_level, cond_arg, usable_tables,
                       sargables);
        // Indicate that this ref access candidate is for subquery lookup:
        for (; save != *key_fields; save++)
          save->cond_guard= ((Item_func_trig_cond*)cond)->get_trig_var();
      }
      return;
    }
  }

  /* If item is of type 'field op field/constant' add it to key_fields */
  if (cond->type() != Item::FUNC_ITEM)
    return;
  Item_func *cond_func= (Item_func*) cond;
  switch (cond_func->select_optimize()) {
  case Item_func::OPTIMIZE_NONE:
    break;
  case Item_func::OPTIMIZE_KEY:
  {
    Item **values;
    // BETWEEN, IN, NE
    if (cond_func->key_item()->real_item()->type() == Item::FIELD_ITEM &&
        !(cond_func->used_tables() & OUTER_REF_TABLE_BIT))
    {
      values= cond_func->arguments()+1;
      if (cond_func->functype() == Item_func::NE_FUNC &&
        cond_func->arguments()[1]->real_item()->type() == Item::FIELD_ITEM &&
             !(cond_func->arguments()[0]->used_tables() & OUTER_REF_TABLE_BIT))
        values--;
      DBUG_ASSERT(cond_func->functype() != Item_func::IN_FUNC ||
                  cond_func->argument_count() != 2);
      add_key_equal_fields(key_fields, *and_level, cond_func,
                           (Item_field*) (cond_func->key_item()->real_item()),
                           0, values, 
                           cond_func->argument_count()-1,
                           usable_tables, sargables);
    }
    if (cond_func->functype() == Item_func::BETWEEN)
    {
      values= cond_func->arguments();
      for (uint i= 1 ; i < cond_func->argument_count() ; i++)
      {
        Item_field *field_item;
        if (cond_func->arguments()[i]->real_item()->type() == Item::FIELD_ITEM