Re: Performance regression with deeply nested subqueries
IRC conversation:

(16:13:57) montywi: spetrunia: the following query takes much longer in 5.3 than in 5.2:
(16:14:00) montywi: select a from crash_me where a in (select a from crash_me where a in (select a from crash_me where a in (select a from crash_me where a in (select a from crash_me where a in (select a from crash_me where a in (select a from crash_me where a in (select a from crash_me where a in (select a from crash_me where a in (select a from crash_me where a in (select a from crash_me where a in (select a from crash_me where a in (select a from crash_me where
(16:14:00) montywi: a in (select a from crash_me where a in (select a from crash_me where a in (select a from crash_me where a in (select a from crash_me where a in (select a from crash_me where a in (select a from crash_me where a in (select a from crash_me where a in (select a from crash_me where a in (select a from crash_me where a in (select a from crash_me where a in (select a from crash_me where a in (select a from crash_me where a in (select a from crash_m
(16:14:02) montywi: e where a in (select a from crash_me where a in (select a from crash_me where a in (select a from crash_me where a in (select a from crash_me where a in (select a from crash_me where a in (select a from crash_me where a in (select a from crash_me))))))))))))))))))))))))))))))))
(16:14:22) montywi: this for a table with one row
(16:14:25) montywi: This is in crash-me.sh
(16:15:22) montywi: timour: see above. We are talking about minutes
(16:16:44) timour: montywi, hi, I will investigate later today, have to do some admin stuff before the call today.
(16:17:02) montywi: no big problem, just something we need to take a look at
(16:17:21) montywi: can't understand how the above could 'take forever' for a table with 1 row
(16:17:56) montywi: In 5.2 the subqueries are probably regarded as a constant which explains why it was fast
(16:20:47) timour: montywi, yes, this is one of the changes in 5.3 - we do not evaluate subqueries during optimization. However, minutes seems to be too much, have to investigate.
(16:22:21) spetrunia: montywi: checking
(16:22:37) montywi: have now run for 10 minutes
(16:24:33) spetrunia: montywi: what does EXPLAIN say?
(16:24:53) spetrunia: I'm wondering what there could be done for so much time with a table of 1 row..
(16:24:57) ***spetrunia tries to repeat
(16:25:05) montywi: http://pastie.org/2427796
(16:25:54) montywi: | 1 | PRIMARY | crash_me | system | NULL | NULL | NULL | NULL | 1 | |
(16:25:54) montywi: | 2 | DEPENDENT SUBQUERY | crash_me | system | NULL | NULL | NULL | NULL | 1 | |
(16:26:10) montywi: and then row 2 is repeated for 32 times
(16:26:12) spetrunia: I get ERROR 1473 (HY000): Too high level of nesting for select
(16:26:24) spetrunia: thread_stack...
(16:29:00) spetrunia: nope, thread_stack doesn't help
(16:29:06) spetrunia: still the same error
(16:29:40) spetrunia: ok repeated
(16:34:08) spetrunia: montywi: execution doesn't make much sense.. I think there is a bug somewhere
(16:34:16) spetrunia: and I doubt that the query will ever finish
(16:34:29) spetrunia: (I could repeat with a select 1 level shallower)
(16:34:32) spetrunia: I will file a bug
(16:34:42) montywi: spetrunia: ok. Please file a bug and put on your todo
(16:35:02) montywi: this would be nice to fix as otherwise we can't run crash-me.sh on mariadb
(16:35:20) spetrunia: but when one has optimizer_switch='semijoin=on', it's fast!
(16:35:27) spetrunia: new optimizations help even there
(16:35:43) spetrunia: | 1 | SIMPLE | crash_me | system | NULL | NULL | NULL | NULL | 1 | |
(16:35:43) spetrunia: | 1 | SIMPLE | crash_me | system | NULL | NULL | NULL | NULL | 1 | |
(16:35:43) spetrunia: | 1 | SIMPLE | crash_me | system | NULL | NULL | NULL | NULL | 1 | |
(16:35:43) spetrunia: | 1 | SIMPLE | crash_me | system | NULL | NULL | NULL | NULL | 1 | |
(16:35:46) spetrunia: flattening works

Re: Performance regression with deeply nested subqueries
Test case:

CREATE TABLE `crash_me` (
`a` int(11) NOT NULL,
`b` char(10) NOT NULL
) ENGINE=MyISAM DEFAULT CHARSET=latin1;
insert into crash_me values (1, 'a');
select a from crash_me where a in (select a from crash_me where a in (select a from crash_me where a in (select a from crash_me where a in (select a from crash_me where a in (select a from crash_me where a in (select a from crash_me where a in (select a from crash_me where a in (select a from crash_me where a in (select a from crash_me where a in (select a from crash_me where a in (select a from crash_me where a in (select a from crash_me where a in (select a from crash_me where a in (select a from crash_me where a in (select a from crash_me where a in (select a from crash_me where a in (select a from crash_me where a in (select a from crash_me where a in (select a from crash_me where a in (select a from crash_me where a in (select a from crash_me where a in (select a from crash_me where a in (select a from crash_me where a in (select a from crash_me where a in (select a from crash_me where a in (select a from crash_me where a in (select a from crash_me where a in (select a from crash_me where a in (select a from crash_me where a in (select a from crash_me where a in (select a from crash_me where a in (select a from crash_me))))))))))))))))))))))))))))))));

Re: Performance regression with deeply nested subqueries
Analysis:

The optimizer distinguishes two kinds of 'constant' conditions:
expensive ones, and non-expensive ones. These constant conditions
are extracted from the WHERE clause during optimization by
make_join_select. The non-expensive conditions are also evaluated
there, 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.

Since in general there can be other conditions (e.g. ON, HAVING clauses),
the relevant execution logic is:

JOIN::exec()
{
if (! join->exec_const_cond->val_int())

continue execution
execute the original WHERE clause
...
}

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.

Solutions:
a) Use the built-in cache of subqueries to avoid re-execution.
b) Modify make_cond_for_table to wrap each expensive constant
condition in an Item_cache object. Make sure to wrap the actual
conditions, not their AND/OR parents.
In addition this modified make_cond_for_table could extract the
expensive constant conditions, and the non-expensive ones separately.
c) Modify make_cond_for_table to substitute each expensive constant
condition in JOIN::cond with TRUE (Item_int(1)), and make sure that the
whole expensive condition is checked, and execution stops if it is FALSE.
Thus if the whole expensive condition is true, execution of the where
clause will not have to re-check it, and if it is FALSE, execution will never
try to evaluate the WHERE clause.

Re: Performance regression with deeply nested subqueries
FYI: in order to repeat with current 5.3-main, one needs to

SET @@optimizer_switch-'subquery_cache=off,semijoin=off'

Re: Performance regression with deeply nested subqueries
The fact that make_join_select() does not distinguish between expensive and cheap constant conditions can be viewed as a deficiency. Filed it, with example, here: bug #885799

Re: Performance regression with deeply nested subqueries
Re Solutions a) and b): we already have "subquery cache", there seems to be no need for another level of caching.

Re: Performance regression with deeply nested subqueries
More attention to the two places where expensive constant conditions are
evaluated:

First execution happens in JOIN::exec:

<code>
/*
Evaluate expensive constant conditions that were not evaluated during
optimization. Do not evaluate them for EXPLAIN statements as these
condtions may be arbitrarily costly, and because the optimize phase
might not have produced a complete executable plan for EXPLAINs.
*/
if (exec_const_cond && !(select_options & SELECT_DESCRIBE) &&
!exec_const_cond->val_int())
zero_result_cause= "Impossible WHERE noticed after reading const tables";

if (zero_result_cause)

</code>

Note that:
SELECT: if the condition is not satisfied, we return from JOIN::exec
EXPLAIN: we don't evaluate the condition at all.

Second execution is done here:

#0 do_select (join=0xbfa44c0, fields=0xbec2d3c, table=0x0, procedure=0x0) at sql_select.cc:14764
#1 0x0837c484 in JOIN::exec (this=0xbfa44c0) at sql_select.cc:2679

inside do_select(), we do:

<code>
...
if (join->table_count == join->const_tables)
{
/*
HAVING will be checked after processing aggregate functions,
But WHERE should checkd here (we alredy have read tables)
*/
if (!join->conds || join->conds->val_int())

</code>

Note that:

• this is a degenerate case with all tables being const tables. Non-degenerate
  joins will not attempt to evaluate join->conds (which is the entire WHERE
  clause of the join)

• Since this is a case of all tables being const tables, I can propose a theory
  that

(join->table_count == join->const_tables) => join->exec_const_cond == join->conds

and thus, the second check is redundant for non-EXPLAIN cases.
EXPLAINs should be analyzed and dealt with separately.

Launchpad bug id: 833777