MySQL Bugs: #35136: Obviously slower plan is choosed at searching uses LIKE '%xxx%' clause

Bug #35136	Obviously slower plan is choosed at searching uses LIKE '%xxx%' clause
Submitted:	7 Mar 2008 8:34	Modified:	21 Jul 2008 11:36
Reporter:	Yasufumi Kinoshita	Email Updates:
Status:	Duplicate	Impact on me:	None
Category:	MySQL Server: Optimizer	Severity:	S3 (Non-critical)
Version:	5.0.54	OS:	Any
Assigned to:		CPU Architecture:	Any

Description:
Obviously slower plan is choosed when we use LIKE '%xxx%' clause at join.

The slower plan seems to be not scalable for InnoDB.
(If heavy load with many CPUs, may cause contentions of Adaptive Hash)

In the following case, we shouldn't use the index 'i_i_title'.

How to repeat:
> gunzip -c dump.sql.gz | mysql [database] -uxxxx

mysql> explain SELECT STRAIGHT_JOIN i_id, i_title, a_fname, a_lname FROM item, author WHERE i_title LIKE '%BABABAOGBABAIN%' AND i_a_id = a_id ORDER BY i_title ASC LIMIT 50;
+----+-------------+--------+--------+---------------+---------+---------+------------------+------+-----------------------------+
| id | select_type | table  | type   | possible_keys | key     | key_len | ref              | rows | Extra                       |
+----+-------------+--------+--------+---------------+---------+---------+------------------+------+-----------------------------+
|  1 | SIMPLE      | item   | ALL    | i_i_a_id      | NULL    | NULL    | NULL             | 9290 | Using where; Using filesort |
|  1 | SIMPLE      | author | eq_ref | PRIMARY       | PRIMARY | 4       | test.item.i_a_id |    1 |                             |
+----+-------------+--------+--------+---------------+---------+---------+------------------+------+-----------------------------+
2 rows in set (0.00 sec)

mysql> SELECT STRAIGHT_JOIN i_id, i_title, a_fname, a_lname FROM item, author WHERE i_title LIKE '%BABABAOGBABAIN%' AND i_a_id = a_id ORDER BY i_title ASC LIMIT 50;
+------+-------------------------------------------------------------+-------------------+----------------------+
| i_id | i_title                                                     | a_fname           | a_lname              |
+------+-------------------------------------------------------------+-------------------+----------------------+
| 5092 | BABABAOGBABAINBrown, various years in the chief years come  | NG1EzauBY9fSJlv   | BABABABAULATSE       |
| 1008 | BABABAOGBABAINReports go. Available,                        | EXRfBj3y1D9FAiHv  | BABABABAATALRE       |
| 3404 | BABABAOGBABAINTonnes carry. Early,                          | WefSTBz8kEoGEOx   | BABABABARENGRE       |
| 6626 | National fields develop. BABABAOGBABAINNational, poor ways  | DrvqRpEXX         | BABABABAULINAL       |
| 3647 | Strong, chief BABABAOGBABAINyears can see in the different, | ZgauFWEIAAuaFsHEi | BABABABAATRERI1      |
| 7688 | True, free BABABAOGBABAIN friends say on the new, new       | k1EdQAnpwADa      | BABABABAATSENG4snu0I |
+------+-------------------------------------------------------------+-------------------+----------------------+
6 rows in set (0.01 sec)

mysql> create index i_i_title on item (i_title asc);
Query OK, 10000 rows affected (1.18 sec)
Records: 10000  Duplicates: 0  Warnings: 0

mysql> explain SELECT STRAIGHT_JOIN i_id, i_title, a_fname, a_lname FROM item, author WHERE i_title LIKE '%BABABAOGBABAIN%' AND i_a_id = a_id ORDER BY i_title ASC LIMIT 50;
+----+-------------+--------+--------+---------------+-----------+---------+------------------+------+-------------+
| id | select_type | table  | type   | possible_keys | key       | key_len | ref              | rows | Extra       |
+----+-------------+--------+--------+---------------+-----------+---------+------------------+------+-------------+
|  1 | SIMPLE      | item   | index  | i_i_a_id      | i_i_title | 63      | NULL             | 9929 | Using where |
|  1 | SIMPLE      | author | eq_ref | PRIMARY       | PRIMARY   | 4       | test.item.i_a_id |    1 |             |
+----+-------------+--------+--------+---------------+-----------+---------+------------------+------+-------------+
2 rows in set (0.00 sec)

mysql> SELECT STRAIGHT_JOIN i_id, i_title, a_fname, a_lname FROM item, author WHERE i_title LIKE '%BABABAOGBABAIN%' AND i_a_id = a_id ORDER BY i_title ASC LIMIT 50;
+------+-------------------------------------------------------------+-------------------+----------------------+
| i_id | i_title                                                     | a_fname           | a_lname              |
+------+-------------------------------------------------------------+-------------------+----------------------+
| 5092 | BABABAOGBABAINBrown, various years in the chief years come  | NG1EzauBY9fSJlv   | BABABABAULATSE       |
| 1008 | BABABAOGBABAINReports go. Available,                        | EXRfBj3y1D9FAiHv  | BABABABAATALRE       |
| 3404 | BABABAOGBABAINTonnes carry. Early,                          | WefSTBz8kEoGEOx   | BABABABARENGRE       |
| 6626 | National fields develop. BABABAOGBABAINNational, poor ways  | DrvqRpEXX         | BABABABAULINAL       |
| 3647 | Strong, chief BABABAOGBABAINyears can see in the different, | ZgauFWEIAAuaFsHEi | BABABABAATRERI1      |
| 7688 | True, free BABABAOGBABAIN friends say on the new, new       | k1EdQAnpwADa      | BABABABAATSENG4snu0I |
+------+-------------------------------------------------------------+-------------------+----------------------+
6 rows in set (0.05 sec)

Suggested fix:
We shouldn't use the index 'i_i_title', in this case.

Sorry,
ftp://ftp.mysql.com/pub/mysql/upload/
seems not to accept file larger than 256KB..

Thank you for a problem report. Can you upload some smaller test case or just SHOW CREATE TABLE and SHOW TABLE STATUS results for the tables involved? Why do you think index should NOT be used?

Yasufumi,

I do agree that optimizer choosed a bit slower plan, for this (!) particular case. But I do not know if any statistics exist that will allow optimizer to take into account the fact that only 6 rows have BABABAOGBABAIN substring somewhere in the middle of column's value.

I'd like to see a complete test case to check and/or provide some workarounds.

mysql> show create table author\G
*************************** 1. row ***************************
       Table: author
Create Table: CREATE TABLE `author` (
  `a_id` int(11) NOT NULL,
  `a_fname` varchar(20) default NULL,
  `a_lname` varchar(20) default NULL,
  `a_mname` varchar(20) default NULL,
  `a_dob` date default NULL,
  `a_bio` text,
  PRIMARY KEY  (`a_id`)
) ENGINE=InnoDB DEFAULT CHARSET=latin1
1 row in set (0.00 sec)

mysql> show create table item\G
*************************** 1. row ***************************
       Table: item
Create Table: CREATE TABLE `item` (
  `i_id` int(11) NOT NULL default '0',
  `i_title` varchar(60) default NULL,
  `i_a_id` int(11) default NULL,
  `i_pub_date` date default NULL,
  `i_publisher` varchar(60) default NULL,
  `i_subject` varchar(60) default NULL,
  `i_desc` text,
  `i_related1` int(11) default NULL,
  `i_related2` int(11) default NULL,
  `i_related3` int(11) default NULL,
  `i_related4` int(11) default NULL,
  `i_related5` int(11) default NULL,
  `i_thumbnail` int(9) default NULL,
  `i_image` int(9) default NULL,
  `i_srp` decimal(17,2) default NULL,
  `i_cost` decimal(17,2) default NULL,
  `i_avail` date default NULL,
  `i_stock` smallint(5) default NULL,
  `i_isbn` varchar(13) default NULL,
  `i_page` smallint(5) default NULL,
  `i_backing` varchar(15) default NULL,
  `i_dimensions` varchar(25) default NULL,
  PRIMARY KEY  (`i_id`),
  KEY `i_i_subject` (`i_subject`),
  KEY `i_i_a_id` (`i_a_id`),
  CONSTRAINT `item_ibfk_1` FOREIGN KEY (`i_a_id`) REFERENCES `author` (`a_id`)
) ENGINE=InnoDB DEFAULT CHARSET=latin1
1 row in set (0.00 sec)

mysql> select count(a_id) from author;
+-------------+
| count(a_id) |
+-------------+
|        2500 |
+-------------+
1 row in set (0.08 sec)

mysql> select count(i_id) from item;
+-------------+
| count(i_id) |
+-------------+
|       10000 |
+-------------+
1 row in set (0.16 sec)

<<result of DBT-1 (I've fixed bugs and tuned)>>

server: Xeon E5310(1.6GHz:quad core) x 2

./dbdriver --access_direct --dbhost susesv --item_count 10000 --customer_count 576000 --emulated_users 10 --rampup_rate 10 --think_time 0 --duration 120

1.without index i_i_title on item (i_title asc)

Interaction                 %%  Avg. Response Time (s)
Admin Confirm            0.09                   0.002
Admin Request            0.09                   0.001
Best Sellers             5.04                   0.009
Buy Confirm              1.18                   0.014
Buy Request              2.56                   0.005
Customer Registration    2.94                   0.000
Home                    16.16                   0.002
New Products             5.01                   0.009
Order Display            0.68                   0.010
Order Inquiry            0.77                   0.001
Product Detail          16.93                   0.001
Search Request          19.95                   0.000
Search Results          16.95                   0.011
Shopping Cart           11.66                   0.003

2546.1 bogotransactions per second
2.0 minute duration
total bogotransactions 305533
total errors 0

2.with index i_i_title on item (i_title asc)

Interaction                 %%  Avg. Response Time (s)
Admin Confirm            0.09                   0.002
Admin Request            0.10                   0.001
Best Sellers             5.07                   0.014
Buy Confirm              1.25                   0.012
Buy Request              2.66                   0.006
Customer Registration    3.07                   0.000
Home                    16.02                   0.001
New Products             4.91                   0.014
Order Display            0.62                   0.010
Order Inquiry            0.72                   0.001
Product Detail          16.85                   0.001
Search Request          20.01                   0.000
Search Results          17.04                   0.072
Shopping Cart           11.59                   0.003

666.7 bogotransactions per second  /*less than 1/4!*/
2.0 minute duration
total bogotransactions 86666
total errors 0

----

The query is used at "Search Results" interaction.
It needs data in columns not in the index (i_a_id), and needs whole of record anyway.
And, the both of tables are entirely on buffer_pool.
So, using the secondary index is just only a waste.
Moreover, it seems to cause heavy use of Adaptive Hash Index and contentions, and worsen CPU-scalability...

Some DBT-1 sets for MySQL include the index. (But I don't know its reason..)
(e.g. http://www.ipa.go.jp/software/open/forum/development/download/051115/dbt1-v2.1-MySQL-ODBC-...)

We should recognize that MySQL is falsely charged with low performance and scalability of DBT-1 by this slower plan.

The whole of the results

Attachment: bad_indexes_effect.pdf (application/pdf, text), 12.49 KiB.

This looks like a (more complicated?) kind of Bug #36259. Please, check.

I think you should be right.
The "ORDER BY" clause seems to affect the plan too strongly.

mysql> select version();
+---------------------+
| version()           |
+---------------------+
| 5.1.26-rc-community |
+---------------------+
1 row in set (0.00 sec)

mysql> explain SELECT STRAIGHT_JOIN i_id, i_title, a_fname, a_lname FROM item, author WHERE i_title LIKE '%BABABAOGBABAIN%' AND i_a_id = a_id ORDER BY i_title ASC LIMIT 50;
+----+-------------+--------+--------+---------------+---------+---------+------------------+-------+-----------------------------+
| id | select_type | table  | type   | possible_keys | key     | key_len | ref              | rows  | Extra                       |
+----+-------------+--------+--------+---------------+---------+---------+------------------+-------+-----------------------------+
|  1 | SIMPLE      | item   | ALL    | i_i_a_id      | NULL    | NULL    | NULL             | 10014 | Using where; Using filesort |
|  1 | SIMPLE      | author | eq_ref | PRIMARY       | PRIMARY | 4       | test.item.i_a_id |     1 |                             |
+----+-------------+--------+--------+---------------+---------+---------+------------------+-------+-----------------------------+
2 rows in set (0.00 sec)

mysql> explain SELECT STRAIGHT_JOIN i_id, i_title, a_fname, a_lname FROM item, author WHERE i_title LIKE '%BABABAOGBABAIN%' AND i_a_id = a_id LIMIT 50;
+----+-------------+--------+--------+---------------+---------+---------+------------------+-------+-------------+
| id | select_type | table  | type   | possible_keys | key     | key_len | ref              | rows  | Extra       |
+----+-------------+--------+--------+---------------+---------+---------+------------------+-------+-------------+
|  1 | SIMPLE      | item   | ALL    | i_i_a_id      | NULL    | NULL    | NULL             | 10014 | Using where |
|  1 | SIMPLE      | author | eq_ref | PRIMARY       | PRIMARY | 4       | test.item.i_a_id |     1 |             |
+----+-------------+--------+--------+---------------+---------+---------+------------------+-------+-------------+
2 rows in set (0.00 sec)

mysql> create index i_i_title on item (i_title asc);
Query OK, 10000 rows affected (1.73 sec)
Records: 10000  Duplicates: 0  Warnings: 0

mysql> explain SELECT STRAIGHT_JOIN i_id, i_title, a_fname, a_lname FROM item, author WHERE i_title LIKE '%BABABAOGBABAIN%' AND i_a_id = a_id ORDER BY i_title ASC LIMIT 50;
+----+-------------+--------+--------+---------------+-----------+---------+------------------+------+-------------+
| id | select_type | table  | type   | possible_keys | key       | key_len | ref              | rows | Extra       |
+----+-------------+--------+--------+---------------+-----------+---------+------------------+------+-------------+
|  1 | SIMPLE      | item   | index  | i_i_a_id      | i_i_title | 63      | NULL             |   50 | Using where |
|  1 | SIMPLE      | author | eq_ref | PRIMARY       | PRIMARY   | 4       | test.item.i_a_id |    1 |             |
+----+-------------+--------+--------+---------------+-----------+---------+------------------+------+-------------+
2 rows in set (0.00 sec)

mysql> explain SELECT STRAIGHT_JOIN i_id, i_title, a_fname, a_lname FROM item, author WHERE i_title LIKE '%BABABAOGBABAIN%' AND i_a_id = a_id LIMIT 50;
+----+-------------+--------+--------+---------------+---------+---------+------------------+-------+-------------+
| id | select_type | table  | type   | possible_keys | key     | key_len | ref              | rows  | Extra       |
+----+-------------+--------+--------+---------------+---------+---------+------------------+-------+-------------+
|  1 | SIMPLE      | item   | ALL    | i_i_a_id      | NULL    | NULL    | NULL             | 10167 | Using where |
|  1 | SIMPLE      | author | eq_ref | PRIMARY       | PRIMARY | 4       | test.item.i_a_id |     1 |             |
+----+-------------+--------+--------+---------------+---------+---------+------------------+-------+-------------+
2 rows in set (0.00 sec)

I think this is a duplicate of Bug #36259.