Bug #58818 Incorrect result for IN/ANY subquery with HAVING condition
Submitted: 8 Dec 2010 15:07 Modified: 20 Jan 2011 19:45
Reporter: Ole John Aske Email Updates:
Status: Closed Impact on me:
None 
Category:MySQL Server: Optimizer Severity:S2 (Serious)
Version:5.6.99, 5.5, 5.1 OS:Any
Assigned to: Ole John Aske CPU Architecture:Any
Triage: Triaged: D2 (Serious)

[8 Dec 2010 15:07] Ole John Aske
Description:
When executing a query of the general form:

 - SELECT ... WHERE <column> NOT IN (<subquery> HAVING <false pred>);
 - SELECT ... WHERE <column> IN (<subquery> HAVING <false pred>) IS UNKNOWN;

Where 
  - <subquery> return a NULL value for the column being compared
    against <column>
  - <false pred> will evaluate to false.

We get incorrect results from the query which are such that it looks like
that the 'HAVING <false pred>' was not evaluated.

How to repeat:
drop table t1,t1s,t2s;
create table t1(i int);
insert into t1 values (1), (2), (3);

create table t1s(i int);
insert into t1s values (10), (20), (30);
create table t2s(i int);
insert into t2s values (100), (200), (300);

# First inspect the result from the query we will soon 
# use as our subquery:
select straight_join t2s.i
   from
   t1s left outer join t2s on t2s.i = t1s.i;

+------+
| i    |
+------+
| NULL |
| NULL |
| NULL |
+------+
3 rows in set (0.00 sec)

# Correct! We then add a 'having condition to this query 

select straight_join t2s.i
   from
   t1s left outer join t2s on t2s.i = t1s.i
   having t2s.i = 999;
Empty set (0.00 sec)

# Correct, as expected the HAVING condition removed all NULL rows
# from the resultset.
#
# We then reuse this query as a ANY/IN subquery 

# As <subquery> return an empty set, 'i NOT ON <subquery>
# Should always be true
select * from t1
where t1.i NOT IN
(
  select straight_join t2s.i 
  from
  t1s left outer join t2s on t2s.i = t1s.i
  having t2s.i = 100
);
# -> Empty set, incorrect

# As <subquery> return an empty set, 'i ON <subquery> IS UNKNOWN
# Should always be false
select * from t1
where t1.i IN
(
  select straight_join t2s.i 
  from
  t1s left outer join t2s on t2s.i = t1s.i
  having t2s.i = 100
) IS UNKNOWN;
+------+
| i    |
+------+
|    1 |
|    2 |
|    3 |
+------+
# Surprise!, incorrect

#we observe the same incorrect behavior for an ANY subquery
select * from t1
where not t1.i = ANY
(
  select straight_join t2s.i 
  from
  t1s left outer join t2s on t2s.i = t1s.i
  having t2s.i = 999
);

select * from t1
 where t1.i = ANY (
  select straight_join t2s.i 
  from
  t1s left outer join t2s on t2s.i = t1s.i
  having t2s.i = 999
 ) is unknown
;
[8 Dec 2010 15:17] John Embretsen
The developer fixing this could probably take a look at Bug#56690 ("Wrong results with subquery with GROUP BY inside < ANY clause") at the same time...
[8 Dec 2010 15:18] Miguel Solorzano
Thank you for the bug report.
[8 Dec 2010 15:34] 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/126331

3477 Ole John Aske	2010-12-08
      Fix for bug#58818 Incorrect result for IN/ANY subquery with HAVING condition
      
      The fix is to ensure that the HAVING condition 'IS TRUE' when doing a 
      Item_in_subselect::single_value_transformer
      
      If the ::single_value_transformer() find an existing HAVING condition it used
      to do the transformation:
      
       1) HAVING cond -> (HAVING Cond) AND (cond_guard (Item_ref_null_helper(...))
      
      As the AND condition above is Mc'Carty evaluated, the idea was that the
      right side of the AND cond would be executed only if the HAVING evaluated to true.
      
      This logic failed to considder the 3-value logic required by NULL/UNKNOWN evaluation.
      Evaluating 'UNKNOWN AND <right cond>' requires the right AND-argument to be evaluated and
      'false' returned if <right cond> evaluated to false, else unknown.
      
      To get the required behaviour this fix change the transformation in 1) to be:
      
      2) HAVING cond -> ((HAVING Cond) IS TRUE) AND (cond_guard (Item_ref_null_helper(...))
[8 Dec 2010 15:40] 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/126334

3394 Ole John Aske	2010-12-08
      SPJ-sca-scan: Cherry picked fix for bug#58818: Incorrect result for IN/ANY subquery with HAVING condition
      
      The fix is to ensure that the HAVING condition 'IS TRUE' when doing a
      Item_in_subselect::single_value_transformer
      
      If the ::single_value_transformer() find an existing HAVING condition it used
      to do the transformation:
      
         1) HAVING cond -> (HAVING Cond) AND (cond_guard (Item_ref_null_helper(...))
      
      As the AND condition above is Mc'Carty evaluated, the idea was that the
      right side of the AND cond would be executed only if the HAVING evaluated to true.
      
      This logic failed to considder the 3-value logic required by NULL/UNKNOWN evaluation.
      Evaluating 'UNKNOWN AND <right cond>' requires the right AND-argument to be evaluated and
      'false' returned if <right cond> evaluated to false, else unknown.
      
      To get the required behaviour this fix change the transformation in 1) to be:
      
         2) HAVING cond -> ((HAVING Cond) IS TRUE) AND (cond_guard (Item_ref_null_helper(...))
[8 Dec 2010 15:42] 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/126335

3395 Ole John Aske	2010-12-08
      SPJ-sca-scan: Cherry picked fix for bug#58818: Incorrect result for IN/ANY subquery with HAVING condition
      
      The fix is to ensure that the HAVING condition 'IS TRUE' when doing a
      Item_in_subselect::single_value_transformer
      
      If the ::single_value_transformer() find an existing HAVING condition it used
      to do the transformation:
      
         1) HAVING cond -> (HAVING Cond) AND (cond_guard (Item_ref_null_helper(...))
      
      As the AND condition above is Mc'Carty evaluated, the idea was that the
      right side of the AND cond would be executed only if the HAVING evaluated to true.
      
      This logic failed to considder the 3-value logic required by NULL/UNKNOWN evaluation.
      Evaluating 'UNKNOWN AND <right cond>' requires the right AND-argument to be evaluated and
      'false' returned if <right cond> evaluated to false, else unknown.
      
      To get the required behaviour this fix change the transformation in 1) to be:
      
         2) HAVING cond -> ((HAVING Cond) IS TRUE) AND (cond_guard (Item_ref_null_helper(...))
[9 Dec 2010 8:49] Ole John Aske
After applying this fix, the result file for subselect3 will change and has to to updated. (Due to an EXPLAIN showing the extra 'IS TRUE' test)
[29 Dec 2010 8:38] 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/127651

3529 Ole John Aske	2010-12-29
      Updated fix for bug#58818 (Incorrect result for IN/ANY subquery with HAVING condition),
      based on review comments from Sergey Glukov:
      
      If the ::single_value_transformer() find an existing HAVING condition it used
      to do the transformation:
            
         1) HAVING cond -> (HAVING Cond) AND (cond_guard (Item_ref_null_helper(...))
      
      As the AND condition in 1) is Mc'Carty evaluated, the
      right side of the AND cond should be executed only if the 
      original 'HAVING evaluated' to true.
      
      However, as we failed to set 'top_level' for the tranformed HAVING condition,
      'abort_on_null' was FALSE after transformation. An
      UNKNOWN having condition will then not terminate evaluation of the
      transformed having condition, and we incorrectly continued
      into the Item_ref_null_helper() part.
[12 Jan 2011 12:15] 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/128502

3238 Ole John Aske	2011-01-12
      Fix for bug#58818: Incorrect result for IN/ANY subquery
      
      If the ::single_value_transformer() find an existing HAVING condition it used
      to do the transformation:
                  
        1) HAVING cond -> (HAVING Cond) AND (cond_guard (Item_ref_null_helper(...))
            
      As the AND condition in 1) is Mc'Carty evaluated, the
      right side of the AND cond should be executed only if the 
      original 'HAVING evaluated' to true.
            
      However, as we failed to set 'top_level' for the tranformed HAVING condition,
      'abort_on_null' was FALSE after transformation. An
      UNKNOWN having condition will then not terminate evaluation of the
      transformed having condition, and we incorrectly continued
      into the Item_ref_null_helper() part.
[12 Jan 2011 12:21] 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/128503

3488 Ole John Aske	2011-01-12 [merge]
      Merge of fix for bug#58818 from '5.5' -> 'trunk'
[12 Jan 2011 12:22] Bugs System
Pushed into mysql-trunk 5.6.2 (revid:ole.john.aske@oracle.com-20110112122116-rz733y2yo6ce1mmq) (version source revid:ole.john.aske@oracle.com-20110112122116-rz733y2yo6ce1mmq) (merge vers: 5.6.2) (pib:24)
[12 Jan 2011 12:23] Bugs System
Pushed into mysql-5.5 5.5.9 (revid:ole.john.aske@oracle.com-20110112121522-oqfyus25bhvz9lk0) (version source revid:ole.john.aske@oracle.com-20110112121522-oqfyus25bhvz9lk0) (merge vers: 5.5.9) (pib:24)
[12 Jan 2011 12:48] Ole John Aske
Pushed to mysql-5.5 and mysql-trunk
[12 Jan 2011 19:38] Roy Lyseng
You can try this for documentation:
A NOT IN predicate with a subquery containing a HAVING clause could retrieve too many rows, when the subquery itself returned NULL.
[13 Jan 2011 12:29] 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/128647

3405 Ole John Aske	2011-01-13
      SPJ-scan-scan: Updated fix for bug#58818 
      'Incorrect result for IN/ANY subquery with HAVING condition'
      according to what has been approved and pushed to mysql-5.5 & mysql-trunk.
[14 Jan 2011 13:37] Bugs System
Pushed into mysql-5.1-telco-7.0 5.1.51-ndb-7.0.21 (revid:ole.john.aske@oracle.com-20110114133647-wmiy33cz0ej61xl7) (version source revid:ole.john.aske@oracle.com-20110114133647-wmiy33cz0ej61xl7) (merge vers: 5.1.51-ndb-7.0.21) (pib:24)
[20 Jan 2011 19:45] Paul Dubois
Noted in 5.1.51-ndb-7.0.21, 5.5.9, 5.6.2 changelogs.

A NOT IN predicate with a subquery containing a HAVING clause could
retrieve too many rows, when the subquery itself returned NULL.