~drizzle-trunk/drizzle/development

/* - mode: c; c-basic-offset: 2; indent-tabs-mode: nil; -*-

 *  vim:expandtab:shiftwidth=2:tabstop=2:smarttab:

 *

 *  Copyright (C) 2008-2009 Sun Microsystems, Inc.

 *

 *  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; either version 2 of the License, or

 *  (at your option) any later version.

 *

 *  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

 */

/**

 * @file

 *

 * Implementation of the Join class

 * 

 * @defgroup Query_Optimizer  Query Optimizer

 * @{

 */

#include <config.h>

#include <float.h>

#include <math.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/sql_select.h> /* include join.h */

#include <drizzled/lock.h>

#include <drizzled/nested_join.h>

#include <drizzled/join.h>

#include <drizzled/join_cache.h>

#include <drizzled/show.h>

#include <drizzled/field/blob.h>

#include <drizzled/open_tables_state.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/sum.h>

#include <drizzled/optimizer/explain_plan.h>

#include <drizzled/optimizer/access_method_factory.h>

#include <drizzled/optimizer/access_method.h>

#include <drizzled/records.h>

#include <drizzled/probes.h>

#include <drizzled/internal/my_bit.h>

#include <drizzled/internal/my_sys.h>

#include <drizzled/internal/iocache.h>

#include <drizzled/plugin/storage_engine.h>

#include <drizzled/session.h>

#include <drizzled/select_result.h>

#include <drizzled/debug.h>

#include <drizzled/item/subselect.h>

#include <drizzled/my_hash.h>

#include <drizzled/sql_lex.h>

#include <drizzled/statistics_variables.h>

#include <drizzled/system_variables.h>

#include <algorithm>

using namespace std;

namespace drizzled {

extern plugin::StorageEngine *heap_engine;

/** Declarations of static functions used in this source file. */

static bool make_group_fields(Join *main_join, Join *curr_join);

static void calc_group_buffer(Join *join, Order *group);

static bool alloc_group_fields(Join *join, Order *group);

static uint32_t cache_record_length(Join *join, uint32_t index);

static double prev_record_reads(Join *join, uint32_t idx, table_map found_ref);

static bool get_best_combination(Join *join);

static void set_position(Join *join,

                         uint32_t index,

                         JoinTable *table,

                         optimizer::KeyUse *key);

static bool choose_plan(Join *join,table_map join_tables);

static void best_access_path(Join *join, JoinTable *s,

                             Session *session,

                             table_map remaining_tables,

                             uint32_t 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, uint32_t depth, uint32_t prune_level);

static bool best_extension_by_limited_search(Join *join,

                                             table_map remaining_tables,

                                             uint32_t idx,

                                             double record_count,

                                             double read_time,

                                             uint32_t depth,

                                             uint32_t prune_level);

static uint32_t determine_search_depth(Join* join);

static void make_simple_join(Join*, Table*);

static void make_outerjoin_info(Join *join);

static bool make_join_select(Join *join, optimizer::SqlSelect *select,COND *item);

static void make_join_readinfo(Join&);

static void update_depend_map(Join *join);

static void update_depend_map(Join *join, Order *order);

static Order *remove_constants(Join *join,Order *first_order,COND *cond, bool change_list, bool *simple_order);

static void return_zero_rows(Join *join,

                            select_result *res,

                            TableList *tables,

                            List<Item> &fields,

                            bool send_row,

                            uint64_t select_options,

                            const char *info,

                            Item *having);

static COND *simplify_joins(Join *join, List<TableList> *join_list, COND *conds, bool top);

static int remove_duplicates(Join *join,Table *entry,List<Item> &fields, Item *having);

static int setup_without_group(Session *session, 

                               Item **ref_pointer_array,

                               TableList *tables,

                               TableList *,

                               List<Item> &fields,

                               List<Item> &all_fields,

                               COND **conds,

                               Order *order,

                               Order *group,

                               bool *hidden_group_fields);

static bool make_join_statistics(Join *join, TableList *leaves, COND *conds, DYNAMIC_ARRAY *keyuse);

static uint32_t build_bitmap_for_nested_joins(List<TableList> *join_list, uint32_t first_unused);

static Table *get_sort_by_table(Order *a, Order *b,TableList *tables);

static void reset_nj_counters(List<TableList> *join_list);

static bool test_if_subpart(Order *a,Order *b);

static void restore_prev_nj_state(JoinTable *last);

static bool add_ref_to_table_cond(Session *session, JoinTable *join_tab);

static void free_blobs(Field **ptr); /* Rename this method...conflicts with another in global namespace... */

Join::Join(Session *session_arg, 

           List<Item> &fields_arg, 

           uint64_t select_options_arg,

           select_result *result_arg) :

  join_tab(NULL),

  best_ref(NULL),

  map2table(NULL),

  join_tab_save(NULL),

  table(NULL),

  all_tables(NULL),

  sort_by_table(NULL),

  tables(0),

  outer_tables(0),

  const_tables(0),

  send_group_parts(0),

  sort_and_group(false),

  first_record(false),

  full_join(false),

  group(false),

  no_field_update(false),

  do_send_rows(true),

  resume_nested_loop(false),

  no_const_tables(false),

  select_distinct(false),

  group_optimized_away(false),

  simple_order(false),

  simple_group(false),

  no_order(false),

  skip_sort_order(false),

  union_part(false),

  optimized(false),

  need_tmp(false),

  hidden_group_fields(false),

  const_table_map(0),

  found_const_table_map(0),

  outer_join(0),

  send_records(0),

  found_records(0),

  examined_rows(0),

  row_limit(0),

  select_limit(0),

  fetch_limit(HA_POS_ERROR),

  session(session_arg),

  fields_list(fields_arg), 

  join_list(NULL),

  unit(NULL),

  select_lex(NULL),

  select(NULL),

  exec_tmp_table1(NULL),

  exec_tmp_table2(NULL),

  sum_funcs(NULL),

  sum_funcs2(NULL),

  having(NULL),

  tmp_having(NULL),

  having_history(NULL),

  select_options(select_options_arg),

  result(result_arg),

  lock(session_arg->open_tables.lock),

  tmp_join(NULL),

  all_fields(fields_arg),

  error(0),

  cond_equal(NULL),

  return_tab(NULL),

  ref_pointer_array(NULL),

  items0(NULL),

  items1(NULL),

  items2(NULL),

  items3(NULL),

  ref_pointer_array_size(0),

  zero_result_cause(NULL),

  sortorder(NULL),

  table_reexec(NULL),

  join_tab_reexec(NULL)

{

  select_distinct= test(select_options & SELECT_DISTINCT);

  if (&fields_list != &fields_arg) /* only copy if not same*/

    fields_list= fields_arg;

  memset(&keyuse, 0, sizeof(keyuse));

  tmp_table_param.init();

  tmp_table_param.end_write_records= HA_POS_ERROR;

  rollup.setState(Rollup::STATE_NONE);

}

  /** 

   * This method is currently only used when a subselect EXPLAIN is performed.

   * I pulled out the init() method and have simply reset the values to what

   * was previously in the init() method.  See the note about the hack in 

   * sql_union.cc...

   */

void Join::reset(Session *session_arg, 

                 List<Item> &fields_arg, 

                 uint64_t select_options_arg,

                 select_result *result_arg)

{

  join_tab= NULL;

  best_ref= NULL;

  map2table= NULL;

  join_tab_save= NULL;

  table= NULL;

  all_tables= NULL;

  sort_by_table= NULL;

  tables= 0;

  outer_tables= 0;

  const_tables= 0;

  send_group_parts= 0;

  sort_and_group= false;

  first_record= false;

  full_join= false;

  group= false;

  no_field_update= false;

  do_send_rows= true;

  resume_nested_loop= false;

  no_const_tables= false;

  select_distinct= false;

  group_optimized_away= false;

  simple_order= false;

  simple_group= false;

  no_order= false;

  skip_sort_order= false;

  union_part= false;

  optimized= false;

  need_tmp= false;

  hidden_group_fields= false;

  const_table_map= 0;

  found_const_table_map= 0;

  outer_join= 0;

  send_records= 0;

  found_records= 0;

  examined_rows= 0;

  row_limit= 0;

  select_limit= 0;

  fetch_limit= HA_POS_ERROR;

  session= session_arg;

  fields_list= fields_arg; 

  join_list= NULL;

  unit= NULL;

  select_lex= NULL;

  select= NULL;

  exec_tmp_table1= NULL;

  exec_tmp_table2= NULL;

  sum_funcs= NULL;

  sum_funcs2= NULL;

  having= NULL;

  tmp_having= NULL;

  having_history= NULL;

  select_options= select_options_arg;

  result= result_arg;

  lock= session_arg->open_tables.lock;

  tmp_join= NULL;

  all_fields= fields_arg;

  error= 0;

  cond_equal= NULL;

  return_tab= NULL;

  ref_pointer_array= NULL;

  items0= NULL;

  items1= NULL;

  items2= NULL;

  items3= NULL;

  ref_pointer_array_size= 0;

  zero_result_cause= NULL;

  sortorder= NULL;

  table_reexec= NULL;

  join_tab_reexec= NULL;

  select_distinct= test(select_options & SELECT_DISTINCT);

  if (&fields_list != &fields_arg) /* only copy if not same*/

    fields_list= fields_arg;

  memset(&keyuse, 0, sizeof(keyuse));

  tmp_table_param.init();

  tmp_table_param.end_write_records= HA_POS_ERROR;

  rollup.setState(Rollup::STATE_NONE);

}

bool Join::is_top_level_join() const

{

  return unit == &session->lex().unit && (unit->fake_select_lex == 0 || select_lex == unit->fake_select_lex);

}

/**

  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,

                  TableList *tables_init,

                  uint32_t wild_num,

                  COND *conds_init,

                  uint32_t og_num,

                  Order *order_init,

                  Order *group_init,

                  Item *having_init,

                  Select_Lex *select_lex_arg,

                  Select_Lex_Unit *unit_arg)

{

  // to prevent double initialization on EXPLAIN

  if (optimized)

    return 0;

  conds= conds_init;

  order= order_init;

  group_list= group_init;

  having= having_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();

  session->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 (session->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(session, &select_lex->context, join_list, tables_list, &select_lex->leaf_tables, false))

  {

      return(-1);

  }

  TableList *table_ptr;

  for (table_ptr= select_lex->leaf_tables; table_ptr; table_ptr= table_ptr->next_leaf)

  {

    tables++;

  }

  if (setup_wild(session, fields_list, &all_fields, wild_num))

    return -1;

  select_lex->setup_ref_array(session, og_num);

  if (setup_fields(session, *rref_pointer_array, fields_list, MARK_COLUMNS_READ, &all_fields, 1) ||

    setup_without_group(session, *rref_pointer_array, tables_list, select_lex->leaf_tables, fields_list,

    all_fields, &conds, order, group_list, &hidden_group_fields))

    return -1;

  ref_pointer_array= *rref_pointer_array;

  if (having)

  {

    nesting_map save_allow_sum_func= session->lex().allow_sum_func;

    session->setWhere("having clause");

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

        having->check_cols(1)));

    select_lex->having_fix_field= 0;

    if (having_fix_rc || session->is_error())

      return(-1);

    session->lex().allow_sum_func= save_allow_sum_func;

  }

  {

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

    {

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

        in_subs= (Item_in_subselect*)subselect;

      {

        bool do_materialize= true;

        /*

          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

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

        {

          return((trans_res == Item_subselect::RES_ERROR));

        }

      }

    }

  }

  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(session, ref_pointer_array, all_fields);

    }

  }

  if (having && having->with_sum_func)

    having->split_sum_func(session, 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_func(session, ref_pointer_array,

                               all_fields, item_sum->ref_by, false);

    } while (item_sum != end);

  }

  if (select_lex->inner_refs_list.size() &&

      fix_inner_refs(session, all_fields, select_lex, ref_pointer_array))

    return(-1);

  /*

    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.test(NON_AGG_FIELD_USED) &&

      select_lex->full_group_by_flag.test(SUM_FUNC_USED))

  {

    my_message(ER_MIX_OF_GROUP_FUNC_AND_FIELDS,

               ER(ER_MIX_OF_GROUP_FUNC_AND_FIELDS), MYF(0));

    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)

    return(-1);

  /* 

   * The below will create the new table for

   * CREATE TABLE ... SELECT

   *

   * @see create_table_from_items() in drizzled/sql_insert.cc

   */

  if (result && result->prepare(fields_list, unit_arg))

    return(-1);

  /* Init join struct */

  count_field_types(select_lex, &tmp_table_param, all_fields, 0);

  ref_pointer_array_size= all_fields.size() * 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));

    return(-1);

  }

#endif

  if (select_lex->olap == ROLLUP_TYPE && rollup_init())

    return(-1);

  if (alloc_func_list())

    return(-1);

  return 0; // All OK

}

/*

  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;

  }

}

/**

  global select optimisation.

  @note

    error code saved in field 'error'

  @retval

    0   success

  @retval

    1   error

*/

int Join::optimize()

{

  // to prevent double initialization on EXPLAIN

  if (optimized)

    return 0;

  optimized= 1;

  session->set_proc_info("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 (session->lex().ignore)

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

    {

      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(session, &conds);

      conds->change_ref_to_fields(session, tables_list);

      conds->top_level_item();

      having= 0;

    }

  }

#endif

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

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

  if (session->is_error())

  {

    error= 1;

    return 1;

  }

  {

    having= optimize_cond(this, having, join_list, &having_value);

    if (session->is_error())

    {

      error= 1;

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

      zero_result_cause=  having_value == Item::COND_FALSE ?

                           "Impossible HAVING" : "Impossible WHERE";

      tables = 0;

      goto setup_subq_exit;

    }

  }

  /* Optimize count(*), cmin() and cmax() */

  if (tables_list && tmp_table_param.sum_func_count && ! group_list)

  {

    int res;

    /*

      optimizer::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= optimizer::sum_query(select_lex->leaf_tables, all_fields, conds)))

    {

      if (res == HA_ERR_KEY_NOT_FOUND)

      {

        zero_result_cause= "No matching min/max row";

        tables = 0;

        goto setup_subq_exit;

      }

      if (res > 1)

      {

        error= res;

        return 1;

      }

      if (res < 0)

      {

        zero_result_cause= "No matching min/max row";

        tables = 0;

        goto setup_subq_exit;

      }

      zero_result_cause= "Select tables optimized away";

      tables_list= 0;       // All tables resolved

      const_tables= tables;

      /*

        Extract all table-independent conditions and replace the WHERE

        clause with them. All other conditions were computed by optimizer::sum_query