MySQL Bugs: #11989: indexes not used when different columns are referenced around OR condition

Bug #11989	indexes not used when different columns are referenced around OR condition
Submitted:	17 Jul 2005 14:00	Modified:	18 Jul 2005 15:48
Reporter:	Frank van Viegen	Email Updates:
Status:	Not a Bug	Impact on me:	None
Category:	MySQL Server	Severity:	S3 (Non-critical)
Version:	4.1.12	OS:	pc-linux-gnu (i386)
Assigned to:	Aleksey Kishkin	CPU Architecture:	Any

Description:
When different indexed colums are referenced on both sides of an OR statement in a WHERE condition, their respective indexes are not used.

How to repeat:
create table test (a int not null, b int not null, primary key(a), key(b));
insert into test(a,b) values(1,2);
insert into test(a,b) values(3,4);
explain select * from test where a=3 || b=3;
-> type=ALL
-> possible_keys=PRIMARY,b
-> key=NULL

Suggested fix:
A work-around (which gets nasty for more complicated queries) is to use a UNION instead of an OR condition:

select * from test where a=3 union select * from test where a=4;

Being the naive mysql user that I am however, I was *very* surpised to find out that mysql does not perform this optimization by itself. For my current project it turned out that my false assumption in this matter was exposed in about 10 different queries, leading to pretty extreme scalability problems.

Could you test it on 4.1.12 ? 

At least when I tried I got:

mysql> explain select * from test where a=3 || b=3 \G
*************************** 1. row ***************************
           id: 1
  select_type: SIMPLE
        table: test
         type: index
possible_keys: PRIMARY,b
          key: b
      key_len: 4
          ref: NULL
         rows: 2
        Extra: Using where; Using index
1 row in set (0.00 sec)

I tried the exact same thing on 4.1.12 from debian, with the same results. If you like I could try on a non-debian mysql as well, however I have found out that the discrepancy between our results is probably caused by different table types. When I change the table type from MyISAM to InnoDB, I get the same output you did.

Your MySQL connection id is 8 to server version: 4.1.12-Debian_1-log

mysql> explain select * from test where a=3 || b=3\G
*************************** 1. row ***************************
           id: 1
  select_type: SIMPLE
        table: test
         type: ALL
possible_keys: PRIMARY,b
          key: NULL
      key_len: NULL
          ref: NULL
         rows: 2
        Extra: Using where
1 row in set (0.00 sec)

mysql> alter table test type = innodb;

mysql> explain select * from test where a=3 || b=3\G
*************************** 1. row ***************************
           id: 1
  select_type: SIMPLE
        table: test
         type: index
possible_keys: PRIMARY,b
          key: b
      key_len: 4
          ref: NULL
         rows: 2
        Extra: Using where; Using index
1 row in set (0.01 sec)

Frank, 

mysql for small tables can use tablescan instead of index search (it makes some profit in IO operations). How big tables did you test?

It still happens for pretty large (450k rows) tables. That's how I  found out about the problem; you can imagine queries starting to show up in the slow-query-log when you join something like this with another reasonably large table.

mysql> explain select * from messages where id=5 or matchId=5\G
*************************** 1. row ***************************
           id: 1
  select_type: SIMPLE
        table: messages
         type: ALL
possible_keys: PRIMARY,matchId
          key: NULL
      key_len: NULL
          ref: NULL
         rows: 450341
        Extra: Using where
1 row in set (0.00 sec)

could you submit this table to our ftp server? It will be visible for our developers only. the point is we need a testcase in order to check what's wrong.. 

ftp://ftp.mysql.com/pub/mysql/upload/

PS. did you test 'force index'?

The contents of this particular table is a bit privacy sensitive and bit large, so I made up a bogus table with a reasonable amount of records and uploaded it as bug11989.sql.gz. The problem seems to occur on every MyISAM table though. 

mysql> describe bug11989\G
*************************** 1. row ***************************
  Field: a
   Type: int(11)
   Null:
    Key: MUL
Default: 0
  Extra:
*************************** 2. row ***************************
  Field: b
   Type: int(11)
   Null:
    Key: MUL
Default: 0
  Extra:
2 rows in set (0.00 sec)

mysql> explain select * from bug11989 where a=5 or b = 5\G
*************************** 1. row ***************************
           id: 1
  select_type: SIMPLE
        table: bug11989
         type: ALL
possible_keys: a,b
          key: NULL
      key_len: NULL
          ref: NULL
         rows: 88377
        Extra: Using where
1 row in set (0.00 sec)

For this larger table, InnoDB now gives the same result.

Using 'force index(a)' or 'force index(b)' reduces what is listed as 'possible_keys', but the actual key is still NULL.

Delving a bit more into the subject, what I'd expect to see from EXPLAIN is actually a bit more complicated than I expected at first. :) So maybe this is actually more of a feature request than a bug-report (running into it feels like a bug though :)). I guess the output would need to be something along the lines of:

*************************** 1. row ***************************
           id: 1
  select_type: PRIMARY
        table: bug11989
         type: ref
possible_keys: a
          key: a
      key_len: 4
          ref: const
         rows: 1
        Extra: Using where
*************************** 2. row ***************************
           id: 2
  select_type: UNION
        table: bug11989
         type: ref
possible_keys: b
          key: b
      key_len: 4
          ref: const
         rows: 1
        Extra: Using where
*************************** 3. row ***************************
           id: NULL
  select_type: UNION RESULT
        table: <union1,2>
         type: ALL
possible_keys: NULL
          key: NULL
      key_len: NULL
          ref: NULL
         rows: NULL
        Extra:
3 rows in set (0.00 sec)

MySQL before 5.0.4 could not use index on OR clauses, unless all columns involved are in composite index.

This is fixed in 5.0.