MySQL Bugs: #43600: Wrong query result if pushed index condition returns 2

Bug #43600	Wrong query result if pushed index condition returns 2
Submitted:	12 Mar 2009 15:16	Modified:	23 Nov 2010 3:34
Reporter:	Sergey Petrunya	Email Updates:
Status:	Closed	Impact on me:	None
Category:	MySQL Server: Optimizer	Severity:	S3 (Non-critical)
Version:	6.0, 5.4	OS:	Any
Assigned to:	Evgeny Potemkin	CPU Architecture:	Any
Tags:	ICP, index condition pushdown, regression

Description:
A query which uses index condition pushdown may a wrong result if the pushed index condition evaluates to "2". (Yes normal predicates evaluate to 1, 0, or NULL but we need to process odd/C-like predicates also)

How to repeat:
Run this:

CREATE TABLE t1 (
  a int NOT NULL
);

CREATE TABLE t2 (
  a int NOT NULL,
  b int NOT NULL,
  filler char(100) DEFAULT NULL,
  KEY a (a,b)
);

insert into t1 values (0),(1),(2),(3),(4);

insert into t2 select A.a + 10 *B.a, 1, 'filler' from t1 A, t1 B;

--echo This should use index condition pushdown for t2
explain select * from t1, t2 where t2.a=t1.a and t2.b + 1;

--echo The following should not produce an empty resultset:
select * from t1, t2 where t2.a=t1.a and t2.b + 1;
select * from t1, t2 ignore index(a) where t2.a=t1.a and t2.b + 1;

And get this:

mysql> explain select * from t1, t2 where t2.a=t1.a and t2.b + 1;
+----+-------------+-------+------+---------------+------+---------+-----------+------+-----------------------+
| id | select_type | table | type | possible_keys | key  | key_len | ref       | rows | Extra                 |
+----+-------------+-------+------+---------------+------+---------+-----------+------+-----------------------+
|  1 | SIMPLE      | t1    | ALL  | NULL          | NULL | NULL    | NULL      |    5 |                       | 
|  1 | SIMPLE      | t2    | ref  | a             | a    | 4       | k333.t1.a |    1 | Using index condition | 
+----+-------------+-------+------+---------------+------+---------+-----------+------+-----------------------+
2 rows in set (0.01 sec)

mysql> select * from t1, t2 where t2.a=t1.a and t2.b + 1;
Empty set (0.03 sec)

mysql> select * from t1, t2 ignore index(a) where t2.a=t1.a and t2.b + 1;
+---+---+---+--------+
| a | a | b | filler |
+---+---+---+--------+
| 0 | 0 | 1 | filler | 
| 1 | 1 | 1 | filler | 
| 2 | 2 | 1 | filler | 
| 3 | 3 | 1 | filler | 
| 4 | 4 | 1 | filler | 
+---+---+---+--------+
5 rows in set (0.01 sec)

Suggested fix:
(Discussed with Guilhem on IRC/Email)

Thank you for the bug report. Verified as described:

mysql 6.0 >
mysql 6.0 > -- echo The following should not produce an empty resultset:
mysql 6.0 > select * from t1, t2 where t2.a=t1.a and t2.b + 1;
Empty set (0.00 sec)

mysql 6.0 > select * from t1, t2 ignore index(a) where t2.a=t1.a and t2.b + 1;
+---+---+---+--------+
| a | a | b | filler |
+---+---+---+--------+
| 0 | 0 | 1 | filler |
| 1 | 1 | 1 | filler |
| 2 | 2 | 1 | filler |
| 3 | 3 | 1 | filler |
| 4 | 4 | 1 | filler |
+---+---+---+--------+
5 rows in set (0.02 sec)

I will fix MyISAM+Maria

Had to focus on something else, didn't fix MyISAM+Maria.
The one who fixes this, could also implement a change which SergeyP and I discussed: at least in MyISAM and Maria, the function returns my_bool but can return 2; my_bool is not meant for 2 it's meant for true/false. The return type should be changed to a new enum:
There are actually three values:
1=ICP_MATCH     - index tuple satisfies the pushed index condition (the engine
              should fetch and return the record)
0=ICP_NO_MATCH  - index tuple doesn't satisfy the pushed index condition (the 
              engine should discard the tuple and go to the next one)
2=ICP_OUT_OF_RANGE - index tuple is out range that we're scanning, e.g. this 
                 if we're scanning "t.key BETWEEN 10 AND 20" and got a 
                 "t.key=21" tuple (the engine should stop scanning and return 
                 HA_ERR_END_OF_FILE right away).
And this change should be done in all engines which have this problem.

To clarify the fixes to do: in ha_myisam.cc there is:
my_bool index_cond_func_myisam(void *arg)
{
  ha_myisam *h= (ha_myisam*)arg;
  if (h->end_range)
  {
    if (h->compare_key2(h->end_range) > 0)
      return 2; /* caller should return HA_ERR_END_OF_FILE already */
  }
  return (my_bool)h->pushed_idx_cond->val_int();
}
First problem: quoting SergeyP about this line:
  return (my_bool)h->pushed_idx_cond->val_int();
<quote>Ooops. If val_int() returns 2 then we'll get wrong results. This line should be:
   return test(h->pushed_idx_cond->val_int())
</quote> ("wrong results" is showed by the testcase in this bug report).
Second problem: the function's return type is my_bool (so, the function should return TRUE/FALSE, true/false, or 0/1), but actually there is a "return 2"! the function actually returns one of 0/1/2 (0 and 1 will be returned by the "test(...val_int())", so its return type should be int; SergeyP and I agreed that it would even be better if it returned a value from this new enum: ICP_MATCH=1, ICP_NO_MATCH=0, ICP_OUT_OF_RANGE=2. And SergeyP said this enum should be visible to all engines, and all engines having an index cond pushdown function could be made to use this enum; for example index_cond_func_innodb has "first problem" and "second problem" and should be fixed too.

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

2825 Evgeny Potemkin	2009-07-28
      Bug#43600: Incorrect type conversion caused wrong result.
      
      The index_cond_func_xxx function is used to evaluate pushed index condition or
      return an error if the tuple being checked is out of range.
      And there are two bugs in it:
      1) The function result type is my_bool, but actually it can return 3
         values - TRUE/FALSE/OUT OF RANGE.
      2) The type of the pushed condition evaluation is converted to my_bool, but
      since the evaluation result isn't checked it's possible to return values
      other that 0/1, thus falsely returning OUT OF RANGE.
      
      The fix for this bug introduces the enum for the index_cond_func_xxx's
      result called ICP_RESULT. It has three values:
      
      0=ICP_NO_MATCH  - index tuple doesn't satisfy the pushed index condition (the 
                    engine should discard the tuple and go to the next one)
      1=ICP_MATCH     - index tuple satisfies the pushed index condition (the engine
                    should fetch and return the record)
      2=ICP_OUT_OF_RANGE - index tuple is out range that we're scanning, e.g. this 
                       if we're scanning "t.key BETWEEN 10 AND 20" and got a 
                       "t.key=21" tuple (the engine should stop scanning and return 
                       HA_ERR_END_OF_FILE right away).
      
      The index_cond_func_myisam and index_cond_func_innodb functions now checking
      the pushed condition evaluation result, and making sure that only 0/1 are
      returned.
     @ include/my_handler.h
        Bug#43600: Incorrect type conversion caused wrong result.
        The enum for the index_cond_func_xxx's result is introduced.
        It's called ICP_RESULT.
     @ mysql-test/include/mix1.inc
        A test case added for the bug#43600.
     @ mysql-test/r/innodb_mysql.result
        A test case added for the bug#43600.
     @ mysql-test/r/myisam.result
        A test case added for the bug#43600.
     @ mysql-test/t/myisam.test
        A test case added for the bug#43600.
     @ storage/innobase/handler/ha_innodb.cc
        Bug#43600: Incorrect type conversion caused wrong result.
        The result type of the index_cond_func_innodb function
        is changed to uint and the result of the pushed condition
        evaluation now is checked to make sure that only 0/1 are returned.
     @ storage/innobase/include/row0mysql.h
        Bug#43600: Incorrect type conversion caused wrong result.
        The result type of the index_cond_func_innodb function
        is changed to uint.
     @ storage/myisam/ha_myisam.cc
        Bug#43600: Incorrect type conversion caused wrong result.
        The index_cond_func_myisam function now checks the pushed
        condition evaluation result, and makes sure that only 0/1 are
        returned.
     @ storage/myisam/ha_myisam.h
        Bug#43600: Incorrect type conversion caused wrong result.
        Result type of the index_cond_func_xxx function is changed to the
        ICP_RESULT enum.
     @ storage/myisam/myisamdef.h
        Bug#43600: Incorrect type conversion caused wrong result.
        Result type of the index_cond_func_xxx function is changed to the
        ICP_RESULT enum.

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

2825 Evgeny Potemkin	2009-07-30
      Bug#43600: Incorrect type conversion caused wrong result.
      
      The index_cond_func_xxx function is used to evaluate pushed index condition or
      return an error if the tuple being checked is out of range.
      And there are two bugs in it:
      1) The function result type is my_bool, but actually it can return 3
         values - TRUE/FALSE/OUT OF RANGE.
      2) The type of the pushed condition evaluation is converted to my_bool, but
      since the evaluation result isn't checked it's possible to return values
      other that 0/1, thus falsely returning OUT OF RANGE.
      
      The fix for this bug introduces the enum for the index_cond_func_xxx's
      result called ICP_RESULT. It has three values:
      
      0=ICP_NO_MATCH  - index tuple doesn't satisfy the pushed index condition (the 
                    engine should discard the tuple and go to the next one)
      1=ICP_MATCH     - index tuple satisfies the pushed index condition (the engine
                    should fetch and return the record)
      2=ICP_OUT_OF_RANGE - index tuple is out range that we're scanning, e.g. this 
                       if we're scanning "t.key BETWEEN 10 AND 20" and got a 
                       "t.key=21" tuple (the engine should stop scanning and return 
                       HA_ERR_END_OF_FILE right away).
      
      The index_cond_func_myisam and index_cond_func_innodb functions now checking
      the pushed condition evaluation result, and making sure that only 0/1 are
      returned.
     @ include/my_handler.h
        Bug#43600: Incorrect type conversion caused wrong result.
        The enum for the index_cond_func_xxx's result is introduced.
        It's called ICP_RESULT.
     @ mysql-test/include/mix1.inc
        A test case added for the bug#43600.
     @ mysql-test/r/innodb_mysql.result
        A test case added for the bug#43600.
     @ mysql-test/r/myisam.result
        A test case added for the bug#43600.
     @ mysql-test/t/myisam.test
        A test case added for the bug#43600.
     @ storage/innobase/handler/ha_innodb.cc
        Bug#43600: Incorrect type conversion caused wrong result.
        The result type of the index_cond_func_innodb function
        is changed to uint and the result of the pushed condition
        evaluation now is checked to make sure that only 0/1 are returned.
     @ storage/innobase/include/row0mysql.h
        Bug#43600: Incorrect type conversion caused wrong result.
        The result type of the index_cond_func_innodb function
        is changed to uint.
     @ storage/myisam/ha_myisam.cc
        Bug#43600: Incorrect type conversion caused wrong result.
        The index_cond_func_myisam function now checks the pushed
        condition evaluation result, and makes sure that only 0/1 are
        returned.
     @ storage/myisam/ha_myisam.h
        Bug#43600: Incorrect type conversion caused wrong result.
        Result type of the index_cond_func_xxx function is changed to the
        ICP_RESULT enum.
     @ storage/myisam/myisamdef.h
        Bug#43600: Incorrect type conversion caused wrong result.
        Result type of the index_cond_func_xxx function is changed to the
        ICP_RESULT enum.

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

2863 Evgeny Potemkin	2009-09-02 [merge]
      Auto-merged fix for the bug#43600.

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

2807 Evgeny Potemkin	2009-09-02 [merge]
      Auto-merged fix for the bug#43600.

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

3587 Evgeny Potemkin	2009-09-08 [merge]
      Auto-merged fix for the bug#43600.

Pushed into 5.4.4-alpha (revid:alik@sun.com-20090914155317-m1g9wodmndzdj4l1) (version source revid:alik@sun.com-20090914155317-m1g9wodmndzdj4l1) (merge vers: 5.4.4-alpha) (pib:11)

Pushed into 5.4.4-alpha (revid:alik@sun.com-20090915134838-5nj3ycjfsqc2vr2f) (version source revid:epotemkin@mysql.com-20090902125107-9koiubdmafvnrhqb) (merge vers: 5.4.4-alpha) (pib:11)

Noted in 5.4.4 changelog.

Queries executed using index condition pushdown could return
incorrect results because the condition could evaluate to an
unexpected result.

Pushed into 6.0.14-alpha (revid:alik@sun.com-20090929093622-1mooerbh12e97zux) (version source revid:alik@sun.com-20090923103200-kyo2bakdo6tfb2fb) (merge vers: 6.0.14-alpha) (pib:11)

Noted in 6.0.14 changelog.

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

3171 Evgeny Potemkin	2010-05-12
      Bug#43600: Incorrect type conversion caused wrong result.
      
      The index_cond_func_xxx function is used to evaluate pushed index condition or
      return an error if the tuple being checked is out of range.
      And there are two bugs in it:
      1) The function result type is my_bool, but actually it can return 3
         values - TRUE/FALSE/OUT OF RANGE.
      2) The type of the pushed condition evaluation is converted to my_bool, but
      since the evaluation result isn't checked it's possible to return values
      other that 0/1, thus falsely returning OUT OF RANGE.
      
      The fix for this bug introduces the enum for the index_cond_func_xxx's
      result called ICP_RESULT. It has three values:
      
      0=ICP_NO_MATCH - index tuple doesn't satisfy the pushed index condition (the 
                    engine should discard the tuple and go to the next one)
      1=ICP_MATCH - index tuple satisfies the pushed index condition (the engine
                    should fetch and return the record)
      2=ICP_OUT_OF_RANGE - index tuple is out range that we're scanning, e.g. this 
                       if we're scanning "t.key BETWEEN 10 AND 20" and got a 
                       "t.key=21" tuple (the engine should stop scanning and return 
                       HA_ERR_END_OF_FILE right away).
      
      The index_cond_func_myisam and index_cond_func_innodb functions now checking
      the pushed condition evaluation result, and making sure that only 0/1 are
      returned.
      Original revid:epotemkin@mysql.com-20090730151527-19pdqet083a9uc25
     @ include/my_handler.h
        Bug#43600: Incorrect type conversion caused wrong result.
        The enum for the index_cond_func_xxx's result is introduced.
        It's called ICP_RESULT.
     @ mysql-test/include/mix1.inc
        A test case added for the bug#43600.
     @ mysql-test/r/innodb_mysql.result
        A test case added for the bug#43600.
     @ mysql-test/r/myisam.result
        A test case added for the bug#43600.
     @ mysql-test/t/myisam.test
        A test case added for the bug#43600.
     @ storage/innobase/handler/ha_innodb.cc
        Bug#43600: Incorrect type conversion caused wrong result.
        The result type of the index_cond_func_innodb function
        is changed to uint and the result of the pushed condition
        evaluation now is checked to make sure that only 0/1 are returned.
     @ storage/innobase/include/row0mysql.h
        Bug#43600: Incorrect type conversion caused wrong result.
        The result type of the index_cond_func_innodb function
        is changed to uint.
     @ storage/myisam/ha_myisam.cc
        Bug#43600: Incorrect type conversion caused wrong result.
        The index_cond_func_myisam function now checks the pushed
        condition evaluation result, and makes sure that only 0/1 are
        returned.
     @ storage/myisam/ha_myisam.h
        Bug#43600: Incorrect type conversion caused wrong result.
        Result type of the index_cond_func_xxx function is changed to the
        ICP_RESULT enum.
     @ storage/myisam/myisamdef.h
        Bug#43600: Incorrect type conversion caused wrong result.
        Result type of the index_cond_func_xxx function is changed to the
        ICP_RESULT enum.

Pushed into mysql-next-mr (revid:alik@sun.com-20100816062819-bluwgdq8q4xysmlg) (version source revid:alik@sun.com-20100816062612-enatdwnv809iw3s9) (pib:20)

Pushed into mysql-trunk 5.6.99-m5 (revid:alexander.nozdrin@oracle.com-20101113155825-czmva9kg4n31anmu) (version source revid:vasil.dimov@oracle.com-20100629074804-359l9m9gniauxr94) (merge vers: 5.6.99-m4) (pib:21)

Bug does not appear in any released 5.6.x version. No 5.6.1 changelog entry needed.