How MySQL Optimizer Decides Table Join Order

This article explains how the MySQL Cost-Based Optimizer (CBO) determines the most efficient execution order when joining multiple tables. We will explore how the optimizer evaluates execution plans, utilizes table statistics, estimates query costs, and applies search algorithms to balance optimization time with query performance.

1. The Cost-Based Optimizer (CBO)

MySQL uses a Cost-Based Optimizer to determine the execution plan for a query. Before executing a query, the optimizer calculates the estimated “cost” of various execution paths and selects the one with the lowest cost.

The cost is a numeric value representing the estimated effort required to execute the query, measured primarily in: * Disk I/O operations: The cost of reading data pages from disk into memory. * CPU cycles: The cost of processing rows, evaluating conditions, sorting, and performing join operations in memory.

To calculate these costs, the optimizer relies on engine statistics, which include table cardinality (the estimated number of unique values), the number of rows in each table, and index distribution.

2. Managing the Search Space

When joining \(N\) tables, the theoretical number of possible join orders is \(N!\) (N-factorial). For example, joining 10 tables results in over 3.6 million possible combinations. Evaluating every combination would take longer than executing the query itself.

To prevent this bottleneck, MySQL uses two primary strategies:

3. Key Factors Influencing Join Order

During the evaluation process, the optimizer uses several heuristics and rules to prioritize certain tables over others:

Row Count and Cardinality

The optimizer generally prefers to start with the table that will return the fewest rows after applying WHERE clause filters. By starting with a smaller intermediate result set (the “outer table” in a nested-loop join), MySQL minimizes the number of lookups required for subsequent tables (the “inner tables”).

Index Availability

If a join column is indexed, the optimizer is highly likely to place that table later in the join order. This allows MySQL to perform fast index lookups (ref or eq_ref access types) instead of expensive full table scans for each row of the outer table.

Join Types

MySQL evaluates the types of joins requested (e.g., INNER JOIN, LEFT JOIN, RIGHT JOIN): * Inner Joins: The optimizer has complete freedom to reorder the tables to find the most efficient path. * Outer Joins (LEFT/RIGHT): These joins introduce logical dependencies. A LEFT JOIN forces the left table to be read before the right table unless the optimizer can simplify the outer join into an inner join (which it does if the WHERE clause filters out NULL values from the inner table).

4. How to Influence the Join Order

If the optimizer makes a suboptimal choice due to outdated statistics or complex queries, developers can manually influence the join order using the following tools: