~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

  @{

*/

#include "config.h"

#include <string>

#include <iostream>

#include <algorithm>

#include <vector>

#include "drizzled/sql_select.h" /* include join.h */

#include "drizzled/error.h"

#include "drizzled/gettext.h"

#include "drizzled/util/test.h"

#include "drizzled/name_resolution_context_state.h"

#include "drizzled/nested_join.h"

#include "drizzled/probes.h"

#include "drizzled/show.h"

#include "drizzled/item/cache.h"

#include "drizzled/item/cmpfunc.h"

#include "drizzled/item/copy_string.h"

#include "drizzled/item/uint.h"

#include "drizzled/cached_item.h"

#include "drizzled/sql_base.h"

#include "drizzled/field/blob.h"

#include "drizzled/check_stack_overrun.h"

#include "drizzled/lock.h"

#include "drizzled/item/outer_ref.h"

#include "drizzled/index_hint.h"

#include "drizzled/memory/multi_malloc.h"

#include "drizzled/records.h"

#include "drizzled/internal/iocache.h"

#include "drizzled/sql_union.h"

#include "drizzled/optimizer/key_field.h"

#include "drizzled/optimizer/position.h"

#include "drizzled/optimizer/sargable_param.h"

#include "drizzled/optimizer/key_use.h"

#include "drizzled/optimizer/range.h"

#include "drizzled/optimizer/quick_range_select.h"

#include "drizzled/optimizer/quick_ror_intersect_select.h"

using namespace std;

namespace drizzled

{

static int sort_keyuse(optimizer::KeyUse *a, optimizer::KeyUse *b);

static COND *build_equal_items(Session *session, COND *cond,

                               COND_EQUAL *inherited,

                               List<TableList> *join_list,

                               COND_EQUAL **cond_equal_ref);

static Item* part_of_refkey(Table *form,Field *field);

static bool cmp_buffer_with_ref(JoinTable *tab);

static void change_cond_ref_to_const(Session *session,

                                     vector<COND_CMP>& save_list,

                                     Item *and_father,

                                     Item *cond,

                                     Item *field,

                                     Item *value);

static bool copy_blobs(Field **ptr);

static bool eval_const_cond(COND *cond)

{

    return ((Item_func*) cond)->val_int() ? true : false;

}

/*

  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 copy_blobs(Field **ptr)

{

  for (; *ptr ; ptr++)

  {

    if ((*ptr)->flags & BLOB_FLAG)

      if (((Field_blob *) (*ptr))->copy())

	return 1;				// Error

  }

  return 0;

}

/**

  This handles SELECT with and without UNION.

*/

bool handle_select(Session *session, LEX *lex, select_result *result,

                   uint64_t setup_tables_done_option)

{

  bool res;

  register Select_Lex *select_lex= &lex->select_lex;

  DRIZZLE_SELECT_START(session->query.c_str());

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

      select_lex->master_unit()->fake_select_lex)

    res= drizzle_union(session, lex, result, &lex->unit,

		       setup_tables_done_option);

  else

  {

    Select_Lex_Unit *unit= &lex->unit;

    unit->set_limit(unit->global_parameters);

    session->session_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(session, &select_lex->ref_pointer_array,

		      (TableList*) 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_st*) select_lex->order_list.first,

		      (order_st*) select_lex->group_list.first,

		      select_lex->having,

		      select_lex->options | session->options |

                      setup_tables_done_option,

		      result, unit, select_lex);

  }

  res|= session->is_error();

  if (unlikely(res))

    result->abort();

  DRIZZLE_SELECT_DONE(res, session->limit_found_rows);

  return res;

}

/*

  Fix fields referenced from inner selects.

  SYNOPSIS

    fix_inner_refs()

    session               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(Session *session, 

                    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(session, 0))

      return true;

    session->used_tables|= item->used_tables();

  }

  return res;

}

/*****************************************************************************

  Check fields, find best join, do the select and output fields.

  mysql_select assumes that all tables are already opened

*****************************************************************************/

/*

  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.

*/

void save_index_subquery_explain_info(JoinTable *join_tab, Item* where)

{

  join_tab->packed_info= TAB_INFO_HAVE_VALUE;

  if (join_tab->table->covering_keys.test(join_tab->ref.key))

    join_tab->packed_info |= TAB_INFO_USING_INDEX;

  if (where)

    join_tab->packed_info |= TAB_INFO_USING_WHERE;

  for (uint32_t 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;

    }

  }

}

/**

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

  @param session                  thread Cursor

  @param rref_pointer_array   a reference to ref_pointer_array of

                              the top-level select_lex for this query

  @param tables               list of all tables used in this query.

                              The tables have been pre-opened.

  @param 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.

  @param 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.

  @param conds                top level item of an expression representing

                              WHERE clause of the top level select

  @param og_num               total number of ORDER BY and GROUP BY clauses

                              arguments

  @param order                linked list of ORDER BY agruments

  @param group                linked list of GROUP BY arguments

  @param having               top level item of HAVING expression

  @param select_options       select options (BIG_RESULT, etc)

  @param 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.

  @param select_lex           the only Select_Lex of this query

  @param 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.

  @retval

    false  success

  @retval

    true   an error

*/

bool mysql_select(Session *session,

                  Item ***rref_pointer_array,

                  TableList *tables, 

                  uint32_t wild_num, 

                  List<Item> &fields,

                  COND *conds, 

                  uint32_t og_num,  

                  order_st *order, 

                  order_st *group,

                  Item *having, 

                  uint64_t select_options,

                  select_result *result, 

                  Select_Lex_Unit *unit,

                  Select_Lex *select_lex)

{

  bool err;

  bool free_join= 1;

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

        {

          return(true);

        }

      }

      else

      {

        if ((err= join->prepare(rref_pointer_array, tables, wild_num,

                               conds, og_num, order, group, having, select_lex, unit)))

        {

          goto err;

        }

      }

    }

    free_join= 0;

    join->select_options= select_options;

  }

  else

  {

    if (!(join= new JOIN(session, fields, select_options, result)))

      return(true);

    session->set_proc_info("init");

    session->used_tables=0;                         // Updated by setup_fields

    if ((err= join->prepare(rref_pointer_array, tables, wild_num,

                           conds, og_num, order, group, having,

                           select_lex, unit)) == true)

    {

      goto err;

    }

  }

  err= join->optimize();

  if (err)

  {

    goto err; // 1

  }

  if (session->lex->describe & DESCRIBE_EXTENDED)

  {

    join->conds_history= join->conds;

    join->having_history= (join->having?join->having:join->tmp_having);

  }

  if (session->is_error())

    goto err;

  join->exec();

  if (session->lex->describe & DESCRIBE_EXTENDED)

  {

    select_lex->where= join->conds_history;

    select_lex->having= join->having_history;

  }

err:

  if (free_join)

  {

    session->set_proc_info("end");

    err|= select_lex->cleanup();

    return(err || session->is_error());

  }

  return(join->error);

}

inline Item *and_items(Item* cond, Item *item)

{

  return (cond? (new Item_cond_and(cond, item)) : item);

}

static void fix_list_after_tbl_changes(Select_Lex *new_parent, List<TableList> *tlist)

{

  List_iterator<TableList> it(*tlist);

  TableList *table;

  while ((table= it++))

  {

    if (table->on_expr)

      table->on_expr->fix_after_pullout(new_parent, &table->on_expr);

    if (table->nested_join)

      fix_list_after_tbl_changes(new_parent, &table->nested_join->join_list);

  }

}

/*****************************************************************************

  Create JoinTableS, make a guess about the table types,

  Approximate how many records will be used in each table

*****************************************************************************/

ha_rows get_quick_record_count(Session *session, optimizer::SqlSelect *select, Table *table, const key_map *keys,ha_rows limit)

{

  int error;

  if (check_stack_overrun(session, STACK_MIN_SIZE, NULL))

    return(0);                           // Fatal error flag is set

  if (select)

  {

    select->head=table;

    table->reginfo.impossible_range=0;

    if ((error= select->test_quick_select(session, *(key_map *)keys,(table_map) 0,

                                          limit, 0, false)) == 1)

      return(select->quick->records);

    if (error == -1)

    {

      table->reginfo.impossible_range=1;

      return(0);

    }

  }

  return(HA_POS_ERROR);			/* This shouldn't happend */

}

/*****************************************************************************

  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

*****************************************************************************/

/**

  Add all keys with uses 'field' for some keypart.

  If field->and_level != and_level then only mark key_part as const_part.

*/

uint32_t max_part_bit(key_part_map bits)

{

  uint32_t found;

  for (found=0; bits & 1 ; found++,bits>>=1) ;

  return found;

}

static int sort_keyuse(optimizer::KeyUse *a, optimizer::KeyUse *b)

{

  int res;

  if (a->getTable()->tablenr != b->getTable()->tablenr)

    return static_cast<int>((a->getTable()->tablenr - b->getTable()->tablenr));

  if (a->getKey() != b->getKey())

    return static_cast<int>((a->getKey() - b->getKey()));

  if (a->getKeypart() != b->getKeypart())

    return static_cast<int>((a->getKeypart() - b->getKeypart()));

  // Place const values before other ones

  if ((res= test((a->getUsedTables() & ~OUTER_REF_TABLE_BIT)) -

       test((b->getUsedTables() & ~OUTER_REF_TABLE_BIT))))

    return res;

  /* Place rows that are not 'OPTIMIZE_REF_OR_NULL' first */

  return static_cast<int>(((a->getOptimizeFlags() & KEY_OPTIMIZE_REF_OR_NULL) -

		          (b->getOptimizeFlags() & KEY_OPTIMIZE_REF_OR_NULL)));

}

/**

  Update keyuse array with all possible keys we can use to fetch rows.

  @param       session

  @param[out]  keyuse         Put here ordered array of KeyUse structures

  @param       join_tab       Array in tablenr_order

  @param       tables         Number of tables in join

  @param       cond           WHERE condition (note that the function analyzes

                              join_tab[i]->on_expr too)

  @param       normal_tables  Tables not inner w.r.t some outer join (ones

                              for which we can make ref access based the WHERE

                              clause)

  @param       select_lex     current SELECT

  @param[out]  sargables      std::vector of found sargable candidates

   @retval

     0  OK

   @retval

     1  Out of memory.

*/

bool update_ref_and_keys(Session *session,

                         DYNAMIC_ARRAY *keyuse,

                         JoinTable *join_tab,

                         uint32_t tables,

                         COND *cond, 

                         COND_EQUAL *,

                         table_map normal_tables,

                         Select_Lex *select_lex,

                         vector<optimizer::SargableParam> &sargables)

{

  uint	and_level,i,found_eq_constant;

  optimizer::KeyField *key_fields, *end, *field;

  uint32_t sz;

  uint32_t m= max(select_lex->max_equal_elems,(uint32_t)1);

  /*

    All predicates that are used to fill arrays of KeyField

    and SargableParam classes have at most 2 arguments

    except BETWEEN predicates that have 3 arguments and

    IN predicates.

    This any predicate if it's not BETWEEN/IN can be used

    directly to fill at most 2 array elements, either of KeyField 

    or SargableParam type. For a BETWEEN predicate 3 elements

    can be filled as this predicate is considered as

    saragable with respect to each of its argument.

    An IN predicate can require at most 1 element as currently

    it is considered as sargable only for its first argument.

    Multiple equality can add  elements that are filled after

    substitution of field arguments by equal fields. There

    can be not more than select_lex->max_equal_elems such

    substitutions.

  */

  sz= sizeof(optimizer::KeyField) *

      (((session->lex->current_select->cond_count+1) +

	session->lex->current_select->between_count)*m+1);

  if (! (key_fields= (optimizer::KeyField*) session->alloc(sz)))

    return true;

  and_level= 0;

  field= end= key_fields;

  if (my_init_dynamic_array(keyuse, sizeof(optimizer::KeyUse), 20, 64))

    return true;

  if (cond)

  {

    add_key_fields(join_tab->join, &end, &and_level, cond, normal_tables,

                   sargables);

    for (; field != end; field++)

    {

      add_key_part(keyuse, field);

      /* Mark that we can optimize LEFT JOIN */

      if (field->getValue()->type() == Item::NULL_ITEM &&

	  ! field->getField()->real_maybe_null())

      {

	field->getField()->table->reginfo.not_exists_optimize= 1;

      }

    }

  }

  for (i= 0; i < tables; i++)

  {

    /*

      Block the creation of keys for inner tables of outer joins.

      Here only the outer joins that can not be converted to

      inner joins are left and all nests that can be eliminated

      are flattened.

      In the future when we introduce conditional accesses

      for inner tables in outer joins these keys will be taken

      into account as well.

    */

    if (*join_tab[i].on_expr_ref)

      add_key_fields(join_tab->join, &end, &and_level,

                     *join_tab[i].on_expr_ref,

                     join_tab[i].table->map, sargables);

  }

  /* Process ON conditions for the nested joins */

  {

    List_iterator<TableList> li(*join_tab->join->join_list);

    TableList *table;

    while ((table= li++))

    {

      if (table->nested_join)

        add_key_fields_for_nj(join_tab->join, table, &end, &and_level,

                              sargables);

    }

  }

  /* fill keyuse with found key parts */

  for ( ; field != end ; field++)

    add_key_part(keyuse,field);

  /*

    Sort the array of possible keys and remove the following key parts:

    - ref if there is a keypart which is a ref and a const.

      (e.g. if there is a key(a,b) and the clause is a=3 and b=7 and b=t2.d,

      then we skip the key part corresponding to b=t2.d)

    - keyparts without previous keyparts

      (e.g. if there is a key(a,b,c) but only b < 5 (or a=2 and c < 3) is

      used in the query, we drop the partial key parts from consideration).

  */

  if (keyuse->elements)

  {

    optimizer::KeyUse key_end,*prev,*save_pos,*use;

    internal::my_qsort(keyuse->buffer,keyuse->elements,sizeof(optimizer::KeyUse),

                       (qsort_cmp) sort_keyuse);

    memset(&key_end, 0, sizeof(key_end)); /* Add for easy testing */

    insert_dynamic(keyuse,(unsigned char*) &key_end);

    use= save_pos= dynamic_element(keyuse, 0, optimizer::KeyUse*);

    prev= &key_end;

    found_eq_constant= 0;

    for (i= 0; i < keyuse->elements-1; i++, use++)

    {

      if (! use->getUsedTables() && use->getOptimizeFlags() != KEY_OPTIMIZE_REF_OR_NULL)

        use->getTable()->const_key_parts[use->getKey()]|= use->getKeypartMap();

      if (use->getKey() == prev->getKey() && use->getTable() == prev->getTable())

      {

        if (prev->getKeypart() + 1 < use->getKeypart() || 

            ((prev->getKeypart() == use->getKeypart()) && found_eq_constant))

          continue;				/* remove */

      }

      else if (use->getKeypart() != 0)		// First found must be 0

        continue;

#ifdef HAVE_purify

      /* Valgrind complains about overlapped memcpy when save_pos==use. */

      if (save_pos != use)

#endif

        *save_pos= *use;

      prev=use;

      found_eq_constant= ! use->getUsedTables();

      /* Save ptr to first use */

      if (! use->getTable()->reginfo.join_tab->keyuse)

        use->getTable()->reginfo.join_tab->keyuse= save_pos;

      use->getTable()->reginfo.join_tab->checked_keys.set(use->getKey());

      save_pos++;

    }

    i= (uint32_t) (save_pos - (optimizer::KeyUse*) keyuse->buffer);