A semi-join is a preparation-time transformation that enables multiple execution strategies such as table pullout, duplicate weedout, first match, loose scan, and materializtion. The optimizer uses semi-join strategies to improve subquery execution, as described in this section.
For an inner join between two tables, the join returns a row
from one table as many times as there are matches in the other
table. But for some questions, the only information that
matters is whether there is a match, not the number of
matches. Suppose that there are tables named
list classes in a course curriculum and class rosters
(students enrolled in each class), respectively. To list the
classes that actually have students enrolled, you could use
SELECT class.class_num, class.class_name FROM class INNER JOIN roster WHERE class.class_num = roster.class_num;
However, the result lists each class once for each enrolled student. For the question being asked, this is unnecessary duplication of information.
class_num is a primary key in
class table, duplicate suppression is
possible by using
DISTINCT, but it is inefficient to generate all
matching rows first only to eliminate duplicates later.
The same duplicate-free result can be obtained by using a subquery:
SELECT class_num, class_name FROM class WHERE class_num IN (SELECT class_num FROM roster);
Here, the optimizer can recognize that the
IN clause requires the subquery to return
only one instance of each class number from the
roster table. In this case, the query can
use a semi-join; that
is, an operation that returns only one instance of each row in
class that is matched by rows in
Outer join and inner join syntax is permitted in the outer query specification, and table references may be base tables, derived tables, or view references.
In MySQL, a subquery must satisfy these criteria to be handled as a semi-join:
It must be an
=ANY) subquery that appears at the top level of the
ONclause, possibly as a term in an
ANDexpression. For example:
SELECT ... FROM ot1, ... WHERE (oe1, ...) IN (SELECT ie1, ... FROM it1, ... WHERE ...);
it_represent tables in the outer and inner parts of the query, and
ie_represent expressions that refer to columns in the outer and inner tables.
It must not contain a
It must not be implicitly grouped (it must contain no aggregate functions).
It must not have
STRAIGHT_JOINmodifier must not be present.
The number of outer and inner tables together must be less than the maximum number of tables permitted in a join.
The subquery may be correlated or uncorrelated.
DISTINCT is permitted, as is
ORDER BY is
If a subquery meets the preceding criteria, MySQL converts it to a semi-join and makes a cost-based choice from these strategies:
Convert the subquery to a join, or use table pullout and run the query as an inner join between subquery tables and outer tables. Table pullout pulls a table out from the subquery to the outer query.
Duplicate Weedout: Run the semi-join as if it was a join and remove duplicate records using a temporary table.
FirstMatch: When scanning the inner tables for row combinations and there are multiple instances of a given value group, choose one rather than returning them all. This "shortcuts" scanning and eliminates production of unnecessary rows.
LooseScan: Scan a subquery table using an index that enables a single value to be chosen from each subquery's value group.
Materialize the subquery into an indexed temporary table that is used to perform a join, where the index is used to remove duplicates. The index might also be used later for lookups when joining the temporary table with the outer tables; if not, the table is scanned. For more information about materialization, see Section 184.108.40.206, “Optimizing Subqueries with Materialization”.
Each of these strategies except Duplicate Weedout can be
enabled or disabled using the
semijoinflag controls whether semi-joins are used.
semijoinis enabled, the
materializationflags enable finer control over the permitted semi-join strategies.
These flags are enabled by default. See Section 8.9.2, “Switchable Optimizations”.
EXPLAIN output indicates the
use of semi-join strategies as follows:
Semi-joined tables show up in the outer select. For extended
EXPLAINoutput, the text displayed by a following
SHOW WARNINGSshows the rewritten query, which displays the semi-join structure. (See Section 8.8.3, “Extended EXPLAIN Output Format”.) From this you can get an idea about which tables were pulled out of the semi-join. If a subquery was converted to a semi-join, you will see that the subquery predicate is gone and its tables and
WHEREclause were merged into the outer query join list and
Temporary table use for Duplicate Weedout is indicated by
End temporaryin the
Extracolumn. Tables that were not pulled out and are in the range of
EXPLAINoutput rows covered by
End temporaryhave their
rowidin the temporary table.
Extracolumn indicates join shortcutting.
Extracolumn indicates use of the LooseScan strategy.
nare key part numbers.
Temporary table use for materialization is indicated by rows with a
MATERIALIZEDand rows with a