Three days ago I’ve finally managed to push the code for WL#3985 “Subquery optimization: smart choice between semi-join and materialization” into MySQL 6.0. I missed the clone-off date so it won’t be in the upcoming MySQL 6.0.9 release, the only way to get it before the next 6.0.10 release is from the lp:mysql-server/6.0 bazaar repository.

What’s new in the push

Before WL#3985, 6.0’s subquery optimization had these three deficiencies:

1. For semi-join (see cheatsheet for definition) subqueries, you had to make a choice between having the optimizer use materialization or all other strategies. The default behavior was not to use materialization, you could only get it by setting a server variable to disable all other strategies.
2. The choice among other strategies (FirstMatch, DuplicateWeedout, LooseScan) wasn’t very intelligent – roughly speaking, the optimizer would first pick a join order as if there were only inner joins, and then remember that some of them are actually semi-joins and try to find how it can resolve semi-joins with the picked join order.
3. Materialization only worked in the outer-to-inner fashion, that is, if you got a query like
   select * from people where name in (select owner from aircraft) it would still scan the people and make lookups into a temporary table of aircraft owners. It was not possible to make it scan the temptable of aircraft owners and make lookups into people.

WL#3985 fully addresses #1 and #2, and partially addresses #3. That is, now

• Semi-join subqueries can use Materialization in an inner-to-outer fashion
• Join optimizer is aware of existence of semi-joins and makes a fully automatic, cost-based choice between FirstMatch, DuplicateWeedout, LooseScan, inner-to-outer and outer-to-inner variants of Materialization.

This is expected to be a considerable improvement. The most common class of subqueries,
SELECT ... WHERE expr IN (SELECT ... w/o GROUPing/UNIONs/etc) AND ...
is now covered by a reasonably complete set of execution strategies and the optimizer is expected to have the capability to choose a good strategy for every case.

Possible gotchas, and we’re looking for input

I can’t state that the subquery optimizer does have the capability to pick a good plan because we haven’t done much experiments with the subquery cost model yet. We intend to do some benchmarking, but will also very much appreciate any input on how does the subquery optimizer behave for real-world queries. The code should be reasonably stable now – there are only three known problems, all of which are not very popular edge cases:

• LEFT JOINs. You may get wrong query results when the subquery or parent subquery use left joins.
• “Grandparent” correlation. A query with a semi-join child subquery which has a semi-join grandchild subquery which refers to a column in the top-level select may produce wrong query plans/results under certain circumstances.
• Different datatypes. You may get wrong query results of queries that have col1 IN (SELECT col2) where col1 and col2 are of different types (which should not happen too often in practice)

If you have subqueries with LEFT JOINs, please let us know also, because so far all LEFT JOIN+subquery cases we have were generated by the random query generator, certain properties of MySQL codebase make it difficult to make outer joins work with semi-joins, and if we don’t get any real-world LEFT JOIN examples, chances are we will disable subquery optimizations if there’s LEFT JOIN in the parent select, or in the subquery, or in either case.

I’ve finally found time to put together a couple of wiki pages describing what work we’re doing for subquery optimizations in MySQL 6.0:

• The Subquery_Works page has an overview of what we’ve done so far, we’re doing now and our future plans.
• The 6.0 Subquery Optimization Cheatsheet has a short, easy-to-read description of what has been released in MySQL 6.0.3. That should be enough if you just want to get the new version and see if your subquery is/can be faster now or not. If you want to know more details, the nearest occasion is my MySQL University session on February, 28.
• I’ve done a quick preliminary assessment of the impact of new optimizations. The raw results and first conclusions are here on the 6.0 Subquery Optimization Benchmarks page. We will be doing more analysis and I intend to post more observations based on the already collected data, stay tuned.

That’s everything I have on subqueries so far, but as I’ve already mentioned more is on the way.

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.

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.