sql_optimizer.h

#ifndef SQL_OPTIMIZER_INCLUDED
#define SQL_OPTIMIZER_INCLUDED

/* Copyright (c) 2000, 2013, Oracle and/or its affiliates. All rights reserved.

   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., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301  USA */


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

#include "opt_explain_format.h"

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;

typedef struct st_rollup
{
  enum State { STATE_NONE, STATE_INITED, STATE_READY };
  State state;
  Item_null_array null_items;
  Ref_ptr_array *ref_pointer_arrays;
  List<Item> *fields;
} ROLLUP;

class JOIN :public Sql_alloc
{
  JOIN(const JOIN &rhs);                        
  JOIN& operator=(const JOIN &rhs);             
public:
  JOIN_TAB *join_tab,**best_ref;
  JOIN_TAB **map2table;    
  TABLE    **table;
  /*
    The table which has an index that allows to produce the requried ordering.
    A special value of 0x1 means that the ordering will be produced by
    passing 1st non-const table to filesort(). NULL means no such table exists.
  */
  TABLE    *sort_by_table;
  uint     tables;         
  uint     primary_tables; 
  uint     const_tables;   
  uint     tmp_tables;     
  uint     send_group_parts;
  bool     sort_and_group; 
  bool     first_record,full_join, no_field_update;
  bool     group;            
  bool     do_send_rows;
  table_map all_table_map;   
  table_map const_table_map; 

  table_map found_const_table_map;
  table_map outer_join;      
  /* Number of records produced after join + group operation */
  ha_rows  send_records;
  ha_rows found_records,examined_rows,row_limit;
  // m_select_limit is used to decide if we are likely to scan the whole table.
  ha_rows m_select_limit;
  ha_rows  fetch_limit;

  ha_rows  min_ft_matches;

  /* Finally picked QEP. This is result of join optimization */
  POSITION *best_positions;

/******* Join optimization state members start *******/
  
  /* Current join optimization state */
  POSITION *positions;  

  /* We also maintain a stack of join optimization states in * join->positions[] */
/******* Join optimization state members end *******/


  Next_select_func first_select;
  double   best_read;
  ha_rows  best_rowcount;
  List<Item> *fields;
  List<Cached_item> group_fields, group_fields_cache;
  THD      *thd;
  Item_sum  **sum_funcs, ***sum_funcs_end;
  Item_sum  **sum_funcs2, ***sum_funcs_end2;
  ulonglong  select_options;
  select_result *result;
  TMP_TABLE_PARAM tmp_table_param;
  MYSQL_LOCK *lock;
  SELECT_LEX_UNIT *unit;
  SELECT_LEX *select_lex;
  bool no_const_tables; 
  
  ROLLUP rollup;                                

  bool select_distinct;                         

  bool group_optimized_away;

  /*
    simple_xxxxx is set if ORDER/GROUP BY doesn't include any references
    to other tables than the first non-constant table in the JOIN.
    It's also set if ORDER/GROUP BY is empty.
    Used for deciding for or against using a temporary table to compute 
    GROUP/ORDER BY.
  */
  bool simple_order, simple_group;

  /*
    ordered_index_usage is set if an ordered index access
    should be used instead of a filesort when computing 
    ORDER/GROUP BY.
  */
  enum
  {
    ordered_index_void,       // No ordered index avail.
    ordered_index_group_by,   // Use index for GROUP BY
    ordered_index_order_by    // Use index for ORDER BY
  } ordered_index_usage;

  bool no_order;
  bool          skip_sort_order;

  bool need_tmp;
  int hidden_group_field_count;

  Key_use_array keyuse;

  List<Item> all_fields; 

  List<Item> tmp_all_fields1, tmp_all_fields2, tmp_all_fields3;
  List<Item> tmp_fields_list1, tmp_fields_list2, tmp_fields_list3;
  List<Item> &fields_list; 
  List<Item> procedure_fields_list;
  int error; 

  class ORDER_with_src
  {
    struct null {};

  public:
    ORDER *order;  //< ORDER expression that we are wrapping with this class
    Explain_sort_clause src; //< origin of order list

  private:
    int flags; //< bitmap of Explain_sort_property

  public:
    ORDER_with_src() { clean(); }

    ORDER_with_src(ORDER *order_arg, Explain_sort_clause src_arg)
    : order(order_arg), src(src_arg), flags(order_arg ? ESP_EXISTS : ESP_none)
    {}

    ORDER_with_src &operator=(null *) { clean(); return *this; }

    ORDER_with_src(null *) { clean(); }

    operator       ORDER *()       { return order; }
    operator const ORDER *() const { return order; }

    ORDER* operator->() const { return order; }
 
    void clean() { order= NULL; src= ESC_none; flags= ESP_none; }

    void set_flag(Explain_sort_property flag)
    {
      DBUG_ASSERT(order);
      flags|= flag;
    }
    void reset_flag(Explain_sort_property flag) { flags&= ~flag; }
    bool get_flag(Explain_sort_property flag) const {
      DBUG_ASSERT(order);
      return flags & flag;
    }
    int get_flags() const { DBUG_ASSERT(order); return flags; }
  };

  ORDER_with_src order, group_list;

  Explain_format_flags explain_flags;

  Item       *conds;                      
  Item       *having;                     
  Item       *having_for_explain;    
  TABLE_LIST *tables_list;           
  List<TABLE_LIST> *join_list;       
  COND_EQUAL *cond_equal;
  /*
    Join tab to return to. Points to an element of join->join_tab array, or to
    join->join_tab[-1].
    This is used at execution stage to shortcut join enumeration. Currently
    shortcutting is done to handle outer joins or handle semi-joins with
    FirstMatch strategy.
  */
  JOIN_TAB *return_tab;

  /*
    Used pointer reference for this select.
    select_lex->ref_pointer_array contains five "slices" of the same length:
    |========|========|========|========|========|
     ref_ptrs items0   items1   items2   items3
   */
  Ref_ptr_array ref_ptrs;
  // Copy of the initial slice above, to be used with different lists
  Ref_ptr_array items0, items1, items2, items3;
  // Used by rollup, to restore ref_ptrs after overwriting it.
  Ref_ptr_array current_ref_ptrs;

  const char *zero_result_cause; 
  
  bool union_part; 
  bool optimized; 

  bool child_subquery_can_materialize;
  bool allow_outer_refs;

  // true: No need to run DTORs on pointers.
  Mem_root_array<Item_exists_subselect*, true> sj_subselects;

  /* Temporary tables used to weed-out semi-join duplicates */
  List<TABLE> sj_tmp_tables;
  List<Semijoin_mat_exec> sjm_exec_list;
  /* end of allocation caching storage */

  bool set_group_rpa;
  bool group_sent;

  JOIN(THD *thd_arg, List<Item> &fields_arg, ulonglong select_options_arg,
       select_result *result_arg)
    : keyuse(thd_arg->mem_root),
      fields_list(fields_arg),
      sj_subselects(thd_arg->mem_root)
  {
    init(thd_arg, fields_arg, select_options_arg, result_arg);
  }

  void init(THD *thd_arg, List<Item> &fields_arg, ulonglong select_options_arg,
       select_result *result_arg)
  {
    join_tab= 0;
    tables= 0;
    primary_tables= 0;
    const_tables= 0;
    tmp_tables= 0;
    const_table_map= 0;
    join_list= 0;
    implicit_grouping= FALSE;
    sort_and_group= 0;
    first_record= 0;
    do_send_rows= 1;
    send_records= 0;
    found_records= 0;
    fetch_limit= HA_POS_ERROR;
    min_ft_matches= HA_POS_ERROR;
    examined_rows= 0;
    thd= thd_arg;
    sum_funcs= sum_funcs2= 0;
    having= having_for_explain= 0;
    select_options= select_options_arg;
    result= result_arg;
    lock= thd_arg->lock;
    select_lex= 0; //for safety
    select_distinct= test(select_options & SELECT_DISTINCT);
    no_order= 0;
    simple_order= 0;
    simple_group= 0;
    ordered_index_usage= ordered_index_void;
    skip_sort_order= 0;
    need_tmp= 0;
    hidden_group_field_count= 0; /*safety*/
    error= 0;
    return_tab= 0;
    ref_ptrs.reset();
    items0.reset();
    items1.reset();
    items2.reset();
    items3.reset();
    zero_result_cause= 0;
    optimized= child_subquery_can_materialize= false;
    cond_equal= 0;
    group_optimized_away= 0;

    all_fields= fields_arg;
    if (&fields_list != &fields_arg)      /* Avoid valgrind-warning */
      fields_list= fields_arg;
    keyuse.clear();
    tmp_table_param.init();
    tmp_table_param.end_write_records= HA_POS_ERROR;
    rollup.state= ROLLUP::STATE_NONE;

    no_const_tables= FALSE;
    /* can help debugging (makes smaller test cases): */
    DBUG_EXECUTE_IF("no_const_tables",no_const_tables= TRUE;);
    first_select= sub_select;
    set_group_rpa= false;
    group_sent= 0;
  }

  bool plan_is_const() const { return const_tables == primary_tables; }

  bool plan_is_single_table() { return primary_tables - const_tables == 1; }

  int prepare(TABLE_LIST *tables, uint wind_num,
              Item *conds, uint og_num, ORDER *order, ORDER *group,
              Item *having,
              SELECT_LEX *select, SELECT_LEX_UNIT *unit);
  int optimize();
  void reset();
  void exec();
  bool prepare_result(List<Item> **columns_list);
  bool explain();
  bool destroy();
  void restore_tmp();
  bool alloc_func_list();
  bool flatten_subqueries();
  bool make_sum_func_list(List<Item> &all_fields,
                          List<Item> &send_fields,
                          bool before_group_by, bool recompute= FALSE);

  Ref_ptr_array ref_ptr_array_slice(size_t slice_num)
  {
    size_t slice_sz= select_lex->ref_pointer_array.size() / 5U;
    DBUG_ASSERT(select_lex->ref_pointer_array.size() % 5 == 0);
    DBUG_ASSERT(slice_num < 5U);
    return Ref_ptr_array(&select_lex->ref_pointer_array[slice_num * slice_sz],
                         slice_sz);
  }

  void copy_ref_ptr_array(Ref_ptr_array dst_arr, Ref_ptr_array src_arr)
  {
    DBUG_ASSERT(dst_arr.size() >= src_arr.size());
    void *dest= dst_arr.array();
    const void *src= src_arr.array();
    memcpy(dest, src, src_arr.size() * src_arr.element_size());
  }

  void set_items_ref_array(Ref_ptr_array src_arr)
  {
    copy_ref_ptr_array(ref_ptrs, src_arr);
    current_ref_ptrs= src_arr;
  }

  void init_items_ref_array()
  {
    items0= ref_ptr_array_slice(1);
    copy_ref_ptr_array(items0, ref_ptrs);
    current_ref_ptrs= items0;
  }

  bool rollup_init();
  bool rollup_process_const_fields();
  bool rollup_make_fields(List<Item> &all_fields, List<Item> &fields,
                          Item_sum ***func);
  int rollup_send_data(uint idx);
  int rollup_write_data(uint idx, TABLE *table);
  void remove_subq_pushed_predicates(Item **where);
  void join_free();
  void cleanup(bool full);
  void clear();
  bool save_join_tab();
  void restore_join_tab();
  bool init_save_join_tab();
  bool send_row_on_empty_set() const
  {
    return (do_send_rows && tmp_table_param.sum_func_count != 0 &&
            group_list == NULL && !group_optimized_away &&
            select_lex->having_value != Item::COND_FALSE);
  }
  bool change_result(select_result *result);
  bool is_top_level_join() const
  {
    return (unit == &thd->lex->unit && (unit->fake_select_lex == 0 ||
                                        select_lex == unit->fake_select_lex));
  }
  bool cache_const_exprs();
  bool generate_derived_keys();
  void drop_unused_derived_keys();
  bool get_best_combination();
  bool update_equalities_for_sjm();
  bool add_sorting_to_table(JOIN_TAB *tab, ORDER_with_src *order);
  bool decide_subquery_strategy();
  void refine_best_rowcount();

private:
  void send_data();
  
  bool create_intermediate_table(JOIN_TAB *tab, List<Item> *tmp_table_fields,
                                 ORDER_with_src &tmp_table_group,
                                 bool save_sum_fields);
  bool create_first_intermediate_table();
  void optimize_distinct();

  void optimize_fts_query();


  void optimize_fts_limit_query();

  void replace_item_field(const char* field_name, Item* new_item);

#ifdef WITH_PARTITION_STORAGE_ENGINE
  bool prune_table_partitions(THD *thd);
#endif

  bool implicit_grouping; 

  void set_prefix_tables();
  void cleanup_item_list(List<Item> &items) const;
public: // @todo: Make private
  void set_semijoin_embedding();
private:
  void set_semijoin_info();
  bool set_access_methods();
  bool setup_materialized_table(JOIN_TAB *tab, uint tableno,
                                const POSITION *inner_pos,
                                POSITION *sjm_pos);
  bool make_tmp_tables_info();
  bool compare_costs_of_subquery_strategies(
         Item_exists_subselect::enum_exec_method *method);

  class Prepare_error_tracker
  {
public:
    Prepare_error_tracker(THD *thd_arg) : thd(thd_arg) {}
    ~Prepare_error_tracker()
    {
      if (unlikely(thd->is_error()))
        thd->lex->mark_broken();
    }
private:
    THD *const thd;
  };

};


bool uses_index_fields_only(Item *item, TABLE *tbl, uint keyno, 
                            bool other_tbls_ok);
void update_depend_map(JOIN *join);
void reset_nj_counters(List<TABLE_LIST> *join_list);
Item *remove_eq_conds(THD *thd, Item *cond, Item::cond_result *cond_value);
Item *optimize_cond(THD *thd, Item *conds, COND_EQUAL **cond_equal,
                    List<TABLE_LIST> *join_list,
                    bool build_equalities, Item::cond_result *cond_value);
Item* substitute_for_best_equal_field(Item *cond,
                                      COND_EQUAL *cond_equal,
                                      void *table_join_idx);
Item *build_equal_items(THD *thd, Item *cond,
                        COND_EQUAL *inherited, bool do_inherit,
                        List<TABLE_LIST> *join_list,
                        COND_EQUAL **cond_equal_ref);
bool is_indexed_agg_distinct(JOIN *join, List<Item_field> *out_args);
Key_use_array *create_keyuse_for_table(THD *thd, TABLE *table, uint keyparts,
                                       Item_field **fields,
                                       List<Item> outer_exprs);
Item_equal *find_item_equal(COND_EQUAL *cond_equal, Field *field,
                            bool *inherited_fl);
Item_field *get_best_field(Item_field *item_field, COND_EQUAL *cond_equal);
Item *
make_cond_for_table(Item *cond, table_map tables, table_map used_table,
                    bool exclude_expensive_cond);

inline bool field_time_cmp_date(const Field *f, const Item *v)
{
  return f->is_temporal() && !f->is_temporal_with_date() &&
    v->is_temporal_with_date();
}

#endif /* SQL_OPTIMIZER_INCLUDED */