How MySQL Optimizer Uses Cost-Based Models

The MySQL query optimizer plays a crucial role in database performance by determining the most efficient way to execute a SQL query. By employing a Cost-Based Optimizer (CBO) model, MySQL evaluates various potential execution plans and assigns a numeric cost to each based on estimated system resource usage, such as I/O operations and CPU cycles. This article explains how the MySQL optimizer calculates these costs, utilizes system statistics, and ultimately selects the lowest-cost execution plan for query execution.

Understanding the Cost-Based Optimizer (CBO)

At its core, the MySQL optimizer is cost-based. This means its primary goal is to find the query execution plan that has the lowest total cost. The “cost” does not represent actual execution time in seconds, but rather a relative unit of measurement that represents the estimated effort required by the database engine to perform the operations.

To determine this cost, the optimizer calculates two primary types of expenses: * I/O Cost: The effort required to read and write data from disk or buffer memory. * CPU Cost: The effort required to process rows in memory, evaluate filtering conditions (WHERE clauses), perform sorting operations, and execute joins.

The Cost Model Tables

MySQL stores the constants used to calculate these costs in system tables within the mysql schema. These tables allow users to inspect and even customize how the optimizer weighs different database operations:

  1. mysql.server_cost: Contains cost constants for general server operations. This includes activities like compiling temporary tables, executing row comparisons, and creating memory or disk-based internal tables.
  2. mysql.engine_cost: Contains cost constants for storage-engine-specific operations, such as reading a page from the buffer pool versus reading a page from a physical disk.

By default, reading a page from disk is assigned a higher cost than reading a page from the memory buffer, which naturally guides the optimizer to choose execution plans that maximize memory utilization and minimize disk access.

The Role of Database Statistics

The optimizer cannot calculate accurate costs without knowing the structure and distribution of your data. To estimate costs, it relies heavily on InnoDB engine statistics, which are automatically gathered and updated. These statistics include: * Table Cardinality: The estimated number of unique values in an index. High cardinality indicates a highly selective index, which is cheaper to search. * Table Size: The number of pages and rows in a table. * Index Divisibility: How data is distributed across the B-tree structure of the index.

If these statistics are outdated or inaccurate, the optimizer may miscalculate costs and choose an inefficient execution plan. Running the ANALYZE TABLE command forces MySQL to update these statistics, helping the optimizer make better-informed decisions.

How the Optimizer Evaluates and Chooses a Plan

When a query is executed, the optimizer goes through several distinct phases to choose the final plan:

1. Generating Alternative Plans

The optimizer identifies all possible ways to execute the query. This includes scanning the table sequentially (a full table scan), using various indexes, or joining tables in different sequences.

2. Pruning the Search Space

For complex queries involving multiple tables, the number of possible join orders grows exponentially. To prevent the optimization process from taking longer than the query execution itself, MySQL uses a greedy search algorithm to prune high-cost paths early, focusing only on the most promising execution combinations.

3. Calculating the Total Cost

For each viable plan, the optimizer calculates the cumulative CPU and I/O costs. For example, if evaluating an index lookup versus a full table scan, it compares: * Full Table Scan Cost: (Number of data pages * Page read cost) + (Number of rows * Row evaluation cost). * Index Lookup Cost: (Number of index pages read * Page read cost) + (Estimated matching rows * Row evaluation cost) + (Data page lookups * Page read cost).

4. Selecting the Lowest Cost Plan

The optimizer compares the final numbers for each generated plan and selects the one with the lowest overall numeric cost. This chosen path is then compiled into the final execution plan.

Viewing Optimizer Costs

Database administrators can inspect the costs calculated by the optimizer using the EXPLAIN statement. By running EXPLAIN FORMAT=JSON SELECT ..., MySQL will output a detailed JSON object showing the calculated query_cost, the read_cost, and the eval_cost for each step of the query. For even deeper diagnostics, the optimizer_trace feature can be enabled to view every single plan the optimizer considered and why specific plans were rejected due to higher costs.