Fix for bug lp:944706, task MDEV-193

The patch enables back constant subquery execution during
query optimization after it was disabled during the development
of MWL#89 (cost-based choice of IN-TO-EXISTS vs MATERIALIZATION).

The main idea is that constant subqueries are allowed to be executed
during optimization if their execution is not expensive.

The approach is as follows:
- Constant subqueries are recursively optimized in the beginning of
  JOIN::optimize of the outer query. This is done by the new method
  JOIN::optimize_constant_subqueries(). This is done so that the cost
  of executing these queries can be estimated.
- Optimization of the outer query proceeds normally. During this phase
  the optimizer may request execution of non-expensive constant subqueries.
  Each place where the optimizer may potentially execute an expensive
  expression is guarded with the predicate Item::is_expensive().
- The implementation of Item_subselect::is_expensive has been extended
  to use the number of examined rows (estimated by the optimizer) as a
  way to determine whether the subquery is expensive or not.
- The new system variable "expensive_subquery_limit" controls how many
  examined rows are considered to be not expensive. The default is 100.

In addition, multiple changes were needed to make this solution work
in the light of the changes made by MWL#89. These changes were needed
to fix various crashes and wrong results, and legacy bugs discovered
during development.

1 files changed, 62 insertions, 30 deletions

diff --git a/mysql-test/r/subselect_no_scache.result b/mysql-test/r/subselect_no_scache.result
index 9b24af0dc3a..f7a8e8efd01 100644
--- a/mysql-test/r/subselect_no_scache.result
+++ b/mysql-test/r/subselect_no_scache.result
@@ -377,12 +377,12 @@ INSERT INTO t8 (pseudo,email) VALUES ('joce1','test1');
 INSERT INTO t8 (pseudo,email) VALUES ('2joce1','2test1');
 EXPLAIN EXTENDED SELECT pseudo,(SELECT email FROM t8 WHERE pseudo=(SELECT pseudo FROM t8 WHERE pseudo='joce')) FROM t8 WHERE pseudo=(SELECT pseudo FROM t8 WHERE pseudo='joce');
 id	select_type	table	type	possible_keys	key	key_len	ref	rows	filtered	Extra
-1	PRIMARY	t8	const	PRIMARY	PRIMARY	37	const	1	100.00	Using where; Using index
+1	PRIMARY	t8	const	PRIMARY	PRIMARY	37	const	1	100.00	Using index
 4	SUBQUERY	t8	const	PRIMARY	PRIMARY	37	const	1	100.00	Using index
-2	SUBQUERY	t8	const	PRIMARY	PRIMARY	37	const	1	100.00	Using where
+2	SUBQUERY	t8	const	PRIMARY	PRIMARY	37	const	1	100.00	
 3	SUBQUERY	t8	const	PRIMARY	PRIMARY	37	const	1	100.00	Using index
 Warnings:
-Note	1003	select `test`.`t8`.`pseudo` AS `pseudo`,(select `test`.`t8`.`email` from `test`.`t8` where (`test`.`t8`.`pseudo` = (select 'joce' from `test`.`t8` where 1))) AS `(SELECT email FROM t8 WHERE pseudo=(SELECT pseudo FROM t8 WHERE pseudo='joce'))` from `test`.`t8` where (`test`.`t8`.`pseudo` = (select 'joce' from `test`.`t8` where 1))
+Note	1003	select 'joce' AS `pseudo`,(select 'test' from `test`.`t8` where 1) AS `(SELECT email FROM t8 WHERE pseudo=(SELECT pseudo FROM t8 WHERE pseudo='joce'))` from `test`.`t8` where 1
 SELECT pseudo FROM t8 WHERE pseudo=(SELECT pseudo,email FROM
 t8 WHERE pseudo='joce');
 ERROR 21000: Operand should contain 1 column(s)
@@ -523,6 +523,7 @@ ERROR 21000: Subquery returns more than 1 row
 show warnings;
 Level	Code	Message
 Error	1242	Subquery returns more than 1 row
+Error	1028	Sort aborted: Subquery returns more than 1 row
 drop table t1;
 create table t1 (a int);
 insert into t1 values (1),(2),(3);
@@ -553,11 +554,7 @@ SELECT numreponse, (SELECT numeropost FROM t1 HAVING numreponse=1) FROM (SELECT
 numreponse	(SELECT numeropost FROM t1 HAVING numreponse=1)
 INSERT INTO t1 (numeropost,numreponse,pseudo) VALUES (1,1,'joce'),(1,2,'joce'),(1,3,'test');
 EXPLAIN EXTENDED SELECT numreponse FROM t1 WHERE numeropost='1' AND numreponse=(SELECT 1 FROM t1 WHERE numeropost='1');
-id	select_type	table	type	possible_keys	key	key_len	ref	rows	filtered	Extra
-1	PRIMARY	t1	const	PRIMARY,numreponse	PRIMARY	7	const,const	1	100.00	Using where; Using index
-2	SUBQUERY	t1	ref	PRIMARY	PRIMARY	3	const	2	100.00	Using index
-Warnings:
-Note	1003	select `test`.`t1`.`numreponse` AS `numreponse` from `test`.`t1` where ((`test`.`t1`.`numeropost` = '1') and (`test`.`t1`.`numreponse` = (select 1 from `test`.`t1` where (`test`.`t1`.`numeropost` = '1'))))
+ERROR 21000: Subquery returns more than 1 row
 SELECT numreponse FROM t1 WHERE numeropost='1' AND numreponse=(SELECT 1 FROM t1 WHERE numeropost='1');
 ERROR 21000: Subquery returns more than 1 row
 EXPLAIN EXTENDED SELECT MAX(numreponse) FROM t1 WHERE numeropost='1';
@@ -1681,34 +1678,34 @@ select * from t3 where NULL >= any (select b from t2);
 a
 explain extended select * from t3 where NULL >= any (select b from t2);
 id	select_type	table	type	possible_keys	key	key_len	ref	rows	filtered	Extra
-1	PRIMARY	t3	ALL	NULL	NULL	NULL	NULL	3	100.00	
-2	SUBQUERY	t2	system	NULL	NULL	NULL	NULL	0	0.00	const row not found
+1	PRIMARY	NULL	NULL	NULL	NULL	NULL	NULL	NULL	NULL	Impossible WHERE
+2	SUBQUERY	NULL	NULL	NULL	NULL	NULL	NULL	NULL	NULL	no matching row in const table
 Warnings:
-Note	1003	select `test`.`t3`.`a` AS `a` from `test`.`t3` where <nop>(<in_optimizer>(NULL,((select min(NULL) from `test`.`t2`) <= NULL)))
+Note	1003	select `test`.`t3`.`a` AS `a` from `test`.`t3` where 0
 select * from t3 where NULL >= any (select b from t2 group by 1);
 a
 explain extended select * from t3 where NULL >= any (select b from t2 group by 1);
 id	select_type	table	type	possible_keys	key	key_len	ref	rows	filtered	Extra
-1	PRIMARY	t3	ALL	NULL	NULL	NULL	NULL	3	100.00	
-2	SUBQUERY	t2	system	NULL	NULL	NULL	NULL	0	0.00	const row not found
+1	PRIMARY	NULL	NULL	NULL	NULL	NULL	NULL	NULL	NULL	Impossible WHERE
+2	SUBQUERY	NULL	NULL	NULL	NULL	NULL	NULL	NULL	NULL	no matching row in const table
 Warnings:
-Note	1003	select `test`.`t3`.`a` AS `a` from `test`.`t3` where <nop>(<in_optimizer>(NULL,((select min(NULL) from `test`.`t2`) <= NULL)))
+Note	1003	select `test`.`t3`.`a` AS `a` from `test`.`t3` where 0
 select * from t3 where NULL >= some (select b from t2);
 a
 explain extended select * from t3 where NULL >= some (select b from t2);
 id	select_type	table	type	possible_keys	key	key_len	ref	rows	filtered	Extra
-1	PRIMARY	t3	ALL	NULL	NULL	NULL	NULL	3	100.00	
-2	SUBQUERY	t2	system	NULL	NULL	NULL	NULL	0	0.00	const row not found
+1	PRIMARY	NULL	NULL	NULL	NULL	NULL	NULL	NULL	NULL	Impossible WHERE
+2	SUBQUERY	NULL	NULL	NULL	NULL	NULL	NULL	NULL	NULL	no matching row in const table
 Warnings:
-Note	1003	select `test`.`t3`.`a` AS `a` from `test`.`t3` where <nop>(<in_optimizer>(NULL,((select min(NULL) from `test`.`t2`) <= NULL)))
+Note	1003	select `test`.`t3`.`a` AS `a` from `test`.`t3` where 0
 select * from t3 where NULL >= some (select b from t2 group by 1);
 a
 explain extended select * from t3 where NULL >= some (select b from t2 group by 1);
 id	select_type	table	type	possible_keys	key	key_len	ref	rows	filtered	Extra
-1	PRIMARY	t3	ALL	NULL	NULL	NULL	NULL	3	100.00	
-2	SUBQUERY	t2	system	NULL	NULL	NULL	NULL	0	0.00	const row not found
+1	PRIMARY	NULL	NULL	NULL	NULL	NULL	NULL	NULL	NULL	Impossible WHERE
+2	SUBQUERY	NULL	NULL	NULL	NULL	NULL	NULL	NULL	NULL	no matching row in const table
 Warnings:
-Note	1003	select `test`.`t3`.`a` AS `a` from `test`.`t3` where <nop>(<in_optimizer>(NULL,((select min(NULL) from `test`.`t2`) <= NULL)))
+Note	1003	select `test`.`t3`.`a` AS `a` from `test`.`t3` where 0
 insert into t2 values (2,2), (2,1), (3,3), (3,1);
 select * from t3 where a > all (select max(b) from t2 group by a);
 a
@@ -1770,7 +1767,7 @@ id	select_type	table	type	possible_keys	key	key_len	ref	rows	filtered	Extra
 3	UNION	t1	system	NULL	NULL	NULL	NULL	1	100.00	
 NULL	UNION RESULT	<union2,3>	ALL	NULL	NULL	NULL	NULL	NULL	NULL	
 Warnings:
-Note	1003	select 'e' AS `s1` from dual where <nop>(<in_optimizer>('f',(<min>(select 'e' from dual union select 'e' from dual) < 'f')))
+Note	1003	select 'e' AS `s1` from dual where 1
 drop table t1;
 CREATE TABLE t1 (number char(11) NOT NULL default '') ENGINE=MyISAM CHARSET=latin1;
 INSERT INTO t1 VALUES ('69294728265'),('18621828126'),('89356874041'),('95895001874');
@@ -3105,7 +3102,7 @@ ON r.a = (SELECT t2.a FROM t2 WHERE t2.c = t1.a AND t2.b <= '359899'
              ORDER BY t2.c DESC, t2.b DESC LIMIT 1) WHERE t1.a = 10;
 id	select_type	table	type	possible_keys	key	key_len	ref	rows	Extra
 1	PRIMARY	t1	system	PRIMARY	NULL	NULL	NULL	1	
-1	PRIMARY	r	eq_ref	PRIMARY	PRIMARY	4	const	1	Using where
+1	PRIMARY	r	const	PRIMARY	PRIMARY	4	const	1	
 2	DEPENDENT SUBQUERY	t2	range	b	b	40	NULL	2	Using index condition
 SELECT sql_no_cache t1.a, r.a, r.b FROM t1 LEFT JOIN t2 r
 ON r.a = (SELECT t2.a FROM t2 WHERE t2.c = t1.a AND t2.b <= '359899'
@@ -3117,7 +3114,7 @@ ON r.a = (SELECT t2.a FROM t2 WHERE t2.c = t1.a AND t2.b <= '359899'
             ORDER BY t2.c, t2.b LIMIT 1) WHERE t1.a = 10;
 id	select_type	table	type	possible_keys	key	key_len	ref	rows	Extra
 1	PRIMARY	t1	system	PRIMARY	NULL	NULL	NULL	1	
-1	PRIMARY	r	eq_ref	PRIMARY	PRIMARY	4	const	1	Using where
+1	PRIMARY	r	const	PRIMARY	PRIMARY	4	const	1	
 2	DEPENDENT SUBQUERY	t2	range	b	b	40	NULL	2	Using index condition
 SELECT sql_no_cache t1.a, r.a, r.b FROM t1 LEFT JOIN t2 r
 ON r.a = (SELECT t2.a FROM t2 WHERE t2.c = t1.a AND t2.b <= '359899'
@@ -3733,8 +3730,8 @@ explain select * from t1 where not exists
 ((select t11.i from t1 t11) union (select t12.i from t1 t12));
 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	t11	system	NULL	NULL	NULL	NULL	0	const row not found
-3	UNION	t12	system	NULL	NULL	NULL	NULL	0	const row not found
+2	SUBQUERY	NULL	NULL	NULL	NULL	NULL	NULL	NULL	no matching row in const table
+3	UNION	NULL	NULL	NULL	NULL	NULL	NULL	NULL	no matching row in const table
 NULL	UNION RESULT	<union2,3>	ALL	NULL	NULL	NULL	NULL	NULL	
 DROP TABLE t1;
 CREATE TABLE t1 (a VARCHAR(250), b INT auto_increment, PRIMARY KEY (b));
@@ -4204,8 +4201,8 @@ CREATE TABLE t1 (a int, b int, KEY (a));
 INSERT INTO t1 VALUES (1,1),(2,1);
 EXPLAIN SELECT 1 FROM t1 WHERE a = (SELECT COUNT(*) FROM t1 GROUP BY b);
 id	select_type	table	type	possible_keys	key	key_len	ref	rows	Extra
-1	PRIMARY	t1	ref	a	a	5	const	0	Using where; Using index
-2	SUBQUERY	t1	ALL	NULL	NULL	NULL	NULL	2	Using temporary; Using filesort
+1	PRIMARY	t1	ref	a	a	5	const	1	Using where; Using index
+2	SUBQUERY	internal_tmp_table	ALL	group_key	NULL	NULL	NULL	1	Using temporary; Using filesort
 DROP TABLE t1;
 CREATE TABLE t1 (id int NOT NULL, st CHAR(2), INDEX idx(id));
 INSERT INTO t1 VALUES
@@ -4632,7 +4629,7 @@ id	select_type	table	type	possible_keys	key	key_len	ref	rows	filtered	Extra
 1	PRIMARY	t1	ALL	NULL	NULL	NULL	NULL	2	100.00	
 2	SUBQUERY	t1	ALL	NULL	NULL	NULL	NULL	2	100.00	
 Warnings:
-Note	1003	select 1 AS `1` from `test`.`t1` where <nop>(<in_optimizer>(1,((select max(`test`.`t1`.`a1`) from `test`.`t1`) > 1)))
+Note	1003	select 1 AS `1` from `test`.`t1` where 1
 SELECT 1 FROM t1 WHERE 1 < SOME (SELECT a1 FROM t1);
 1
 1
@@ -5966,7 +5963,7 @@ id	select_type	table	type	possible_keys	key	key_len	ref	rows	Extra
 EXPLAIN SELECT * FROM t1 WHERE EXISTS (SELECT * FROM t1 WHERE a=7);
 id	select_type	table	type	possible_keys	key	key_len	ref	rows	Extra
 1	PRIMARY	t1	ALL	NULL	NULL	NULL	NULL	4	
-2	SUBQUERY	t1	ref	a	a	5	const	1	Using index
+2	SUBQUERY	t1	ref	a	a	5	const	1	
 DROP TABLE t1;
 #
 # BUG#12616253 - WRONG RESULT WITH EXISTS(SUBQUERY) (MISSING ROWS)
@@ -6127,7 +6124,7 @@ set optimizer_switch=@tmp_optimizer_switch;
 EXPLAIN SELECT * FROM t1 WHERE EXISTS (SELECT * FROM t1 WHERE a=7);
 id	select_type	table	type	possible_keys	key	key_len	ref	rows	Extra
 1	PRIMARY	t1	ALL	NULL	NULL	NULL	NULL	4	
-2	SUBQUERY	t1	ref	a	a	5	const	1	Using index
+2	SUBQUERY	t1	ref	a	a	5	const	1	
 
 DROP TABLE t1;
 #
@@ -6568,6 +6565,41 @@ SELECT COUNT(f1), f2 IN (SELECT f1 FROM t1 WHERE f2 > 0) AS f4 FROM t2, t1 WHERE
 COUNT(f1)	f4
 0	0
 drop table t1,t2;
+#
+# LP BUG#944706 Query with impossible or constant subquery in WHERE or HAVING is not
+# precomputed and thus not part of optimization
+#
+CREATE TABLE t1 ( a VARCHAR(16), KEY (a) );
+INSERT INTO t1 VALUES ('Abilene'),('Akron'),('Albany'),('Albuquerque'),('Alexandria'),('Allentown'),
+('Amarillo'),('Anaheim'),('Anchorage'),('Ann Arbor'),('Arden-Arcade');
+EXPLAIN
+SELECT MAX( alias2.a ) AS field
+FROM t1 AS alias1, t1 AS alias2, t1 AS alias3
+WHERE alias1.a = alias2.a OR alias1.a = 'y'
+HAVING field>'B' AND ( 'Moscow' ) IN ( SELECT a FROM t1 );
+id	select_type	table	type	possible_keys	key	key_len	ref	rows	Extra
+1	PRIMARY	NULL	NULL	NULL	NULL	NULL	NULL	NULL	Impossible HAVING
+2	DEPENDENT SUBQUERY	t1	index_subquery	a	a	19	const	1	Using index; Using where
+SELECT MAX( alias2.a ) AS field
+FROM t1 AS alias1, t1 AS alias2, t1 AS alias3
+WHERE alias1.a = alias2.a OR alias1.a = 'y'
+HAVING field>'B' AND ( 'Moscow' ) IN ( SELECT a FROM t1 );
+field
+EXPLAIN
+SELECT MAX( alias2.a )
+FROM t1 AS alias1, t1 AS alias2, t1 AS alias3
+WHERE alias1.a = alias2.a OR ('Moscow') IN ( SELECT a FROM t1 );
+id	select_type	table	type	possible_keys	key	key_len	ref	rows	Extra
+1	PRIMARY	alias1	index	a	a	19	NULL	11	Using where; Using index
+1	PRIMARY	alias2	ref	a	a	19	test.alias1.a	2	Using index
+1	PRIMARY	alias3	index	NULL	a	19	NULL	11	Using index; Using join buffer (flat, BNL join)
+2	DEPENDENT SUBQUERY	t1	index_subquery	a	a	19	const	1	Using index; Using where
+SELECT MAX( alias2.a )
+FROM t1 AS alias1, t1 AS alias2, t1 AS alias3
+WHERE alias1.a = alias2.a OR ('Moscow') IN ( SELECT a FROM t1 );
+MAX( alias2.a )
+Arden-Arcade
+drop table t1;
 # return optimizer switch changed in the beginning of this test
 set optimizer_switch=@subselect_tmp;
 set optimizer_switch=default;