Re: Query with impossible HAVING takes 1 millisec on 5.2 and 8 sec on 5.3
(comment based on the original, non-simplified testcase. The testcase posted here looks ok but I did not do a real check with it)

This bug demonstrates a problem with the optimizer, in particular with the choice between IN->EXISTS and Materialization strategies.

We have a query:

const1 IN (SELECT inner_expr FROM ... )

Why would the optimizer pick Materialization, when we have "const1" on the left side, and so will make only one lookup in the materialized table? It is obvious that IN->EXISTS will always be better than Materialization for such cases.

Re: Query with impossible HAVING takes 1 millisec on 5.2 and 8 sec on 5.3
Unfortunately the analysis in comment #1 is incorrect as shown below.

The real reason for the difference in execution times between 5.2 and 5.3 is a result of re-engineering subquery optimization to be done during the optimization phase. One consequence of this change is that subqueries can no longer be executed during optimization of the outer query. The reason for this is two-fold:

(1) A subquery may be arbitrarily expensive, thus it may make optimization and explain arbitrarily slow.
(2) Execution of subqueries during the optimization phase has side-effects that permanently change some data structures that represent a subquery. These side-effects later may lead to crashes.

In 5.2 a subquery of the type "const1 IN (SELECT inner_expr FROM ... )" is evaluated during the optimize_cond phase in JOIN::optimize, the result is substituted in the containing condition, and the condition is simplified. In the case of this example, the optimizer finds that the HAVING clause is FALSE, and produces an empty result without even executing the query.

In 5.3 subquery predicates are not evaluated during optimization, therefore such subsitution cannot be performed, and the query is executed as a normal JOIN.

Further investigation of the query plan in 5.3 shows that if we use the default join_cache_level=2, execution is very slow ~1.8 sec, while with join_cache_level=0, execution takes ~0.07 sec. This problem can be shown without a subquery, thus it is not related to this bug.

The attachment below contains detailed EXPLAINs, and execution times for 5.2/5.3 with various combinaitons of materialization=on/off, and join_cache_level=0/2.

Re: Query with impossible HAVING takes 1 millisec on 5.2 and 8 sec on 5.3
EXPLAINs, and execution times for 5.2, 5.3 with different join_cache_level, and materialization.

EXPLAINs, and execution times for 5.2, 5.3 with different join_cache_level, and materialization.
lpb944706-analysis.txt
LPexportBug944706_lpb944706-analysis.txt

Re: Query with impossible HAVING takes 1 millisec on 5.2 and 8 sec on 5.3
Possible solutions:

1) Delayed constant optimization.

There are various optimizations that rely on constant evaluation.
One way to address this problem would be to:

• Decide on which constant optimizations are the most important ones, and
• add an extra phase in the beginning of query execution that repeats
  all important constant optimizations for expensive conditions.
  As a result of this phase we may detect at the very start of query execution that
  a query result is empty, e.g. because of FALSE WHERE or HAVING clauses.

The disadvantages of this solution are:

• There may be dependencies on other optimizations, which in turn may make the
  approach unfeasible for some (or most) of the constant optimizations.
• If not all optimizations are repeated, there will still be cases of performance
  regressions compared to other server versions that use subqueries during
  constant optimization, and it is hard to know which cases are the most common ones.

2) Constant optimization for "cheap" subqueries

The second approach is to:

• Pre-optimize early those queries that may potentially be used for constant optimization.
• Estimate the cost of subquery evaluation for the above subqueries.
• Modify the Item::is_expensive() method to use the cost estimate to decide if a subquery is "cheap".
• Evaluate "cheap" subqueries whenever necessary. This would follow automatically from the changed
  implementation of is_expensive().

Problems/disadvantages:

• There are few cases when EXPLAIN needs data structures (TABLE_LIST) that were changed destructively
  while a subquery was executed before the actual explain code.
• The most time-consuming part seems to be that enabling constant optimization for subqueries results in
  several wrong results. Some of them are known bugs in MySQL, others possibly specific to MariaDB.

Re: Query with impossible HAVING takes 1 millisec on 5.2 and 8 sec on 5.3
If subqueries are not expensive (5.2, or changed 5.3) the query is optimized as follows:

• JOIN::optimize for the outer query calls:
  having= optimize_cond(this, having, join_list, &having_value, &having_equal);
• optimize_cond() calls remove_eq_conds()
• remove_eq_conds() calls eval_const_cond() as follows:
  else if (cond->const_item() && !cond->is_expensive()) { *cond_value= eval_const_cond(cond) ? Item::COND_TRUE : Item::COND_FALSE; return (COND*) 0; }
• eval_const_cond() calls Item_in_optimizer::val_int(), which in turn
  optimizes and executes the subquery, and returns FALSE to remove_eq_conds().
• remove_eq_conds() returns a NULL item, and sets JOIN::having_value = Item::COND_FALSE.
• JOIN::optimize checks that having_value is Item::COND_FALSE, and sets
  zero_result_cause= "Impossible HAVING"
• JOIN::exec checks for zero_result_cause and returns empty result without executing.
  EXPLAIN shows "Impossible HAVING".

If subqueries are expensive (5.3), the query is processed as follows:

• optimize_cond for the outer JOIN doesn't remove the HAVING clause.
• The optimizer optimizes both the query and the subquery.
• Execution proceeds normally by executing the three-way join in the
  query until end_send_group evaluates the HAVING clause once, which
  results in a single subquery execution.

Since the subquery is evaluated only once, one may wonder why this query
takes so much time. The reason is an inefficient JOIN plan that is chosen
with the default join_cache_level=2. The plan is:
-----------------------------------------------------------------------------------------------------------------------------------------------

-----------------------------------------------------------------------------------------------------------------------------------------------

-----------------------------------------------------------------------------------------------------------------------------------------------

This plan takes 1.8 sec.

With join_cache_level=0 there is a much better plan:
-----------------------------------------------------------------------------------------------------------

-----------------------------------------------------------------------------------------------------------

-----------------------------------------------------------------------------------------------------------

This plan takes 0.07 sec.

If we allow subqueries to be used for constant optimization we mask the problem
with the inneficient JOIN plan.

Re: Query with impossible HAVING takes 1 millisec on 5.2 and 8 sec on 5.3
Let's analyze a simpler query:

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

If subqueries are not expensive (5.2, or changed 5.3) the query is optimized as the
original test case, with the only difference, that optimize_cond is run for the WHERE
clause, and the WHERE clause is transformed into: "alias1.a = alias2.a".

This allows the JOIN optimizer to find a good plan that takes 0.02 sec:
-----------------------------------------------------------------------------------------------------------------------------------------------

-----------------------------------------------------------------------------------------------------------------------------------------------

-----------------------------------------------------------------------------------------------------------------------------------------------

In 5.3 where subqueries are expensive, the IN cannot be optimized away, and the OR condition doesn't allow a plan with ref access. The resulting plan takes ~ 3 sec:

------------------------------------------------------------------------------------------------------------------------------------------------------

------------------------------------------------------------------------------------------------------------------------------------------------------

------------------------------------------------------------------------------------------------------------------------------------------------------

Since there is subquery caching, the subquery itself is executed only once, but the function
that tests the cache is called for each join row.

Finally, as in the original query the above plan can be improved by setting join_cache_level=0 down to 0.07 sec:

-------------------------------------------------------------------------------------------

-------------------------------------------------------------------------------------------

-------------------------------------------------------------------------------------------

Re: Query with impossible or constant subquery in WHERE or HAVING is not precomputed and thus not part of optimization
Also filed in JIRA as MDEV-193

Re: Query with impossible or constant subquery in WHERE or HAVING is not precomputed and thus not part of optimization
Pushed to MariaDB 5.5.25.

Launchpad bug id: 944706