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

 */

/*

  TODO:

  Fix that MAYBE_KEY are stored in the tree so that we can detect use

  of full hash keys for queries like:

  select s.id, kws.keyword_id from sites as s,kws where s.id=kws.site_id and kws.keyword_id in (204,205);

*/

/*

  This cursor contains:

  RangeAnalysisModule

    A module that accepts a condition, index (or partitioning) description,

    and builds lists of intervals (in index/partitioning space), such that

    all possible records that match the condition are contained within the

    intervals.

    The entry point for the range analysis module is get_mm_tree() function.

    The lists are returned in form of complicated structure of interlinked

    optimizer::SEL_TREE/optimizer::SEL_IMERGE/SEL_ARG objects.

    See quick_range_seq_next, find_used_partitions for examples of how to walk

    this structure.

    All direct "users" of this module are located within this cursor, too.

  Range/index_merge/groupby-minmax optimizer module

    A module that accepts a table, condition, and returns

     - a QUICK_*_SELECT object that can be used to retrieve rows that match

       the specified condition, or a "no records will match the condition"

       statement.

    The module entry points are

      test_quick_select()

      get_quick_select_for_ref()

  Record retrieval code for range/index_merge/groupby-min-max.

    Implementations of QUICK_*_SELECT classes.

  KeyTupleFormat

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

  The code in this cursor (and elsewhere) makes operations on key value tuples.

  Those tuples are stored in the following format:

  The tuple is a sequence of key part values. The length of key part value

  depends only on its type (and not depends on the what value is stored)

    KeyTuple: keypart1-data, keypart2-data, ...

  The value of each keypart is stored in the following format:

    keypart_data: [isnull_byte] keypart-value-bytes

  If a keypart may have a NULL value (key_part->field->real_maybe_null() can

  be used to check this), then the first byte is a NULL indicator with the

  following valid values:

    1  - keypart has NULL value.

    0  - keypart has non-NULL value.

  <questionable-statement> If isnull_byte==1 (NULL value), then the following

  keypart->length bytes must be 0.

  </questionable-statement>

  keypart-value-bytes holds the value. Its format depends on the field type.

  The length of keypart-value-bytes may or may not depend on the value being

  stored. The default is that length is static and equal to

  KeyPartInfo::length.

  Key parts with (key_part_flag & HA_BLOB_PART) have length depending of the

  value:

     keypart-value-bytes: value_length value_bytes

  The value_length part itself occupies HA_KEY_BLOB_LENGTH=2 bytes.

  See key_copy() and key_restore() for code to move data between index tuple

  and table record

  CAUTION: the above description is only sergefp's understanding of the

           subject and may omit some details.

*/

#include "config.h"

#include <math.h>

#include <float.h>

#include <string>

#include <vector>

#include <algorithm>

#include <boost/dynamic_bitset.hpp>

#include "drizzled/sql_base.h"

#include "drizzled/sql_select.h"

#include "drizzled/error.h"

#include "drizzled/optimizer/cost_vector.h"

#include "drizzled/item/cmpfunc.h"

#include "drizzled/field/num.h"

#include "drizzled/check_stack_overrun.h"

#include "drizzled/optimizer/sum.h"

#include "drizzled/optimizer/range.h"

#include "drizzled/optimizer/quick_range.h"

#include "drizzled/optimizer/quick_range_select.h"

#include "drizzled/optimizer/quick_group_min_max_select.h"

#include "drizzled/optimizer/quick_index_merge_select.h"

#include "drizzled/optimizer/quick_ror_intersect_select.h"

#include "drizzled/optimizer/quick_ror_union_select.h"

#include "drizzled/optimizer/table_read_plan.h"

#include "drizzled/optimizer/sel_arg.h"

#include "drizzled/optimizer/sel_imerge.h"

#include "drizzled/optimizer/sel_tree.h"

#include "drizzled/optimizer/range_param.h"

#include "drizzled/records.h"

#include "drizzled/internal/my_sys.h"

#include "drizzled/internal/iocache.h"

#include "drizzled/temporal.h" /* Needed in get_mm_leaf() for timestamp -> datetime comparisons */

using namespace std;

namespace drizzled

{

#define HA_END_SPACE_KEY 0

/*

  Convert double value to #rows. Currently this does floor(), and we

  might consider using round() instead.

*/

static inline ha_rows double2rows(double x)

{

    return static_cast<ha_rows>(x);

}

static unsigned char is_null_string[2]= {1,0};

/**

  Get cost of reading nrows table records in a "disk sweep"

  A disk sweep read is a sequence of Cursor->rnd_pos(rowid) calls that made

  for an ordered sequence of rowids.

  We assume hard disk IO. The read is performed as follows:

   1. The disk head is moved to the needed cylinder

   2. The controller waits for the plate to rotate

   3. The data is transferred

  Time to do #3 is insignificant compared to #2+#1.

  Time to move the disk head is proportional to head travel distance.

  Time to wait for the plate to rotate depends on whether the disk head

  was moved or not.

  If disk head wasn't moved, the wait time is proportional to distance

  between the previous block and the block we're reading.

  If the head was moved, we don't know how much we'll need to wait for the

  plate to rotate. We assume the wait time to be a variate with a mean of

  0.5 of full rotation time.

  Our cost units are "random disk seeks". The cost of random disk seek is

  actually not a constant, it depends one range of cylinders we're going

  to access. We make it constant by introducing a fuzzy concept of "typical

  datafile length" (it's fuzzy as it's hard to tell whether it should

  include index cursor, temp.tables etc). Then random seek cost is:

    1 = half_rotation_cost + move_cost * 1/3 * typical_data_file_length

  We define half_rotation_cost as DISK_SEEK_BASE_COST=0.9.

  @param table             Table to be accessed

  @param nrows             Number of rows to retrieve

  @param interrupted       true <=> Assume that the disk sweep will be

                           interrupted by other disk IO. false - otherwise.

  @param cost         OUT  The cost.

*/

static void get_sweep_read_cost(Table *table,

                                ha_rows nrows,

                                bool interrupted,

                                optimizer::CostVector *cost)

{

  cost->zero();

  if (table->cursor->primary_key_is_clustered())

  {

    cost->setIOCount(table->cursor->read_time(table->getShare()->getPrimaryKey(),

                                             static_cast<uint32_t>(nrows),

                                             nrows));

  }

  else

  {

    double n_blocks=

      ceil(uint64_t2double(table->cursor->stats.data_file_length) / IO_SIZE);

    double busy_blocks=

      n_blocks * (1.0 - pow(1.0 - 1.0/n_blocks, rows2double(nrows)));

    if (busy_blocks < 1.0)

      busy_blocks= 1.0;

    cost->setIOCount(busy_blocks);

    if (! interrupted)

    {

      /* Assume reading is done in one 'sweep' */

      cost->setAvgIOCost((DISK_SEEK_BASE_COST +

                          DISK_SEEK_PROP_COST*n_blocks/busy_blocks));

    }

  }

}

static optimizer::SEL_TREE * get_mm_parts(optimizer::RangeParameter *param,

                               COND *cond_func,

                               Field *field,

			                         Item_func::Functype type,

                               Item *value,

			                         Item_result cmp_type);

static optimizer::SEL_ARG *get_mm_leaf(optimizer::RangeParameter *param,

                                       COND *cond_func,

                                       Field *field,

                                       KEY_PART *key_part,

			                                 Item_func::Functype type,

                                       Item *value);

static optimizer::SEL_TREE *get_mm_tree(optimizer::RangeParameter *param, COND *cond);

static bool is_key_scan_ror(optimizer::Parameter *param, uint32_t keynr, uint8_t nparts);

static ha_rows check_quick_select(Session *session,

                                  optimizer::Parameter *param,

                                  uint32_t idx,

                                  bool index_only,

                                  optimizer::SEL_ARG *tree,

                                  bool update_tbl_stats,

                                  uint32_t *mrr_flags,

                                  uint32_t *bufsize,

                                  optimizer::CostVector *cost);

static optimizer::RangeReadPlan *get_key_scans_params(Session *session,

                                                      optimizer::Parameter *param,

                                                      optimizer::SEL_TREE *tree,

                                                      bool index_read_must_be_used,

                                                      bool update_tbl_stats,

                                                      double read_time);

static

optimizer::RorIntersectReadPlan *get_best_ror_intersect(const optimizer::Parameter *param,

                                                        optimizer::SEL_TREE *tree,

                                                        double read_time,

                                                        bool *are_all_covering);

static

optimizer::RorIntersectReadPlan *get_best_covering_ror_intersect(optimizer::Parameter *param,

                                                                 optimizer::SEL_TREE *tree,

                                                                 double read_time);

static

optimizer::TableReadPlan *get_best_disjunct_quick(Session *session,

                                                  optimizer::Parameter *param,

                                                  optimizer::SEL_IMERGE *imerge,

                                                  double read_time);

static

optimizer::GroupMinMaxReadPlan *get_best_group_min_max(optimizer::Parameter *param, optimizer::SEL_TREE *tree);

static optimizer::SEL_TREE *tree_and(optimizer::RangeParameter *param, 

                                     optimizer::SEL_TREE *tree1, 

                                     optimizer::SEL_TREE *tree2);

static optimizer::SEL_ARG *sel_add(optimizer::SEL_ARG *key1, optimizer::SEL_ARG *key2);

static optimizer::SEL_ARG *key_and(optimizer::RangeParameter *param,

                                   optimizer::SEL_ARG *key1,

                                   optimizer::SEL_ARG *key2,

                                   uint32_t clone_flag);

static bool get_range(optimizer::SEL_ARG **e1, optimizer::SEL_ARG **e2, optimizer::SEL_ARG *root1);

optimizer::SEL_ARG optimizer::null_element(optimizer::SEL_ARG::IMPOSSIBLE);

static bool null_part_in_key(KEY_PART *key_part,

                             const unsigned char *key,

                             uint32_t length);

bool sel_trees_can_be_ored(optimizer::SEL_TREE *tree1, 

                           optimizer::SEL_TREE *tree2, 

                           optimizer::RangeParameter *param);

/*

  Perform AND operation on two index_merge lists and store result in *im1.

*/

inline void imerge_list_and_list(List<optimizer::SEL_IMERGE> *im1, List<optimizer::SEL_IMERGE> *im2)

{

  im1->concat(im2);

}

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

** Basic functions for SqlSelect and QuickRangeSelect

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

	/* make a select from mysql info

	   Error is set as following:

	   0 = ok

	   1 = Got some error (out of memory?)

	   */

optimizer::SqlSelect *optimizer::make_select(Table *head,

                                             table_map const_tables,

                                             table_map read_tables,

                                             COND *conds,

                                             bool allow_null_cond,

                                             int *error)

{

  optimizer::SqlSelect *select= NULL;

  *error= 0;

  if (! conds && ! allow_null_cond)

  {

    return 0;

  }

  if (! (select= new optimizer::SqlSelect))

  {

    *error= 1;			// out of memory

    return 0;

  }

  select->read_tables=read_tables;

  select->const_tables=const_tables;

  select->head=head;

  select->cond=conds;

  if (head->sort.io_cache)

  {

    memcpy(select->file, head->sort.io_cache, sizeof(internal::IO_CACHE));

    select->records=(ha_rows) (select->file->end_of_file/

			       head->cursor->ref_length);

    delete head->sort.io_cache;

    head->sort.io_cache=0;

  }

  return(select);

}

optimizer::SqlSelect::SqlSelect() 

  :

    quick(NULL),

    cond(NULL),

    file(static_cast<internal::IO_CACHE *>(memory::sql_calloc(sizeof(internal::IO_CACHE)))),

    free_cond(false)

{

  quick_keys.reset();

  needed_reg.reset();

  my_b_clear(file);

}

void optimizer::SqlSelect::cleanup()

{

  if (quick)

  {

    delete quick;

    quick= NULL;

  }

  if (free_cond)

  {

    free_cond= 0;

    delete cond;

    cond= 0;

  }

  file->close_cached_file();

}

optimizer::SqlSelect::~SqlSelect()

{

  cleanup();

}

bool optimizer::SqlSelect::check_quick(Session *session, 

                                       bool force_quick_range,

                                       ha_rows limit)

{

  key_map tmp;

  tmp.set();

  return (test_quick_select(session, 

                           tmp, 

                           0, 

                           limit,

                           force_quick_range, 

                           false) < 0);

}

bool optimizer::SqlSelect::skip_record()

{

  return (cond ? cond->val_int() == 0 : 0);

}

optimizer::QuickSelectInterface::QuickSelectInterface()

  :

    max_used_key_length(0),

    used_key_parts(0)

{}

/*

  Find the best index to retrieve first N records in given order

  SYNOPSIS

    get_index_for_order()

      table  Table to be accessed

      order  Required ordering

      limit  Number of records that will be retrieved

  DESCRIPTION

    Find the best index that allows to retrieve first #limit records in the

    given order cheaper then one would retrieve them using full table scan.

  IMPLEMENTATION

    Run through all table indexes and find the shortest index that allows

    records to be retrieved in given order. We look for the shortest index

    as we will have fewer index pages to read with it.

    This function is used only by UPDATE/DELETE, so we take into account how

    the UPDATE/DELETE code will work:

     * index can only be scanned in forward direction

     * HA_EXTRA_KEYREAD will not be used

    Perhaps these assumptions could be relaxed.

  RETURN

    Number of the index that produces the required ordering in the cheapest way

    MAX_KEY if no such index was found.

*/

uint32_t optimizer::get_index_for_order(Table *table, Order *order, ha_rows limit)

{

  uint32_t idx;

  uint32_t match_key= MAX_KEY, match_key_len= MAX_KEY_LENGTH + 1;

  Order *ord;

  for (ord= order; ord; ord= ord->next)

    if (!ord->asc)

      return MAX_KEY;

  for (idx= 0; idx < table->getShare()->sizeKeys(); idx++)

  {

    if (!(table->keys_in_use_for_query.test(idx)))

      continue;

    KeyPartInfo *keyinfo= table->key_info[idx].key_part;

    uint32_t n_parts=  table->key_info[idx].key_parts;

    uint32_t partno= 0;

    /*

      The below check is sufficient considering we now have either BTREE

      indexes (records are returned in order for any index prefix) or HASH

      indexes (records are not returned in order for any index prefix).

    */

    if (! (table->index_flags(idx) & HA_READ_ORDER))

      continue;

    for (ord= order; ord && partno < n_parts; ord= ord->next, partno++)

    {

      Item *item= order->item[0];

      if (! (item->type() == Item::FIELD_ITEM &&

           ((Item_field*)item)->field->eq(keyinfo[partno].field)))

        break;

    }

    if (! ord && table->key_info[idx].key_length < match_key_len)

    {

      /*

        Ok, the ordering is compatible and this key is shorter then

        previous match (we want shorter keys as we'll have to read fewer

        index pages for the same number of records)

      */

      match_key= idx;

      match_key_len= table->key_info[idx].key_length;

    }

  }

  if (match_key != MAX_KEY)

  {

    /*

      Found an index that allows records to be retrieved in the requested

      order. Now we'll check if using the index is cheaper then doing a table

      scan.

    */

    double full_scan_time= table->cursor->scan_time();

    double index_scan_time= table->cursor->read_time(match_key, 1, limit);

    if (index_scan_time > full_scan_time)

      match_key= MAX_KEY;

  }

  return match_key;

}

/*

  Fill param->needed_fields with bitmap of fields used in the query.

  SYNOPSIS

    fill_used_fields_bitmap()

      param Parameter from test_quick_select function.

  NOTES

    Clustered PK members are not put into the bitmap as they are implicitly

    present in all keys (and it is impossible to avoid reading them).

  RETURN

    0  Ok

    1  Out of memory.

*/

static int fill_used_fields_bitmap(optimizer::Parameter *param)

{

  Table *table= param->table;

  uint32_t pk;

  param->tmp_covered_fields.clear();

  param->needed_fields.resize(table->getShare()->sizeFields());

  param->needed_fields.reset();

  param->needed_fields|= *table->read_set;

  param->needed_fields|= *table->write_set;

  pk= param->table->getShare()->getPrimaryKey();

  if (pk != MAX_KEY && param->table->cursor->primary_key_is_clustered())

  {

    /* The table uses clustered PK and it is not internally generated */

    KeyPartInfo *key_part= param->table->key_info[pk].key_part;

    KeyPartInfo *key_part_end= key_part +

                                 param->table->key_info[pk].key_parts;

    for (;key_part != key_part_end; ++key_part)

      param->needed_fields.reset(key_part->fieldnr-1);

  }

  return 0;

}

/*

  Test if a key can be used in different ranges

  SYNOPSIS

    SqlSelect::test_quick_select()

      session               Current thread

      keys_to_use       Keys to use for range retrieval

      prev_tables       Tables assumed to be already read when the scan is

                        performed (but not read at the moment of this call)

      limit             Query limit

      force_quick_range Prefer to use range (instead of full table scan) even

                        if it is more expensive.

  NOTES

    Updates the following in the select parameter:

      needed_reg - Bits for keys with may be used if all prev regs are read

      quick      - Parameter to use when reading records.

    In the table struct the following information is updated:

      quick_keys           - Which keys can be used

      quick_rows           - How many rows the key matches

      quick_condition_rows - E(# rows that will satisfy the table condition)

  IMPLEMENTATION

    quick_condition_rows value is obtained as follows:

      It is a minimum of E(#output rows) for all considered table access

      methods (range and index_merge accesses over various indexes).

    The obtained value is not a true E(#rows that satisfy table condition)

    but rather a pessimistic estimate. To obtain a true E(#...) one would

    need to combine estimates of various access methods, taking into account

    correlations between sets of rows they will return.

    For example, if values of tbl.key1 and tbl.key2 are independent (a right

    assumption if we have no information about their correlation) then the

    correct estimate will be:

      E(#rows("tbl.key1 < c1 AND tbl.key2 < c2")) =

      = E(#rows(tbl.key1 < c1)) / total_rows(tbl) * E(#rows(tbl.key2 < c2)

    which is smaller than

       MIN(E(#rows(tbl.key1 < c1), E(#rows(tbl.key2 < c2)))

    which is currently produced.

  TODO

   * Change the value returned in quick_condition_rows from a pessimistic

     estimate to true E(#rows that satisfy table condition).

     (we can re-use some of E(#rows) calcuation code from index_merge/intersection

      for this)

   * Check if this function really needs to modify keys_to_use, and change the

     code to pass it by reference if it doesn't.

   * In addition to force_quick_range other means can be (an usually are) used

     to make this function prefer range over full table scan. Figure out if

     force_quick_range is really needed.

  RETURN

   -1 if impossible select (i.e. certainly no rows will be selected)

    0 if can't use quick_select

    1 if found usable ranges and quick select has been successfully created.

*/

int optimizer::SqlSelect::test_quick_select(Session *session,

                                            key_map keys_to_use,

				                                    table_map prev_tables,

				                                    ha_rows limit,

                                            bool force_quick_range,

                                            bool ordered_output)

{

  uint32_t idx;

  double scan_time;

  if (quick)

  {

    delete quick;

    quick= NULL;

  }

  needed_reg.reset();

  quick_keys.reset();

  if (keys_to_use.none())

    return 0;

  records= head->cursor->stats.records;

  if (!records)

    records++;

  scan_time= (double) records / TIME_FOR_COMPARE + 1;

  read_time= (double) head->cursor->scan_time() + scan_time + 1.1;

  if (head->force_index)

    scan_time= read_time= DBL_MAX;

  if (limit < records)

    read_time= (double) records + scan_time + 1; // Force to use index

  else if (read_time <= 2.0 && !force_quick_range)

    return 0;				/* No need for quick select */

  keys_to_use&= head->keys_in_use_for_query;

  if (keys_to_use.any())

  {

    memory::Root alloc;

    optimizer::SEL_TREE *tree= NULL;

    KEY_PART *key_parts;

    KeyInfo *key_info;

    optimizer::Parameter param;

    if (check_stack_overrun(session, 2*STACK_MIN_SIZE, NULL))

      return 0;                           // Fatal error flag is set

    /* set up parameter that is passed to all functions */

    param.session= session;

    param.prev_tables= prev_tables | const_tables;

    param.read_tables= read_tables;

    param.current_table= head->map;

    param.table=head;

    param.keys=0;

    param.mem_root= &alloc;

    param.old_root= session->mem_root;

    param.needed_reg= &needed_reg;

    param.imerge_cost_buff_size= 0;

    param.using_real_indexes= true;

    param.remove_jump_scans= true;

    param.force_default_mrr= ordered_output;

    session->no_errors=1;				// Don't warn about NULL

    memory::init_sql_alloc(&alloc, session->variables.range_alloc_block_size, 0);

    if (!(param.key_parts= (KEY_PART*) alloc.alloc_root( sizeof(KEY_PART) * head->getShare()->key_parts)) ||

        fill_used_fields_bitmap(&param))

    {

      session->no_errors=0;

      alloc.free_root(MYF(0));			// Return memory & allocator

      return 0;				// Can't use range

    }

    key_parts= param.key_parts;

    session->mem_root= &alloc;

    /*

      Make an array with description of all key parts of all table keys.

      This is used in get_mm_parts function.

    */

    key_info= head->key_info;

    for (idx=0 ; idx < head->getShare()->sizeKeys() ; idx++, key_info++)

    {

      KeyPartInfo *key_part_info;

      if (! keys_to_use.test(idx))

	continue;

      param.key[param.keys]=key_parts;

      key_part_info= key_info->key_part;