FirstMatch strategy
The idea
FirstMatch is an execution strategy for Semi-join subqueries.
It is very similar to how IN/EXISTS subqueries were executed in MySQL 5.x.
Let's take the usual example of search for countries with big cities:
select * from Country where Country.code IN (select City.Country from City where City.Population > 1*1000*1000) and Country.continent='Europe'
Suppose, our execution plan is to find countries in Europe, and then for each found country check if it has any big cities. Regular inner join execution will look as follows:
Since Germany has got two big cities (in this diagram), it will be put into query output twice. This is not correct, SELECT ... FROM Country
should not produce the same query twice. FirstMatch strategy avoids production of duplicates by short-cutting execution as soon as the first genuine match was found:
Note that short-cutting has to take place after "Using where" has been applied. It would have been wrong to short-cut after we've found Trier.
FirstMatch in action
EXPLAIN for the above query will look as follows:
MariaDB [world]> explain select * from Country where Country.code IN (select City.Country from City where City.Population > 1*1000*1000) and Country.continent='Europe'; +----+-------------+---------+------+--------------------+-----------+---------+--------------------+------+----------------------------------+ | id | select_type | table | type | possible_keys | key | key_len | ref | rows | Extra | +----+-------------+---------+------+--------------------+-----------+---------+--------------------+------+----------------------------------+ | 1 | PRIMARY | Country | ref | PRIMARY,continent | continent | 17 | const | 60 | Using index condition | | 1 | PRIMARY | City | ref | Population,Country | Country | 3 | world.Country.Code | 18 | Using where; FirstMatch(Country) | +----+-------------+---------+------+--------------------+-----------+---------+--------------------+------+----------------------------------+ 2 rows in set (0.00 sec)
FirstMatch(Country)
in in the Extra column means that as soon as we have produced one matching record combination, short-cut the execution and jump back to table Country.
FirstMatch's query plan is very similar to one you would get in MySQL:
MySQL [world]> explain select * from Country where Country.code IN (select City.Country from City where City.Population > 1*1000*1000) and Country.continent='Europe'; +----+--------------------+---------+----------------+--------------------+-----------+---------+-------+------+------------------------------------+ | id | select_type | table | type | possible_keys | key | key_len | ref | rows | Extra | +----+--------------------+---------+----------------+--------------------+-----------+---------+-------+------+------------------------------------+ | 1 | PRIMARY | Country | ref | continent | continent | 17 | const | 60 | Using index condition; Using where | | 2 | DEPENDENT SUBQUERY | City | index_subquery | Population,Country | Country | 3 | func | 18 | Using where | +----+--------------------+---------+----------------+--------------------+-----------+---------+-------+------+------------------------------------+ 2 rows in set (0.01 sec)
and these two query plans will execute in the same time. However, in general, FirstMatch will have an advantage:
- FirstMatch is one of many strategies that can be used to run the subquery, while IN->EXISTS transformation (which you observe in the second EXPLAIN) is the only choice.