/*
   Copyright (c) 2011, 2019, 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, version 2.0,
   as published by the Free Software Foundation.

   This program is also distributed with certain software (including
   but not limited to OpenSSL) that is licensed under separate terms,
   as designated in a particular file or component or in included license
   documentation.  The authors of MySQL hereby grant you an additional
   permission to link the program and your derivative works with the
   separately licensed software that they have included with MySQL.

   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, version 2.0, 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 "my_dbug.h"
#include "sql/sql_bitmap.h"
#include "storage/ndb/include/ndbapi/NdbDictionary.hpp"
#include "storage/ndb/plugin/ha_ndbcluster.h"

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

namespace AQP {
class Join_plan;
class Table_access;
}  // namespace AQP

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;

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