Sergei Petrunia's blog

Nested outer joins

Here is MySQL’s nested outer joins optimization cheat sheet:

Conversions:
- RIGHT JOIN is converted to LEFT JOIN. FULL JOIN is not supported.
- Outer joins are converted to inner joins when possible
Constraints on join order:
- “Outer tables go first”
- “No interleaving”
Table access rules:
- “Inner” table access methods are constructed from parts of the ON condition. WHERE condition can’t be used to construct table accesses.
- Parts of ON condition are checked as soon as possible
- Parts of the WHERE condition
  – are not checked until we’ve found a row combination that matches the ON clause
  – are checked as soon as possible after that.

Or, in more detail:

Conversions

RIGHT JOIN to LEFT JOIN conversion is obvious:

  (t1 RIGHT JOIN t2 ON cond) = (t2 LEFT JOIN t1 ON cond)

Conversion from outer to inner join is possible when the result of inner join will be the same. It will be the same if the row combination with NULL-complimented row will not pass the WHERE clause. For example, if we look at the query

  t1 LEFT JOIN t2 ON some_cond WHERE t2.a=t1.b

we’ll see that a row with t2.a IS NULL will not satisfy the WHERE condition. Hence, this outer join can be converted to inner.

Constraints on join order

Outer tables go first: any outer table used in the outer join’s ON clause must be before all of the inner tables.
No interleaving: tables contained within an outer join must form a continuous sequence in the join order. Interleaving with tables that are outside of the outer join is not allowed.

Table access rules

Now, this requires some explanation. MySQL’s nested-loops join code tries to check parts of the WHERE as soon as
possible. For example when a query

SELECT * FROM
  t1,t2, ...
WHERE
  t1.col1=c1 AND
  t2.col1=t1.col2 AND t2.col2=c3 AND
  ...

is executed using a join order of (t1, t2,…), it proceeds according to this kind of scenario:

We can see here that the the WHERE condition is split into parts that are checked “as early as possible”.

With outer joins is more complicated. We need to know if we’ll need to generate a NULL-complemented row combination. We won’t need to if there was a combination of inner tables that matched the ON (but not necessarily the WHERE) clause. The solution is to switch the WHERE parts checking on and off.

The best way to show it is with example: Suppose we have a query

 SELECT * FROM ... ot1 LEFT JOIN (it1, it2) ON somecond WHERE ...

and suppose the join order is (ot1, it1, it2, …). The execution will proceed in this manner:

What’s visible there? When we start scanning table it1, we check only the ON condition. We can’t check the WHERE – we could iscard some it1’s row that is the only row that will match the ON condition, think there will be no matches, and erroneously generate the NULL-complimented row.

After we’ve found the match for the ON condition, we go back and check all parts of the WHERE we did not check because of the above mentioned reason.

After that, the execution proceeds as if this was an inner join, with ON merged into the WHERE clause.

The diagram also shows why we can’t use parts of the WHERE clause to create table acccess methods: because there are times when we can’t use parts of the WHERE for filtering. We always can use parts of the ON though.

Now it should be clear where all Table Access Rules came from.

Subqueries: the new strategy for "NULL IN (SELECT …)"

I hope this is my last post about this topic. It seems we’ve resolved all of the issues and I’ll now describe the user-visible consequences.
To recall, we’re talking about subquery predicates in form

 (oe1, ..., oeN) [NOT] IN (SELECT ie1, ..., ieN FROM ... )

that are located in a context where it matters if the predicate’s result is NULL or FALSE. The name “oe” stands for “outer expression”, ie stands for “inner expression”.

MySQL evaluates queries “from outside to inside”, i.e. we first get the values of (oe1, .. oeN) and then we run the subquery and capture the rows it produces. An apparent and very useful optimization is to “inform” the subquery that we’re looking only for rows that have “ie1=oe1”, “ie2=oe2” and so on. This is done by injecting appropriate equalities into subquery’s WHERE (or HAVING) clause. That is,

 (oe1, ..., oeN) [NOT] IN (SELECT ie1, ..., ieN FROM ... )

becomes

  EXISTS (SELECT 1 /* ie1, ..., ieN */
           FROM ... WHERE subquery_where AND
                          oe1=ie1 AND
                          oe2=ie2 AND
                          ...
                          oeN=ieN))

However, this conversion is only valid if we ignore possible NULL values. If some of the ie_k can be NULL, then we need to use oe_k=ie_k OR ie_k IS NULL instead. I’ve covered this case in detail here in NULL problem in the right part section.

Correct handling of cases where some oe_k IS NULL requires more radical changes. We’ve just made those changes and here they are:

The new strategy

According to SQL’s interpretation of NULL as “unknown value”,

  NULL IN (non-empty-list-of-some-values) = NULL
  NULL IN () = FALSE

So, when we want to evaluate

  NULL IN (SELECT ie FROM ... )

we need to run the SELECT and see if it will produce any rows. Note that we need to run the original SELECT, without any injected equalities mentioned in the previous section.

On the other hand, it is absolutely essential to have

  not_null_oe IN (SELECT ie FROM ...)

converted to

  EXISTS (SELECT 1 /* ie1 */ FROM ... WHERE ie1=not_null_oe ...)

If we don’t do this, subqueries will be terribly slow. We’ve solved this “inject or not inject” dilemma by wrapping the injected conditions into triggers. A subquery

  (oe1, ..., oeN) [NOT] IN (SELECT ie1, ..., ieN FROM ... )

is converted into

  EXISTS (SELECT 1 /* ie1, ..., ieN */
           FROM ... WHERE subquery_where AND
                          trigcond(oe1=ie1) AND
                          trigcond(oeN=ieN) AND
                          ...
         )

where each trigcond(X) is a special “magic” function defined as:

  trigcond(X) := X    when the "linked" outer expression oe_i is not NULL
  trigcond(X) := TRUE when the "linked" outer expression oe_i is NULL

Equalities that are wrapped into trigcond() function are not first class predicates for the query optimizer. Most optimizations cannot deal with predicates that may be turned on and off at query execution time, so they assume any trigcond(X) to be unknown function and ignore it. At the moment, triggerered equalities can be used by those optimizations:

Ref-optimizer: trigcond(X=Y [OR Y IS NULL]) can be used to construct ref, eq_ref or ref_or_null table accesses.
Index lookup-based subquery execution engines: trigcond(X=Y) can be used to construct unique_subquery or index_subquery access.
Table condition generator: if the subquery is a join of several tables, triggered condition will be checked as soon as possible.

When the optimizer uses triggered condition to create some kind of index lookup-based access (#1 and #2 in the above list), it must have a strategy for the case when the condition is turned off. This “Plan B” strategy is always the same – do a full table scan. In EXPLAIN the plan B shows up as “Full scan on NULL key” in the “Extra” column:

mysql> explain select t1.col1, t1.col1 IN (select t2.key1 from t2 where t2.col2=t1.col2) from t1

*************************** 1. row ***************************
           id: 1
  select_type: PRIMARY
        table: t1
        ...
*************************** 2. row ***************************
           id: 2
  select_type: DEPENDENT SUBQUERY
        table: t2
         type: index_subquery
possible_keys: key1
          key: key1
      key_len: 5
          ref: func
         rows: 2
        Extra: Using where; Full scan on NULL key

And if you run EXPLAIN EXTENDED …; SHOW WARNINGS you can see the triggered condition:

*************************** 2. row ***************************
  Level: Note
   Code: 1003
Message: select `test`.`t1`.`col1` AS `col1`,<in_optimizer>(`test`.`t1`.`col1`,<exists>(<
index_lookup>(<cache>(`test`.`t1`.`col1`) in t2 on key1 checking NULL where (`test`.`t2`.
`col2` = `test`.`t1`.`col2`) having trigcond(<is_not_null_test>(`test`.`t2`.`key1`))))) AS
`t1.col1 IN (select t2.key1 from t2 where t2.col2=t1.col2)` from `test`.`t1`

Performance implications

The first apparent implication is that NULL IN (SELECT …) now may cause full table scans (slow!) where it previously did not. This is the price to pay for correct results.
For multi-table subqueries the execution of NULL IN (SELECT …) is going to be particularly slow because the join optimizer doesn’t optimize for the case when outer expression is NULL. It assumes that subquery evaluations with NULL on the left side are very rare, even if there is statistics that says otherwise

On the other hand, if you have left expression that may be NULL but actually never is, you will not lose any speed.

The practical hints are

A column must be declared as NOT NULL if it really is. This is important for the other parts of the query optimizer too.
If you don’t really need the correct NULL/FALSE answer, you can easily avoid the slow execution path: just replace
```
     oe IN (SELECT ie FROM ...)
```
with
```
     (oe IS NOT NULL) AND (oe IN (SELECT ie FROM ...))
```
and NULL IN (SELECT …) will never be evaluated because MySQL stops evaluating AND parts as soon as the answer is clear.

The goal of this new strategy was to improve compliance and not speed. However we’ve had an intent to not make anything unneccessarily slow. If something became slower for you please file a bug, perhaps we’ll be able to do something about it.

Subqueries: NULLs and IN/=ANY problem fixed

A while ago I wrote about problem with NULLs and IN/=ANY subqueries MySQL had. I was completely correct when I wrote that the fix won’t be simple. It took 3 bug entries (BUG#8804, BUG#24085, BUG#24127), several review iterations by Igor, and the final patch is around 2,300 lines long.

The good news is that this patch solves the problem completely, and it is already in the 5.0.36 tree. The documentation is not yet updated, doing that is now on my todo. There is quite a lot to document: we’ve had to introduce “switchable access methods”, where a table accessed using ref is sometimes accessed using full table scan. (for the impatient: no, the new access method is not not called ref_or_null_or_all :-), it is still ref[_or_null] but with “Full scan on NULL key” in the “Extra” column).

I’ll post here when the docs become available.

An idea how to speed up nested-loops join a little

Working on subquery optimizations, got an idea how to speed up join execution a little. Read on.

The idea

Consider a query:

select * from t1, t2, t3 where t3.key=t1.col1 and t2.key=t1.col2

Suppose the join order is t1, t2, t3, i.e. the EXPLAIN is like

+-------+------+---------------+------+---------+--------------+-..
| table | type | possible_keys | key  | key_len | ref          |
+-------+------+---------------+------+---------+--------------+-..
| t1    | ALL  | NULL          | NULL | NULL    | NULL         |
| t2    | ref  | key           | key  | 5       | test.t1.col1 |
| t3    | ref  | key           | key  | 5       | test.t1.col2 |
+-------+------+---------------+------+---------+--------------+-..

The important property is that access to t3 is independent of access to t2. MySQL’s nested loops join algorithm will run this as in this swimlane diagram:

NL execution diagram

Here we assume that

table t2 has 4 rows such that t2.key=t1.col1
table t3 doesn’t have any rows such that t3.key=t1.col2

As soon as we make first index lookup in table t3 (the one with blue border), we see that there will be no matching row combinations for this row of t1. Nevertheless, MySQL executioner will proceed to examine different rows in table t2 (marked with red border). This is redundant and can be easily avoided.

The implementation

The executioner part is easy: just maked the nested-loops join code to “jump back” in the cases like the illustrated. If we don’t find a match and table access/selection condition does not depend on the preceding table(s), then go back to the last table that the table access depends on. I don’t have the ready term for this, the working name is “short-cutting”.

The optimizer part is (as usual) more complicated. One way is to take the easy route: let the join optimizer (the part of code that chooses the join order) remain unaware of the short-cutting. Once the join order is produced, set up the executioner to perform short-cutting where appopriate.

The bad part is that join optimizer doesn’t account for short-cutting when comparing costs of various join orders, which may lead it to choose non-optimal join orders. However, taking short-cutting into account won’t be easy:

First, we’ll need to generate selection conditions for the join orders we consider (in other words, figure out if the EXPLAIN will have “Using WHERE”). Our current way of doing this will probably be too expensive to be done for each considered join order.
Second, we’ll need to get somewhere an estimate of how often short-cutting will occur. That is, we’ll need to know probability that for some *arbitrary* values of columns from preceding tables, table T will have no rows that would satisfy given condition COND(preceding_tables, T). This estimate is likely to end up being some while guess like “lets use
0.5”.

At the moment the easy route seems like the way to go.

2007-02-11: Fixed typos in EXPLAIN ouput

IN/=ANY Subqueries NULL woes

NULL values are suprisingly hazardous for MySQL’s way of optimizing IN subqueries. MySQL takes the ‘=’ from ‘=ANY’ and tries to push it down into the subquery, essentially changing IN subquery into EXISTS subquery. That is, a subquery like

outer_expr IN (SELECT inner_expr FROM ... WHERE subq_where)

is converted to:

EXISTS (SELECT 1 FROM ... WHERE subq_where AND outer_expr=inner_expr)

and then MySQL can use the pushed-down equality to limit number of rows it has to look through when running the subquery. This “pushdown” works as long as outer_expr and inner_expr can’t be NULL or you don’t care whether subquery result is NULL or FALSE (MySQL figures that you don’t care if the subquery is a part of OR or AND expression in the WHERE clause).When you start caring about producing correct NULL or FALSE results, problems start coming from left and right, literally:

NULL problem in the right part

Suppose outer_expr is not a NULL value but the subquery doesn’t produce a row
such that outer_expr=inner_expr.
Then “non_null_outer_expr IN (SELECT …)” evaluates to

FALSE, if the SELECT produces only non-null values, or produces nothing
NULL, if the SELECT produces (among others) a row with inner_expr IS NULL.

The “look for rows with inner_expr=outer_expr” approach is not valid anymore. You have to use a more complicated “look for rows with inner_expr=outer_expr, and if nothing is found, look for rows with inner_expr IS NULL”. Roughly speaking, the subquery can be converted to:

EXISTS (SELECT 1 FROM ... WHERE subq_where AND
(outer_expr=inner_expr OR
inner_expr IS NULL))

The need to evaluate this is the reason why MySQL has ‘ref_or_null’ access method:

mysql> EXPLAIN
-> SELECT outer_expr IN (SELECT t2.maybe_null_key
->                       FROM t2, t3 WHERE ...)
-> FROM t1;
*************************** 1. row ***************************
id: 1
select_type: PRIMARY
table: t1
...
*************************** 2. row ***************************
id: 2
select_type: DEPENDENT SUBQUERY
table: t2
type: ref_or_null
possible_keys: maybe_null_key
key: maybe_null_key
key_len: 5
ref: func
rows: 2
Extra: Using where; Using index
...

Subqery-specific access methods, unique_subquery and index_subquery, too have or-null variants. They are not visible in EXPLAIN output, you need to use EXPLAIN EXTENDED and look through the produced warnings:

mysql> EXPLAIN EXTENDED
-> SELECT outer_expr IN (SELECT maybe_null_key FROM t2) FROM t1;
*************************** 1. row ***************************
id: 1
select_type: PRIMARY
table: t1
...
*************************** 2. row ***************************
id: 2
select_type: DEPENDENT SUBQUERY
table: t2
type: index_subquery
possible_keys: maybe_null_key
key: maybe_null_key
key_len: 5
ref: func
rows: 2
Extra: Using index
2 rows in set, 1 warning (0.00 sec)

mysql> show warnings;
*************************** 1. row ***************************
Level: Note
Code: 1003
Message: select (`test`.`t1`.`outer_expr`,
(((`test`.`t1`.`outer_expr`) in t2 on
maybe_null_key checking NULL))) AS `outer_expr IN (SELECT
maybe_null_key FROM t2)` from `test`.`t1`

The “OR … IS NULL” makes things slightly more complicated (and some optimizations within the subquery become impossible), but generally this is tolerable.

NULL hazard in the left part

The situation is much worse when you get NULL for outer_expr. According to NULL handling rules, NULL IN (SELECT inner_expr …) should evaluate to

FALSE, if the SELECT produces no rows.
NULL, if the SELECT produces any rows.

We’ll need to be able to check if the SELECT has produced any rows at all, so we can’t add “outer_expr = inner_expr” into the subquery. This is a problem, because lots of real world subqueries become very slow if we don’t push the equality down. At the moment, MySQL’s choice is to be fast rather than correct, and you may get FALSE where you should have gotten NULL. There seems to be no easy solution – essentially you need to have two different ways to execute the subquery depending on what is the value of left_expr is.

Me, Igor and Evgen are working on a fix. Hopefully I’ll be able post a resolution update soon.

Partitioning optimizations documentation is available

It’s been nine months since partition pruning code has been pushed into MySQL 5.1. Another available optimization, partition selection, has been in the main tree for even longer. There haven’t been any bugs reported for some time, so the code should be reasonably stable now.

And if you’re interested in what’s under the hood, a rather detailed description of partitioning optimizations is now available here:

http://dev.mysql.com/doc/internals/en/partitioning-optimizations.html

It is a part of the internals manual, but I tried to write it so it doesn’t
require any knowledge of MySQL source code. (and don’t be scared away by my English – the text in the manual has passed the scrutiny of the documentation team 🙂

Hello World!

Hi! My name is Sergey Petrunia and I’m one of the developers in MySQL Query Optimizer team. If you don’t have a habit of leafing through the commits list, you probably don’t hear much about what we’re doing, and we don’t have your feedback on it.
This blog is my attempt to rectify this situation a bit. Let’s see if it will succeed.