~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

 *

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

using namespace std;

namespace drizzled

{

extern plugin::StorageEngine *heap_engine;

extern std::bitset<12> test_flags;

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

static bool alloc_group_fields(Join *join,order_st *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 bool make_simple_join(Join *join,Table *tmp_table);

static void make_outerjoin_info(Join *join);

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

static bool make_join_readinfo(Join *join);

static void update_depend_map(Join *join);

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

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

static int 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_st *order,

                               order_st *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_st *a,order_st *b,TableList *tables);

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

static bool test_if_subpart(order_st *a,order_st *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... */

/**

  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_st *order_init,

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

      select_lex->setup_ref_array(session, og_num) ||

      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->where="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_st *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.elements &&

      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_st *group_tmp= group_list ; group_tmp ; group_tmp= group_tmp->next)

      send_group_parts++;

  }

  if (error)

    goto err;

  /* 

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

    goto err;

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

  return(0); // All OK

err:

  return(-1);

}

/*

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

        and the MIN/MAX/COUNT function(s) have been replaced by constants,

        so there is no need to compute the whole WHERE clause again.

        Notice that make_cond_for_table() will always succeed to remove all

        computed conditions, because optimizer::sum_query() is applicable only to

        conjunctions.

        Preserve conditions for EXPLAIN.

      */

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

      {

        COND *table_independent_conds= make_cond_for_table(conds, PSEUDO_TABLE_BITS, 0, 0);

        conds= table_independent_conds;

      }

      goto setup_subq_exit;

    }

  }

  if (!tables_list)

  {

    error= 0;

    return(0);

  }

  error= -1;          // Error is sent to client

  sort_by_table= get_sort_by_table(order, group_list, select_lex->leaf_tables);

  /* Calculate how to do the join */

  session->set_proc_info("statistics");

  if (make_join_statistics(this, select_lex->leaf_tables, conds, &keyuse) ||

      session->is_fatal_error)

  {

    return 1;

  }

  /* Remove distinct if only const tables */

  select_distinct= select_distinct && (const_tables != tables);

  session->set_proc_info("preparing");

  if (result->initialize_tables(this))

  {

    return 1;        // error == -1

  }

  if (const_table_map != found_const_table_map &&

      !(select_options & SELECT_DESCRIBE) &&

      (!conds ||

       !(conds->used_tables() & RAND_TABLE_BIT) ||

       select_lex->master_unit() == &session->lex->unit)) // upper level SELECT

  {

    zero_result_cause= "no matching row in const table";

    goto setup_subq_exit;

  }

  if (!(session->options & OPTION_BIG_SELECTS) &&

      best_read > (double) session->variables.max_join_size &&

      !(select_options & SELECT_DESCRIBE))

  {

    my_message(ER_TOO_BIG_SELECT, ER(ER_TOO_BIG_SELECT), MYF(0));

    error= -1;

    return 1;

  }

  if (const_tables && !(select_options & SELECT_NO_UNLOCK))

    mysql_unlock_some_tables(session, table, const_tables);

  if (!conds && outer_join)

  {

    /* Handle the case where we have an OUTER JOIN without a WHERE */

    conds=new Item_int((int64_t) 1,1);  // Always true

  }

  select= optimizer::make_select(*table, const_table_map,

                                 const_table_map, conds, 1, &error);

  if (error)

  {

    error= -1;

    return 1;

  }

  reset_nj_counters(join_list);

  make_outerjoin_info(this);

  /*

    Among the equal fields belonging to the same multiple equality

    choose the one that is to be retrieved first and substitute

    all references to these in where condition for a reference for

    the selected field.

  */

  if (conds)

  {

    conds= substitute_for_best_equal_field(conds, cond_equal, map2table);

    conds->update_used_tables();

  }

  /*

    Permorm the the optimization on fields evaluation mentioned above

    for all on expressions.

  */

  for (JoinTable *tab= join_tab + const_tables; tab < join_tab + tables ; tab++)

  {

    if (*tab->on_expr_ref)

    {

      *tab->on_expr_ref= substitute_for_best_equal_field(*tab->on_expr_ref,

                                                         tab->cond_equal,

                                                         map2table);

      (*tab->on_expr_ref)->update_used_tables();

    }

  }

  if (conds &&!outer_join && const_table_map != found_const_table_map &&

      (select_options & SELECT_DESCRIBE) &&

      select_lex->master_unit() == &session->lex->unit) // upper level SELECT

  {

    conds=new Item_int((int64_t) 0,1);  // Always false

  }

  if (make_join_select(this, select, conds))

  {

    zero_result_cause=

      "Impossible WHERE noticed after reading const tables";

    goto setup_subq_exit;

  }

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

  /* Optimize distinct away if possible */

  {

    order_st *org_order= order;

    order= remove_constants(this, order,conds,1, &simple_order);

    if (session->is_error())

    {

      error= 1;

      return 1;

    }

    /*

      If we are using ORDER BY NULL or ORDER BY const_expression,

      return result in any order (even if we are using a GROUP BY)

    */

    if (!order && org_order)

      skip_sort_order= 1;

  }

  /*

     Check if we can optimize away GROUP BY/DISTINCT.

     We can do that if there are no aggregate functions, the

     fields in DISTINCT clause (if present) and/or columns in GROUP BY

     (if present) contain direct references to all key parts of

     an unique index (in whatever order) and if the key parts of the

     unique index cannot contain NULLs.

     Note that the unique keys for DISTINCT and GROUP BY should not

     be the same (as long as they are unique).

     The FROM clause must contain a single non-constant table.

  */

  if (tables - const_tables == 1 && (group_list || select_distinct) &&

      ! tmp_table_param.sum_func_count &&

      (! join_tab[const_tables].select ||

       ! join_tab[const_tables].select->quick ||

       join_tab[const_tables].select->quick->get_type() !=

       optimizer::QuickSelectInterface::QS_TYPE_GROUP_MIN_MAX))

  {

    if (group_list && list_contains_unique_index(join_tab[const_tables].table, find_field_in_order_list, (void *) group_list))

    {

      /*

        We have found that grouping can be removed since groups correspond to

        only one row anyway, but we still have to guarantee correct result

        order. The line below effectively rewrites the query from GROUP BY

        <fields> to ORDER BY <fields>. There are two exceptions:

        - if skip_sort_order is set (see above), then we can simply skip

          GROUP BY;

        - we can only rewrite ORDER BY if the ORDER BY fields are 'compatible'

          with the GROUP BY ones, i.e. either one is a prefix of another.

          We only check if the ORDER BY is a prefix of GROUP BY. In this case

          test_if_subpart() copies the ASC/DESC attributes from the original

          ORDER BY fields.

          If GROUP BY is a prefix of order_st BY, then it is safe to leave

          'order' as is.

       */

      if (! order || test_if_subpart(group_list, order))

          order= skip_sort_order ? 0 : group_list;

      /*

        If we have an IGNORE INDEX FOR GROUP BY(fields) clause, this must be

        rewritten to IGNORE INDEX FOR order_st BY(fields).

      */

      join_tab->table->keys_in_use_for_order_by=

        join_tab->table->keys_in_use_for_group_by;

      group_list= 0;

      group= 0;

    }

    if (select_distinct &&

       list_contains_unique_index(join_tab[const_tables].table,

                                 find_field_in_item_list,

                                 (void *) &fields_list))

    {

      select_distinct= 0;

    }

  }

  if (group_list || tmp_table_param.sum_func_count)

  {

    if (! hidden_group_fields && rollup.state == ROLLUP::STATE_NONE)

      select_distinct=0;

  }

  else if (select_distinct && tables - const_tables == 1)