MySQL Bugs: #11945: Index not used in 'OUTER JOIN b ON (a.a = b.a OR a.a = b.b)'

Bug #11945	Index not used in 'OUTER JOIN b ON (a.a = b.a OR a.a = b.b)'
Submitted:	14 Jul 2005 16:23	Modified:	15 Jan 2010 17:14
Reporter:	Ken Johanson	Email Updates:
Status:	No Feedback	Impact on me:	None
Category:	MySQL Server: Optimizer	Severity:	S2 (Serious)
Version:	5.0.7	OS:	Linux (Linux /Fedora 3)
Assigned to:		CPU Architecture:	Any

Description:
Following query does not use existing indexes in fields b.a or b.b.

describe SELECT '1'
FROM a
LEFT JOIN b ON (a.a = b.a OR a.a = b.b)

The following also performs only a non-index join

describe SELECT '1'
FROM a
LEFT JOIN b ON a.a IN (a.a, b.b)

The FORCE INDEX syntax also does not help.

How to repeat:
Execute above samples using tables having indexes on all the above-referenced fields

Typo correction:

describe SELECT '1'
FROM a
LEFT JOIN b ON a.a IN (b.a, b.b)

(table ref in first list item)

Thanks for your bug report.

Verified using 5.0.7 under Win32 !

create table a (a int not null, b int not null, primary key(a,b));
create table b (a int not null, b int not null, primary key(a,b));

mysql> describe SELECT '1'
    -> FROM a
    -> LEFT JOIN b ON a.a IN (b.a, b.b);
+----+-------------+-------+--------+---------------+------+---------+------+---
---+---------------------+
| id | select_type | table | type   | possible_keys | key  | key_len | ref  | ro
ws | Extra               |
+----+-------------+-------+--------+---------------+------+---------+------+---
---+---------------------+
|  1 | SIMPLE      | a     | system | NULL          | NULL | NULL    | NULL |
 0 | const row not found |
|  1 | SIMPLE      | b     | system | NULL          | NULL | NULL    | NULL |
 0 | const row not found |
+----+-------------+-------+--------+---------------+------+---------+------+---
---+---------------------+
2 rows in set (0.00 sec)

This is actually a request for an optimization.
This optimization hopefully will be implemented in version 5.2.

I'm in no position to argue... but this seems more like a bug (even if it simply has never been implemented), because other DBs (I've tried two) do search in the indexes; the query seems pretty simple; more of all, this causes a HUGE performance hit on a table that is only about 20000 rows (and my table is growing rapidly)... And 5.2 appears to be a long way out (1+ years my guess?). I'm not reliant on this beta version - I only tested on it to see if the problem went away from my 4.x production version, which is where the fix really seems needed.

Please, this should be raised to a higher priority - the query is arguably very simple, but its lack of optimization yields abominable performance that appears to increase exponentially when one table's column count grows. I have a working table with only 20000 rows but the query takes 10 seconds on a 2Ghz box.. its used to take 3 seconds with half as many rows.

This *certainly* is not a trivial bug (and its is a bug from a high level / end-user perspective, in the optimizer, not a 'feature request')

It is possible that these two are related. I am, however, not an expert on the 'under the hood' workings of the DBMS. This is a question better directed to the MySQL developer to whom this is assigned.

As a side note, however, it would seem to me that any time a join is performed and no index is used even though an appropriate index is available that this constitutes a feature deficiency of sufficient severity to qualify as a bug.

As far as I can see index is used in recent 5.0:

77-52-7-73:5.0 openxs$ bin/mysql -uroot test
Reading table information for completion of table and column names
You can turn off this feature to get a quicker startup with -A

Welcome to the MySQL monitor.  Commands end with ; or \g.
Your MySQL connection id is 1
Server version: 5.0.89-debug Source distribution

Type 'help;' or '\h' for help. Type '\c' to clear the current input statement.

mysql> create table a (a int not null, b int not null, primary key(a,b));
Query OK, 0 rows affected (0.01 sec)

mysql> create table b (a int not null, b int not null, primary key(a,b));
Query OK, 0 rows affected (0.00 sec)

mysql> insert into a values(1,1), (2,2), (3,3);
Query OK, 3 rows affected (0.00 sec)
Records: 3  Duplicates: 0  Warnings: 0

mysql> insert into b values(1,1), (0,0);
Query OK, 2 rows affected (0.00 sec)
Records: 2  Duplicates: 0  Warnings: 0

mysql> explain SELECT '1'
    -> FROM a
    -> LEFT JOIN b ON a.a IN (b.a, b.b)
    -> \G
*************************** 1. row ***************************
           id: 1
  select_type: SIMPLE
        table: a
         type: index
possible_keys: NULL
          key: PRIMARY
      key_len: 8
          ref: NULL
         rows: 3
        Extra: Using index
*************************** 2. row ***************************
           id: 1
  select_type: SIMPLE
        table: b
         type: index
possible_keys: NULL
          key: PRIMARY
      key_len: 8
          ref: NULL
         rows: 2
        Extra: Using index
2 rows in set (0.02 sec)

Do you need anything else?

No feedback was provided for this bug for over a month, so it is
being suspended automatically. If you are able to provide the
information that was originally requested, please do so and change
the status of the bug back to "Open".