Bug #22753 No equality propagation into BETWEEN predicates
Submitted: 27 Sep 2006 18:41 Modified: 26 Oct 2006 3:38
Reporter: Igor Babaev Email Updates:
Status: Closed Impact on me:
None 
Category:MySQL Server: Optimizer Severity:S5 (Performance)
Version:5.0.26-BK OS:Any (all)
Assigned to: Igor Babaev CPU Architecture:Any

[27 Sep 2006 18:41] Igor Babaev
Description:
There is no equality propagation anymore into BETWEEN predicates.
This problem appeared after the patch for bug #21698.
Apparently the patch was incomplete.

How to repeat:
We can see the problem from the following example:

mysql> CREATE TABLE t1 (pk varchar(10) PRIMARY KEY, fk varchar(16));
Query OK, 0 rows affected (0.07 sec)

mysql> CREATE TABLE t2 (pk varchar(16) PRIMARY KEY, fk varchar(10));
Query OK, 0 rows affected (0.05 sec)

mysql>
mysql> INSERT INTO t1 VALUES
    ->   ('d','dddd'), ('i','iii'), ('a','aa'), ('b','bb'), ('g','gg'),
    ->   ('e','eee'), ('c','cccc'), ('h','hhh'), ('j','jjj'), ('f','fff');
Query OK, 10 rows affected (0.00 sec)
Records: 10  Duplicates: 0  Warnings: 0

mysql> INSERT INTO t2 VALUES
    ->   ('jjj', 'j'), ('cc','c'), ('ccc','c'), ('aaa', 'a'), ('jjjj','j'),
    ->   ('hhh','h'), ('gg','g'), ('fff','f'), ('ee','e'), ('ffff','f'),
    ->   ('bbb','b'), ('ff','f'), ('cccc','c'), ('dddd','d'), ('jj','j'),
    ->   ('aaaa','a'), ('bb','b'), ('eeee','e'), ('aa','a'), ('hh','h');
Query OK, 20 rows affected (0.00 sec)
Records: 20  Duplicates: 0  Warnings: 0

For the tree before the patch for bug #21698
(ChangeSet@1.2216.35.4, 2006-08-31 07:27:34-07:00, igor@rurik.mysql.com +4 -0
  Fixed bug #16249: different results for a range with an without index
  when a range condition use an invalid DATETIME constant.)
we had:

mysql> EXPLAIN SELECT t2.*
    ->   FROM t1 JOIN t2 ON t2.fk=t1.pk
    ->     WHERE t2.fk BETWEEN 'a' AND 'c' AND t2.pk=t1.fk;
+----+-------------+-------+-------+---------------+---------+---------+------------+------+-------------+
| id | select_type | table | type  | possible_keys | key     | key_len | ref        | rows | Extra       |
+----+-------------+-------+-------+---------------+---------+---------+------------+------+-------------+
|  1 | SIMPLE      | t1    | range | PRIMARY       | PRIMARY | 12      | NULL       |    3 | Using where |
|  1 | SIMPLE      | t2    | ref   | PRIMARY       | PRIMARY | 18      | test.t1.fk |    1 | Using where |
+----+-------------+-------+-------+---------------+---------+---------+------------+------+-------------+
2 rows in set (0.05 sec)

For the current tree 
(ChangeSet@1.2277.1.1, 2006-09-25 06:46:15-07:00, igor@rurik.mysql.com +3 -0
  Merge rurik.mysql.com:/home/igor/mysql-4.1-opt
  into  rurik.mysql.com:/home/igor/mysql-5.0-opt
  MERGE: 1.1616.2144.220)
we have:

mysql> EXPLAIN SELECT t2.*
    ->   FROM t1 JOIN t2 ON t2.fk=t1.pk
    ->     WHERE t2.fk BETWEEN 'a' AND 'c' AND t2.pk=t1.fk;
+----+-------------+-------+------+---------------+---------+---------+------------+------+-------------+
| id | select_type | table | type | possible_keys | key     | key_len | ref        | rows | Extra       |
+----+-------------+-------+------+---------------+---------+---------+------------+------+-------------+
|  1 | SIMPLE      | t1    | ALL  | PRIMARY       | NULL    | NULL    | NULL       |   10 |             |
|  1 | SIMPLE      | t2    | ref  | PRIMARY       | PRIMARY | 18      | test.t1.fk |    1 | Using where |
+----+-------------+-------+------+---------------+---------+---------+------------+------+-------------+
2 rows in set (0.00 sec)

The second execution plan is worse than the first one.
[29 Sep 2006 14:26] Igor Babaev
The same problem exists for IN predicates.
[29 Sep 2006 14:43] Bugs System
A patch for this bug has been committed. After review, it may
be pushed to the relevant source trees for release in the next
version. You can access the patch from:

  http://lists.mysql.com/commits/12849

ChangeSet@1.2280, 2006-09-29 07:43:25-07:00, igor@rurik.mysql.com +3 -0
  Fixed bug #22753.
  After the patch for big 21698 equality propagation stopped
  working for BETWEEN and IN predicates with STRING arguments.
  This changeset completes the solution of the above patch.
[21 Oct 2006 9:15] Georgi Kodinov
Pushed in 5.0.27/5.1.13-beta
[26 Oct 2006 3:38] Paul DuBois
Noted in 5.0.30, 5.1.13 changelogs.