Bug #35922 Equity propagation does not work properly w functions
Submitted: 9 Apr 2008 5:23 Modified: 11 Apr 2008 13:08
Reporter: Peter Zaitsev (Basic Quality Contributor) Email Updates:
Status: Not a Bug Impact on me:
None 
Category:MySQL Server: Optimizer Severity:S3 (Non-critical)
Version:5.0.54, 5.0.60 OS:Any
Assigned to: CPU Architecture:Any
Tags: qc

[9 Apr 2008 5:23] Peter Zaitsev
Description:
Equity propagation does not work as you would expect causing poor pan to be selected:

CREATE TABLE `p` (
  `id` bigint(20) unsigned NOT NULL auto_increment,
  `url` varchar(1000) NOT NULL,
  `url_crc` int(10) unsigned NOT NULL,
  PRIMARY KEY  (`id`),
  KEY `url_crc` (`url_crc`)
) ENGINE=MyISAM AUTO_INCREMENT=67464 DEFAULT CHARSET=latin1;

mysql> select * from p limit 5;
+----+---------------------------------+------------+
| id | url                             | url_crc    |
+----+---------------------------------+------------+
|  1 | http://www.pollenation.net/     | 1776188156 |
|  2 | http://www.nnseek.com/cat/ibm/  | 2644613628 |
|  3 | http://www.nnseek.com/cat/thur/ |  665366524 |
|  4 | http://www.utoronto.ca          | 3747297788 |
|  5 | http://labs.digg.com/arc        | 2866438908 |
+----+---------------------------------+------------+
5 rows in set (0.00 sec)

mysql> explain select * from p where url="http://www.pollenation.net/" and url_crc=crc32(url);
+----+-------------+-------+------+---------------+------+---------+------+-------+-------------+
| id | select_type | table | type | possible_keys | key  | key_len | ref  | rows  | Extra       |
+----+-------------+-------+------+---------------+------+---------+------+-------+-------------+
|  1 | SIMPLE      | p     | ALL  | NULL          | NULL | NULL    | NULL | 67463 | Using where |
+----+-------------+-------+------+---------------+------+---------+------+-------+-------------+
1 row in set (0.00 sec)

How to repeat:
See above.

If you use textual url second time it works OK:

mysql> explain select * from p where url="http://www.pollenation.net/" and url_crc=crc32("http://www.pollenation.net/");
+----+-------------+-------+------+---------------+---------+---------+-------+------+-------------+
| id | select_type | table | type | possible_keys | key     | key_len | ref   | rows | Extra       |
+----+-------------+-------+------+---------------+---------+---------+-------+------+-------------+
|  1 | SIMPLE      | p     | ref  | url_crc       | url_crc | 4       | const |    1 | Using where |
+----+-------------+-------+------+---------------+---------+---------+-------+------+-------------+
1 row in set (0.00 sec)
[9 Apr 2008 6:11] Valeriy Kravchuk
Thank you for a problem report. Verified just as described with latest 5.0.60-BK:

openxs@suse:~/dbs/5.0> 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.60 Source distribution

Type 'help;' or '\h' for help. Type '\c' to clear the buffer.

mysql> CREATE TABLE `p` (
    ->   `id` bigint(20) unsigned NOT NULL auto_increment,
    ->   `url` varchar(1000) NOT NULL,
    ->   `url_crc` int(10) unsigned NOT NULL,
    ->   PRIMARY KEY  (`id`),
    ->   KEY `url_crc` (`url_crc`)
    -> ) ENGINE=MyISAM AUTO_INCREMENT=67464 DEFAULT CHARSET=latin1;
Query OK, 0 rows affected (0.01 sec)

mysql> insert into p values (1, 'http://www.pollenation.net/', 0);
Query OK, 1 row affected (0.00 sec)

mysql> insert into p values (2, 'http://www.nnseek.com/cat/ibm/', 0);
Query OK, 1 row affected (0.00 sec)

mysql> insert into p values (3, 'http://www.nnseek.com/cat/thur/', 0);
Query OK, 1 row affected (0.00 sec)

mysql> insert into p values (4, 'http://www.utoronto.ca', 0);
Query OK, 1 row affected (0.01 sec)

mysql> insert into p values (5, 'http://labs.digg.com/arc', 0);
Query OK, 1 row affected (0.00 sec)

mysql> update p set url_crc=crc32(url);
Query OK, 5 rows affected (0.01 sec)
Rows matched: 5  Changed: 5  Warnings: 0

mysql> select * from p limit 5;
+----+---------------------------------+------------+
| id | url                             | url_crc    |
+----+---------------------------------+------------+
|  1 | http://www.pollenation.net/     | 1776188156 |
|  2 | http://www.nnseek.com/cat/ibm/  | 2644613628 |
|  3 | http://www.nnseek.com/cat/thur/ |  665366524 |
|  4 | http://www.utoronto.ca          | 3747297788 |
|  5 | http://labs.digg.com/arc        | 2866438908 |
+----+---------------------------------+------------+
5 rows in set (0.00 sec)

mysql> explain select * from p where url="http://www.pollenation.net/" and
    -> url_crc=crc32(url);
+----+-------------+-------+------+---------------+------+---------+------+------+-------------+
| id | select_type | table | type | possible_keys | key  | key_len | ref  | rows | Extra       |
+----+-------------+-------+------+---------------+------+---------+------+------+-------------+
|  1 | SIMPLE      | p     | ALL  | NULL          | NULL | NULL    | NULL |    5 | Using where |
+----+-------------+-------+------+---------------+------+---------+------+------+-------------+
1 row in set (0.02 sec)

mysql> explain select * from p where url="http://www.pollenation.net/" and url_crc=crc32('http://www.pollenation.net');
+----+-------------+-------+------+---------------+---------+---------+-------+------+-------------+
| id | select_type | table | type | possible_keys | key     | key_len | ref   | rows | Extra       |
+----+-------------+-------+------+---------------+---------+---------+-------+------+-------------+
|  1 | SIMPLE      | p     | ref  | url_crc       | url_crc | 4       | const |    1 | Using where |
+----+-------------+-------+------+---------------+---------+---------+-------+------+-------------+
1 row in set (0.00 sec)

mysql> explain extended select * from p where url="http://www.pollenation.net/" and url_crc=crc32(url);
+----+-------------+-------+------+---------------+------+---------+------+------+-------------+
| id | select_type | table | type | possible_keys | key  | key_len | ref  | rows | Extra       |
+----+-------------+-------+------+---------------+------+---------+------+------+-------------+
|  1 | SIMPLE      | p     | ALL  | NULL          | NULL | NULL    | NULL |    5 | Using where |
+----+-------------+-------+------+---------------+------+---------+------+------+-------------+
1 row in set, 1 warning (0.00 sec)

mysql> show warnings\G
*************************** 1. row ***************************
  Level: Note
   Code: 1003
Message: select `test`.`p`.`id` AS `id`,`test`.`p`.`url` AS `url`,`test`.`p`.`url_crc` AS `url_crc` from `test`.`p` where ((`test`.`p`.`url` = _latin1'http://www.pollenation.net/') and (`test`.`p`.`url_crc` = crc32(`test`.`p`.`url`)))
1 row in set (0.00 sec)

Adding more rows and analysing table does not help optimizer to make any other plan:

mysql> insert into p(url, url_crc) select url, url_crc from p where url not like '%poll%';
Query OK, 4 rows affected (0.00 sec)
Records: 4  Duplicates: 0  Warnings: 0

mysql> insert into p(url, url_crc) select url, url_crc from p where url not like '%poll%';
Query OK, 8 rows affected (0.00 sec)
Records: 8  Duplicates: 0  Warnings: 0

...

mysql> insert into p(url, url_crc) select url, url_crc from p where url not like '%poll%';
Query OK, 2048 rows affected (0.04 sec)
Records: 2048  Duplicates: 0  Warnings: 0

mysql> analyze table p;
+--------+---------+----------+----------+
| Table  | Op      | Msg_type | Msg_text |
+--------+---------+----------+----------+
| test.p | analyze | status   | OK       |
+--------+---------+----------+----------+
1 row in set (0.00 sec)

mysql> explain select * from p where url="http://www.pollenation.net/" and url_crc=crc32(url)\G
*************************** 1. row ***************************
           id: 1
  select_type: SIMPLE
        table: p
         type: ALL
possible_keys: NULL
          key: NULL
      key_len: NULL
          ref: NULL
         rows: 4097
        Extra: Using where
1 row in set (0.00 sec)
[11 Apr 2008 13:08] Sergei Golubchik
It is not as easy as it looks. In general from A=B does not follow that f(A)=f(B). And in this particular case it is certainly false:

Using your testcase...

CREATE TABLE `p` (
  `id` bigint(20) unsigned NOT NULL auto_increment,
  `url` varchar(1000) NOT NULL,
  `url_crc` int(10) unsigned NOT NULL,
  PRIMARY KEY  (`id`),
  KEY `url_crc` (`url_crc`)
) ENGINE=MyISAM AUTO_INCREMENT=67464 DEFAULT CHARSET=latin1;
insert into p values (1, 'http://www.pollenation.net/', 0);
insert into p values (2, 'HTTP://WWW.POLLENATION.NET/', 0);
update p set url_crc=crc32(url);

mysql> select * from p where url="http://www.pollenation.net/" and url_crc=crc32(url);
+----+-----------------------------+------------+
| id | url                         | url_crc    |
+----+-----------------------------+------------+
|  1 | http://www.pollenation.net/ | 1776188156 | 
|  2 | HTTP://WWW.POLLENATION.NET/ | 4216947324 | 
+----+-----------------------------+------------+
2 rows in set (0.00 sec)

mysql> select * from p where url="http://www.pollenation.net/" and url_crc=crc32('http://www.pollenation.net/');
+----+-----------------------------+------------+
| id | url                         | url_crc    |
+----+-----------------------------+------------+
|  1 | http://www.pollenation.net/ | 1776188156 | 
+----+-----------------------------+------------+
1 row in set (0.00 sec)