sql_select.h

#ifndef SQL_SELECT_INCLUDED
#define SQL_SELECT_INCLUDED

/* Copyright (c) 2000, 2014, 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 */


/**
  @file

  @brief
  classes to use when handling where clause
*/

#include "procedure.h"
#include <myisam.h>
#include "sql_array.h"                        /* Array */
#include "records.h"                          /* READ_RECORD */
#include "opt_range.h"                /* SQL_SELECT, QUICK_SELECT_I */
#include "filesort.h"

#include "mem_root_array.h"
#include "sql_executor.h"
#include "opt_explain_format.h" // for Extra_tag

#include <functional>
/**
   Returns a constant of type 'type' with the 'A' lowest-weight bits set.
   Example: LOWER_BITS(uint, 3) == 7.
   Requirement: A < sizeof(type) * 8.
*/
#define LOWER_BITS(type,A)	((type) (((type) 1 << (A)) -1))

/* Values in optimize */
#define KEY_OPTIMIZE_EXISTS		1
#define KEY_OPTIMIZE_REF_OR_NULL	2
#define FT_KEYPART                      (MAX_REF_PARTS+10)

/**
  A Key_use represents an equality predicate of the form (table.column = val),
  where the column is indexed by @c keypart in @c key and @c val is either a
  constant, a column from other table, or an expression over column(s) from
  other table(s). If @c val is not a constant, then the Key_use specifies an
  equi-join predicate, and @c table must be put in the join plan after all
  tables in @c used_tables.

  At an abstract level a Key_use instance can be viewed as a directed arc
  of an equi-join graph, where the arc originates from the table(s)
  containing the column(s) that produce the values used for index lookup
  into @c table, and the arc points into @c table.

  For instance, assuming there is only an index t3(c), the query

  @code
    SELECT * FROM t1, t2, t3
    WHERE t1.a = t3.c AND
          t2.b = t3.c;
  @endcode

  would generate two arcs (instances of Key_use)

  @code
     t1-- a ->- c --.
                    |
                    V
                    t3
                    ^
                    |
     t2-- b ->- c --'
  @endcode

  If there were indexes t1(a), and t2(b), then the equi-join graph
  would have two additional arcs "c->a" and "c->b" recording the fact
  that it is possible to perform lookup in either direction.

  @code
    t1-- a ->- c --.    ,-- c -<- b --- t2
     ^             |    |               ^
     |             |    |               |
     `-- a -<- c - v    v-- c ->- b ----'
                     t3
  @endcode

  The query

  @code
    SELECT * FROM t1, t2, t3 WHERE t1.a + t2.b = t3.c;
  @endcode

  can be viewed as a graph with one "multi-source" arc:

  @code
    t1-- a ---
              |
               >-- c --> t3
              |
    t2-- b ---
  @endcode

  The graph of all equi-join conditions usable for index lookup is
  stored as an ordered sequence of Key_use elements in
  JOIN::keyuse_array. See sort_keyuse() for details on the
  ordering. Each JOIN_TAB::keyuse points to the first array element
  with the same table.
*/
class Key_use {
public:
  // We need the default constructor for unit testing.
  Key_use()
    : table(NULL),
      val(NULL),
      used_tables(0),
      key(0),
      keypart(0),
      optimize(0),
      keypart_map(0),
      ref_table_rows(0),
      null_rejecting(false),
      cond_guard(NULL),
      sj_pred_no(UINT_MAX),
      bound_keyparts(0),
      fanout(0.0),
      read_cost(0.0)
  {}

  Key_use(TABLE *table_arg, Item *val_arg, table_map used_tables_arg,
          uint key_arg, uint keypart_arg, uint optimize_arg,
          key_part_map keypart_map_arg, ha_rows ref_table_rows_arg,
          bool null_rejecting_arg, bool *cond_guard_arg,
          uint sj_pred_no_arg) :
  table(table_arg), val(val_arg), used_tables(used_tables_arg),
  key(key_arg), keypart(keypart_arg), optimize(optimize_arg),
  keypart_map(keypart_map_arg), ref_table_rows(ref_table_rows_arg),
  null_rejecting(null_rejecting_arg), cond_guard(cond_guard_arg),
  sj_pred_no(sj_pred_no_arg), bound_keyparts(0), fanout(0.0),
  read_cost(0.0)
  {}

  TABLE *table;            ///< table owning the index

  /**
    Value used for lookup into @c key. It may be an Item_field, a
    constant or any other expression. If @c val contains a field from
    another table, then we have a join condition, and the table(s) of
    the field(s) in @c val should be before @c table in the join plan.
  */
  Item	*val;

  /**
    All tables used in @c val, that is all tables that provide bindings
    for the expression @c val. These tables must be in the plan before
    executing the equi-join described by a Key_use.
  */
  table_map used_tables;
  uint key;                ///< number of index
  uint keypart;            ///< used part of the index
  uint optimize;           ///< 0, or KEY_OPTIMIZE_*
  key_part_map keypart_map;       ///< like keypart, but as a bitmap
  ha_rows      ref_table_rows;    ///< Estimate of how many rows for a key value
  /**
    If true, the comparison this value was created from will not be
    satisfied if val has NULL 'value'.
    Not used if the index is fulltext (such index cannot be used for
    equalities).
  */
  bool null_rejecting;
  /**
    !NULL - This Key_use was created from an equality that was wrapped into
            an Item_func_trig_cond. This means the equality (and validity of
            this Key_use element) can be turned on and off. The on/off state
            is indicted by the pointed value:
              *cond_guard == TRUE <=> equality condition is on
              *cond_guard == FALSE <=> equality condition is off

    NULL  - Otherwise (the source equality can't be turned off)

    Not used if the index is fulltext (such index cannot be used for
    equalities).
  */
  bool *cond_guard;
  /**
     0..63    <=> This was created from semi-join IN-equality # sj_pred_no.
     UINT_MAX  Otherwise

     Not used if the index is fulltext (such index cannot be used for
     semijoin).

     @see get_semi_join_select_list_index()
  */
  uint         sj_pred_no;

  /*
    The three members below are different from the rest of Key_use: they are
    set only by Optimize_table_order, and they change with the currently
    considered join prefix.
  */

  /**
     The key columns which are equal to expressions depending only of earlier
     tables of the current join prefix.
     This information is stored only in the first Key_use of the index.
  */
  key_part_map bound_keyparts;

  /**
     Fanout of the ref access path for this index, in the current join
     prefix.
     This information is stored only in the first Key_use of the index.
  */
  double fanout;

  /**
    Cost of the ref access path for the current join prefix, i.e. the
    cost of using ref access once multiplied by estimated number of
    partial rows from tables earlier in the join sequence.
    read_cost does NOT include cost of processing rows on the
    server side (row_evaluate_cost).

    Example: If the cost of ref access on this index is 5, and the
    estimated number of partial rows from earlier tables is 10,
    read_cost=50.

    This information is stored only in the first Key_use of the index.
  */
  double read_cost;
};


// Key_use has a trivial destructor, no need to run it from Mem_root_array.
typedef Mem_root_array<Key_use, true> Key_use_array;

class store_key;

typedef struct st_table_ref : public Sql_alloc
{
  bool		key_err;
  /** True if something was read into buffer in join_read_key.  */
  bool          has_record;
  uint          key_parts;                ///< num of ...
  uint          key_length;               ///< length of key_buff
  int           key;                      ///< key no
  uchar         *key_buff;                ///< value to look for with key
  uchar         *key_buff2;               ///< key_buff+key_length
  /**
     Used to store the value from each keypart field. These values are
     used for ref access. If key_copy[key_part] == NULL it means that
     the value is constant and does not need to be reevaluated
  */
  store_key     **key_copy;
  Item          **items;                  ///< val()'s for each keypart
  /*  
    Array of pointers to trigger variables. Some/all of the pointers may be
    NULL.  The ref access can be used iff
    
      for each used key part i, (!cond_guards[i] || *cond_guards[i]) 

    This array is used by subquery code. The subquery code may inject
    triggered conditions, i.e. conditions that can be 'switched off'. A ref 
    access created from such condition is not valid when at least one of the 
    underlying conditions is switched off (see subquery code for more details).
    If a table in a subquery has this it means that the table access 
    will switch from ref access to table scan when the outer query 
    produces a NULL value to be checked for in the subquery. This will
    be used by NOT IN subqueries and IN subqueries for which 
    is_top_level_item() returns false.
  */
  bool          **cond_guards;
  /**
    (null_rejecting & (1<<i)) means the condition is '=' and no matching
    rows will be produced if items[i] IS NULL (see add_not_null_conds())
  */
  key_part_map  null_rejecting;
  table_map	depend_map;		  ///< Table depends on these tables.
  /* null byte position in the key_buf. Used for REF_OR_NULL optimization */
  uchar          *null_ref_key;
  /*
    The number of times the record associated with this key was used
    in the join.
  */
  ha_rows       use_count;

  /*
    TRUE <=> disable the "cache" as doing lookup with the same key value may
    produce different results (because of Index Condition Pushdown)
  */
  bool          disable_cache;

  st_table_ref()
    : key_err(TRUE),
      has_record(FALSE),
      key_parts(0),
      key_length(0),
      key(-1),
      key_buff(NULL),
      key_buff2(NULL),
      key_copy(NULL),
      items(NULL),
      cond_guards(NULL),
      null_rejecting(0),
      depend_map(0),
      null_ref_key(NULL),
      use_count(0),
      disable_cache(FALSE)
  {
  }

  /**
    @returns whether the reference contains NULL values which could never give
    a match.
  */
  bool impossible_null_ref() const
  {
    if (null_rejecting != 0)
    {
      for (uint i= 0 ; i < key_parts ; i++)
      {
        if ((null_rejecting & 1 << i) && items[i]->is_null())
          return TRUE;
      }
    }
    return FALSE;
  }


  /**
    Check if there are triggered/guarded conditions that might be
    'switched off' by the subquery code when executing 'Full scan on
    NULL key' subqueries.

    @return true if there are guarded conditions, false otherwise
  */

  bool has_guarded_conds() const
  {
    DBUG_ASSERT(key_parts == 0 || cond_guards != NULL);

    for (uint i = 0; i < key_parts; i++)
    {
      if (cond_guards[i])
        return true;
    }
    return false;
  }
} TABLE_REF;


/*
  The structs which holds the join connections and join states
*/
enum join_type { /*
                   Initial state. Access type has not yet been decided
                   for the table
                 */
                 JT_UNKNOWN,
                 /* Table has exactly one row */
                 JT_SYSTEM,
                 /*
                   Table has at most one matching row. Values read
                   from this row can be treated as constants. Example:
                   "WHERE table.pk = 3"
                  */
                 JT_CONST,
                 /*
                   '=' operator is used on unique index. At most one
                   row is read for each combination of rows from
                   preceding tables
                 */
                 JT_EQ_REF,
                 /*
                   '=' operator is used on non-unique index
                 */
                 JT_REF,
                 /*
                   Full table scan.
                 */
                 JT_ALL,
                 /*
                   Range scan.
                 */
                 JT_RANGE,
                 /*
                   Like table scan, but scans index leaves instead of
                   the table
                 */
                 JT_INDEX_SCAN,
                 /* Fulltext index is used */
                 JT_FT,
                 /*
                   Like ref, but with extra search for NULL values.
                   E.g. used for "WHERE col = ... OR col IS NULL"
                  */
                 JT_REF_OR_NULL,
                 /*
                   Like eq_ref for subqueries: Replaces subquery with
                   index lookup in unique index
                  */
                 JT_UNIQUE_SUBQUERY,
                 /*
                   Like unique_subquery but for non-unique index
                 */
                 JT_INDEX_SUBQUERY,
                 /*
                   Do multiple range scans over one table and combine
                   the results into one. The merge can be used to
                   produce unions and intersections
                 */
                 JT_INDEX_MERGE};

/// @returns join type according to quick select type used
join_type calc_join_type(int quick_type);

class JOIN;

/* Values for JOIN_TAB::packed_info */
#define TAB_INFO_HAVE_VALUE 1
#define TAB_INFO_USING_INDEX 2
#define TAB_INFO_USING_WHERE 4
#define TAB_INFO_FULL_SCAN_ON_NULL 8

class JOIN_CACHE;
class SJ_TMP_TABLE;

#define SJ_OPT_NONE 0
#define SJ_OPT_DUPS_WEEDOUT 1
#define SJ_OPT_LOOSE_SCAN   2
#define SJ_OPT_FIRST_MATCH  3
#define SJ_OPT_MATERIALIZE_LOOKUP  4
#define SJ_OPT_MATERIALIZE_SCAN  5

inline bool sj_is_materialize_strategy(uint strategy)
{
  return strategy >= SJ_OPT_MATERIALIZE_LOOKUP;
}

/** 
    Bits describing quick select type
*/
enum quick_type { QS_NONE, QS_RANGE, QS_DYNAMIC_RANGE};


/**
  A position of table within a join order. This structure is primarily used
  as a part of join->positions and join->best_positions arrays.

  One POSITION element contains information about:
   - Which table is accessed
   - Which access method was chosen
      = Its cost and #of output records
   - Semi-join strategy choice. Note that there are two different
     representation formats:
      1. The one used during join optimization
      2. The one used at plan refinement/code generation stage.
      We call fix_semijoin_strategies_for_picked_join_order() to switch
      between #1 and #2. See that function's comment for more details.

   - Semi-join optimization state. When we're running join optimization, 
     we main a state for every semi-join strategy which are various
     variables that tell us if/at which point we could consider applying the
     strategy.  
     The variables are really a function of join prefix but they are too
     expensive to re-caclulate for every join prefix we consider, so we
     maintain current state in join->positions[#tables_in_prefix]. See
     advance_sj_state() for details.

  This class has to stay a POD, because it is memcpy'd in many places.
*/

typedef struct st_position : public Sql_alloc
{
  /**
    The number of rows that will be fetched by the chosen access
    method per each row combination of previous tables. That is:

      rows_fetched = selectivity(access_condition) * cardinality(table)

    where 'access_condition' is whatever condition was chosen for
    index access, depending on the access method ('ref', 'range',
    etc.)

    @Note that for index/table scans, rows_fetched may be less than
    the number of rows in the table because the cost of evaluating
    constant conditions is included in the scan cost, and the number
    of rows produced by these scans is the estimated number of rows
    that pass the constant conditions. @see
    Optimize_table_order::calculate_scan_cost()
  */
  double rows_fetched;

  /**
    Cost of accessing the table in course of the entire complete join
    execution, i.e. cost of one access method use (e.g. 'range' or
    'ref' scan ) multiplied by estimated number of rows from tables
    earlier in the join sequence.

    read_cost does NOT include cost of processing rows within the
    executor (row_evaluate_cost).
  */
  double read_cost;
  
  /**
    The fraction of the 'rows_fetched' rows that will pass the table
    conditions that were NOT used by the access method. If, e.g.,

      "SELECT ... WHERE t1.colx = 4 and t1.coly > 5"

    is resolved by ref access on t1.colx, filter_effect will be the
    fraction of rows that will pass the "t1.coly > 5" predicate. The
    valid range is 0..1, where 0.0 means that no rows will pass the
    table conditions and 1.0 means that all rows will pass.

    It is used to calculate how many row combinations will be joined
    with the next table, @see prefix_rowcount below.

    @Note that with condition filtering enabled, it is possible to get
    a fanout = rows_fetched * filter_effect that is less than 1.0.
    Consider, e.g., a join between t1 and t2:

       "SELECT ... WHERE t1.col1=t2.colx and t2.coly OP <something>"

    where t1 is a prefix table and the optimizer currently calculates
    the cost of adding t2 to the join. Assume that the chosen access
    method on t2 is a 'ref' access on 'colx' that is estimated to
    produce 2 rows per row from t1 (i.e., rows_fetched = 2). It will
    in this case be perfectly fine to calculate a filtering effect
    <0.5 (resulting in "rows_fetched * filter_effect < 1.0") from the
    predicate "t2.coly OP <something>". If so, the number of row
    combinations from (t1,t2) is lower than the prefix_rowcount of t1.

    The above is just an example of how the fanout of a table can
    become less than one. It can happen for any access method.
  */
  float filter_effect;

  /**
    prefix_rowcount and prefix_cost form a stack of partial join
    order costs and output sizes

    prefix_rowcount: The number of row combinations that will be
    joined to the next table in the join sequence.

    For a joined table it is calculated as
      prefix_rowcount =
          last_table.prefix_rowcount * rows_fetched * filter_effect

    @see filter_effect

    For a semijoined table it may be less than this formula due to
    duplicate elimination.
  */
  double prefix_rowcount;
  double prefix_cost;

  JOIN_TAB *table;

  /**
    NULL  -  'index' or 'range' or 'index_merge' or 'ALL' access is used.
    Other - [eq_]ref[_or_null] access is used. Pointer to {t.keypart1 = expr}
  */
  Key_use *key;

  /** If ref-based access is used: bitmap of tables this table depends on  */
  table_map ref_depend_map;
  bool use_join_buffer; 

  /**
    Current optimization state: Semi-join strategy to be used for this
    and preceding join tables.
    
    Join optimizer sets this for the *last* join_tab in the
    duplicate-generating range. That is, in order to interpret this field, 
    one needs to traverse join->[best_]positions array from right to left.
    When you see a join table with sj_strategy!= SJ_OPT_NONE, some other
    field (depending on the strategy) tells how many preceding positions 
    this applies to. The values of covered_preceding_positions->sj_strategy
    must be ignored.
  */
  uint sj_strategy;
  /**
    Valid only after fix_semijoin_strategies_for_picked_join_order() call:
    if sj_strategy!=SJ_OPT_NONE, this is the number of subsequent tables that
    are covered by the specified semi-join strategy
  */
  uint n_sj_tables;

  /**
    Bitmap of semi-join inner tables that are in the join prefix and for
    which there's no provision yet for how to eliminate semi-join duplicates
    which they produce.
  */
  table_map dups_producing_tables;

/* LooseScan strategy members */

  /* The first (i.e. driving) table we're doing loose scan for */
  uint        first_loosescan_table;
  /* 
     Tables that need to be in the prefix before we can calculate the cost
     of using LooseScan strategy.
  */
  table_map   loosescan_need_tables;

  /*
    keyno  -  Planning to do LooseScan on this key. If keyuse is NULL then 
              this is a full index scan, otherwise this is a ref+loosescan
              scan (and keyno matches the KEUSE's)
    MAX_KEY - Not doing a LooseScan
  */
  uint loosescan_key;  // final (one for strategy instance )
  uint loosescan_parts; /* Number of keyparts to be kept distinct */
  
/* FirstMatch strategy */
  /*
    Index of the first inner table that we intend to handle with this
    strategy
  */
  uint first_firstmatch_table;
  /*
    Tables that were not in the join prefix when we've started considering 
    FirstMatch strategy.
  */
  table_map first_firstmatch_rtbl;
  /* 
    Tables that need to be in the prefix before we can calculate the cost
    of using FirstMatch strategy.
   */
  table_map firstmatch_need_tables;

/* Duplicate Weedout strategy */
  /* The first table that the strategy will need to handle */
  uint  first_dupsweedout_table;
  /*
    Tables that we will need to have in the prefix to do the weedout step
    (all inner and all outer that the involved semi-joins are correlated with)
  */
  table_map dupsweedout_tables;

/* SJ-Materialization-Scan strategy */
  /* The last inner table (valid once we're after it) */
  uint      sjm_scan_last_inner;
  /*
    Tables that we need to have in the prefix to calculate the correct cost.
    Basically, we need all inner tables and outer tables mentioned in the
    semi-join's ON expression so we can correctly account for fanout.
  */
  table_map sjm_scan_need_tables;

  /**
     Even if the query has no semijoin, two sj-related members are read and
     must thus have been set, by this function.
  */
  void no_semijoin()
  {
    sj_strategy= SJ_OPT_NONE;
    dups_producing_tables= 0;
  }
  /**
    Set complete estimated cost and produced rowcount for the prefix of tables
    up to and including this table, in the join plan.

    @param cost     Estimated cost
    @param rowcount Estimated row count
  */
  void set_prefix_cost(double cost, double rowcount)
  {
    prefix_cost= cost;
    prefix_rowcount= rowcount;
  }
  /**
    Set complete estimated cost and produced rowcount for the prefix of tables
    up to and including this table, calculated from the cost of the previous
    stage, the fanout of the current stage and the cost to process a row at
    the current stage.

    @param idx      Index of position object within array, if zero there is no
                    "previous" stage that can be added.
    @param cm       Cost model that provides the actual calculation
  */
  void set_prefix_join_cost(uint idx, const Cost_model_server *cm)
  {
    if (idx == 0)
    {
      prefix_rowcount= rows_fetched;
      prefix_cost= read_cost + cm->row_evaluate_cost(prefix_rowcount);
    }
    else
    {
      prefix_rowcount= (this-1)->prefix_rowcount * rows_fetched;
      prefix_cost= (this-1)->prefix_cost + read_cost +
                   cm->row_evaluate_cost(prefix_rowcount);
    }
    prefix_rowcount*= filter_effect;
  }
} POSITION;

struct st_cache_field;
class QEP_operation;
class Filesort;


/**
  Query plan node.

  Specifies:

  - a table access operation on the table specified by this node, and

  - a join between the result of the set of previous plan nodes and
    this plan node.
*/
typedef struct st_join_table : public Sql_alloc
{
  st_join_table();

  table_map prefix_tables() const { return prefix_tables_map; }

  table_map added_tables() const { return added_tables_map; }

  /**
    Set available tables for a table in a join plan.

    @param prefix_tables: Set of tables available for this plan
    @param prev_tables: Set of tables available for previous table, used to
                        calculate set of tables added for this table.
  */
  void set_prefix_tables(table_map prefix_tables, table_map prev_tables)
  {
    prefix_tables_map= prefix_tables;
    added_tables_map= prefix_tables & ~prev_tables;
  }

  /**
    Add an available set of tables for a table in a join plan.

    @param tables: Set of tables added for this table in plan.
  */
  void add_prefix_tables(table_map tables)
  { prefix_tables_map|= tables; added_tables_map|= tables; }

  /// Sets the pointer to the join condition of TABLE_LIST
  void init_join_cond_ref(TABLE_LIST *tl)
  {
    m_join_cond_ref= tl->optim_join_cond_ref();
  }

  /// @returns join condition
  Item *join_cond() const
  {
    return *m_join_cond_ref;
  }

  /**
     Sets join condition
     @note this also changes TABLE_LIST::m_join_cond.
  */
  void set_join_cond(Item *cond)
  {
    *m_join_cond_ref= cond;
  }

  /// @returns the table condition for this table in the join order.
  Item *condition() const
  {
    return m_condition;
  }
  /// Set the combined condition for a table (may be performed several times)
  void set_condition(Item *to, uint line)
  {
    DBUG_PRINT("info", 
               ("JOIN_TAB::m_condition changes %p -> %p at line %u tab %p",
                m_condition, to, line, this));
    m_condition= to;
    quick_order_tested.clear_all();
  }

  /// Set table condition, for JOIN_TAB as well as for SELECT object
  Item *set_jt_and_sel_condition(Item *new_cond, uint line)
  {
    Item *tmp_cond= m_condition;
    set_condition(new_cond, line);
    if (select)
      select->cond= new_cond;
    return tmp_cond;
  }

  /// Return true if join_tab should perform a FirstMatch action
  bool do_firstmatch() const { return firstmatch_return; }

  /// Return true if join_tab should perform a LooseScan action
  bool do_loosescan() const { return loosescan_key_len; }

  /// Return true if join_tab starts a Duplicate Weedout action
  bool starts_weedout() const { return flush_weedout_table; }

  /// Return true if join_tab finishes a Duplicate Weedout action
  bool finishes_weedout() const { return check_weed_out_table; }

  TABLE         *table;
  POSITION      *position;      /**< points into best_positions array        */
  Key_use       *keyuse;        /**< pointer to first used key               */
  SQL_SELECT    *select;
  QUICK_SELECT_I *quick;
private:
  /**
    Table condition, ie condition to be evaluated for a row from this table.
    Notice that the condition may refer to rows from previous tables in the
    join prefix, as well as outer tables.
  */
  Item          *m_condition;
  /**
     Pointer to the associated join condition:
     - if this is a table with position==NULL (e.g. internal sort/group
     temporary table), pointer is NULL
     - otherwise, pointer is the address of some TABLE_LIST::m_join_cond.
     Thus, TABLE_LIST::m_join_cond and *JOIN_TAB::m_join_cond_ref are the same
     thing (changing one changes the other; thus, optimizations made on the
     second are reflected in SELECT_LEX::print_table_array() which uses the
     first).
  */
  Item          **m_join_cond_ref;
public:
  COND_EQUAL    *cond_equal;    /**< multiple equalities for the on expression*/
  st_join_table *first_inner;   /**< first inner table for including outerjoin*/
  bool           found;         /**< true after all matches or null complement*/
  bool           not_null_compl;/**< true before null complement is added    */
  /// For a materializable derived or SJ table: true if has been materialized
  bool           materialized;
  st_join_table *last_inner;    /**< last table table for embedding outer join*/
  st_join_table *first_upper;  /**< first inner table for embedding outer join*/
  st_join_table *first_unmatched; /**< used for optimization purposes only   */
  
  /* Special content for EXPLAIN 'Extra' column or NULL if none */
  Extra_tag     info;
  /* 
    Bitmap of TAB_INFO_* bits that encodes special line for EXPLAIN 'Extra'
    column, or 0 if there is no info.
  */
  uint          packed_info;

  READ_RECORD::Setup_func materialize_table;
  /**
     Initialize table for reading and fetch the first row from the table. If
     table is a materialized derived one, function must materialize it with
     prepare_scan().
  */
  READ_RECORD::Setup_func read_first_record;
  Next_select_func next_select;
  READ_RECORD	read_record;
  /* 
    The following two fields are used for a [NOT] IN subquery if it is
    executed by an alternative full table scan when the left operand of
    the subquery predicate is evaluated to NULL.
  */  
  READ_RECORD::Setup_func save_read_first_record;/* to save read_first_record */
  READ_RECORD::Read_func save_read_record;/* to save read_record.read_record */
  /**
    Struct needed for materialization of semi-join. Set for a materialized
    temporary table, and NULL for all other join_tabs (except when
    materialization is in progress, @see join_materialize_semijoin()).
  */
  Semijoin_mat_exec *sj_mat_exec;          
  double	worst_seeks;
  /** Keys with constant part. Subset of keys. */
  key_map	const_keys;
  key_map	checked_keys;			/**< Keys checked */
  key_map	needed_reg;
  key_map       keys;                           /**< all keys with can be used */
  /**
    Used to avoid repeated range analysis for the same key in
    test_if_skip_sort_order(). This would otherwise happen if the best
    range access plan found for a key is turned down.
    quick_order_tested is cleared every time the select condition for
    this JOIN_TAB changes since a new condition may give another plan
    and cost from range analysis.
   */
  key_map       quick_order_tested;

  /* Either #rows in the table or 1 for const table.  */
  ha_rows	records;
  /*
    Number of records that will be scanned (yes scanned, not returned) by the
    best 'independent' access method, i.e. table scan or QUICK_*_SELECT)
  */
  ha_rows       found_records;
  /*
    Cost of accessing the table using "ALL" or range/index_merge access
    method (but not 'index' for some reason), i.e. this matches method which
    E(#records) is in found_records.
  */
  ha_rows       read_time;
  /**
    The set of tables that this table depends on. Used for outer join and
    straight join dependencies.
  */
  table_map     dependent;
  /**
    The set of tables that are referenced by key from this table.
  */
  table_map     key_dependent;
private:
  /**
    The set of all tables available in the join prefix for this table,
    including the table handled by this JOIN_TAB.
  */
  table_map     prefix_tables_map;
  /**
    The set of tables added for this table, compared to the previous table
    in the join prefix.
  */
  table_map     added_tables_map;
public:
  /// ID of index used for index scan or semijoin LooseScan
  uint		index;
  uint		used_fields,used_fieldlength,used_blobs;
  uint          used_null_fields;
  uint          used_rowid_fields;
  uint          used_uneven_bit_fields;
  enum quick_type use_quick;
  enum join_type type;
  bool          not_used_in_distinct;
  /**
     Estimated number of rows read from the table per nested-loop iteration.
  */
  ha_rows       rowcount;
  TABLE_REF	ref;
  /**
    Join buffering strategy.
    After optimization it contains chosen join buffering strategy (if any).
   */
  uint          use_join_cache;
  QEP_operation *op;
  /*
    Index condition for BKA access join
  */
  Item          *cache_idx_cond;
  SQL_SELECT    *cache_select;
  JOIN		*join;

  /* SemiJoinDuplicateElimination variables: */
  /*
    Embedding SJ-nest (may be not the direct parent), or NULL if none.
    This variable holds the result of table pullout.
  */
  TABLE_LIST    *emb_sj_nest;

  /**
    Boundaries of semijoin inner tables around this table. Valid only once
    final QEP has been chosen. Depending on the strategy, they may define an
    interval (all tables inside are inner of a semijoin) or
    not. last_sj_inner_tab is not set for Duplicates Weedout.
  */
  struct st_join_table *first_sj_inner_tab;
  struct st_join_table *last_sj_inner_tab;

  /* Variables for semi-join duplicate elimination */
  SJ_TMP_TABLE  *flush_weedout_table;
  SJ_TMP_TABLE  *check_weed_out_table;
  
  /*
    If set, means we should stop join enumeration after we've got the first
    match and return to the specified join tab. May point to
    join->join_tab[-1] which means stop join execution after the first
    match.
  */
  struct st_join_table  *firstmatch_return;
 
  /*
    Length of key tuple (depends on #keyparts used) to store in loosescan_buf.
    If zero, means that loosescan is not used.
  */
  uint loosescan_key_len;

  /* Buffer to save index tuple to be able to skip duplicates */
  uchar *loosescan_buf;

  /* 
    If doing a LooseScan, this join tab is the first (i.e.  "driving") join
    tab, and match_tab points to the last join tab handled by the strategy.
    match_tab->found_match should be checked to see if the current value group
    had a match.
    If doing a FirstMatch, check this join tab to see if there is a match.
    Unless the FirstMatch performs a "split jump", this is equal to the
    current join_tab.
  */
  struct st_join_table *match_tab;
  /*
    Used by FirstMatch and LooseScan. TRUE <=> there is a matching
    record combination
  */
  bool found_match;
  
  /*
    Used by DuplicateElimination. tab->table->ref must have the rowid
    whenever we have a current record. copy_current_rowid needed because
    we cannot bind to the rowid buffer before the table has been opened.
  */
  int  keep_current_rowid;
  st_cache_field *copy_current_rowid;

  /* NestedOuterJoins: Bitmap of nested joins this table is part of */
  nested_join_map embedding_map;

  /* Tmp table info */
  Temp_table_param *tmp_table_param;

  /* Sorting related info */
  Filesort *filesort;

  /**
    List of topmost expressions in the select list. The *next* JOIN TAB
    in the plan should use it to obtain correct values. Same applicable to
    all_fields. These lists are needed because after tmp tables functions
    will be turned to fields. These variables are pointing to
    tmp_fields_list[123]. Valid only for tmp tables and the last non-tmp
    table in the query plan.
    @see JOIN::make_tmp_tables_info()
  */
  List<Item> *fields;
  /** List of all expressions in the select list */
  List<Item> *all_fields;
  /*
    Pointer to the ref array slice which to switch to before sending
    records. Valid only for tmp tables.
  */
  Ref_ptr_array *ref_array;

  /** Number of records saved in tmp table */
  ha_rows send_records;

  /** HAVING condition for checking prior saving a record into tmp table*/
  Item *having;

  /** TRUE <=> remove duplicates on this table. */
  bool distinct;

  /** TRUE <=> only index is going to be read for this table */
  bool use_keyread;

  /** Flags from SE's MRR implementation, to be used by JOIN_CACHE */
  uint join_cache_flags;

  /** TRUE <=> AM will scan backward */
  bool reversed_access;

  /** FT function */
  Item_func_match *ft_func;

  /** Clean up associated table after query execution, including resources */
  void cleanup();

  bool is_using_loose_index_scan() const
  {
    /*
      If JOIN_TAB::filesort is set, then the access method defined in
      filesort will be used to read from the table and
      JOIN_TAB::select reads from filesort using scan or ref access.
    */
    DBUG_ASSERT(!(select && select->quick && filesort));

    const SQL_SELECT *sel= filesort ? filesort->select : select;
    return (sel && sel->quick &&
            (sel->quick->get_type() == QUICK_SELECT_I::QS_TYPE_GROUP_MIN_MAX));
  }
  bool is_using_agg_loose_index_scan() const
  {
    /*
      If JOIN_TAB::filesort is set, then the access method defined in
      filesort will be used to read from the table and
      JOIN_TAB::select reads from filesort using scan or ref access.
    */
    DBUG_ASSERT(!(select && select->quick && filesort));

    const SQL_SELECT *sel= filesort ? filesort->select : select;
    return (sel && sel->quick &&
            (sel->quick->get_type() ==
             QUICK_SELECT_I::QS_TYPE_GROUP_MIN_MAX) &&
            static_cast<QUICK_GROUP_MIN_MAX_SELECT*>(sel->quick)->
                                                     is_agg_distinct());
  }
  /* SemiJoinDuplicateElimination: reserve space for rowid */
  bool check_rowid_field()
  {
    if (keep_current_rowid && !used_rowid_fields)
    {
      used_rowid_fields= 1;
      used_fieldlength+= table->file->ref_length;
    }
    return MY_TEST(used_rowid_fields);
  }
  bool is_inner_table_of_outer_join() const
  {
    return first_inner != NULL;
  }
  bool is_single_inner_of_semi_join() const
  {
    return first_sj_inner_tab == this && last_sj_inner_tab == this;
  }
  bool is_single_inner_of_outer_join() const
  {
    return first_inner == this && first_inner->last_inner == this;
  }
  bool is_first_inner_for_outer_join() const
  {
    return first_inner && first_inner == this;
  }

  /// @returns semijoin strategy for this table.
  uint get_sj_strategy() const
  {
    if (first_sj_inner_tab == NULL)
      return SJ_OPT_NONE;
    DBUG_ASSERT(first_sj_inner_tab->position->sj_strategy != SJ_OPT_NONE);
    return first_sj_inner_tab->position->sj_strategy;
  }
  /**
     @returns query block id for an inner table of materialized semi-join, and
              0 for all other tables.
  */
  uint sjm_query_block_id() const;

  bool and_with_condition(Item *tmp_cond, uint line);
  bool and_with_jt_and_sel_condition(Item *tmp_cond, uint line);

  /**
    Check if there are triggered/guarded conditions that might be
    'switched off' by the subquery code when executing 'Full scan on
    NULL key' subqueries.

    @return true if there are guarded conditions, false otherwise
  */

  bool has_guarded_conds() const
  {
    return ref.has_guarded_conds();
  }
  Item *unified_condition() const;
  bool prepare_scan();
  bool use_order() const; ///< Use ordering provided by chosen index?
  bool sort_table();
  bool remove_duplicates();
  /**
    A helper function that allocates appropriate join cache object and
    sets next_select function of previous tab.
  */
  void init_join_cache();
} JOIN_TAB;

inline
st_join_table::st_join_table()
  : table(NULL),
    position(NULL),
    keyuse(NULL),
    select(NULL),
    quick(NULL),
    m_condition(NULL),
    m_join_cond_ref(NULL),
    cond_equal(NULL),
    first_inner(NULL),
    found(false),
    not_null_compl(false),
    materialized(false),
    last_inner(NULL),
    first_upper(NULL),
    first_unmatched(NULL),
    info(ET_none),
    packed_info(0),
    materialize_table(NULL),
    read_first_record(NULL),
    next_select(NULL),
    read_record(),
    save_read_first_record(NULL),
    save_read_record(NULL),
    sj_mat_exec(NULL),
    worst_seeks(0.0),
    const_keys(),
    checked_keys(),
    needed_reg(),
    keys(),
    quick_order_tested(),

    records(0),
    found_records(0),
    read_time(0),

    dependent(0),
    key_dependent(0),
    prefix_tables_map(0),
    added_tables_map(0),
    index(0),
    used_fields(0),
    used_fieldlength(0),
    used_blobs(0),
    used_null_fields(0),
    used_rowid_fields(0),
    used_uneven_bit_fields(0),
    use_quick(QS_NONE),
    type(JT_UNKNOWN),
    not_used_in_distinct(false),

    rowcount(0),
    ref(),
    use_join_cache(0),
    op(NULL),

    cache_idx_cond(NULL),
    cache_select(NULL),
    join(NULL),

    emb_sj_nest(NULL),
    first_sj_inner_tab(NULL),
    last_sj_inner_tab(NULL),

    flush_weedout_table(NULL),
    check_weed_out_table(NULL),
    firstmatch_return(NULL),
    loosescan_key_len(0),
    loosescan_buf(NULL),
    match_tab(NULL),
    found_match(FALSE),

    keep_current_rowid(0),
    copy_current_rowid(NULL),
    embedding_map(0),
    tmp_table_param(NULL),
    filesort(NULL),
    fields(NULL),
    all_fields(NULL),
    ref_array(NULL),
    send_records(0),
    having(NULL),
    distinct(false),
    use_keyread(false),
    join_cache_flags(0),
    reversed_access(false),
    ft_func(NULL)
{
  /**
    @todo Add constructor to READ_RECORD.
    All users do init_read_record(), which does memset(),
    rather than invoking a constructor.
  */
  memset(&read_record, 0, sizeof(read_record));
}

/**
  "Less than" comparison function object used to compare two JOIN_TAB
  objects based on a number of factors in this order:

   - table before another table that depends on it (straight join, 
     outer join etc), then
   - table before another table that depends on it to use a key
     as access method, then
   - table with smallest number of records first, then
   - the table with lowest-value pointer (i.e., the one located 
     in the lowest memory address) first.

  @param jt1  first JOIN_TAB object
  @param jt2  second JOIN_TAB object

  @note The order relation implemented by Join_tab_compare_default is not
    transitive, i.e. it is possible to choose a, b and c such that 
    (a < b) && (b < c) but (c < a). This is the case in the
    following example: 

      a: dependent = <none>   found_records = 3
      b: dependent = <none>   found_records = 4
      c: dependent = b        found_records = 2

        a < b: because a has fewer records
        b < c: because c depends on b (e.g outer join dependency)
        c < a: because c has fewer records

    This implies that the result of a sort using the relation
    implemented by Join_tab_compare_default () depends on the order in
    which elements are compared, i.e. the result is
    implementation-specific.

  @return
    true if jt1 is smaller than jt2, false otherwise
*/
class Join_tab_compare_default :
  public std::binary_function<const JOIN_TAB*, const JOIN_TAB*, bool>
{
public:
  bool operator()(const JOIN_TAB *jt1, const JOIN_TAB *jt2)
  {
    // Sorting distinct tables, so a table should not be compared with itself
    DBUG_ASSERT(jt1 != jt2);

    if (jt1->dependent & jt2->table->map)
      return false;
    if (jt2->dependent & jt1->table->map)
      return true;

    const bool jt1_keydep_jt2= jt1->key_dependent & jt2->table->map;
    const bool jt2_keydep_jt1= jt2->key_dependent & jt1->table->map;

    if (jt1_keydep_jt2 && !jt2_keydep_jt1)
      return false;
    if (jt2_keydep_jt1 && !jt1_keydep_jt2)
      return true;

    if (jt1->found_records > jt2->found_records)
      return false;
    if (jt1->found_records < jt2->found_records)
      return true;

    return jt1 < jt2;
  }
};

/**
  "Less than" comparison function object used to compare two JOIN_TAB
  objects that are joined using STRAIGHT JOIN. For STRAIGHT JOINs, 
  the join order is dictated by the relative order of the tables in the
  query which is reflected in JOIN_TAB::dependent. Table size and key
  dependencies are ignored here.
*/
class Join_tab_compare_straight :
  public std::binary_function<const JOIN_TAB*, const JOIN_TAB*, bool>
{
public:
  bool operator()(const JOIN_TAB *jt1, const JOIN_TAB *jt2)
  {
    // Sorting distinct tables, so a table should not be compared with itself
    DBUG_ASSERT(jt1 != jt2);

    /*
      We don't do subquery flattening if the parent or child select has
      STRAIGHT_JOIN modifier. It is complicated to implement and the semantics
      is hardly useful.
    */
    DBUG_ASSERT(!jt1->emb_sj_nest);
    DBUG_ASSERT(!jt2->emb_sj_nest);

    if (jt1->dependent & jt2->table->map)
      return false;
    if (jt2->dependent & jt1->table->map)
      return true;

    return jt1 < jt2;
  }
};

/*
  Same as Join_tab_compare_default but tables from within the given
  semi-join nest go first. Used when optimizing semi-join
  materialization nests.
*/
class Join_tab_compare_embedded_first :
  public std::binary_function<const JOIN_TAB*, const JOIN_TAB*, bool>
{
private:
  const TABLE_LIST *emb_nest;
public:
  
  Join_tab_compare_embedded_first(const TABLE_LIST *nest) : emb_nest(nest){}

  bool operator()(const JOIN_TAB *jt1, const JOIN_TAB *jt2)
  {
    // Sorting distinct tables, so a table should not be compared with itself
    DBUG_ASSERT(jt1 != jt2);

    if (jt1->emb_sj_nest == emb_nest && jt2->emb_sj_nest != emb_nest)
      return true;
    if (jt1->emb_sj_nest != emb_nest && jt2->emb_sj_nest == emb_nest)
      return false;

    Join_tab_compare_default cmp;
    return cmp(jt1,jt2);
  }
};


typedef Bounds_checked_array<Item_null_result*> Item_null_array;

typedef struct st_select_check {
  uint const_ref,reg_ref;
} SELECT_CHECK;

/* Extern functions in sql_select.cc */
void count_field_types(SELECT_LEX *select_lex, Temp_table_param *param, 
                       List<Item> &fields, bool reset_with_sum_func,
                       bool save_sum_fields);
uint find_shortest_key(TABLE *table, const key_map *usable_keys);

/* functions from opt_sum.cc */
bool simple_pred(Item_func *func_item, Item **args, bool *inv_order);
int opt_sum_query(THD* thd,
                  TABLE_LIST *tables, List<Item> &all_fields, Item *conds);

/* from sql_delete.cc, used by opt_range.cc */
extern "C" int refpos_order_cmp(const void* arg, const void *a,const void *b);

/** class to copying an field/item to a key struct */

class store_key :public Sql_alloc
{
public:
  bool null_key; /* TRUE <=> the value of the key has a null part */
  enum store_key_result { STORE_KEY_OK, STORE_KEY_FATAL, STORE_KEY_CONV };
  store_key(THD *thd, Field *field_arg, uchar *ptr, uchar *null, uint length)
    :null_key(0), null_ptr(null), err(0)
  {
    if (field_arg->type() == MYSQL_TYPE_BLOB
        || field_arg->type() == MYSQL_TYPE_GEOMETRY)
    {
      /* 
        Key segments are always packed with a 2 byte length prefix.
        See mi_rkey for details.
      */
      to_field= new Field_varstring(ptr, length, 2, null, 1, 
                                    Field::NONE, field_arg->field_name,
                                    field_arg->table->s, field_arg->charset());
      to_field->init(field_arg->table);
    }
    else
      to_field=field_arg->new_key_field(thd->mem_root, field_arg->table,
                                        ptr, null, 1);
  }
  virtual ~store_key() {}			/** Not actually needed */
  virtual const char *name() const=0;

  /**
    @brief sets ignore truncation warnings mode and calls the real copy method

    @details this function makes sure truncation warnings when preparing the
    key buffers don't end up as errors (because of an enclosing INSERT/UPDATE).
  */
  enum store_key_result copy()
  {
    enum store_key_result result;
    THD *thd= to_field->table->in_use;
    enum_check_fields saved_count_cuted_fields= thd->count_cuted_fields;
    sql_mode_t sql_mode= thd->variables.sql_mode;
    thd->variables.sql_mode&= ~(MODE_STRICT_ALL_TABLES |
                                MODE_STRICT_TRANS_TABLES);

    thd->count_cuted_fields= CHECK_FIELD_IGNORE;

    result= copy_inner();

    thd->count_cuted_fields= saved_count_cuted_fields;
    thd->variables.sql_mode= sql_mode;

    return result;
  }

 protected:
  Field *to_field;				// Store data here
  uchar *null_ptr;
  uchar err;

  virtual enum store_key_result copy_inner()=0;
};


static store_key::store_key_result
type_conversion_status_to_store_key (type_conversion_status ts)
{
  switch (ts)
  {
  case TYPE_OK:
    return store_key::STORE_KEY_OK;
  case TYPE_NOTE_TRUNCATED:
  case TYPE_WARN_TRUNCATED:
  case TYPE_NOTE_TIME_TRUNCATED:
    return store_key::STORE_KEY_CONV;
  case TYPE_WARN_OUT_OF_RANGE:
  case TYPE_ERR_NULL_CONSTRAINT_VIOLATION:
  case TYPE_ERR_BAD_VALUE:
  case TYPE_ERR_OOM:
    return store_key::STORE_KEY_FATAL;
  default:
    DBUG_ASSERT(false); // not possible
  }

  return store_key::STORE_KEY_FATAL;
}

class store_key_field: public store_key
{
  Copy_field copy_field;
  const char *field_name;
 public:
  store_key_field(THD *thd, Field *to_field_arg, uchar *ptr,
                  uchar *null_ptr_arg,
		  uint length, Field *from_field, const char *name_arg)
    :store_key(thd, to_field_arg,ptr,
	       null_ptr_arg ? null_ptr_arg : from_field->maybe_null() ? &err
	       : (uchar*) 0, length), field_name(name_arg)
  {
    if (to_field)
    {
      copy_field.set(to_field,from_field,0);
    }
  }
  const char *name() const { return field_name; }

 protected: 
  enum store_key_result copy_inner()
  {
    TABLE *table= copy_field.to_field()->table;
    my_bitmap_map *old_map= dbug_tmp_use_all_columns(table,
                                                     table->write_set);
    copy_field.invoke_do_copy(&copy_field);
    dbug_tmp_restore_column_map(table->write_set, old_map);
    null_key= to_field->is_null();
    return err != 0 ? STORE_KEY_FATAL : STORE_KEY_OK;
  }
};


class store_key_item :public store_key
{
 protected:
  Item *item;
public:
  store_key_item(THD *thd, Field *to_field_arg, uchar *ptr,
                 uchar *null_ptr_arg, uint length, Item *item_arg)
    :store_key(thd, to_field_arg, ptr,
	       null_ptr_arg ? null_ptr_arg : item_arg->maybe_null ?
	       &err : (uchar*) 0, length), item(item_arg)
  {}
  const char *name() const { return "func"; }

 protected:  
  enum store_key_result copy_inner()
  {
    TABLE *table= to_field->table;
    my_bitmap_map *old_map= dbug_tmp_use_all_columns(table,
                                                     table->write_set);
    type_conversion_status save_res= item->save_in_field(to_field, true);
    store_key_result res;
    /*
     Item::save_in_field() may call Item::val_xxx(). And if this is a subquery
     we need to check for errors executing it and react accordingly
    */
    if (save_res != TYPE_OK && table->in_use->is_error())
      res= STORE_KEY_FATAL;
    else
      res= type_conversion_status_to_store_key(save_res);
    dbug_tmp_restore_column_map(table->write_set, old_map);
    null_key= to_field->is_null() || item->null_value;
    return (err != 0) ? STORE_KEY_FATAL : res;
  }
};


class store_key_const_item :public store_key_item
{
  bool inited;
public:
  store_key_const_item(THD *thd, Field *to_field_arg, uchar *ptr,
		       uchar *null_ptr_arg, uint length,
		       Item *item_arg)
    :store_key_item(thd, to_field_arg, ptr,
                    null_ptr_arg, length, item_arg), inited(0)
  {
  }
  static const char static_name[]; ///< used out of this class
  const char *name() const { return static_name; }

protected:  
  enum store_key_result copy_inner()
  {
    if (!inited)
    {
      inited=1;
      store_key_result res= store_key_item::copy_inner();
      if (res && !err)
        err= res;
    }
    return (err > 2 ? STORE_KEY_FATAL : (store_key_result) err);
  }
};

bool error_if_full_join(JOIN *join);
bool handle_select(THD *thd, select_result *result,
                   ulong setup_tables_done_option);
bool mysql_prepare_and_optimize_select(THD *thd,
                  List<Item> &list,
                  ulonglong select_type,
                  select_result *result,
                  SELECT_LEX *select_lex, bool *free_join);
bool mysql_select(THD *thd,
                  List<Item> &list,
                  ulonglong select_type,
                  select_result *result,
                  SELECT_LEX *select_lex);
void free_underlaid_joins(THD *thd, SELECT_LEX *select);


void calc_used_field_length(THD *thd, JOIN_TAB *join_tab);

inline bool optimizer_flag(THD *thd, uint flag)
{ 
  return (thd->variables.optimizer_switch & flag);
}

uint get_index_for_order(ORDER *order, TABLE *table, SQL_SELECT *select,
                         ha_rows limit, bool *need_sort, bool *reverse);
ORDER *simple_remove_const(ORDER *order, Item *where);
bool const_expression_in_where(Item *cond, Item *comp_item,
                               Field *comp_field= NULL,
                               Item **const_item= NULL);
bool test_if_subpart(ORDER *a,ORDER *b);
void calc_group_buffer(JOIN *join,ORDER *group);
bool make_join_readinfo(JOIN *join, ulonglong options, uint no_jbuf_after);
bool create_ref_for_key(JOIN *join, JOIN_TAB *j, Key_use *org_keyuse,
                        table_map used_tables);
bool types_allow_materialization(Item *outer, Item *inner);
bool and_conditions(Item **e1, Item *e2);

static inline Item * and_items(Item* cond, Item *item)
{
  return (cond? (new Item_cond_and(cond, item)) : item);
}

uint actual_key_parts(const KEY *key_info);
uint actual_key_flags(KEY *key_info);

int test_if_order_by_key(ORDER *order, TABLE *table, uint idx,
                         uint *used_key_parts= NULL);
bool test_if_cheaper_ordering(const JOIN_TAB *tab,
                              ORDER *order, TABLE *table,
                              key_map usable_keys, int key,
                              ha_rows select_limit,
                              int *new_key, int *new_key_direction,
                              ha_rows *new_select_limit,
                              uint *new_used_key_parts= NULL,
                              uint *saved_best_key_parts= NULL);
/**
  Calculate properties of ref key: key length, number of used key parts,
  dependency map, possibility of null.

  @param keyuse               Array of keys to consider
  @param tab                  join_tab to calculate ref parameters for
  @param key                  number of the key to use
  @param used_tables          tables read prior to this table
  @param [out] chosen_keyuses when given, this function will fill array with
                              chosen keyuses
  @param [out] length_out     calculated length of the ref
  @param [out] keyparts_out   calculated number of used keyparts
  @param [out] dep_map        when given, calculated dependency map
  @param [out] maybe_null     when given, calculated maybe_null property
*/

void calc_length_and_keyparts(Key_use *keyuse, JOIN_TAB *tab, const uint key,
                              table_map used_tables,Key_use **chosen_keyuses,
                              uint *length_out, uint *keyparts_out,
                              table_map *dep_map, bool *maybe_null);

#endif /* SQL_SELECT_INCLUDED */