WL#3527: Extend IGNORE INDEX so places where index is ignored can be specified

Currently MySQL allows one to specify what indexes to ignore during
join optimization. The scope of the current IGNORE INDEX statement is
only the FROM clause, while all other clauses are not affected.

However, in certain cases (see BUG#21174 for an example), the optimizer
may incorrectly choose an index for sorting and/or grouping, and
produce an inefficient query plan.

TODO: This WorkLog can be extended to add the FOR {JOIN | ORDER | GROUP BY}
clause to USE INDEX and FORCE INDEX. This addition will balance the three
clauses and contribute to more consistent syntax.

This task provides the means to specify what indexes are
ignored for what operation in a more fine-grained manner, thus
making it possible to manually force a better plan. We do this
by extending the current IGNORE INDEX syntax to:

IGNORE INDEX [FOR {JOIN | ORDER | GROUP BY}]

so that:
- if no FOR is specified, the index will be ignored everywhere
  (as in the current 5.1.??? after the fix for BUG#21174).
- if MySQL is started with the compatiblity option --old then
  IGNORE INDEX without a FOR clause works as 5.0 (ie, the index
  will only be ignored for JOINs, but can still be used to
  compute ORDER BY.

See BUG#21174 for further details

Copyright (c) 2001-2007 by MySQL AB. All rights reserved.

LLD for WL#3527:  Extend IGNORE INDEX so places where index is ignored
can be specified (ver.3.0)

The current implementation of IGNORE INDEX stores the index names
in a list of Strings in SELECT_LEX::ignore_index. The problem with
this approach is that there is one such list per select, therefore
this list is naturally interpreted as referring to the whole select.

In order to allow the user to ignore indexes in various clauses/parts
of a select, we suggest making a tagged list of strings. 
The list will unite the current USE and IGNORE lists.
Each element of the list will have an index name and a tag that denotes 
the place where this index is quoted : 
IGNORE [FOR JOIN | FOR ORDER BY |  FOR GROUP BY], USE or FORCE.
One such list will be added to SELECT_LEX (used by the parser to collect
the data for the current table) and in TABLE_LIST to store the data about
index hints for the table.
We will then add two new keymaps to TABLE (to complement
keys_in_use_for_query) : keys_in_use_for_group_by and 
keys_in_use_for_order_by. All the keymap will be filled in setup_tables()
and used at the appropriate places.                                            
                         
Examples of intended use:
SELECT a FROM t1 IGNORE INDEX FOR JOIN i1,i2;
SELECT a FROM t1 IGNORE INDEX FOR GROUP BY i2;
SELECT a FROM t1 IGNORE INDEX FOR ORDER BY i3;

We will also extend the syntax of IGNORE INDEX to support multiple
IGNORE INDEX statements (in no particular order) that concatenate 
the list of indexes to a single list.
Examples :

don't consider i1 for GROUP BY and i2 for ORDER BY:
SELECT a FROM t1 
  IGNORE INDEX FOR GROUP BY i1 IGNORE INDEX FOR ORDER BY i2;

don't consider i1 at all (join,GROUP BY,ORDER BY) and i2 for ORDER BY:
SELECT a FROM t1 
  IGNORE INDEX i1 IGNORE INDEX FOR ORDER BY i2;

The above can be expressed as :
SELECT a FROM t1 
  IGNORE INDEX FOR GROUP BY i1 
  IGNORE INDEX FOR JOIN i1 
  IGNORE INDEX FOR ORDER BY i1,i2;

don't consider i1 and i2 for GROUP BY:
SELECT a FROM t1 
  IGNORE INDEX FOR GROUP BY i1 IGNORE INDEX FOR GROUP BY i2;

The above can be expressed as :
SELECT a FROM t1 
  IGNORE INDEX FOR GROUP BY i1,i2;

We make the changes to 5.1
We make IGNORE INDEX ,...  equivalent to :
IGNORE INDEX FOR JOIN ,...
IGNORE INDEX FOR ORDER BY ,...
IGNORE INDEX FOR GROUP BY ,...
which corresponds to a more natural meaning.
We add a mysqld option to initialize IGNORE INDEX without 
further specification in a 5.0 compatible way : i.e. only add to 
IGNORE INDEX FOR JOIN list instead of all. 
This option is to be obsoleted for 5.2 leaving only the new 
behaviour.
In 5.0 we only add an IGNORE INDEX FOR JOIN that is equivalent to
IGNORE INDEX.

Care must be taken with the -old_mode option and statement based replication :
as having the master and the slave in different modes my lead to replication
errors. This must be very clearly mentioned in the documentation of the option.

List of changes needed: 

1. Declare an enum key_usage_type { INDEX_HINT_IGNORE_JOIN, 
  INDEX_HINT_IGNORE_GROUP, INDEX_HINT_IGNORE_ORDER, INDEX_HINT_IGNORE, 
  INDEX_HINT_USE, INDEX_HINT_FORCE } for the tags of the tagged list.

2. Declare the tagged list element :
 class key_usage : public Sql_alloc
 {
   public:
     enum key_usage_type type;
     LEX_STRING name;
   
     key_usage (enum key_usage_type type_arg, char *str, uint length) : 
       type(type_arg)
     {
       name.str= str;
       name.length= length;
     }
 }; 

3. Take out the following  members from SELECT_LEX : 
  use_index, *use_index_ptr, ignore_index, *ignore_index_ptr
  together with the corresponding utility member functions : 
  get_use_index(), get_ignore_index().
  This removes the initialization of these from 
  SELECT_LEX::init_select(). 
  Take out use_index/ignore_index from TABLE_LIST.

4. Add the tagged list members to SELECT_LEX :   
  /* current index hint kind. used in filling up index_hints */
  enum key_usage_type key_usage_type;
  /* a list of USE/FORCE/IGNORE INDEX */
  List index_hints;

5. Add keys_in_use_for_group_by and keys_in_use_for_order_by to
   TABLE (next to keys_in_use_for_query).

6. Add an List element in TABLE_LIST to hold a copy of
   the tagged list from SELECT_LEX.

7. Add utility functions to handle the tagged list in SELECT_LEX: 
  /* add a index hint to the tagged list of hints */
  bool index_hint_add (char *str, uint length)
  {
    return index_hints.push_front (new key_usage(key_usage_type, 
                                                 str, length));
  }

  /* specify the type of hint the index_hint_add will use */
  void set_current_hint(enum key_usage_type type)
  {
    key_usage_type= type;
  }

  List* get_index_hints(void) { return &index_hints; }
  void clear_index_hints(void) { index_hints.empty(); }

8. Rename TABLE->used_keys to keys_usable_in_read_only

9. make a function st_table_list::process_index_hints() to 
   iterate over the tagged list in TABLE_LIST and fill up the 
   bitmaps in TABLE.

10. Make ha_myisam::assign_to_keycache() and ha_myisam::preload_keys()
  use the new (single list).

11. Remove the initialization of keys_in_use_for_query and used_keys
  from open_table()/reopen_table()/reopen_name_locked_table().

12. Make setup_tables() initialize the table->keys_in_use_for_query and 
  the new members table->keys_in_use_for_order_by and 
  table->keys_in_use_for_group_by. setup_table() does that by iterating
  calling TABLE_LIST::process_index_hints

13. Modify the SELECT_LEX::add_table_to_list() to use the new tagged 
  list (copy it from SELECT_LEX to TABLE_LIST).

14. Add the keymap to use as an argument to test_if_skip_sort_order(). 
  Pass either keys_in_use_for_group_by or keys_in_use_for_order_by 
  depending of what is being processed. Use that argument instead of
  table->s->keys_in_use to make the index hints FOR ORDER BY/FOR 
  GROUP BY effective.

15. Extend the parser to :
 - Support multiple index hints
 - Reset the tagged list in SELECT_LEX at the start of processing a 
   table.
 - Set the current index hint kind in SELECT_LEX.  
 - Fill the tagged list in SELECT_LEX using the current_index_hint.
 - Pass the collected hints list to add_table_to_list()

16. add an '--old' option to mysqld :
   - new enum OPT_OLD to options_mysqld enum in mysqld.cc
   - new member 'my_bool opt_old' to system_variables
   - new initializer to my_long_options[] in mysqld.cc:
     {"old", OPT_OLD,
       "Use compatible behaviour.",
       (gptr*) &global_system_variables.opt_old,
       (gptr*) &max_system_variables.opt_old, 0, GET_BOOL, 
       NO_ARG, 0, 0, 0, 0, 0, 0},
   - initialize global_system_variables.opt_old to zero in 
     mysql_init_variables()
   - add a new thread variable in set_var.cc :
     sys_var_thd_bool    sys_old("old",&SV::opt_old);