WL#13538: Add index hints based on new hint infrastructure

Affects: Server-8.0 — Status: Complete

Description
Requirements
High Level Architecture
Low Level Design

Index hints give the optimizer information about how to
choose indexes during query processing. Currently MySQL
supports USE/IGNORE/FORCE hints
(see https://dev.mysql.com/doc/refman/8.0/en/index-hints.html for more details).

The goal of this task is to replace these hints with
the hints based on new hint infrastructure
(see https://dev.mysql.com/doc/refman/8.0/en/optimizer-hints.html and
 WL#8017 for more details).

Related bugs:

BUG#89805 OPTIONALLY AVOID HARD ERRORS ON IGNORE INDEX OR FORCE INDEX USAGE.
BUG#87670 FORCE INDEX FOR GROUP BY IS NOT ALWAYS HONORED.

Functional requirements:

F-1: New index hints should provide the same functionality as the old index hints.

F-2: New index hints should be allowed to be used in views.

F-3: New index hints should be allowed to be used for UPDATE/DELETE commands.

F-4: If both old and new hints are present, new hints override the old hints.

F-5: There is no direct replacement for USE INDEX in the new hints. The same
     functionality can be obtained using NO_[JOIN|GROUP|ORDER_]INDEX hints.

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

F-7: Hints must follow SELECT|INSERT|REPLACE|UPDATE|DELETE key words
     in a query specification.

F-8: EXPLAIN must understand hints.

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

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

F-11: Unresolved hints cause warning.

1. Some key points regarding currently used index hints.
(see https://dev.mysql.com/doc/refman/8.0/en/index-hints.html)

1.1 There are three index hints: USE INDEX, FORCE INDEX, IGNORE INDEX.

USE INDEX(index_list) tells MySQL to use only one of the
named indexes to find rows in the table.

FORCE INDEX (index_list) hint acts like USE INDEX (index_list),
with the addition that a table scan is assumed to be very expensive.
In other words, a table scan is used only if there is no way to use
one of the named indexes to find rows in the table.

IGNORE INDEX (index_list) tells MySQL to not use some particular index or indexes.

1.2 It's possible to specify the scope of an index hint
(FOR JOIN, FOR GROUP BY, FOR ORDER BY) by adding a FOR clause to the hint.

FOR JOIN modifier tells MySQL to use/not use specified indexes
for various access methods(ref, range etc).

FOR GROUP BY modifier tells MySQL to use/not use specified indexes
for index scan for GROUP BY operation.

FOR ORDER BY modifier tells MySQL to use/not use specified indexes
for sorting rows.

If scope is not specified, the index specified in the index_list applies to the 
entire table (i.e can be used for JOIN, GROUP BY and ORDER BY in case of USE 
INDEX/FORCE INDEX and cannot be used for JOIN,GROUP BY and ORDER BY in case of 
IGNORE INDEX).

1.3 USE INDEX and FORCE INDEX cannot be used at the same time.
USE INDEX|FORCE INDEX and IGNORE INDEX can be used.

1.4 It is syntactically valid to omit index_list for USE INDEX,
which means “use no indexes.”
Omitting index_list for FORCE INDEX or IGNORE INDEX is a syntax error.

1.5 Interaction with index-level optimizer hints.
Index hints have a higher priority than index-level optimizer hints.
Index hints apply first and new index-level optimizer hints work with
the set of indexes limited by index hints.

Example:
---
# Index merge i_a, i_b, i_c is used.
EXPLAIN SELECT /*+ INDEX_MERGE(t1 i_a, i_b, i_c) */ a FROM t1 WHERE a = 1 AND b = 2 AND c = 3;
id	select_type	table	partitions	type	possible_keys	key	key_len	ref	rows	filtered	Extra
1	SIMPLE	t1	NULL	index_merge	i_a,i_b,i_ab,i_c	i_c,i_b,i_a	5,5,5	NULL	1	100.00	Using intersect(i_c,i_b,i_a); Using where; Using index
---
# Index merge i_a, i_b, i_c cannot be used since i_c is forced.
EXPLAIN SELECT /*+ INDEX_MERGE(t1 i_a, i_b, i_c) */ a FROM t1 FORCE INDEX (i_c) WHERE a = 1 AND b = 2 AND c = 3;
id	select_type	table	partitions	type	possible_keys	key	key_len	ref	rows	filtered	Extra
1	SIMPLE	t1	NULL	ref	i_c	i_c	5	const	1	5.00	Using where
---

1.6 Index hints can be used in view.

Example:
---
CREATE VIEW v1 AS SELECT a FROM t1 IGNORE KEY (i_a) ORDER BY a;

SHOW CREATE VIEW v1;
View	Create View	character_set_client	collation_connection
v1	CREATE ALGORITHM=UNDEFINED DEFINER=`root`@`localhost` SQL SECURITY DEFINER VIEW `v1` AS select `t1`.`a` AS `a` from `t1` IGNORE INDEX (`i_a`) order by `t1`.`a`	utf8mb4	utf8mb4_0900_ai_ci

EXPLAIN SELECT * FROM v1;
id	select_type	table	partitions	type	possible_keys	key	key_len	ref	rows	filtered	Extra
1	SIMPLE	t1	NULL	index	NULL	i_ab	10	NULL	256	100.00	Using index
---


2. Known problems with the index hints.

2.1 Index hints apply to SELECT statements only.
Hints for UPDATE/DELETE are not supported

2.2 Query fails with an error if the index specified in the hints
does not exists

2.3 FORCE INDEX FOR GROUP BY is not used as it should

Example:

CREATE TABLE t1 (a INT, b INT, KEY i1(a), KEY i2(a,b));
INSERT INTO t1 VALUES (1,1),(2,2),(3,3),(4,4),(5,5),(6,6),(7,7),(8,8);
INSERT INTO t1 SELECT a,b FROM t1;
INSERT INTO t1 SELECT a,b FROM t1;
INSERT INTO t1 SELECT a,b FROM t1;
INSERT INTO t1 SELECT a,b FROM t1;
INSERT INTO t1 SELECT a,b FROM t1;
ANALYZE TABLE t1;
---
explain SELECT a, MAX(b) FROM t1 GROUP BY a;
id	select_type	table	partitions	type	possible_keys	key	key_len	ref	rows	filtered	Extra
1	SIMPLE	t1	NULL	range	i1,i2	i2	5	NULL	9	100.00	Using index for group-by
---

# Tell MySQL to use 'i2' index for index scan
explain SELECT a, MAX(b) FROM t1 FORCE INDEX FOR GROUP BY (i2) GROUP BY a;
id	select_type	table	partitions	type	possible_keys	key	key_len	ref	rows	filtered	Extra
1	SIMPLE	t1	NULL	range	i1,i2	i2	5	NULL	9	100.00	Using index for group-by
---

Index scan is not used here but it should. The problem is that
MySQL by default consider all indexes as if 'USE INDEX' hint is
specified for them.

In other words the query

'SELECT a, MAX(b) FROM t1 GROUP BY a' is equivalent to

'SELECT a, MAX(b) FROM t1 USE INDEX(i1, i2) GROUP BY a'.

When FORCE INDEX FOR GROUP BY (i2) is used, 'i2' index is still
available for range scan and range scan is chosen since it's cheaper.
To avoid this problem it's necessary to specify additional hint:
---
explain SELECT a, MAX(b) FROM t1 FORCE INDEX FOR GROUP BY (i2)
IGNORE INDEX FOR JOIN (i2) GROUP BY a;
id	select_type	table	partitions	type	possible_keys	key	key_len	ref	rows	filtered	Extra
1	SIMPLE	t1	NULL	index	i1,i2	i2	10	NULL	256	100.00	NULL
---

Note there is no 'Using index' info in 'Extra' column despite the fact
that 'i2' is used here for index scan(one more bug to fix).

2.4 FORCE INDEX FOR ORDER BY is not used as it should.

There is a similar situation with 'FOR ORDER BY'.
---
explain SELECT a FROM t1 FORCE INDEX FOR ORDER BY (i2) ORDER BY a;
id	select_type	table	partitions	type	possible_keys	key	key_len	ref	rows	filtered	Extra
1	SIMPLE	t1	NULL	index	NULL	i1	5	NULL	256	100.00	Using index; Using filesort
---

2.5 USE INDEX and FORCE INDEX are indirectly used at the same time even
if it's not allowed(see 1.3 and 2.3).


3. New index hints.

3.1 The following new index hints are introduced:

  JOIN_INDEX/NO_JOIN_INDEX,
  GROUP_INDEX/NO_GROUP_INDEX,
  ORDER_INDEX/NO_ORDER_INDEX,
  INDEX/NO_INDEX.

  Data set for examples:
  ---
  CREATE TABLE t1 (a INT, b INT, c INT, d INT,
                   KEY i_a(a), KEY i_b(b),
                   KEY i_ab(a,b), KEY i_c(c), KEY i_d(d));
  INSERT INTO t1 VALUES
  (1,1,1,1),(2,2,2,1),(3,3,3,1),(4,4,4,1),
  (5,5,5,1),(6,6,6,1),(7,7,7,1),(8,8,8,1);
  INSERT INTO t1 SELECT a,b, c + 10, d FROM t1;
  INSERT INTO t1 SELECT a,b, c + 20, d FROM t1;
  INSERT INTO t1 SELECT a,b, c + 40, d FROM t1;
  INSERT INTO t1 SELECT a,b, c + 80, d FROM t1;
  INSERT INTO t1 SELECT a,b, c + 160, d FROM t1;
  ANALYZE TABLE t1;
  ---

  New index hints specification:

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

  New hints are index-level hints.
  (see https://dev.mysql.com/doc/refman/8.0/en/optimizer-hints.html#optimizer-hints-index-level for more details)

  Hints force the optimizer to use/ignore specified set of indexes for
  specified table. If no index is specified, all usable indexes are
  considered/ignored by the optimizer.

  3.1.1 JOIN_INDEX/NO_JOIN_INDEX forces MySQL to use/not use specified
  indexes for various access methods(ref, range etc). It's an analogue of
  FORCE/IGNORE INDEX FOR JOIN hint.

  Examples:
  # Force ref access for index i_a
  EXPLAIN SELECT /*+ JOIN_INDEX(t1 i_a) */ a FROM t1 WHERE a = 1 AND b = 2 AND c = 3;
  id	select_type	table	partitions	type	possible_keys	key	key_len	ref	rows	filtered	Extra
  1	SIMPLE	t1	NULL	ref	i_a	i_a	5	const	32	0.39	Using where

  # Ignore ref & range access for all indexes
  EXPLAIN SELECT /*+ NO_JOIN_INDEX(t1) */ a FROM t1 WHERE a = 1 AND b = 2 AND c = 3;
  id	select_type	table	partitions	type	possible_keys	key	key_len	ref	rows	filtered	Extra
  1	SIMPLE	t1	NULL	ALL	NULL	NULL	NULL	NULL	256	0.39	Using where

  3.1.2 GROUP_INDEX/NO_GROUP_INDEX forces MySQL to use/not use specified
  indexes for index scan for GROUP BY operation. It's an analogue of
  FORCE/IGNORE INDEX FOR GROUP BY hint.

  Examples:
  #Force i_ab index for GROUP BY, i_ab index scan is used.
  EXPLAIN SELECT /*+ GROUP_INDEX(t1 i_ab) */ a, max(b) FROM t1 GROUP BY a;
  id	select_type	table	partitions	type	possible_keys	key	key_len	ref	rows	filtered	Extra
  1	SIMPLE	t1	NULL	index	i_a,i_ab	i_ab	10	NULL	256	100.00	Using index

  # Ignore index for GROUP BY operation, loose scan is used.
  EXPLAIN SELECT /*+ NO_GROUP_INDEX(t1 i_ab) */ a, max(b) FROM t1 GROUP BY a;
  id	select_type	table	partitions	type	possible_keys	key	key_len	ref	rows	filtered	Extra
  1	SIMPLE	t1	NULL	range	i_a,i_ab	i_ab	5	NULL	9	100.00	Using index for group-by; Using temporary

  3.1.3 ORDER_INDEX/NO_ORDER_INDEX forces MySQL to use/not use specified
  indexes for sorting rows. It's an analogue of 
  FORCE/IGNORE INDEX FOR ORDER BY hint.

  Examples:
  # Force i_ab index for sorting rows
  EXPLAIN SELECT /*+ ORDER_INDEX(t1 i_ab) */ a FROM t1 ORDER BY a;
  id	select_type	table	partitions	type	possible_keys	key	key_len	ref	rows	filtered	Extra
  1	SIMPLE	t1	NULL	index	NULL	i_ab	10	NULL	256	100.00	Using index

  # Ignore indexes for order by, filesort is used for sorting rows.
  EXPLAIN SELECT /*+ NO_ORDER_INDEX(t1) */ a FROM t1 ORDER BY a;
  id	select_type	table	partitions	type	possible_keys	key	key_len	ref	rows	filtered	Extra
  1	SIMPLE	t1	NULL	index	NULL	i_a	5	NULL	256	100.00	Using index; Using filesort

  3.1.4 INDEX/NO_INDEX forces MySQL to use/not use specified indexes for 
  all the scopes of indexes(FOR JOIN, FOR GROUP BY, FOR ORDER BY).
  It's an analogue of FORCE/IGNORE INDEX hint.

  Examples:
  #Force the use of i_a, i_b indexes, intersect(i_a,i_b) is used.
  EXPLAIN SELECT /*+ INDEX(t1 i_a, i_b) */ a FROM t1 WHERE a = 1 AND b = 2 AND c = 3;
  id	select_type	table	partitions	type	possible_keys	key	key_len	ref	rows	filtered	Extra
  1	SIMPLE	t1	NULL	index_merge	i_a,i_b	i_a,i_b	5,5	NULL	4	1.25	Using intersect(i_a,i_b); Using where

  # Ignore i_a, i_b, i_ab indexes, i_c is used.
  EXPLAIN SELECT /*+ NO_INDEX(t1 i_a, i_b, i_ab) */ a FROM t1 WHERE a = 1 AND b = 2 AND c = 3;
  id	select_type	table	partitions	type	possible_keys	key	key_len	ref	rows	filtered	Extra
  1	SIMPLE	t1	NULL	ref	i_c	i_c	5	const	1	5.00	Using where

  New index hints have a higher priority than other index-level optimizer
  hints(SKIP_SCAN, INDEX_MERGE, etc). Index hints apply first and other
  index-level optimizer hints work with with the set of indexes limited by
  index hints.

3.2 Differences and changes in behavior of old and new index hints.

  3.2.1 If no index is specified with new index hints, all usable indexes are 
  considered/ignored by the optimizer. However, old index hints do not allow 
  empty index list for FORCE/IGNORE INDEX.

  Examples:
  # Force all possible indexes.
  EXPLAIN SELECT /*+ INDEX(t1) */ a FROM t1 WHERE a = 1 AND b = 2 AND c = 3;
  id	select_type	table	partitions	type	possible_keys	key	key_len	ref	rows	filtered	Extra
  1	SIMPLE	t1	NULL	ref	i_a,i_b,i_ab,i_c	i_ab	10	const,const	1	5.00	Using where

  #Ignore all indexes.
  EXPLAIN SELECT /*+ NO_INDEX(t1) */ a FROM t1 WHERE a = 1 AND b = 2 AND c = 3;
  id	select_type	table	partitions	type	possible_keys	key	key_len	ref	rows	filtered	Extra
  1	SIMPLE	t1	NULL	ALL	NULL	NULL	NULL	NULL	256	0.39	Using where

  3.2.2 Analogues of USE INDEX hints are not implemented. MySQL by default
  considers all indexes as if 'USE INDEX' hint is specified for them.
  So desired set of indexes with 'USE INDEX' behavior can be obtained
  using various combinations of
  NO_INDEX/NO_JOIN_INDEX/NO_GROUP_INDEX/NO_ORDER_INDEX hints.
  
  Examples:
  # Index i_c is used with old hint.
  EXPLAIN SELECT a FROM t1 USE INDEX (i_c)WHERE a = 1 AND b = 2 AND c = 3;
  id	select_type	table	partitions	type	possible_keys	key	key_len	ref	rows	filtered	Extra
  1	SIMPLE	t1	NULL	ref	i_c	i_c	5	const	1	5.00	Using where

  # The same behavior with new hint.
  EXPLAIN SELECT /*+ NO_INDEX(t1 i_a, i_b, i_ab) */ a FROM t1 WHERE a = 1 AND b = 2 AND c = 3;
  id	select_type	table	partitions	type	possible_keys	key	key_len	ref	rows	filtered	Extra
  1	SIMPLE	t1	NULL	ref	i_c	i_c	5	const	1	5.00	Using where

  3.2.3 Old index hints silently ignored if both old and new index hints
  are specified at the same time.

  Examples:
  # Old hints for index i_c is ignored.
  EXPLAIN SELECT /*+ INDEX(t1 i_b) */ a FROM t1 FORCE INDEX (i_c) WHERE a = 1 AND b = 2 AND c = 3;
  id	select_type	table	partitions	type	possible_keys	key	key_len	ref	rows	filtered	Extra
  1	SIMPLE	t1	NULL	ref	i_b	i_b	5	const	32	0.39	Using where

3.3 Using new hints in views.
    New index hints are allowed to be used in views.

  Examples:
  CREATE VIEW v1 AS SELECT /*+ NO_INDEX(t1 i_a,i_b) */ a FROM t1 WHERE
   b IN (SELECT /*+ NO_INDEX(t1 i_ab,i_b) */ a FROM t1 WHERE a > 3)
  ORDER BY a;
  CREATE VIEW v2 AS SELECT /*+ INDEX(ta i_a) */ ta.a FROM v1, t1 ta 
  WHERE ta.a >   3;

  SHOW CREATE VIEW v2;
  # Prints index hints specified in view body. Underlying view hints are not
  printed.
  ---
  View	Create View	character_set_client	collation_connection
  v2	CREATE ALGORITHM=UNDEFINED DEFINER=`root`@`localhost` SQL SECURITY 
  DEFINER VIEW `v2` AS select /*+ INDEX(`ta`@`select#1` `i_a`) */ `ta`.`a` AS 
  `a` from (`v1` join `t1` `ta`) where (`ta`.`a` > 3)	utf8mb4	  
  utf8mb4_0900_ai_ci
  ---

  EXPLAIN SELECT /*+ INDEX(tb i_a) */ tb.a FROM v2, t1 tb WHERE tb.a > 3;
  # Hints used in SELECT are printed after the first SELECT.
  # Hints used in underlying views are printed after corresponding table name.
  ---
  id	select_type	table	partitions	type	possible_keys	key	key_len	ref	rows	filtered	Extra
  1	SIMPLE	t1	NULL	range	i_a	i_a	5	NULL	160	5.00	Using where; Using index; LooseScan
  1	SIMPLE	t1	NULL	index	NULL	i_ab	10	NULL	256	12.50	Using where; Using index; Using join buffer (Block Nested Loop)
  1	SIMPLE	ta	NULL	range	i_a	i_a	5	NULL	160	100.00	Using where; Using index; Using join buffer (Block Nested Loop)
  1	SIMPLE	tb	NULL	range	i_a	i_a	5	NULL	160	100.00	Using where; Using index; Using join buffer (Block Nested Loop)
  Warnings:
  Note	1003	/* select#1 */ select /*+ INDEX(`tb`@`select#1` `i_a`) */ 
  `test`.`tb`.`a` AS `a` from `test`.`t1` /*+ NO_INDEX(`t1`@`select#1`
  `i_a`, `i_b`) */  semi join (`test`.`t1` /*+ NO_INDEX(`t1`@`select#2` `i_ab`, 
  `i_b`) */ ) join `test`.`t1` `ta` /*+ INDEX(`ta`@`select#1` `i_a`) */
  join `test`.`t1` `tb` where ((`test`.`t1`.`b` = `test`.`t1`.`a`) and 
  (`test`.`tb`.`a` > 3) and (`ta`.`a` > 3) and (`test`.`t1`.`a` > 3))
  ---


3.4 New index hints can be used with UPDATE/DELETE commands.

  # Force i_a index for UPDATE.
  EXPLAIN UPDATE /*+ INDEX(t1 i_a) */ t1 SET d = 1 WHERE a = 1 AND b = 2 AND c = 3;
  id	select_type	table	partitions	type	possible_keys	key	key_len	ref	rows	filtered	Extra
  1	UPDATE	t1	NULL	range	i_a	i_a	5	const	32	100.00	Using where

  # Force i_a index for DELETE.
  EXPLAIN DELETE /*+ INDEX(t1 i_a) */ FROM t1 WHERE a = 1 AND b = 2 AND c = 3;
  id	select_type	table	partitions	type	possible_keys	key	key_len	ref	rows	filtered	Extra
  1	DELETE	t1	NULL	range	i_a	i_a	5	const	32	100.00	Using where

sql/opt_hints.h

Class Opt_hints:
  added new function
    virtual const LEX_CSTRING *get_print_name();

class Compound_key_hint:
  added new functions
    Key_map *get_key_map();
    bool is_hint_conflicting(Opt_hints_table *table_hint,
                            Opt_hints_key *key_hint) 

New auxiliary classes for the check of intersected hints:

/**
  Auxiliary class for JOIN_INDEX, GROUP_INDEX, ORDER_INDEX hints.
*/
class Index_key_hint : public Compound_key_hint {
 public:
  bool is_hint_conflicting(Opt_hints_table *table_hint,
                           Opt_hints_key *key_hint) override;
};

/**
  Auxiliary class for INDEX hint.
*/
class Glob_index_key_hint : public Compound_key_hint {
 public:
  bool is_hint_conflicting(Opt_hints_table *table_hint,
                           Opt_hints_key *key_hint) override;
};


class Opt_hints_table:
  added compound hints
   Glob_index_key_hint index;  // For INDEX/NO_INDEX
   Index_key_hint join_index;  // For JOIN_INDEX/NO_JOIN_INDEX
   Index_key_hint group_index; // For GROUP_INDEX/NO_GROUP_INDEX
   Index_key_hint order_index; // For ORDER_INDEX/NO_ORDER_INDEX

  added new methods
   // Check if the hint forces to use indexes.
   bool is_force_index_hint(opt_hints_enum type_arg) 
   // Check if the hint is conflicting with previously specified
   // index hints.
   bool is_hint_conflicting(Opt_hints_key *key_hint, opt_hints_enum type);
   /**
    Function updates key_to_use key map depending on index hint state.

    @param keys_to_use            key to use
    @param available_keys_to_use  available keys to use
    @param type_arg               hint type
   */
   void update_index_hint_map(Key_map *keys_to_use,
                              Key_map *available_keys_to_use,
                              opt_hints_enum type_arg);
   /**
    Function updates keys_in_use_for_query, keys_in_use_for_group_by,
    keys_in_use_for_order_by depending on INDEX, JOIN_INDEX, GROUP_INDEX,
    ORDER_INDEX hints.

    @param thd            pointer to THD object
    @param tbl            pointer to TABLE object

    @return false if no index hint is specified, true otherwise.
   */
    update_index_hint_maps(THD *thd, TABLE *tbl)

sql/parse_tree_hints.cc:
   function find_qb_hints() is modified so that it can find
   a query block using system name(i.e. name generated using
   'select#' prefix and select number)

   PT_qb_level_hint::append_args()
     added check for hints which can be used in view.

   PT_key_level_hint::append_args()
     refactored so that it can detect intersected index hints.

sql/sql_bitmap.h

class Bitmap<64>
  added new method
    uint bits_set();

sql/sql_lex.cc
  Function print_table_array()
    added the code which prints table-level hint info
    after table name(used for EXPLAIN only).

  SELECT_LEX::print_hints()
    modified so that it can print hints for 
    CREATE VIEW & SHOW CREATE VIEW commands.

sql/sql_resolver.cc
  SELECT_LEX::setup_tables()
  added Opt_hints_table::set_index_hint_maps() method call.

sql/sql_view.cc
  parse_view_definition()
  added the code which allows to print hints specified in view.