~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

 */

#ifndef DRIZZLED_OPTIMIZER_QUICK_INDEX_MERGE_SELECT_H

#define DRIZZLED_OPTIMIZER_QUICK_INDEX_MERGE_SELECT_H

#include "drizzled/optimizer/range.h"

#include <boost/dynamic_bitset.hpp>

#include <vector>

namespace drizzled

{

namespace optimizer

{

/**

  @class QuickIndexMergeSelect - index_merge access method quick select.

    QuickIndexMergeSelect uses

     * QuickRangeSelects to get rows

     * Unique class to remove duplicate rows

  INDEX MERGE OPTIMIZER

    Current implementation doesn't detect all cases where index_merge could

    be used, in particular:

     * index_merge will never be used if range scan is possible (even if

       range scan is more expensive)

     * index_merge+'using index' is not supported (this the consequence of

       the above restriction)

     * If WHERE part contains complex nested AND and OR conditions, some ways

       to retrieve rows using index_merge will not be considered. The choice

       of read plan may depend on the order of conjuncts/disjuncts in WHERE

       part of the query, see comments near imerge_list_or_list and

       SEL_IMERGE::or_sel_tree_with_checks functions for details.

     * There is no "index_merge_ref" method (but index_merge on non-first

       table in join is possible with 'range checked for each record').

    See comments around SEL_IMERGE class and test_quick_select for more

    details.

  ROW RETRIEVAL ALGORITHM

    index_merge uses Unique class for duplicates removal.  index_merge takes

    advantage of Clustered Primary Key (CPK) if the table has one.

    The index_merge algorithm consists of two phases:

    Phase 1 (implemented in QuickIndexMergeSelect::prepare_unique):

    prepare()

    {

      activate 'index only';

      while(retrieve next row for non-CPK scan)

      {

        if (there is a CPK scan and row will be retrieved by it)

          skip this row;

        else

          put its rowid into Unique;

      }

      deactivate 'index only';

    }

    Phase 2 (implemented as sequence of QuickIndexMergeSelect::get_next

    calls):

    fetch()

    {

      retrieve all rows from row pointers stored in Unique;

      free Unique;

      retrieve all rows for CPK scan;

    }

*/

class QuickIndexMergeSelect : public QuickSelectInterface

{

public:

  QuickIndexMergeSelect(Session *session, Table *table);

  ~QuickIndexMergeSelect();

  int init();

  int reset(void);

  /**

   * Get next row for index_merge.

   * NOTES

   * The rows are read from

   * 1. rowids stored in Unique.

   * 2. QuickRangeSelect with clustered primary key (if any).

   * The sets of rows retrieved in 1) and 2) are guaranteed to be disjoint.

   */

  int get_next();

  bool reverse_sorted() const

  {

    return false;

  }

  bool unique_key_range() const

  {

    return false;

  }

  int get_type() const

  {

    return QS_TYPE_INDEX_MERGE;

  }

  void add_keys_and_lengths(String *key_names, String *used_lengths);

  void add_info_string(String *str);

  bool is_keys_used(const boost::dynamic_bitset<>& fields);

  bool push_quick_back(QuickRangeSelect *quick_sel_range);

  /* range quick selects this index_merge read consists of */

  std::vector<QuickRangeSelect *> quick_selects;

  /* quick select that uses clustered primary key (NULL if none) */

  QuickRangeSelect *pk_quick_select;

  /* true if this select is currently doing a clustered PK scan */

  bool  doing_pk_scan;

  memory::Root alloc;

  Session *session;

  /**

   * Perform key scans for all used indexes (except CPK), get rowids and merge

   * them into an ordered non-recurrent sequence of rowids.

   *

   * The merge/duplicate removal is performed using Unique class. We put all

   * rowids into Unique, get the sorted sequence and destroy the Unique.

   *

   * If table has a clustered primary key that covers all rows (true for bdb

   * and innodb currently) and one of the index_merge scans is a scan on PK,

   * then rows that will be retrieved by PK scan are not put into Unique and

   * primary key scan is not performed here, it is performed later separately.

   *

   * RETURN

   * @retval 0     OK

   * @retval other error

   */

  int read_keys_and_merge();

  /* used to get rows collected in Unique */

  ReadRecord read_record;

};

} /* namespace optimizer */

} /* namespace drizzled */

#endif /* DRIZZLED_OPTIMIZER_QUICK_INDEX_MERGE_SELECT_H */