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, 19 insertions, 16 deletions

diff --git a/mysql-test/r/subselect4.result b/mysql-test/r/subselect4.result
index 82360f9fe9f..c17ffe75282 100644
--- a/mysql-test/r/subselect4.result
+++ b/mysql-test/r/subselect4.result
@@ -562,7 +562,7 @@ WHERE f3 = (
 SELECT t1.f3 FROM t1
 WHERE ( t1.f10 ) IN ( SELECT f11 FROM t2 GROUP BY f11 ));
 id	select_type	table	type	possible_keys	key	key_len	ref	rows	Extra
-1	PRIMARY	t1	ref	f3	f3	5	const	0	Using where
+1	PRIMARY	NULL	NULL	NULL	NULL	NULL	NULL	NULL	Impossible WHERE noticed after reading const tables
 2	SUBQUERY	t1	ALL	NULL	NULL	NULL	NULL	2	
 2	SUBQUERY	<subquery3>	eq_ref	distinct_key	distinct_key	4	func	1	
 3	MATERIALIZED	t2	ALL	NULL	NULL	NULL	NULL	2	
@@ -577,7 +577,7 @@ WHERE f3 = (
 SELECT f3 FROM t1
 WHERE ( f10, f10 ) IN ( SELECT f11, f11 FROM t2 GROUP BY f11 ));
 id	select_type	table	type	possible_keys	key	key_len	ref	rows	Extra
-1	PRIMARY	t1	ref	f3	f3	5	const	0	Using where
+1	PRIMARY	NULL	NULL	NULL	NULL	NULL	NULL	NULL	Impossible WHERE noticed after reading const tables
 2	SUBQUERY	t1	ALL	NULL	NULL	NULL	NULL	2	
 2	SUBQUERY	<subquery3>	eq_ref	distinct_key	distinct_key	8	func,func	1	
 3	MATERIALIZED	t2	ALL	NULL	NULL	NULL	NULL	2	
@@ -1220,6 +1220,13 @@ id	select_type	table	type	possible_keys	key	key_len	ref	rows	Extra
 2	SUBQUERY	t2	ALL	NULL	NULL	NULL	NULL	2	Using where
 3	SUBQUERY	SQ1_t1	index	NULL	f4	5	NULL	2	Using index; Using temporary
 3	SUBQUERY	SQ1_t3	index	f4	f4	5	NULL	2	Using where; Using index; Using join buffer (flat, BNL join)
+SELECT * FROM t1 WHERE
+(SELECT f2 FROM t2
+WHERE f4 <= ALL
+(SELECT max(SQ1_t1.f4)
+FROM t3 AS SQ1_t1 JOIN t3 AS SQ1_t3 ON SQ1_t3.f4
+GROUP BY SQ1_t1.f4));
+ERROR 21000: Subquery returns more than 1 row
 drop table t1, t2, t3;
 #
 # BUG#52317: Assertion failing in Field_varstring::store() 
@@ -1250,8 +1257,7 @@ FROM t2 JOIN t1 ON t1.f3
 WHERE ('v') IN (SELECT f4 FROM t2)
 GROUP BY f9;
 id	select_type	table	type	possible_keys	key	key_len	ref	rows	Extra
-1	PRIMARY	t2	system	NULL	NULL	NULL	NULL	1	
-1	PRIMARY	t1	ALL	NULL	NULL	NULL	NULL	2	Using where
+1	PRIMARY	NULL	NULL	NULL	NULL	NULL	NULL	NULL	Impossible WHERE noticed after reading const tables
 3	DEPENDENT SUBQUERY	NULL	NULL	NULL	NULL	NULL	NULL	NULL	Impossible WHERE noticed after reading const tables
 2	DEPENDENT SUBQUERY	t1	ALL	NULL	NULL	NULL	NULL	2	
 SELECT COUNT(t2.f3),
@@ -1267,8 +1273,7 @@ FROM t2 JOIN t1 ON t1.f3
 WHERE ('v') IN (SELECT f4 FROM t2)
 ORDER BY f9;
 id	select_type	table	type	possible_keys	key	key_len	ref	rows	Extra
-1	PRIMARY	t2	system	NULL	NULL	NULL	NULL	1	
-1	PRIMARY	t1	ALL	NULL	NULL	NULL	NULL	2	Using where
+1	PRIMARY	NULL	NULL	NULL	NULL	NULL	NULL	NULL	Impossible WHERE noticed after reading const tables
 3	DEPENDENT SUBQUERY	NULL	NULL	NULL	NULL	NULL	NULL	NULL	Impossible WHERE noticed after reading const tables
 2	DEPENDENT SUBQUERY	t1	ALL	NULL	NULL	NULL	NULL	2	
 SELECT COUNT(t2.f3),
@@ -1277,7 +1282,7 @@ FROM t2 JOIN t1 ON t1.f3
 WHERE ('v') IN (SELECT f4 FROM t2)
 ORDER BY f9;
 COUNT(t2.f3)	f9
-0	2
+0	NULL
 EXPLAIN
 SELECT COUNT(t2.f3),
 (SELECT t2.f1 FROM t1 limit 1) AS f9
@@ -1285,8 +1290,7 @@ FROM t2 JOIN t1
 WHERE ('v') IN (SELECT f4 FROM t2)
 GROUP BY f9;
 id	select_type	table	type	possible_keys	key	key_len	ref	rows	Extra
-1	PRIMARY	t2	system	NULL	NULL	NULL	NULL	1	
-1	PRIMARY	t1	ALL	NULL	NULL	NULL	NULL	2	
+1	PRIMARY	NULL	NULL	NULL	NULL	NULL	NULL	NULL	Impossible WHERE noticed after reading const tables
 3	DEPENDENT SUBQUERY	NULL	NULL	NULL	NULL	NULL	NULL	NULL	Impossible WHERE noticed after reading const tables
 2	DEPENDENT SUBQUERY	t1	ALL	NULL	NULL	NULL	NULL	2	
 SELECT COUNT(t2.f3),
@@ -1302,8 +1306,7 @@ FROM t2 JOIN t1
 WHERE ('v') IN (SELECT f4 FROM t2)
 ORDER BY f9;
 id	select_type	table	type	possible_keys	key	key_len	ref	rows	Extra
-1	PRIMARY	t2	system	NULL	NULL	NULL	NULL	1	
-1	PRIMARY	t1	ALL	NULL	NULL	NULL	NULL	2	
+1	PRIMARY	NULL	NULL	NULL	NULL	NULL	NULL	NULL	Impossible WHERE noticed after reading const tables
 3	DEPENDENT SUBQUERY	NULL	NULL	NULL	NULL	NULL	NULL	NULL	Impossible WHERE noticed after reading const tables
 2	DEPENDENT SUBQUERY	t1	ALL	NULL	NULL	NULL	NULL	2	
 SELECT COUNT(t2.f3),
@@ -1325,7 +1328,7 @@ EXPLAIN
 SELECT (SELECT f1 FROM t1) AS field1 FROM t2 GROUP BY field1;
 id	select_type	table	type	possible_keys	key	key_len	ref	rows	Extra
 1	PRIMARY	t2	ALL	NULL	NULL	NULL	NULL	2	
-2	SUBQUERY	t1	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
 SELECT (SELECT f1 FROM t1) AS field1 FROM t2 GROUP BY field1;
 field1
 NULL
@@ -1333,7 +1336,7 @@ EXPLAIN
 SELECT (SELECT f1 FROM t1) AS field1 FROM t2 ORDER BY field1;
 id	select_type	table	type	possible_keys	key	key_len	ref	rows	Extra
 1	PRIMARY	t2	ALL	NULL	NULL	NULL	NULL	2	
-2	SUBQUERY	t1	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
 SELECT (SELECT f1 FROM t1) AS field1 FROM t2 ORDER BY field1;
 field1
 NULL
@@ -1631,7 +1634,7 @@ SET SESSION optimizer_switch='in_to_exists=on,materialization=off';
 EXPLAIN
 SELECT * FROM t1 WHERE ( 6 ) NOT IN ( SELECT t2.f3 FROM t2 JOIN t3 ON t3.f10 = t2.f10);
 id	select_type	table	type	possible_keys	key	key_len	ref	rows	Extra
-1	PRIMARY	t1	ALL	NULL	NULL	NULL	NULL	2	
+1	PRIMARY	NULL	NULL	NULL	NULL	NULL	NULL	NULL	Impossible WHERE
 2	DEPENDENT SUBQUERY	t3	system	NULL	NULL	NULL	NULL	1	
 2	DEPENDENT SUBQUERY	t2	ref_or_null	f10	f10	10	const,const	2	Using where; Using index
 SELECT * FROM t1 WHERE ( 6 ) NOT IN ( SELECT t2.f3 FROM t2 JOIN t3 ON t3.f10 = t2.f10);
@@ -1852,8 +1855,8 @@ GROUP BY 1, 2;
 id	select_type	table	type	possible_keys	key	key_len	ref	rows	Extra
 1	PRIMARY	t3	system	NULL	NULL	NULL	NULL	1	Using temporary; Using filesort
 1	PRIMARY	t2	ALL	NULL	NULL	NULL	NULL	2	Using where
-2	SUBQUERY	NULL	NULL	NULL	NULL	NULL	NULL	NULL	Impossible WHERE noticed after reading const tables
-3	MATERIALIZED	t1	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	MATERIALIZED	NULL	NULL	NULL	NULL	NULL	NULL	NULL	no matching row in const table
 PREPARE st1 FROM "
 SELECT t2.f1, (SELECT f2 FROM t1 WHERE (7) IN (SELECT f1 FROM t1))
 FROM t2 JOIN t3 ON t3.f4 = t2.f4