ha_ndbcluster_push.h

/*
   Copyright (c) 2011, 2013, Oracle and/or its affiliates. All rights reserved.

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

#include "sql_bitmap.h"

class NdbTransaction;
class NdbQueryBuilder;
class NdbQueryOperand;
class NdbQueryOperationDef;
class ndb_pushed_builder_ctx;
struct NdbError;

namespace AQP{
  class Join_plan;
  class Table_access;
};

void ndbcluster_build_key_map(const NdbDictionary::Table* table, 
			      const NDB_INDEX_DATA& index,
			      const KEY *key_def,
			      uint ix_map[]);


/** 
 * This type is used in conjunction with AQP::Join_plan and represents a set 
 * of the table access operations of the join plan. 
 * Had to subclass Bitmap as the default Bitmap<64> c'tor didn't initialize its
 * map.
 */
typedef Bitmap<(MAX_TABLES > 64 ? MAX_TABLES : 64)> table_bitmap;

class ndb_table_access_map : public table_bitmap
{
public:
  explicit ndb_table_access_map()
   : table_bitmap(0)
  {}
  explicit ndb_table_access_map(uint table_no)
   : table_bitmap(0)
  { set_bit(table_no);
  }

  void add(const ndb_table_access_map& table_map)
  { // Require const_cast as signature of class Bitmap::merge is not const correct
    merge(const_cast<ndb_table_access_map&>(table_map));
  }
  void add(uint table_no)
  {
    set_bit(table_no);
  }

  bool contain(const ndb_table_access_map& table_map) const
  {
    return table_map.is_subset(*this);
  }
  bool contain(uint table_no) const
  {
    return is_set(table_no);
  }

  uint first_table(uint start= 0) const;
  uint last_table(uint start= MAX_TABLES) const;

}; // class ndb_table_access_map


/** This class represents a prepared pushed (N-way) join operation.
 *
 *  It might be instantiated multiple times whenever the query,
 *  or this subpart of the query, is being (re-)executed by
 *  ::createQuery() or it's wrapper method 
 *  ha_ndbcluster::create_pushed_join().
 */
class ndb_pushed_join
{
public:
  explicit ndb_pushed_join(const ndb_pushed_builder_ctx& builder_ctx,
                           const NdbQueryDef* query_def);
  
  ~ndb_pushed_join(); 

  /**
   * Check that this prepared pushed query matches the type
   * of operation specified by the arguments.
   */
  bool match_definition(int type, //NdbQueryOperationDef::Type, 
                        const NDB_INDEX_DATA* idx) const;

  /** Create an executable instance of this defined query. */
  NdbQuery* make_query_instance(
                        NdbTransaction* trans,
                        const NdbQueryParamValue* keyFieldParams,
                        uint paramCnt) const;

  /** Get the number of pushed table access operations.*/
  uint get_operation_count() const
  { return m_operation_count; }

  /**
   * In a pushed join, fields in lookup keys and scan bounds may refer to 
   * result fields of table access operation that execute prior to the pushed
   * join. This method returns the number of such references.
   */
  uint get_field_referrences_count() const
  { return m_field_count; }

  const NdbQueryDef& get_query_def() const
  { return *m_query_def; }

  /** Get the table that is accessed by the i'th table access operation.*/
  TABLE* get_table(uint i) const
  { 
    DBUG_ASSERT(i < m_operation_count);
    return m_tables[i];
  }

  /** 
   * This is the maximal number of fields in the key of any pushed table
   * access operation.
   */
  static const uint MAX_KEY_PART= MAX_KEY;
  /**
   * In a pushed join, fields in lookup keys and scan bounds may refer to 
   * result fields of table access operation that execute prior to the pushed
   * join. This constant specifies the maximal number of such references for 
   * a query.
   */
  static const uint MAX_REFERRED_FIELDS= 16;
  /**
   * For each table access operation in a pushed join, this is the maximal 
   * number of key fields that may refer to the fields of the parent operation.
   */
  static const uint MAX_LINKED_KEYS= MAX_KEY;
  /** 
   * This is the maximal number of table access operations there can be in a 
   * single pushed join.
   */
  static const uint MAX_PUSHED_OPERATIONS= MAX_TABLES;

private:
  const NdbQueryDef* const m_query_def;  // Definition of pushed join query

  /** This is the number of table access operations in the pushed join.*/
  uint m_operation_count;

  /** This is the tables that are accessed by the pushed join.*/
  TABLE* m_tables[MAX_PUSHED_OPERATIONS];

  /**
   * This is the number of referred fields of table access operation that 
   * execute prior to the pushed join.
   */
  const uint m_field_count;

  /**
   * These are the referred fields of table access operation that execute 
   * prior to the pushed join.
   */
  Field* m_referred_fields[MAX_REFERRED_FIELDS];
}; // class ndb_pushed_join



/**
 * Contains the context and helper methods used during ::make_pushed_join().
 *
 * Interacts with the AQP which provides interface to the query prepared by
 * the mysqld optimizer.
 *
 * Execution plans built for pushed joins are stored inside this builder context.
 */
class ndb_pushed_builder_ctx
{
  friend ndb_pushed_join::ndb_pushed_join(
                           const ndb_pushed_builder_ctx& builder_ctx,
                           const NdbQueryDef* query_def);

public:
  ndb_pushed_builder_ctx(const AQP::Join_plan& plan);
  ~ndb_pushed_builder_ctx();

  /**
   * Build the pushed query identified with 'is_pushable_with_root()'.
   * Returns:
   *   = 0: A NdbQueryDef has successfully been prepared for execution.
   *   > 0: Returned value is the error code.
   *   < 0: There is a pending NdbError to be retrieved with getNdbError()
   */
  int make_pushed_join(const AQP::Table_access* join_root,
                       const ndb_pushed_join* &pushed_join);

  const NdbError& getNdbError() const;

private:
  /**
   * Collect all tables which may be pushed together with 'root'.
   * Returns 'true' if anything is pushable.
   */
  bool is_pushable_with_root(
                  const AQP::Table_access* root);

  bool is_pushable_as_child(
                  const AQP::Table_access* table);

  bool is_const_item_pushable(
                  const Item* key_item, 
                  const KEY_PART_INFO* key_part);

  bool is_field_item_pushable(
                  const AQP::Table_access* table,
                  const Item* key_item, 
                  const KEY_PART_INFO* key_part,
                  ndb_table_access_map& parents);

  int optimize_query_plan();

  int build_query();

  void collect_key_refs(
                  const AQP::Table_access* table,
                  const Item* key_refs[]) const;

  int build_key(const AQP::Table_access* table,
                const NdbQueryOperand* op_key[]);

  uint get_table_no(const Item* key_item) const;

private:
  const AQP::Join_plan& m_plan;
  const AQP::Table_access* m_join_root;

  // Scope of tables covered by this pushed join
  ndb_table_access_map m_join_scope;

  // Scope of tables evaluated prior to 'm_join_root'
  // These are effectively const or params wrt. the pushed join
  ndb_table_access_map m_const_scope;

  // Set of tables which 'FirstMatch' algorithm will 
  // skip when a FirstMatch has been found.
  // Use a bitmap as there may be multiple usage of FirstMatch
  // in a query, and each FirstMatch may skip multiple tables.
  ndb_table_access_map m_firstmatch_skipped;

  // Number of internal operations used so far (unique lookups count as two).
  uint m_internal_op_count;

  uint m_fld_refs;
  Field* m_referred_fields[ndb_pushed_join::MAX_REFERRED_FIELDS];

  // Handle to the NdbQuery factory.
  // Possibly reused if multiple NdbQuery's are pushed.
  NdbQueryBuilder* m_builder;

  enum pushability
  {
    PUSHABLE_AS_PARENT= 0x01,
    PUSHABLE_AS_CHILD= 0x02
  } enum_pushability;

  struct pushed_tables
  {
    pushed_tables() : 
      m_maybe_pushable(0),
      m_common_parents(), 
      m_extend_parents(), 
      m_depend_parents(), 
      m_parent(MAX_TABLES), 
      m_ancestors(), 
      m_fanout(1.0),
      m_child_fanout(1.0),
      m_op(NULL) 
    {}

    int m_maybe_pushable;  // OR'ed bits from 'enum_pushability'

    /**
     * We maintain two sets of parent candidates for each table: 
     *  - 'common' are those parents for which ::collect_key_refs()
     *     will find key_refs[] (possibly through the EQ-sets) such that all
     *     linkedValues() refer fields from the same parent.
     *  - 'extended' are those parents refered from some of the 
     *     key_refs[], and having the rest of the key_refs[] available as
     *     'grandparent refs'.
     */
    ndb_table_access_map m_common_parents;
    ndb_table_access_map m_extend_parents;

    /**
     * (sub)Set of a parents which *must* be available as ancestors
     * due to dependencies on these parents tables.
     *
     * NOTE1: When the 'm_parent' has been choosen by
     *        ::optimize_query_plan(), any remaining grandparent 
     *        dependencies has to be added the 'depend_parents' 
     *        of the choosen parents such that it is taken into account
     *        when calculating the ancestor tables.
     *
     * NOTE2: These 'depend_parents' place restrictions on which of the
     *        'common', 'extend' parents above we actually may use:
     *        As all 'depend_parents' must be joined as (grand)parents 
     *        prior to one of the selected common/extend parents, only
     *        parents >= the last 'depend_parents' are the real candidates.
     *
     *        We currently mask away the unusable common/extend parents
     *        as part of ::optimize_query_plan() prior to selecting
     *        the parent.
     */
    ndb_table_access_map m_depend_parents;

    /**
     * The actual parent is choosen among (m_common_parents | m_extend_parents)
     * by ::optimize_query_plan()
     */
    uint m_parent;

    /**
     * All ancestors available throught the 'm_parent' chain
     */
    ndb_table_access_map m_ancestors;

    /**
     * The fanout of this table.
     */
    double m_fanout;

    /**
     * The (cross) product of all child fanouts.
     */
    double m_child_fanout;

    const NdbQueryOperationDef* m_op;
  } m_tables[MAX_TABLES];

  /**
   * There are two different table enumerations used:
   */
  struct table_remap
  {
    Uint16 to_external;  // m_remap[] is indexed with internal table_no
    Uint16 to_internal;  // m_remap[] is indexed with external tablenr
  } m_remap[MAX_TABLES];

}; // class ndb_pushed_builder_ctx