Bug #16166 cannot force index merge

Description:
It is sometimes not possible to force index merge.

This limitation can make it impossible to use index merge in queries with a range scan (per documentat, FORCE INDEX is required in some situations where a range scan occurs).

How to repeat:
DROP TABLE IF EXISTS t1;
CREATE TABLE t1 (cola char(3) not null, colb char(3) not null, key (cola), key (colb));

INSERT INTO t1 VALUES ('foo','bar'),('fuz','baz');

explain select * from t1 WHERE cola = 'foo' AND colb = 'bar';
explain select * from t1 force index(cola,colb) WHERE cola = 'foo' AND colb = 'bar';

-- we need to have to have a few thousand more rows for index merge to work...
INSERT INTO t1 SELECT * from t1 WHERE cola = 'foo';
INSERT INTO t1 SELECT * from t1 WHERE cola = 'foo';
INSERT INTO t1 SELECT * from t1 WHERE cola = 'foo';
INSERT INTO t1 SELECT * from t1 WHERE cola = 'foo';
INSERT INTO t1 SELECT * from t1 WHERE cola = 'foo';
INSERT INTO t1 SELECT * from t1 WHERE cola = 'foo';
INSERT INTO t1 SELECT * from t1 WHERE cola = 'foo';
INSERT INTO t1 SELECT * from t1 WHERE cola = 'foo';
INSERT INTO t1 SELECT * from t1 WHERE cola = 'foo';

INSERT INTO t1 SELECT * from t1 WHERE cola <> 'foo';
INSERT INTO t1 SELECT * from t1 WHERE cola <> 'foo';
INSERT INTO t1 SELECT * from t1 WHERE cola <> 'foo';
INSERT INTO t1 SELECT * from t1 WHERE cola <> 'foo';
INSERT INTO t1 SELECT * from t1 WHERE cola <> 'foo';
INSERT INTO t1 SELECT * from t1 WHERE cola <> 'foo';
INSERT INTO t1 SELECT * from t1 WHERE cola <> 'foo';
INSERT INTO t1 SELECT * from t1 WHERE cola <> 'foo';
INSERT INTO t1 SELECT * from t1 WHERE cola <> 'foo';
INSERT INTO t1 SELECT * from t1 WHERE cola <> 'foo';
INSERT INTO t1 SELECT * from t1 WHERE cola <> 'foo';
INSERT INTO t1 SELECT * from t1 WHERE cola <> 'foo';
INSERT INTO t1 SELECT * from t1 WHERE cola <> 'foo';

OPTIMIZE TABLE t1;
explain select * from t1 WHERE cola = 'foo' AND colb = 'bar';
explain select * from t1 force index(cola,colb) WHERE cola = 'foo' AND colb = 'bar';

-- Apparently there is a certain threshhold before index merge is used.... this should be documented somewhere if this does not already exist
INSERT INTO t1 SELECT * from t1 WHERE cola <> 'foo';

OPTIMIZE TABLE t1;

explain select * from t1 WHERE cola = 'foo' AND colb = 'bar';
explain select * from t1 force index(cola,colb) WHERE cola = 'foo' AND colb = 'bar';

Suggested fix:
Using FORCE INDEX should always cause the optimizer to do an index merge if the index merge is logically possible.

FORCE INDEX(idx1, idx2) tells the server that using table scan is much more expensive than using index idx1 OR idx2 OR both of them.

The problem is that FORCE INDEX *prevents* index merge from happening in a situation where index merge is normally selected by the optimizer.

The first two explains of the original example give the following output:

mysql 5.0.17-max (root) "test"> explain select * from t1 WHERE cola = 'foo' AND colb = 'bar' \G
*************************** 1. row ***************************
           id: 1
  select_type: SIMPLE
        table: t1
         type: ref
possible_keys: cola,colb
          key: cola
      key_len: 3
          ref: const
         rows: 1
        Extra: Using where
1 row in set (0.00 sec)

mysql 5.0.17-max (root) "test"> explain select * from t1 force index (cola, colb) WHERE cola = 'foo' AND colb = 'bar' \G
*************************** 1. row ***************************
           id: 1
  select_type: SIMPLE
        table: t1
         type: ref
possible_keys: cola,colb
          key: cola
      key_len: 3
          ref: const
         rows: 1
        Extra: Using where
1 row in set (0.00 sec)

The last two explains of the original example give the following output:

mysql 5.0.17-max (root) "test"> explain select * from t1 WHERE cola = 'foo' AND colb = 'bar' \G
*************************** 1. row ***************************
           id: 1
  select_type: SIMPLE
        table: t1
         type: index_merge
possible_keys: cola,colb
          key: cola,colb
      key_len: 3,3
          ref: NULL
         rows: 14
        Extra: Using intersect(cola,colb); Using where; Using index
1 row in set (0.00 sec)

mysql 5.0.17-max (root) "test"> explain select * from t1 force index(cola,colb) WHERE cola = 'foo' AND colb = 'bar' \G
*************************** 1. row ***************************
           id: 1
  select_type: SIMPLE
        table: t1
         type: ref
possible_keys: cola,colb
          key: cola
      key_len: 3
          ref: const
         rows: 555
        Extra: Using where
1 row in set (0.00 sec)

A patch for this bug has been committed. After review, it may
be pushed to the relevant source trees for release in the next
version. You can access the patch from:

  http://lists.mysql.com/commits/910

A patch for this bug has been committed. After review, it may
be pushed to the relevant source trees for release in the next
version. You can access the patch from:

  http://lists.mysql.com/commits/946

The fix has been pushed into 5.0.19 tree.

Note for the changelog:
For query that used Index Merge intersection algorithm for indexes idx1... idxN , adding "FORCE INDEX (idx1,...,idxN) caused the Index Merge intersection not to be used anymore ("ref" on one of idx{i} was used instead).

Added to 5.0.19 changelog:

<listitem>
        <para>
          The <literal>FORCE INDEX</literal> keyword in a query would
          prevent an index merge from being used where an index merge
          would normally be chosen by the optimizer. (Bug #16166)
        </para>
      </listitem>