Bug #48190 Error processing ALL subqueries on empty sets - different than JavaDB/Postgres
Submitted: 20 Oct 2009 14:59
Reporter: Patrick Crews Email Updates:
Status: Verified Impact on me:
None 
Category:MySQL Server: Optimizer Severity:S3 (Non-critical)
Version:5.1,6.0 OS:Any
Assigned to:
Tags: regression, subquery
Triage: Triaged: D2 (Serious)

[20 Oct 2009 14:59] Patrick Crews
Description:
MySQL 5.1 and 6.0 are processing ALL subqueries that return empty sets differently than JavaDB and Postgresql.
I have not tested this against 5.0
This query:
SELECT table1 .`varchar_nokey`  
FROM C table1  LEFT  JOIN A table2  ON table2 .`pk`  = table1 .`pk`  
WHERE table2 .`int_key`  <  ALL (  
SELECT `pk`  
FROM C  
WHERE `varchar_key`  != `varchar_nokey`  )   ;

Produces this diff in a 3 way comparison between MySQL, Javadb, and Postgres:
# 10:27:57 @@ -0,0 +1,20 @@
# 10:27:57 +NULL
# 10:27:57 +c
# 10:27:57 +d
# 10:27:57 +e
# 10:27:57 +f
# 10:27:57 +h
# 10:27:57 +j
# 10:27:57 +k
# 10:27:57 +k
# 10:27:57 +m
# 10:27:57 +m
# 10:27:57 +m
# 10:27:57 +n
# 10:27:57 +o
# 10:27:57 +r
# 10:27:57 +t
# 10:27:57 +t
# 10:27:57 +u
# 10:27:57 +w
# 10:27:57 +y

MySQL EXPLAIN output:
EXPLAIN SELECT table1 .`varchar_nokey`
FROM C table1  LEFT  JOIN A table2  ON table2 .`pk`  = table1 .`pk`
WHERE table2 .`int_key`  <  ALL (
SELECT `pk`
FROM C
WHERE `varchar_key`  != `varchar_nokey`  )   ;
id	select_type	table	type	possible_keys	key	key_len	ref	rows	Extra
1	PRIMARY	NULL	NULL	NULL	NULL	NULL	NULL	NULL	Impossible WHERE noticed after reading const tables
2	SUBQUERY	C	ALL	NULL	NULL		NULL	NULL	20	Using where

It appears that the other two systems are interpreting the WHERE clause differently

How to repeat:
MTR test case (can apply the queries to other DBMS's as needed):

#/* Server0: MySQL 6.0.14-alpha-debug-log */
#/* Server1: JavaDB Version N/A */

#/*!50400 SET SESSION optimizer_switch = 'firstmatch=off,index_merge=on,index_merge_union=on,index_merge_sort_union=on,index_merge_intersection=on,loosescan=off,materialization=off,semijoin=off' */;
#/*!50400 SET SESSION optimizer_use_mrr = 'disable' */;
/*!50400 SET SESSION engine_condition_pushdown = 'ON' */;
#/*!50400 SET SESSION join_cache_level = 1 */;
#/*!50400 SET SESSION debug = '+d,optimizer_no_icp' */;

#/* Begin test case for query 0 */

--disable_warnings
DROP TABLE /*! IF EXISTS */ A;
DROP TABLE /*! IF EXISTS */ C;
--enable_warnings

CREATE TABLE `A` (
  `pk` int(11) NOT NULL AUTO_INCREMENT,
  `int_key` int(11) DEFAULT NULL,
  `varchar_key` varchar(1) DEFAULT NULL,
  `varchar_nokey` varchar(1) DEFAULT NULL,
  PRIMARY KEY (`pk`),
  KEY `int_key` (`int_key`),
  KEY `varchar_key` (`varchar_key`,`int_key`)
) ENGINE=MyISAM DEFAULT CHARSET=latin1;
CREATE TABLE `C` (
  `pk` int(11) NOT NULL AUTO_INCREMENT,
  `int_key` int(11) DEFAULT NULL,
  `varchar_key` varchar(1) DEFAULT NULL,
  `varchar_nokey` varchar(1) DEFAULT NULL,
  PRIMARY KEY (`pk`),
  KEY `int_key` (`int_key`),
  KEY `varchar_key` (`varchar_key`,`int_key`)
) ENGINE=MyISAM AUTO_INCREMENT=21 DEFAULT CHARSET=latin1;
INSERT INTO `C` VALUES (1,2,'w','w');
INSERT INTO `C` VALUES (2,9,'m','m');
INSERT INTO `C` VALUES (3,3,'m','m');
INSERT INTO `C` VALUES (4,9,'k','k');
INSERT INTO `C` VALUES (5,NULL,'r','r');
INSERT INTO `C` VALUES (6,9,'t','t');
INSERT INTO `C` VALUES (7,3,'j','j');
INSERT INTO `C` VALUES (8,8,'u','u');
INSERT INTO `C` VALUES (9,8,'h','h');
INSERT INTO `C` VALUES (10,53,'o','o');
INSERT INTO `C` VALUES (11,0,NULL,NULL);
INSERT INTO `C` VALUES (12,5,'k','k');
INSERT INTO `C` VALUES (13,166,'e','e');
INSERT INTO `C` VALUES (14,3,'n','n');
INSERT INTO `C` VALUES (15,0,'t','t');
INSERT INTO `C` VALUES (16,1,'c','c');
INSERT INTO `C` VALUES (17,9,'m','m');
INSERT INTO `C` VALUES (18,5,'y','y');
INSERT INTO `C` VALUES (19,6,'f','f');
INSERT INTO `C` VALUES (20,2,'d','d');

 
SELECT table1 .`varchar_nokey`  
FROM C table1  LEFT  JOIN A table2  ON table2 .`pk`  = table1 .`pk`  
WHERE table2 .`int_key`  <  ALL (  
SELECT `pk`  
FROM C  
WHERE `varchar_key`  != `varchar_nokey`  )   ;

#/* Diff: */

#/* --- /tmp//randgen9159-1256048893-server0.dump	2009-10-20 10:28:13.000000000 -0400
# +++ /tmp//randgen9159-1256048893-server1.dump	2009-10-20 10:28:13.000000000 -0400
# @@ -0,0 +1,20 @@
# +NULL
# +c
# +d
# +e
# +f
# +h
# +j
# +k
# +k
# +m
# +m
# +m
# +n
# +o
# +r
# +t
# +t
# +u
# +w
# +y */

DROP TABLE A;
DROP TABLE C;
#/* End of test case for query 0 */

Suggested fix:
Determine if we are correctly interpreting this WHERE clause.
[21 Oct 2009 12:31] Roy Lyseng
Here is the relevant part of the SQL standard (2003):

<quantified comparison predicate> ::=
    <row value predicand><quantified comparison predicate part 2>
<quantified comparison predicate part 2> ::=
    <comp op><quantifier> <table subquery>
<quantifier> ::=
    <all>
  | <some>
<all> ::= ALL

Let R be the result of the <row value predicand> and let T be the result of the <table subquery>.

2) The result of “R<comp op><quantifier>T” is derived by the application of the implied <comparison predicate> “R<comp op>RT” to every row RT in T:

Case:
a) If T is empty or if the implied <comparison predicate> is True for every row RT in T, then “R<comp op><all>T” is True.

In our case, R varies over an outer join result with 20 rows, <quantifier> is ALL, <comp op> is "<" and T is an empty subquery. Hence we can apply Case a) above to all R, and see that since T is empty, the predicate is True for every row R.

MySQL delivers an empty result, which is wrong.

EXPLAIN notices an "Impossible WHERE noticed after reading const tables", which indicates that this might be a too aggressive const value elimination.