A transformation takes place for expressions like this:

WHERE column1 = column2 AND column2 = 'x'

For such expressions, since it is known that, if A=B and B=C then A=C (the Transitivity Law), the transformed condition becomes:

WHERE column1='x' AND column2='x'

This transformation occurs for column1 <operator> column2 conditions if and only if <operator> is one of these operators:

=, <, >, <=, >=, <>, <=>, LIKE 

That is, transitive transformations don't apply for BETWEEN. Probably they should not apply for LIKE either, but that's a story for another day.

Constant propagation happens in a loop, so the output from one propagation step can be input for the next step.

See: /sql/sql_select.cc, change_cond_ref_to_const(). Or See: /sql/sql_select.cc, propagate_cond_constants().

A transformation takes place for conditions that are always true, for example:

WHERE 0=0 AND column1='y'

In this case, the first condition is removed, leaving

WHERE column1='y'

See: /sql/sql_select.cc, remove_eq_conds().

A transformation also takes place for conditions that are always false. For example, consider this WHERE clause:

WHERE (0 = 1 AND s1 = 5) OR s1 = 7

Since the parenthesized part is always false, it is removed, reducing this expression to

WHERE s1 = 7 

In some cases, where the WHERE clause represents an impossible condition, the optimizer might eliminate it completely. Consider the following:

WHERE (0 = 1 AND s1 = 5)

Because it is never possible for this condition to be true, the EXPLAIN statement will show the words Impossible WHERE. Informally, we at MySQL say that the WHERE has been optimized away.

If a column cannot be NULL, the optimizer removes any non-relevant IS NULL conditions. Thus,

WHERE not_null_column IS NULL 

is an always-false situation, and

WHERE not_null_column IS NOT NULL 

is an always-true situation so such columns are also eliminated from the conditional expression. This can be tricky. For example, in an OUTER JOIN, a column which is defined as NOT NULL might still contain a NULL. The optimizer leaves IS NULL conditions alone in such exceptional situations.

The optimizer will not detect all Impossible WHERE situations — there are too many possibilities in this regard. For example:

CREATE TABLE Table1 (column1 CHAR(1));
...
SELECT * FROM Table1 WHERE column1 = 'Canada';

The optimizer will not eliminate the condition in the query, even though the CREATE TABLE definition makes it an impossible condition.

A transformation takes place for this expression:

WHERE column1 = 1 + 2 

which becomes:

WHERE column1 = 3 

Before you say, “but I never would write 1 + 2 in the first place”, remember what was said earlier about constant propagation. It is quite easy for the optimizer to put such expressions together. This process simplifies the result.

A MySQL constant is something more than a mere literal in the query. It can also be the contents of a constant table, which is defined as follows:

For example, if the table definition for Table0 contains

... PRIMARY KEY (column1,column2) 

then this expression

FROM Table0 ... WHERE column1=5 AND column2=7 ... 

returns a constant table. More simply, if the table definition for Table1 contains

... unique_not_null_column INT NOT NULL UNIQUE 

then this expression

FROM Table1 ... WHERE unique_not_null_column=5 

returns a constant table.

These rules mean that a constant table has at most one row value. MySQL will evaluate a constant table in advance, to find out what that value is. Then MySQL will plug that value into the query. Here's an example:

SELECT Table1.unique_not_null_column, Table2.any_column
    FROM Table1, Table2
    WHERE Table1.unique_not_null_column = Table2.any_column
    AND Table1.unique_not_null_column = 5;

When evaluating this query, MySQL first finds that table Table1 after restriction with Table1.unique_not_null_column is a constant table according to the second definition above. So it retrieves that value.

If the retrieval fails (there is no row in the table with unique_not_null_column = EXPLAIN for the statement:

Impossible WHERE noticed after reading const tables 

Alternatively, if the retrieval succeeds (there is exactly one row in the table with unique_not_null_column = MySQL transforms the query to this:

SELECT 5, Table2.any_column
    FROM Table1, Table2
    WHERE 5 = Table2.any_column
    AND 5 = 5;

Actually this is a grand-combination example. The optimizer does some of the transformation because of constant propagation, which we described earlier. By the way, we described constant propagation first because it happens happens before MySQL figures out what the constant tables are. The sequence of optimizer steps sometimes makes a difference.

Although many queries have no constant-table references, it should be kept in mind that whenever the word constant is mentioned hereafter, it refers either to a literal or to the contents of a constant table.

See: /sql/sql_select.cc, make_join_statistics().

When evaluating a conditional expression, MySQL decides what join type the expression has. (Again: despite the word join, this applies for all conditional expressions, not just join expressions. A term like access type would be clearer.) These are the documented join types, in order from best to worst:

See: /sql/sql_select.h, enum join_type{}. Notice that there are a few other (undocumented) join types too, for subqueries.

The optimizer can use the join type to pick a driver expression. For example, consider this query:

SELECT *
FROM Table1
WHERE indexed_column = 5 AND unindexed_column = 6

Since indexed_column has a better join type, it is more likely to be the driver. You'll see various exceptions as this description proceeds, but this is a simple first rule.

What is significant about a driver? Consider that there are two execution paths for the query:

The Bad Execution Plan: Read every row in the table. (This is called a sequential scan of Table1 or simply table scan.) For each row, examine the values in indexed_column and in unindexed_column, to see if they meet the conditions.

The Good Execution Plan: Via the index, look up the rows which have indexed_column = This is called an indexed search.) For each row, examine the value in unindexed_column to see if it meets the condition.

An indexed search generally involves fewer accesses than a sequential scan, and far fewer accesses if the table is large but the index is unique. That is why it is better to access with the good execution plan, and why it is often good to choose indexed_column as the driver.

Bad join choices can cause more damage than bad choices in single-table searches, so MySQL developers have spent proportionally more time making sure that the tables in a query are joined in an optimal order and that optimal access methods (often called access paths) are chosen to retrieve table data. A combination of a fixed order in which tables are joined and the corresponding table access methods for each table is called query execution plan (QEP). The goal of the query optimizer is to find an optimal QEP among all such possible plans. There are several general ideas behind join optimization.

Each plan (or part of plan) is assigned a cost. The cost of a plan reflects roughly the resources needed to compute a query according to the plan, where the main factor is the number of rows that will be accessed while computing a query. Once we have a way to assign costs to different QEPs we have a way to compare them. Thus, the goal of the optimizer is to find a QEP with minimal cost among all possible plans.

In MySQL, the search for an optimal QEP is performed in a bottom-up manner. The optimizer first considers all plans for one table, then all plans for two tables, and so on, until it builds a complete optimal QEP. Query plans that consist of only some of the tables (and predicates) in a query are called partial plans. The optimizer relies on the fact that the more tables that are added to a partial plan, the greater its cost. This allows the optimizer to expand with more tables only the partial plans with lower cost than the current best complete plan.

The key routine that performs the search for an optimal QEP is sql/sql_select.cc, find_best(). It performs an exhaustive search of all possible plans and thus guarantees it will find an optimal one.

Below we represent find_best() in an extremely free translation to pseudocode. It is recursive, so some input variables are labeled so far to indicate that they come from a previous iteration.

remaining_tables = {t1, ..., tn}; /* all tables referenced in a query */

procedure find_best(
   partial_plan in,      /* in, partial plan of tables-joined-so-far */
   partial_plan_cost,    /* in, cost of partial_plan */
   remaining_tables,     /* in, set of tables not referenced in partial_plan */
   best_plan_so_far,     /* in/out, best plan found so far */
   best_plan_so_far_cost)/* in/out, cost of best_plan_so_far */
{
   for each table T from remaining_tables
   {
     /* Calculate the cost of using table T. Factors that the
        optimizer takes into account may include:
          Many rows in table (bad)
          Many key parts in common with tables so far (very good)
          Restriction mentioned in the WHERE clause (good)
          Long key (good)
          Unique or primary key (good)
          Full-text key (bad)
        Other factors that may at some time be worth considering:
          Many columns in key
          Short average/maximum key length
          Small table file
          Few levels in index
          All ORDER BY / GROUP columns come from this table */
     cost = complex-series-of-calculations;
     /* Add the cost to the cost so far. */
     partial_plan_cost+= cost;

     if (partial_plan_cost >= best_plan_so_far_cost)
       /* partial_plan_cost already too great, stop search */
       continue;

     partial_plan= expand partial_plan by best_access_method;
     remaining_tables= remaining_tables - table T;
     if (remaining_tables is not an empty set)
     {
       find_best(partial_plan, partial_plan_cost,
                 remaining_tables,
                 best_plan_so_far, best_plan_so_far_cost);
     }
     else
     {
       best_plan_so_far_cost= partial_plan_cost;
       best_plan_so_far= partial_plan;
     }
   }
}

Here the optimizer applies a depth-first search algorithm. It performs estimates for every table in the FROM clause. It will stop a search early if the estimate becomes worse than the best estimate so far. The order of scanning will depend on the order that the tables appear in the FROM clause.

See: /sql/table.h, struct st_table.

ANALYZE TABLE may affect some of the factors that the optimizer considers.

See also: /sql/sql_sqlect.cc, make_join_statistics().

The straightforward use of find_best() and greedy_search() will not apply for LEFT JOIN or RIGHT JOIN. For example, starting with MySQL 4.0.14, the optimizer may change a left join to a straight join and swap the table order in some cases. See also LEFT JOIN and RIGHT JOIN Optimization.

Some conditions can work with indexes, but over a (possibly wide) range of keys. These are known as range conditions, and are most often encountered with expressions involving these operators: >, >=, <, <=, IN, LIKE, BETWEEN

To the optimizer, this expression:

column1 IN (1,2,3) 

is the same as this one:

column1 = 1 OR column1 = 2 OR column1 = 3 

and MySQL treats them the same — there is no need to change IN to OR for a query, or vice versa.

The optimizer will use an index (range search) for

column1 LIKE 'x%'

but not for

column1 LIKE '%x'

That is, there is no range search if the first character in the pattern is a wildcard.

To the optimizer,

column1 BETWEEN 5 AND 7 

is the same as this expression

column1 >= 5 AND column1 <= 7 

and again, MySQL treats both expressions the same.

The optimizer may change a Range to an ALL join type if a condition would examine too many index keys. Such a change is particularly likely for < and > conditions and multiple-level secondary indexes. See: (for MyISAM indexes) /myisam/mi_range.c, mi_records_in_range().

Consider this query:

SELECT column1 FROM Table1; 

If column1 is indexed, then the optimizer may choose to retrieve the values from the index rather than from the table. An index which is used this way is called a covering index in most texts. MySQL simply uses the word “index” in EXPLAIN descriptions.

For this query:

SELECT column1, column2 FROM Table1; 

the optimizer will use join type = index only if the index has this definition:

CREATE INDEX ... ON Table1 (column1, column2); 

In other words, all columns in the select list must be in the index. (The order of the columns in the index does not matter.) Thus it might make sense to define a multiple-column index strictly for use as a covering index, regardless of search considerations.

An ANDed search has the form condition1 AND condition2, as in this example:

WHERE column1 = 'x' AND column2 = 'y'

Here, the optimizer's decision process can be described as follows:

The optimizer can also choose to perform an index_merge index intersection, as described in Section 8.2.2.5.2, “Index Merge Optimizer”.

Here's an example:

CREATE TABLE Table1 (s1 INT, s2 INT);
CREATE INDEX Index1 ON Table1 (s2);
CREATE INDEX Index2 ON Table1 (s1);
...
SELECT * FROM Table1 WHERE s1 = 5 AND s2 = 5;

When choosing a strategy to solve this query, the optimizer picks s2 = 5 as the driver because the index for s2 was created first. Regard this as an accidental effect rather than a rule, it could change at any moment.

An ORed search has the form "condition1" OR "condition2", as in this example:

WHERE column1 = 'x' OR column2 = 'y'

Here the optimizer's decision is to use a sequential scan.

There is also an option to use index merge under such circumstances. See Section 8.2.2.5.1, “Overview” and Index Merge Optimization, for more information.

The above warning does not apply if the same column is used in both conditions. For example:

WHERE column1 = 'x' OR column1 = 'y'

In such a case, the search is indexed because the expression is a range search. This subject will be revisited during the discussion of the IN predicate.

All SELECT statements within a UNION are optimized separately. Therefore, for this query:

SELECT * FROM Table1 WHERE column1 = 'x'
UNION ALL
SELECT * FROM TABLE1 WHERE column2 = 'y'

if both column1 and column2 are indexed, then each SELECT is done using an indexed search, and the result sets are merged. Notice that this query might produce the same results as the query used in the OR example, which uses a sequential scan.

It is a logical rule that

column1 <> 5 

is the same as

column1 < 5 OR column1 > 5 

However, MySQL does not transform in this circumstance. If you think that a range search would be better, then you should do your own transforming in such cases.

It is also a logical rule that

WHERE NOT (column1 != 5) 

is the same as

WHERE column1 = 5 

However, MySQL does not transform in this circumstance either.

We expect to add optimizations for both the previous cases.

This section discusses the NULLs filtering optimization used for ref and eq_ref joins.

..., tblX, ..., tblY, ... 

tblY.key_column = tblX.column 

... AND tblY.key_partN = tblX.column AND ... 

(tblY.key_partN = tblX.column) => (tblX.column IS NOT NULL) 

tblX.key_part1 = expr1 AND tblX.key_part2 = expr2 AND ... 

This section discussions optimizations relating to MySQL Partitioning. See Partitioning for general information about the partitioning implementation in MySQL 5.1 and later.

CREATE TABLE t (columns)
PARTITION BY p_type(p_func(col1, col2,... colN)...);

WHERE t.col1=const1 AND t.col2=const2 AND ... t.colN=constN

CREATE TABLE t (columns)
PARTITION BY
p_type(p_func(int_col))
...

WHERE const1 <= int_col <= const2

int_field=const1 OR int_field=const1 + 1 OR int_field=const1 + 2 OR ... OR int_field=const2 

 #define MAX_RANGE_TO_WALK=10 

const1                                                                            >= int_col >= const2

CREATE TABLE t (columns)
PARTITION BY RANGE|LIST(unary_ascending_function(column))

const1 <= t.col <= const2    

  => p_func(const1) <= 

p_func(t.column) <= p_func(const2)

A <= p_func(t.column) <= B 

                        p0     p1      p2    
  table partitions    ------x------x--------x-------->
 
  search interval     ----x==============x----------->
                          A              B

                      p0  p1   p2   p1   p1   p0    
table partitions    --+---+----+----+----+----+----> 

search interval     ----x===================x------> A B 

(keypart1, keypart2, ..., keypartN)

  
(part_col1, part_col2, ... part_colN,
subpart_col1, subpart_col2, ... subpart_colM)

  
CREATE TABLE t (..., pf INT, sp1 CHAR(5), sp2 INT, ... )
  PARTITION BY LIST (pf)
  SUBPARTITION BY HASH(sp1, sp2) (
    PARTITION p0 VALUES IN (1), 
    PARTITION p1 VALUES IN (2),
    PARTITION p2 VALUES IN (3),
    PARTITION p3 VALUES IN (4),
    PARTITION p4 VALUES IN (5),
  );

pf=1 AND (sp1='foo' AND sp2 IN (40,50))

OR 

(pf1=3 OR pf1=4) AND sp1='bar' AND sp2=33    

OR

((pf=3 OR pf=4) AND sp1=5)

OR

p=8 

(root)
   |               :   
   | Partitioning  :         Sub-partitioning 
   |               :    
   |               :          
   |               :            
   |   +------+    :     +-----------+   +--------+
   \---| pf=1 |----:-----| sp1='foo' |---| sp2=40 |
       +------+    :     +-----------+   +--------+
          |        :                         |
          |        :                     +--------+
          |        :                     | sp2=50 |
          |        :                     +--------+
          |        :    
          |        :              
       +------+    :     +-----------+   +--------+          
       | pf=3 |----:--+--| sp1='bar' |---| sp2=33 |
       +------+    :  |  +-----------+   +--------+          
          |        :  |            
       +------+    :  |            
       | pf=4 |----:--+
       +------+    :              
          |        : 
          |        :  
       +------+    :     +-----------+   
       | pf=8 |----:-----| sp1='baz' |
       +------+    :     +-----------+  

SELECT * FROM t1 WHERE partition_id=10 OR subpartition_id=20 

CREATE TABLE t1 (a INT, b INT);

INSERT INTO t1 VALUES (1,1),(2,2),(3,3);

CREATE TABLE t2 (
    keypart1 INT, 
    keypart2 INT, 
    KEY(keypart1, keypart2)
)
PARTITION BY HASH(keypart2);

INSERT INTO t2 VALUES (1,1),(2,2),(3,3);

SELECT * FROM t1, t2 
    WHERE  t2.keypart1=t1.a 
    AND    t2.keypart2=t1.b;