MySQL Bugs: #57030: 'BETWEEN' evaluation is incorrect

Bug #57030	'BETWEEN' evaluation is incorrect
Submitted:	27 Sep 2010 8:28	Modified:	28 Feb 2011 20:52
Reporter:	Ole John Aske	Email Updates:
Status:	Closed	Impact on me:	None
Category:	MySQL Server: Optimizer	Severity:	S2 (Serious)
Version:	5.0.91, 5.1.52, 5.5.7, 5.6.99	OS:	Any
Assigned to:	Ole John Aske	CPU Architecture:	Any

Description:
A WHERE condition containing a BETWEEN predicate term may return incorrect result as described in 'How to repeat'

Explaining the incorrect query :

mysql> explain
    -> SELECT * FROM t1
    ->  WHERE 10 BETWEEN 10 AND i4;
+----+-------------+-------+-------+---------------+-------+---------+-------+------+-------+
| id | select_type | table | type  | possible_keys | key   | key_len | ref   | rows | Extra |
+----+-------------+-------+-------+---------------+-------+---------+-------+------+-------+
|  1 | SIMPLE      | t1    | const | i4_uq         | i4_uq | 5       | const |    1 |       |
+----+-------------+-------+-------+---------------+-------+---------+-------+------+-------+
1 row in set (0.00 sec)

A 'const' table access is used for t1 which is incorrect! It might indicate that the first part of the predicate '10 BETWEEN 10 ...' fools the optimizer to handle it as a const table access.

How to repeat:
create table t1(pk int primary key, i4 int);
create unique index i4_uq on t1(i4);

insert into t1 values (1,10), (2,20), (3,30);

Return the (incorrect) result set 

explain
SELECT * FROM t1
 WHERE 10 BETWEEN 10 AND i4;
+----+------+
| pk | i4   |
+----+------+
|  1 |   10 |
+----+------+
1 row in set (0.00 sec)

Then, apply the BETWEEN rewrite rule:

 'X BETWEEN <low> AND <high>' -> 'X >= <low> AND X <= <high>'

explain
SELECT * FROM t1
 WHERE 10 >= 10 AND 10 <= i4;

+----+------+
| pk | i4   |
+----+------+
|  1 |   10 |
|  2 |   20 |
|  3 |   30 |
+----+------+
3 rows in set (0.00 sec)

Which is correct

This bug report is similar to bug#54802: 'NOT BETWEEN' evaluation is incorrect.

Verified just as described, also - with 5.0.91:

C:\Program Files\MySQL\MySQL Server 5.1\bin>mysql -uroot -proot -P3308 test
Welcome to the MySQL monitor.  Commands end with ; or \g.
Your MySQL connection id is 5
Server version: 5.0.91-community-nt MySQL Community Edition (GPL)

Copyright (c) 2000, 2010, Oracle and/or its affiliates. All rights reserved.
This software comes with ABSOLUTELY NO WARRANTY. This is free software,
and you are welcome to modify and redistribute it under the GPL v2 license

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

mysql> create table t1(pk int primary key, i4 int);
Query OK, 0 rows affected (0.89 sec)

mysql> create unique index i4_uq on t1(i4);
Query OK, 0 rows affected (0.59 sec)
Records: 0  Duplicates: 0  Warnings: 0

mysql>
mysql> insert into t1 values (1,10), (2,20), (3,30);
Query OK, 3 rows affected (0.06 sec)
Records: 3  Duplicates: 0  Warnings: 0

mysql> explain
    -> SELECT * FROM t1
    ->  WHERE 10 BETWEEN 10 AND i4;
+----+-------------+-------+-------+---------------+-------+---------+-------+--
----+-------------+
| id | select_type | table | type  | possible_keys | key   | key_len | ref   | r
ows | Extra       |
+----+-------------+-------+-------+---------------+-------+---------+-------+--
----+-------------+
|  1 | SIMPLE      | t1    | const | i4_uq         | i4_uq | 5       | const |
  1 | Using index |
+----+-------------+-------+-------+---------------+-------+---------+-------+--
----+-------------+
1 row in set (0.11 sec)

mysql> SELECT * FROM t1
    ->  WHERE 10 BETWEEN 10 AND i4;
+----+------+
| pk | i4   |
+----+------+
|  1 |   10 |
+----+------+
1 row in set (0.00 sec)

mysql> SELECT * FROM t1
    ->  WHERE 10 >= 10 AND 10 <= i4;
+----+------+
| pk | i4   |
+----+------+
|  1 |   10 |
|  2 |   20 |
|  3 |   30 |
+----+------+
3 rows in set (0.05 sec)

mysql> explain SELECT * FROM t1
    ->  WHERE 10 >= 10 AND 10 <= i4;
+----+-------------+-------+-------+---------------+-------+---------+------+---
---+--------------------------+
| id | select_type | table | type  | possible_keys | key   | key_len | ref  | ro
ws | Extra                    |
+----+-------------+-------+-------+---------------+-------+---------+------+---
---+--------------------------+
|  1 | SIMPLE      | t1    | index | i4_uq         | i4_uq | 5       | NULL |
 3 | Using where; Using index |
+----+-------------+-------+-------+---------------+-------+---------+------+---
---+--------------------------+
1 row in set (0.03 sec)

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/125940

3477 Ole John Aske	2010-12-03
      Fix for bug#57030: 'BETWEEN' evaluation is incorrect
      
      Root cause for this bug is that the optimizer try to detect & optimize the special case:
        '<field> BETWEEN c1 AND c1' and handle this as the condition '<field> = c1'
      
      This was implemented inside add_key_field(.. *field, *value[]...) which assumed
      field to refer key Field, and value[] to refer a [low...high] constant pair.
      value[0] and value[1] was then compared for equality.
      
      In a 'normal' BETWEEN condition of the form '<field> BETWEEN val1 and val2' the
      BETWEEN operation is represented with an argementlist containing the
      values [<field>, val1, val2] - add_key_field() is then called with 
      parameters field= <field>, *value=val1.
      
      However, if the BETWEEN predicate specified:
      
      1)  '<const1> BETWEEN <const2> AND <field> 
      
      the 'field' and 'value' arguments to add_key_field() had to be swapped. This was implemented
      by trying the cheat add_key_field() to handle it like:
      
      2) '<const1> GE <const2> AND <const1> LE <field>'
      
      As we didn't really replace the BETWEEN operation with 'ge' and 'le', 
      add_key_field() still handled it as a 'BETWEEN' and compared the (swapped) 
      arguments <const1> and <const2> for equality. If they was equal, the 
      condition 1) was incorrectly 'optimized' to:
      
      3) '<field> EQ <const1>'
      
      This fix uses the 'num_values' argument to detect the cases where the BETWEEN
      should not be interpreted as a BETWEEN anymore. if 'num_values < 2' it has logicaly
      been transformed to a GE / LE.

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/125941

3477 Ole John Aske	2010-12-03
      Alternative fix for bug#57030: 'BETWEEN' evaluation is incorrect
      
      This is a more extensive, but IMHO a more correct fix for handling BETWEEN optimization.
      It introduce some refactoring where a BETWEEN condition is rewritten 
      to a 'GE AND LE' condition inside add_key_fields() and optimized as such.
      
      The special condition 'field' BETWEEN <c1> and <c1> is still detected and rewritten
      to 'field' EQ <c1>. 
      
      ALternative (shorter and more hacky) fix is at: http://lists.mysql.com/commits/125940
      
      ..................
      
      Root cause for this bug is that the optimizer try to detect & optimize the special case:
        '<field> BETWEEN c1 AND c1' and handle this as the condition '<field> = c1'
      
      This was implemented inside add_key_field(.. *field, *value[]...) which assumed
      field to refer key Field, and value[] to refer a [low...high] constant pair.
      value[0] and value[1] was then compared for equality.
      
      In a 'normal' BETWEEN condition of the form '<field> BETWEEN val1 and val2' the
      BETWEEN operation is represented with an argementlist containing the
      values [<field>, val1, val2] - add_key_field() is then called with 
      parameters field= <field>, *value=val1.
      
      However, if the BETWEEN predicate specified:
      
      1)  '<const1> BETWEEN <const2> AND <field> 
      
      the 'field' and 'value' arguments to add_key_field() had to be swapped. This was implemented
      by trying the cheat add_key_field() to handle it like:
      
      2) '<const1> GE <const2> AND <const1> LE <field>'
      
      As we didn't really replace the BETWEEN operation with 'ge' and 'le', 
      add_key_field() still handled it as a 'BETWEEN' and compared the (swapped) 
      arguments <const1> and <const2> for equality. If they was equal, the 
      condition 1) was incorrectly 'optimized' to:
      
      3) '<field> EQ <const1>'
      
      This fix replace the BETWEEN with a 'GE AND LE' pair and let add_key_field() extract
      any key equalities / ranges from from this transformed condition.

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/125946

3386 Ole John Aske	2010-12-03
      SPJ-scan-scan: Cherry picked fix for bug#57030 as this was a RQG test showstopper
      
      NOTE: There are two alternative fixes available for this bug. I have picked 
      the smalles, but most hacky of of these fixes.
      
      Might replace - and hopefully will - with the other fix if reviwers 
      find that one better .

Updated 'Versions' to also include 5.5.x and 5.6.x

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/127372

3529 Ole John Aske	2010-12-21
      Updated fix after review for bug#57030 'BETWEEN' evaluation is incorrect'
      
      Root cause for this bug is that the optimizer try to detect&  optimize the special case:
      '<field>  BETWEEN c1 AND c1' and handle this as the condition '<field>  = c1'
      
      This was implemented inside add_key_field(.. *field, *value[]...) which assumed
      field to refer key Field, and value[] to refer a [low...high] constant pair.
      value[0] and value[1] was then compared for equality.
      
      In a 'normal' BETWEEN condition of the form '<field>  BETWEEN val1 and val2' the
      BETWEEN operation is represented with an argementlist containing the
      values [<field>, val1, val2] - add_key_field() is then called with
      parameters field=<field>, *value=val1.
      
      However, if the BETWEEN predicate specified:
      
        1)  '<const1>  BETWEEN<const2>  AND<field>
      
      the 'field' and 'value' arguments to add_key_field() had to be swapped. This was implemented
      by trying to cheat add_key_field() to handle it like:
      
         2) '<const1>  GE<const2>  AND<const1>  LE<field>'
      
      As we didn't really replace the BETWEEN operation with 'ge' and 'le',
      add_key_field() still handled it as a 'BETWEEN' and compared the (swapped)
      arguments<const1>  and<const2>  for equality. If they was equal, the
      condition 1) was incorrectly 'optimized' to:
      
         3) '<field>  EQ<const1>'
      
      This fix moves this optimization of '<field>  BETWEEN c1 AND c1' into
      add_key_fields() which then calls add_key_equal_fields() to collect 
      key equality / comparison for the key fields in the BETWEEN condition.
      
      Compared to first commit, a few new testcases has also been added as
      suggested by Evgeny Potemkin.

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/127421

3529 Ole John Aske	2010-12-21
      Another updated fix for bug#57030 after review by Evgeny Potemkin ('BETWEEN' evaluation is incorrect')
      
      Root cause for this bug is that the optimizer try to detect&  optimize the special case:
      '<field>  BETWEEN c1 AND c1' and handle this as the condition '<field>  = c1'
      
      This was implemented inside add_key_field(.. *field, *value[]...) which assumed
      field to refer key Field, and value[] to refer a [low...high] constant pair.
      value[0] and value[1] was then compared for equality.
      
      In a 'normal' BETWEEN condition of the form '<field>  BETWEEN val1 and val2' the
      BETWEEN operation is represented with an argementlist containing the
      values [<field>, val1, val2] - add_key_field() is then called with
      parameters field=<field>, *value=val1.
      
      However, if the BETWEEN predicate specified:
      
        1)  '<const1>  BETWEEN<const2>  AND<field>
      
      the 'field' and 'value' arguments to add_key_field() had to be swapped. This was implemented
      by trying to cheat add_key_field() to handle it like:
      
         2) '<const1>  GE<const2>  AND<const1>  LE<field>'
      
      As we didn't really replace the BETWEEN operation with 'ge' and 'le',
      add_key_field() still handled it as a 'BETWEEN' and compared the (swapped)
      arguments<const1>  and<const2>  for equality. If they was equal, the
      condition 1) was incorrectly 'optimized' to:
      
         3) '<field>  EQ<const1>'
      
      This fix moves this optimization of '<field>  BETWEEN c1 AND c1' into
      add_key_fields() which then calls add_key_equal_fields() to collect 
      key equality / comparison for the key fields in the BETWEEN condition.
      
      Compared to first commit, a few new testcases has also been added as
      suggested by Evgeny Potemkin.

Pushed into mysql-5.1-telco-7.0 5.1.51-ndb-7.0.21 (revid:ole.john.aske@oracle.com-20110114150809-tm8ue7igyvq6dnyj) (version source revid:ole.john.aske@oracle.com-20110114150809-tm8ue7igyvq6dnyj) (merge vers: 5.1.51-ndb-7.0.21) (pib:24)

Fix has been backported to mysql-5.1-telco-7.x. Still awaiting retriage to decide if it will also be pushed to 5.5+.

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/130119

3571 Ole John Aske	2011-02-01
      Fix for bug#57030: ('BETWEEN' evaluation is incorrect')
                  
      Root cause for this bug is that the optimizer try to detect&
      optimize the special case:
            
      '<field>  BETWEEN c1 AND c1' and handle this as the condition '<field>  = c1'
                  
      This was implemented inside add_key_field(.. *field, *value[]...)
      which assumed field to refer key Field, and value[] to refer a [low...high]
      constant pair. value[0] and value[1] was then compared for equality.
                  
      In a 'normal' BETWEEN condition of the form '<field>  BETWEEN val1 and val2' the
      BETWEEN operation is represented with an argementlist containing the
      values [<field>, val1, val2] - add_key_field() is then called with
      parameters field=<field>, *value=val1.
                  
      However, if the BETWEEN predicate specified:
                  
       1)  '<const1>  BETWEEN<const2>  AND<field>
                  
      the 'field' and 'value' arguments to add_key_field() had to be swapped.
      This was implemented by trying to cheat add_key_field() to handle it like:
                  
       2) '<const1>  GE<const2>  AND<const1>  LE<field>'
                  
      As we didn't really replace the BETWEEN operation with 'ge' and 'le',
      add_key_field() still handled it as a 'BETWEEN' and compared the (swapped)
      arguments<const1>  and<const2>  for equality. If they was equal, the
      condition 1) was incorrectly 'optimized' to:
                  
       3) '<field>  EQ <const1>'
                  
      This fix moves this optimization of '<field>  BETWEEN c1 AND c1' into
      add_key_fields() which then calls add_key_equal_fields() to collect 
      key equality / comparison for the key fields in the BETWEEN condition.

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/130121

3584 Ole John Aske	2011-02-01 [merge]
      Merge of fix for bug#57030

Pushed into mysql-trunk 5.6.2 (revid:ole.john.aske@oracle.com-20110201124739-xmivchewz2vqc04b) (version source revid:ole.john.aske@oracle.com-20110201124739-xmivchewz2vqc04b) (merge vers: 5.6.2) (pib:24)

Pushed into mysql-5.5 5.5.10 (revid:ole.john.aske@oracle.com-20110201122328-hdrlhd5cgbxq3zgd) (version source revid:ole.john.aske@oracle.com-20110201122328-hdrlhd5cgbxq3zgd) (merge vers: 5.5.10) (pib:24)

Pushed into mysql-5.1 5.1.56 (revid:ole.john.aske@oracle.com-20110201122016-8ngficfn0a1358hw) (version source revid:ole.john.aske@oracle.com-20110201122016-8ngficfn0a1358hw) (merge vers: 5.1.56) (pib:24)

Pushed into mysql-5.1, mysql-5.5 and mysql-trunk.
(In addition to prev. push to 'telco' branches'

Noted in 5.1.56, 5.5.10 changelogs.

The expression const1 BETWEEN const2 AND field was optimized
incorrectly and produced incorrect results. 

CHANGESET - http://lists.mysql.com/commits/130121