To measure the speed of a specific MySQL expression or function, invoke the BENCHMARK() function using the mysql client program. Its syntax is BENCHMARK(loop_count,expression). The return value is always zero, but mysql prints a line displaying approximately how long the statement took to execute. For example:

mysql> SELECT BENCHMARK(1000000,1+1);+------------------------+| BENCHMARK(1000000,1+1) |+------------------------+|  0 |+------------------------+1 row in set (0.32 sec)

This result was obtained on a Pentium II 400MHz system. It shows that MySQL can execute 1,000,000 simple addition expressions in 0.32 seconds on that system.

The built-in MySQL functions are typically highly optimized, but there may be some exceptions. BENCHMARK() is an excellent tool for finding out if some function is a problem for your queries.

This benchmark suite is meant to tell any user what operations a given SQL implementation performs well or poorly. You can get a good idea for how the benchmarks work by looking at the code and results in the sql-bench directory in any MySQL source distribution.

Note that this benchmark is single-threaded, so it measures the minimum time for the operations performed. We plan to add multi-threaded tests to the benchmark suite in the future.

To use the benchmark suite, the following requirements must be satisfied:

After you obtain a MySQL source distribution, you can find the benchmark suite located in its sql-bench directory. To run the benchmark tests, build MySQL, and then change location into the sql-bench directory and execute the run-all-tests script:

shell> cd sql-benchshell> perl run-all-tests --server=server_name

server_name should be the name of one of the supported servers. To get a list of all options and supported servers, invoke this command:

shell> perl run-all-tests --help

The crash-me script also is located in the sql-bench directory. crash-me tries to determine what features a database system supports and what its capabilities and limitations are by actually running queries. For example, it determines:

For more information about benchmark results, visit http://www.mysql.com/why-mysql/benchmarks/.

Benchmark your application and database to find out where the bottlenecks are. After fixing one bottleneck (or by replacing it with a "dummy" module), you can proceed to identify the next bottleneck. Even if the overall performance for your application currently is acceptable, you should at least make a plan for each bottleneck and decide how to solve it if someday you really need the extra performance.

For examples of portable benchmark programs, look at those in the MySQL benchmark suite. See Section 8.12.2, "The MySQL Benchmark Suite". You can take any program from this suite and modify it for your own needs. By doing this, you can try different solutions to your problem and test which really is fastest for you.

Another free benchmark suite is the Open Source Database Benchmark, available at http://osdb.sourceforge.net/.

It is very common for a problem to occur only when the system is very heavily loaded, even if other aspects of the system were tested extensively. These performance problems are typically due to issues of basic database design (for example, table scans are not good under high load) or problems with the operating system or libraries. These problems are much easier to fix if isolated during pre-production testing.

To avoid problems like this, benchmark your whole application under the worst possible load:

These programs or packages can bring a system to its knees, so be sure to use them only on your development systems.

You can query the tables in the performance_schema database to see real-time information about the performance characteristics of your server and the applications it is running. See Chapter 21, MySQL Performance Schema for details.

As you monitor the performance of your MySQL server, examine the process list, which is the set of threads currently executing within the server. Process list information is available from these sources:

You can always view information about your own threads. To view information about threads being executed for other accounts, you must have the PROCESS privilege.

Each process list entry contains several pieces of information:

The following sections list the possible Command values, and State values grouped by category. The meaning for some of these values is self-evident. For others, additional description is provided.

The range access method uses a single index to retrieve a subset of table rows that are contained within one or several index value intervals. It can be used for a single-part or multiple-part index. The following sections give a detailed description of how intervals are extracted from the WHERE clause.

SELECT * FROM t1  WHERE key_col > 1  AND key_col < 10;SELECT * FROM t1  WHERE key_col = 1  OR key_col IN (15,18,20);SELECT * FROM t1  WHERE key_col LIKE 'ab%'  OR key_col BETWEEN 'bar' AND 'foo';

SELECT * FROM t1 WHERE  (key1 < 'abc' AND (key1 LIKE 'abcde%' OR key1 LIKE '%b')) OR  (key1 < 'bar' AND nonkey = 4) OR  (key1 < 'uux' AND key1 > 'z');

key_part1  key_part2  key_part3  NULL   1  'abc'  NULL   1  'xyz'  NULL   2  'foo'   1 1  'abc'   1 1  'xyz'   1 2  'abc'   2 1  'aaa'

(1,-inf,-inf) <= (key_part1,key_part2,key_part3) < (1,+inf,+inf)

The Index Merge method is used to retrieve rows with several range scans and to merge their results into one. The merge can produce unions, intersections, or unions-of-intersections of its underlying scans. This access method merges index scans from a single table; it does not merge scans across multiple tables.

In EXPLAIN output, the Index Merge method appears as index_merge in the type column. In this case, the key column contains a list of indexes used, and key_len contains a list of the longest key parts for those indexes.

Examples:

SELECT * FROM tbl_name WHERE key1 = 10 OR key2 = 20;SELECT * FROM tbl_name  WHERE (key1 = 10 OR key2 = 20) AND non_key=30;SELECT * FROM t1, t2  WHERE (t1.key1 IN (1,2) OR t1.key2 LIKE 'value%')  AND t2.key1=t1.some_col;SELECT * FROM t1, t2  WHERE t1.key1=1  AND (t2.key1=t1.some_col OR t2.key2=t1.some_col2);

The Index Merge method has several access algorithms (seen in the Extra field of EXPLAIN output):

The following sections describe these methods in greater detail.

The choice between different possible variants of the Index Merge access method and other access methods is based on cost estimates of various available options.

SELECT * FROM innodb_table WHERE primary_key < 10 AND key_col1=20;SELECT * FROM tbl_name  WHERE (key1_part1=1 AND key1_part2=2) AND key2=2;

SELECT COUNT(*) FROM t1 WHERE key1=1 AND key2=1;

SELECT * FROM t1 WHERE key1=1 OR key2=2 OR key3=3;SELECT * FROM innodb_table WHERE (key1=1 AND key2=2) OR  (key3='foo' AND key4='bar') AND key5=5;

SELECT * FROM tbl_name WHERE key_col1 < 10 OR key_col2 < 20;SELECT * FROM tbl_name  WHERE (key_col1 > 10 OR key_col2 = 20) AND nonkey_col=30;

This optimization improves the efficiency of direct comparisons between a nonindexed column and a constant. In such cases, the condition is "pushed down" to the storage engine for evaluation. This optimization can be used only by the NDBCLUSTER storage engine.

For MySQL Cluster, this optimization can eliminate the need to send nonmatching rows over the network between the cluster's data nodes and the MySQL Server that issued the query, and can speed up queries where it is used by a factor of 5 to 10 times over cases where condition pushdown could be but is not used.

Suppose that a MySQL Cluster table is defined as follows:

CREATE TABLE t1 ( a INT, b INT, KEY(a)) ENGINE=NDBCLUSTER;

Condition pushdown can be used with queries such as the one shown here, which includes a comparison between a nonindexed column and a constant:

SELECT a, b FROM t1 WHERE b = 10;

The use of condition pushdown can be seen in the output of EXPLAIN:

mysql> EXPLAIN SELECT a,b FROM t1 WHERE b = 10\G*************************** 1. row ***************************   id: 1  select_type: SIMPLE table: t1 type: ALLpossible_keys: NULL  key: NULL  key_len: NULL  ref: NULL rows: 10 Extra: Using where with pushed condition

However, condition pushdown cannot be used with either of these two queries:

SELECT a,b FROM t1 WHERE a = 10;SELECT a,b FROM t1 WHERE b + 1 = 10;

Condition pushdown is not applicable to the first query because an index exists on column a. (An index access method would be more efficient and so would be chosen in preference to condition pushdown.) Condition pushdown cannot be employed for the second query because the comparison involving the nonindexed column b is indirect. (However, condition pushdown could be applied if you were to reduce b + 1 = 10 to b = 9 in the WHERE clause.)

Condition pushdown may also be employed when an indexed column is compared with a constant using a > or < operator:

mysql> EXPLAIN SELECT a, b FROM t1 WHERE a < 2\G*************************** 1. row ***************************   id: 1  select_type: SIMPLE table: t1 type: rangepossible_keys: a  key: a  key_len: 5  ref: NULL rows: 2 Extra: Using where with pushed condition

Other supported comparisons for condition pushdown include the following:

In all of the cases in the preceding list, it is possible for the condition to be converted into the form of one or more direct comparisons between a column and a constant.

Engine condition pushdown is enabled by default. To disable it at server startup, set the optimizer_switch system variable. For example, in a my.cnf file, use these lines:

[mysqld]optimizer_switch=engine_condition_pushdown=off

At runtime, disable condition pushdown like this:

SET optimizer_switch='engine_condition_pushdown=off';

Before MySQL 5.5.3, disable condition pushdown using the engine_condition_pushdown system variable. At server startup:

[mysqld]engine_condition_pushdown=0

At runtime, use either of these statements:

SET engine_condition_pushdown=OFF;

SET engine_condition_pushdown=0;

Limitations. Condition pushdown is subject to the following limitations:

MySQL can perform the same optimization on col_name IS NULL that it can use for col_name = constant_value. For example, MySQL can use indexes and ranges to search for NULL with IS NULL.

Examples:

SELECT * FROM tbl_name WHERE key_col IS NULL;SELECT * FROM tbl_name WHERE key_col <=> NULL;SELECT * FROM tbl_name  WHERE key_col=const1 OR key_col=const2 OR key_col IS NULL;

If a WHERE clause includes a col_name IS NULL condition for a column that is declared as NOT NULL, that expression is optimized away. This optimization does not occur in cases when the column might produce NULL anyway; for example, if it comes from a table on the right side of a LEFT JOIN.

MySQL can also optimize the combination col_name = expr OR col_name IS NULL, a form that is common in resolved subqueries. EXPLAIN shows ref_or_null when this optimization is used.

This optimization can handle one IS NULL for any key part.

Some examples of queries that are optimized, assuming that there is an index on columns a and b of table t2:

SELECT * FROM t1 WHERE t1.a=expr OR t1.a IS NULL;SELECT * FROM t1, t2 WHERE t1.a=t2.a OR t2.a IS NULL;SELECT * FROM t1, t2  WHERE (t1.a=t2.a OR t2.a IS NULL) AND t2.b=t1.b;SELECT * FROM t1, t2  WHERE t1.a=t2.a AND (t2.b=t1.b OR t2.b IS NULL);SELECT * FROM t1, t2  WHERE (t1.a=t2.a AND t2.a IS NULL AND ...)  OR (t1.a=t2.a AND t2.a IS NULL AND ...);

ref_or_null works by first doing a read on the reference key, and then a separate search for rows with a NULL key value.

Note that the optimization can handle only one IS NULL level. In the following query, MySQL uses key lookups only on the expression (t1.a=t2.a AND t2.a IS NULL) and is not able to use the key part on b:

SELECT * FROM t1, t2  WHERE (t1.a=t2.a AND t2.a IS NULL)  OR (t1.b=t2.b AND t2.b IS NULL);

MySQL implements an A LEFT JOIN B join_condition as follows:

The implementation of RIGHT JOIN is analogous to that of LEFT JOIN with the roles of the tables reversed.

The join optimizer calculates the order in which tables should be joined. The table read order forced by LEFT JOIN or STRAIGHT_JOIN helps the join optimizer do its work much more quickly, because there are fewer table permutations to check. Note that this means that if you do a query of the following type, MySQL does a full scan on b because the LEFT JOIN forces it to be read before d:

SELECT *  FROM a JOIN b LEFT JOIN c ON (c.key=a.key)  LEFT JOIN d ON (d.key=a.key)  WHERE b.key=d.key;

The fix in this case is reverse the order in which a and b are listed in the FROM clause:

SELECT *  FROM b JOIN a LEFT JOIN c ON (c.key=a.key)  LEFT JOIN d ON (d.key=a.key)  WHERE b.key=d.key;

For a LEFT JOIN, if the WHERE condition is always false for the generated NULL row, the LEFT JOIN is changed to a normal join. For example, the WHERE clause would be false in the following query if t2.column1 were NULL:

SELECT * FROM t1 LEFT JOIN t2 ON (column1) WHERE t2.column2=5;

Therefore, it is safe to convert the query to a normal join:

SELECT * FROM t1, t2 WHERE t2.column2=5 AND t1.column1=t2.column1;

This can be made faster because MySQL can use table t2 before table t1 if doing so would result in a better query plan. To provide a hint about the table join order, use STRAIGHT_JOIN. (See Section 13.2.9, "SELECT Syntax".)

MySQL executes joins between tables using a nested-loop algorithm or variations on it.

Nested-Loop Join Algorithm

A simple nested-loop join (NLJ) algorithm reads rows from the first table in a loop one at a time, passing each row to a nested loop that processes the next table in the join. This process is repeated as many times as there remain tables to be joined.

Assume that a join between three tables t1, t2, and t3 is to be executed using the following join types:

Table   Join Typet1  ranget2  reft3  ALL

If a simple NLJ algorithm is used, the join is processed like this:

for each row in t1 matching range {  for each row in t2 matching reference key { for each row in t3 {  if row satisfies join conditions,  send to client }  }}

Because the NLJ algorithm passes rows one at a time from outer loops to inner loops, it typically reads tables processed in the inner loops many times.

Block Nested-Loop Join Algorithm

A Block Nested-Loop (BNL) join algorithm uses buffering of rows read in outer loops to reduce the number of times that tables in inner loops must be read. For example, if 10 rows are read into a buffer and the buffer is passed to the next inner loop, each row read in the inner loop can be compared against all 10 rows in the buffer. The reduces the number of times the inner table must be read by an order of magnitude.

MySQL uses join buffering under these conditions:

For the example join described previously for the NLJ algorithm (without buffering), the join is done as follow using join buffering:

for each row in t1 matching range {  for each row in t2 matching reference key { store used columns from t1, t2 in join buffer if buffer is full {  for each row in t3 { for each t1, t2 combination in join buffer {  if row satisfies join conditions,  send to client }  }  empty buffer }  }}if buffer is not empty {  for each row in t3 { for each t1, t2 combination in join buffer {  if row satisfies join conditions,  send to client }  }}

If S is the size of each stored t1, t2 combination is the join buffer and C is the number of combinations in the buffer, the number of times table t3 is scanned is:

(S * C)/join_buffer_size + 1

The number of t3 scans decreases as the value of join_buffer_size increases, up to the point when join_buffer_size is large enough to hold all previous row combinations. At that point, there is no speed to be gained by making it larger.

The syntax for expressing joins permits nested joins. The following discussion refers to the join syntax described in Section 13.2.9.2, "JOIN Syntax".

The syntax of table_factor is extended in comparison with the SQL Standard. The latter accepts only table_reference, not a list of them inside a pair of parentheses. This is a conservative extension if we consider each comma in a list of table_reference items as equivalent to an inner join. For example:

SELECT * FROM t1 LEFT JOIN (t2, t3, t4) ON (t2.a=t1.a AND t3.b=t1.b AND t4.c=t1.c)

is equivalent to:

SELECT * FROM t1 LEFT JOIN (t2 CROSS JOIN t3 CROSS JOIN t4) ON (t2.a=t1.a AND t3.b=t1.b AND t4.c=t1.c)

In MySQL, CROSS JOIN is a syntactic equivalent to INNER JOIN (they can replace each other). In standard SQL, they are not equivalent. INNER JOIN is used with an ON clause; CROSS JOIN is used otherwise.

In general, parentheses can be ignored in join expressions containing only inner join operations. After removing parentheses and grouping operations to the left, the join expression:

t1 LEFT JOIN (t2 LEFT JOIN t3 ON t2.b=t3.b OR t2.b IS NULL)   ON t1.a=t2.a

transforms into the expression:

(t1 LEFT JOIN t2 ON t1.a=t2.a) LEFT JOIN t3 ON t2.b=t3.b OR t2.b IS NULL

Yet, the two expressions are not equivalent. To see this, suppose that the tables t1, t2, and t3 have the following state:

In this case, the first expression returns a result set including the rows (1,1,101,101), (2,NULL,NULL,NULL), whereas the second expression returns the rows (1,1,101,101), (2,NULL,NULL,101):

mysql> SELECT * -> FROM t1 ->  LEFT JOIN ->  (t2 LEFT JOIN t3 ON t2.b=t3.b OR t2.b IS NULL) ->  ON t1.a=t2.a;+------+------+------+------+| a | a | b | b |+------+------+------+------+| 1 | 1 |  101 |  101 || 2 | NULL | NULL | NULL |+------+------+------+------+mysql> SELECT * -> FROM (t1 LEFT JOIN t2 ON t1.a=t2.a) ->  LEFT JOIN t3 ->  ON t2.b=t3.b OR t2.b IS NULL;+------+------+------+------+| a | a | b | b |+------+------+------+------+| 1 | 1 |  101 |  101 || 2 | NULL | NULL |  101 |+------+------+------+------+

In the following example, an outer join operation is used together with an inner join operation:

t1 LEFT JOIN (t2, t3) ON t1.a=t2.a

That expression cannot be transformed into the following expression:

t1 LEFT JOIN t2 ON t1.a=t2.a, t3.

For the given table states, the two expressions return different sets of rows:

mysql> SELECT * -> FROM t1 LEFT JOIN (t2, t3) ON t1.a=t2.a;+------+------+------+------+| a | a | b | b |+------+------+------+------+| 1 | 1 |  101 |  101 || 2 | NULL | NULL | NULL |+------+------+------+------+mysql> SELECT * -> FROM t1 LEFT JOIN t2 ON t1.a=t2.a, t3;+------+------+------+------+| a | a | b | b |+------+------+------+------+| 1 | 1 |  101 |  101 || 2 | NULL | NULL |  101 |+------+------+------+------+

Therefore, if we omit parentheses in a join expression with outer join operators, we might change the result set for the original expression.

More exactly, we cannot ignore parentheses in the right operand of the left outer join operation and in the left operand of a right join operation. In other words, we cannot ignore parentheses for the inner table expressions of outer join operations. Parentheses for the other operand (operand for the outer table) can be ignored.

The following expression:

(t1,t2) LEFT JOIN t3 ON P(t2.b,t3.b)

is equivalent to this expression:

t1, t2 LEFT JOIN t3 ON P(t2.b,t3.b)

for any tables t1,t2,t3 and any condition P over attributes t2.b and t3.b.

Whenever the order of execution of the join operations in a join expression (join_table) is not from left to right, we talk about nested joins. Consider the following queries:

SELECT * FROM t1 LEFT JOIN (t2 LEFT JOIN t3 ON t2.b=t3.b) ON t1.a=t2.a  WHERE t1.a > 1SELECT * FROM t1 LEFT JOIN (t2, t3) ON t1.a=t2.a  WHERE (t2.b=t3.b OR t2.b IS NULL) AND t1.a > 1

Those queries are considered to contain these nested joins:

t2 LEFT JOIN t3 ON t2.b=t3.bt2, t3

The nested join is formed in the first query with a left join operation, whereas in the second query it is formed with an inner join operation.

In the first query, the parentheses can be omitted: The grammatical structure of the join expression will dictate the same order of execution for join operations. For the second query, the parentheses cannot be omitted, although the join expression here can be interpreted unambiguously without them. (In our extended syntax the parentheses in (t2, t3) of the second query are required, although theoretically the query could be parsed without them: We still would have unambiguous syntactical structure for the query because LEFT JOIN and ON would play the role of the left and right delimiters for the expression (t2,t3).)

The preceding examples demonstrate these points:

Queries with nested outer joins are executed in the same pipeline manner as queries with inner joins. More exactly, a variation of the nested-loop join algorithm is exploited. Recall by what algorithmic schema the nested-loop join executes a query. Suppose that we have a join query over 3 tables T1,T2,T3 of the form:

SELECT * FROM T1 INNER JOIN T2 ON P1(T1,T2) INNER JOIN T3 ON P2(T2,T3)  WHERE P(T1,T2,T3).

Here, P1(T1,T2) and P2(T3,T3) are some join conditions (on expressions), whereas P(t1,t2,t3) is a condition over columns of tables T1,T2,T3.

The nested-loop join algorithm would execute this query in the following manner:

FOR each row t1 in T1 {  FOR each row t2 in T2 such that P1(t1,t2) { FOR each row t3 in T3 such that P2(t2,t3) {  IF P(t1,t2,t3) { t:=t1||t2||t3; OUTPUT t;  } }  }}

The notation t1||t2||t3 means "a row constructed by concatenating the columns of rows t1, t2, and t3." In some of the following examples, NULL where a row name appears means that NULL is used for each column of that row. For example, t1||t2||NULL means "a row constructed by concatenating the columns of rows t1 and t2, and NULL for each column of t3."

Now let's consider a query with nested outer joins:

SELECT * FROM T1 LEFT JOIN  (T2 LEFT JOIN T3 ON P2(T2,T3))  ON P1(T1,T2)  WHERE P(T1,T2,T3).

For this query, we modify the nested-loop pattern to get:

FOR each row t1 in T1 {  BOOL f1:=FALSE;  FOR each row t2 in T2 such that P1(t1,t2) { BOOL f2:=FALSE; FOR each row t3 in T3 such that P2(t2,t3) {  IF P(t1,t2,t3) { t:=t1||t2||t3; OUTPUT t;  }  f2=TRUE;  f1=TRUE; } IF (!f2) {  IF P(t1,t2,NULL) { t:=t1||t2||NULL; OUTPUT t;  }  f1=TRUE; }  }  IF (!f1) { IF P(t1,NULL,NULL) {  t:=t1||NULL||NULL; OUTPUT t; }  }}

In general, for any nested loop for the first inner table in an outer join operation, a flag is introduced that is turned off before the loop and is checked after the loop. The flag is turned on when for the current row from the outer table a match from the table representing the inner operand is found. If at the end of the loop cycle the flag is still off, no match has been found for the current row of the outer table. In this case, the row is complemented by NULL values for the columns of the inner tables. The result row is passed to the final check for the output or into the next nested loop, but only if the row satisfies the join condition of all embedded outer joins.

In our example, the outer join table expressed by the following expression is embedded:

(T2 LEFT JOIN T3 ON P2(T2,T3))

Note that for the query with inner joins, the optimizer could choose a different order of nested loops, such as this one:

FOR each row t3 in T3 {  FOR each row t2 in T2 such that P2(t2,t3) { FOR each row t1 in T1 such that P1(t1,t2) {  IF P(t1,t2,t3) { t:=t1||t2||t3; OUTPUT t;  } }  }}

For the queries with outer joins, the optimizer can choose only such an order where loops for outer tables precede loops for inner tables. Thus, for our query with outer joins, only one nesting order is possible. For the following query, the optimizer will evaluate two different nestings:

SELECT * T1 LEFT JOIN (T2,T3) ON P1(T1,T2) AND P2(T1,T3)  WHERE P(T1,T2,T3)

The nestings are these:

FOR each row t1 in T1 {  BOOL f1:=FALSE;  FOR each row t2 in T2 such that P1(t1,t2) { FOR each row t3 in T3 such that P2(t1,t3) {  IF P(t1,t2,t3) { t:=t1||t2||t3; OUTPUT t;  }  f1:=TRUE }  }  IF (!f1) { IF P(t1,NULL,NULL) {  t:=t1||NULL||NULL; OUTPUT t; }  }}

and:

FOR each row t1 in T1 {  BOOL f1:=FALSE;  FOR each row t3 in T3 such that P2(t1,t3) { FOR each row t2 in T2 such that P1(t1,t2) {  IF P(t1,t2,t3) { t:=t1||t2||t3; OUTPUT t;  }  f1:=TRUE }  }  IF (!f1) { IF P(t1,NULL,NULL) {  t:=t1||NULL||NULL; OUTPUT t; }  }}

In both nestings, T1 must be processed in the outer loop because it is used in an outer join. T2 and T3 are used in an inner join, so that join must be processed in the inner loop. However, because the join is an inner join, T2 and T3 can be processed in either order.

When discussing the nested-loop algorithm for inner joins, we omitted some details whose impact on the performance of query execution may be huge. We did not mention so-called "pushed-down" conditions. Suppose that our WHERE condition P(T1,T2,T3) can be represented by a conjunctive formula:

P(T1,T2,T2) = C1(T1) AND C2(T2) AND C3(T3).

In this case, MySQL actually uses the following nested-loop schema for the execution of the query with inner joins:

FOR each row t1 in T1 such that C1(t1) {  FOR each row t2 in T2 such that P1(t1,t2) AND C2(t2)  { FOR each row t3 in T3 such that P2(t2,t3) AND C3(t3) {  IF P(t1,t2,t3) { t:=t1||t2||t3; OUTPUT t;  } }  }}

You see that each of the conjuncts C1(T1), C2(T2), C3(T3) are pushed out of the most inner loop to the most outer loop where it can be evaluated. If C1(T1) is a very restrictive condition, this condition pushdown may greatly reduce the number of rows from table T1 passed to the inner loops. As a result, the execution time for the query may improve immensely.

For a query with outer joins, the WHERE condition is to be checked only after it has been found that the current row from the outer table has a match in the inner tables. Thus, the optimization of pushing conditions out of the inner nested loops cannot be applied directly to queries with outer joins. Here we have to introduce conditional pushed-down predicates guarded by the flags that are turned on when a match has been encountered.

For our example with outer joins with:

P(T1,T2,T3)=C1(T1) AND C(T2) AND C3(T3)

the nested-loop schema using guarded pushed-down conditions looks like this:

FOR each row t1 in T1 such that C1(t1) {  BOOL f1:=FALSE;  FOR each row t2 in T2  such that P1(t1,t2) AND (f1?C2(t2):TRUE) { BOOL f2:=FALSE; FOR each row t3 in T3 such that P2(t2,t3) AND (f1&&f2?C3(t3):TRUE) {  IF (f1&&f2?TRUE:(C2(t2) AND C3(t3))) { t:=t1||t2||t3; OUTPUT t;  }  f2=TRUE;  f1=TRUE; } IF (!f2) {  IF (f1?TRUE:C2(t2) && P(t1,t2,NULL)) { t:=t1||t2||NULL; OUTPUT t;  }  f1=TRUE; }  }  IF (!f1 && P(t1,NULL,NULL)) {  t:=t1||NULL||NULL; OUTPUT t;  }}

In general, pushed-down predicates can be extracted from join conditions such as P1(T1,T2) and P(T2,T3). In this case, a pushed-down predicate is guarded also by a flag that prevents checking the predicate for the NULL-complemented row generated by the corresponding outer join operation.

Note that access by key from one inner table to another in the same nested join is prohibited if it is induced by a predicate from the WHERE condition. (We could use conditional key access in this case, but this technique is not employed yet in MySQL 5.5.)

Table expressions in the FROM clause of a query are simplified in many cases.

At the parser stage, queries with right outer joins operations are converted to equivalent queries containing only left join operations. In the general case, the conversion is performed according to the following rule:

(T1, ...) RIGHT JOIN (T2,...) ON P(T1,...,T2,...) =(T2, ...) LEFT JOIN (T1,...) ON P(T1,...,T2,...)

All inner join expressions of the form T1 INNER JOIN T2 ON P(T1,T2) are replaced by the list T1,T2, P(T1,T2) being joined as a conjunct to the WHERE condition (or to the join condition of the embedding join, if there is any).

When the optimizer evaluates plans for join queries with outer join operation, it takes into consideration only the plans where, for each such operation, the outer tables are accessed before the inner tables. The optimizer options are limited because only such plans enables us to execute queries with outer joins operations by the nested loop schema.

Suppose that we have a query of the form:

SELECT * T1 LEFT JOIN T2 ON P1(T1,T2)  WHERE P(T1,T2) AND R(T2)

with R(T2) narrowing greatly the number of matching rows from table T2. If we executed the query as it is, the optimizer would have no other choice besides to access table T1 before table T2 that may lead to a very inefficient execution plan.

Fortunately, MySQL converts such a query into a query without an outer join operation if the WHERE condition is null-rejected. A condition is called null-rejected for an outer join operation if it evaluates to FALSE or to UNKNOWN for any NULL-complemented row built for the operation.

Thus, for this outer join:

T1 LEFT JOIN T2 ON T1.A=T2.A

Conditions such as these are null-rejected:

T2.B IS NOT NULL,T2.B > 3,T2.C <= T1.C,T2.B < 2 OR T2.C > 1

Conditions such as these are not null-rejected:

T2.B IS NULL,T1.B < 3 OR T2.B IS NOT NULL,T1.B < 3 OR T2.B > 3

The general rules for checking whether a condition is null-rejected for an outer join operation are simple. A condition is null-rejected in the following cases:

A condition can be null-rejected for one outer join operation in a query and not null-rejected for another. In the query:

SELECT * FROM T1 LEFT JOIN T2 ON T2.A=T1.A LEFT JOIN T3 ON T3.B=T1.B  WHERE T3.C > 0

the WHERE condition is null-rejected for the second outer join operation but is not null-rejected for the first one.

If the WHERE condition is null-rejected for an outer join operation in a query, the outer join operation is replaced by an inner join operation.

For example, the preceding query is replaced with the query:

SELECT * FROM T1 LEFT JOIN T2 ON T2.A=T1.A INNER JOIN T3 ON T3.B=T1.B  WHERE T3.C > 0

For the original query, the optimizer would evaluate plans compatible with only one access order T1,T2,T3. For the replacing query, it additionally considers the access sequence T3,T1,T2.

A conversion of one outer join operation may trigger a conversion of another. Thus, the query:

SELECT * FROM T1 LEFT JOIN T2 ON T2.A=T1.A LEFT JOIN T3 ON T3.B=T2.B  WHERE T3.C > 0

will be first converted to the query:

SELECT * FROM T1 LEFT JOIN T2 ON T2.A=T1.A INNER JOIN T3 ON T3.B=T2.B  WHERE T3.C > 0

which is equivalent to the query:

SELECT * FROM (T1 LEFT JOIN T2 ON T2.A=T1.A), T3  WHERE T3.C > 0 AND T3.B=T2.B

Now the remaining outer join operation can be replaced by an inner join, too, because the condition T3.B=T2.B is null-rejected and we get a query without outer joins at all:

SELECT * FROM (T1 INNER JOIN T2 ON T2.A=T1.A), T3  WHERE T3.C > 0 AND T3.B=T2.B

Sometimes we succeed in replacing an embedded outer join operation, but cannot convert the embedding outer join. The following query:

SELECT * FROM T1 LEFT JOIN  (T2 LEFT JOIN T3 ON T3.B=T2.B)  ON T2.A=T1.A  WHERE T3.C > 0

is converted to:

SELECT * FROM T1 LEFT JOIN  (T2 INNER JOIN T3 ON T3.B=T2.B)  ON T2.A=T1.A  WHERE T3.C > 0,

That can be rewritten only to the form still containing the embedding outer join operation:

SELECT * FROM T1 LEFT JOIN  (T2,T3)  ON (T2.A=T1.A AND T3.B=T2.B)  WHERE T3.C > 0.

When trying to convert an embedded outer join operation in a query, we must take into account the join condition for the embedding outer join together with the WHERE condition. In the query:

SELECT * FROM T1 LEFT JOIN  (T2 LEFT JOIN T3 ON T3.B=T2.B)  ON T2.A=T1.A AND T3.C=T1.C  WHERE T3.D > 0 OR T1.D > 0

the WHERE condition is not null-rejected for the embedded outer join, but the join condition of the embedding outer join T2.A=T1.A AND T3.C=T1.C is null-rejected. So the query can be converted to:

SELECT * FROM T1 LEFT JOIN  (T2, T3)  ON T2.A=T1.A AND T3.C=T1.C AND T3.B=T2.B  WHERE T3.D > 0 OR T1.D > 0

In some cases, MySQL can use an index to satisfy an ORDER BY clause without doing any extra sorting.

The index can also be used even if the ORDER BY does not match the index exactly, as long as all of the unused portions of the index and all the extra ORDER BY columns are constants in the WHERE clause. The following queries use the index to resolve the ORDER BY part:

SELECT * FROM t1  ORDER BY key_part1,key_part2,... ;SELECT * FROM t1  WHERE key_part1=constant  ORDER BY key_part2;SELECT * FROM t1  ORDER BY key_part1 DESC, key_part2 DESC;SELECT * FROM t1  WHERE key_part1=1  ORDER BY key_part1 DESC, key_part2 DESC;

In some cases, MySQL cannot use indexes to resolve the ORDER BY, although it still uses indexes to find the rows that match the WHERE clause. These cases include the following:

Availability of an index for sorting may be affected by the use of column aliases. Suppose that the column t1.a is indexed. In this statement, the name of the column in the select list is a. It refers to t1.a, so for the reference to a in the ORDER BY, the index can be used:

SELECT a FROM t1 ORDER BY a;

In this statement, the name of the column in the select list is also a, but it is the alias name. It refers to ABS(a), so for the reference to a in the ORDER BY, the index cannot be used:

SELECT ABS(a) AS a FROM t1 ORDER BY a;

In the following statement, the ORDER BY refers to a name that is not the name of a column in the select list. But there is a column in t1 named a, so the ORDER BY uses that, and the index can be used. (The resulting sort order may be completely different from the order for ABS(a), of course.)

SELECT ABS(a) AS b FROM t1 ORDER BY a;

By default, MySQL sorts all GROUP BY col1, col2, ... queries as if you specified ORDER BY col1, col2, ... in the query as well. If you include an ORDER BY clause explicitly that contains the same column list, MySQL optimizes it away without any speed penalty, although the sorting still occurs. If a query includes GROUP BY but you want to avoid the overhead of sorting the result, you can suppress sorting by specifying ORDER BY NULL. For example:

INSERT INTO fooSELECT a, COUNT(*) FROM bar GROUP BY a ORDER BY NULL;

With EXPLAIN SELECT ... ORDER BY, you can check whether MySQL can use indexes to resolve the query. It cannot if you see Using filesort in the Extra column. See Section 8.8.1, "Optimizing Queries with EXPLAIN". Filesort uses a fixed-length row-storage format similar to that used by the MEMORY storage engine. Variable-length types such as VARCHAR are stored using a fixed length.

MySQL has two filesort algorithms for sorting and retrieving results. The original method uses only the ORDER BY columns. The modified method uses not just the ORDER BY columns, but all the columns used in the query.

The optimizer selects which filesort algorithm to use. It normally uses the modified algorithm except when BLOB or TEXT columns are involved, in which case it uses the original algorithm.

The original filesort algorithm works as follows:

One problem with this approach is that it reads rows twice: One time when evaluating the WHERE clause, and again after sorting the pair values. And even if the rows were accessed successively the first time (for example, if a table scan is done), the second time they are accessed randomly. (The sort keys are ordered, but the row positions are not.)

The modified filesort algorithm incorporates an optimization such that it records not only the sort key value and row position, but also the columns required for the query. This avoids reading the rows twice. The modified filesort algorithm works like this:

Using the modified filesort algorithm, the tuples are longer than the pairs used in the original method, and fewer of them fit in the sort buffer (the size of which is given by sort_buffer_size). As a result, it is possible for the extra I/O to make the modified approach slower, not faster. To avoid a slowdown, the optimization is used only if the total size of the extra columns in the sort tuple does not exceed the value of the max_length_for_sort_data system variable. (A symptom of setting the value of this variable too high is a combination of high disk activity and low CPU activity.)

For slow queries for which filesort is not used, try lowering max_length_for_sort_data to a value that is appropriate to trigger a filesort.

If you want to increase ORDER BY speed, check whether you can get MySQL to use indexes rather than an extra sorting phase. If this is not possible, you can try the following strategies:

The most general way to satisfy a GROUP BY clause is to scan the whole table and create a new temporary table where all rows from each group are consecutive, and then use this temporary table to discover groups and apply aggregate functions (if any). In some cases, MySQL is able to do much better than that and to avoid creation of temporary tables by using index access.

The most important preconditions for using indexes for GROUP BY are that all GROUP BY columns reference attributes from the same index, and that the index stores its keys in order (for example, this is a BTREE index and not a HASH index). Whether use of temporary tables can be replaced by index access also depends on which parts of an index are used in a query, the conditions specified for these parts, and the selected aggregate functions.

There are two ways to execute a GROUP BY query through index access, as detailed in the following sections. In the first method, the grouping operation is applied together with all range predicates (if any). The second method first performs a range scan, and then groups the resulting tuples.

In MySQL, GROUP BY is used for sorting, so the server may also apply ORDER BY optimizations to grouping. See Section 8.13.9, "ORDER BY Optimization".

SELECT c1, c2 FROM t1 GROUP BY c1, c2;SELECT DISTINCT c1, c2 FROM t1;SELECT c1, MIN(c2) FROM t1 GROUP BY c1;SELECT c1, c2 FROM t1 WHERE c1 < const GROUP BY c1, c2;SELECT MAX(c3), MIN(c3), c1, c2 FROM t1 WHERE c2 > const GROUP BY c1, c2;SELECT c2 FROM t1 WHERE c1 < const GROUP BY c1, c2;SELECT c1, c2 FROM t1 WHERE c3 = const GROUP BY c1, c2;

SELECT COUNT(DISTINCT c1), SUM(DISTINCT c1) FROM t1;SELECT COUNT(DISTINCT c1, c2), COUNT(DISTINCT c2, c1) FROM t1;

SELECT DISTINCT COUNT(DISTINCT c1) FROM t1;SELECT COUNT(DISTINCT c1) FROM t1 GROUP BY c1;

DISTINCT combined with ORDER BY needs a temporary table in many cases.

Because DISTINCT may use GROUP BY, learn how MySQL works with columns in ORDER BY or HAVING clauses that are not part of the selected columns. See Section 12.16.3, "MySQL Extensions to GROUP BY".

In most cases, a DISTINCT clause can be considered as a special case of GROUP BY. For example, the following two queries are equivalent:

SELECT DISTINCT c1, c2, c3 FROM t1WHERE c1 > const;SELECT c1, c2, c3 FROM t1WHERE c1 > const GROUP BY c1, c2, c3;

Due to this equivalence, the optimizations applicable to GROUP BY queries can be also applied to queries with a DISTINCT clause. Thus, for more details on the optimization possibilities for DISTINCT queries, see Section 8.13.10, "GROUP BY Optimization".

When combining LIMIT row_count with DISTINCT, MySQL stops as soon as it finds row_count unique rows.

If you do not use columns from all tables named in a query, MySQL stops scanning any unused tables as soon as it finds the first match. In the following case, assuming that t1 is used before t2 (which you can check with EXPLAIN), MySQL stops reading from t2 (for any particular row in t1) when it finds the first row in t2:

SELECT DISTINCT t1.a FROM t1, t2 where t1.a=t2.a;

Certain optimizations are applicable to comparisons that use the IN operator to test subquery results (or that use =ANY, which is equivalent). This section discusses these optimizations, particularly with regard to the challenges that NULL values present. The last part of the discussion includes suggestions on what you can do to help the optimizer.

Consider the following subquery comparison:

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

MySQL evaluates queries "from outside to inside." That is, it first obtains the value of the outer expression outer_expr, and then runs the subquery and captures the rows that it produces.

A very useful optimization is to "inform" the subquery that the only rows of interest are those where the inner expression inner_expr is equal to outer_expr. This is done by pushing down an appropriate equality into the subquery's WHERE clause. That is, the comparison is converted to this:

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

After the conversion, MySQL can use the pushed-down equality to limit the number of rows that it must examine when evaluating the subquery.

More generally, a comparison of N values to a subquery that returns N-value rows is subject to the same conversion. If oe_i and ie_i represent corresponding outer and inner expression values, this subquery comparison:

(oe_1, ..., oe_N) IN  (SELECT ie_1, ..., ie_N FROM ... WHERE subquery_where)

Becomes:

EXISTS (SELECT 1 FROM ... WHERE subquery_where  AND oe_1 = ie_1  AND ...  AND oe_N = ie_N)

The following discussion assumes a single pair of outer and inner expression values for simplicity.

The conversion just described has its limitations. It is valid only if we ignore possible NULL values. That is, the "pushdown" strategy works as long as both of these two conditions are true:

When either or both of those conditions do not hold, optimization is more complex.

Suppose that outer_expr is known to be a non-NULL value but the subquery does not produce a row such that outer_expr = inner_expr. Then outer_expr IN (SELECT ...) evaluates as follows:

In this situation, the approach of looking for rows with outer_expr = inner_expr is no longer valid. It is necessary to look for such rows, but if none are found, also look for rows where inner_expr is NULL. Roughly speaking, the subquery can be converted to:

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

The need to evaluate the extra IS NULL condition is why MySQL has the ref_or_null access method:

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

The unique_subquery and index_subquery subquery-specific access methods also have "or NULL" variants. However, they are not visible in EXPLAIN output, so you must use EXPLAIN EXTENDED followed by SHOW WARNINGS (note the checking NULL in the warning message):

mysql> EXPLAIN EXTENDED -> SELECT outer_expr IN (SELECT maybe_null_key FROM t2) FROM t1\G*************************** 1. row ***************************   id: 1  select_type: PRIMARY table: t1...*************************** 2. row ***************************   id: 2  select_type: DEPENDENT SUBQUERY table: t2 type: index_subquerypossible_keys: maybe_null_key  key: maybe_null_key  key_len: 5  ref: func rows: 2 Extra: Using indexmysql> SHOW WARNINGS\G*************************** 1. row ***************************  Level: Note   Code: 1003Message: select (`test`.`t1`.`outer_expr`, (((`test`.`t1`.`outer_expr`) in t2 on maybe_null_key checking NULL))) AS `outer_expr IN (SELECT maybe_null_key FROM t2)` from `test`.`t1`

The additional OR ... IS NULL condition makes query execution slightly more complicated (and some optimizations within the subquery become inapplicable), but generally this is tolerable.

The situation is much worse when outer_expr can be NULL. According to the SQL interpretation of NULL as "unknown value," NULL IN (SELECT inner_expr ...) should evaluate to:

For proper evaluation, it is necessary to be able to check whether the SELECT has produced any rows at all, so outer_expr = inner_expr cannot be pushed down into the subquery. This is a problem, because many real world subqueries become very slow unless the equality can be pushed down.

Essentially, there must be different ways to execute the subquery depending on the value of outer_expr.

The optimizer chooses SQL compliance over speed, so it accounts for the possibility that outer_expr might be NULL.

If outer_expr is NULL, to evaluate the following expression, it is necessary to run the SELECT to determine whether it produces any rows:

NULL IN (SELECT inner_expr FROM ... WHERE subquery_where)

It is necessary to run the original SELECT here, without any pushed-down equalities of the kind mentioned earlier.

On the other hand, when outer_expr is not NULL, it is absolutely essential that this comparison:

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

be converted to this expression that uses a pushed-down condition:

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

Without this conversion, subqueries will be slow. To solve the dilemma of whether to push down or not push down conditions into the subquery, the conditions are wrapped in "trigger" functions. Thus, an expression of the following form:

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

is converted into:

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

More generally, if the subquery comparison is based on several pairs of outer and inner expressions, the conversion takes this comparison:

(oe_1, ..., oe_N) IN (SELECT ie_1, ..., ie_N FROM ... WHERE subquery_where)

and converts it to this expression:

EXISTS (SELECT 1 FROM ... WHERE subquery_where  AND trigcond(oe_1=ie_1)  AND ...  AND trigcond(oe_N=ie_N)   )

Each trigcond(X) is a special function that evaluates to the following values:

Note that trigger functions are not triggers of the kind that you create with CREATE TRIGGER.

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

When the optimizer uses a triggered condition to create some kind of index lookup-based access (as for the first two items of the preceding list), it must have a fallback strategy for the case when the condition is turned off. This fallback strategy is always the same: Do a full table scan. In EXPLAIN output, the fallback shows up as Full scan on NULL key in the Extra column:

mysql> EXPLAIN SELECT t1.col1, -> t1.col1 IN (SELECT t2.key1 FROM t2 WHERE t2.col2=t1.col2) FROM t1\G*************************** 1. row ***************************   id: 1  select_type: PRIMARY table: t1 ...*************************** 2. row ***************************   id: 2  select_type: DEPENDENT SUBQUERY table: t2 type: index_subquerypossible_keys: key1  key: key1  key_len: 5  ref: func rows: 2 Extra: Using where; Full scan on NULL key

If you run EXPLAIN EXTENDED followed by SHOW WARNINGS, you can see the triggered condition:

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

The use of triggered conditions has some performance implications. A NULL IN (SELECT ...) expression now may cause a full table scan (which is slow) when it previously did not. This is the price paid for correct results (the goal of the trigger-condition strategy was to improve compliance and not speed).

For multiple-table subqueries, execution of NULL IN (SELECT ...) will be particularly slow because the join optimizer does not optimize for the case where the outer expression is NULL. It assumes that subquery evaluations with NULL on the left side are very rare, even if there are statistics that indicate otherwise. On the other hand, if the outer expression might be NULL but never actually is, there is no performance penalty.

To help the query optimizer better execute your queries, use these tips: