WL#9167: Index merge hints

MySQL has possibility to control use of index merge using
optimizer_switch(index_merge, index_merge_intersection, index_merge_sort_union,
index_merge_union). It would be more convenient allow the user to control index
merge behavior for the particular query without changing the optimizer switch.
New hints INDEX_MERGE, NO_INDEX_MERGE will  be added for this purpose.

Functional requirements:

F-1: Hints must be enclosed into /*+ */ comment.

F-2: Hints must be specified after SELECT|INSERT|REPLACE|UPDATE|DELETE key words.

F-3: EXPLAIN must understand hints.

F-4: Active hints must be printed in EXPLAIN warning.

F-5: Subsequent conflicting/duplicating hints are ignored with warning.

F-6: Unresolved hints cause warning.

Non-Functional requirements:

NONE

1. INDEX_MERGE

   Specification:

   INDEX_MERGE([@QB_NAME] table [index[, index]...])
   or 
   INDEX_MERGE(table@QB_NAME [index[, index]...])


   The hint forces the optimizer to use index merge for the specified
   table using the specified set of indexes. If no index is specified,
   all possible index combinations are considered by the optimizer and
   cheapest one is selected.  Note that the hint may be ignored if the
   index combination is not applicable to the given query.

   Some examples:

   t1(a, b, c, d, key(a), key(b), key(c)) and query
   
   SELECT /*+ INDEX_MERGE(t1 a, b, c)*/ * FROM t1
   WHERE b = 1 AND c = 2 AND d = 3;
   Index merge (b,c) will be used in this case.

   SET optimizer_switch='index_merge_intersection=off';
   SELECT /*+ INDEX_MERGE(t1 b, c) */ * FROM t1
   WHERE b = 1 AND c = 2 AND d = 3;
   Index merge (b,c) will be used in this case.

   SET optimizer_switch='index_merge_intersection=off';
   SELECT /*+ INDEX_MERGE(t1 b) */ * FROM t1
   WHERE b = 1 AND c = 2 AND d = 3;
   No index merge will be used since only one key is specified.

   SET optimizer_switch='index_merge_intersection=on';
   SELECT /*+ INDEX_MERGE(t1 b) */ * FROM t1
   WHERE b = 1 AND c = 2 AND d = 3;
   No index merge will be used since only one key is specified
   
2. NO_INDEX_MERGE

   Specification:

   NO_INDEX_MERGE([@QB_NAME] table [index[, index]...])
   or 
   NO_INDEX_MERGE(table@QB_NAME [index[, index]...])

   The hint disables index merge combinations that involve any of the
   specified indexes. If no index is specified, index merge is not
   allowed for the table.

Resolving conflicting hints.

First specified hint is applied and next conflicting hints are ignored with
warning. If it's impossible to apply a valid hint, it is silently ignored
without any warning. Note that if INDEX_MERGE and NO_INDEX_MERGE are used
at the same time, second specified hints is treated as conflicting and
ignored with warning. For example,

/*+ INDEX_MERGE(t1 idx1, idx2) NO_INDEX_MERGE(t1 idx1) */

 INDEX_MERGE(t1 idx1, idx2) is applicable and NO_INDEX_MERGE is ignored.

/*+ INDEX_MERGE(t1 idx1, idx2) NO_INDEX_MERGE(t1 idx2) */

 NO_INDEX_MERGE is ignored because there is a preceding hint for
 the same table.

/*+ NO_INDEX_MERGE(t1 idx1, idx2) INDEX_MERGE(t1 idx2) */

 INDEX_MERGE is ignored because there is a preceding hint for
 the same table.

Interaction with optimizer switch.

Hint has as higher priority, i.e. if optimizer_switch is OFF and
hint is specified then the hint is applicable. 

Interaction with old style hints USE|FORCE|IGNORE INDEX.

Old hints have higher priority towards to new style hints.


Examples:

  /*+ INDEX_MERGE(t1 idx1, idx2, idx3) */ ... IGNORE INDEX idx1

There is conflict between old and new style hints. In this case
index 'idx1' will be excluded from the possible ranges for index
merge/

  /*+ NO_INDEX_MERGE(t1 idx1, idx2) */ ... FORCE INDEX idx1, idx2

Index merge is disallowed for idx1, idx2 but optimizer is forced to
use either idx1 or idx2 for range or ref access. Here is no conflicts,
both hint are applicable.

If IGNORE INDEX hint contains multiple indexes,
indexes specified in the old hint are unavailable for index merge.

FORCE/USE INDEX hints make only specified indexes to be available for
index merge.

Examples:

EXPLAIN SELECT /*+ INDEX_MERGE(t1 f2, f3, f4) */ f2 FROM t1
FORCE INDEX (f2, f3) WHERE f4 = 'h' AND f2 = 2 AND f3 = 'b';

Index merge intersection(f2, f3) will be used.

EXPLAIN SELECT /*+ INDEX_MERGE(t1 f2, f3, f4) */ f2 FROM t1
USE INDEX (f2, f3) WHERE f4 = 'h' AND f2 = 2 AND f3 = 'b';

Index merge intersection(f2, f3) will be used.

Hint infrastructure changes:

1. Added complex [NO_]INDEX_MERGE hint.

struct st_opt_hint_info opt_hint_info[]=
{
  ...
  {"INDEX_MERGE", false, false},
}


2. Added auxiliary class for complex key objects.
Object of this class has information about
PT_key_level_hint object, resolved state and
specified keys if they exist. If there is no key
specified, key_map is empty and information about
hint state is obtained from PT_key_level_hint object.

class Compound_key_hint
{
  PT_key_level_hint *pt_hint;
  Key_map key_map;
  bool resolved;

public:

  Compound_key_hint()
  {
    key_map.init();
    resolved= false;
    pt_hint= NULL;
  }

  void set_pt_hint( PT_key_level_hint *pt_hint_arg) { pt_hint= pt_hint_arg; }
  PT_key_level_hint *get_pt_hint() { return pt_hint; }

  void set_resolved(bool arg) { resolved= arg; }
  bool is_resolved() { return resolved; }

  void set_key_map(uint i) { key_map.set_bit(i); }
  bool is_set_key_map(uint i) { return key_map.is_set(i); }
  bool is_key_map_clear_all() { return key_map.is_clear_all(); }
};

3. Added some service functions:

virtual void Opt_hints::set_resolved_ext() { set_resolved(); }
virtual bool Opt_hints::is_resolved_by_type(opt_hints_enum type_arg)
{ return resolved; }
virtual void Opt_hints::set_unresolved(opt_hints_enum type_arg) {}
virtual bool Opt_hints::ignore_print(opt_hints_enum type_arg) const
{ return false; }

4. Added new function:

/**
  Returns true if index merge hint state is on with or without
  specified keys, otherwise returns false.

  @param thd                Pointer to THD object
  @param table              Pointer to TABLE object
  @param keyno              Key number

  @return true if index merge hint state is on with or without
          specified keys, otherwise retruns false.
*/
bool idx_merge_key_enabled(const THD *thd, const TABLE *table, uint keyno);


Changes in opt_range.cc:

There are three index merge types:
Index merge intersection.
Index merge union.
Index merge sort union.

Decision about the use of index merge intersection is taken
in get_best_ror_intersect() based on suitable keys and cost.
Suitable keys are filtered using key map specified in INDEX_MERGE
hint. If no keys specified, filtering is processed based on
INDEX_MERGE hint state(NO_INDEX_MERGE means no suitable keys,
for INDEX_MERGE all suitable are involved into processing).
Cost check is ignored only if INDEX_MERGE hint is used(to force
index merge use). If NO_INDEX_MERGE is specified, cost check is not
ignored.

Decision about the use of index merge union & sort union is taken
in get_best_disjunct_quick() function. The same(as for intersect)
logic is used.

class TABLE_READ_PLAN, added new field:

  /**
    TRUE if creation of the object is forced by hint, FALSE otherwise.
  */
  bool forced_by_hint;

Added initialization of this field in constructor.

class QUICK_SELECT_I, added new field:

  /**
    TRUE if creation of the object is forced by hint, FALSE otherwise.
  */
  bool forced_by_hint;

Added initialization of this field in appropriate 
TRP_...::make_quick() functions.

Changes in sql_planner.cc:

Added code which ignores best_ref if quick object is forced by hint.