EXPLAIN returns a row of
information for each table used in the
SELECT statement. It lists the
tables in the output in the order that MySQL would read them
while processing the statement. MySQL resolves all joins using a
nested-loop join method. This means that MySQL reads a row from
the first table, and then finds a matching row in the second
table, the third table, and so on. When all tables are
processed, MySQL outputs the selected columns and backtracks
through the table list until a table is found for which there
are more matching rows. The next row is read from this table and
the process continues with the next table.
MySQL Workbench has a Visual Explain capability that provides a
visual representation of
EXPLAIN output. See
Tutorial: Using Explain to Improve Query Performance.
Each output row from
provides information about one table. Each row contains the
values summarized in
Table 8.1, “EXPLAIN Output Columns”, and described
in more detail following the table. Column names are shown in
the table's first column; the second column provides the
equivalent property name shown in the output when
FORMAT=JSON is used.
Table 8.1 EXPLAIN Output Columns
||The table for the output row|
||The matching partitions|
||The join type|
||The possible indexes to choose|
||The index actually chosen|
||The length of the chosen key|
||The columns compared to the index|
||Estimate of rows to be examined|
||Percentage of rows filtered by table condition|
JSON properties which are
NULL are not
displayed in JSON-formatted
SELECTidentifier. This is the sequential number of the
SELECTwithin the query. The value can be
NULLif the row refers to the union result of other rows. In this case, the
tablecolumn shows a value like
<unionto indicate that the row refers to the union of the rows with
The type of
SELECT, which can be any of those shown in the following table. A JSON-formatted
SELECTtype as a property of a
query_block, unless it is
PRIMARY. The JSON names (where applicable) are also shown in the table.
JSON Name Meaning
None Second or later
SELECTstatement in a
Second or later
SELECTstatement in a
UNION, dependent on outer query
Result of a
SELECTin subquery, dependent on outer query
None Derived table
Derived table dependent on another table
A subquery for which the result cannot be cached and must be re-evaluated for each row of the outer query
The second or later select in a
UNIONthat belongs to an uncacheable subquery (see
DEPENDENTtypically signifies the use of a correlated subquery. See Section 220.127.116.11, “Correlated Subqueries”.
DEPENDENT SUBQUERYevaluation differs from
UNCACHEABLE SUBQUERYevaluation. For
DEPENDENT SUBQUERY, the subquery is re-evaluated only once for each set of different values of the variables from its outer context. For
UNCACHEABLE SUBQUERY, the subquery is re-evaluated for each row of the outer context.
When you specify
EXPLAIN, the output has no single property directly equivalent to
query_blockproperty corresponds to a given
SELECT. Properties equivalent to most of the
SELECTsubquery types just shown are available (an example being
MATERIALIZED), and are displayed when appropriate. There are no JSON equivalents for
The name of the table to which the row of output refers. This can also be one of the following values:
<union: The row refers to the union of the rows with
<derived: The row refers to the derived table result for the row with an
N. A derived table may result, for example, from a subquery in the
<subquery: The row refers to the result of a materialized subquery for the row with an
N. See Section 18.104.22.168, “Optimizing Subqueries with Materialization”.
The partitions from which records would be matched by the query. The value is
NULLfor nonpartitioned tables. See Section 23.3.5, “Obtaining Information About Partitions”.
The join type. For descriptions of the different types, see
possible_keyscolumn indicates the indexes from which MySQL can choose to find the rows in this table. Note that this column is totally independent of the order of the tables as displayed in the output from
EXPLAIN. That means that some of the keys in
possible_keysmight not be usable in practice with the generated table order.
If this column is
NULL(or undefined in JSON-formatted output), there are no relevant indexes. In this case, you may be able to improve the performance of your query by examining the
WHEREclause to check whether it refers to some column or columns that would be suitable for indexing. If so, create an appropriate index and check the query with
EXPLAINagain. See Section 13.1.9, “ALTER TABLE Statement”.
To see what indexes a table has, use
SHOW INDEX FROM.
keycolumn indicates the key (index) that MySQL actually decided to use. If MySQL decides to use one of the
possible_keysindexes to look up rows, that index is listed as the key value.
It is possible that
keywill name an index that is not present in the
possible_keysvalue. This can happen if none of the
possible_keysindexes are suitable for looking up rows, but all the columns selected by the query are columns of some other index. That is, the named index covers the selected columns, so although it is not used to determine which rows to retrieve, an index scan is more efficient than a data row scan.
InnoDB, a secondary index might cover the selected columns even if the query also selects the primary key because
InnoDBstores the primary key value with each secondary index. If
NULL, MySQL found no index to use for executing the query more efficiently.
To force MySQL to use or ignore an index listed in the
USE INDEX, or
IGNORE INDEXin your query. See Section 8.9.4, “Index Hints”.
ANALYZE TABLEhelps the optimizer choose better indexes. For
MyISAMtables, myisamchk --analyze does the same. See Section 22.214.171.124, “ANALYZE TABLE Statement”, and Section 7.6, “MyISAM Table Maintenance and Crash Recovery”.
key_lencolumn indicates the length of the key that MySQL decided to use. The value of
key_lenenables you to determine how many parts of a multiple-part key MySQL actually uses. If the
key_lencolumn also says
Due to the key storage format, the key length is one greater for a column that can be
NULLthan for a
refcolumn shows which columns or constants are compared to the index named in the
keycolumn to select rows from the table.
If the value is
func, the value used is the result of some function. To see which function, use
EXPLAINto see the extended
EXPLAINoutput. The function might actually be an operator such as an arithmetic operator.
rowscolumn indicates the number of rows MySQL believes it must examine to execute the query.
InnoDBtables, this number is an estimate, and may not always be exact.
filteredcolumn indicates an estimated percentage of table rows that will be filtered by the table condition. The maximum value is 100, which means no filtering of rows occurred. Values decreasing from 100 indicate increasing amounts of filtering.
rowsshows the estimated number of rows examined and
filteredshows the number of rows that will be joined with the following table. For example, if
rowsis 1000 and
filteredis 50.00 (50%), the number of rows to be joined with the following table is 1000 × 50% = 500.
This column contains additional information about how MySQL resolves the query. For descriptions of the different values, see
There is no single JSON property corresponding to the
Extracolumn; however, values that can occur in this column are exposed as JSON properties, or as the text of the
type column of
EXPLAIN output describes how
tables are joined. In JSON-formatted output, these are found
as values of the
access_type property. The
following list describes the join types, ordered from the best
type to the worst:
The table has only one row (= system table). This is a special case of the
The table has at most one matching row, which is read at the start of the query. Because there is only one row, values from the column in this row can be regarded as constants by the rest of the optimizer.
consttables are very fast because they are read only once.
SELECT * FROM tbl_name WHERE primary_key=1; SELECT * FROM tbl_name WHERE primary_key_part1=1 AND primary_key_part2=2;
One row is read from this table for each combination of rows from the previous tables. Other than the
consttypes, this is the best possible join type. It is used when all parts of an index are used by the join and the index is a
UNIQUE NOT NULLindex.
eq_refcan be used for indexed columns that are compared using the
=operator. The comparison value can be a constant or an expression that uses columns from tables that are read before this table. In the following examples, MySQL can use an
eq_refjoin to process
SELECT * FROM ref_table,other_table WHERE ref_table.key_column=other_table.column; SELECT * FROM ref_table,other_table WHERE ref_table.key_column_part1=other_table.column AND ref_table.key_column_part2=1;
All rows with matching index values are read from this table for each combination of rows from the previous tables.
refis used if the join uses only a leftmost prefix of the key or if the key is not a
UNIQUEindex (in other words, if the join cannot select a single row based on the key value). If the key that is used matches only a few rows, this is a good join type.
SELECT * FROM ref_table WHERE key_column=expr; SELECT * FROM ref_table,other_table WHERE ref_table.key_column=other_table.column; SELECT * FROM ref_table,other_table WHERE ref_table.key_column_part1=other_table.column AND ref_table.key_column_part2=1;
The join is performed using a
This join type is like
ref, but with the addition that MySQL does an extra search for rows that contain
NULLvalues. This join type optimization is used most often in resolving subqueries. In the following examples, MySQL can use a
ref_or_nulljoin to process
SELECT * FROM ref_table WHERE key_column=expr OR key_column IS NULL;
This join type indicates that the Index Merge optimization is used. In this case, the
keycolumn in the output row contains a list of indexes used, and
key_lencontains a list of the longest key parts for the indexes used. For more information, see Section 126.96.36.199, “Index Merge Optimization”.
This type replaces
INsubqueries of the following form:
value IN (SELECT primary_key FROM single_table WHERE some_expr)
unique_subqueryis just an index lookup function that replaces the subquery completely for better efficiency.
This join type is similar to
unique_subquery. It replaces
INsubqueries, but it works for nonunique indexes in subqueries of the following form:
value IN (SELECT key_column FROM single_table WHERE some_expr)
Only rows that are in a given range are retrieved, using an index to select the rows. The
keycolumn in the output row indicates which index is used. The
key_lencontains the longest key part that was used. The
NULLfor this type.
SELECT * FROM tbl_name WHERE key_column = 10; SELECT * FROM tbl_name WHERE key_column BETWEEN 10 and 20; SELECT * FROM tbl_name WHERE key_column IN (10,20,30); SELECT * FROM tbl_name WHERE key_part1 = 10 AND key_part2 IN (10,20,30);
indexjoin type is the same as
ALL, except that the index tree is scanned. This occurs two ways:
If the index is a covering index for the queries and can be used to satisfy all data required from the table, only the index tree is scanned. In this case, the
Using index. An index-only scan usually is faster than
ALLbecause the size of the index usually is smaller than the table data.
A full table scan is performed using reads from the index to look up data rows in index order.
Uses indexdoes not appear in the
MySQL can use this join type when the query uses only columns that are part of a single index.
A full table scan is done for each combination of rows from the previous tables. This is normally not good if the table is the first table not marked
const, and usually very bad in all other cases. Normally, you can avoid
ALLby adding indexes that enable row retrieval from the table based on constant values or column values from earlier tables.
Extra column of
EXPLAIN output contains
additional information about how MySQL resolves the query. The
following list explains the values that can appear in this
column. Each item also indicates for JSON-formatted output
which property displays the
For some of these, there is a specific property. The others
display as the text of the
If you want to make your queries as fast as possible, look out
Extra column values of
Using temporary, or,
EXPLAIN output, for
using_temporary_table properties equal to
Child of '(JSON:
table' pushed join@1
This table is referenced as the child of
tablein a join that can be pushed down to the NDB kernel. Applies only in NDB Cluster, when pushed-down joins are enabled. See the description of the
ndb_join_pushdownserver system variable for more information and examples.
const row not found(JSON property:
For a query such as
SELECT ... FROM, the table was empty.
Deleting all rows(JSON property:
MySQL is looking for distinct values, so it stops searching for more rows for the current row combination after it has found the first matching row.
The semijoin FirstMatch join shortcutting strategy is used for
Full scan on NULL key(JSON property:
This occurs for subquery optimization as a fallback strategy when the optimizer cannot use an index-lookup access method.
Impossible HAVING(JSON property:
HAVINGclause is always false and cannot select any rows.
Impossible WHERE(JSON property:
WHEREclause is always false and cannot select any rows.
Impossible WHERE noticed after reading const tables(JSON property:
The semijoin LooseScan strategy is used.
nare key part numbers.
No matching min/max row(JSON property:
No row satisfies the condition for a query such as
SELECT MIN(...) FROM ... WHERE.
no matching row in const table(JSON property:
For a query with a join, there was an empty table or a table with no rows satisfying a unique index condition.
No matching rows after partition pruning(JSON property:
No tables used(JSON property:
The query has no
FROMclause, or has a
EXPLAINdisplays this value when there is no
SELECTpart. For example, it appears for
EXPLAIN INSERT INTO t VALUES(10)because that is equivalent to
EXPLAIN INSERT INTO t SELECT 10 FROM DUAL.
Not exists(JSON property:
MySQL was able to do a
LEFT JOINoptimization on the query and does not examine more rows in this table for the previous row combination after it finds one row that matches the
LEFT JOINcriteria. Here is an example of the type of query that can be optimized this way:
SELECT * FROM t1 LEFT JOIN t2 ON t1.id=t2.id WHERE t2.id IS NULL;
t2.idis defined as
NOT NULL. In this case, MySQL scans
t1and looks up the rows in
t2using the values of
t1.id. If MySQL finds a matching row in
t2, it knows that
t2.idcan never be
NULL, and does not scan through the rest of the rows in
t2that have the same
idvalue. In other words, for each row in
t1, MySQL needs to do only a single lookup in
t2, regardless of how many rows actually match in
In MySQL 8.0.17 and later, this can also indicate that a
WHEREcondition of the form
NOT IN (or
NOT EXISTS (has been transformed internally into an antijoin. This removes the subquery and brings its tables into the plan for the topmost query, providing improved cost planning. By merging semijoins and antijoins, the optimizer can reorder tables in the execution plan more freely, in some cases resulting in a faster plan.
You can see when an antijoin transformation is performed for a given query by checking the
SHOW WARNINGSfollowing execution of
EXPLAIN, or in the output of
An antijoin is the complement of a semijoin
. The antijoin returns all rows from
table_afor which there is no row in
Plan isn't ready yet(JSON property: none)
This value occurs with
EXPLAIN FOR CONNECTIONwhen the optimizer has not finished creating the execution plan for the statement executing in the named connection. If execution plan output comprises multiple lines, any or all of them could have this
Extravalue, depending on the progress of the optimizer in determining the full execution plan.
Range checked for each record (index map:(JSON property:
MySQL found no good index to use, but found that some of indexes might be used after column values from preceding tables are known. For each row combination in the preceding tables, MySQL checks whether it is possible to use a
index_mergeaccess method to retrieve rows. This is not very fast, but is faster than performing a join with no index at all. The applicability criteria are as described in Section 188.8.131.52, “Range Optimization”, and Section 184.108.40.206, “Index Merge Optimization”, with the exception that all column values for the preceding table are known and considered to be constants.
Indexes are numbered beginning with 1, in the same order as shown by
SHOW INDEXfor the table. The index map value
Nis a bitmask value that indicates which indexes are candidates. For example, a value of
0x19(binary 11001) means that indexes 1, 4, and 5 will be considered.
This indicates that the row applies to the recursive
SELECTpart of a recursive common table expression. See Section 13.2.15, “WITH (Common Table Expressions)”.
Rematerialize (X,...)is displayed in the
EXPLAINrow for table
Xis any lateral derived table whose rematerialization is triggered when a new row of
Tis read. For example:
SELECT ... FROM t, LATERAL (derived table that refers to t) AS dt ...
The content of the derived table is rematerialized to bring it up to date each time a new row of
tis processed by the top query.
This indicates how many directory scans the server performs when processing a query for
INFORMATION_SCHEMAtables, as described in Section 8.2.3, “Optimizing INFORMATION_SCHEMA Queries”. The value of
Ncan be 0, 1, or
Select tables optimized away(JSON property:
The optimizer determined 1) that at most one row should be returned, and 2) that to produce this row, a deterministic set of rows must be read. When the rows to be read can be read during the optimization phase (for example, by reading index rows), there is no need to read any tables during query execution.
The first condition is fulfilled when the query is implicitly grouped (contains an aggregate function but no
GROUP BYclause). The second condition is fulfilled when one row lookup is performed per index used. The number of indexes read determines the number of rows to read.
Consider the following implicitly grouped query:
SELECT MIN(c1), MIN(c2) FROM t1;
MIN(c1)can be retrieved by reading one index row and
MIN(c2)can be retrieved by reading one row from a different index. That is, for each column
c2, there exists an index where the column is the first column of the index. In this case, one row is returned, produced by reading two deterministic rows.
Extravalue does not occur if the rows to read are not deterministic. Consider this query:
SELECT MIN(c2) FROM t1 WHERE c1 <= 10;
(c1, c2)is a covering index. Using this index, all rows with
c1 <= 10must be scanned to find the minimum
c2value. By contrast, consider this query:
SELECT MIN(c2) FROM t1 WHERE c1 = 10;
In this case, the first index row with
c1 = 10contains the minimum
c2value. Only one row must be read to produce the returned row.
For storage engines that maintain an exact row count per table (such as
MyISAM, but not
Extravalue can occur for
COUNT(*)queries for which the
WHEREclause is missing or always true and there is no
GROUP BYclause. (This is an instance of an implicitly grouped query where the storage engine influences whether a deterministic number of rows can be read.)
These values indicate file-opening optimizations that apply to queries for
Skip_open_table: Table files do not need to be opened. The information is already available from the data dictionary.
Open_frm_only: Only the data dictionary need be read for table information.
Open_full_table: Unoptimized information lookup. Table information must be read from the data dictionary and by reading table files.
End temporary(JSON property:
This indicates temporary table use for the semijoin Duplicate Weedout strategy.
unique row not found(JSON property:
For a query such as
SELECT ... FROM, no rows satisfy the condition for a
PRIMARY KEYon the table.
Using filesort(JSON property:
MySQL must do an extra pass to find out how to retrieve the rows in sorted order. The sort is done by going through all rows according to the join type and storing the sort key and pointer to the row for all rows that match the
WHEREclause. The keys then are sorted and the rows are retrieved in sorted order. See Section 220.127.116.11, “ORDER BY Optimization”.
Using index(JSON property:
The column information is retrieved from the table using only information in the index tree without having to do an additional seek to read the actual row. This strategy can be used when the query uses only columns that are part of a single index.
InnoDBtables that have a user-defined clustered index, that index can be used even when
Using indexis absent from the
Extracolumn. This is the case if
Using index condition(JSON property:
Tables are read by accessing index tuples and testing them first to determine whether to read full table rows. In this way, index information is used to defer (“push down”) reading full table rows unless it is necessary. See Section 18.104.22.168, “Index Condition Pushdown Optimization”.
Using index for group-by(JSON property:
Similar to the
Using indextable access method,
Using index for group-byindicates that MySQL found an index that can be used to retrieve all columns of a
DISTINCTquery without any extra disk access to the actual table. Additionally, the index is used in the most efficient way so that for each group, only a few index entries are read. For details, see Section 22.214.171.124, “GROUP BY Optimization”.
Using index for skip scan(JSON property:
Indicates that the Skip Scan access method is used. See Skip Scan Range Access Method.
Using join buffer (Block Nested Loop),
Using join buffer (Batched Key Access)(JSON property:
Tables from earlier joins are read in portions into the join buffer, and then their rows are used from the buffer to perform the join with the current table.
(Block Nested Loop)indicates use of the Block Nested-Loop algorithm and
(Batched Key Access)indicates use of the Batched Key Access algorithm. That is, the keys from the table on the preceding line of the
EXPLAINoutput will be buffered, and the matching rows will be fetched in batches from the table represented by the line in which
Using join bufferappears.
In JSON-formatted output, the value of
using_join_bufferis always either one of
Block Nested Loopor
Batched Key Access.
Using MRR(JSON property:
Tables are read using the Multi-Range Read optimization strategy. See Section 126.96.36.199, “Multi-Range Read Optimization”.
Using intersect(...)(JSON property:
Using temporary(JSON property:
To resolve the query, MySQL needs to create a temporary table to hold the result. This typically happens if the query contains
ORDER BYclauses that list columns differently.
Using where(JSON property:
WHEREclause is used to restrict which rows to match against the next table or send to the client. Unless you specifically intend to fetch or examine all rows from the table, you may have something wrong in your query if the
Extravalue is not
Using whereand the table join type is
Using wherehas no direct counterpart in JSON-formatted output; the
attached_conditionproperty contains any
Using where with pushed condition(JSON property:
This item applies to
NDBtables only. It means that NDB Cluster is using the Condition Pushdown optimization to improve the efficiency of a direct comparison between a nonindexed column and a constant. In such cases, the condition is “pushed down” to the cluster's data nodes and is evaluated on all data nodes simultaneously. This eliminates the need to send nonmatching rows over the network, and can speed up such queries by a factor of 5 to 10 times over cases where Condition Pushdown could be but is not used. For more information, see Section 188.8.131.52, “Engine Condition Pushdown Optimization”.
Zero limit(JSON property:
The query had a
LIMIT 0clause and cannot select any rows.
You can get a good indication of how good a join is by taking
the product of the values in the
column of the
This should tell you roughly how many rows MySQL must examine
to execute the query. If you restrict queries with the
variable, this row product also is used to determine which
statements to execute and which to abort. See
Section 5.1.1, “Configuring the Server”.
The following example shows how a multiple-table join can be
optimized progressively based on the information provided by
EXPLAIN SELECT tt.TicketNumber, tt.TimeIn, tt.ProjectReference, tt.EstimatedShipDate, tt.ActualShipDate, tt.ClientID, tt.ServiceCodes, tt.RepetitiveID, tt.CurrentProcess, tt.CurrentDPPerson, tt.RecordVolume, tt.DPPrinted, et.COUNTRY, et_1.COUNTRY, do.CUSTNAME FROM tt, et, et AS et_1, do WHERE tt.SubmitTime IS NULL AND tt.ActualPC = et.EMPLOYID AND tt.AssignedPC = et_1.EMPLOYID AND tt.ClientID = do.CUSTNMBR;
For this example, make the following assumptions:
The columns being compared have been declared as follows.
Table Column Data Type
The tables have the following indexes.
tt.ActualPCvalues are not evenly distributed.
Initially, before any optimizations have been performed, the
EXPLAIN statement produces the
table type possible_keys key key_len ref rows Extra et ALL PRIMARY NULL NULL NULL 74 do ALL PRIMARY NULL NULL NULL 2135 et_1 ALL PRIMARY NULL NULL NULL 74 tt ALL AssignedPC, NULL NULL NULL 3872 ClientID, ActualPC Range checked for each record (index map: 0x23)
ALL for each table, this
output indicates that MySQL is generating a Cartesian product
of all the tables; that is, every combination of rows. This
takes quite a long time, because the product of the number of
rows in each table must be examined. For the case at hand,
this product is 74 × 2135 × 74 × 3872 =
45,268,558,720 rows. If the tables were bigger, you can only
imagine how long it would take.
One problem here is that MySQL can use indexes on columns more
efficiently if they are declared as the same type and size. In
CHAR are considered the same if
they are declared as the same size.
tt.ActualPC is declared as
CHAR(15), so there is a length mismatch.
To fix this disparity between column lengths, use
ALTER TABLE to lengthen
ActualPC from 10 characters to 15
mysql> ALTER TABLE tt MODIFY ActualPC VARCHAR(15);
et.EMPLOYID are both
VARCHAR(15). Executing the
EXPLAIN statement again
produces this result:
table type possible_keys key key_len ref rows Extra tt ALL AssignedPC, NULL NULL NULL 3872 Using ClientID, where ActualPC do ALL PRIMARY NULL NULL NULL 2135 Range checked for each record (index map: 0x1) et_1 ALL PRIMARY NULL NULL NULL 74 Range checked for each record (index map: 0x1) et eq_ref PRIMARY PRIMARY 15 tt.ActualPC 1
This is not perfect, but is much better: The product of the
rows values is less by a factor of 74. This
version executes in a couple of seconds.
A second alteration can be made to eliminate the column length
mismatches for the
mysql> ALTER TABLE tt MODIFY AssignedPC VARCHAR(15), MODIFY ClientID VARCHAR(15);
After that modification,
EXPLAIN produces the output
table type possible_keys key key_len ref rows Extra et ALL PRIMARY NULL NULL NULL 74 tt ref AssignedPC, ActualPC 15 et.EMPLOYID 52 Using ClientID, where ActualPC et_1 eq_ref PRIMARY PRIMARY 15 tt.AssignedPC 1 do eq_ref PRIMARY PRIMARY 15 tt.ClientID 1
At this point, the query is optimized almost as well as
possible. The remaining problem is that, by default, MySQL
assumes that values in the
column are evenly distributed, and that is not the case for
tt table. Fortunately, it is easy to
tell MySQL to analyze the key distribution:
mysql> ANALYZE TABLE tt;
With the additional index information, the join is perfect and
EXPLAIN produces this result:
table type possible_keys key key_len ref rows Extra tt ALL AssignedPC NULL NULL NULL 3872 Using ClientID, where ActualPC et eq_ref PRIMARY PRIMARY 15 tt.ActualPC 1 et_1 eq_ref PRIMARY PRIMARY 15 tt.AssignedPC 1 do eq_ref PRIMARY PRIMARY 15 tt.ClientID 1
rows column in the output from
EXPLAIN is an educated guess
from the MySQL join optimizer. Check whether the numbers are
even close to the truth by comparing the
rows product with the actual number of rows
that the query returns. If the numbers are quite different,
you might get better performance by using
STRAIGHT_JOIN in your
SELECT statement and trying to
list the tables in a different order in the
FROM clause. (However,
STRAIGHT_JOIN may prevent indexes from
being used because it disables semijoin transformations. See
Section 184.108.40.206, “Optimizing IN and EXISTS Subquery Predicates with Semijoin