MySQL Bugs: #12284: Full index not used when joining tables

Bug #12284	Full index not used when joining tables
Submitted:	30 Jul 2005 12:23	Modified:	18 Aug 2005 11:56
Reporter:	Perry Stupp	Email Updates:
Status:	Closed	Impact on me:	None
Category:	MySQL Server: Optimizer	Severity:	S2 (Serious)
Version:	4.1.7	OS:	Linux (Linux 2.4.7-10)
Assigned to:		CPU Architecture:	Any

Description:
I am working with two queries that are essentially "equivalent" in that they return the same resultset. While the "data" is retrieved from only one table, the difference between the two queries is that one explicitly lists several foreign key id's while the other query needs to look them up using a join; i.e. 

Query 1 - 

select * 
  from datatable 
where fk1 = 1 and fk2 = 2 and datetime between 'DATE1' and 'DATE2'... 

vs. 

Query 2 - 

select * 
from datatable, fktable1, fktable2 
where fktable1.name = 'one' and fktable2.name = 'two' 
and datatable.fk1 = fktable1.id and datatable.fk2 = fktable2.id 
and datetime between 'DATE1' and 'DATE2' 

The index needed to optimize the query is index1

fk1, fk2, datetime 

Now, when I run explain plan on the first query it indicates that it needs to search only 159 records which is pretty much as I expected / want. i.e. 

+----+-------------+-----------+-------+---------------+--------+---------+------+------+-------------+
| id | select_type | table     | type  | possible_keys | key    | key_len | ref  | rows | Extra       |
+----+-------------+-----------+-------+---------------+--------+---------+------+------+-------------+
|  1 | SIMPLE      | datatable | range | index1,index2 | index1 |      26 | NULL |  159 | Using where |
+----+-------------+-----------+-------+---------------+--------+---------+------+------+-------------+

when I run explain plan on the second query, however, the number of rows that need to be searched for the same data is 14736. 

+----+-------------+-----------+-------+---------------+----------+---------+-------------+-------+-------------+
| id | select_type | table     | type  | possible_keys | key      | key_len | ref         | rows  | Extra       |
+----+-------------+-----------+-------+---------------+----------+---------+-------------+-------+-------------+
|  1 | SIMPLE      | fktable1  | const | fkindex1      | fkindex1 |     100 | const       |     1 |             |
|  1 | SIMPLE      | fktable2  | const | fkindex2      | fkindex2 |      50 | const       |     1 |             |
|  1 | SIMPLE      | datatable | range | index1,index2 | index1   |      22 | const,const |  14736| Using where |
+----+-------------+-----------+-------+---------------+----------+---------+------+------+---------------------+

The difference is that the key_len of the second query is shorter - presumably because it is not using the date portion of the index (and hence the extra rows to search). I guess my question is, why isn't it using the full index on the second query? Is this working as expected or possibly a bug? 

In my search to find an answer I found a similar concern posted at http://lists.mysql.com/mysql/185090.

Thanks for your assistance.

How to repeat:
Create three tables

datatable
| Field              | Type            | Null  | Key | Default                     | Extra |
| fk1                | decimal(10,0) |       |       | 0                             |       |
| fk2                | decimal(10,0) |       |       | 0                             |       |
| datetime        | timestamp      | YES |       | CURRENT_TIMESTAMP |       |
| value             | decimal(10,0) |       |       | 0                             |       |

index1 = fk1, fk2, datetime

fktable1
+-------+---------------+------+-----+---------+-------+
| Field | Type          | Null | Key | Default | Extra |
+-------+---------------+------+-----+---------+-------+
| id    | decimal(10,0) |      | UNI | 0       |       |
| name  | varchar(100)  |      | PRI |         |       |
+-------+---------------+------+-----+---------+-------+

fkindex1 = name
fkindex1a = id

fktable2
+-------+---------------+------+-----+---------+-------+
| Field | Type          | Null | Key | Default | Extra |
+-------+---------------+------+-----+---------+-------+
| id    | decimal(10,0) |      | UNI | 0       |       |
| name  | varchar(100)  |      | PRI |         |       |
+-------+---------------+------+-----+---------+-------+

fkindex2 = name
fkindex2a = id

Query with desired results / performance

select * 
  from datatable 
where fk1 = 1 and fk2 = 2 and datetime between 'DATE1' and 'DATE2'... 

Query not using full index - poor performance

select * 
from datatable, fktable1, fktable2 
where fktable1.name = 'one' and fktable2.name = 'two' 
and datatable.fk1 = fktable1.id and datatable.fk2 = fktable2.id 
and datetime between 'DATE1' and 'DATE2'

Just wanted to add that when I do

select * 
from datatable, fktable1, fktable2 
where fktable1.name = 'one' and fktable2.name = 'two' 
and datatable.fk1 = fktable1.id and datatable.fk2 = fktable2.id 
and datetime = 'DATE1' 

it uses the full index and returns instantaneously.  The problem of course is that I need a date range so this doesn't work for my application.

I also found that the full index is used when the date range doesn't return any values.

Perhaps this is better categorized under 'Optimizer'?  Unfortunately my application won't scale without this capability and we have only a limited amount of time before we'll be forced back to Oracle if this isn't addressed.  Any help would be greatly appreciated...

Hi! When I tested against 4.1.12 , I got little bit another query plan.  Could you check your database against latest mysql server? And if you still have bad query plan, I need exact table definitions and data you tested (if it contains some private info, you can upload it to our ftp and nobody but developers will be able to read it).

 explain select *  from datatable, fktable1, fktable2  where fktable1.name = 'A' and fktable2.name = 'B'  and datatable.fk1 = fktable1.id and datatable.fk2 = fktable2.id  and dt between '2005-01-01' and '2005-09-01';
+----+-------------+-----------+-------+---------------+---------+---------+-------------+------+--------------------------+
| id | select_type | table     | type  | possible_keys | key     | key_len | ref         | rows | Extra                    |
+----+-------------+-----------+-------+---------------+---------+---------+-------------+------+--------------------------+
|  1 | SIMPLE      | fktable1  | const | PRIMARY,id    | PRIMARY |     300 | const       |    1 |                          |
|  1 | SIMPLE      | fktable2  | const | PRIMARY,id    | PRIMARY |     300 | const       |    1 |                          |
|  1 | SIMPLE      | datatable | ref   | i1            | i1      |      24 | const,const |    1 | Using where; Using index |
+----+-------------+-----------+-------+---------------+---------+---------+-------------+------+--------------------------+
3 rows in set (0.00 sec)

I did following tables:
 CREATE TABLE `datatable` (
  `fk1` decimal(10,0) default NULL,
  `fk2` decimal(10,0) default NULL,
  `dt` timestamp NOT NULL default CURRENT_TIMESTAMP on update CURRENT_TIMESTAMP,
  KEY `i1` (`fk1`,`fk2`,`dt`)
) ENGINE=MyISAM DEFAULT CHARSET=utf8 ;

 CREATE TABLE `fktable1` (
  `id` decimal(10,0) default NULL,
  `name` varchar(100) NOT NULL default '',
  PRIMARY KEY  (`name`),
  UNIQUE KEY `id` (`id`)
) ENGINE=MyISAM DEFAULT CHARSET=utf8 ;

 CREATE TABLE `fktable2` (
  `id` decimal(10,0) default NULL,
  `name` varchar(100) NOT NULL default '',
  PRIMARY KEY  (`name`),
  UNIQUE KEY `id` (`id`)
) ENGINE=MyISAM DEFAULT CHARSET=utf8 ;

insert into datatable values(1,2,NOW());
insert into datatable values(3,4,NOW());
insert into fktable1 values(1,'A'),(2,'B'),(3,'C'),(4,'D'),(5,'E');
insert into fktable2 values(1,'A'),(2,'B'),(3,'C'),(4,'D'),(5,'E');

Aleksey,

Thanks very much for your assistance.  I have tried 4.1.13 and still have the same problem.  I ran your test and it also worked as desired (Using Where; Using Index) so I suspect that this has something to do with the amount of data in the database.  The database with Indexes is nearly 2GB (and growing) - assuming this is ok, please let me know how / where to upload it.

Regards,

Perry.

If 2GB is too large, I can make the files available on our website for you to download.  If that is preferred, let me know and I'll arrange a private login id for you.

I would prefer to write small script for populate tables with random values. When i have some results with this script I put them here.

Aleksey,

Thanks for your help.  We have migrated the database to MS-SQL and the performance has improved substantially - I am lowering the severity of the ticket since I now have a workaround (albeit not the type of workaround that I had hoped for).  We would still like to use MySQL so any on-going efforts to help address the problem won't be in vain. 

I'm wondering, we have quite a large index key cache set up for the database - is there any chance that this could be affecting the decision of the optimizer?  It may be a bit of a stretch but perhaps it is choosing to read all of the extra rows of data to have the values cached for subsequent queries and since the value of the cache is so large it thinks that is what we want.  I guess I can always try reducing the size of the cache to see what happens but I thought I'd throw that out there...

Please let me know how you make out with your testing.

Regards,

Perry.

Never mind, I managed to address the problem myself.  Performance is back to where it should be and while not quite as good as SQL Server it is well beyond acceptable.  Thanks anyway for what little help you tried to provide.

Perry, dare I ask what you did to work around this issue?  I have observed it on a system with only 16M allocated to key_buffer.

As far as I can tell, it is still not fixed, even in version 6 (supported by bug 19548).

I have even encountered situations where highly useful compound indexes are entirely ignored in favor of less useful single-column indexes, and forcing the use of the compound index causes the query optimiser to down tools and refuse to use any index at all.

I tried adjusting max_seeks_for_key in light of this but it made no difference.

This issue is a real barrier to application scalability.