~drizzle-trunk/drizzle/development

/* 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 */

/**

  @file

  @brief

  mysql_select and join optimization

  @defgroup Query_Optimizer  Query Optimizer

  @{

*/

#ifdef USE_PRAGMA_IMPLEMENTATION

#pragma implementation				// gcc: Class implementation

#endif

#include "mysql_priv.h"

#include "sql_select.h"

#include <m_ctype.h>

#include <my_bit.h>

#include <hash.h>

const char *join_type_str[]={ "UNKNOWN","system","const","eq_ref","ref",

			      "MAYBE_REF","ALL","range","index",

			      "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, uint idx, 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, uchar *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 bool make_join_readinfo(JOIN *join, ulonglong options, uint no_jbuf_after);

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, bool in_sj);

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 

void advance_sj_state(const table_map remaining_tables, const JOIN_TAB *tab);

static void restore_prev_sj_state(const table_map remaining_tables, 

                                  const JOIN_TAB *tab);

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, KEY *keyinfo, 

                                    MI_COLUMNDEF *start_recinfo,

                                    MI_COLUMNDEF **recinfo,

				    ulonglong options);

static int do_select(JOIN *join,List<Item> *fields,TABLE *tmp_table);

static enum_nested_loop_state

evaluate_join_record(JOIN *join, JOIN_TAB *join_tab,

                     int 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_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 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_read_next_different(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_same(READ_RECORD *info);

static int join_read_next_same_diff(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);

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,

                                 bool exclude_expensive_cond);

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,

                                    const key_map *map);

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,

                             bool is_order_by);

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 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);

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);

static bool test_if_ref(Item_field *left_item,Item *right_item);

static bool replace_where_subcondition(JOIN *join, Item *old_cond, 

                                       Item *new_cond, bool fix_fields);

/*

  This is used to mark equalities that were made from i-th IN-equality.

  We limit semi-join InsideOut optimization to handling max 64 inequalities,

  The following variable occupies 64 addresses.

*/

const char *subq_sj_cond_name=

  "0123456789ABCDEF0123456789abcdef0123456789ABCDEF0123456789abcdef-sj-cond";

static bool bitmap_covers(const table_map x, const table_map y)

{

  return !test(y & ~x);

}

/**

  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");

  MYSQL_SELECT_START();

  if (select_lex->master_unit()->is_union() || 

      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);

    thd->thd_marker= 0;

    /*

      '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->is_error()));

  res|= thd->is_error();

  if (unlikely(res))

    result->abort();

  MYSQL_SELECT_END();

  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->table_name,

                          ref->field_name, ref->alias_name_used) :

              new Item_ref(ref->context, item_ref, ref->table_name,

                          ref->field_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;

}

#define MAGIC_IN_WHERE_TOP_LEVEL 10

/**

  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).

  @todo

    Add check of calculation of GROUP functions and fields:

    SELECT COUNT(*)+table.col1 from table1;

  @retval

    -1   on error

  @retval

    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->is_union();

  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, &select_lex->leaf_tables,

                                    FALSE))

      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, MARK_COLUMNS_READ,

		   &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->is_error())

      DBUG_RETURN(-1);				/* purecov: inspected */

    thd->lex->allow_sum_func= save_allow_sum_func;

  }

  if (!thd->lex->view_prepare_mode)

  {

    Item_subselect *subselect;

    Item_in_subselect *in_subs= NULL;

    /*

      Are we in a subquery predicate?

      TODO: the block below will be executed for every PS execution without need.

    */

    if ((subselect= select_lex->master_unit()->item))

    {

      bool do_semijoin= !test(thd->variables.optimizer_switch &

                              OPTIMIZER_SWITCH_NO_SEMIJOIN);

      if (subselect->substype() == Item_subselect::IN_SUBS)

        in_subs= (Item_in_subselect*)subselect;

      DBUG_PRINT("info", ("Checking if subq can be converted to semi-join"));

      /*

        Check if we're in subquery that is a candidate for flattening into a

        semi-join (which is done done in flatten_subqueries()). The

        requirements are:

          1. Subquery predicate is an IN/=ANY subq predicate

          2. Subquery is a single SELECT (not a UNION)

          3. Subquery does not have GROUP BY or ORDER BY

          4. Subquery does not use aggregate functions or HAVING

          5. Subquery predicate is at the AND-top-level of ON/WHERE clause

          6. No execution method was already chosen (by a prepared statement).

          (*). We are not in a subquery of a single table UPDATE/DELETE that 

               doesn't have a JOIN (TODO: We should handle this at some

               point by switching to multi-table UPDATE/DELETE)

          (**). We're not in a confluent table-less subquery, like

                "SELECT 1". 

      */

      if (in_subs &&                                                    // 1

          !select_lex->master_unit()->first_select()->next_select() &&  // 2

          !select_lex->group_list.elements && !order &&                 // 3

          !having && !select_lex->with_sum_func &&                      // 4

          thd->thd_marker &&                                            // 5

          select_lex->outer_select()->join &&                           // (*)

          select_lex->master_unit()->first_select()->leaf_tables &&     // (**) 

          do_semijoin &&

          in_subs->exec_method == Item_in_subselect::NOT_TRANSFORMED)   // 6

      {

        DBUG_PRINT("info", ("Subquery is semi-join conversion candidate"));

        {

          if (!in_subs->left_expr->fixed &&

               in_subs->left_expr->fix_fields(thd, &in_subs->left_expr))

          {

            DBUG_RETURN(-1);

          }

          /*

            Check that the right part of the subselect contains no more than one

            column. E.g. in SELECT 1 IN (SELECT * ..) the right part is (SELECT * ...)

          */

          if (subselect->substype() == Item_subselect::IN_SUBS &&

             (select_lex->item_list.elements != 

              ((Item_in_subselect*)subselect)->left_expr->cols()))

          {

            my_error(ER_OPERAND_COLUMNS, MYF(0), ((Item_in_subselect*)subselect)->left_expr->cols());

            DBUG_RETURN(-1);

          }

        }

        /* Register the subquery for further processing */

        select_lex->outer_select()->join->sj_subselects.append(thd->mem_root, in_subs);

        in_subs->expr_join_nest= (TABLE_LIST*)thd->thd_marker;

      }

      else

      {

        DBUG_PRINT("info", ("Subquery can't be converted to semi-join"));

        bool do_materialize= !test(thd->variables.optimizer_switch &

                                   OPTIMIZER_SWITCH_NO_MATERIALIZATION);

        /*

          Check if the subquery predicate can be executed via materialization.

          The required conditions are:

          1. Subquery predicate is an IN/=ANY subq predicate

          2. Subquery is a single SELECT (not a UNION)

          3. Subquery is not a table-less query. In this case there is no

             point in materializing.

          4. Subquery predicate is a top-level predicate

             (this implies it is not negated)

             TODO: this is a limitation that should be lifeted once we

             implement correct NULL semantics (WL#3830)

          5. Subquery is non-correlated

             TODO:

             This is an overly restrictive condition. It can be extended to:

             (Subquery is non-correlated ||

              Subquery is correlated to any query outer to IN predicate ||

              (Subquery is correlated to the immediate outer query &&

               Subquery !contains {GROUP BY, ORDER BY [LIMIT],

               aggregate functions) && subquery predicate is not under "NOT IN"))

          6. No execution method was already chosen (by a prepared statement).

          (*) The subquery must be part of a SELECT statement. The current

               condition also excludes multi-table update statements.

          We have to determine whether we will perform subquery materialization

          before calling the IN=>EXISTS transformation, so that we know whether to

          perform the whole transformation or only that part of it which wraps

          Item_in_subselect in an Item_in_optimizer.

        */

        if (do_materialize && 

            in_subs  &&                                                   // 1

            !select_lex->master_unit()->first_select()->next_select() &&  // 2

            select_lex->master_unit()->first_select()->leaf_tables &&     // 3

            thd->lex->sql_command == SQLCOM_SELECT)                       // *

        {

          if (in_subs->is_top_level_item() &&                             // 4

              !in_subs->is_correlated &&                                  // 5

              in_subs->exec_method == Item_in_subselect::NOT_TRANSFORMED) // 6

            in_subs->exec_method= Item_in_subselect::MATERIALIZATION;

        }

        Item_subselect::trans_res trans_res;

        if ((trans_res= subselect->select_transformer(this)) !=

            Item_subselect::RES_OK)

        {

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

          DBUG_RETURN((trans_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;

      }

    }

  }

  /*

    Check if there are references to un-aggregated columns when computing 

    aggregate functions with implicit grouping (there is no GROUP BY).

    MODE_ONLY_FULL_GROUP_BY is enabled here by default

  */

  if (!group_list && select_lex->full_group_by_flag == (NON_AGG_FIELD_USED | SUM_FUNC_USED))

  {

    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++;

  }

  if (error)

    goto err;					/* purecov: inspected */

  if (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:

  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.

    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.

    TODO: We can remove the equalities that will be guaranteed to be true by the

    fact that subquery engine will be using index lookup. This must be done only

    for cases where there are no conversion errors of significance, e.g. 257

    that is searched in a byte. But this requires homogenization of the return 

    codes of all Field*::store() methods.

*/

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 &&

      test_if_ref ((Item_field *)((Item_func *)conds)->arguments()[1],

                   ((Item_func *)conds)->arguments()[0]))

  {

    *where= 0;

    return;

  }

}

/*

  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->covering_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;

    }

  }

}

/*

  Check if the table's rowid is included in the temptable

  SYNOPSIS

    sj_table_is_included()

      join      The join

      join_tab  The table to be checked

  DESCRIPTION

    SemiJoinDuplicateElimination: check the table's rowid should be included

    in the temptable. This is so if

    1. The table is not embedded within some semi-join nest

    2. The has been pulled out of a semi-join nest, or

    3. The table is functionally dependent on some previous table

    [4. This is also true for constant tables that can't be

        NULL-complemented but this function is not called for such tables]

  RETURN

    TRUE  - Include table's rowid

    FALSE - Don't

*/

static bool sj_table_is_included(JOIN *join, JOIN_TAB *join_tab)

{

  if (join_tab->emb_sj_nest)

    return FALSE;

  /* Check if this table is functionally dependent on the tables that

     are within the same outer join nest

  */

  TABLE_LIST *embedding= join_tab->table->pos_in_table_list->embedding;

  if (join_tab->type == JT_EQ_REF)

  {

    Table_map_iterator it(join_tab->ref.depend_map & ~PSEUDO_TABLE_BITS);

    uint idx;

    while ((idx= it.next_bit())!=Table_map_iterator::BITMAP_END)

    {

      JOIN_TAB *ref_tab= join->join_tab + idx;

      if (embedding == ref_tab->table->pos_in_table_list->embedding)

        return TRUE;

    }

    /* Ok, functionally dependent */

    return FALSE;

  }

  /* Not functionally dependent => need to include*/

  return TRUE;

}

TABLE *create_duplicate_weedout_tmp_table(THD *thd, uint uniq_tuple_length_arg,

                                          SJ_TMP_TABLE *sjtbl);

/*

  Setup the strategies to eliminate semi-join duplicates.

  SYNOPSIS

    setup_semijoin_dups_elimination()

      join           Join to process

      options        Join options (needed to see if join buffering will be 

                     used or not)

      no_jbuf_after  Another bit of information re where join buffering will

                     be used.

  DESCRIPTION

    Setup the strategies to eliminate semi-join duplicates. ATM there are 3

    strategies:

    1. DuplicateWeedout (use of temptable to remove duplicates based on rowids

                         of row combinations)

    2. FirstMatch (pick only the 1st matching row combination of inner tables)

    3. InsideOut (scanning the sj-inner table in a way that groups duplicates

                  together and picking the 1st one)

    The join order has "duplicate-generating ranges", and every range is

    served by one strategy or a combination of FirstMatch with with some

    other strategy.

    "Duplicate-generating range" is defined as a range within the join order

    that contains all of the inner tables of a semi-join. All ranges must be

    disjoint, if tables of several semi-joins are interleaved, then the ranges

    are joined together, which is equivalent to converting

      SELECT ... WHERE oe1 IN (SELECT ie1 ...) AND oe2 IN (SELECT ie2 )

    to

      SELECT ... WHERE (oe1, oe2) IN (SELECT ie1, ie2 ... ...)

    .

    Applicability conditions are as follows:

    DuplicateWeedout strategy

    ~~~~~~~~~~~~~~~~~~~~~~~~~

      (ot|nt)*  [ it ((it|ot|nt)* (it|ot))]  (nt)*

      +------+  +=========================+  +---+

        (1)                 (2)               (3)

       (1) - Prefix of OuterTables (those that participate in 

             IN-equality and/or are correlated with subquery) and outer 

             Noncorrelated Tables.

       (2) - The handled range. The range starts with the first sj-inner

             table, and covers all sj-inner and outer tables 

             Within the range,  Inner, Outer, outer Noncorrelated tables

             may follow in any order.

       (3) - The suffix of outer Noncorrelated tables.

    FirstMatch strategy

    ~~~~~~~~~~~~~~~~~~~

      (ot|nt)*  [ it ((it|nt)* it) ]  (nt)*

      +------+  +==================+  +---+

        (1)             (2)          (3)

      (1) - Prefix of outer and non-correlated tables

      (2) - The handled range, which may contain only inner and

            non-correlated tables.

      (3) - The suffix of outer Noncorrelated tables.

    InsideOut strategy 

    ~~~~~~~~~~~~~~~~~~

     (ot|ct|nt) [ insideout_tbl (ot|nt|it)* it ]  (ot|nt)*

     +--------+   +===========+ +=============+   +------+

        (1)           (2)          (3)              (4)

      (1) - Prefix that may contain any outer tables. The prefix must contain

            all the non-trivially correlated outer tables. (non-trivially means

            that the correlation is not just through the IN-equality).

      (2) - Inner table for which the InsideOut scan is performed.

      (3) - The remainder of the duplicate-generating range. It is served by 

            application of FirstMatch strategy, with the exception that

            outer IN-correlated tables are considered to be non-correlated.

      (4) - THe suffix of outer and outer non-correlated tables.

    If several strategies are applicable, their relative priorities are:

      1. InsideOut

      2. FirstMatch 

      3. DuplicateWeedout

    This function walks over the join order and sets up the strategies by

    setting appropriate members in join_tab structures.

  RETURN

    FALSE  OK 

    TRUE   Out of memory error

*/

static

int setup_semijoin_dups_elimination(JOIN *join, ulonglong options, uint no_jbuf_after)

{

  table_map cur_map= join->const_table_map | PSEUDO_TABLE_BITS;

  struct {

    /* 

      0 - invalid (EOF marker), 

      1 - InsideOut, 

      2 - Temptable (maybe confluent),

      3 - Temptable with join buffering

    */

    uint strategy;

    uint start_idx; /* Left range bound */

    uint end_idx;   /* Right range bound */

    /* 

      For Temptable strategy: Bitmap of all outer and correlated tables from 

      all involved join nests.

    */

    table_map outer_tables;

  } dups_ranges [MAX_TABLES];

  TABLE_LIST *emb_insideout_nest= NULL;

  table_map emb_sj_map= 0;  /* A bitmap of sj-nests (that is, their sj-inner

                               tables) whose ranges we're in */

  table_map emb_outer_tables= 0; /* sj-outer tables for those sj-nests */

  table_map range_start_map= 0; /* table_map at current range start */

  bool dealing_with_jbuf= FALSE; /* TRUE <=> table within cur range uses join buf */

  int cur_range= 0;

  uint i;

  DBUG_ENTER("setup_semijoin_dups_elimination");

  /*

    First pass: locate the duplicate-generating ranges and pick the strategies.

  */

  for (i=join->const_tables ; i < join->tables ; i++)

  {

    JOIN_TAB *tab=join->join_tab+i;

    TABLE *table=tab->table;

    cur_map |= table->map;

    if (tab->emb_sj_nest) // Encountered an sj-inner table

    {

      if (!emb_sj_map)

      {

        dups_ranges[cur_range].start_idx= i;

        range_start_map= cur_map & ~table->map;

        /*

          Remember if this is a possible start of range that is covered by

          the InsideOut strategy (the reason that it is not covered could

          be that it overlaps with anther semi-join's range. we don't

          support InsideOut for joined ranges)

        */

        if (join->best_positions[i].use_insideout_scan)

          emb_insideout_nest= tab->emb_sj_nest;

      }

      emb_sj_map |= tab->emb_sj_nest->sj_inner_tables;

      emb_outer_tables |= tab->emb_sj_nest->nested_join->sj_depends_on;

      if (tab->emb_sj_nest != emb_insideout_nest)

      {

        /*

          Two different semi-joins interleave. This cannot be handled by

          InsideOut strategy.

        */

        emb_insideout_nest= NULL;

      }

    }

    if (emb_sj_map) /* We're in duplicate-generating range */

    {

      if (i != join->const_tables && !(options & SELECT_NO_JOIN_CACHE) &&

          tab->type == JT_ALL && tab->use_quick != 2 && !tab->first_inner &&

          i <= no_jbuf_after && !dealing_with_jbuf)

      {

        /*

          This table uses join buffering, which makes use of FirstMatch or 

          InsideOut strategies impossible for the current and (we assume) 

          preceding duplicate-producing ranges.

          That is, for the join order:

              x x [ x  x]  x  [x x x]  x  [x x X*  x] x

                  |     |     |     |          | \

                  +-----+     +-----+          |  join buffering use

                     r1          r2         we're here

          we'll have to remove r1 and r2 and use duplicate-elimination

          strategy that spans all the tables, starting from the very 1st

          one.

        */

        dealing_with_jbuf= TRUE;

        emb_insideout_nest= FALSE;

        /* 

          Absorb all preceding duplicate-eliminating ranges. Their strategies

          do not matter: 

        */

        for (int prev_range= 0; prev_range < cur_range; prev_range++)

        {

          dups_ranges[cur_range].outer_tables |= 

            dups_ranges[prev_range].outer_tables;

        }

        dups_ranges[0].start_idx= 0; /* Will need to start from the 1st table */

        dups_ranges[0].outer_tables= dups_ranges[cur_range].outer_tables;

        cur_range=  0;

      }

      /*

        Check if we are at the end of duplicate-producing range. We are if

        1. It's an InsideOut range (which presumes all correlated tables are

           in the prefix), and all inner tables are in the join order prefix,

           or

        2. It's a DuplicateElimination range (possibly covering several

           SJ-nests), and all inner, outer, and correlated tables of all 

           sj-nests are in the join order prefix.

      */

      bool end_of_range= FALSE;

      if (emb_insideout_nest && 

          bitmap_covers(cur_map, emb_insideout_nest->sj_inner_tables))

      {

        /* Save that this range is handled with InsideOut: */

        dups_ranges[cur_range].strategy= 1;

        end_of_range= TRUE;

      }

      else if (bitmap_covers(cur_map, emb_outer_tables | emb_sj_map))

      {

        /*

          This is a complete range to be handled with either DuplicateWeedout 

          or FirstMatch

        */

        dups_ranges[cur_range].strategy= dealing_with_jbuf? 3 : 2;

        /* 

          This will hold tables from within the range that need to be put 

          into the join buffer before we can use the FirstMatch on its tail.

        */

        dups_ranges[cur_range].outer_tables= emb_outer_tables & 

                                             ~range_start_map;

        end_of_range= TRUE;

      }

      if (end_of_range)

      {

        dups_ranges[cur_range].end_idx= i+1;

        emb_sj_map= emb_outer_tables= 0;

        emb_insideout_nest= NULL;

        dealing_with_jbuf= FALSE;

        dups_ranges[++cur_range].strategy= 0;

      }

    }

  }

  THD *thd= join->thd;

  SJ_TMP_TABLE **next_sjtbl_ptr= &join->sj_tmp_tables;

  /*

    Second pass: setup the chosen strategies    

  */

  for (int j= 0; j < cur_range; j++)

  {

    JOIN_TAB *tab=join->join_tab + dups_ranges[j].start_idx;

    JOIN_TAB *jump_to;

    if (dups_ranges[j].strategy == 1)  // InsideOut strategy

    {

      tab->insideout_match_tab= join->join_tab + dups_ranges[j].end_idx - 1;

      jump_to= tab++;

    }

    else // DuplicateWeedout strategy

    {

      SJ_TMP_TABLE::TAB sjtabs[MAX_TABLES];

      table_map cur_map= join->const_table_map | PSEUDO_TABLE_BITS;

      uint jt_rowid_offset= 0; // # tuple bytes are already occupied (w/o NULL bytes)

      uint jt_null_bits= 0;    // # null bits in tuple bytes

      SJ_TMP_TABLE::TAB *last_tab= sjtabs;

      uint rowid_keep_flags= JOIN_TAB::CALL_POSITION | JOIN_TAB::KEEP_ROWID;

      JOIN_TAB *last_outer_tab= tab - 1;

      /*

        Walk through the range and remember

         - tables that need their rowids to be put into temptable

         - the last outer table

      */

      for (; tab < join->join_tab + dups_ranges[j].end_idx; tab++)

      {

        if (sj_table_is_included(join, tab))

        {

          last_tab->join_tab= tab;

          last_tab->rowid_offset= jt_rowid_offset;

          jt_rowid_offset += tab->table->file->ref_length;

          if (tab->table->maybe_null)

          {

            last_tab->null_byte= jt_null_bits / 8;

            last_tab->null_bit= jt_null_bits++;

          }

          last_tab++;

          tab->table->prepare_for_position();

          tab->rowid_keep_flags= rowid_keep_flags;

        }

        cur_map |= tab->table->map;

        if (!tab->emb_sj_nest && bitmap_covers(cur_map, 

                                               dups_ranges[j].outer_tables))

          last_outer_tab= tab;

      }

      if (jt_rowid_offset) /* Temptable has at least one rowid */

      {

        SJ_TMP_TABLE *sjtbl;

        uint tabs_size= (last_tab - sjtabs) * sizeof(SJ_TMP_TABLE::TAB);

        if (!(sjtbl= (SJ_TMP_TABLE*)thd->alloc(sizeof(SJ_TMP_TABLE))) ||

            !(sjtbl->tabs= (SJ_TMP_TABLE::TAB*) thd->alloc(tabs_size)))

          DBUG_RETURN(TRUE);

        memcpy(sjtbl->tabs, sjtabs, tabs_size);

        sjtbl->tabs_end= sjtbl->tabs + (last_tab - sjtabs);

        sjtbl->rowid_len= jt_rowid_offset;

        sjtbl->null_bits= jt_null_bits;

        sjtbl->null_bytes= (jt_null_bits + 7)/8;

        *next_sjtbl_ptr= sjtbl;

        next_sjtbl_ptr= &(sjtbl->next);

        sjtbl->next= NULL;

        sjtbl->tmp_table= 

          create_duplicate_weedout_tmp_table(thd, 

                                             sjtbl->rowid_len + 

                                             sjtbl->null_bytes,

                                             sjtbl);

        join->join_tab[dups_ranges[j].start_idx].flush_weedout_table= sjtbl;

        join->join_tab[dups_ranges[j].end_idx - 1].check_weed_out_table= sjtbl;

      }

      tab= last_outer_tab + 1;

      jump_to= last_outer_tab;

    }

    /* Create the FirstMatch tail */

    for (; tab < join->join_tab + dups_ranges[j].end_idx; tab++)

    {

      if (tab->emb_sj_nest)

        tab->do_firstmatch= jump_to; 

      else

        jump_to= tab;

    }

  }

  DBUG_RETURN(FALSE);

}

static void cleanup_sj_tmp_tables(JOIN *join)

{

  for (SJ_TMP_TABLE *sj_tbl= join->sj_tmp_tables; sj_tbl; 

       sj_tbl= sj_tbl->next)

  {

    if (sj_tbl->tmp_table)

    {

      free_tmp_table(join->thd, sj_tbl->tmp_table);

    }

  }

  join->sj_tmp_tables= NULL;

}

uint make_join_orderinfo(JOIN *join);

/**

  global select optimisation.

  @note

    error code saved in field 'error'

  @retval

    0   success

  @retval

    1   error

*/

int

JOIN::optimize()

{

  DBUG_ENTER("JOIN::optimize");

  // to prevent double initialization on EXPLAIN

  if (optimized)

    DBUG_RETURN(0);

  optimized= 1;

  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.

    */

    sel->first_cond_optimization= 0;

    /* Convert all outer joins to inner joins if possible */

    conds= simplify_joins(this, join_list, conds, TRUE, FALSE);

    build_bitmap_for_nested_joins(join_list, 0);

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

  }

  conds= optimize_cond(this, conds, join_list, &cond_value);   

  if (thd->is_error())

  {

    error= 1;

    DBUG_PRINT("error",("Error from optimize_cond"));