Fix bug lp:833777

Analysis:
The optimizer distinguishes two kinds of 'constant' conditions:
expensive ones, and non-expensive ones. The non-expensive conditions
are evaluated inside make_join_select(), and if false, already the
optimizer detects empty query results.

In order to avoid arbitrarily expensive optimization, the evaluation of
expensive constant conditions is delayed until execution. These conditions
are attached to JOIN::exec_const_cond and evaluated in the beginning of
JOIN::exec. The relevant execution logic is:

JOIN::exec()
{
  if (! join->exec_const_cond->val_int())
  {
    produce an empty result;
    stop execution
  }
  continue execution
  execute the original WHERE clause (that contains exec_const_cond)
 ...
}

As a result, when an expensive constant condition is
TRUE, it is evaluated twice - once through
JOIN::exec_const_cond, and once through JOIN::cond.
When the expensive constant condition is a subquery,
predicate, the subquery is evaluated twice. If we have
many levels of subqueries, this logic results in a chain
of recursive subquery executions that walk a perfect
binary tree. The result is that for subquries with depth N,
JOIN::exec is executed O(2^N) times.

Solution:
Notice that the second execution of the constant conditions
happens inside do_select(), in the branch:
if (join->table_count == join->const_tables) { ... }
In this case exec_const_cond is equivalent to the whole WHERE
clause, therefore the WHERE clause has already been checked in
the beginnig of JOIN::exec, and has been found to be true.
The bug is addressed by not evaluating the WHERE clause if there
was exec_const_conds, and it was TRUE.

8 files changed, 68 insertions, 3 deletions

diff --git a/mysql-test/r/func_compress.result b/mysql-test/r/func_compress.result
index 5c87939c75b..7a59c1beb8b 100644
--- a/mysql-test/r/func_compress.result
+++ b/mysql-test/r/func_compress.result
@@ -103,7 +103,6 @@ foo
 Warnings:
 Error	1259	ZLIB: Input data corrupted
 Error	1259	ZLIB: Input data corrupted
-Error	1259	ZLIB: Input data corrupted
 explain select *, uncompress(a) from t1;
 id	select_type	table	type	possible_keys	key	key_len	ref	rows	Extra
 1	SIMPLE	t1	system	NULL	NULL	NULL	NULL	1	
diff --git a/mysql-test/r/subselect.result b/mysql-test/r/subselect.result
index e71887f80ac..dc1596bf063 100644
--- a/mysql-test/r/subselect.result
+++ b/mysql-test/r/subselect.result
@@ -5665,4 +5665,14 @@ ERROR 21000: Subquery returns more than 1 row
 SET SESSION sql_mode=@old_sql_mode;
 DEALLOCATE PREPARE stmt;
 DROP TABLE t1;
+#
+# LP BUG#833777 Performance regression with deeply nested subqueries
+#
+create table t1 (a int not null, b char(10) not null);
+insert into t1 values (1, 'a');
+set @@optimizer_switch='in_to_exists=on,semijoin=off,materialization=off,subquery_cache=off';
+select a from t1 where a in (select a from t1 where a in (select a from t1 where a in (select a from t1 where a in (select a from t1 where a in (select a from t1 where a in (select a from t1 where a in (select a from t1 where a in (select a from t1 where a in (select a from t1 where a in (select a from t1 where a in (select a from t1 where a in (select a from t1 where a in (select a from t1 where a in (select a from t1 where a in (select a from t1 where a in (select a from t1 where a in (select a from t1 where a in (select a from t1 where a in (select a from t1 where a in (select a from t1 where a in (select a from t1 where a in (select a from t1 where a in (select a from t1 where a in (select a from t1 where a in (select a from t1 where a in (select a from t1 where a in (select a from t1 where a in (select a from t1 where a in (select a from t1 where a in (select a from t1 where a in (select a from t1 where a in (select a from t1))))))))))))))))))))))))))))))));
+a
+1
+drop table t1;
 set optimizer_switch=@subselect_tmp;
diff --git a/mysql-test/r/subselect_no_mat.result b/mysql-test/r/subselect_no_mat.result
index 6b6af156a00..fac396bc527 100644
--- a/mysql-test/r/subselect_no_mat.result
+++ b/mysql-test/r/subselect_no_mat.result
@@ -5670,6 +5670,16 @@ ERROR 21000: Subquery returns more than 1 row
 SET SESSION sql_mode=@old_sql_mode;
 DEALLOCATE PREPARE stmt;
 DROP TABLE t1;
+#
+# LP BUG#833777 Performance regression with deeply nested subqueries
+#
+create table t1 (a int not null, b char(10) not null);
+insert into t1 values (1, 'a');
+set @@optimizer_switch='in_to_exists=on,semijoin=off,materialization=off,subquery_cache=off';
+select a from t1 where a in (select a from t1 where a in (select a from t1 where a in (select a from t1 where a in (select a from t1 where a in (select a from t1 where a in (select a from t1 where a in (select a from t1 where a in (select a from t1 where a in (select a from t1 where a in (select a from t1 where a in (select a from t1 where a in (select a from t1 where a in (select a from t1 where a in (select a from t1 where a in (select a from t1 where a in (select a from t1 where a in (select a from t1 where a in (select a from t1 where a in (select a from t1 where a in (select a from t1 where a in (select a from t1 where a in (select a from t1 where a in (select a from t1 where a in (select a from t1 where a in (select a from t1 where a in (select a from t1 where a in (select a from t1 where a in (select a from t1 where a in (select a from t1 where a in (select a from t1 where a in (select a from t1 where a in (select a from t1))))))))))))))))))))))))))))))));
+a
+1
+drop table t1;
 set optimizer_switch=@subselect_tmp;
 set optimizer_switch=default;
 select @@optimizer_switch like '%materialization=on%';
diff --git a/mysql-test/r/subselect_no_opts.result b/mysql-test/r/subselect_no_opts.result
index 7eb45ae7d9b..41e350f966b 100644
--- a/mysql-test/r/subselect_no_opts.result
+++ b/mysql-test/r/subselect_no_opts.result
@@ -5666,5 +5666,15 @@ ERROR 21000: Subquery returns more than 1 row
 SET SESSION sql_mode=@old_sql_mode;
 DEALLOCATE PREPARE stmt;
 DROP TABLE t1;
+#
+# LP BUG#833777 Performance regression with deeply nested subqueries
+#
+create table t1 (a int not null, b char(10) not null);
+insert into t1 values (1, 'a');
+set @@optimizer_switch='in_to_exists=on,semijoin=off,materialization=off,subquery_cache=off';
+select a from t1 where a in (select a from t1 where a in (select a from t1 where a in (select a from t1 where a in (select a from t1 where a in (select a from t1 where a in (select a from t1 where a in (select a from t1 where a in (select a from t1 where a in (select a from t1 where a in (select a from t1 where a in (select a from t1 where a in (select a from t1 where a in (select a from t1 where a in (select a from t1 where a in (select a from t1 where a in (select a from t1 where a in (select a from t1 where a in (select a from t1 where a in (select a from t1 where a in (select a from t1 where a in (select a from t1 where a in (select a from t1 where a in (select a from t1 where a in (select a from t1 where a in (select a from t1 where a in (select a from t1 where a in (select a from t1 where a in (select a from t1 where a in (select a from t1 where a in (select a from t1 where a in (select a from t1 where a in (select a from t1))))))))))))))))))))))))))))))));
+a
+1
+drop table t1;
 set optimizer_switch=@subselect_tmp;
 set @optimizer_switch_for_subselect_test=null;
diff --git a/mysql-test/r/subselect_no_scache.result b/mysql-test/r/subselect_no_scache.result
index f7f593fb8ca..dcbe7eb2266 100644
--- a/mysql-test/r/subselect_no_scache.result
+++ b/mysql-test/r/subselect_no_scache.result
@@ -5669,6 +5669,16 @@ ERROR 21000: Subquery returns more than 1 row
 SET SESSION sql_mode=@old_sql_mode;
 DEALLOCATE PREPARE stmt;
 DROP TABLE t1;
+#
+# LP BUG#833777 Performance regression with deeply nested subqueries
+#
+create table t1 (a int not null, b char(10) not null);
+insert into t1 values (1, 'a');
+set @@optimizer_switch='in_to_exists=on,semijoin=off,materialization=off,subquery_cache=off';
+select a from t1 where a in (select a from t1 where a in (select a from t1 where a in (select a from t1 where a in (select a from t1 where a in (select a from t1 where a in (select a from t1 where a in (select a from t1 where a in (select a from t1 where a in (select a from t1 where a in (select a from t1 where a in (select a from t1 where a in (select a from t1 where a in (select a from t1 where a in (select a from t1 where a in (select a from t1 where a in (select a from t1 where a in (select a from t1 where a in (select a from t1 where a in (select a from t1 where a in (select a from t1 where a in (select a from t1 where a in (select a from t1 where a in (select a from t1 where a in (select a from t1 where a in (select a from t1 where a in (select a from t1 where a in (select a from t1 where a in (select a from t1 where a in (select a from t1 where a in (select a from t1 where a in (select a from t1 where a in (select a from t1))))))))))))))))))))))))))))))));
+a
+1
+drop table t1;
 set optimizer_switch=@subselect_tmp;
 set optimizer_switch=default;
 select @@optimizer_switch like '%subquery_cache=on%';
diff --git a/mysql-test/r/subselect_no_semijoin.result b/mysql-test/r/subselect_no_semijoin.result
index bb1ffa6942a..6b474f22f4a 100644
--- a/mysql-test/r/subselect_no_semijoin.result
+++ b/mysql-test/r/subselect_no_semijoin.result
@@ -5666,5 +5666,15 @@ ERROR 21000: Subquery returns more than 1 row
 SET SESSION sql_mode=@old_sql_mode;
 DEALLOCATE PREPARE stmt;
 DROP TABLE t1;
+#
+# LP BUG#833777 Performance regression with deeply nested subqueries
+#
+create table t1 (a int not null, b char(10) not null);
+insert into t1 values (1, 'a');
+set @@optimizer_switch='in_to_exists=on,semijoin=off,materialization=off,subquery_cache=off';
+select a from t1 where a in (select a from t1 where a in (select a from t1 where a in (select a from t1 where a in (select a from t1 where a in (select a from t1 where a in (select a from t1 where a in (select a from t1 where a in (select a from t1 where a in (select a from t1 where a in (select a from t1 where a in (select a from t1 where a in (select a from t1 where a in (select a from t1 where a in (select a from t1 where a in (select a from t1 where a in (select a from t1 where a in (select a from t1 where a in (select a from t1 where a in (select a from t1 where a in (select a from t1 where a in (select a from t1 where a in (select a from t1 where a in (select a from t1 where a in (select a from t1 where a in (select a from t1 where a in (select a from t1 where a in (select a from t1 where a in (select a from t1 where a in (select a from t1 where a in (select a from t1 where a in (select a from t1 where a in (select a from t1))))))))))))))))))))))))))))))));
+a
+1
+drop table t1;
 set optimizer_switch=@subselect_tmp;
 set @optimizer_switch_for_subselect_test=null;
diff --git a/mysql-test/t/subselect.test b/mysql-test/t/subselect.test
index c310878f0f8..aab2f536fd1 100644
--- a/mysql-test/t/subselect.test
+++ b/mysql-test/t/subselect.test
@@ -4768,4 +4768,14 @@ SET SESSION sql_mode=@old_sql_mode;
 DEALLOCATE PREPARE stmt;
 DROP TABLE t1;
 
+--echo #
+--echo # LP BUG#833777 Performance regression with deeply nested subqueries
+--echo #
+
+create table t1 (a int not null, b char(10) not null);
+insert into t1 values (1, 'a');
+set @@optimizer_switch='in_to_exists=on,semijoin=off,materialization=off,subquery_cache=off';
+select a from t1 where a in (select a from t1 where a in (select a from t1 where a in (select a from t1 where a in (select a from t1 where a in (select a from t1 where a in (select a from t1 where a in (select a from t1 where a in (select a from t1 where a in (select a from t1 where a in (select a from t1 where a in (select a from t1 where a in (select a from t1 where a in (select a from t1 where a in (select a from t1 where a in (select a from t1 where a in (select a from t1 where a in (select a from t1 where a in (select a from t1 where a in (select a from t1 where a in (select a from t1 where a in (select a from t1 where a in (select a from t1 where a in (select a from t1 where a in (select a from t1 where a in (select a from t1 where a in (select a from t1 where a in (select a from t1 where a in (select a from t1 where a in (select a from t1 where a in (select a from t1 where a in (select a from t1 where a in (select a from t1))))))))))))))))))))))))))))))));
+drop table t1;
+
 set optimizer_switch=@subselect_tmp;
diff --git a/sql/sql_select.cc b/sql/sql_select.cc
index c25d96ddef1..d1af7435706 100644
--- a/sql/sql_select.cc
+++ b/sql/sql_select.cc
@@ -14782,9 +14782,15 @@ do_select(JOIN *join,List<Item> *fields,TABLE *table,Procedure *procedure)
   {
     /*
       HAVING will be checked after processing aggregate functions,
-      But WHERE should checkd here (we alredy have read tables)
+      But WHERE should checkd here (we alredy have read tables).
+      If there is join->exec_const_cond, and all tables are constant, then it
+      is equivalent to join->conds. exec_const_cond is already checked in the
+      beginning of JOIN::exec. If it is false, JOIN::exec returns zero
+      result already there, therefore execution reaches this point only if
+      exec_const_cond is TRUE. Since it is equvalent to join->conds, then
+      join->conds is also TRUE.
     */
-    if (!join->conds || join->conds->val_int())
+    if (!join->conds || join->exec_const_cond || join->conds->val_int())
     {
       error= (*end_select)(join, 0, 0);
       if (error == NESTED_LOOP_OK || error == NESTED_LOOP_QUERY_LIMIT)