Performance regression with deeply nested subqueries

[Philip Stoev]

Monty reported that the following query, taken from the crash-me.sh script takes much longer in 5.3:

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))))))))))))))))))))))))))))))))

[Philip Stoev (pstoev-askmonty)]

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 s...

[Philip Stoev (pstoev-askmonty)]

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))))))))))))))))))))))))))))))));

[Timour Katchaounov (timour)]

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())
  {
    produce an empty result;
    stop execution
  }
  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.

[Sergey Petrunia (sergefp)]

FYI: in order to repeat with current 5.3-main, one needs to

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

[Sergey Petrunia (sergefp)]

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

[Sergey Petrunia (sergefp)]

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

[Sergey Petrunia (sergefp)]

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)
  {
    (void) return_zero_rows(this, result, select_lex->leaf_tables,
                            *columns_list,
       send_row_on_empty_set(),
       select_options,
       zero_result_cause,
       having ? having : tmp_having);
    DBUG_VOID_RETURN;
  }
</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())
    {
      ...
    }
    else if (join->send_row_on_empty_set())
    {
      ...
    }

</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.