MySQL Optimizer Blogs

Slides from Percona Live and airbnb Tech Talks

Øystein — Tue, 21 Apr 2015 21:14:00 +0000

Last week I presented my talk, "How to Analyze and Tune SQL Queries for Better Performance" both at Percona Live in Santa Clara and at airbnb Tech Talks in San Francisco. The slides are available on slideshare. A video recording from the airbnb talk should eventually be available the airbnb Tech Talks page.

MySQL Webinar: Analyze & Tune Queries for Better Performance

Øystein — Wed, 25 Feb 2015 19:49:00 +0000

Thanks to everyone who attended my webinar today, and thanks for all the positive feedback in the Q&A session. Unfortunately, I was not able to respond to everyone during the 15 minutes available for Q&A. If your question did not get answered, feel free to use the comments section of this blog post to ask your question. You can also ask questions on the MySQL Optimizer Forum.

The slides from the presentation are available here. In a few days, I expect it to be possible to access it as an MySQL On-Demand Webinar.

MySQL Webinar: Analyze & Tune Queries for Better Performance

Øystein — Wed, 18 Feb 2015 20:23:00 +0000

On Wednesday, February 25 at 18:00 CET (9 am Pacific Time), I will do webinar on how to analyze and tune MySQL queries for better performance.

The webinar covers how the MySQL optimizer chooses a specific plan to execute SQL queries. I will also show you how to use tools such as EXPLAIN (including the new JSON-based output) and Optimizer Trace to analyze query plans. We will also review how the Visual Explain functionality available in MySQL Workbench helps us visualize these plans. The webinar will also contain several examples of how to take advantage of the query analysis to improve performance of MySQL queries.

The presentation will be approximately 60 minutes long followed by Q&A.

For details on how to register for the webinar visit http://www.mysql.com/news-and-events/web-seminars/analyze-tune-queries-for-better-performance/

When ONLY_FULL_GROUP_BY Won’t See the Query Is Deterministic…

Guilhem Bichot — Mon, 19 Jan 2015 02:27:00 +0000

Hi! Just to say I wrote this new post about only_full_group_by tricks, on the MySQL Server team's blog.

MySQL 5.7: only_full_group_by Improved, Recognizing Functional Dependencies, Enabled by Default!

Guilhem Bichot — Wed, 10 Dec 2014 05:36:00 +0000

I just posted on the Server team's blog, an account on my recent only_full_group_by work. We have made significant improvements in 5.7.5, worth a look!

Speaking at MySQL Central @ Open World

Øystein — Mon, 29 Sep 2014 03:58:00 +0000

I am speaking at two sessions at Oracle Open World this week; one tutorial and one hands-on-lab:

How to Analyze and Tune MySQL Queries for Better Performance
Monday, Sep 29, 10:15 AM
MySQL EXPLAIN in Practice
Wednesday, Oct 1, 10:15 AM

I can also recommend the other sessions by members of the MySQL Optimizer Team:

Manyi Lu: MySQL 5.7: What’s New in the Parser and the Optimizer?
Wednesday, Oct 1, 11:30 AM
Olav Sandstå: MySQL Cost Model
Wednesday, Oct 1, 4:45 PM

Looking forward to meeting and talking with you at Oracle Open World!

MySQL Webinar: MySQL EXPLAIN, explained

Øystein — Fri, 18 Jul 2014 14:17:00 +0000

Some time ago, Matt Lord and I delivered a webinar on the MySQL EXPLAIN feature. This webinar is available for on-demand access here. Based on the questions we got during the webinar, I want to emphasize that EXPLAIN does not execute the query, it only determines the query plan for the query. Hence, EXPLAIN will not be able to evaluate how good the chosen query plan actually is.

If you have questions on this topic after listening to this webinar, feel free to ask questions; either as comments on this blog or at the MySQL Optimizer Forum.

You can also access other webinars on MySQL. New webinars will be announced here.

A Multi-Table Trick to Speed up Single-Table UPDATE/DELETE Statements

Øystein — Mon, 14 Jul 2014 18:51:00 +0000

This post appeared first on mysqlserverteam.com

In MySQL, query optimization of single-table UPDATE/DELETE statements is more limited than for SELECT statements. I guess the main reason for this is to limit the optimizer overhead for very simple statements. However, this also means that optimization opportunities are sometimes missed for more complex UPDATE/DELETE statements.

Example

Using the DBT-3 database, the following SQL statement will increase prices by 10% on parts from suppliers in the specified country:

UPDATE part
SET p_retailprice = p_retailprice*1.10
WHERE p_partkey IN
     (SELECT ps_partkey
      FROM partsupp JOIN supplier
      ON ps_suppkey = s_suppkey
      WHERE s_nationkey = 4);

Visual EXPLAIN in MySQL Workbench shows that the optimizer will choose the following execution plan for this UPDATE statement:

That is, for every row in the part table, MySQL will check if this part is supplied by a supplier of the requested nationality. Consider the following similar SELECT statement:

SELECT * FROM part 
WHERE p_partkey IN 
     (SELECT ps_partkey 
      FROM partsupp JOIN supplier 
      ON ps_suppkey = s_suppkey 
      WHERE s_nationkey = 4);

In MySQL 5.6, the query optimizer will apply semi-join transformation to this query. Hence, the execution plan is quite different from the similar UPDATE statement:

As you can see, there is no sub-query in this plan. The query has been transformed into a three-way join. The great advantage of this semi-join transformation is that the optimizer is now free to re-arrange the order of the tables to be joined. Instead of having to go through all 179,000 parts, it will now start with the estimated 414 suppliers from the given country and find all parts supplied by them. This is obviously more efficient, and it would be good if MySQL would use the same approach for the UPDATE statement.

The Multi-Table Trick

Unlike single-table UPDATE statements, the MySQL Optimizer will use all available optimizations for multi-table UPDATE statements. This means that by rewriting the query as follows, the semi-join optimizations will apply:

UPDATE part, (SELECT 1) dummy 
SET p_retailprice = p_retailprice*1.10
WHERE p_partkey IN 
     (SELECT ps_partkey 
      FROM partsupp JOIN supplier 
      ON ps_suppkey = s_suppkey 
      WHERE s_nationkey = 4);

Notice the extra dummy table in the first line. Here is what happens when I execute the single-table and multi-table variants on a DBT-3 database (scale factor 1):

mysql> UPDATE part SET p_retailprice = p_retailprice*1.10 WHERE p_partkey IN (SELECT ps_partkey FROM partsupp JOIN supplier ON ps_suppkey = s_suppkey WHERE s_nationkey = 4);
Query OK, 31097 rows affected, 28003 warnings (2.63 sec)
Rows matched: 31097  Changed: 31097  Warnings: 28003

mysql> ROLLBACK;
Query OK, 0 rows affected (0.20 sec)

mysql> UPDATE part, (SELECT 1) dummy SET p_retailprice = p_retailprice*1.10 WHERE p_partkey IN (SELECT ps_partkey FROM partsupp JOIN supplier ON ps_suppkey = s_suppkey WHERE s_nationkey = 4); 
Query OK, 31097 rows affected, 28003 warnings (0.40 sec)
Rows matched: 31097  Changed: 31097  Warnings: 28003

As you can see, execution time is reduced from 2.63 seconds to 0.40 seconds by using this trick. (I had executed both statements several times before, so the reported execution times are for a steady state with all accessed data in memory.)

Multi-Table DELETE

The same trick can be used for DELETE statements. Instead of the single-table variant,

DELETE FROM part
WHERE p_partkey IN
       (SELECT ps_partkey
        FROM partsupp JOIN supplier
        ON ps_suppkey = s_suppkey
        WHERE s_nationkey = 4);

you can use the equivalent multi-table variant:

DELETE part FROM part
WHERE p_partkey IN
       (SELECT ps_partkey
        FROM partsupp JOIN supplier
        ON ps_suppkey = s_suppkey
        WHERE s_nationkey = 4);

This rewrite gives a similar performance improvement as reported for the above UPDATE statement.

Re-factoring some internals of prepared statements in 5.7

Guilhem Bichot — Wed, 21 May 2014 08:07:00 +0000

[ this is a re-posting of what I published on the MySQL server team blog a few days ago ]

When the MySQL server receives a SELECT query, the query goes through several consecutive phases:

parsing: SQL words are recognized, the query is split into different parts following the SQL grammar rules: a list of selected expressions, a list of tables to read, a WHERE condition, …
resolution: the output of the parsing stage contains names of columns and names of tables. Resolution is about making sense out of this. For example, in “WHERE foo=3“, “foo” is a column name without a table name; by applying SQL name resolution rules, we discover the table who contains “foo” (it can be complicated if subqueries or outer joins are involved).
optimization: finding the best way to read tables: the best order of tables, and for each table, the best way to access it (index lookup, index scan, …). The output is the so-called “plan”.
execution: we read tables as dictated by the plan above, and send output rows to the client.

This design hasn’t changed since many many years. Originally, MySQL didn’t have prepared statements. So it took a query, passed it through the phases above, and then threw it away. This still happens nowadays when using non-prepared statements.
But, with a prepared statement, come more requirements. MySQL has to be able to execute the query a second time (and a third time, and so on, at the user’s will). No matter the used API (the C API or the SQL API), this usually looks like the following dialogue:

 # Assume that "t" contains 3 rows with values 1, 2, 98 in a column
 user: PREPARE stmt FROM 'SELECT * FROM t';
 MySQL: okay
 user: EXECUTE stmt;
 MYSQL: 1,2,98
 user: INSERT INTO t VALUES (0);
 user: EXECUTE stmt;
 MYSQL: 1,2,98,0

SQL mandates that syntax and semantic errors be reported by PREPARE, without postponing them to EXECUTE. So, PREPARE needs to do at least parsing and resolution, to spot any such error.
Then there is an implementation question: when it receives "EXECUTE stmt", how can MySQL remember what “stmt” is?
The simplest, most obvious solution would be, during PREPARE, to simply store "stmt" => "SELECT * FROM t" in some session-local key/value dictionary. When "EXECUTE stmt" comes, MySQL would find the query string in the dictionary, and go through all stages (parsing, resolution, optimization, execution). And when the next "EXECUTE stmt" comes, it would do the same again.
Of course, that would not be efficient. At least parsing and resolution theoretically don’t need to be re-done every time: query’s text doesn’t change, so only one parsing is necessary; the structure of tables (names and type of columns) doesn’t change, so only one resolution is necessary (but see footnote 1). So, what PREPARE actually stores in the key/value dictionary, is "stmt" => tree, where “tree” is the output of the resolution phase; it’s an in-memory tree of C++ objects, each object representing an expression, a column of a table, a table, a left join, a boolean condition, …
With this design, only optimization and execution are repeated by each "EXECUTE stmt" (but see footnote 2). Repeating optimization is sometimes a smart thing to do; imagine that between the first and second EXECUTE, the table’s data distribution has significantly changed (perhaps due to other clients), then the plan of the first EXECUTE is maybe not the best one anymore, and searching for a new plan makes sense. In other cases, repeating optimization is a waste, because the old plan would be good enough. As of today, MySQL always repeats optimization; making this more flexible would be an interesting enhancement for the future, but today’s situation is: we repeat optimization.

Optimization does everything it can to speed up the query. Imagine the query references 10 tables in its FROM clause. To find the best order to access those 10 tables, we need to consider 10! possible orders, roughly 3,000,000. It takes time to consider that many plans. The optimizer has techniques to cut this down, let me show one. If one table is referenced like this in the WHERE clause:
WHERE t.pk=39 AND ...
then, because “t.pk” is a primary key, I know that at most one row of this table will participate in the result, and it makes sense to read it with a primary key lookup. And this read has to be done only once in this execution. So let’s put “t” first in the plan, unconditionally. This technique, known as “constant tables”, divides the number of possible orders by a factor of 10 in our example (only 9 tables left to order). Now, imagine that the WHERE clause looks like this:
WHERE t.pk=39 AND t.c1>t2.c2
As soon as I read the row of “t” with a primary key lookup (looking up 39), I get access to the value of t.c1; say it is 100. My condition can thus be simplified to:
WHERE 100>t2.c2
Notice how the AND has disappeared.
The inequality predicate “100>t2.c2″ is interesting: assuming that t2.c2 is indexed, it means that a range scan is a possibility for reading t2.
This little example was meant to demonstrate that MySQL, in the optimization phase, does data-based transformations to the query: transformations which depend on the content of tables, and which apply for one single execution; indeed, when the next execution comes, it may be that the row of “t” with t.pk=39 now has t.c1=1200, so our condition simplifications don’t hold anymore. Another way to say this, is: data-based transformations must be non-permanent.
So the AND operator which was killed above during the optimization of the first EXECUTE, must be resurrected for the optimization of the second EXECUTE.
To achieve this, at the end of resolution we rename tree to permanent_tree, then we make a copy of it, which we name tree. The optimization phase has access to tree, and no access to permanent_tree. The optimization operates on tree, does data-based transformations on it. When the second EXECUTE starts, permanent_tree is fetched, copied into a new tree, on which the optimization operates. For example, the AND operator always exists in permanent_tree.

What about permanent transformations? For example, consider this query:

SELECT * FROM t1 JOIN (t2 JOIN t3 ON t2.a=t3.a) ON t2.b+t3.b>t1.b
WHERE t1.b*2>15;

The result of this query is defined by the SQL standard as: get the result of the most inner join (t2,t3), filter with t2.a=t3.a, then join the result with t1, filter with t2.b+t3.b>t1.b, then filter with t1.b*2>15. With this definition, the order of tables’ reading and the order of application of conditions are constrained. For example, reading t2 then t1 then t3 is not possible. But if we notice that the query is equivalent to:

SELECT * FROM t1, t2, t3 WHERE t2.a=t3.a AND t2.b+t3.b>t1.b
AND t1.b*2>15;

then we have 3! = 6 possible orders for tables. More plans to examine, but more potential for finding a good plan – it is very possible that the best plan, the one yielding the fastest execution, is not among the ones suggested by the SQL standard’s definition.
The equivalence between both queries is semantics-based, not data-based. Thus, the transformation from the first to the second query can be permanent: it can be done once for all, not at every EXECUTE.
Permanent transformations include:

JOIN-to-WHERE, like in the example above
outer-join-to-inner-join, when there is something in the WHERE clause which allows to deduce that NULL-complemented rows will actually not participate in the result
semi-join, more or less merging an “IN (subquery)” predicate into the parent query
IN-to-EXISTS, rewriting “x IN (subquery)” to “EXISTS (modified subquery)”.

After giving all this background (phew…), I’m now ready to explain one re-factoring which I did in MySQL 5.7.4. The situation of permanent transformations in MySQL 5.6 is the following:

IN-to-EXISTS : done in the resolution phase.
semi-join, JOIN-to-WHERE, outer-join-to-inner-join: done in the optimization phase.

Doing permanent transformations during optimization (step (2) above) is surprising, as optimization is re-done at every EXECUTE. Fortunately, we can internally know if an optimization is the first or not; if it’s not, we skip step (2).
So in the end, efficiency is guaranteed – permanent transformations are not re-done. Though this design agreeably looks strange.

Now, putting pieces together, on the way to more strangeness: you remember that after the resolution phase, we produce permanent_tree and save it for all future EXECUTEs. It thus contains permanent transformations done in resolution, good. But, it does not contain those done in optimization (semijoin …), as optimization runs after permanent_tree has been produced. Still we do want semi-join and friends to be reused by all future EXECUTEs, so they must be put in permanent_tree! So we get an even more strange design:

resolution
1. do some permanent transformations (IN-to-EXISTS) on tree
2. rename tree to permanent_tree
3. copy permanent_tree to a new tree (for optimization to do nonpermanent transformations on it)
optimization
1. if first optimization:
  1. do some more permanent transformations (semijoin, etc) on tree
  2. throw permanent_tree away
  3. copy tree to a new permanent_tree
2. do nonpermanent transformations on tree
execution
1. read tables and send rows
2. throw tree away

This has a few nasty effects:

permanent transformations are scattered: the boundary between phases is blurred, which is a code readability problem, and an impediment for future improvements in the Optimizer in general
efficiency loss: copying a tree in resolution phase takes some time and memory; in the first optimization we throw permanent_tree away and do the copying again… Bad.
real bugs. Yes, because what the resolution phase thinks of permanent_tree is not true anymore: this object has been deleted and replaced by another one, in the first optimization… so the next EXECUTE gets confused…

In MySQL 5.7.4, I have moved all permanent transformations to where they belong, so now we have the more straightforward design:

resolution
1. do all permanent transformations on tree
2. rename tree to permanent_tree
optimization
1. copy permanent_tree to a new tree (for optimization to do nonpermanent transformations on it)
2. do nonpermanent transformations on tree
execution
1. read tables and send rows
2. throw tree away

If we had done this re-factoring earlier, we would have saved us some headaches. But, better late than never. It’s at least comforting that nowadays we have time to do re-factoring, even if it means spending several man-months on a task like that. It really took that much time: the idea may look simple, but the devil was in the details as usual, and if you add, on top of coding time, review time by two reviewers, and QA time to verify that I didn’t break anything… But in my team we are convinced that this is a long-term investment which will pay. Moreover, when we do such re-factoring work, it gives us the occasion to remove the little hacks which accumulated over time to work around the root problem (which the re-factoring finally addresses). And that leads to even more code simplification.

There are a few more details in the Worklog page if you are interested (note the multiple tabs there).

That’s all for today. If you reached this line, congratulations :-)

Footnotes:
1. I hear you say: “what if an ALTER TABLE is done between PREPARE and EXECUTE?! This may change names and types of columns!”. Yes, you are right, but there exists, somewhere in the prepared statement subsystem, a detector for this; it runs when EXECUTE starts, and if it spots a table structure change since the statement was prepared, it throws away the prepared statement (as “out-of-date”), silently re-prepares it and then docks into EXECUTE; the user does not notice, except if she looks at com_stmt_reprepare in SHOW STATUS. This detector is external to the Optimizer and runs before it; so if the Optimizer is involved in EXECUTE, it can safely assume that nothing has changed since PREPARE.
2. Ok, a part of resolution is repeated too. It would be good to avoid that, in the future.

The range access method and why you should use EXPLAIN JSON

Jørgen Løland — Fri, 28 Mar 2014 13:59:00 +0000

I got an interesting question about EXPLAIN and the range access method recently. The person had a query that could be written either with a BETWEEN predicate or an IN predicate, something similar to this:

mysql> EXPLAIN SELECT * 
    -> FROM orders WHERE customer_id BETWEEN 7 AND 10 AND value > 500;
+----+-------------+--------+-------+----------+----------+------+------
| id | select_type | table  | type  | key      | key_len  | rows | Extra
+----+-------------+--------+-------+----------+----------+------+------
|  1 | SIMPLE      | orders | range | cust_val | 10       |   91 |  ...
+----+-------------+--------+-------+----------+----------+------+------

mysql> EXPLAIN SELECT * 
    -> FROM orders WHERE customer_id IN (7,8,9,10) AND value > 500;
+----+-------------+--------+-------+----------+----------+------+------
| id | select_type | table  | type  | key      | key_len  | rows | Extra
+----+-------------+--------+-------+----------+----------+------+------
|  1 | SIMPLE      | orders | range | cust_val | 10       |   44 |  ...
+----+-------------+--------+-------+----------+----------+------+------

The table was:

CREATE TABLE orders (

order_id INT NOT NULL PRIMARY KEY,

customer_id INT,

value INT,

order_date DATE,

KEY custid_value (customer_id, value)

)

Given that customer_id is an integer value, these queries should be equivalent. And that's what EXPLAIN seems to tell us too: same access method, same key, same key_length etc.

You may have guessed the question by now: If the queries are equivalent, why isn't the rows estimate identical? Is one of the numbers wrong or do these queries have different execution plans after all?

Read more »

Range access: now in an IN predicate near you.

Martin — Tue, 10 Dec 2013 07:42:00 +0000

Several users have reported that certain queries with IN predicates can't use index scans even though all the columns in the query are indexed. What's worse, if you reformulate your query without IN, the indexes are used. Let's take some example query. Suppose we have a table with two indexed columns:

CREATE TABLE t1 (
col1 INTEGER,
col2 INTEGER,
...

KEY key1( col1, col2 )

);

Let's take a look at some queries that could take advantage of the key1 index to read rows without accessing the table.

SELECT col1, col2 FROM t1 WHERE col1 = 100;
SELECT col1, col2 FROM t1 WHERE col1 > 100 AND col1 < 200;
SELECT col1, col2 FROM t1 WHERE col1 > 100 AND col1 < 200 OR col1 > 300 AND col1 < 400;
SELECT col1, col2 FROM t1 WHERE col1 = 100 AND col2 > 100 AND cold2 < 200;

These queries will use what MySQL calls Index Range Scans. (although the first query could also use Ref Scan). This access method will fetch rows from the index trees given a start and end value. It's also possible to read multiple intervals, each with a start and end value, as we saw in query 3 above.

A special case of intervals is when the endpoints are the same value. Range scans can be used for conditions such as col1 = 100 because it's equivalent to the interval 100 <= col1 <= 100. This way we can use range scans for a broader class of queries.

Armed with multiple-interval scans, a.k.a. multi-range reads, or MRR for short, we can use the range access for queries such as

SELECT col1, col2 FROM t1

WHERE col1 = 100 or col1 = 200 or col1 = 300;

We can use all columns in the index of course:

SELECT col1, col2 FROM t1

WHERE col1 = 100 AND col2 = 100

OR col1 = 200 AND col2 = 200

OR col1 = 300 AND col2 = 300;

At some point, this syntax becomes unwieldy. And this isn't just aesthetics, for really big queries, we get a combinatorial blowup which can cause parsing to take a long time. This is the reason why SQL has IN predicates to say the same thing:

SELECT col1, col2 FROM t1

WHERE col1 = 100 OR col2 = 200 OR col2 = 300;

means the same as

SELECT col1, col2 FROM t1

WHERE col1 IN (100, 200, 300);

And for rows it gets even more convenient:

SELECT col1, col2 FROM t1

WHERE col1 = 100 AND col2 = 100

OR col1 = 200 AND col2 = 200

OR col1 = 300 AND col2 = 300;

can be written as

SELECT col1, col2 FROM t1

WHERE (col1, col2) IN ((100, 100), (200, 200), (300, 300));

The problem that users saw is that suddenly MySQL doesn't use MRR any more, and resorts to scanning the entire index. This is because the range optimizer ignored IN conditions over rows. The range optimizer is the sub-optimizer that analyzes conditions and translates them into a multi-range structure that can be handed to the storage engine to fetch the rows from the index. It handled IN predicates as long as they were over scalars or just a single row, but completely ignored lists of rows.

As of 5.7.3 this hole in the net is stitched up. The range optimizer gladly opens the door for queries with IN predicates as long as

The predicate is only IN, not NOT IN.
The row on the predicate's left-hand side is only indexed column references, in the same index.
The rows contain only constants or come from a previously read table in nested-loops join.

Note that 'constants' is a pretty broad category. It consists of pre-evaluated expressions, even some sub-queries, SQL variables and similar beings.

WITH RECURSIVE and MySQL

Guilhem Bichot — Mon, 18 Nov 2013 06:17:00 +0000

If you have been using certain DBMSs, or reading recent versions of the SQL standard, you are probably aware of the so-called "WITH clause" of SQL.
Some call it Subquery Factoring. Others call it Common Table Expression.
In its simplest form, this feature is a kind of "boosted derived table".

Assume that a table T1 has three columns:


CREATE TABLE T1(
YEAR INT, # 2000, 2001, 2002 ...
MONTH INT, # January, February, ...
SALES INT # how much we sold on that month of that year
);

Now I want to know the sales trend (increase/decrease), year after year:


SELECT D1.YEAR, (CASE WHEN D1.S>D2.S THEN 'INCREASE' ELSE 'DECREASE' END) AS TREND
FROM
  (SELECT YEAR, SUM(SALES) AS S FROM T1 GROUP BY YEAR) AS D1,
  (SELECT YEAR, SUM(SALES) AS S FROM T1 GROUP BY YEAR) AS D2
WHERE D1.YEAR = D2.YEAR-1;

Both derived tables are based on the same subquery text, but usually a DBMS is not smart enough to recognize it. Thus, it will evaluate "SELECT YEAR, SUM(SALES)... GROUP BY YEAR" twice! A first time to fill D1, a second time to fill D2. This limitation is sometimes stated as "it's not possible to refer to a derived table twice in the same query".
Such double evaluation can lead to a serious performance problem. Using WITH, this limitation does not exist, and the following statement evaluates the subquery only once:


WITH D AS (SELECT YEAR, SUM(SALES) AS S FROM T1 GROUP BY YEAR)
SELECT D1.YEAR, (CASE WHEN D1.S>D2.S THEN 'INCREASE' ELSE 'DECREASE' END) AS TREND
FROM
 D AS D1,
 D AS D2
WHERE D1.YEAR = D2.YEAR-1;

This already demonstrates one benefit of WITH.
In MySQL, WITH is not yet supported. But it can be emulated with a view:


CREATE VIEW D AS (SELECT YEAR, SUM(SALES) AS S FROM T1 GROUP BY YEAR);
SELECT D1.YEAR, (CASE WHEN D1.S>D2.S THEN 'INCREASE' ELSE 'DECREASE' END) AS TREND
FROM
 D AS D1,
 D AS D2
WHERE D1.YEAR = D2.YEAR-1;
DROP VIEW D;

Instead of a view, I could as well create D as a normal table. But not as a temporary table, because in MySQL a temporary table cannot be referred twice in the same query, as mentioned in the manual.

After this short introduction, showing the simplest form of WITH, I would like to turn to the more complex form of WITH: the RECURSIVE form.
According to the SQL standard, to use the recursive form, you should write WITH RECURSIVE. However, looking at some other DBMSs, they seem to not require the RECURSIVE word.
WITH RECURSIVE is a powerful construct. For example, it can do the same job as Oracle's CONNECT BY clause (you can check out some example conversions between both constructs).
Let's walk through an example, to understand what WITH RECURSIVE does.

Assume you have a table of employees (this is a very classical example of WITH RECURSIVE):


CREATE TABLE EMPLOYEES (
ID INT PRIMARY KEY,
NAME VARCHAR(100),
MANAGER_ID INT,
INDEX (MANAGER_ID),
FOREIGN KEY (MANAGER_ID) REFERENCES EMPLOYEES(ID)
);
INSERT INTO EMPLOYEES VALUES
(333, "Yasmina", NULL),
(198, "John", 333),
(29, "Pedro", 198),
(4610, "Sarah", 29),
(72, "Pierre", 29),
(692, "Tarek", 333);

In other words, Yasmina is CEO, John and Tarek report to her. Pedro reports to John, Sarah and Pierre report to Pedro.
In a big company, they would be thousands of rows in this table.

Now, let's say that you would like to know, for each employee: "how many people are, directly and indirectly, reporting to him/her"? Here is how I would do it. First, I would make a list of people who are not managers: with a subquery I get the list of all managers, and using NOT IN (subquery) I get the list of all non-managers:


SELECT ID, NAME, MANAGER_ID, 0 AS REPORTS
FROM EMPLOYEES
WHERE ID NOT IN (SELECT MANAGER_ID FROM EMPLOYEES WHERE MANAGER_ID IS NOT NULL);

Then I would insert the results into a new table named EMPLOYEES_EXTENDED; EXTENDED stands for "extended with more information", the new information being the fourth column named REPORTS: it is a count of people who are reporting directly or indirectly to the employee. Because we have listed people who are not managers, they have a value of 0 in the REPORTS column.
Then, we can produce the rows for "first level" managers (the direct managers of non-managers):


SELECT M.ID, M.NAME, M.MANAGER_ID, SUM(1+E.REPORTS) AS REPORTS
FROM EMPLOYEES M JOIN EMPLOYEES_EXTENDED E ON M.ID=E.MANAGER_ID
GROUP BY M.ID, M.NAME, M.MANAGER_ID;

Explanation: for a row of M (that is, for an employee), the JOIN will produce zero or more rows, one per non-manager directly reporting to the employee.
Each such non-manager contributes to the value of REPORTS for his manager, through two numbers: 1 (the non-manager himself), and the number of direct/indirect reports of the non-manager (i.e. the value of REPORTS for the non-manager).
Then I would empty EMPLOYEES_EXTENDED, and fill it with the rows produced just above, which describe the first level managers.
Then the same query should be run again, and it would produce information about the "second level" managers. And so on.
Finally, at one point Yasmina will be the only row of EMPLOYEES_EXTENDED, and when we run the above SELECT again, the JOIN will produce no rows, because E.MANAGER_ID will be NULL (she's the CEO). We are done.

It's time for a recap: EMPLOYEES_EXTENDED has been a kind of "temporary buffer", which has successively held non-managers, first level managers, second level managers, etc. We have used recursion. The answer to the original problem is: the union of all the successive content of EMPLOYEES_EXTENDED.
Non-managers have been the start of the recursion, which is usually called "the anchor member" or "the seed". The SELECT query which moves from one step of recursion to the next one, is the "recursive member". The complete statement looks like this:


WITH RECURSIVE
# The temporary buffer, also used as UNION result:
EMPLOYEES_EXTENDED
AS
(
  # The seed:
  SELECT ID, NAME, MANAGER_ID, 0 AS REPORTS
  FROM EMPLOYEES
  WHERE ID NOT IN (SELECT MANAGER_ID FROM EMPLOYEES WHERE MANAGER_ID IS NOT NULL)
UNION ALL
  # The recursive member:
  SELECT M.ID, M.NAME, M.MANAGER_ID, SUM(1+E.REPORTS) AS REPORTS
  FROM EMPLOYEES M JOIN EMPLOYEES_EXTENDED E ON M.ID=E.MANAGER_ID
  GROUP BY M.ID, M.NAME, M.MANAGER_ID
)
# what we want to do with the complete result (the UNION):
SELECT * FROM EMPLOYEES_EXTENDED;

MySQL does not yet support WITH RECURSIVE, but it is possible to code a generic stored procedure which can easily emulate it. Here is how you would call it:


CALL WITH_EMULATOR(
"EMPLOYEES_EXTENDED",
"
  SELECT ID, NAME, MANAGER_ID, 0 AS REPORTS
  FROM EMPLOYEES
  WHERE ID NOT IN (SELECT MANAGER_ID FROM EMPLOYEES WHERE MANAGER_ID IS NOT NULL)
",
"
  SELECT M.ID, M.NAME, M.MANAGER_ID, SUM(1+E.REPORTS) AS REPORTS
  FROM EMPLOYEES M JOIN EMPLOYEES_EXTENDED E ON M.ID=E.MANAGER_ID
  GROUP BY M.ID, M.NAME, M.MANAGER_ID
",
"SELECT * FROM EMPLOYEES_EXTENDED",
0,
""
);

You can recognize, as arguments of the stored procedure, every member of the WITH standard syntax: name of the temporary buffer, query for the seed, query for the recursive member, and what to do with the complete result. The last two arguments - 0 and the empty string - are details which you can ignore for now.

Here is the result returned by this stored procedure:


+------+---------+------------+---------+
| ID   | NAME    | MANAGER_ID | REPORTS |
+------+---------+------------+---------+
|   72 | Pierre  |         29 |       0 |
|  692 | Tarek   |        333 |       0 |
| 4610 | Sarah   |         29 |       0 |
|   29 | Pedro   |        198 |       2 |
|  333 | Yasmina |       NULL |       1 |
|  198 | John    |        333 |       3 |
|  333 | Yasmina |       NULL |       4 |
+------+---------+------------+---------+
7 rows in set

Notice how Pierre, Tarek and Sarah have zero reports, Pedro has two, which looks correct... However, Yasmina appears in two rows! Odd? Yes and no. Our algorithm starts from non-managers, the "leaves" of the tree (Yasmina being the root of the tree). Then our algorithm looks at first level managers, the direct parents of leaves. Then at second level managers. But Yasmina is both a first level manager (of the nonmanager Tarek) and a third level manager (of the nonmanagers Pierre, Tarek and Sarah). That's why she appears twice in the final result: once for the "tree branch" which ends at leaf Tarek, once for the tree branch which ends at leaves Pierre, Tarek and Sarah. The first tree branch contributes 1 direct/indirect report. The second tree branch contributes 4. The right number, which we want, is the sum of the two: 5. Thus we just need to change the final query, in the CALL:


CALL WITH_EMULATOR(
"EMPLOYEES_EXTENDED",
"
  SELECT ID, NAME, MANAGER_ID, 0 AS REPORTS
  FROM EMPLOYEES
  WHERE ID NOT IN (SELECT MANAGER_ID FROM EMPLOYEES WHERE MANAGER_ID IS NOT NULL)
",
"
  SELECT M.ID, M.NAME, M.MANAGER_ID, SUM(1+E.REPORTS) AS REPORTS
  FROM EMPLOYEES M JOIN EMPLOYEES_EXTENDED E ON M.ID=E.MANAGER_ID
  GROUP BY M.ID, M.NAME, M.MANAGER_ID
",
"
  SELECT ID, NAME, MANAGER_ID, SUM(REPORTS)
  FROM EMPLOYEES_EXTENDED
  GROUP BY ID, NAME, MANAGER_ID
",
0,
""
);

And here is finally the proper result:


+------+---------+------------+--------------+
| ID   | NAME    | MANAGER_ID | SUM(REPORTS) |
+------+---------+------------+--------------+
|   29 | Pedro   |        198 |            2 |
|   72 | Pierre  |         29 |            0 |
|  198 | John    |        333 |            3 |
|  333 | Yasmina |       NULL |            5 |
|  692 | Tarek   |        333 |            0 |
| 4610 | Sarah   |         29 |            0 |
+------+---------+------------+--------------+
6 rows in set

Let's finish by showing the body of the stored procedure. You will notice that it does heavy use of dynamic SQL, thanks to prepared statements. Its body does not depend on the particular problem to solve, it's reusable as-is for other WITH RECURSIVE use cases. I have added comments inside the body, so it should be self-explanatory. If it's not, feel free to drop a comment on this post, and I will explain further.


# Usage: the standard syntax:
#   WITH RECURSIVE recursive_table AS
#    (initial_SELECT
#     UNION ALL
#     recursive_SELECT)
#   final_SELECT;
# should be translated by you to 
# CALL WITH_EMULATOR(recursive_table, initial_SELECT, recursive_SELECT,
#                    final_SELECT, 0, "").

# ALGORITHM:
# 1) we have an initial table T0 (actual name is an argument
# "recursive_table"), we fill it with result of initial_SELECT.
# 2) We have a union table U, initially empty.
# 3) Loop:
#   add rows of T0 to U,
#   run recursive_SELECT based on T0 and put result into table T1,
#   if T1 is empty
#      then leave loop,
#      else swap T0 and T1 (renaming) and empty T1
# 4) Drop T0, T1
# 5) Rename U to T0
# 6) run final select, send relult to client

# This is for *one* recursive table.
# It would be possible to write a SP creating multiple recursive tables.

delimiter |

CREATE PROCEDURE WITH_EMULATOR(
recursive_table varchar(100), # name of recursive table
initial_SELECT varchar(65530), # seed a.k.a. anchor
recursive_SELECT varchar(65530), # recursive member
final_SELECT varchar(65530), # final SELECT on UNION result
max_recursion int unsigned, # safety against infinite loop, use 0 for default
create_table_options varchar(65530) # you can add CREATE-TABLE-time options
# to your recursive_table, to speed up initial/recursive/final SELECTs; example:
# "(KEY(some_column)) ENGINE=MEMORY"
)

BEGIN
  declare new_rows int unsigned;
  declare show_progress int default 0; # set to 1 to trace/debug execution
  declare recursive_table_next varchar(120);
  declare recursive_table_union varchar(120);
  declare recursive_table_tmp varchar(120);
  set recursive_table_next  = concat(recursive_table, "_next");
  set recursive_table_union = concat(recursive_table, "_union");
  set recursive_table_tmp   = concat(recursive_table, "_tmp");
  # If you need to reference recursive_table more than
  # once in recursive_SELECT, remove the TEMPORARY word.
  SET @str = # create and fill T0
    CONCAT("CREATE TEMPORARY TABLE ", recursive_table, " ",
    create_table_options, " AS ", initial_SELECT);
  PREPARE stmt FROM @str;
  EXECUTE stmt;
  SET @str = # create U
    CONCAT("CREATE TEMPORARY TABLE ", recursive_table_union, " LIKE ", recursive_table);
  PREPARE stmt FROM @str;
  EXECUTE stmt;
  SET @str = # create T1
    CONCAT("CREATE TEMPORARY TABLE ", recursive_table_next, " LIKE ", recursive_table);
  PREPARE stmt FROM @str;
  EXECUTE stmt;
  if max_recursion = 0 then
    set max_recursion = 100; # a default to protect the innocent
  end if;
  recursion: repeat
    # add T0 to U (this is always UNION ALL)
    SET @str =
      CONCAT("INSERT INTO ", recursive_table_union, " SELECT * FROM ", recursive_table);
    PREPARE stmt FROM @str;
    EXECUTE stmt;
    # we are done if max depth reached
    set max_recursion = max_recursion - 1;
    if not max_recursion then
      if show_progress then
        select concat("max recursion exceeded");
      end if;
      leave recursion;
    end if;
    # fill T1 by applying the recursive SELECT on T0
    SET @str =
      CONCAT("INSERT INTO ", recursive_table_next, " ", recursive_SELECT);
    PREPARE stmt FROM @str;
    EXECUTE stmt;
    # we are done if no rows in T1
    select row_count() into new_rows;
    if show_progress then
      select concat(new_rows, " new rows found");
    end if;
    if not new_rows then
      leave recursion;
    end if;
    # Prepare next iteration:
    # T1 becomes T0, to be the source of next run of recursive_SELECT,
    # T0 is recycled to be T1.
    SET @str =
      CONCAT("ALTER TABLE ", recursive_table, " RENAME ", recursive_table_tmp);
    PREPARE stmt FROM @str;
    EXECUTE stmt;
    # we use ALTER TABLE RENAME because RENAME TABLE does not support temp tables
    SET @str =
      CONCAT("ALTER TABLE ", recursive_table_next, " RENAME ", recursive_table);
    PREPARE stmt FROM @str;
    EXECUTE stmt;
    SET @str =
      CONCAT("ALTER TABLE ", recursive_table_tmp, " RENAME ", recursive_table_next);
    PREPARE stmt FROM @str;
    EXECUTE stmt;
    # empty T1
    SET @str =
      CONCAT("TRUNCATE TABLE ", recursive_table_next);
    PREPARE stmt FROM @str;
    EXECUTE stmt;
  until 0 end repeat;
  # eliminate T0 and T1
  SET @str =
    CONCAT("DROP TEMPORARY TABLE ", recursive_table_next, ", ", recursive_table);
  PREPARE stmt FROM @str;
  EXECUTE stmt;
  # Final (output) SELECT uses recursive_table name
  SET @str =
    CONCAT("ALTER TABLE ", recursive_table_union, " RENAME ", recursive_table);
  PREPARE stmt FROM @str;
  EXECUTE stmt;
  # Run final SELECT on UNION
  SET @str = final_SELECT;
  PREPARE stmt FROM @str;
  EXECUTE stmt;
  # No temporary tables may survive:
  SET @str =
    CONCAT("DROP TEMPORARY TABLE ", recursive_table);
  PREPARE stmt FROM @str;
  EXECUTE stmt;
  # We are done :-)
END|

delimiter ;

In the SQL Standard, WITH RECURSIVE allows some nice additional tweaks (depth-first or breadth-first ordering, cycle detection). In future posts I will show how to emulate them too.

FAQ: InnoDB extended secondary keys

Jørgen Løland — Mon, 21 Oct 2013 13:11:00 +0000

MySQL 5.6 introduced a new feature called extended secondary keys. We get a lot of questions about it and find that most of them come from a few incorrect assumption. In this post I'll try to get rid of the confusion once and for all. Famous last words... here goes:

Q1: Do I need to do anything to enable extended secondary keys?

No, nothing at all. It's on by default and I can't see any sensible reason why you would want to disable it. However, it is possible to disable it by tuning the optimizer_switch: SET optimizer_switch='use_index_extensions={on|off}'.

Q2: Does extended secondary keys only work with InnoDB?

No, it should work with any storage engine that uses the primary key columns as reference to the row, which means most storage engines with clustered primary keys. I say "should" because it requires a minimum of work from the storage engine provider; it must announce to MySQL that it is supported.

Read more »

The second MySQL seminar: a summary

Jørgen Løland — Fri, 18 Oct 2013 13:02:00 +0000

Once again, Geir Høydalsvik and I had the pleasure of hosting a MySQL mini-seminar in Trondheim. 25+ attendants from at least 7 different companies and a few professors from the computer science dept. at NTNU showed up on yesterdays event. I recognized many of these from the first seminar but there were some new faces as well.

This time, Mark Leith came on a visit from the UK. He gave an introduction to Performance Schema and ps_helper. ps_helper is a really nice tool to make sense of the overwhelming amount of data collected by PS. He also gave a very convincing demo of MySQL Enterprise Monitor (MEM). More than a few attendants now plan to give MEM a try in their environment. You can too - there's a 30 day trial, which should be more than enough to decide if you need it :-)

Like last time, we had great discussions, pizza and a very good time. I'm looking forward to the next seminar already.

If you're interested, Mark's PS presentation can be found on slideshare. ps_helper is both on github and on his blog. ps_helper comes highly recommended!

Next MySQL mini-seminar in Trondheim October 17

Jørgen Løland — Fri, 13 Sep 2013 14:21:00 +0000

We have the pleasure to announce that the next MySQL mini-seminar in Trondheim will be held on October 17 15:00-18:00. This time, MySQL Monitoring and performance schema evangelist Mark Leith will visit us. The agenda will be similar to last mini-seminar:

Presentation: MySQL monitoring and performance Schema, by Mark Leith
Q&A, discussions
Suggestions for presentations on future seminars
Food and mingling

For more info, see the registration page.

Don't miss this opportunity to meet experts, developers and other MySQL users.

The first MySQL mini-seminar in Trondheim was a huge success!

Jørgen Løland — Thu, 20 Jun 2013 11:16:00 +0000

Yesterday, Geir Høydalsvik and I had the pleasure of hosting a MySQL mini-seminar in Trondheim, Norway.

The topic of the day was a presentation by yours truly on how the MySQL optimizer works. Geir briefly explained how the MySQL teams are organized in Oracle, and that our focus is on delivering high quality on time.

We had lots of interesting questions and discussions (and pizza) afterwards. Of particular interest was:

How the MySQL code base can be modularized to make it maintainable and testable. The takeaway was that MySQL has invested a lot on refactoring the last couple of years to improve in this area and will continue to do so in both the near and far future.
How testing is done in MySQL. The answer was that the QA teams have been significantly ramped up since Sun acquired MySQL. In addition to much more resources to the QA teams, developers are now expected to write unit tests using the Google unit test framework for new functionality whenever it makes sense. Refactoring and modularization of the code makes this a lot easier to do now.

Close to 20 MySQL users attended in addition to a handful of MySQL hackers located in the Trondheim office. The users had very different backgrounds: from start-ups to solid established companies, and deployment on MySQL 5.1, 5.5 and 5.6. All agreed that the mini-seminar was a great initiative and that it should not be a one-time event. Yesterday's event will therefore not be the mini-seminar, but rather the first in a series.

We'll get back to you with agenda and date for the next mini-seminar once the details have been decided.

The Outer Join to Inner Join Coversion

Martin — Wed, 15 May 2013 05:41:00 +0000

It is a central part of the MySQL philisophy to try and help you as much as you can. There are many occasions when it could tell you that what you are asking for is utterly stupid or give you a bad execution plan because "you asked for it". But we're friendly here. We don't do that. One of those cases is when you run a query with an outer join but you really meant an inner join, or you don't care.

Inner joins are almost always cheaper to execute than outer joins and that is why MySQL rewrites them to inner joins whenever it can.

An outer join may have WHERE conditions on any of the columns in the result set. In fact, it is a common trick to find non-matching rows using the IS NULL predicate. Here's an example:

TABLE person

name id
Tom 1
Dick 2
Harry 3

TABLE car

brand owner_id mfg_year
Chevy 1 2007
Volvo 3 2008

The query SELECT name FROM person LEFT OUTER JOIN car ON id = owner_id WHERE brand IS NULL would give you the names of people that don't have a car. The IS NULL predicate is TRUE for an UNKNOWN value. Nearly all other predicates are what we refer to as null-rejecting. A null-rejecting predicate is one that is UNKNOWN if any of its arguments is UNKNOWN. This goes for most SQL predicates: >, <, =.

On the top-level of the where clause, there is an implicit IS TRUE predicate. This way you never get to see rows where it is unknown if they match your search condition or not. So the where clause in our query above is equivalent to

WHERE brand IS NULL IS TRUE

We could also query

SELECT name
FROM person LEFT OUTER JOIN car ON id = owner_id
WHERE mfg_year = 2008 IS UNKNOWN

The result of which would be "Dick", because it is indeed unknown if Dick's car was made in 2008 if he doesn't have a car. Computation wise, the condition is evaluated bottom-up: UNKNOWN = 2008 is UNKNOWN.

We are now ready to turn this notion into a rule-of-thumb: If there are predicates in the where clause that are not nested inside predicates that turn UNKNOWN into TRUE, for example IS NULL or IS UNKNOWN (i.e. null-rejecting), then we can turn the outer join into an inner join before we optimize, because the result set is the same. Unfortunately this translation does not show up in EXPLAIN, but it does in the optimizer trace. Here's how to see it.

SET optimizer_trace="enabled=on";

SELECT name
FROM person LEFT OUTER JOIN car ON id = owner_id
WHERE mfg_year = 2008;
+-------+
| name |
+-------+
| Harry |
+-------+
SELECT trace FROM information_schema.optimizer_trace;
...

{
"join_optimization": {
"select#": 1,
"steps": [
{
"transformations_to_nested_joins": {
"transformations": [
"outer_join_to_inner_join",
"JOIN_condition_to_WHERE",
"parenthesis_removal"
],
"expanded_query": "/* select#1 */ select `person`.`name` AS `name` from `person` join `car` where ((`car`.`mfg_year` = 2008) and (`person`.`id` = `car`.`owner_id`))"

...

When is a Subquery Executed?

Øystein — Thu, 02 May 2013 14:17:00 +0000

In an earlier blog post, I managed to confuse myself as to when a subquery was executed. It is not very clear from the output of EXPLAIN where the execution of a subquery takes place. Let's take a look at the following example query (Query 17 in the DBT-3 benchmark):

select sum(l_extendedprice) / 7.0 as avg_yearly
from lineitem, part
where p_partkey = l_partkey
  and p_brand = 'Brand#33' and p_container = 'LG CAN'
  and l_quantity < (
 select 0.2 * avg(l_quantity)
 from lineitem
 where l_partkey = p_partkey
);

If you run EXPLAIN on this query, you will see the following execution plan:

+----+--------------------+----------+------+---------------------------------+---------------------+---------+---------------------+---------+-------------+
| id | select_type        | table    | type | possible_keys                   | key                 | key_len | ref                 | rows    | Extra       |
+----+--------------------+----------+------+---------------------------------+---------------------+---------+---------------------+---------+-------------+
|  1 | PRIMARY            | part     | ALL  | PRIMARY                         | NULL                | NULL    | NULL                | 2000000 | Using where |
|  1 | PRIMARY            | lineitem | ref  | i_l_suppkey_partkey,i_l_partkey | i_l_suppkey_partkey | 5       | dbt3.part.p_partkey |      14 | Using where |
|  2 | DEPENDENT SUBQUERY | lineitem | ref  | i_l_suppkey_partkey,i_l_partkey | i_l_suppkey_partkey | 5       | dbt3.part.p_partkey |      14 | NULL        |
+----+--------------------+----------+------+---------------------------------+---------------------+---------+---------------------+---------+-------------+

It is not straightforward to determine from this plan when the subquery will be executed. We see that both tables of the join has "Using where" in the Extra column. In other words, the original WHERE clause has been split between the two tables. The question is: Which part contains the subquery?

In this specific case, the answer is pretty evident when looking closer at the query. The subquery is part of an expression which refers to a column of the lineitem table, l_quantity, and within the subquery, there is also also a reference to p_partkey of the part table. In other words, columns from both tables of the join is needed when executing the subqquery. Hence, the subquery will be part of the where clause attached to the last table of the join.

This means that the above query will, for each row in the part table that satisfies the condition attached to the part table, look up matching rows in the lineitem table, and, for every matching row, execute the subquery. As you probably realize, one will have to know quite a bit about how the optimizer handles WHERE conditions in order to deduce this. But don't despair! An extension to EXPLAIN in MySQL 5.6 make things much clearer.

Structured EXPLAIN

With MySQL 5.6, you can get a structured version of the query plan in JSON format. All you need to do is to write "EXPLAIN FORMAT=JSON" instead of just EXPLAIN. Let's take a look at what the JSON EXPLAIN output for the query discussed above looks like:

{
  "query_block": {
    "select_id": 1,
    "nested_loop": [
      {
        "table": {
          "table_name": "part",
          "access_type": "ALL",
          "possible_keys": [
            "PRIMARY"
          ] /* possible_keys */,
          "rows": 2000000,
          "filtered": 100,
          "attached_condition": "((`dbt3`.`part`.`p_container` = 'LG CAN') and (`dbt3`.`part`.`p_brand` = 'Brand#33'))"
        } /* table */
      },
      {
        "table": {
          "table_name": "lineitem",
          "access_type": "ref",
          "possible_keys": [
            "i_l_suppkey_partkey",
            "i_l_partkey"
          ] /* possible_keys */,
          "key": "i_l_suppkey_partkey",
          "used_key_parts": [
            "l_partkey"
          ] /* used_key_parts */,
          "key_length": "5",
          "ref": [
            "dbt3.part.p_partkey"
          ] /* ref */,
          "rows": 14,
          "filtered": 100,
          "attached_condition": "(`dbt3`.`lineitem`.`l_quantity` < (/* select#2 */ select (0.2 * avg(`dbt3`.`lineitem`.`l_quantity`)) from `dbt3`.`lineitem` where (`dbt3`.`lineitem`.`l_partkey` = `dbt3`.`part`.`p_partkey`)))",
          "attached_subqueries": [
            {
              "dependent": true,
              "cacheable": false,
              "query_block": {
                "select_id": 2,
                "table": {
                  "table_name": "lineitem",
                  "access_type": "ref",
                  "possible_keys": [
                    "i_l_suppkey_partkey",
                    "i_l_partkey"
                  ] /* possible_keys */,
                  "key": "i_l_suppkey_partkey",
                  "used_key_parts": [
                    "l_partkey"
                  ] /* used_key_parts */,
                  "key_length": "5",
                  "ref": [
                    "dbt3.part.p_partkey"
                  ] /* ref */,
                  "rows": 14,
                  "filtered": 100
                } /* table */
              } /* query_block */
            }
          ] /* attached_subqueries */
        } /* table */
      }
    ] /* nested_loop */
  } /* query_block */
}

You probably recognize much of the information from traditional EXPLAIN, but there is also some information that traditional EXPLAIN do not show. The "attached_condition" field shows which parts of the WHERE condition is evaluated at which stage of the query execution. That is, the condition attached to a table will be evaluated for each row that is read from this table. In this specific example, it shows that the subquery is part of the condition attached to the lineitem table, and the "attached_subqueries" field for that table contains the execution plan for the subquery.

Visual EXPLAIN

Structured EXPLAIN, or EXPLAIN in JSON format, is also much more suitable for tools that want to process and display query plans. MySQL Workbench 5.2 uses structural EXPLAIN to visualize MySQL query plans. Below is shown the result of Visual EXPLAIN for the example query used in this blog post:

Note that MySQL Workbench colors the table boxes based on which access method is used. A red box indicates a tables scan, while a green box is used for index look-ups (ref access).

As we all know: "A picture is worth a thousand words", and from the above picture it should be pretty clear when the subquery is executed.

When and How to Take Advantage of New Optimizer Features in MySQL 5.6

Øystein — Fri, 22 Feb 2013 19:08:00 +0000

A few weeks ago, I made a presentation with the above title at FOSDEM in Brussels. My slides can be found here. The MySQL and Friends devroom had many interesting presentations and the room was full for most of them.

Fixing awkward TIMESTAMP behaviors...

Guilhem Bichot — Tue, 19 Feb 2013 08:12:00 +0000

There are great features in MySQL 5.6. But not only that. We also tried to correct some old behaviors and limitations which, over the years, have shown to irritate our Community. The behavior of TIMESTAMP columns is one of them.

My colleague Martin Hansson did most of the work and summarized it well in his blog. Thanks to him, since MySQL 5.6.5, it's possible to declare more than one TIMESTAMP column with the DEFAULT CURRENT_TIMESTAMP or ON UPDATE CURRENT_TIMESTAMP attributes. And it's possible to have DATETIME columns with such attributes. Two limitations lifted!

But that is not the end of the story. TIMESTAMP was still special. Unlike other datatypes, if not declared with the NULL or NOT NULL attributes, it would automatically get NOT NULL. And the first TIMESTAMP column of the table would automatically get DEFAULT CURRENT_TIMESTAMP ON UPDATE CURRENT_TIMESTAMP. Many people found these behaviors odd. For them, my colleague Gopal Shankar added a new option to the server, documented here. The old behavior, now depreciated, is still available if the option is not used.

But that is still not the end of the story. "CREATE TABLE ... SELECT" dealt strangely with columns having DEFAULT CURRENT_TIMESTAMP. Just look at this simple example, which shows results with version 5.6.9:


CREATE TABLE t1 (
t1a TIMESTAMP DEFAULT CURRENT_TIMESTAMP,
t1b TIMESTAMP DEFAULT '2000-01-01 01:00:00'
);
INSERT INTO t1 VALUES ();
SELECT * FROM t1;
t1a t1b
2013-02-19 18:12:41 2000-01-01 01:00:00

The content of t1 is as expected (remember that "()" in INSERT means "insert columns' defaults").
Now let's create a second table, which should have four columns: first, two extra columns t2a and t2b, then two columns filled with values selected from t1:


CREATE TABLE t2 (
t2a TIMESTAMP DEFAULT CURRENT_TIMESTAMP,
t2b TIMESTAMP DEFAULT '2000-01-01 02:00:00'
) SELECT * FROM t1;
SHOW CREATE TABLE t2;
Table Create Table
t2 CREATE TABLE `t2` (
  `t2a` timestamp NOT NULL DEFAULT CURRENT_TIMESTAMP,
  `t2b` timestamp NOT NULL DEFAULT '2000-01-01 02:00:00',
  `t1a` timestamp NOT NULL DEFAULT '0000-00-00 00:00:00',
  `t1b` timestamp NOT NULL DEFAULT '2000-01-01 01:00:00'
) ENGINE=InnoDB DEFAULT CHARSET=latin1

See how t2.t1b inherited the DEFAULT attribute of its source column t1.t1b: DEFAULT '2000-01-01 01:00:00', as expected, and as the documentation says. But! t2.t1a did NOT inherit the DEFAULT attribute of its source column t1.t1a: it rather got the strange DEFAULT '0000-00-00 00:00:00' (year zero...). That's one first problem: constant defaults are properly inherited, but function defaults are not.
Now let's look at the content of t2:


SELECT * FROM t2;
t2a t2b t1a t1b
0000-00-00 00:00:00 2000-01-01 02:00:00 2013-02-19 18:12:41 2000-01-01 01:00:00

The last two columns, which have their source in t1, have the same value as their source column, which is correct.
The two first (extra) columns did not have their values specified, so their default should have been inserted. That's what nicely happened for t2b. But not for t2a: year zero again! That's one second problem: an extra column is not filled with its default if it is a function default.

I grouped those two problems under the name of Bug#16163936, and fixed them. Here are the results in 5.6.10:


SHOW CREATE TABLE t2;
Table Create Table
t2 CREATE TABLE `t2` (
  `t2a` timestamp NOT NULL DEFAULT CURRENT_TIMESTAMP,
  `t2b` timestamp NOT NULL DEFAULT '2000-01-01 02:00:00',
  `t1a` timestamp NOT NULL DEFAULT CURRENT_TIMESTAMP,
  `t1b` timestamp NOT NULL DEFAULT '2000-01-01 01:00:00'
) ENGINE=InnoDB DEFAULT CHARSET=latin1
SELECT * FROM t2;
t2a t2b t1a t1b
2013-02-19 18:27:39 2000-01-01 02:00:00 2013-02-19 18:27:39 2000-01-01 01:00:00

All correct!

DBT-3 Q3: 6 x performance in MySQL 5.6.10

Jørgen Løland — Wed, 13 Feb 2013 09:18:00 +0000

When MySQL gets a query, it is the job of the optimizer to find the cheapest way to execute that query. Decisions include access method (range access, table scan, index lookup etc), join order, sorting strategy etc. If we simplify a bit, the optimizer first identifies the different ways to access each table and calculate their cost. After that, the join order is decided.

However, some access methods can only be considered after the join order has been decided and therefore gets special treatment in the MySQL optimizer. For join conditions, e.g. "WHERE table1.col1 = table2.col2", index lookup can only be used in table2 if table1 is earlier in the join sequence. Another class of access methods is only meaningful for tables that are first in the join order. An example is queries with ORDER BY ... LIMIT. Prior to MySQL 5.6.10 there was a bug in MySQL that made the optimizer choose inefficient execution plans for this query type. That's the topic I discuss below.

Read more »

Gluh on InnoDB extended secondary keys

Jørgen Løland — Thu, 20 Dec 2012 08:38:00 +0000

Sergey Glukhov (Gluh) recently wrote an interesting blog about InnoDB secondary key improvements in MySQL 5.6. His blog isn't aggregated to planet.mysql.com but certainly deserves some attention.

Here it is: InnoDB, extended secondary keys.

InnoDB, extended secondary keys.

Sergey Glukhov — Wed, 19 Dec 2012 11:30:00 +0000

It's a well-know fact that InnoDB secondary keys contain both user defined columns and the primary key columns. For example, if a table has PRIMARY KEY(pk) and secondary key k1(f1), then index k1 is internally stored as k1(f1,pk).

Prior to version 5.6.9, the MySQL optimizer could only partially use these extended primary key columns: they could be used for sorting and to provide index only access. Starting from MySQL 5.6.9, the optimizer makes full use of the extended columns. This means that 'ref' access, range access, MIN/MAX optimizations, index_merge, loose index scan etc all works as if you had created the index with all primary key columns in all secondary keys. The new feature is turned on and off by optimizer switch 'use_index_extensions' and is on by default.

Consider we have following table:

CREATE TABLE t1
(
f1 INT NOT NULL DEFAULT '0',
f2 INT NOT NULL DEFAULT '0',
f3 DATE DEFAULT NULL,
PRIMARY KEY (f1, f2),
KEY k_f3 (f3)
) ENGINE = InnoDB;

INSERT INTO t1 VALUES (1, 1, '1998-01-01'), (1, 2, '1999-01-01'),
(1, 3, '2000-01-01'), (1, 4, '2001-01-01'), (1, 5, '2002-01-01'),
(2, 1, '1998-01-01'), (2, 2, '1999-01-01'), (2, 3, '2000-01-01'),
(2, 4, '2001-01-01'), (2, 5, '2002-01-01'), (3, 1, '1998-01-01'),
(3, 2, '1999-01-01'), (3, 3, '2000-01-01'), (3, 4, '2001-01-01'),
(3, 5, '2002-01-01'), (4, 1, '1998-01-01'), (4, 2, '1999-01-01'),
(4, 3, '2000-01-01'), (4, 4, '2001-01-01'), (4, 5, '2002-01-01'),
(5, 1, '1998-01-01'), (5, 2, '1999-01-01'), (5, 3, '2000-01-01'),
(5, 4, '2001-01-01'), (5, 5, '2002-01-01');

Lets take a look at the difference in results with "use_index_extensions=off|on":


mysql> set optimizer_switch= "use_index_extensions=off";
Query OK, 0 rows affected (0.00 sec)
mysql> FLUSH STATUS;
Query OK, 0 rows affected (0.00 sec)
mysql> SELECT COUNT(*) FROM t1 WHERE f3 = '2000-01-01' AND f1 BETWEEN 1 AND 3;
+----------+
| COUNT(*) |
+----------+
|        3 |
+----------+
1 row in set (0.01 sec)
mysql> SHOW STATUS LIKE 'handler_read_next';
+-------------------+-------+
| Variable_name     | Value |
+-------------------+-------+
| Handler_read_next | 5     |
+-------------------+-------+
1 row in set (0.00 sec)


mysql> set optimizer_switch= "use_index_extensions=on";
Query OK, 0 rows affected (0.00 sec)
mysql> FLUSH STATUS;
Query OK, 0 rows affected (0.00 sec)
mysql> SELECT COUNT(*) FROM t1 WHERE f3 = '2000-01-01' AND f1 BETWEEN 1 AND 3;
+----------+
| COUNT(*) |
+----------+
|        3 |
+----------+
1 row in set (0.00 sec)
mysql> SHOW STATUS LIKE 'handler_read_next';
+-------------------+-------+
| Variable_name     | Value |
+-------------------+-------+
| Handler_read_next | 3     |
+-------------------+-------+
1 row in set (0.00 sec)

Number of handler_read_next is decreased with use_index_extensions=on. It happens because optimizer uses 'f3, f1' pair for range access. This behaviour change is indirectly can be visible is explain:


mysql> set optimizer_switch= "use_index_extensions=off";
Query OK, 0 rows affected (0.00 sec)
mysql> EXPLAIN SELECT COUNT(*) FROM t1 WHERE f3 = '2000-01-01' AND f1 BETWEEN 1 AND 3;
+----+-------------+-------+------+---------------+------+---------+-------+------+--------------------------+
| id | select_type | table | type | possible_keys | key  | key_len | ref   | rows | Extra                    |
+----+-------------+-------+------+---------------+------+---------+-------+------+--------------------------+
|  1 | SIMPLE      | t1    | ref  | PRIMARY,k_f3  | k_f3 | 4       | const |    5 | Using where; Using index |
+----+-------------+-------+------+---------------+------+---------+-------+------+--------------------------+
1 row in set (0.00 sec)


mysql> set optimizer_switch= "use_index_extensions=on";
Query OK, 0 rows affected (0.00 sec)
mysql> EXPLAIN SELECT COUNT(*) FROM t1 WHERE f3 = '2000-01-01' AND f1 BETWEEN 1 AND 3;
+----+-------------+-------+-------+---------------+------+---------+------+------+--------------------------+
| id | select_type | table | type  | possible_keys | key  | key_len | ref  | rows | Extra                    |
+----+-------------+-------+-------+---------------+------+---------+------+------+--------------------------+
|  1 | SIMPLE      | t1    | range | PRIMARY,k_f3  | k_f3 | 8       | NULL |    3 | Using where; Using index |
+----+-------------+-------+-------+---------------+------+---------+------+------+--------------------------+

As you can see key_len field is changed (4 with "use_index_extensions=off" and 8 with "use_index_extensions=on") which means that 'f3, f1' pair is used with enabled feature.

Another example shows the improvement when using JOIN(the same table with 12800 records):


mysql> SELECT COUNT(*) FROM t1;
+----------+
| COUNT(*) |
+----------+
|    12800 |
+----------+
1 row in set (0.07 sec)

mysql> set optimizer_switch= "use_index_extensions=off";
Query OK, 0 rows affected (0.00 sec)
mysql> SELECT count(*) FROM t1 AS t1 JOIN t1 AS t2 ON t2.f1 = t1.f1
WHERE t1.f3 = '2000-01-01' AND t2.f3 = '2002-01-01';
+----------+
| count(*) |
+----------+
|    10240 |
+----------+
1 row in set (0.47 sec)

set optimizer_switch= "use_index_extensions=on";
Query OK, 0 rows affected (0.00 sec)
mysql> SELECT count(*) FROM t1 AS t1 JOIN t1 AS t2 ON t2.f1 = t1.f1
WHERE t1.f3 = '2000-01-01' AND t2.f3 = '2002-01-01';
+----------+
| count(*) |
+----------+
|    10240 |
+----------+
1 row in set (0.18 sec)

As you can see execution of the query is roughly 2.5 better with enabled "use_index_extensions" switch.

Favorite MySQL 5.6 features: an optimizer perspective

Jørgen Løland — Mon, 17 Dec 2012 13:55:00 +0000

There are so many exciting new features in MySQL 5.6 that I almost don't know where to start. To mention a few, MySQL's multi-core scalability has been significantly improved to meet modern hardware, InnoDB has better index statistics, much better performance, and online ALTER, replication has multi-threaded slaves and global transaction identifiers, performance schema has added capabilities to provide a much more detailed view of what's bogging a server down, and more... much more.

However, my prime interest is the optimizer, which is why I've compiled a list of my favorite new optimizer features in 5.6. Here goes:

New ways to understand query plans:
The most common requests from DBAs is to get more information to understand how and why MySQL behaves like it does. You can come a very long way at squeezing performance out of MySQL if you can answer questions like "What Query Execution Plan (QEP) did the server decide to use?" and "Why was this QEP picked?". In this department, MySQL 5.6 delivers a bunch of new features.

Read more »

Cost-based choice between subquery materialization and EXISTS

Guilhem Bichot — Fri, 12 Oct 2012 03:02:00 +0000

In a previous post, I had demonstrated how subquery materialization, introduced in MySQL 5.6.5, improves the performance of certain queries, like query Q16 of DBT3. Such improvement was easily explained:

Subquery materialization has a high start up cost (it needs to create and fill the temporary table).
But afterwards it has fast lookups (temporary table has a hash index, no duplicates, and is in memory).
In other words, compared to EXISTS, the first evaluation of the IN predicate is slow (high start up cost) and all following evaluations are fast (just a hash lookup).
In the DBT 3 setup, one outer table (named "part") has 200,000 rows, so there are 200,000 evaluations of IN, thus subquery materialization wins over EXISTS because the time it loses in the first evaluation is more than compensated by the many faster following evaluations.

However, if there were only few outer rows, then subquery materialization should logically be slower than EXISTS (the compensation would not happen anymore)... MySQL 5.6.5, by blindly always choosing subquery materialization, takes the risk of making certain queries slower. There needs to be a cost-based choice between the two strategies, to pick the best, depending on the situation! That is what I have implemented in MySQL 5.6.7.

To show it in action, I will use query Q16 again. First I will run it with the normal "part" table which has 200,000 rows. Then I will reduce this table to only 200 rows, and run the query again. Each time, I will run EXPLAIN to see what subquery strategy is chosen by the optimizer. I will also, by tweaking the optimizer_switch variable, force the optimizer to use the other strategy which it didn't like, in order to verify that it is indeed worse.

For brevity, let me jump directly to the results, obtained with a release build of MySQL 5.6.7 on my machine:

Rows in *part*	Optimizer chooses	Execution time	If I force alternative
200,000	Materialization	550 ms	830 ms
200	EXISTS	1 ms	10 ms

We can see that in both cases the optimizer has made the right choice!

Index merge annoyances fixed in MySQL 5.6

Jørgen Løland — Tue, 02 Oct 2012 10:32:00 +0000

While the index merge access types certainly are useful for a number of queries, there has been some frustration expressed both from customers and the community about how it...

is not used when it should have been
is used when ref access is obviously better
merges suboptimal indexes
is too restricted in which conditions can be used

I could come up with numerous examples of related bugs and feature requests dating back more than six years. To list a few: 17673, 30151, 23322, 65274, 65359.

The good news is that we have fixed all these issues in the latest released MySQL 5.6 server.

Consider the problem in BUG#65274 (simplified a bit):
CREATE TABLE phpbb_posts (
...
KEY `topic_id` (`topic_id`),
KEY `forum_id` (`forum_id`)
KEY `tid_fid` (`topic_id`,`forum_id`),
);
SELECT count(*) FROM phpbb_posts WHERE topic_id = 110126 AND forum_id = 19;

Read more »

Speaking at MySQL Connect This Week-end

Øystein — Thu, 27 Sep 2012 13:02:00 +0000

I will give a talk at MySQL Connect where I present examples of how MySQL 5.6 improves the performance of many of the queries in the DBT-3 benchmark. I will also be giving a brief description of the relevant new optimization techniques and examples of the types of queries that will benefit from these techniques. My presentation is on Sunday (September 30) at 1.15pm.

I will also like to point you to the other presentations made by member of the MySQL Optimizer team:

Olav Sandstå: MySQL Optimizer Overview (Saturday at 11:30am)
Manyi Lu: Overview of New Optimizer Features in MySQL 5.6 (Saturday at 1:00pm)
Evgeny Potemkin: Powerful EXPLAIN in MySQL 5.6 (Sunday at 4:15pm)

We will also be having a BOF on Saturday evening (7:00 am) where we like people to come and give us some input on which query optimizations they would like us to work on for future releases.

From Months to Seconds with Subquery Materialization

Øystein — Sat, 07 Jul 2012 14:11:00 +0000

In an earlier blog post, I showed how optimizer improvements in MySQL 5.6 gave better performance for several of the queries in the DBT-3 benchmark.
However, for one of the queries, Query 18, I was not able to give exact numbers for the improvement since the query took very long in MySQL 5.5. I decided to try to find out exactly how long the query would take, but when the query had run for one month, I gave up. How can a query take so long? Especially, when I had set up InnoDB with a buffer pool that should be large enough to hold the entire database. Let's have a look at the query:

select c_name, c_custkey, o_orderkey, o_orderdate, o_totalprice, sum(l_quantity)
from customer, orders, lineitem
where o_orderkey in (
                select l_orderkey
                from lineitem
                group by l_orderkey
                having sum(l_quantity) > 313
  )
  and c_custkey = o_custkey
  and o_orderkey = l_orderkey
group by c_name, c_custkey, o_orderkey, o_orderdate, o_totalprice
order by o_totalprice desc, o_orderdate
LIMIT 100;

This query will find the orders from customers that have placed big orders. The reason that this takes so long in MySQL 5.5, is that the subquery in the WHERE clause will be executed for each processed row of the table for which this subquery is part of the WHERE predicate. Let's look at the EXPLAIN output for this query:

+----+--------------------+----------+-------+--------------------------------------------+-----------------------+---------+-------------------------+---------+---------------------------------+
| id | select_type        | table    | type  | possible_keys                              | key                   | key_len | ref                     | rows    | Extra                           |
+----+--------------------+----------+-------+--------------------------------------------+-----------------------+---------+-------------------------+---------+---------------------------------+
|  1 | PRIMARY            | customer | ALL   | PRIMARY                                    | NULL                  | NULL    | NULL                    |  150000 | Using temporary; Using filesort | 
|  1 | PRIMARY            | orders   | ref   | PRIMARY,i_o_custkey                        | i_o_custkey           | 5       | dbt3.customer.c_custkey |       7 | Using where                     | 
|  1 | PRIMARY            | lineitem | ref   | PRIMARY,i_l_orderkey,i_l_orderkey_quantity | i_l_orderkey_quantity | 4       | dbt3.orders.o_orderkey  |       2 | Using index                     | 
|  2 | DEPENDENT SUBQUERY | lineitem | index | NULL                                       | PRIMARY               | 8       | NULL                    | 6001215 | NULL                            | 
+----+--------------------+----------+-------+--------------------------------------------+-----------------------+---------+-------------------------+---------+---------------------------------+

The select_type for the subquery is DEPENDENT SUBQUERY. Since the left hand side of the IN-expression is a field from the orders table, the subquery will be executed for each row processed from this table. This implies that the index scan of the lineitem table will be performed more than one million times given the rows estimates in the EXPLAIN output (150000*7). I have measured that one execution of the sub-query takes about 3.5 seconds when all the data is in memory. Hence, it will take more than 40 days to execute it one million times.

In MySQL 5.6, Subquery Materialization may be used to avoid the repeated execution of subqueries. This implies that the subquery is executed once and the result stored (materialized) in a temporary table. Then, for each row where the subquery was earlier executed, a hash-based look-up into the temporary table will be made instead to check whether there is a match. The EXPLAIN output for Query 18, looks like this in MySQL 5.6:

+----+-------------+----------+-------+--------------------------------------------+-----------------------+---------+-------------------------+---------+---------------------------------+
| id | select_type | table    | type  | possible_keys                              | key                   | key_len | ref                     | rows    | Extra                           |
+----+-------------+----------+-------+--------------------------------------------+-----------------------+---------+-------------------------+---------+---------------------------------+
|  1 | PRIMARY     | customer | ALL   | PRIMARY                                    | NULL                  | NULL    | NULL                    |  150000 | Using temporary; Using filesort | 
|  1 | PRIMARY     | orders   | ref   | PRIMARY,i_o_custkey                        | i_o_custkey           | 5       | dbt3.customer.c_custkey |       7 | Using where                     | 
|  1 | PRIMARY     | lineitem | ref   | PRIMARY,i_l_orderkey,i_l_orderkey_quantity | i_l_orderkey_quantity | 4       | dbt3.orders.o_orderkey  |       2 | Using index                     | 
|  2 | SUBQUERY    | lineitem | index | NULL                                       | PRIMARY               | 8       | NULL                    | 6001215 | NULL                            | 
+----+-------------+----------+-------+--------------------------------------------+-----------------------+---------+-------------------------+---------+---------------------------------+

The only difference is that select_type of the subquery now is SUBQUERY. In other words, it is no longer dependent on the preceding tables, and can be executed only once. In my run of DBT-3 with MySQL 5.6, Query 18 takes only 6.8 seconds. Hence, we have gone from more than a month to just a few seconds! My colleague Guilhem has earlier written about another DBT-3 query that is improved with Subquery Materialization.

Performance improvements for big INFORMATION_SCHEMA tables

Jørgen Løland — Fri, 04 May 2012 08:27:00 +0000

A short while after I fixed the legacy bug that prevented temporary MyISAM tables from using the dynamic record format, I got an email from Davi Arnaut @ Twitter. It turned out that Twitter needed to fix the very same problem, but for the case when INFORMATION_SCHEMA temporary tables use MyISAM.

In short, INFORMATION_SCHEMA tables provide access to database metadata. Despite their name, they are more like views than tables: when you query them, relevant data is gathered from the dictionary and other server internals, not from tables. The gathered data is stored in a temporary table (memory or MyISAM depending on size) and then returned to the user.

The reason Davi emailed me was to let me know that he had further improved the fix for temporary MyISAM tables to also enable the use of dynamic record format for INFORMATION_SCHEMA tables. I usually don't have huge databases on my development box so the problem of querying metadata had gone unnoticed. But it turns out that Davi and his colleagues at Twitter do deal with massive amounts of data :-)

This was one of the queries that caused problems:

SELECT pool_id FROM INFORMATION_SCHEMA.INNODB_BUFFER_PAGE limit 1;

Read more »

Copying unused bytes is bad (duh!)

Jørgen Løland — Wed, 18 Apr 2012 10:59:00 +0000

Last summer my colleague Marko Mäkelä committed this seemingly innocent performance fix for InnoDB in MySQL 5.6:

3581 Marko Makela 2011-08-10
Bug#12835650 VARCHAR maximum length performance impact

row_sel_field_store_in_mysql_format(): Do not pad the unused part of
the buffer reserved for a True VARCHAR column (introduced in 5.0.3).
Add Valgrind instrumentation ensuring that the unused part will be
flagged uninitialized.

Before this, buffers which were used to send VARCHARs from InnoDB to the MySQL server were padded with 0s if the string was shorter than specified by the column. If, e.g., the string "foo" was stored in a VARCHAR(8), InnoDB used to write "3foo00000" to the buffer (the first character - 3 - determines the actual length of the string). However, even though these trailing bytes are not used anywhere, writing 0s to the buffer certainly has a cost. Hence the fix which stops InnoDB from writing them.

Oh my were we up for a ride! All of a sudden Valgrind started barking like this (and similar) for a number of tests:

Thread 19:
Syscall param pwrite64(buf) points to uninitialised byte(s)
at 0x381C60EEE3: ??? (in /lib64/libpthread-2.12.so)
by 0x84B703: my_pwrite (my_pread.c:162) by 0x86FE6F: mi_nommap_pwrite (mysql_file.h:1203)
   by 0x88621B: _mi_write_static_record (mi_statrec.c:65)
   by 0x889592: mi_write (mi_write.c:142)
   by 0x532085: handler::ha_write_row(unsigned char*) (handler.cc:6043)
   by 0x69B7F7: end_write(JOIN*, st_join_table*, bool) (sql_select.cc:20237)
   by 0x69A43C: evaluate_join_record(JOIN*, st_join_table*, int)
(sql_select.cc:19187)
   by 0x69A8E0: sub_select(JOIN*, st_join_table*, bool) (sql_select.cc:19294)

The modifications we did to the server to remedy the problems can be divided into two categories as described below. In the end, the result was significantly improved performance.

Read more »

New MySQL optimizer team page launched

Jørgen Løland — Fri, 13 Apr 2012 15:07:00 +0000

FYI: A MySQL Optimizer Team blog aggregate page has been launched. It will be continuously updated with the latest blogs published by the MySQL optimizer developers. Now you can easily stay updated ;-)

Improved DBT-3 Results with MySQL 5.6.5

Øystein — Wed, 11 Apr 2012 01:01:00 +0000

In addition to the Optimizer features added in earlier 5.6 Development Milestone Releases, the newly released MySQL 5.6.5 Development Milestone Release adds a few more. I think this is a good time to check how all these new optimizer features impact the performance of the DBT-3 benchmark queries. In this blog post, I will compare the performance of the DBT-3 queries in MySQL 5.5 and MySQL 5.6.5.

Test Setup

I used a DBT-3 scale 1 database (InnoDB tables) that was stored on a traditional hard disk, and the InnoDB database size was a bit more than 2.5 GB. The DBT-3 queries were run in two settings: a disk-bound setting with a very small InnoDB buffer pool (50 MB), and CPU-bound with a 3 GB InnoDB buffer pool (all data in memory). The query cache was disabled, and by setting --innodb_flush_method=O_DIRECT, the file buffering in the file system was also out of the way. If not stated otherwise, default settings were used for all other MySQL system variables.

For the disk-bound scenario, each query were executed 10 times in a row, and the results presented are the average of the last 8 runs. Since the buffer pool was very small, and there was no buffering in the file system, there were very little difference between the first and the tenth execution of the queries. The only exceptions were Query 16 and Query 22 where the working data sets were so small that subsequent executions were not disk-bound. Due to this, I have not included the result for these queries in the presentation of the disk-bound scenario.

For the CPU-bound scenario, each query were executed 20 times in a row, but the results presented are still the average of the last 8 runs. (The reason for this, is that I observed that for several of the queries, the 8th or so execution of the query took significantly longer than the other executions.)

The order in which the different queries were run were randomized, but the same order was used in all experiments.

In order to get stable execution plans, I enabled InnoDB Persistent Statistics and recorded exact statistics in the statistics tables as discussed here. Since Persistent Statistics is not available in 5.5, I used optimizer hints to force a similar join order and index usage as for 5.6 where necessary.

For MySQL 5.6.5, the DBT-3 queries were run both with default settings for the optimizer_switch variable, and with setting optimizer_switch='mrr_cost_based=off,batched_key_access=on' in order to activate the Disk-Sweep Multi-Range Read (DS-MRR)and Batched Key Access (BKA) features.

OK, enough talking, let's move on to the results.

Disk-Bound Workload

The below chart shows the execution times for the DBT-3 queries in a disk-bound setting. The executions times in MySQL 5.5, MySQL 5.6.5 with default optimizer_switch settings, and MySQL 5.6.5 with DS-MRR and BKA activated are compared. The execution times for MySQL 5.6.5 default is set to 1, and the relative execution times are shown for the other two variants.

Except for Query 18, there are no significant differences between MySQL 5.5 and MySQL 5.6.5 with default settings. However, for Query 18 the improvement is dramatic. While it takes days to execute this query in MySQL 5.5, it takes less 45 minutes in MySQL 5.6.5. This improvement is due to Subquery Materialization, and I will discuss this further in a later blog post.

As discussed in an earlier blog post, BKA can give very big improvements when the workload is disk-bound. This is illustrated by the improvements of queries 2, 5, 8, 9, 13, 18, 19, and 21. Note also that there are some queries that does not benefit from BKA. As discussed in the aforementioned blog, Query 17 gets better locality for the disk accesses without BKA, and turning on BKA makes it take 16 times longer to execute. We also see that Query 11 performs worse with BKA. I plan to investigate further the reason for this.

Queries 3, 4, 10, 14, and 15, are improved by using the DS-MRR algorithm when doing range access. That is, the rows in the base table are not accessed in the order given by the index used for range access, but in sequential order as viewed from the clustered primary key index.

CPU-Bound Workload

The below chart shows the execution times for the DBT-3 queries in a CPU-bound setting. As above the executions times in MySQL 5.5, MySQL 5.6.5 with default optimizer_switch settings, and MySQL 5.6.5 with DS-MRR and BKA activated are compared.

For MySQL 5.6.5 with default settings, the most significant improvement is for Query 18 also with a CPU-bound workload. In addition, there is a 10% improvement for Query 16. This is also due to Subquery Materialization, and my colleague Guilhem discusses this improvement in more detail.

As discussed in my previous blog post on BKA, several queries perform worse with BKA in a CPU-bound setting (e.g., queries 2, 11, 13, and 17). Only query 18 performs better with BKA in this setting.

On the other hand, many of the queries that benefited from DS-MRR with a disk-bound workload, still show some improvement with a CPU-bound workload.

Conclusions

The results from comparing the new MySQL 5.6.5 release with MySQL 5.5, show that Subquery Materialization have significant effects on the execution time of the few DBT-3 queries where it applies.

Also, as shown earlier, BKA has a good effect for disk-bound workloads, while it in many cases will cause worse performance for CPU-bound workloads.

Disk-sweep MRR has a good effect on the performace of range scans in for disk-bound workloads, and it also shows a small improvement for many queries with CPU-bound workloads.

Improvements for many-table joins in MySQL 5.6

Jørgen Løland — Tue, 10 Apr 2012 22:00:00 +0000

A lot has happened in MySQL 5.6 for queries joining many tables. For the most common use cases we have drastically reduced the cost of finding the execution plan. We have also improved the heuristics and removed bugs so that the final plan is often better than it used to be. Read on if you are one of those people who do 15 way joins!

Finding a query execution plan
First some background. You can skip this part if you know how MySQL picks the table join order in 5.5.

When presented with a query, MySQL will try to find the best order to join tables by employing a greedy search algorithm. The outcome is what we call a query execution plan, QEP. When you join just a few tables, there's no problem calculating the cost of all join order combinations and then pick the best plan. However, since there are (#tables)! possible combinations, the cost of calculating them all soon becomes too high: for five tables, e.g., there are 120 combinations which is no problem to compute. For 10 tables there are 3.6 million combinations and for 15 tables there are 1307 billion. You get the picture. For this reason, MySQL makes a trade off: use heuristics to only explore promising plans. This is supposed to significantly reduce the number of plans MySQL needs to calculate, but at the same time you risk not finding the best one.

Read more »

On queries with many values in the IN clause

Jørgen Løland — Tue, 10 Apr 2012 15:00:00 +0000

A few customers with rather extreme needs have contacted us about a performance issue with the range optimizer. Our solution to the problem is to introduce a new variable in MySQL 5.6, eq_range_index_dive_limit, which can be used to control whether or not the range optimizer will a) do index dives, or b) use index statistics when estimating the number of rows in the ranges of the query. The former method gives a far more accurate estimate while the latter costs a lot less to compute.

This is what the help text has to tell about the variable:

The optimizer will use existing index statistics instead of doing index dives for equality ranges if the number of equality ranges for the index is larger than or equal to [the value of variable]. If set to 0, index dives are always used.

"Equality range" means predicates using operators IN() or =, and it's important to notice that the number of such ranges is counted on a per index basis. Furthermore, index dives are not used on unique/primary indexes, so only non-unique indexes are affected.

The two ways row estimates can be computed

For as long as there have been a range access method in MySQL, the number of rows in a range has been estimated by diving down the index to find the start and end of the range and use these to count the number of rows between them. This technique is accurate, and is therefore a good basis to make the best possible execution plan (QEP) for the query. Unfortunately, it involves two index dives for each range. That's not a big deal if you run normal queries with a few equality ranges like

SELECT title FROM albums WHERE artist IN (10, 12)

But some MySQL users have queries with hundreds of values in the IN clause. For such queries it may take considerably longer to optimize the query than to execute it. This is when it makes sense to use the less accurate index statistics. Consider this example:

Read more »

Faster subqueries with materialization

Guilhem Bichot — Tue, 10 Apr 2012 08:55:00 +0000

In a previous post, I analyzed how a query of the famous DBT3 benchmark was
optimized by MySQL. It was this query, named "Q16" in the DBT3 jargon:


select
 p_brand,
 p_type,
 p_size,
 count(distinct ps_suppkey) as supplier_cnt
from
 partsupp,
 part
where
 p_partkey = ps_partkey
 and p_brand <> 'Brand#23'
 and p_type not like 'LARGE PLATED%'
 and p_size in (43, 1, 25, 5, 35, 12, 42, 40)
 and ps_suppkey not in (
  select
   s_suppkey
  from
   supplier
  where
   s_comment like '%Customer%Complaints%'
 )
group by
 p_brand,
 p_type,
 p_size
order by
 supplier_cnt desc,
 p_brand,
 p_type,
 p_size;

Here is a brief recap of conclusions I had drawn:

for this query, MySQL tranforms the IN condition to EXISTS and then
evaluates it with the "unique_subquery" technique, which does an index
lookup into the subquery's table.
IN is evaluated 120,000 times (once per combined row of the outer tables).
The total execution time of query Q16 is 0.65 seconds.

If you look at the original subquery, before IN becomes EXISTS, you will see that it's not correlated, which means that it does not mention columns of tables of the top query's FROM clause ('partsupp' and 'part'). Thus, its resultset is constant throughout execution of the entire top query; here it is:


mysql> select
    -> s_suppkey
    -> from
    -> supplier
    -> where
    -> s_comment like '%Customer%Complaints%';
+-----------+
| s_suppkey |
+-----------+
|       358 |
|      2820 |
|      3804 |
|      9504 |
+-----------+
4 rows in set (0.00 sec)

The transformation to EXISTS, because it injects equalities like
`partsupp`.`ps_suppkey` = supplier`.`s_suppkey`
into the subquery's WHERE clause, makes the subquery correlated: it thus has to be executed 120,000 times, so we do 120,000 times this:

an index lookup in 'supplier' (which has 10,000 rows)
a test of the found row(s) against the LIKE condition.

Intuitively, determining the 4-row resultset once for all, and injecting it into the top query should yield better performance - it is fast to evaluate
ps_suppkey not in (358, 2820, 3804, 9504) .
Starting from the just released MySQL 5.6.5, this transformation is automatically done by the Optimizer, and is called subquery materialization. The subquery's resultset is determined once for all and stored into an in-memory temporary table. If the temporary table has only 4 rows as in our example, searching for a match in it can be done with a scan; but if it had more rows, a hash index would help greatly. So a hash index is always created on the temporary table's columns. Last, this index is unique: there is no point in storing duplicates, and they would make the table bigger. After this one-time setup has been completed, each evaluation of IN simply does a hash index lookup into the 4-row temporary table.

My former colleague Timour Katchaounov started developing this feature years ago, when working for MySQL/Sun. In the last months, after a round of intensive QA, we have fixed some last bugs in it, in preparation for releasing in 5.6.5. But the feature still had one limitation: it was applicable only if IN was placed at certain positions in the query. For example, it couldn't be used with NOT IN. And query Q16 has a NOT IN! so the Optimizer could not apply subquery materialization to it, and was thus stuck with using EXISTS. Sad!

Why it could not work with NOT IN, is not very easy to explain. It has to do with NULL values, because they sometimes prevent using the hash index. To give an idea, look at this:
(NULL, 1) NOT IN (SELECT ...)
Per the SQL standard, if the subquery's resultset contains at least one row of the form (x,1) where x is any number (or NULL), then the IN condition is neither TRUE, nor FALSE, it is UNKNOWN. So is the NOT IN condition, because it is the negation of IN, and NOT(UNKNOWN) is UNKNOWN.
Here are example of such rows: (NULL,1), (421,1), (236,1), (5329,1), ad infinitam.
We can see that those rows will not be found by a lookup in the hash index: this index is defined on the two columns, it has a usual "prefix-only" behaviour, which means that it cannot be used to search for "any value in first column, then 1 in second column". As long as the sentence starts with "any value in first column" a table scan is necessary; we should read each row of the temporary table and compare its second column with 1 until we find a matching row. And that:

will drag subquery materialization's performance down
will drag subquery materialization's code complexity up.

And I have even not covered all problems here: there can be more than two columns, there can be more than one NULL in the left argument of IN, there can also be NULLs inside the subquery's resultset.

In some lucky cases, the scan can be avoided, for example:
SELECT * FROM table1 WHERE (a,b) IN (SELECT ...)
If (a,b) is (NULL,1), the IN will be UNKNOWN or FALSE. It will be UNKNOWN if the subquery's resultset contains one (x,1) as seen above; otherwise it will be FALSE. No matter what, it will not be TRUE, and this is all that WHERE wants to know - (a,b) can thus be rejected without doing a scan.
Now, for
SELECT * FROM table1 WHERE (a,b) NOT IN (SELECT ...)
i.e.
SELECT * FROM table1 WHERE NOT ((a,b) IN (SELECT ...))
things are different: if (a,b) is (NULL,1), the IN will be UNKNOWN or FALSE, as we said. So NOT IN will be UNKNOWN or TRUE. "Hum, can you be more specific?? I need to know if it's TRUE", will the WHERE evaluation code ask. Then we have to do the scan...

So now you understand why subquery materialization was restricted to certain placement of IN.

What I have done recently is to lift this restriction in two simple, however common, cases:

If all outer and inner expressions are not nullable, then no NULL can get in the way, so there is no problem.
If there is only one outer expression (and thus there is only one inner expression), figuring out the correct TRUE/FALSE/UNKNOWN answer is immediate. Understanding why... is left as an exercise to the reader :-)

Those two cases are independent: as long as one is satisfied, subquery materialization can apply to IN, no matter where it is placed (NOT IN, etc).

It turned out to be very easy to code this: I had a working prototype in an afternoon.

Q16 happens to meet the criteria of both cases: columns 'ps_suppkey' and 's_suppkey' are declared NOT NULL (first case), and the subquery has only one outer and one inner expression (second case).

So nowadays MySQL can, and does, use subquery materialization for query Q16; thanks to it, the execution time is down from 0.65 seconds to 0.47 seconds, which is a 25% improvement!

The new technique is visible in EXPLAIN. I want to first show how EXPLAIN was with the EXISTS transformation, so I temporarily disable subquery materialization, then run EXPLAIN, enable subquery materialization, run EXPLAIN:


mysql> set optimizer_switch='materialization=off';
mysql> explain ...

+----+--------------------+----------+-----------------+----------------------+--------------+---------+---------------------+--------+----------------------------------------------+
| id | select_type        | table    | type            | possible_keys        | key          | key_len | ref                 | rows   | Extra                                        |
+----+--------------------+----------+-----------------+----------------------+--------------+---------+---------------------+--------+----------------------------------------------+
|  1 | PRIMARY            | part     | ALL             | PRIMARY              | NULL         | NULL    | NULL                | 199742 | Using where; Using temporary; Using filesort |
|  1 | PRIMARY            | partsupp | ref             | PRIMARY,i_ps_partkey | i_ps_partkey | 4       | dbt3.part.p_partkey |      2 | Using where; Using index                     |
|  2 | DEPENDENT SUBQUERY | supplier | unique_subquery | PRIMARY              | PRIMARY      | 4       | func                |      1 | Using where                                  |
+----+--------------------+----------+-----------------+----------------------+--------------+---------+---------------------+--------+----------------------------------------------+

mysql> set optimizer_switch='materialization=default'; # 'on' would work too
mysql> explain ...

+----+-------------+----------+------+----------------------+--------------+---------+---------------------+--------+----------------------------------------------+
| id | select_type | table    | type | possible_keys        | key          | key_len | ref                 | rows   | Extra                                        |
+----+-------------+----------+------+----------------------+--------------+---------+---------------------+--------+----------------------------------------------+
|  1 | PRIMARY     | part     | ALL  | PRIMARY              | NULL         | NULL    | NULL                | 199742 | Using where; Using temporary; Using filesort |
|  1 | PRIMARY     | partsupp | ref  | PRIMARY,i_ps_partkey | i_ps_partkey | 4       | dbt3.part.p_partkey |      2 | Using where; Using index                     |
|  2 | SUBQUERY    | supplier | ALL  | NULL                 | NULL         | NULL    | NULL                |  10113 | Using where                                  |
+----+-------------+----------+------+----------------------+--------------+---------+---------------------+--------+----------------------------------------------+

If you compare, the big difference is that the third line says SUBQUERY and not DEPENDENT SUBQUERY anymore. DEPENDENT SUBQUERY means that it has be executed once per row of the top query. SUBQUERY means that it is executed only once.
EXPLAIN FORMAT=JSON, another new feature in MySQL 5.6.5, shows more details of materialization:


{
  "query_block": {
    "select_id": 1,
    "ordering_operation": {
      "using_temporary_table": true,
      "using_filesort": true,
      "grouping_operation": {
        "using_filesort": true,
        "nested_loop": [
          {
            "table": {
              "table_name": "part",
              "access_type": "ALL",
              "possible_keys": [
                "PRIMARY"
              ],
              "rows": 199742,
              "filtered": 100,
              "attached_condition": "((`dbt3`.`part`.`p_brand` <> 'Brand#23') and (not((`dbt3`.`part`.`p_type` like 'LARGE PLATED%'))) and (`dbt3`.`part`.`p_size` in (43,1,25,5,35,12,42,40)))"
            }
          },
          {
            "table": {
              "table_name": "partsupp",
              "access_type": "ref",
              "possible_keys": [
                "PRIMARY",
                "i_ps_partkey"
              ],
              "key": "i_ps_partkey",
              "key_length": "4",
              "ref": [
                "dbt3.part.p_partkey"
              ],
              "rows": 2,
              "filtered": 100,
              "using_index": true,
              "attached_condition": "(not(< in_optimizer >(`dbt3`.`partsupp`.`ps_suppkey`,`dbt3`.`partsupp`.`ps_suppkey` in ( < materialize > (select `dbt3`.`supplier`.`s_suppkey` from `dbt3`.`supplier` where (`dbt3`.`supplier`.`s_comment` like '%Customer%Complaints%') ), < primary_index_lookup >(`dbt3`.`partsupp`.`ps_suppkey` in < temporary table > on distinct_key where ((`dbt3`.`partsupp`.`ps_suppkey` = `materialized subselect`.`s_suppkey`)))))))",
              "attached_subqueries": [
                {
                  "using_temporary_table": true,
                  "dependent": false,
                  "cacheable": true,
                  "table": {
                    "access_type": "eq_ref",
                    "key": "< auto_key >",
                    "rows": 1
                  },
                  "query_block": {
                    "select_id": 2,
                    "table": {
                      "table_name": "supplier",
                      "access_type": "ALL",
                      "rows": 10113,
                      "filtered": 100,
                      "attached_condition": "(`dbt3`.`supplier`.`s_comment` like '%Customer%Complaints%')"
                    }
                  }
                }
              ]
            }
          }
        ]
      }
    }
  }
}

Don't forget to scroll the box above to the right, because lines are long. This shows that:

For the top query, we read a row from 'part', then one row from 'partsupp', then execute the subquery.
the very first execution of the subquery materializes (<materialize>) select `dbt3`.`supplier`.`s_suppkey` from `dbt3`.`supplier` where (`dbt3`.`supplier`.`s_comment` like '%Customer%Complaints%') into a temporary table
Each subquery execution does a lookup on the primary key of this temporary table (<primary_index_lookup> ... in <temporary table>)
Going further down, we see how the temporary table will be filled: it will be the resultset of a table scan ("access_type": "ALL") of 'supplier' with a filtering LIKE condition.

More details on the feature's usage can be found in the manual.

This is the end of this post. I hope that it puts in good light the work we have put into 5.6. There are many other Optimizer features in this version, like EXPLAIN FORMAT=JSON and others; they are described in my colleagues' blog posts.

Semi-join in MySQL 5.6

Roy Lyseng — Tue, 10 Apr 2012 07:37:00 +0000

MySQL 5.6.5 Development Milestone Release has a whole new set of algorithms for processing subqueries. It is based on transforming a subquery into a semi-join operation, and then treating semi-join like another join operation throughout the optimizer.

A subquery can be transformed to a semi-join if it matches these criteria:

The subquery is part of an IN or =ANY predicate. It cannot be e.g. NOT IN.
The subquery consists of a single query block (it must not contain UNION).
The subquery does not contain GROUP BY or HAVING.
The subquery is not implicitly grouped (it contains no aggregate functions).
The subquery predicate is part of a WHERE clause.
The subquery predicate must not be part of a disjunctive nor a negated search condition.
Neither query block contains the STRAIGHT_JOIN qualifier.
The statement must be a SELECT or INSERT statement. Semi-joins are not allowed with UPDATE or DELETE statements.

Example subquery that can be transformed to a semi-join:

SELECT * FROM nation

WHERE n_regionkey IN (SELECT r_regionkey FROM region

WHERE r_name='AFRICA');

What is a semi-join operation

A semi-join operation is similar to a regular join operation: It takes two (sets of) tables and combines them using a join condition.

Like an outer join, a semi-join is a noncommutative join operator. We denote the tables of the containing query block the outer tables and the tables of the subquery the inner tables.

Two factors distinguish a semi-join from a regular join:

In a semi-join, the inner tables do not cause duplicates in the result.
No columns from the inner tables are added to the result of the operation.

This means that the result of the semi-join is a subset of the rows from the outer tables. It also means that much of the special handling of semi-join is about efficiently eliminating duplicates from the inner tables.

We can represent the above query using the artificial SEMI JOIN operator as follows:

SELECT nation.*

FROM nation SEMI JOIN region

ON nation.n_regionkey = region.r_regionkey AND

region.r_name='AFRICA';

Semi-join optimization

If possible, a subquery is transformed into a semi-join during the query resolution stage. The query blocks containing the outer tables and the inner tables are then combined into a larger query block.

The next step of the optimization is to determine inner tables that are candidate for table pullout. If the inner table of a semi-join has an eq-ref relationship to the outer part of the query, there can be no duplicates from the inner side, and the semi-join can be converted to a regular join. We call that a table pullout, because the table is "pulled out" from the semi-join and joined with the outer tables.

The above subquery can be transformed using table pullout, because there is a unique index on the r_regionkey column. The explain result of the query is as follows:


| id | select_type | table  | type | possible_keys | key           | key_len | ref                     | rows | Extra       |
+----+-------------+--------+------+---------------+---------------+---------+-------------------------+------+-------------+
|  1 | PRIMARY     | region | ALL  | PRIMARY       | NULL          | NULL    | NULL                    |    5 | Using where |
|  1 | PRIMARY     | nation | ref  | i_n_regionkey | i_n_regionkey | 5       | dbt3.region.r_regionkey |    2 |             |

As you can see, there is no difference between this explain result and the explain result of a regular join between these two tables.

The cost-based optimization procedure is then applied to the tables of the query block. Tables taking part in semi-joins are combined in various ways, with the appropriate cost added to the total plan cost. The end result is an optimal table order and an optimal set of semi-join execution strategies.

Semi-join execution strategies

As said before, semi-join is a regular join operation, combined with removal of possible duplicates from the semi-join inner tables. MySQL implements four different semi-join execution strategies, which have different ways of removing duplicates:

FirstMatch
DuplicateWeedout
Materialization
LooseScan

I will handle the FirstMatch strategy in more detail below. The other semi-join strategies will be handled in later blogs. How semi-join strategies can be combined with join buffering will also be handled.

Controlling semi-join strategies

Use of semi-join is controlled with the optimizer_switch flag semijoin:

set optimizer_switch='semijoin=on'

This command enables transformation of subqueries into semi-join operations. This flag is on by default in MySQL 5.6.5.

In addition, individual semi-join strategies can be turned on and off with the following optimizer_switch flags:

firstmatch, materialization, loosescan

These flags enable or disable the use of the respective semi-join strategies. Notice that there is no way to disable the DuplicateWeedout strategy, as this is the "last resort" strategy selected by the cost-based optimizer. There is also no way to disable the TablePullout strategy, when semi-join is enabled.

The default for all semi-join related optimizer_switch flags are:

'semijoin=on,firstmatch=on,materialization=on,loosescan=on'

Notice also that the optimizer_switch flag materialization has a second meaning: It controls the use of the subquery materialization feature (which should not be confused with the semi-join materialization strategy).

Semi-join FirstMatch strategy

The semi-join FirstMatch strategy executes a subquery very similar to how the IN-TO-EXISTS strategy familiar from earlier versions of MySQL works: for each matching row in the outer table, check for a match in the inner table. When a match is found, return the row from the outer table, otherwise continue scanning the inner table until reaching the end.

Here is a query that is processed using FirstMatch strategy:

SELECT * FROM nation

WHERE n_nationkey IN (SELECT c_nationkey FROM customer);

Notice the FirstMatch(nation) indication in explain output, which means that after a match has been found in table customer, the query executor goes back to scan more rows in table nation:


| id | select_type | table    | type | possible_keys | key           | key_len | ref                     | rows | Extra                           |
+----+-------------+----------+------+---------------+---------------+---------+-------------------------+------+---------------------------------+
|  1 | PRIMARY     | nation   | ALL  | PRIMARY       | NULL          | NULL    | NULL                    |   25 |                                 |
|  1 | PRIMARY     | customer | ref  | i_c_nationkey | i_c_nationkey | 5       | dbt3.nation.n_nationkey | 1115 | Using index; FirstMatch(nation) |

Here is the result from IN-TO-EXISTS transformation, which can still be enabled by setting optimizer_switch flags:

set optimizer_switch='semijoin=off,materialization=off' :


| id | select_type        | table    | type           | possible_keys | key           | key_len | ref  | rows | Extra       |
+----+--------------------+----------+----------------+---------------+---------------+---------+------+------+-------------+
|  1 | PRIMARY            | nation   | ALL            | NULL          | NULL          | NULL    | NULL |   25 | Using where |
|  2 | DEPENDENT SUBQUERY | customer | index_subquery | i_c_nationkey | i_c_nationkey | 5       | func | 1115 | Using index |

As this is basically the same strategy that MySQL 5.5 would choose, there is usually no speedup to gain when FirstMatch is chosen. The advantage may however come when FirstMatch is not the most efficient strategy, or when the cost-based optimizer chooses a more efficient table order. The optimizer can determine a better table order, because it will estimate a realistic cost for a semi-join operation. This contrasts MySQL 5.5 where the placement of a subquery in the query plan was strictly rule-based.

Multiple subqueries

It is possible to combine multiple subqueries with AND and still have them transformed to a semi-join:

SELECT * FROM nation

WHERE n_regionkey IN (SELECT r_regionkey FROM region

WHERE r_name='AFRICA') AND

n_nationkey IN (SELECT c_nationkey FROM customer);

The explain output shows one FirstMatch strategy:


| id | select_type | table    | type | possible_keys         | key           | key_len | ref                     | rows | Extra                           |
+----+-------------+----------+------+-----------------------+---------------+---------+-------------------------+------+---------------------------------+
|  1 | PRIMARY     | region   | ALL  | PRIMARY               | NULL          | NULL    | NULL                    |    5 | Using where                     |
|  1 | PRIMARY     | nation   | ref  | PRIMARY,i_n_regionkey | i_n_regionkey | 5       | dbt3.region.r_regionkey |    2 |                                 |
|  1 | PRIMARY     | customer | ref  | i_c_nationkey         | i_c_nationkey | 5       | dbt3.nation.n_nationkey | 1115 | Using index; FirstMatch(nation) |

Nested subqueries

MySQL can process nested subqueries and transform them into one semi-join operation. Here is a slightly artificial example:

SELECT * FROM nation

WHERE n_nationkey IN

(SELECT c_nationkey FROM customer

WHERE c_acctbal IN

(SELECT o_totalprice FROM orders

WHERE o_orderstatus = 'P'));

From the explain output, we see a FirstMatch strategy applied to tables customer and order, jumping back to table nation when a match is found:


| id | select_type | table    | type | possible_keys | key           | key_len | ref                     | rows    | Extra                           |
+----+-------------+----------+------+---------------+---------------+---------+-------------------------+---------+---------------------------------+
|  1 | PRIMARY     | nation   | ALL  | PRIMARY       | NULL          | NULL    | NULL                    |      25 |                                 |
|  1 | PRIMARY     | customer | ref  | i_c_nationkey | i_c_nationkey | 5       | dbt3.nation.n_nationkey |    1115 |                                 |
|  1 | PRIMARY     | orders   | ALL  | NULL          | NULL          | NULL    | NULL                    | 1486350 | Using where; FirstMatch(nation) |

Want to know more?

Check out the MySQL documentation for semi-join optimization here

Optimizer: new EXPLAIN FORMAT=JSON

Gleb Shchepa — Tue, 10 Apr 2012 06:25:00 +0000

New feature: structured EXPLAIN

Probably, most of us tried to read the output of MySQL EXPLAIN command at least once.
And probably many of us have decided, that it isn't so readable and understandable as it has to be.
Some of us even tried to create or use external pretty-printing programs and other complicated converters to make EXPLAIN's output less cryptic, for example nice Percona's Visual Explain script.
But from now we have a native MySQL command that explains query execution plan in a better human-readable and machine-readable way: EXPLAIN FORMAT=JSON!

A trivial example, SELECT from a single table:

mysql> CREATE TABLE t1 (i INT, j INT);
Query OK, 0 rows affected (0.00 sec)

mysql> EXPLAIN SELECT * FROM t1;
+----+-------------+-------+--------+---------------+------+---------+------+------+---------------------+
| id | select_type | table | type   | possible_keys | key  | key_len | ref  | rows | Extra               |
+----+-------------+-------+--------+---------------+------+---------+------+------+---------------------+
|  1 | SIMPLE      | t1    | system | NULL          | NULL | NULL    | NULL |    0 | const row not found |
+----+-------------+-------+--------+---------------+------+---------+------+------+---------------------+
1 row in set (0.00 sec)

mysql> EXPLAIN FORMAT=JSON SELECT * FROM t1;
+------------------------------------------------- ...
| EXPLAIN                                          
+------------------------------------------------- ...
| {
  "query_block": {
    "select_id": 1,
    "table": {
      "table_name": "t1",
      "access_type": "system",
      "rows": 0,
      "filtered": 0,
      "const_row_not_found": true
    }
  }
} |
+------------------------------------------------- ...
1 row in set, 1 warning (0.00 sec)

mysql> SHOW WARNINGS;
+-------+------+----------------------------------------------------------------+
| Level | Code | Message                                                        |
+-------+------+----------------------------------------------------------------+
| Note  | 1003 | /* select#1 */ select NULL AS `i`,NULL AS `j` from `test`.`t1` |
+-------+------+----------------------------------------------------------------+
1 row in set (0.00 sec)

Moreover, new EXPLAIN is not just a 1-to-1 translator of the old EXPLAIN command output.
JSON output is much more informative:

it tries to display a real execution path of the query;
it describes pushed conditions;
temporary table and index creation is displayed in more precise

More advanced example, nested loop join and pushed conditions (see "attached_conditions"):

mysql> CREATE TABLE t2 (i INT KEY, j INT);
Query OK, 0 rows affected (0.00 sec)

mysql> INSERT INTO t1 VALUES (1, 1), (2, 2), (3, 3);
Query OK, 3 rows affected (0.00 sec)
Records: 3  Duplicates: 0  Warnings: 0

mysql> INSERT INTO t2 SELECT * FROM t1;
Query OK, 3 rows affected (0.00 sec)
Records: 3  Duplicates: 0  Warnings: 0

mysql> EXPLAIN SELECT * FROM t1 JOIN t2 ON t1.i = t2.i WHERE t1.j > 1 AND t2.j < 3;
+----+-------------+-------+--------+---------------+---------+---------+-----------+------+-------------+
| id | select_type | table | type   | possible_keys | key     | key_len | ref       | rows | Extra       |
+----+-------------+-------+--------+---------------+---------+---------+-----------+------+-------------+
|  1 | SIMPLE      | t1    | ALL    | NULL          | NULL    | NULL    | NULL      |    3 | Using where |
|  1 | SIMPLE      | t2    | eq_ref | PRIMARY       | PRIMARY | 4       | test.t1.i |    1 | Using where |
+----+-------------+-------+--------+---------------+---------+---------+-----------+------+-------------+
2 rows in set (0.00 sec)

mysql> SET end_markers_in_json=true;
Query OK, 0 rows affected (0.00 sec)

mysql> EXPLAIN FORMAT=JSON SELECT * FROM t1 JOIN t2 ON t1.i = t2.i WHERE t1.j > 1 AND t2.j < 3;
+------------------------------------------------- ...
| EXPLAIN
+------------------------------------------------- ...
| {
  "query_block": {
    "select_id": 1,
    "nested_loop": [
      {
        "table": {
          "table_name": "t1",
          "access_type": "ALL",
          "rows": 3,
          "filtered": 100,
          "attached_condition": "((`test`.`t1`.`j` > 1) and (`test`.`t1`.`i` is not null))"
        } /* table */
      },
      {
        "table": {
          "table_name": "t2",
          "access_type": "eq_ref",
          "possible_keys": [
            "PRIMARY"
          ] /* possible_keys */,
          "key": "PRIMARY",
          "key_length": "4",
          "ref": [
            "test.t1.i"
          ] /* ref */,
          "rows": 1,
          "filtered": 100,
          "attached_condition": "(`test`.`t2`.`j` < 3)"
        } /* table */
      }
    ] /* nested_loop */
  } /* query_block */
} |
+------------------------------------------------- ...
1 row in set, 1 warning (0.00 sec)

mysql> SHOW WARNINGS;
+-------+------+---------------------------------- ...
| Level | Code | Message
+-------+------+---------------------------------- ...
| Note  | 1003 | /* select#1 */ select `test`.`t1`.`i` AS `i`,`test`.`t1`.`j` AS `j`,`test`.`t2`.`i` AS `i`,`test`.`t2`.`j` AS `j` from `test`.`t1` join `test`.`t2` where ((`test`.`t2`.`i` = `test`.`t1`.`i`) and (`test`.`t1`.`j` > 1) and (`test`.`t2`.`j` < 3)) |
+-------+------+---------------------------------- ...
1 row in set (0.00 sec)

Thus, instead of the "Using where" in the traditional EXPLAIN output we can see where each part of query condition was pushed down and what part was pushed.

Similar example: "Using index" goes "index_condition":

mysql> EXPLAIN SELECT * FROM t2 WHERE i > 1 AND j < 3;
+----+-------------+-------+-------+---------------+---------+---------+------+------+------------------------------------+
| id | select_type | table | type  | possible_keys | key     | key_len | ref  | rows | Extra                              |
+----+-------------+-------+-------+---------------+---------+---------+------+------+------------------------------------+
|  1 | SIMPLE      | t2    | range | PRIMARY       | PRIMARY | 4       | NULL |    2 | Using index condition; Using where |
+----+-------------+-------+-------+---------------+---------+---------+------+------+------------------------------------+
1 row in set (0.00 sec)

mysql> EXPLAIN FORMAT=JSON SELECT * FROM t2 WHERE i > 1 AND j < 3;
+------------------------------------------------- ...
| EXPLAIN
+------------------------------------------------- ...
| {
  "query_block": {
    "select_id": 1,
    "table": {
      "table_name": "t2",
      "access_type": "range",
      "possible_keys": [
        "PRIMARY"
      ] /* possible_keys */,
      "key": "PRIMARY",
      "key_length": "4",
      "rows": 2,
      "filtered": 100,
      "index_condition": "(`test`.`t2`.`i` > 1)",
      "attached_condition": "(`test`.`t2`.`j` < 3)"
    } /* table */
  } /* query_block */
} |
+------------------------------------------------- ...
1 row in set, 1 warning (0.00 sec)

mysql> SHOW WARNINGS;
+-------+------+---------------------------------- ...
| Level | Code | Message                                                                                                                                      |
+-------+------+---------------------------------- ...
| Note  | 1003 | /* select#1 */ select `test`.`t2`.`i` AS `i`,`test`.`t2`.`j` AS `j` from `test`.`t2` where ((`test`.`t2`.`i` > 1) and (`test`.`t2`.`j` < 3)) |
+-------+------+---------------------------------- ...
1 row in set (0.00 sec)

Also the new explain reflects the proper execution order of "grouping_operation" (GROUP BY clause), "ordering_operation" (ORDER BY) and "duplicates_removal" (DISTINCT etc.) operations.
Each of them may be an initiator of temporary table or temporary index (filesort) creation.
One of the most advanced features of new EXPLAIN is how it displays temporary tables and temporary indices.
Whereas the traditional EXPLAIN may "aggregate" two facts of temporary table creation into the single "Using temporary table" message (and similar for temporary index), the new JSON output tries to display both (if any) at the proper place: i.e. if the "ORDER BY" clause is the initiator of a temporary table creation, the new EXPLAIN shows "using_temporary_table": true key-value pair under the "ordering_operation" node, and if, for example, the "GROUP BY" causes a temporary index creation, the EXPLAIN outputs "using_filesort": true pair under the "grouping_operation" node.

Simple example with DISTINCT, GROUP BY and ORDER BY:

mysql> EXPLAIN SELECT DISTINCT * FROM t1 GROUP BY i ORDER BY j;
+----+-------------+-------+------+---------------+------+---------+------+------+---------------------------------+
| id | select_type | table | type | possible_keys | key  | key_len | ref  | rows | Extra                           |
+----+-------------+-------+------+---------------+------+---------+------+------+---------------------------------+
|  1 | SIMPLE      | t1    | ALL  | NULL          | NULL | NULL    | NULL |    3 | Using temporary; Using filesort |
+----+-------------+-------+------+---------------+------+---------+------+------+---------------------------------+
1 row in set (0.00 sec)

mysql> EXPLAIN FORMAT=JSON SELECT DISTINCT * FROM t1 GROUP BY i ORDER BY j;
+------------------------------------------------- ...
| EXPLAIN
+------------------------------------------------- ...
| {
  "query_block": {
    "select_id": 1,
    "ordering_operation": {
      "using_filesort": true,
      "duplicates_removal": {
        "using_filesort": false,
        "grouping_operation": {
          "using_temporary_table": true,
          "using_filesort": false,
          "table": {
            "table_name": "t1",
            "access_type": "ALL",
            "rows": 3,
            "filtered": 100
          } /* table */
        } /* grouping_operation */
      } /* duplicates_removal */
    } /* ordering_operation */
  } /* query_block */
} |
+------------------------------------------------- ...
1 row in set, 1 warning (0.00 sec)

mysql> SHOW WARNINGS;
+-------+------+---------------------------------- ...
| Level | Code | Message                                                                                                                                         |
+-------+------+---------------------------------- ...
| Note  | 1003 | /* select#1 */ select distinct `test`.`t1`.`i` AS `i`,`test`.`t1`.`j` AS `j` from `test`.`t1` group by `test`.`t1`.`i` order by `test`.`t1`.`j` |
+-------+------+---------------------------------- ...
1 row in set (0.00 sec)

Another advanced feature is how the new EXPLAIN displays table materializations. It includes "derived tables", semi-join materialization etc.
Update: See Guilhem's post about subqueries with materialization for a complicated example.

Trivial subquery materialization example: "derived table"

mysql> EXPLAIN SELECT * FROM (SELECT * FROM t1) t;
+----+-------------+------------+------+---------------+------+---------+------+------+-------+
| id | select_type | table      | type | possible_keys | key  | key_len | ref  | rows | Extra |
+----+-------------+------------+------+---------------+------+---------+------+------+-------+
|  1 | PRIMARY     | <derived2> | ALL  | NULL          | NULL | NULL    | NULL |    3 | NULL  |
|  2 | DERIVED     | t1         | ALL  | NULL          | NULL | NULL    | NULL |    3 | NULL  |
+----+-------------+------------+------+---------------+------+---------+------+------+-------+
2 rows in set (0.00 sec)

mysql> EXPLAIN FORMAT=JSON SELECT * FROM (SELECT * FROM t1) t;
+------------------------------------------------- ...
| EXPLAIN
+------------------------------------------------- ...
| {
  "query_block": {
    "select_id": 1,
    "table": {
      "table_name": "t",
      "access_type": "ALL",
      "rows": 3,
      "filtered": 100,
      "materialized_from_subquery": {
        "using_temporary_table": true,
        "dependent": false,
        "cacheable": true,
        "query_block": {
          "select_id": 2,
          "table": {
            "table_name": "t1",
            "access_type": "ALL",
            "rows": 3,
            "filtered": 100
          } /* table */
        } /* query_block */
      } /* materialized_from_subquery */
    } /* table */
  } /* query_block */
} |
+------------------------------------------------- ...
1 row in set, 1 warning (0.00 sec)

mysql> SHOW WARNINGS;
+-------+------+---------------------------------- ...
| Level | Code | Message                                                                                                                                             |
+-------+------+---------------------------------- ...
| Note  | 1003 | /* select#1 */ select `t`.`i` AS `i`,`t`.`j` AS `j` from (/* select#2 */ select `test`.`t1`.`i` AS `i`,`test`.`t1`.`j` AS `j` from `test`.`t1`) `t` |
+-------+------+---------------------------------- ...
1 row in set (0.00 sec)

The new JSON EXPLAIN is feature rich, please try it and have fun!

And, at the end of this post, let me thank Evgeny Potemkin and Guilhem Bichot for their great help in design and implementation of structured EXPLAIN!

DATETIME DEFAULT NOW() finally available.

Martin — Tue, 10 Apr 2012 06:04:00 +0000

Having been rather desired for a while now, this feature is finally available as of MySQL Server version 5.6.5. It started out as the innocuous bug #27645 back in 2007, not really commanding much attention from anyone. But since, the page has seen around a hundred posts from users. This is a lot of posts for a bug page.

When I got to work on this, I started out looking at how functions in the default clause worked for the one supported case, CURRENT_TIMESTAMP (a.k.a. NOW() in MySQL) for TIMESTAMP columns. It turned out to be a little more complex than it had to, the TIMESTAMP type has a lot of special rules attached to it that no other types have, not even DATETIME.

One thing that struck me as a little odd was that you can only have one column with a function in the default or on update clause. So I had to take the decision how to deal with that restriction as we introduced DATETIME DEFAULT CURRENT_TIMESTAMP. Should we forbid having a TIMESTAMP DEFAULT CURRENT TIMESTAMP if there was a DATETIME DEFAULT CURRENT_TIMESTAMP? No matter how I looked at it, there would have to be a bunch of new convoluted special rules added that I couldn't motivate to myself. Moreover, a lot of users seemed to request having one DATETIME column with "default now" and another one "on update now", so they could track both creation and last update time to a row. The request was not lost on me: I decided to lift the one-column-with-NOW() restriction altogether. It made documentation simpler and avoided having rules applying only TIMESTAMP spill over on DATETIME. As expected, there was no technical reason for forbidding it, and the code involved needed an overhaul anyways.

The rules

I will not attempt to describe the various TIMESTAMP rules here, the manual does a great job at it already. Instead I will present the new set of rules for how DATETIME DEFAULT / ON UPDATE CURRENT_TIMESTAMP works.

Trying to store a null value in a DATETIME NOT NULL column will always yield an error.
A DATETIME column accepting nulls has NULL as default value unless specified.
There are no implicit defaults for DATETIME columns except the one above.
A DATETIME DEFAULT CURRENT_TIMESTAMP column will store CURRENT_TIMESTAMP if and only if an insert statement does not list the column or store a full row.
A DATETIME ON UPDATE CURRENT_TIMESTAMP column will store CURRENT_TIMESTAMP if the row is updated and the new row is different from the previous row.

These rules sure look simple enough, don't they? Well, of course there are some more ins and outs to it if you look close enough. Hopefully you should not have to memorize all of these scenarios but it would be unfair of me not to at least mention them.

In rule #4, "an insert statement" includes, of course INSERT, LOAD and REPLACE statements. LOAD statements will store "0000-00-00 00:00:00" (a.k.a. the 'zero date') in a DATETIME column if the file contains a null at the column's position. Under strict sql_mode, the entire statement will fail. TIMESTAMP columns still store CURRENT_TIMESTAMP in this case, regardless of default.

In rule #5, the statements that can update a row are UPDATE and INSERT ... ON DUPLICATE KEY UPDATE ... when there is a duplicate primary key.

Lifting the one-column-with-function-default restriction also has some side-effects when you add or move columns.

As before, the first column in a table that is declared simply "TIMESTAMP" will implicitly be promoted to TIMESTAMP DEFAULT CURRENT_TIMESTAMP ON UPDATE CURRENT_TIMESTAMP. If you add another column that is "TIMESTAMP" before it, they will both be as that long line I just wrote. Previously, you would get an error in this case.
Oh, yeah, error number 1293, a.k.a. ER_TOO_MUCH_AUTO_TIMESTAMP_COLS [sic], can't happen anymore. There's no limit to how many columns with CURRENT_TIMESTAMP you can have. Knock yourself out.

When is NOW()?

In MySQL, CURRENT_TIMESTAMP is defined as the query start time, the time when the query arrives at the server. This means that the value is constant during the execution of the query. So don't be surprised if you update a million rows of type DATETIME(6) ON UPDATE NOW(6) - microsecond precision - and they all get the same update time.

Index Condition Pushdown to the rescue!

Jørgen Løland — Mon, 19 Mar 2012 13:22:00 +0000

A while ago, I explained how range access in a multiple-part index works and why MySQL can't utilize key parts beyond the first occurrence of some often used comparison operators. Luckily, there is a great improvement underway in MySQL 5.6 that will remedy much of this limitation. Meet Index Condition Pushdown.

How does ICP work?

Index Condition Pushdown is a new way for MySQL to evaluate conditions. Instead of evaluating conditions on rows read from a table, ICP makes it possible to evaluate conditions in the index and thereby avoid looking at the table if the condition is false.

Let's assume that we have a multiple-part index covering columns (keypart_1, ..., keypart_n). Further assume that we have a condition with a comparison operator on keypart_1 that does not allow keypart_2,...,keypart_n to be used as a range condition (more on that here).

When MySQL does range access without ICP enabled, the index is traversed to locate rows in the table that are within the range(s) relevant for the conditions on keypart_1. The rows in these ranges are read from the table and returned from the storage engine to the MySQL server. The server then evaluates the remaining conditions, including those that apply to keypart_2,..,keypart_n.

Read more »

Optimizer tracing used by others!

Guilhem Bichot — Thu, 09 Feb 2012 07:51:00 +0000

In a previous post, I had explained how to use MySQL's optimizer tracing, a new feature which appeared in MySQL 5.6.3.

As a developer, it feels really good to see others adopt my work and make something useful out of it! My colleague Dimitri Kravtchuk, who is one of our top Benchmarking experts, has written a blog post where he shows how the optimizer tracing has helped him to figure out why, under load, once in a while and randomly, a query performed badly. His investigation technique may be reusable by other people, so I encourage you to read more about it, here.

Understanding the unique_subquery optimization

Guilhem Bichot — Tue, 29 Nov 2011 06:37:00 +0000

If you use the EXPLAIN SELECT statement to see how your subqueries are treated by MySQL, you may sometimes meet the "unique_subquery" optimization. Here is how the manual describes it:

"unique_subquery: this type replaces ref for some IN subqueries of the following form: value IN (SELECT primary_key FROM single_table WHERE some_expr); unique_subquery is just an index lookup function that replaces the subquery completely for better efficiency".

Few weeks ago, while I was reviewing a patch fixing a bug in unique_subquery, I got a "simplification" pulsion. I told myself that:

unique_subquery is an optimization for a special case of simple subqueries (single inner table, using index, no aggregates);
we have a more general system around, used for more complex subqueries, naturally capable of handling simple ones too if we wanted;
this general system does not have the bug in question...

Then I wondered: what if we removed the unique_subquery optimization, and let the general system handle this simple subquery? This would certainly simplify code, and thus maintainance...But before removing it, of course, we should check whether unique_subquery brings a significant performance benefit.

So today I'm testing unique_subquery against the DBT3 benchmark. I grab a copy of MySQL 5.6.3, and focus on the sixteenth query of DBT3, which contains a subquery (in red) suitable for handling by unique_subquery:


select
 p_brand,
 p_type,
 p_size,
 count(distinct ps_suppkey) as supplier_cnt
from
 partsupp,
 part
where
 p_partkey = ps_partkey
 and p_brand <> 'Brand#23'
 and p_type not like 'LARGE PLATED%'
 and p_size in (43, 1, 25, 5, 35, 12, 42, 40)
 and ps_suppkey not in (
  select
   s_suppkey
  from
   supplier
  where
   s_comment like '%Customer%Complaints%'
 )
group by
 p_brand,
 p_type,
 p_size
order by
 supplier_cnt desc,
 p_brand,
 p_type,
 p_size;

This query executes in 0.65 seconds on my Linux box, and EXPLAIN is:


+----+--------------------+----------+-----------------+----------------------+--------------+---------+---------------------+--------+----------------------------------------------+
| id | select_type        | table    | type            | possible_keys        | key          | key_len | ref                 | rows   | Extra                                        |
+----+--------------------+----------+-----------------+----------------------+--------------+---------+---------------------+--------+----------------------------------------------+
|  1 | PRIMARY            | part     | ALL             | PRIMARY              | NULL         | NULL    | NULL                | 199498 | Using where; Using temporary; Using filesort |
|  1 | PRIMARY            | partsupp | ref             | PRIMARY,i_ps_partkey | i_ps_partkey | 4       | dbt3.part.p_partkey |      2 | Using where; Using index                     |
|  2 | DEPENDENT SUBQUERY | supplier | unique_subquery | PRIMARY              | PRIMARY      | 4       | func                |      1 | Using where                                  |
+----+--------------------+----------+-----------------+----------------------+--------------+---------+---------------------+--------+----------------------------------------------+

When I disable unique_subquery (by modifying MySQL's C++ code), EXPLAIN becomes:


+----+--------------------+----------+--------+----------------------+--------------+---------+---------------------+--------+----------------------------------------------+
| id | select_type        | table    | type   | possible_keys        | key          | key_len | ref                 | rows   | Extra                                        |
+----+--------------------+----------+--------+----------------------+--------------+---------+---------------------+--------+----------------------------------------------+
|  1 | PRIMARY            | part     | ALL    | PRIMARY              | NULL         | NULL    | NULL                | 199498 | Using where; Using temporary; Using filesort |
|  1 | PRIMARY            | partsupp | ref    | PRIMARY,i_ps_partkey | i_ps_partkey | 4       | dbt3.part.p_partkey |      2 | Using where; Using index                     |
|  2 | DEPENDENT SUBQUERY | supplier | eq_ref | PRIMARY              | PRIMARY      | 4       | func                |      1 | Using where                                  |
+----+--------------------+----------+--------+----------------------+--------------+---------+---------------------+--------+----------------------------------------------+

The only change, as expected, is that "unique_subquery" becomes "eq_ref". The used index is the same (the primary key of the "supplier" table). The optimizer has the same notion of unicity: "unique_subquery" and "eq_ref" both denote that a single lookup is needed, as the index is UNIQUE. Same index, same number of lookups: execution could well be as fast with "eq_ref" as it was with "unique_subquery".
But... no. Query now executes in 0.80 seconds. 23% slower than with unique_subquery!

Finer-grained timing shows that the extra 0.15 seconds are indeed lost in the subquery evaluation code.

To understand this, let's follow the execution in detail, based on EXPLAIN output above.

First line of EXPLAIN output: we do a table scan on the "part" table ("type=ALL" means "table scan") . The "rows" column of EXPLAIN suggests that we are going to have 199,498 rows of "part".
Second line of EXPLAIN output: for each row from the "part" table, we do an index lookup ("ref") into the "i_ps_partkey" index of the "partsupp" table; apparently such lookup will find two rows ("rows=2").
At this point, we have a row made of needed columns of "part" and of "partsupp". An upper estimate of the number of those rows is 199,498 multiplied by 2: 400,000. Actually, the real number is around 120,000 (there has been filtering going on, as the "Using where" indicates).
Then we evaluate the WHERE clause and thus the "NOT IN (subquery)" predicate (the "DEPENDENT SUBQUERY"). 120,000 evaluations of such predicate. And that's where the difference is.

EXPLAIN EXTENDED and then SHOW WARNINGS show how the predicate
looks like. Let's start with the case where unique_subquery is disabled:


/* select#1 */ select `dbt3`.`part`.`p_brand` AS `p_brand`,`dbt3`.`part`.`p_type` AS `p_type`,`dbt3`.`part`.`p_size` AS `p_size`,count(distinct `dbt3`.`partsupp`.`ps_suppkey`) AS `supplier_cnt` from `dbt3`.`partsupp` join `dbt3`.`part` where ((`dbt3`.`partsupp`.`ps_partkey` = `dbt3`.`part`.`p_partkey`) and (`dbt3`.`part`.`p_brand` <> 'Brand#23') and (not((`dbt3`.`part`.`p_type` like 'LARGE PLATED%'))) and (`dbt3`.`part`.`p_size` in (43,1,25,5,35,12,42,40)) and (not(<in_optimizer>(`dbt3`.`partsupp`.`ps_suppkey`,<exists>(/* select#2 */ select 1 from `dbt3`.`supplier` where ((`dbt3`.`supplier`.`s_comment` like '%Customer%Complaints%') and (<cache>(`dbt3`.`partsupp`.`ps_suppkey`) = `dbt3`.`supplier`.`s_suppkey`))))))) group by `dbt3`.`part`.`p_brand`,`dbt3`.`part`.`p_type`,`dbt3`.`part`.`p_size` order by count(distinct `dbt3`.`partsupp`.`ps_suppkey`) desc,`dbt3`.`part`.`p_brand`,`dbt3`.`part`.`p_type`,`dbt3`.`part`.`p_size`

Above, the part in red says that


ps_suppkey not in (
        select
            s_suppkey
        from
            supplier
        where
            s_comment like '%Customer%Complaints%'
    )

has been transformed from "IN(non correlated subquery)" to "EXISTS(correlated subquery)", yielding this:


not exists (
        select
            1
        from
            supplier
        where
            s_comment like '%Customer%Complaints%'
                        AND s_suppkey = ps_suppkey
        )

or, more exactly (leaving out the NOT operator, for brevity):


<exists>(/* select#2 */ select 1 from `dbt3`.`supplier`
           where ((`dbt3`.`supplier`.`s_comment` like '%Customer%Complaints%')
           and (<cache>(`dbt3`.`partsupp`.`ps_suppkey`) = `dbt3`.`supplier`.`s_suppkey`)))

Evaluating this EXISTS() evaluates the new subquery. This means all the subquery evaluation machinery: calls to JOIN::exec(), sub_select(), evaluate_join_record()... Sure, deep down it does an index lookup like unique_subquery does, but all those function calls have a cost, and so has all the logic which is lying around ready to handle any complexity in the subquery, as this is generic subquery evaluation code ("if group_by do this", "if order_by do this", "if left_join do this": none of those if()s are entered, but deciding to enter them or not has a cost). Plus some initialization code. Plus some de-initialization code. This overhead, repeated 120,000 times, amounts to 0.15 seconds...

Now, EXPLAIN EXTENDED when unique_subquery is enabled:


/* select#1 */ select `dbt3`.`part`.`p_brand` AS `p_brand`,`dbt3`.`part`.`p_type` AS `p_type`,`dbt3`.`part`.`p_size` AS `p_size`,count(distinct `dbt3`.`partsupp`.`ps_suppkey`) AS `supplier_cnt` from `dbt3`.`partsupp` join `dbt3`.`part` where ((`dbt3`.`partsupp`.`ps_partkey` = `dbt3`.`part`.`p_partkey`) and (`dbt3`.`part`.`p_brand` <> 'Brand#23') and (not((`dbt3`.`part`.`p_type` like 'LARGE PLATED%'))) and (`dbt3`.`part`.`p_size` in (43,1,25,5,35,12,42,40)) and (not(<in_optimizer>(`dbt3`.`partsupp`.`ps_suppkey`,<exists>(<primary_index_lookup>(<cache>(`dbt3`.`partsupp`.`ps_suppkey`) in supplier on PRIMARY where ((`dbt3`.`supplier`.`s_comment` like '%Customer%Complaints%') and (<cache>(`dbt3`.`partsupp`.`ps_suppkey`) = `dbt3`.`supplier`.`s_suppkey`)))))))) group by `dbt3`.`part`.`p_brand`,`dbt3`.`part`.`p_type`,`dbt3`.`part`.`p_size` order by count(distinct `dbt3`.`partsupp`.`ps_suppkey`) desc,`dbt3`.`part`.`p_brand`,`dbt3`.`part`.`p_type`,`dbt3`.`part`.`p_size`

The optimizer has first done the same transformation (IN to EXISTS) as we saw before, then has done one more transformation, and EXISTS has become, as written in red above:


<exists>(<primary_index_lookup>(<cache>(`dbt3`.`partsupp`.`ps_suppkey`)
          in supplier on PRIMARY
          where ((`dbt3`.`supplier`.`s_comment` like '%Customer%Complaints%')
          and (<cache>(`dbt3`.`partsupp`.`ps_suppkey`) = `dbt3`.`supplier`.`s_suppkey`))))

which is directly an index lookup ("<primary_index_lookup>"), followed by an additional WHERE clause. So the overhead of full-blown subquery evaluation is
avoided. And this overhead is not neglectable, compared to the index lookup (assuming the relevant index pages are already in memory).

So the conclusion of my experiment is that unique_subquery is worth having. I'll have to direct simplification pulsions to some other code!

Note that there also exists a similar "index_subquery" optimization applying to non-unique indices. And it's worth having, for the same reasons.

Optimizer tracing: how to configure it

Guilhem Bichot — Tue, 04 Oct 2011 15:40:00 +0000

In this blog post, my colleague Jørgen Løland described a new feature of MySQL 5.6: Optimizer Tracing. I recommend reading his article, as it presents this new feature in a simple, easy-to-read manner.

The Optimizer Tracing feature can help understanding what the Optimizer is doing; it is available since milestone 5.6.3, announced October 3rd at Oracle Open World (here is the changelog). It's good to see it mature now; I remember that Sergey Petrunia did the first prototype back in March 2009!

Today I will be giving some must-have tips related to handling big traces.

First thing to know, a trace lives in main memory (internally it is allocated on the heap or free store of the MySQL Server). An SQL statement which gives the optimizer a lot of work (for example, by joining many tables) will generate a large trace. Up to gigabytes in some pathological cases! To avoid hogging memory then, a trace will never grow beyond the value of the @@optimizer_trace_max_mem_size session variable. Which has a default of 16 kilobytes; yes, it's a low value, to protect the innocent. I often raise it in my session, to 1 megabyte, which is enough for most queries in my daily work:

mysql> SET OPTIMIZER_TRACE_MAX_MEM_SIZE=1000000;

If a trace was truncated because exceeding this limit, the column INFORMATION_SCHEMA.OPTIMIZER_TRACE.MISSING_BYTES_BEYOND_MAX_MEM_SIZE shows a non-zero value: the number of bytes which could not be added to the trace.

When I read a trace I like to scroll up and down in it, search for some optimization phase (that means searching for some keyword in the trace); to do this, I set, in the "mysql" command-line client, the pager to "less" (I'm using Unix):

mysql> pager less;

This is very useful. I have all "less" commands under hand: can save to a file, can search for a regular expression match, search forward or backward... One last benefit is that when I have finished reading, quitting "less" makes the trace go away from the terminal, it does not linger on my screen forever, does not occupy the terminal's display history...

When there are many tables to join, as I said above the trace can grow a lot, because the Optimizer evaluates many possible join orders (using an algorithm known as "greedy search"): each evaluated join order is mentioned in the trace. Greedy search ends up being the greatest part of the trace. What if I want to see the trace of what happens in the Optimizer after greedy search is complete? If I set @@optimizer_trace_max_mem_size to a low value, it will trim greedy search and what follows. If I set @@optimizer_trace_max_mem_size to a high value, to see what I want, greedy search will be traced which will possibly exceed the amount of memory I can afford on this machine... It would be nice if I could tell the system: "please do not trace this and that". In my case, it would be "please do not trace greedy search".

As an example, let's consider twenty tables, t1...t20, all similar to this one:

mysql> CREATE TABLE t1 (a INT, INDEX(a)) ENGINE=MYISAM;
mysql> INSERT INTO t1 VALUES(x),(y); # x and y being some integers

and let's run this query, after turning tracing on:

mysql> SET OPTIMIZER_TRACE="ENABLED=ON,END_MARKER=ON";

mysql> EXPLAIN SELECT 1 FROM t1  JOIN t2 ON t2.a=t1.a JOIN t3 ON t3.a=t2.a JOIN t4 ON t4.a=t3.a JOIN t5 ON t5.a=t4.a JOIN t6 ON t6.a=t5.a JOIN t7 ON t7.a=t6.a JOIN t8 ON t8.a=t7.a JOIN t9 ON t9.a=t8.a JOIN t10 ON t10.a=t9.a JOIN t11 ON t11.a=t10.a JOIN t12 ON t12.a=t11.a JOIN t13 ON t13.a=t12.a JOIN t14 ON t14.a=t13.a JOIN t15 ON t15.a=t14.a JOIN t16 ON t16.a=t15.a JOIN t17 ON t17.a=t16.a JOIN t18 ON t18.a=t17.a JOIN t19 ON t19.a=t18.a JOIN t20 ON t20.a=t19.a;
+----+-------------+-------+-------+---------------+------+---------+------------+------+--------------------------+
| id | select_type | table | type  | possible_keys | key  | key_len | ref        | rows | Extra                    |
+----+-------------+-------+-------+---------------+------+---------+------------+------+--------------------------+
|  1 | SIMPLE      | t1    | index | a             | a    | 5       | NULL       |    2 | Using where; Using index |
|  1 | SIMPLE      | t2    | ref   | a             | a    | 5       | test.t1.a  |    1 | Using where; Using index |
|  1 | SIMPLE      | t3    | ref   | a             | a    | 5       | test.t2.a  |    1 | Using where; Using index |
|  1 | SIMPLE      | t4    | ref   | a             | a    | 5       | test.t1.a  |    1 | Using index              |
|  1 | SIMPLE      | t5    | ref   | a             | a    | 5       | test.t1.a  |    1 | Using index              |
|  1 | SIMPLE      | t6    | ref   | a             | a    | 5       | test.t1.a  |    1 | Using index              |
|  1 | SIMPLE      | t7    | ref   | a             | a    | 5       | test.t1.a  |    1 | Using index              |
|  1 | SIMPLE      | t8    | ref   | a             | a    | 5       | test.t1.a  |    1 | Using index              |
|  1 | SIMPLE      | t9    | ref   | a             | a    | 5       | test.t1.a  |    1 | Using where; Using index |
|  1 | SIMPLE      | t10   | ref   | a             | a    | 5       | test.t9.a  |    1 | Using where; Using index |
|  1 | SIMPLE      | t11   | ref   | a             | a    | 5       | test.t1.a  |    1 | Using where; Using index |
|  1 | SIMPLE      | t12   | ref   | a             | a    | 5       | test.t11.a |    1 | Using where; Using index |
|  1 | SIMPLE      | t13   | ref   | a             | a    | 5       | test.t12.a |    1 | Using where; Using index |
|  1 | SIMPLE      | t14   | ref   | a             | a    | 5       | test.t12.a |    1 | Using where; Using index |
|  1 | SIMPLE      | t15   | ref   | a             | a    | 5       | test.t12.a |    1 | Using where; Using index |
|  1 | SIMPLE      | t16   | ref   | a             | a    | 5       | test.t12.a |    1 | Using where; Using index |
|  1 | SIMPLE      | t17   | ref   | a             | a    | 5       | test.t12.a |    1 | Using where; Using index |
|  1 | SIMPLE      | t18   | ref   | a             | a    | 5       | test.t11.a |    1 | Using where; Using index |
|  1 | SIMPLE      | t19   | ref   | a             | a    | 5       | test.t12.a |    1 | Using where; Using index |
|  1 | SIMPLE      | t20   | ref   | a             | a    | 5       | test.t11.a |    1 | Using where; Using index |
+----+-------------+-------+-------+---------------+------+---------+------------+------+--------------------------+

As optimizer developer, it catches my eye that some tables have "Using where" and others don't. "Using where" tells me that a condition is evaluated after fetching a row from the table, but does not tell me what condition. To know more, I will look at the trace. But I'm not interested in the trace of greedy search, which likely accounts, in this 20-table example, for most of the total trace, and would just make my reading less comfortable, or even hog memory, if I had more than those 20 tables or more indices on them, or more complex conditions. So I do:

mysql> SET OPTIMIZER_TRACE_FEATURES="GREEDY_SEARCH=OFF";

and run the EXPLAIN again. To show the resulting trace, I'm posting a screenshot of how it is displaid by the JsonView Firefox add-on. Using this add-on requires taking two precautions:

turning off the end_marker flag of @@optimizer_trace (this flag is good for human-readability but is not JSON-compliant)
sending the trace to a file without escaping of newlines (which is why I use INTO DUMPFILE instead of INTO OUTFILE):

mysql> SET OPTIMIZER_TRACE="END_MARKER=OFF";
mysql> SELECT TRACE INTO DUMPFILE "/tmp/trace.json" FROM INFORMATION_SCHEMA.OPTIMIZER_TRACE;

Here's the trace now in Firefox:

We see how greedy_search=off has eliminated the trace of greedy search ("considered_execution_plans"), replacing it with just an ellipsis ("...")! Then there is what I wanted to see: the part after greedy search, named "attached_conditions_summary", which describes what condition is behind each "Using where" in EXPLAIN. There are equality conditions of course. Some coming directly from the "JOIN ON" conditions. Some deduced by equality propagation (if t1.a=t2.a and t2.a=t3.a then t1.a=t3.a, a new condition which we see is attached to t3). There are also "IS NOT NULL" conditions; indeed, an equality condition of the form t1.a=t2.a allows us to deduce that both t1.a and t2.a are not NULL, so if rows of t1 are retrieved first they can be filtered with this deduced condition, known as early NULL filtering.

There are other flags in @@optimizer_trace_features; we added a flag for each feature which we think can make the trace grow unreasonably large:

greedy search
repeated execution of subqueries (one execution per row)
repeated range optimization (known as "range checked for each record" in EXPLAIN)
range optimization in general.

I think I have shown enough for today. A positive note to finish: in the Optimizer team, this tracing has already helped us to debug some problems, so has started to fulfill its goal!

For the curious: the Optimizer Trace is covered in full detail, including the above, and more, in a chapter of the "MySQL Internals" manual.

Optimizer: new EXPLAIN for…

Gleb Shchepa — Tue, 04 Oct 2011 11:08:00 +0000

Optimizer: new EXPLAIN for data-modifiers

One of the new features of MySQL 5.6.3 is EXPLAIN command for data-modifying statements.
As it's obvious from its name, it outputs QEP (query execution plan) for INSERT, REPLACE, UPDATE and DELETE like old good one does for SELECT:

example:

mysql> EXPLAIN UPDATE t1 SET b = 'b' WHERE a > 2;
+----+-------------+-------+-------+---------------+------+---------+------+------+------------------------------+
| id | select_type | table | type  | possible_keys | key  | key_len | ref  | rows | Extra                        |
+----+-------------+-------+-------+---------------+------+---------+------+------+------------------------------+
|  1 | SIMPLE      | t1    | range | a,a_2         | a    | 16      | NULL |    2 | Using where; Using temporary |
+----+-------------+-------+-------+---------------+------+---------+------+------+------------------------------+
1 row in set (0.00 sec)

All kinds of MySQL syntax are supported:

INSERT from SELECT:

mysql> EXPLAIN INSERT INTO t1 SELECT * FROM t2 WHERE a IN (1, 3, 5);
+----+-------------+-------+-------+---------------+------+---------+------+------+-----------------------+
| id | select_type | table | type  | possible_keys | key  | key_len | ref  | rows | Extra                 |
+----+-------------+-------+-------+---------------+------+---------+------+------+-----------------------+
|  1 | SIMPLE      | t2    | range | t2i1          | t2i1 | 4       | NULL |    3 | Using index condition |
+----+-------------+-------+-------+---------------+------+---------+------+------+-----------------------+
1 row in set (0.00 sec)

EXPLAIN for INSERT ... VALUES works as a special case of the INSERT ... SELECT VALUES FROM DUAL:

trivial EXPLAIN INSERT ... VALUES:

mysql> EXPLAIN INSERT INTO t1 VALUES (1, 2, 3);
+----+-------------+-------+------+---------------+------+---------+------+------+----------------+
| id | select_type | table | type | possible_keys | key  | key_len | ref  | rows | Extra          |
+----+-------------+-------+------+---------------+------+---------+------+------+----------------+
|  1 | SIMPLE      | NULL  | NULL | NULL          | NULL | NULL    | NULL | NULL | No tables used |
+----+-------------+-------+------+---------------+------+---------+------+------+----------------+
1 row in set (0.00 sec)

mysql> EXPLAIN INSERT INTO t1 SELECT 1, 2, 3 FROM DUAL;
+----+-------------+-------+------+---------------+------+---------+------+------+----------------+
| id | select_type | table | type | possible_keys | key  | key_len | ref  | rows | Extra          |
+----+-------------+-------+------+---------------+------+---------+------+------+----------------+
|  1 | SIMPLE      | NULL  | NULL | NULL          | NULL | NULL    | NULL | NULL | No tables used |
+----+-------------+-------+------+---------------+------+---------+------+------+----------------+
1 row in set (0.00 sec)

multi-table UPDATE:

mysql> EXPLAIN UPDATE t1, t2 SET t1.b = t2.b WHERE t1.a = t2.a;
+----+-------------+-------+------+---------------+------+---------+-----------+------+-------+
| id | select_type | table | type | possible_keys | key  | key_len | ref       | rows | Extra |
+----+-------------+-------+------+---------------+------+---------+-----------+------+-------+
|  1 | SIMPLE      | t1    | ALL  | PRIMARY       | NULL | NULL    | NULL      | 3072 |       |
|  1 | SIMPLE      | t2    | ref  | t2i1          | t2i1 | 4       | test.t1.a |    1 |       |
+----+-------------+-------+------+---------------+------+---------+-----------+------+-------+
2 rows in set (0.00 sec)

multi-table DELETE:

mysql> EXPLAIN DELETE FROM t1 USING t1 JOIN t2 ON t1.a = t2.a;
+----+-------------+-------+------+---------------+------+---------+-----------+------+-------------+
| id | select_type | table | type | possible_keys | key  | key_len | ref       | rows | Extra       |
+----+-------------+-------+------+---------------+------+---------+-----------+------+-------------+
|  1 | SIMPLE      | t1    | ALL  | PRIMARY       | NULL | NULL    | NULL      | 3072 |             |
|  1 | SIMPLE      | t2    | ref  | t2i1          | t2i1 | 4       | test.t1.a |    1 | Using index |
+----+-------------+-------+------+---------------+------+---------+-----------+------+-------------+
2 rows in set (0.00 sec)

For single-table UPDATE and DELETE it may be interesting to explain subquery execution:

single-table UPDATE with a subquery:

mysql> EXPLAIN UPDATE t1 SET b = '12345' WHERE a IN (SELECT a FROM t2);
+----+--------------------+-------+----------------+---------------+------+---------+------+------+-------------+
| id | select_type        | table | type           | possible_keys | key  | key_len | ref  | rows | Extra       |
+----+--------------------+-------+----------------+---------------+------+---------+------+------+-------------+
|  1 | PRIMARY            | t1    | ALL            | PRIMARY       | NULL | NULL    | NULL | 3072 | Using where |
|  2 | DEPENDENT SUBQUERY | t2    | index_subquery | t2i1          | t2i1 | 4       | func |    1 | Using index |
+----+--------------------+-------+----------------+---------------+------+---------+------+------+-------------+
2 rows in set (0.00 sec)

... or even:

single-table DELETE with subqueries:

mysql> EXPLAIN DELETE FROM t1 WHERE a IN (SELECT t2.a FROM t2 JOIN t3 WHERE t2.b = t3.b AND t3.a IN (SELECT a FROM t4));
+----+--------------------+-------+------+---------------+------+---------+------+------+-------------- - - -
| id | select_type        | table | type | possible_keys | key  | key_len | ref  | rows | Extra
+----+--------------------+-------+------+---------------+------+---------+------+------+-------------- - - -
|  1 | PRIMARY            | t1    | ALL  | PRIMARY       | NULL | NULL    | NULL | 3072 | Using where
|  2 | DEPENDENT SUBQUERY | t2    | ref  | t2i1          | t2i1 | 4       | func |    1 |
|  2 | DEPENDENT SUBQUERY | t3    | ALL  | NULL          | NULL | NULL    | NULL | 3072 | Using where;
|  3 | DEPENDENT SUBQUERY | t4    | ALL  | NULL          | NULL | NULL    | NULL | 3072 | Using where
+----+--------------------+-------+------+---------------+------+---------+------+------+-------------- - - -
4 rows in set (0.00 sec)

Manuals are available here and here.

Optimizer tracing: Query Execution Plan descriptions beyond EXPLAIN

Jørgen Løland — Tue, 04 Oct 2011 10:02:00 +0000

Understanding why MySQL chooses a particular join order or why table scan is chosen instead of range scan is often very hard even for experienced MySQL users. Two almost identical queries, differing only in constant values, may produce completely different plans. That's why we're introducing a great new feature in 5.6: Optimizer Tracing. The target users of this feature are developers and MySQL users experienced enough to understand the ins and outs of EXPLAIN.

What Optimizer Tracing is
You may already have guessed this, but optimizer tracing is a printout of important decisions the MySQL optimizer has done during the process of making the Query Execution Plan.

The trace is presented in JSON format which is easy to read both for humans and others.

Currently, the optimizer trace includes short explanations for:

Why the join order was chosen.
Important query transformations like IN to EXISTS.
The access methods applicable and why one of them was chosen.
Which conditions are attached to each table (i.e., what hides behind "Using where" in EXPLAIN)

More coverage will be added as we go along.

What Optimizer Tracing is NOT
The feature is not, and never will be, complete in the sense that it does not describe all choices the optimizer does. However, we're going to add more information when we find valuable things to add. We will not guarantee backwards compatibility like we do for EXPLAIN. This gives us the freedom to improve tracing at a high pace without going through multi-release deprecation warnings etc. In other words: optimizer tracing is not a replacement for EXPLAIN.

A quick tour
The best way get a feeling of optimizer tracing is to give it a try. Below is a teaser:
Read more »

Batched Key Access Speeds Up Disk-Bound Join Queries

Øystein — Mon, 03 Oct 2011 18:13:00 +0000

A new feature in MySQL 5.6.3 Development Milestone Release is Batched Key Access (BKA). BKA can be applied when an index lookup can be used to execute a join query. One example of such a query is:

mysql> SELECT * FROM customer JOIN orders ON c_custkey = o_custkey;

Given that the customer table is significantly smaller than the orders table, and assuming that we have an index on the o_custkey column of orders, MySQL have traditionally executed this join as follows: Scan the entire customer table, and for each row in the customer table, do an index look-up into the orders table to find matching rows. This strategy is know as Index Nested Loops Join, or as MySQL EXPLAIN puts it:

+----+-------------+----------+------+---------------+-------------+---------+-------------------------+--------+-------+
| id | select_type | table    | type | possible_keys | key         | key_len | ref                     | rows   | Extra |
+----+-------------+----------+------+---------------+-------------+---------+-------------------------+--------+-------+
|  1 | SIMPLE      | customer | ALL  | PRIMARY       | NULL        | NULL    | NULL                    | 150000 |       |
|  1 | SIMPLE      | orders   | ref  | i_o_custkey   | i_o_custkey | 5       | dbt3.customer.c_custkey |      7 |       |
+----+-------------+----------+------+---------------+-------------+---------+-------------------------+--------+-------+

If BKA is applied, MySQL will instead buffer keys to be used for index look-up in the join buffer, and each time the join buffer is full, it will do a batched look-up on the index. That is, the whole set of keys from the join buffer is sent to the storage engine in one batch. For this purpose, MySQL Server uses the Multi-Range Read interface of the Storage Engine API.

Multi-Range Read (MRR)

The advantage of requesting a batch of rows from the storage engine, is that the storage engine may be able to deliver the rows more efficiently that way. The MRR interface has for some time been used in MySQL Cluster since it reduces communication between nodes by making it possible to request more than one row per round-trip.

A new feature in MySQL 5.6.2 was Disk-Sweep Multi-Range Read (DS-MRR) optimizations for both InnoDB and MyISAM. When DS-MRR is applied, the storage engine will access the data rows in the order given by the base table; instead of in the order given by the index. For a disk-bound query this has two advantages:

All interesting rows on the same disk page will be accessed together. Hence, one do not risk that a page has been removed from the buffer pool between two accesses to the page.
Even if modern disks/file systems do not give any guarantees, accessing the pages in table order, will normally give close to sequential access to the disk. As we know, that should give much better performance compared to random access. (If multiple sessions access the disks simultaneously, the advantage of sequential access within a session will of course be less significant.)

Turning On Batched Key Access

While BKA is advantageous in a disk-bound system, it may actually reduce performance in a CPU-bound setting. (More on this below.) Since the MySQL Optimizer currently has no information on whether a table resides in memory or on disk, BKA is off by default.

You can turn on BKA by setting an optimizer_switch flag. Since BKA depends on MRR, the MRR flag also needs to be on. (This is default.) In addition, since the cost model for MRR is currently way too conservative, in order to use MRR, cost-based MRR optimization needs to be turned off. In other words, the following settings must be done in order for the Optimizer to consider BKA:

mysql> SET optimizer_switch='mrr=on,mrr_cost_based=off,batched_key_access=on';

With BKA turned on, EXPLAIN for the query presented earlier, will look like this:

+----+-------------+----------+------+---------------+-------------+---------+-------------------------+--------+----------------------------------------+
| id | select_type | table    | type | possible_keys | key         | key_len | ref                     | rows   | Extra                                  |
+----+-------------+----------+------+---------------+-------------+---------+-------------------------+--------+----------------------------------------+
|  1 | SIMPLE      | customer | ALL  | PRIMARY       | NULL        | NULL    | NULL                    | 150000 |                                        |
|  1 | SIMPLE      | orders   | ref  | i_o_custkey   | i_o_custkey | 5       | dbt3.customer.c_custkey |      7 | Using join buffer (Batched Key Access) |
+----+-------------+----------+------+---------------+-------------+---------+-------------------------+--------+----------------------------------------+

Performance Impact of BKA on DBT-3 Queries

The chart below shows query execution times, with and without BKA, for all the queries of the DBT-3 benchmark where BKA can be used. The size of the database is DBT-3 scale 1 (4 GB), and in order to get disk bound queries, the size of the InnoDB buffer pool is just 50 MB. We see that, for most of the queries, the run time with BKA is around half the run time without BKA .

Note that Query 17 is an example of a query where it is not beneficial to use BKA even when the query is disk-bound. In that particular case, locality of accesses are very good without BKA, and applying BKA actually spreads accesses to related rows in time, decreasing the buffer cache hit ratio.

Effects of Increasing the Join Buffer Size

As mention above, the size of the batches used by BKA is determined by the size of the join buffer. It follows from the discussion above that the larger the batch, the more efficiently the storage engine may arrange its disk accesses. The results presented above were achieved with a default setting of join_buffer_size (128 kB). We will now look closer at what happens if we increase the size of the join buffer. For this purpose, we will use Query 13 (Customer Distribution Query) from the DBT-3 benchmark:

SELECT c_count, COUNT(*) AS custdist
FROM (
      SELECT c_custkey, COUNT(o_orderkey) AS c_count
      FROM customer LEFT OUTER JOIN orders ON
        c_custkey = o_custkey AND o_comment NOT LIKE '%express%requests%'
      GROUP BY c_custkey
     ) AS c_orders 
GROUP BY c_count
ORDER BY custdist DESC, c_count DESC;

The heart of this query is the join between customer table and orders table:

+----+-------------+------------+-------+---------------+---------------+---------+-------------------------+--------+-----------------------------------------------------+
| id | select_type | table      | type  | possible_keys | key           | key_len | ref                     | rows   | Extra                                               |
+----+-------------+------------+-------+---------------+---------------+---------+-------------------------+--------+-----------------------------------------------------+
|  1 | PRIMARY     | <derived2> | ALL   | NULL          | NULL          | NULL    | NULL                    | 1050000 | Using temporary; Using filesort                     |
|  2 | DERIVED     | customer   | index | NULL          | i_c_nationkey | 5       | NULL                    |  150000 | Using index; Using temporary; Using filesort        |
|  2 | DERIVED     | orders     | ref   | i_o_custkey   | i_o_custkey   | 5       | dbt3.customer.c_custkey |       7 | Using where; Using join buffer (Batched Key Access) |
+----+-------------+------------+-------+---------------+---------------+---------+-------------------------+--------+-----------------------------------------------------+

Using BKA for this query, MySQL will fill the join buffer with customer keys and send a batch of keys to the storage engine. The storage engine will find the primary keys for the requested rows in the i_o_custkey index, sort the primary keys, and access the orders table in primary key order. In other words, there will be one pass over the orders table for each batch. The graph below shows the effect of increasing the join buffer on Query 13. (Note the logarithmic scale of the y-axis.) The query execution time goes down from 20 minutes with a default join buffer to less than 10 secs with a 32 MB join buffer!

BKA Performance When Queries are CPU-bound

As discussed above, BKA is designed to speed up disk-bound queries. Now we will look at what happens if BKA is used in a system where all the data in the database reside in main memory. The chart below presents the results of running the same DBT-3 queries with a InnoDB buffer pool of 5 GB. While the difference is not very significant for most queries, we see there are a few queries where the impact of BKA is quite negative.

The negative impact of BKA is not just the overhead of sorting the keys before accessing the table. If you look at the execution plan for QUERY 13 as presented above, it shows that the result of the join needs to be sorted in order to perform the group by operation of the subquery. This would not have been necessary, had not BKA been used. Without BKA, the result from the join would have been delivered in customer key order and grouping could be done without sorting. Hence, in this experiment, the execution time for Query 13 increased from 3.6 to 4.8 seconds when using BKA.

Use with Care

As I have shown, join query execution can benefit significantly from the use of Batched Key Access. However, there is also examples of queries where BKA do more harm than good. Hence, it should be used with care. My advice is to study the BKA performance for your typical queries and to only turn on BKA for queries that are known to benefit from it.

Kick-off

Guilhem Bichot — Mon, 03 Oct 2011 06:52:00 +0000

Hi all!
Here is a new blog; I'll post here some thoughts, tutorials... all related to my job - software developer at Oracle Corporation, working on MySQL. It will soon be nine years since I joined MySQL AB. After working on interesting topics: Replication, Online Backup, the Maria storage engine, each of them having taught me something, I'm now full-time on the Optimizer, and guess what - it is an interesting topic and it teaches me something!

Tips and tricks: Killer response time for non-overlapping intervals

Jørgen Løland — Tue, 27 Sep 2011 13:42:00 +0000

Assume you have a table where you store non-overlapping intervals using two columns, e.g. IP ranges. IP ranges are simple to represent using integer notation:

CREATE TABLE ip_owner (

owner_id int NOT NULL,
/* some columns */

   ip_start_int bigint NOT NULL,      /* IP address converted to integer */
   ip_end_int bigint NOT NULL,        /* IP address converted to integer */
   PRIMARY KEY (owner_id),

INDEX ip_range (ip_start_int, ip_end_int)

) ENGINE=InnoDB;

And then you find yourself in a situation where you want to know who, if anyone, owns the IP address X. This can be done using the following query:

SELECT * FROM ip_owner WHERE ip_start_int <= X AND ip_end_int >= X;

MySQL can resolve this using a range scan, but will unfortunately only be able to use the ip_start_int <= X part of the condition as a range as explained here. Thus, the query will either be resolved by range scan if fairly few records have ip_start_int <= X or table scan otherwise. That means unreliable response time because it will be much quicker to query low-valued IPs than high valued IPs. I inserted 1M records into the table before running the queries below:

Read more »

The MySQL range access method explained

Jørgen Løland — Tue, 23 Aug 2011 13:32:00 +0000

The range access method uses an index to read a subset of rows that form one or multiple continuous index value intervals. The intervals are defined by the query's range predicates, which are comparisons using any of =, <=>, IN(), IS NULL, IS NOT NULL, >, <, >=, <=, BETWEEN, !=, <> or LIKE.

Some examples:

SELECT * FROM blog WHERE author_id IN (1, 7, 8, 10)

SELECT * FROM orders WHERE value > 1000

You know that the range access method is used when EXPLAIN shows type=range.

Naturally, there has to be an index on the column used by the range predicate. Since indexes are ordered, MySQL will, for each interval, dive down the index using the interval start value and read it's way through the index leaves until it reaches the interval end value:

Read more »

The meaning of ref=func in MySQL EXPLAIN

Jørgen Løland — Wed, 17 Aug 2011 12:52:00 +0000

When EXPLAIN shows that a table is accessed using the [eq_]ref access type, we're used to look at the ref column to see where MySQL gets the value to look up from. Usually, we see either "const" if the value is provided as a constant in the query or a column name if the value is read from a column in an already read table:

EXPLAIN 

SELECT acc_rec.cust_id, acc_rec.amount, acc_rec.invoicenumber

FROM accounts_receivable as acc_rec

WHERE acc_rec.cust_id=1;

+----+-------------+---------+------+---------+-------+

| id | select_type | table   | type | key     | ref   |

+----+-------------+---------+------+---------+-------+

| 1  | SIMPLE      | acc_rec | ref  | cust_id | const |

+----+-------------+---------+------+---------+-------+



EXPLAIN 

SELECT acc_rec.cust_id, acc_rec.amount, acc_rec.invoicenumber,

       customers.firstname, customers.lastname, customers.phone

FROM accounts_receivable AS acc_rec JOIN customers AS cust

ON acc_rec.cust_id = customers.cust_id;

+----+-------------+---------+--------+---------+-----------------+

| id | select_type | table   | type   | key     | ref             |

+----+-------------+---------+--------+---------+-----------------+

| 1  | SIMPLE      | acc_rec | ALL    | NULL    | NULL            |

| 1  | SIMPLE      | cust    | eq_ref | PRIMARY | acc_rec.cust_id |

+----+-------------+---------+--------+---------+-----------------+

But what if ref shows the value "func"? In this case, the value used as input to [eq_]ref is the output of some function. A few examples:

Read more »

InnoDB Persistent Statistics Save the Day

Øystein — Thu, 05 May 2011 13:10:00 +0000

In my previous blog posting, I explained how I was able to get more stable query execution times by increasing the amount of sampling used to by InnoDB to calculate statistics. However, for my example query, Query 8 of the DBT-3 benchmark, the MySQL Optimizer still toggled between three different indexes to use when accessing one of the 8 tables.

I decided to try out InnoDB Persistent Statistics that is one of the new features in the recent MySQL 5.6.2 Development Milestone Release. According to the advertisement, this should give both more accurate and more stable statistics. The improved accuracy is achieved by using a more precise sampling algorithm, while the increased stability is achieved by giving the user full control over when statistics are recalculated. That is, the persistent statistics are not recalculated automatically.

In order to activate persistent statistics, you first need to run a script to create the tables to be used to store the statistics. Then, you can enable the feature by setting the system variable innodb_analyze_is_persistent. For the details, see the MySQL 5.6 Manual.

More Accurate Statistics

To investigate whether the new sampling algorithm gives more accurate statistics, I looked at the average and variance in the estimated cardinality of indexed columns over 100 runs of ANALYZE on the DBT-3 tables. The average of the estimates did not change much as it is actually pretty spot-on with the old sampling algorithm. It is the great variance that causes the observed inaccuracies.

The below chart shows the coefficient of variation for the estimated cardinality. (Columns that are listed more than once, are part of multiple indexes. If a bar in the bar chart is not visible, it means that there was no or very little variance between runs for this column.) The bar chart clearly shows that for most indexes, the sampling algorithm for persistent statistics gives less variance than the old sampling algorithm used with transient statistics. (The number of sampled index pages was 100 in both cases.)

More Stable Statistics

As mentioned above, the persistent statistics will be more stable because it is not updated automatically like the old transient statistics. This way, for our performance regression test, we can run ANALYZE once for each table, and all later runs on this database will use the same statistics. Another advantage of being able to control when statistics are recalculated, is that it can be scheduled at times when one can afford to use a higher sampling rate. The disadvantage is that it becomes the burden of the DBA to make sure to regularly initiate a recalculation of statistics to prevent that the statistics become outdated.

InnoDB Statistics Tables

The InnoDB statistics tables are ordinary tables that are created in a database called innodb. There are two tables: table_stats and index_stats that contain per-table and per-index statistics, respectively:

mysql> describe innodb.table_stats;
+--------------------------+---------------------+------+-----+-------------------+-----------------------------+
| Field                    | Type                | Null | Key | Default           | Extra                       |
+--------------------------+---------------------+------+-----+-------------------+-----------------------------+
| database_name            | varchar(64)         | NO   | PRI | NULL              |                             |
| table_name               | varchar(64)         | NO   | PRI | NULL              |                             |
| stats_timestamp          | timestamp           | NO   |     | CURRENT_TIMESTAMP | on update CURRENT_TIMESTAMP |
| n_rows                   | bigint(20) unsigned | NO   |     | NULL              |                             |
| clustered_index_size     | bigint(20) unsigned | NO   |     | NULL              |                             |
| sum_of_other_index_sizes | bigint(20) unsigned | NO   |     | NULL              |                             |
+--------------------------+---------------------+------+-----+-------------------+-----------------------------+
6 rows in set (0.01 sec)

mysql> describe innodb.index_stats;
+------------------+---------------------+------+-----+-------------------+-----------------------------+
| Field            | Type                | Null | Key | Default           | Extra                       |
+------------------+---------------------+------+-----+-------------------+-----------------------------+
| database_name    | varchar(64)         | NO   | PRI | NULL              |                             |
| table_name       | varchar(64)         | NO   | PRI | NULL              |                             |
| index_name       | varchar(64)         | NO   | PRI | NULL              |                             |
| stat_timestamp   | timestamp           | NO   |     | CURRENT_TIMESTAMP | on update CURRENT_TIMESTAMP |
| stat_name        | varchar(64)         | NO   | PRI | NULL              |                             |
| stat_value       | bigint(20) unsigned | NO   |     | NULL              |                             |
| sample_size      | bigint(20) unsigned | YES  |     | NULL              |                             |
| stat_description | varchar(1024)       | NO   |     | NULL              |                             |
+------------------+---------------------+------+-----+-------------------+-----------------------------+
8 rows in set (0.00 sec)

table_stats contains one row per table:

mysql> select * from innodb.table_stats where table_name='customer';
+---------------+------------+---------------------+--------+----------------------+--------------------------+
| database_name | table_name | stats_timestamp     | n_rows | clustered_index_size | sum_of_other_index_sizes |
+---------------+------------+---------------------+--------+----------------------+--------------------------+
| dbt3          | customer   | 2011-04-01 20:53:30 | 149911 |                 1764 |                      225 |
+---------------+------------+---------------------+--------+----------------------+--------------------------+

index_stats contains several rows per index, and the column stat_name identifies the type of statistics as described by the content of the stat_description column. The n_diff_pfx_ rows contain the cardinality statistics: For rows with stat_name = 'n_diff_pfx_01', stat_value contains the number of distinct values for the first column of the given index. For rows with stat_name = 'n_diff_pfx_02', stat_value contains the number of unique combinations of the two first columns of the given index, and so on. (Note that InnoDB indexes, in addition to the columns that were specified when the index was created, contain all columns of the primary key.)

mysql> select * from innodb.index_stats where table_name='customer';
+---------------+------------+---------------+---------------------+--------------+------------+-------------+-----------------------------------+
| database_name | table_name | index_name    | stat_timestamp      | stat_name    | stat_value | sample_size | stat_description                  |
+---------------+------------+---------------+---------------------+--------------+------------+-------------+-----------------------------------+
| dbt3          | customer   | i_c_nationkey | 2011-04-01 11:40:29 | n_diff_pfx01 |         25 |         171 | c_nationkey                       |
| dbt3          | customer   | i_c_nationkey | 2011-04-01 11:40:29 | n_diff_pfx02 |     150000 |         171 | c_nationkey,c_custkey             |
| dbt3          | customer   | i_c_nationkey | 2011-04-01 11:40:29 | n_leaf_pages |        171 |        NULL | Number of leaf pages in the index |
| dbt3          | customer   | i_c_nationkey | 2011-04-01 11:40:29 | size         |        225 |        NULL | Number of pages in the index      |
| dbt3          | customer   | PRIMARY       | 2011-04-01 11:40:29 | n_diff_pfx01 |     149911 |         100 | c_custkey                         |
| dbt3          | customer   | PRIMARY       | 2011-04-01 11:40:29 | n_leaf_pages |       1746 |        NULL | Number of leaf pages in the index |
| dbt3          | customer   | PRIMARY       | 2011-04-01 11:40:29 | size         |       1764 |        NULL | Number of pages in the index      |
+---------------+------------+---------------+---------------------+--------------+------------+-------------+-----------------------------------+

Manually Updating InnoDB Statistics Tables

Since the statistics tables are normal tables, they can be updated like any other MySQL table. For our performance regression tests, we have decided to record our own numbers in these tables. That way, we will be able to get the exact same numbers even if we for some reason need to recreate the statistics tables (e.g, in another database instance).

When we manually update the statistics tables for the DBT-3 benchmarks, we first turn on persistent statistics and run ANALYZE once for each table. This inserts all necessary rows in the statistics tables, and we will only need to update the relevant rows. Here are an example UPDATE statement for each table:

UPDATE innodb.table_stats SET n_rows=150000 
  WHERE database_name='dbt3' AND table_name='customer' ;
UPDATE innodb.index_stats SET stat_value=25, sample_size=NULL 
  WHERE database_name='dbt3' AND table_name='customer' 
    AND index_name='i_c_nationkey' AND stat_name='n_diff_pfx01';

By convention, I set index_stats.sample_size to NULL to indicate that the value is recorded and not computed by sampling.

A World of New Possibilities

As discussed above, InnoDB Persistent Statistics will be very useful in order to ensure that the same query execution plan is used every time a query is executed. It also gives the users the ability to control when the statistics are recalculated. However, persistent statistics opens up for even more new possibilities.

We will be able to use this feature to extend our testing of the query optimizer. By "faking" the statistics, we will be able to explore and test the execution of different query plans without having to actually modify the database.

It will also be possible for users to change the statistics in order to force a specific query plan. However, one risks introducing side-effects on other queries so this will have to be done with caution.

More Stable Query Execution Times by Improving InnoDB Statistics

Øystein — Thu, 14 Apr 2011 09:21:00 +0000

As part of ensuring that changes to the MySQL Optimizer does not introduce performance regressions, we have started a project to create a new performance regression test suite. One component in this test suite will be the DBT-3 test suite. However, we observed that the execution times for DBT-3 varied so much that, in its present form, it was not usable for detecting performance regressions.

In order to get a better understanding of what was going on, I looked closer at one of the queries that were run, Query 8. For this particular query, which contains an 8-table join, the execution times varied from 1 minute to 5 hours! Looking at 100 runs of this query, I detected 8 different query execution plans. Four of these plans represented differences in which sequence the tables were joined, while the last four differed from the first four with respect to which indexes were used.

Since the MySQL Optimizer is cost based, when the execution plans vary, this is usually because the underlying statistics reported from the storage engine varies. One way to investigate the statistics that the optimizer bases its decisions on, is to use the SHOW INDEX command:

mysql> show index from customer;
+----------+------------+---------------+--------------+-------------+-----------+-------------+----------+--------+------+------------+---------+---------------+
| Table    | Non_unique | Key_name      | Seq_in_index | Column_name | Collation | Cardinality | Sub_part | Packed | Null | Index_type | Comment | Index_comment |
+----------+------------+---------------+--------------+-------------+-----------+-------------+----------+--------+------+------------+---------+---------------+
| customer |          0 | PRIMARY       |            1 | c_custkey   | A         |      150000 |     NULL | NULL   |      | BTREE      |         |               |
| customer |          1 | i_c_nationkey |            1 | c_nationkey | A         |          47 |     NULL | NULL   | YES  | BTREE      |         |               |
+----------+------------+---------------+--------------+-------------+-----------+-------------+----------+--------+------+------------+---------+---------------+

In the above example, the customer table has two indexes, a primary index on c_custkey and a secondary index on c_nationkey. The most important thing to note from this output, is the estimated number of different key values, cardinality . For the two indexed columns of the customer table, the cardinality is 150,000 and 47, respectively.

The InnoDB statistics are calculated on-the-fly the first time a table is used after the server has been started. The statistics may be automatically recalculated at various times, and ANALYZE TABLE can be used to force a recalculation. For a description of how InnoDB calculates its statistics, see the MySQL 5.5 Reference Manual. The important thing to note is that there is a system variable, innodb_stats_sample_pages, that controls the accuracy of the statistics. It determines the number of index pages that are sampled in order to calculate the statistics. The default value is 8.

Continuing with the example above, I ran ANALYZE on the customer table, and here is what I got:

mysql> analyze table customer;
+---------------+---------+----------+----------+
| Table         | Op      | Msg_type | Msg_text |
+---------------+---------+----------+----------+
| dbt3.customer | analyze | status   | OK       |
+---------------+---------+----------+----------+
1 row in set (0.03 sec)

mysql> show index from customer;
+----------+------------+---------------+--------------+-------------+-----------+-------------+----------+--------+------+------------+---------+---------------+
| Table    | Non_unique | Key_name      | Seq_in_index | Column_name | Collation | Cardinality | Sub_part | Packed | Null | Index_type | Comment | Index_comment |
+----------+------------+---------------+--------------+-------------+-----------+-------------+----------+--------+------+------------+---------+---------------+
| customer |          0 | PRIMARY       |            1 | c_custkey   | A         |      150000 |     NULL | NULL   |      | BTREE      |         |               |
| customer |          1 | i_c_nationkey |            1 | c_nationkey | A         |         134 |     NULL | NULL   | YES  | BTREE      |         |               |
+----------+------------+---------------+--------------+-------------+-----------+-------------+----------+--------+------+------------+---------+---------------+
2 rows in set (0.01 sec)

As the observant reader has already noticed, the estimated cardinality of the column c_nationkey has changed significantly. Running ANALYZE several times, I saw numbers as low as 5 and as high as 135 for this column.

The question is then whether we can get better and more stable statistics by increasing the setting of innodb_stats_sample_pages. I increased the value to 100, and ran ANALYZE 100 times. This time, the estimated cardinality was between 22 and 84, and 80% of the time it was between 30 and 60.

So how did this affect the execution plan for query 8? Running the query another 100 times with this new setting of innodb_stats_sample_pages, gave only 3 different execution plans, all with the same join ordering. The remaining difference was in which index was used to access one of the tables. I will discuss how to further reduce the number of plans in a future blog post.

Note that increasing innodb_stats_sample_pages will cause the calculation of statistics to take longer time. In my case, sampling 100 pages did not seem to take a noticeable amount of time, and this should normally not cause any problems when ANALYZE TABLE is run explicitly. However, if InnoDB decides to do an automatic recalculation, the increased time may have some unwanted impact. Hence, this variable should be used with care, and its value should not be set higher than necessary to get reasonably accurate estimates.

Optimizing MySQL filesort with small limit.

didrik — Tue, 12 Apr 2011 01:44:00 +0000

"filesort" is the MySQL catchall algorithm for producing ordered results. (For an explanation on how it works, see Sergey Petrunias blog http://s.petrunia.net/blog/?p=24).

For small data sets, "filesort" simply uses a quicksort in memory. However, for large data sets we create temporary (sorted) files, which are later merged.

In the recent MySQL release candidate http://dev.mysql.com/tech-resources/articles/whats-new-in-mysql-5.6.html this has been optimized for the following kinds of queries (and subqueries)

SELECT ... FROM single_table ... ORDER BY non_index_column [DESC] LIMIT N [OFFSET M];

If we have space in memory for (N + M) rows, we create a (bounded) Priority Queue to hold the data. This means we can produce the ordered result using a single table scan, thus saving the writing/reading of temporary files, and saving the merge step.

How can you see it in action? Sorry, there's no explain for it (yet). What you can do currently is to inspect the status counters which are associated with filesort, and verify they are all zero.

FLUSH STATUS;
SHOW SESSION STATUS LIKE 'Sort%';
<run your select ... limit query>
SHOW SESSION STATUS LIKE 'Sort%';
What kind of speedup can you expect? This depends on your data set, and your sort_buffer_size of course. With this table, and about 20 million rows, and default sort buffer, execution time drops from about 40 seconds to 10 seconds on my desktop machine:

CREATE TABLE t1(
f0 int auto_increment PRIMARY KEY,
f1 int,
f2 varchar(200)
);

SELECT * FROM t1 ORDER BY f2 LIMIT 100;

MySQL 5.6: Index Condition Pushdown

Olav Sandstå — Mon, 11 Apr 2011 16:08:00 +0000

Index Condition Pushdown (ICP) is one of the new optimizer features in the MySQL 5.6.2 milestone release. The goal with Index Condition Pushdown is to move as much as possible of the processing of conditions (mainly WHERE clauses) from the server to the storage engine. Instead of fetching entire rows into the server and then evaluate the conditions in the server, the optimizer "pushes" the parts of condition that can be evaluated using the index down to the storage engine. This gives the storage engine the possibility to filter out non-relevant rows using the index and only return relevant rows to the server. The result of using ICP should be less IO accesses to the base table and fewer accesses from the MySQL server to the storage engine.

To explain how Index Condition Pushdown works let us first look at how retrieval of records based on using an index is done without use of Index Condition Pushdown. The main operations that the storage engine and server perform look approximately like this:

The storage engine reads the next row by first reading the index tuple and then using the index tuple to locate and read the full row from the base table.
The server will then evaluate the WHERE condition on the row and based on this either use or ignore this row.

When Index Condition Pushdown is used, the server will push down the parts of the WHERE condition that can be evaluated using the index to the storage engine. The reading of records from a table will then consist of the following steps:

The storage engine reads the next index tuple from the index.
The storage engine evaluates the pushed index condition using the index tuple. If this condition is not satisfied then the storage engine will proceed to the next entry in the index (go back to step 1). Only when it has found an index entry that satisfies the pushed index condition it will continue to read data from the base table.
The storage engine uses the index entry to locate and read the full row from the table.
The server will evaluate the part of the WHERE condition that has not been pushed down the storage engine and based on this either use or ignore this row.

The savings during execution of the query comes from that the storage engine will be able to filter out and drop reading of full rows from the table every time the pushed index condition evaluates to false by just using data from the index.

The optimizer can use Index Condition Pushdown for queries that need to access full table rows using the range, ref, eq_ref, and ref_or_null access methods. In MySQL 5.6.2 Index Condition Pushdown is implemented for InnoDB and MyISAM.

How to enable Index Condition Pushdown?

There is no need to do anything extra in order to use Index Condition Pushdown in MySQL 5.6.2 since it is enabled by default. If you for some reason should want to disable ICP, for instance to be able to compare the execution time with and without ICP, you can use the optimizer_switch system variable to control the use of it. For example to disable ICP you can set:
optimizer_switch='index_condition_pushdown=off';
This setting can be changed at run-time.

How to know if Index Condition Pushdown is used?

When Index Condition is used, the Extra column in the EXPLAIN of the query will show "Using index condition".

Example using Index Condition Pushdown

To illustrate the effect of using Index Condition Pushdown a small example is needed. Assume you have the following table with information about the five million people living in Norway:

   CREATE TABLE person (
      personid INTEGER PRIMARY KEY,
      firstname CHAR(20),
      lastname CHAR(20),
postalcode INTEGER,
      age INTEGER,
address CHAR(50),
KEY k1 (postalcode,age)
   ) ENGINE=InnoDB;

and you want to find all persons who live close to the city of Bergen (with postal code in the range between 5000 and 5500) and are either 21 or 22 years old. This can be done using the following query:

   SELECT lastname, firstname
   FROM person
   WHERE postalcode BETWEEN 5000 AND 5500 AND age BETWEEN 21 AND 22;

The MySQL optimizer will execute this as a range query using the k1 index. The range query will request the storage engine to read all records where "postalcode BETWEEN 5000 AND 5500".

If this query was run against MySQL 5.5 (which does not have ICP) or if ICP has been disabled then the storage engine will need to fetch all rows that has postal code between 5000 and 5500. With randomly distributed data in the table this would correspond to 250.000 rows that the storage engine has to read and return to the server for evaluation. The server would then evaluate the complete WHERE clause and filter out the records that does not satisfy the "age BETWEEN 21 AND 22". This would result in 5.000 records that would be returned to the user.

With ICP enabled the optimizer will evaluate the WHERE clause and find the parts of it that can be evaluated by using fields from the index. In this case the index contains both the postalcode and the age. Thus, the optimizer will push the entire WHERE clause down to the storage engine. The storage engine can now evaluate the pushed index condition by using the index. So before reading a full row from the base table, the storage engine evaluates the pushed index condition using the index entry. Only those rows that actually qualifies need to be read from the base table. So in this example, the storage engine will evaluate 250.000 index entries but only need to read 5.000 rows from the base table and return those to the server (compared to the 250.000 rows in the case where ICP was not used).

Performance

To get some performance numbers I filled the above table with five million entries with random data (uniformly distributed). The resulting size of the database was about 1 GB on disk. First I disabled the use of ICP and measured the time it took to run the query. The default size of the InnoDB buffer pool is too small to fit this table in memory. So with this setting it took about 15 seconds for this query to complete due to a lot of disk accesses. When I increased the size of the InnoDB buffer pool to 1.5 GB the query takes about 1.4 seconds to complete.

With Index Condition Pushdown enabled it only takes about 90 ms to run the same query both with the default size of the InnoDB buffer pool and the 1.5 GB buffer pool.

In this example the speedup is 15 times when using Index Condition Pushdown (or 160 times in the case of default InnoDB buffer pool size). This speedup is mainly caused by having to read a much lower number of records from the base table (reduced number of IO operations) and a much lower number of calls from the server to InnoDB.

Problems with subquery transformations

Martin — Wed, 30 Jun 2010 01:01:00 +0000

MySQL transforms IN predicates into nearly-equivalent EXISTS predicates, and uses a set of mechanisms to catch all special cases. This transformation, outlined below, also applies to NOT IN predicates since a NOT IN b parses to NOT a IN b. Expressions such as

SELECT * FROM table1 WHERE column1 IN (SELECT column2 FROM table2)

get transformed into

SELECT * FROM table1 WHERE EXISTS

( SELECT column2 FROM table2

WHERE column1 = column2 OR column2 IS NULL )

since the latter can be executed more efficiently. For instance an index can be used for accessing only the rows of table2 that will actually participate in the final result. The added WHERE condition is called a guarded condition, or trigger condition, both terms are used. In order to get correct result, the condition column1 = column2 must be deactivated if we are comparing against a NULL value for column1. This guarantees correct results for most cases but there are some additional cases to consider.

If the IN predicate is used directly in the WHERE clause (e.g. not as a sub-expression of IS UNKNOWN,) a NULL value is treated as false. There is a special property top_level_item of an expression node that tells the execution to filter out NULL values from the subquery. But there are problems with it.

It does not propagate through NOT nodes (or any other nodes for that matter.)
It is only applied to the WHERE and HAVING clauses. Since MySQL allows quantified predicates in the SELECT list - this is not in the SQL standard - an extra hack is needed to make it work. The solution is to add - when top_level_item is false - another guarded condition as HAVING clause. Remember that MySQL allows HAVING without GROUP BY - yet again extending the standard. Hence we end up with

SELECT * FROM table1 WHERE EXISTS

( SELECT column2

FROM table2

WHERE column1 = column2 OR column2 IS NULL

HAVING NOT column2 IS NULL )

This will filter out NULL values causing the result of the subquery to be empty.

1 and 2 together caused Bug#51070. For row valued predicands, e.g.

SELECT * FROM t WHERE (a, b) NOT IN (SELECT c, d FROM u)

there may be partial matches for any two rows. A partial match occurs when the corresponding positions in two rows are either equal, or at least one is NULL. The design above handles these cases just fine as long as NULL values come from the outer table. When there is a NULL value in the row from the inner table, however, it gets filtered out by the HAVING clause. Hence the subquery, now rewritten into

SELECT c, d FROM u WHERE c = a OR b = d

HAVING NOT c IS NULL AND NOT d IS NULL

yields an empty result and the value of IN is false, causing NOT IN to yield true.