MySQL Subquery Flattening into Semi-Joins

This article explains how the MySQL optimizer enhances database performance by flattening subqueries into semi-joins. You will learn what semi-joins are, the specific criteria MySQL uses to trigger this optimization, and the five core execution strategies the optimizer employs to execute these queries efficiently.

Understanding Subqueries and Semi-Joins

In relational databases, a subquery is a query nested inside another query. Traditionally, evaluating a subquery for every row of the outer query (correlated execution) is highly inefficient.

To optimize this, the MySQL optimizer attempts to “flatten” eligible subqueries into semi-joins. A semi-join is a specialized join operation that returns rows from an outer table if and only if there is at least one matching row in an inner table. Unlike a standard inner join, a semi-join stops searching the inner table as soon as it finds the first match for a given outer row, preventing duplicate rows in the final result set.

Eligibility Criteria for Semi-Join Transformation

The MySQL optimizer does not flatten all subqueries. To qualify for a semi-join transformation, a subquery must meet the following conditions:

• Syntax: It must be an IN, = ANY, or EXISTS subquery.
• Location: It must appear at the top level of the WHERE or ON clause, optionally combined with other conditions using AND.
• Structure: It must be a simple SELECT query. It cannot contain UNION operations, GROUP BY or HAVING clauses, or aggregate functions.
• Implicit predicates: It must not contain a LIMIT clause.

The Five Semi-Join Execution Strategies

Once the optimizer decides to flatten a subquery into a semi-join, it evaluates the cost of five distinct execution strategies to choose the most efficient path.

1. Table Pullout

This is the most efficient strategy. If the subquery’s target column has a PRIMARY KEY or a UNIQUE INDEX, the optimizer knows there can be no duplicate matches. It “pulls” the subquery table out into the outer query, treating the entire operation as a standard inner join.

2. FirstMatch

If table pullout is not possible, the optimizer can use the FirstMatch strategy. The query runs like a nested-loop join. For each row in the outer table, MySQL scans the inner table. The moment it finds the first matching row, it returns the outer row and immediately shortcuts the search for that specific outer row, moving on to the next.

3. LooseScan

This strategy is used when the inner table has an index on the join column. MySQL scans the index of the subquery table, but only reads the first row of each group of duplicate values. It then joins these unique keys with the outer table, avoiding the creation of duplicate results.

4. Materialization

The optimizer executes the subquery once and stores the unique results in a temporary, in-memory table (known as a materialized table) with a temporary index. MySQL then performs an inner join between the outer table and this materialized table. If the temporary table becomes too large, it is written to disk.

5. Duplicate Weedout

In this strategy, the optimizer processes the query as a regular inner join, which may generate duplicate rows from the outer table. To handle these duplicates, MySQL creates a temporary table with a primary key. As rows are generated, their row IDs are inserted into this temporary table. If an ID insertion fails because it already exists, the duplicate row is “weeded out” and discarded.

Checking the Optimizer’s Decision

To see how the MySQL optimizer is handling your subqueries, you can prefix your query with the EXPLAIN command:

EXPLAIN SELECT * FROM orders WHERE customer_id IN (SELECT customer_id FROM VIP_customers);

By reviewing the output—specifically the Extra column or by using EXPLAIN FORMAT=JSON—you can identify if a semi-join was utilized and which of the five strategies (e.g., materialized, FirstMatch, LooseScan) the optimizer chose.