Bug #47217 Simple Inner join gives wrong result when order by is used
Submitted: 9 Sep 2009 11:16 Modified: 22 Nov 2010 0:33
Reporter: Bernt Marius Johnsen Email Updates:
Status: Closed Impact on me:
None 
Category:MySQL Server: Optimizer Severity:S2 (Serious)
Version:6.0 OS:Any
Assigned to: Evgeny Potemkin
Tags: regression
Triage: Triaged: D2 (Serious)

[9 Sep 2009 11:16] Bernt Marius Johnsen
Description:
Consider the following SQL:

create table t1 (pk int, v varchar(2), primary key(pk));
create index ix1 on t1(v);
create table t2 (pk int, v varchar(2), primary key(pk));
create index ix2 on t2(v);

insert into t1 values (10,'a'),(11,NULL);
insert into t2 values (10,NULL);

select * from t1 join t2 on t1.v = t2.v order by 1;
select * from t1 join t2 on t1.v = t2.v;

The first select gives 1 row (when t1.v and t2.v are both NULL), while the second select gives 0 rows, which is correct:

mysql> select * from t1 join t2 on t1.v = t2.v order by 1;
+----+------+----+------+
| pk | v    | pk | v    |
+----+------+----+------+
| 11 | NULL | 10 | NULL |
+----+------+----+------+
1 row in set (0.00 sec)

mysql> select * from t1 join t2 on t1.v = t2.v;
Empty set (0.00 sec)

How to repeat:
Se description
[9 Sep 2009 11:43] Valerii Kravchuk
Thank you for the problem report. Do you have semijoin=on in optimizer_switch? Please, check.
[9 Sep 2009 11:59] Bernt Marius Johnsen
Optimizer_switch:

firstmatch=on,index_merge=on,index_merge_union=on,index_merge_sort_union=on,index_merge_intersection=on,loosescan=on,materialization=on,semijoin=on
[9 Sep 2009 12:02] Valerii Kravchuk
Please, try with semijoin=off. Looks related to http://bugs.mysql.com/bug.php?id=46733 etc.
[9 Sep 2009 12:10] Bernt Marius Johnsen
No effect:

mysql> show variables like 'optimizer_switch';
+------------------+------------------------------------------------------------------------------------------------------------------------------------------------------+
| Variable_name    | Value                                                                                                                                                |
+------------------+------------------------------------------------------------------------------------------------------------------------------------------------------+
| optimizer_switch | firstmatch=on,index_merge=on,index_merge_union=on,index_merge_sort_union=on,index_merge_intersection=on,loosescan=on,materialization=on,semijoin=off |
+------------------+------------------------------------------------------------------------------------------------------------------------------------------------------+
1 row in set (0.00 sec)

mysql> select * from t1 join t2 on t1.v = t2.v order by 1;
+----+------+----+------+
| pk | v    | pk | v    |
+----+------+----+------+
| 11 | NULL | 10 | NULL |
+----+------+----+------+
1 row in set (0.00 sec)

mysql> select * from t1 join t2 on t1.v = t2.v;
Empty set (0.01 sec)
[9 Sep 2009 13:48] Valerii Kravchuk
Verified just as described. optimizer_switch settings do not influence wrong results here. Versions 5.1.x and 5.2.3 (next) do not have this bug, so it is a regression.
[16 Sep 2009 8:17] Øystein Grøvlen
The following query that should be equivalent, gives correct result:

select * from t1 join t2 using(v) order by 1;

Plans are different, though:
mysql> explain select * from t1 join t2 on t1.v = t2.v order by 1\G
*************************** 1. row ***************************
           id: 1
  select_type: SIMPLE
        table: t2
         type: system
possible_keys: ix2
          key: NULL
      key_len: NULL
          ref: NULL
         rows: 1
        Extra: Using filesort
*************************** 2. row ***************************
           id: 1
  select_type: SIMPLE
        table: t1
         type: ref
possible_keys: ix1
          key: ix1
      key_len: 5
          ref: const
         rows: 1
        Extra: Using where
2 rows in set (0.00 sec)

mysql> explain select * from t1 join t2 using(v) order by 1\G
*************************** 1. row ***************************
           id: 1
  select_type: SIMPLE
        table: t2
         type: system
possible_keys: ix2
          key: NULL
      key_len: NULL
          ref: NULL
         rows: 1
        Extra:
*************************** 2. row ***************************
           id: 1
  select_type: SIMPLE
        table: t1
         type: ref
possible_keys: ix1
          key: ix1
      key_len: 5
          ref: const
         rows: 1
        Extra:
2 rows in set (0.00 sec)
[17 Sep 2009 9:18] Øystein Grøvlen
Turning on where-tracing shows a difference between 5.1 and 6.0:

6.0:
WHERE:(original) (`test`.`t1`.`v` = `test`.`t2`.`v`)

WHERE:(after equal_items) multiple equal(`test`.`t1`.`v`, `test`.`t2`.`v`)

WHERE:(after const change) multiple equal(`test`.`t1`.`v`, `test`.`t2`.`v`)

WHERE:(after substitute_best_equal) (`test`.`t1`.`v` = '')

WHERE:(t2) ('' is not null)

5.1:
WHERE:(original) (`test`.`t1`.`v` = `test`.`t2`.`v`)

WHERE:(after equal_items) multiple equal(`test`.`t1`.`v`, `test`.`t2`.`v`)

WHERE:(after const change) multiple equal(`test`.`t1`.`v`, `test`.`t2`.`v`)

WHERE:(after substitute_best_equal) (`test`.`t1`.`v` = '')

WHERE:(t2) ('' is not null)

WHERE:(t1) (`test`.`t1`.`v` = '')

WHERE:(t1) (`test`.`t1`.`v` = '')
[18 Sep 2009 13:32] Øystein Grøvlen
The main difference between 5.1 and 6.0 execution is the selection predicate used during filesort of t1.  

In 5.1 the following predicate is used:
  ((`test`.`t1`.`v` <=> '') and (`test`.`t1`.`v` = ''))

In 6.0 the predicate is:
  ((`test`.`t1`.`v` <=> ''))

It seems the <=> comparison (Item_func_equal) regards NULL values to be equal, while the other (Item_func_eq) does not.  Hence, 5.1 will skip rows where v is null, 6.0 will not.

The cause of this difference seems to be different results from test_if_ref as when called by make_cond_for_table.  Next step is to try to understand why.
[18 Sep 2009 14:25] Øystein Grøvlen
The different behavior in 5.1 and 6.0 is related to the following changed code in part_of_refkey:

      if (field->eq(key_part->field) &&
-	  !(key_part->key_part_flag & (HA_PART_KEY_SEG | HA_NULL_PART)))
+	  !(key_part->key_part_flag & HA_PART_KEY_SEG))
	return table->reginfo.join_tab->ref.items[part];

In 5.1, HA_NULL_PART is set and no ref_item is returned so that test_if_ref does not find references that can be eliminated.  In 6.0, HA_NULL_PART is neither set nor tested for.
[21 Sep 2009 7:46] Øystein Grøvlen
Correction to earlier statement about the variant with using clause. The using statement that is equivalent to the problem statement is:

  select * from t1 join t2 using(v) order by 2;

(Since order of columns is different with using clause).

This statement has the same plan and the same wrong result as the problem statement.
[21 Sep 2009 20:01] Guilhem Bichot
For reference, HA_NULL_PART is also met in BUG#46743; but not all findings of BUG#46743 may apply here, for example the present bug already existed before the revision which introduced BUG#46743 (sp1r-gkodinov/kgeorge@magare.gmz-20071121140553-31481)
[21 Sep 2009 20:44] Guilhem Bichot
For reference, HA_NULL_PART is also met in BUG#46743; but not all findings of BUG#46743 may apply here, for example the present bug already existed before the revision which introduced BUG#46743 (sp1r-gkodinov/kgeorge@magare.gmz-20071121140553-31481)
[23 Sep 2009 6:26] Øystein Grøvlen
I (with help from Gleb) have confirmed that this bug was introduced in revision sp1r-sergefp@mysql.com-20070309210824-13110.  Log message for that changeset:

WL#2474 "Multi Range Read: Change the default MRR implementation to implement new MRR interface"
WL#2475 "Batched range read functions for MyISAM/InnoDb"
"Index condition pushdown for MyISAM/InnoDB"
combined into one cset
[24 Sep 2009 10:58] Øystein Grøvlen
As far as I understand the query plan, it handles t2 as a const table
with a single row and replaces t2.v with NULL in the join condition
and uses this for selection during filesort of t1.  However, the
equality operator used in that condition regards NULL values as equal.
(This is where 5.1 differ)

I had expected that add_not_null_conds() would save the day by putting
a not null condition on t1.v, but it turns out that it only puts such
a condition on t2.v.  Since t2 is a const table, this condition is
never evaluated.

I see several ways this problem could be solved:

1. Choose another plan for such queries.  In this particular scenario
   there are indexes on both v columns that could be used.

2. Handle t2 as a zero row const table. Since the single t2 row has
   null for t2.v, we know it should not be part of the join result.

3. Use another comparison operator for the filesort select
   condition. (Item_func_eq instead of Item_func_equal)

4. Reintroduce 5.1 behavior by setting and checking the HA_NULL_PART
   flag of key_part.

5. Make add_not_null_conds() set a not null condition on t1.
   Currently, not null conditions are only set on columns referred to
   by non-const tables.
[24 Sep 2009 13:02] 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/84495

2838 oystein.grovlen@sun.com	2009-09-24
      Bug#47217 Simple Inner join gives wrong result when order by is used
      
      Problem: Join matches on NULL values when filesort select predicate contain
      NULL value from const table propagation.
      
      Solution: When creating a condition for a const reference, make sure to use
      an equal comparison that does not consider NULL values to be equal.
     @ mysql-test/r/join_optimizer.result
        Result for new test case
     @ mysql-test/t/join_optimizer.test
        Add test case for Bug#47217
     @ sql/sql_select.cc
        When creating a condition for a const reference, use Item_func_eq for 
        comparison if reference should not match null values.  This operator not 
        consider NULL values to be equal.
[24 Sep 2009 13:05] Øystein Grøvlen
Committed patch chooses alternative 3 from the list above:  Use another comparison operator for the filesort select condition.  If the key reference should reject null values, Item_func_eq is used instead of Item_func_equal from the comparison.
[6 Oct 2009 12:20] Evgeny Potemkin
The problem is that optimizer chooses wrong execution path.
Will come up with a solution later.
[23 Oct 2009 9:30] Øystein Grøvlen
If we "manually eliminate" the const table from the original query, we get the following query:

select * from t1 where v=NULL order by 1;

This query has the following query plan:
*************************** 1. row ***************************
           id: 1
  select_type: SIMPLE
        table: t1
         type: ref
possible_keys: ix1
          key: ix1
      key_len: 5
          ref: const
         rows: 1
        Extra: Using index condition; Using where; Using filesort

The plan is basically the same as for the original query except for "Using index condition".  This reason for this difference is that for the single table query, test_if_ref() does not cause the equality condition to be removed.

Looking at test_if_ref(), it seems its intention is to handle equality for NULL constants differently that other constants:

      if (right_item->const_item() && !(right_item->is_null())) 

However, this code does not handle constant propagation for fields since the handling of Item_field objects are short-cutted earlier in the function.
Removing this short-cut for fields of const tables as follows, fixes the bug:

     {
       right_item= right_item->real_item();
       if (right_item->type() == Item::FIELD_ITEM)
-	return (field->eq_def(((Item_field *) right_item)->field));
+      {
+        Field *right_field= ((Item_field *)right_item)->field;
+        if (!right_field->table->const_table) // const items are handled below
+          return (field->eq_def(right_field));
+      }
       /* remove equalities injected by IN->EXISTS transformation */
       else if (right_item->type() == Item::CACHE_ITEM)
         return ((Item_cache *)right_item)->eq_def (field);
       if (right_item->const_item() && !(right_item->is_null())) 
       {
[23 Oct 2009 10:56] 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/87920

3667 oystein.grovlen@sun.com	2009-10-23
      Bug#47217 Simple Inner join gives wrong result when order by is used
      
      Problem: Join matches on NULL values when filesort select predicate contain
      NULL value from const table propagation.
      
      Solution: test_in_ref() should not eliminate equality conditions on const table fields 
      fields that are NULL.  Keeping the equality condition makes sure that NULL values
      are not condisered equal when joining on a NULL key.
     @ mysql-test/r/join_optimizer.result
        Result for new test case
     @ mysql-test/r/subselect4.result
        Update a few query plans to reflect that equality conditions are no longer eliminated for NULL fields of constant tables.
     @ mysql-test/t/join_optimizer.test
        Add test case for Bug#47217
     @ sql/sql_select.cc
        It seems that the intention in test_if_ref() is to handle equality for NULL constants differently from other constants.  However, constant propagation for fields is handled differently since the handling of Item_field objects are short-cutted. Removing this short-cut for fields of const tables and letting them be handled the same way as other const items, causes the equality condition to be kept for NULL fields in const tables.  This ensures
        that NULL values are correctly handled with respect to equality.
[11 Nov 2009 13:20] 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/90088

3703 oystein.grovlen@sun.com	2009-11-11
      Bug#47217 Simple Inner join gives wrong result when order by is used
      
      Problem: Join matches on NULL values when filesort select predicate contain
      NULL value from const table propagation.
      
      Solution: When creating a quick select for a constant reference, check whether 
      the ref contain null constants for key parts where NULLs should not match.
      If so, create an object of the new class QUICK_EMPTY_SELECT instead of an
      ordinary QUICK_SELECT_RANGE. QUICK_EMPTY_SELECT represent a quick select with 0
      rows.
     @ mysql-test/r/join_optimizer.result
        Result for new test case
     @ mysql-test/t/join_optimizer.test
        Add test case for Bug#47217
     @ sql/opt_range.cc
        get_quick_select_for_ref now returns pointer to a QUICK_EMPTY_SELECT object if ref could not possibly match any rows. That is, if part of the ref key is a NULL constant, and NULL should not match other NULLs for this part.
        
        Initialize members of QUICK_SELECT_I in constructor to make sure unitialized members will not create surprises for subclasses.
     @ sql/opt_range.h
        Added new class QUICK_EMPTY_SELECT as a subclass of QUICK_SELECT_I.
        It represents a quick select with no rows.
        
        Change *get_quick_select_for_ref to return QUICK_SELECT_I*.  This way, it
        may return a pointer to either a QUICK_RANGE_SELECT object or a
        QUICK_EMPTY_SELECT object.
     @ sql/sql_select.h
        Add a method impossible_null_ref() to TABLE_REF.  This method will check
        whether the reference contains NULL values so that it could never match any
        rows.
[11 Nov 2009 13:21] Øystein Grøvlen
Unchecking Jørgen's approval since the current patch is totally different from the one he approved.
[16 Nov 2009 7:19] Igor Babaev
Igor's solution #1

Attachment: bug47217-solution1.txt (text/plain), 1.07 KiB.

[16 Nov 2009 7:20] Igor Babaev
Igor's solution #2

Attachment: bug47217-solution2.txt (text/plain), 7.87 KiB.

[16 Nov 2009 7:26] Igor Babaev
Oystein,

After having worked on this problem this week-end I came up to the following two solutions. It makes sense to incorporate both of them into the baseline of mysql-6.0.

The first solution just ports the code that still exists in mysql-4.1. Actually you still can see the main bulk of this code in 5.0/5.1/6.0. It's the code that builds null-rejecting predicates (see the function  add_not_null_conds). The predicates are built but are never used. The lines that used them were lost when merging the code into the 5.0 tree. According to the bazaar/BitKeeper historical records it
happened somewhere in April 2005. As the patch that introduced the optimization did not provide any test cases nobody noticed that the optimization had not been enabled in 5.0. 
The original patch still can be found in the bug entry #8877. The optimization is very useful as it allows us in many cases even not to make look-ups when the key value is evaluated to null. So it saves some read accesses. The current 5.0/5.1 code does not do it.

For the test case from this bug entry the solution works perfectly well:

 mysql> explain select * from t1 join t2 on t1.v = t2.v order by 1;
+----+-------------+-------+------+---------------+------+---------+------+------+-----------------------------------------------------+
| id | select_type | table | type | possible_keys | key  | key_len | ref  | rows | Extra                                               |
+----+-------------+-------+------+---------------+------+---------+------+------+-----------------------------------------------------+
|  1 | SIMPLE      | NULL  | NULL | NULL          | NULL | NULL    | NULL | NULL | Impossible WHERE noticed after reading const tables |
+----+-------------+-------+------+---------------+------+---------+------+------+-----------------------------------------------------+
1 row in set (0.00 sec)

mysql> explain select * from t1 join t2 on t1.v = t2.v;
+----+-------------+-------+------+---------------+------+---------+------+------+-----------------------------------------------------+
| id | select_type | table | type | possible_keys | key  | key_len | ref  | rows | Extra                                               |
+----+-------------+-------+------+---------------+------+---------+------+------+-----------------------------------------------------+
|  1 | SIMPLE      | NULL  | NULL | NULL          | NULL | NULL    | NULL | NULL | Impossible WHERE noticed after reading const tables |
+----+-------------+-------+------+---------------+------+---------+------+------+-----------------------------------------------------+
1 row in set (0.00 sec)

At the same time the solution takes into account the case with <=> :

mysql> explain select * from t1 join t2 on t1.v <=> t2.v order by 1;
+----+-------------+-------+--------+---------------+------+---------+-------+------+------------------------------------+
| id | select_type | table | type   | possible_keys | key  | key_len | ref   | rows | Extra                              |
+----+-------------+-------+--------+---------------+------+---------+-------+------+------------------------------------+
|  1 | SIMPLE      | t2    | system | ix2           | NULL | NULL    | NULL  |    1 | Using filesort                     |
|  1 | SIMPLE      | t1    | ref    | ix1           | ix1  | 5       | const |    1 | Using index condition; Using where |
+----+-------------+-------+--------+---------------+------+---------+-------+------+------------------------------------+
2 rows in set (0.00 sec)

mysql> explain select * from t1 join t2 on t1.v <=> t2.v;
+----+-------------+-------+--------+---------------+------+---------+-------+------+-----------------------+
| id | select_type | table | type   | possible_keys | key  | key_len | ref   | rows | Extra                 |
+----+-------------+-------+--------+---------------+------+---------+-------+------+-----------------------+
|  1 | SIMPLE      | t2    | system | ix2           | NULL | NULL    | NULL  |    1 |                       |
|  1 | SIMPLE      | t1    | ref    | ix1           | ix1  | 5       | const |    1 | Using index condition |
+----+-------------+-------+--------+---------------+------+---------+-------+------+-----------------------+
2 rows in set (0.01 sec)
[16 Nov 2009 7:28] Igor Babaev
(Continuation for the previous comment)

If you add more records to t1 and t2:

insert into t2 values (11,NULL);
insert into t1 values (12,'b'),(13,NULL);
insert into t1 values (14,'c'),(15,'cc');
insert into t1 values (16,'d'),(17,'dd');
insert into t1 values (18,'e'),(19,'ee');

you'll have:

mysql> explain select * from t1 join t2 on t1.v = t2.v  where t2.v is null order by 1;
+----+-------------+-------+------+---------------+------+---------+-----------+------+--------------------------------------------------------+
| id | select_type | table | type | possible_keys | key  | key_len | ref       | rows | Extra                                                  |
+----+-------------+-------+------+---------------+------+---------+-----------+------+--------------------------------------------------------+
|  1 | SIMPLE      | t2    | ref  | ix2           | ix2  | 5       | const     |    1 | Using index condition; Using temporary; Using filesort |
|  1 | SIMPLE      | t1    | ref  | ix1           | ix1  | 5       | test.t2.v |    2 |                                                        |
+----+-------------+-------+------+---------------+------+---------+-----------+------+--------------------------------------------------------+
2 rows in set (0.00 sec)

mysql> explain select * from t1 join t2 on t1.v = t2.v  where t2.v is null;
+----+-------------+-------+------+---------------+------+---------+-----------+------+-----------------------+
| id | select_type | table | type | possible_keys | key  | key_len | ref       | rows | Extra                 |
+----+-------------+-------+------+---------------+------+---------+-----------+------+-----------------------+
|  1 | SIMPLE      | t2    | ref  | ix2           | ix2  | 5       | const     |    1 | Using index condition |
|  1 | SIMPLE      | t1    | ref  | ix1           | ix1  | 5       | test.t2.v |    2 |                       |
+----+-------------+-------+------+---------------+------+---------+-----------+------+-----------------------+
2 rows in set (0.00 sec)

These execution plans handle null values nicely:

mysql> flush status;
Query OK, 0 rows affected (0.00 sec)

mysql> show status like 'Handler_read_%';
+-----------------------+-------+
| Variable_name         | Value |
+-----------------------+-------+
| Handler_read_first    | 0     |
| Handler_read_key      | 0     |
| Handler_read_next     | 0     |
| Handler_read_prev     | 0     |
| Handler_read_rnd      | 0     |
| Handler_read_rnd_next | 0     |
+-----------------------+-------+
6 rows in set (0.01 sec)

mysql> select * from t1 join t2 on t1.v = t2.v  where t2.v is null order by 1;
Empty set (0.01 sec)

mysql> show status like 'Handler_read_%';
+-----------------------+-------+
| Variable_name         | Value |
+-----------------------+-------+
| Handler_read_first    | 0     |
| Handler_read_key      | 1     |
| Handler_read_next     | 0     |
| Handler_read_prev     | 0     |
| Handler_read_rnd      | 0     |
| Handler_read_rnd_next | 1     |
+-----------------------+-------+

mysql> flush status;
Query OK, 0 rows affected (0.00 sec)

mysql> show status like 'Handler_read_%';
+-----------------------+-------+
| Variable_name         | Value |
+-----------------------+-------+
| Handler_read_first    | 0     |
| Handler_read_key      | 0     |
| Handler_read_next     | 0     |
| Handler_read_prev     | 0     |
| Handler_read_rnd      | 0     |
| Handler_read_rnd_next | 0     |
+-----------------------+-------+
6 rows in set (0.01 sec)

mysql> select * from t1 join t2 on t1.v = t2.v  where t2.v is null;
Empty set (0.00 sec)

mysql> show status like 'Handler_read_%';
+-----------------------+-------+
| Variable_name         | Value |
+-----------------------+-------+
| Handler_read_first    | 0     |
| Handler_read_key      | 1     |
| Handler_read_next     | 0     |
| Handler_read_prev     | 0     |
| Handler_read_rnd      | 0     |
| Handler_read_rnd_next | 0     |
+-----------------------+-------+

Compare this with:

mysql> flush status;
Query OK, 0 rows affected (0.00 sec)

mysql> select * from t1 join t2 on t1.v <=> t2.v  where t2.v is null order by 1;
+----+------+----+------+
| pk | v    | pk | v    |
+----+------+----+------+
| 11 | NULL | 10 | NULL |
| 11 | NULL | 11 | NULL |
| 13 | NULL | 10 | NULL |
| 13 | NULL | 11 | NULL |
+----+------+----+------+
4 rows in set (0.01 sec)

mysql> show status like 'Handler_read_%';
+-----------------------+-------+
| Variable_name         | Value |
+-----------------------+-------+
| Handler_read_first    | 0     |
| Handler_read_key      | 3     |
| Handler_read_next     | 6     |
| Handler_read_prev     | 0     |
| Handler_read_rnd      | 4     |
| Handler_read_rnd_next | 5     |
+-----------------------+-------+
6 rows in set (0.00 sec)

mysql> flush status;
Query OK, 0 rows affected (0.00 sec)

mysql> select * from t1 join t2 on t1.v <=> t2.v  where t2.v is null;
+----+------+----+------+
| pk | v    | pk | v    |
+----+------+----+------+
| 11 | NULL | 10 | NULL |
| 13 | NULL | 10 | NULL |
| 11 | NULL | 11 | NULL |
| 13 | NULL | 11 | NULL |
+----+------+----+------+
4 rows in set (0.00 sec)

mysql> show status like 'Handler_read_%';
+-----------------------+-------+
| Variable_name         | Value |
+-----------------------+-------+
| Handler_read_first    | 0     |
| Handler_read_key      | 3     |
| Handler_read_next     | 6     |
| Handler_read_prev     | 0     |
| Handler_read_rnd      | 0     |
| Handler_read_rnd_next | 0     |
+-----------------------+-------+
6 rows in set (0.00 sec)

You'll find a patch for this solution in an attachment. Unfortunately this solutions causes many changes in the result files of our test cases with EXPLAIN commands.
Still I think that it would be nice to have this optimization in our code again.

The second solution is more conservative. It just saves the conditions for  ref accesses that are removed from the WHERE condition and returns them back of the plan for ORDER BY requires them. This solution does not result in any changes in the output files of out test suite. The patch for this solution you can find in another attachment. I think this patch is useful anyway.
[20 Nov 2009 12:32] 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/91065

3713 Evgeny Potemkin	2009-11-20
      Bug#47217: Lost optimization caused slowdown & wrong result.
      
      The "early null-filtering" optimization introduced in the fix for the bug#8877
      was lost during 4.1->5.0 merge. The optimization was introduced without test
      case thus error during the merge wasn't noticed. Due to this in some cases
      impossible WHERE expression wasn't detected allowing optimizer to choose a
      wrong plan led to a wrong result. Beside that, absence of early null-filtering
      allowed server to do useless scans with NULL value in a null-rejecting
      predicate thus slowing the query execution.
      
      
      The lost optimization is re-merged.
     @ mysql-test/r/distinct.result
        A test case result is corrected after fix for the bug#47217.
     @ mysql-test/r/greedy_optimizer.result
        A test case result is corrected after fix for the bug#47217.
     @ mysql-test/r/group_by.result
        A test case result is corrected after fix for the bug#47217.
     @ mysql-test/r/join.result
        A test case result is corrected after fix for the bug#47217.
     @ mysql-test/r/join_cache.result
        A test case result is corrected after fix for the bug#47217.
     @ mysql-test/r/join_nested.result
        A test case result is corrected after fix for the bug#47217.
     @ mysql-test/r/join_nested_jcl6.result
        A test case result is corrected after fix for the bug#47217.
     @ mysql-test/r/join_optimizer.result
        A test case is added for the bug#47217.
     @ mysql-test/r/join_outer.result
        A test case result is corrected after fix for the bug#47217.
     @ mysql-test/r/join_outer_jcl6.result
        A test case result is corrected after fix for the bug#47217.
     @ mysql-test/r/myisam.result
        A test case result is corrected after fix for the bug#47217.
     @ mysql-test/r/null_key.result
        A test case result is corrected after fix for the bug#47217.
     @ mysql-test/r/order_by.result
        A test case result is corrected after fix for the bug#47217.
     @ mysql-test/r/select.result
        A test case result is corrected after fix for the bug#47217.
     @ mysql-test/r/select_jcl6.result
        A test case result is corrected after fix for the bug#47217.
     @ mysql-test/r/select_safe.result
        A test case result is corrected after fix for the bug#47217.
     @ mysql-test/r/subselect.result
        A test case result is corrected after fix for the bug#47217.
     @ mysql-test/r/subselect3.result
        A test case result is corrected after fix for the bug#47217.
     @ mysql-test/r/subselect3_jcl6.result
        A test case result is corrected after fix for the bug#47217.
     @ mysql-test/r/subselect_no_mat.result
        A test case result is corrected after fix for the bug#47217.
     @ mysql-test/r/subselect_no_opts.result
        A test case result is corrected after fix for the bug#47217.
     @ mysql-test/r/subselect_no_semijoin.result
        A test case result is corrected after fix for the bug#47217.
     @ mysql-test/r/subselect_sj.result
        A test case result is corrected after fix for the bug#47217.
     @ mysql-test/r/subselect_sj2.result
        A test case result is corrected after fix for the bug#47217.
     @ mysql-test/r/subselect_sj2_jcl6.result
        A test case result is corrected after fix for the bug#47217.
     @ mysql-test/r/subselect_sj_jcl6.result
        A test case result is corrected after fix for the bug#47217.
     @ mysql-test/r/view.result
        A test case result is corrected after fix for the bug#47217.
     @ mysql-test/t/join_optimizer.test
        A test case is added for the bug#47217.
     @ sql/sql_select.cc
        Bug#47217: Lost optimization caused slowdown & wrong result.
        The optimization introduced in the bug fix#8877 is re-merged.
[23 Nov 2009 12:39] Øystein Grøvlen
Patch approved, but suggest that original test case from this bug report is added.
[24 Nov 2009 11:25] 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/91398

3713 Evgeny Potemkin	2009-11-24
      Bug#47217: Lost optimization caused slowdown & wrong result.
      
      The "early null-filtering" optimization introduced in the fix for the bug#8877
      was lost during 4.1->5.0 merge. The optimization was introduced without test
      case thus error during the merge wasn't noticed. Due to this in some cases
      impossible WHERE expression wasn't detected allowing optimizer to choose a
      wrong plan led to a wrong result. Beside that, absence of early null-filtering
      allowed server to do useless scans with NULL value in a null-rejecting
      predicate thus slowing the query execution.
      
      
      The lost optimization is re-merged.
     @ mysql-test/r/distinct.result
        A test case result is corrected after fix for the bug#47217.
     @ mysql-test/r/greedy_optimizer.result
        A test case result is corrected after fix for the bug#47217.
     @ mysql-test/r/group_by.result
        A test case result is corrected after fix for the bug#47217.
     @ mysql-test/r/join.result
        A test case result is corrected after fix for the bug#47217.
     @ mysql-test/r/join_cache.result
        A test case result is corrected after fix for the bug#47217.
     @ mysql-test/r/join_nested.result
        A test case result is corrected after fix for the bug#47217.
     @ mysql-test/r/join_nested_jcl6.result
        A test case result is corrected after fix for the bug#47217.
     @ mysql-test/r/join_optimizer.result
        A test case is added for the bug#47217.
     @ mysql-test/r/join_outer.result
        A test case result is corrected after fix for the bug#47217.
     @ mysql-test/r/join_outer_jcl6.result
        A test case result is corrected after fix for the bug#47217.
     @ mysql-test/r/myisam.result
        A test case result is corrected after fix for the bug#47217.
     @ mysql-test/r/null_key.result
        A test case result is corrected after fix for the bug#47217.
     @ mysql-test/r/order_by.result
        A test case result is corrected after fix for the bug#47217.
     @ mysql-test/r/select.result
        A test case result is corrected after fix for the bug#47217.
     @ mysql-test/r/select_jcl6.result
        A test case result is corrected after fix for the bug#47217.
     @ mysql-test/r/select_safe.result
        A test case result is corrected after fix for the bug#47217.
     @ mysql-test/r/subselect.result
        A test case result is corrected after fix for the bug#47217.
     @ mysql-test/r/subselect3.result
        A test case result is corrected after fix for the bug#47217.
     @ mysql-test/r/subselect3_jcl6.result
        A test case result is corrected after fix for the bug#47217.
     @ mysql-test/r/subselect_no_mat.result
        A test case result is corrected after fix for the bug#47217.
     @ mysql-test/r/subselect_no_opts.result
        A test case result is corrected after fix for the bug#47217.
     @ mysql-test/r/subselect_no_semijoin.result
        A test case result is corrected after fix for the bug#47217.
     @ mysql-test/r/subselect_sj.result
        A test case result is corrected after fix for the bug#47217.
     @ mysql-test/r/subselect_sj2.result
        A test case result is corrected after fix for the bug#47217.
     @ mysql-test/r/subselect_sj2_jcl6.result
        A test case result is corrected after fix for the bug#47217.
     @ mysql-test/r/subselect_sj_jcl6.result
        A test case result is corrected after fix for the bug#47217.
     @ mysql-test/r/view.result
        A test case result is corrected after fix for the bug#47217.
     @ mysql-test/t/join_optimizer.test
        A test case is added for the bug#47217.
     @ sql/sql_select.cc
        Bug#47217: Lost optimization caused slowdown & wrong result.
        The optimization introduced in the bug fix#8877 is re-merged.
[24 Nov 2009 11:27] 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/91401

3728 Evgeny Potemkin	2009-11-24 [merge]
      Auto-merged fix for the bug#47217.
[11 Dec 2009 6:01] Bugs System
Pushed into 6.0.14-alpha (revid:alik@sun.com-20091211055901-yp18b3c7xuhl87rf) (version source revid:alik@sun.com-20091211055401-43rjwq7gjed6ds83) (merge vers: 6.0.14-alpha) (pib:13)
[18 Dec 2009 2:57] Paul Dubois
Noted in 6.0.14 changelogs.

In some cases, an impossible WHERE expression was not detected, 
allowing the optimizer to choose an incorrect execution plan and
leading to a wrong result. Also, the absence of early NULL-filtering
allowed the server to do useless scans with NULL values in a
NULL-rejecting predicate, thus slowing query execution.
[12 May 2010 16:02] 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/108179

3170 Evgeny Potemkin	2010-05-12
      Bug#47217: Lost optimization caused slowdown & wrong result.
      
      The "early null-filtering" optimization introduced in the fix for the bug#8877
      was lost during 4.1->5.0 merge. The optimization was introduced without test
      case thus error during the merge wasn't noticed. Due to this in some cases
      impossible WHERE expression wasn't detected allowing optimizer to choose a
      wrong plan led to a wrong result. Beside that, absence of early null-filtering
      allowed server to do useless scans with NULL value in a null-rejecting
      predicate thus slowing the query execution.
      
      
      The lost optimization is re-merged.
      Origianl revid:epotemkin@mysql.com-20091124112439-c4wmum3xt3276827
     @ mysql-test/r/greedy_optimizer.result
        A test case result is corrected after fix for the bug#47217.
     @ mysql-test/r/group_by.result
        A test case result is corrected after fix for the bug#47217.
     @ mysql-test/r/join.result
        A test case result is corrected after fix for the bug#47217.
     @ mysql-test/r/join_cache.result
        A test case result is corrected after fix for the bug#47217.
     @ mysql-test/r/join_nested.result
        A test case result is corrected after fix for the bug#47217.
     @ mysql-test/r/join_nested_jcl6.result
        A test case result is corrected after fix for the bug#47217.
     @ mysql-test/r/join_optimizer.result
        A test case is added for the bug#47217.
     @ mysql-test/r/join_outer.result
        A test case result is corrected after fix for the bug#47217.
     @ mysql-test/r/join_outer_jcl6.result
        A test case result is corrected after fix for the bug#47217.
     @ mysql-test/r/myisam.result
        A test case result is corrected after fix for the bug#47217.
     @ mysql-test/r/null_key.result
        A test case result is corrected after fix for the bug#47217.
     @ mysql-test/r/order_by.result
        A test case result is corrected after fix for the bug#47217.
     @ mysql-test/r/select.result
        A test case result is corrected after fix for the bug#47217.
     @ mysql-test/r/select_jcl6.result
        A test case result is corrected after fix for the bug#47217.
     @ mysql-test/r/select_safe.result
        A test case result is corrected after fix for the bug#47217.
     @ mysql-test/r/subselect.result
        A test case result is corrected after fix for the bug#47217.
     @ mysql-test/r/subselect3.result
        A test case result is corrected after fix for the bug#47217.
     @ mysql-test/r/subselect3_jcl6.result
        A test case result is corrected after fix for the bug#47217.
     @ mysql-test/r/subselect_no_mat.result
        A test case result is corrected after fix for the bug#47217.
     @ mysql-test/r/subselect_no_opts.result
        A test case result is corrected after fix for the bug#47217.
     @ mysql-test/r/subselect_no_semijoin.result
        A test case result is corrected after fix for the bug#47217.
     @ mysql-test/r/subselect_sj.result
        A test case result is corrected after fix for the bug#47217.
     @ mysql-test/r/subselect_sj2.result
        A test case result is corrected after fix for the bug#47217.
     @ mysql-test/r/subselect_sj2_jcl6.result
        A test case result is corrected after fix for the bug#47217.
     @ mysql-test/r/subselect_sj_jcl6.result
        A test case result is corrected after fix for the bug#47217.
     @ mysql-test/r/view.result
        A test case result is corrected after fix for the bug#47217.
     @ mysql-test/t/join_optimizer.test
        A test case is added for the bug#47217.
     @ sql/sql_select.cc
        Bug#47217: Lost optimization caused slowdown & wrong result.
        The optimization introduced in the bug fix#8877 is re-merged.
[12 May 2010 16:04] 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/108180

3170 Evgeny Potemkin	2010-05-12
      Bug#47217: Lost optimization caused slowdown & wrong result.
      
      The "early null-filtering" optimization introduced in the fix for the bug#8877
      was lost during 4.1->5.0 merge. The optimization was introduced without test
      case thus error during the merge wasn't noticed. Due to this in some cases
      impossible WHERE expression wasn't detected allowing optimizer to choose a
      wrong plan led to a wrong result. Beside that, absence of early null-filtering
      allowed server to do useless scans with NULL value in a null-rejecting
      predicate thus slowing the query execution.
      
      
      The lost optimization is re-merged.
      Origianl revid:epotemkin@mysql.com-20091124112439-c4wmum3xt3276827
     @ mysql-test/r/greedy_optimizer.result
        A test case result is corrected after fix for the bug#47217.
     @ mysql-test/r/group_by.result
        A test case result is corrected after fix for the bug#47217.
     @ mysql-test/r/join.result
        A test case result is corrected after fix for the bug#47217.
     @ mysql-test/r/join_cache.result
        A test case result is corrected after fix for the bug#47217.
     @ mysql-test/r/join_nested.result
        A test case result is corrected after fix for the bug#47217.
     @ mysql-test/r/join_nested_jcl6.result
        A test case result is corrected after fix for the bug#47217.
     @ mysql-test/r/join_optimizer.result
        A test case is added for the bug#47217.
     @ mysql-test/r/join_outer.result
        A test case result is corrected after fix for the bug#47217.
     @ mysql-test/r/join_outer_jcl6.result
        A test case result is corrected after fix for the bug#47217.
     @ mysql-test/r/myisam.result
        A test case result is corrected after fix for the bug#47217.
     @ mysql-test/r/null_key.result
        A test case result is corrected after fix for the bug#47217.
     @ mysql-test/r/order_by.result
        A test case result is corrected after fix for the bug#47217.
     @ mysql-test/r/select.result
        A test case result is corrected after fix for the bug#47217.
     @ mysql-test/r/select_jcl6.result
        A test case result is corrected after fix for the bug#47217.
     @ mysql-test/r/select_safe.result
        A test case result is corrected after fix for the bug#47217.
     @ mysql-test/r/subselect.result
        A test case result is corrected after fix for the bug#47217.
     @ mysql-test/r/subselect3.result
        A test case result is corrected after fix for the bug#47217.
     @ mysql-test/r/subselect3_jcl6.result
        A test case result is corrected after fix for the bug#47217.
     @ mysql-test/r/subselect_no_mat.result
        A test case result is corrected after fix for the bug#47217.
     @ mysql-test/r/subselect_no_opts.result
        A test case result is corrected after fix for the bug#47217.
     @ mysql-test/r/subselect_no_semijoin.result
        A test case result is corrected after fix for the bug#47217.
     @ mysql-test/r/subselect_sj.result
        A test case result is corrected after fix for the bug#47217.
     @ mysql-test/r/subselect_sj2.result
        A test case result is corrected after fix for the bug#47217.
     @ mysql-test/r/subselect_sj2_jcl6.result
        A test case result is corrected after fix for the bug#47217.
     @ mysql-test/r/subselect_sj_jcl6.result
        A test case result is corrected after fix for the bug#47217.
     @ mysql-test/r/view.result
        A test case result is corrected after fix for the bug#47217.
     @ mysql-test/t/join_optimizer.test
        A test case is added for the bug#47217.
     @ sql/sql_select.cc
        Bug#47217: Lost optimization caused slowdown & wrong result.
        The optimization introduced in the bug fix#8877 is re-merged.
[16 Aug 2010 6:41] Bugs System
Pushed into mysql-next-mr (revid:alik@sun.com-20100816062819-bluwgdq8q4xysmlg) (version source revid:alik@sun.com-20100816062612-enatdwnv809iw3s9) (pib:20)
[13 Nov 2010 16:09] Bugs System
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)
[22 Nov 2010 0:33] Paul Dubois
Noted in 5.6.1 changelog.
[23 Nov 2010 2:16] Paul Dubois
Correction: No 5.6.1 changelog entry. Bug does not appear in any released 5.6.x version.