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.