FirstMatch strategy

FirstMatch è una strategia di esecuzione per le subquery di tipo semi-join.

L'idea

E' molto simile all'esecuzione delle subquery IN/EXISTS in MySQL 5.x.

Vediamo il solito esempio della ricerca dei Paesi con grandi città:

select * from Country 
where Country.code IN (select City.Country 
                       from City 
                       where City.Population > 1*1000*1000)
      and Country.continent='Europe'

Si supponga che il piano di esecuzione consista nel trovare gli Stati in Europa e poi, per ognuno di essi, controllare se contiene grandi città. Ecco la normale esecuzione della inner join:

Siccome la Germania ha due grandi città (in questo diagramma), sarà inserita due volte nell'output della query. Questo comportamento non è corretto, perché SELECT ... FROM Country non dovrebbe ripetere lo stesso record più volte. La strategia FirstMatch evita di creare dei duplicati tagliando corta l'esecuzione appena trova la prima corrispondenza genuina:

Si noti che tale scorciatoia deve avvenire dopo l'applicazione di "Using where". Sarebbe stato errato farlo dopo aver trovato Trier.

FirstMatch in azione

L'output di EXPLAIN per la query sopra riportata assomiglia al seguente:

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) nel campo Extra significa che appena è stato prodotta una combinazione di record, abbrevia l'esecuzione e torna alla tabella Country.

Il piano di esecuzione di FirstMatch è molto simile a quello che si avrebbe 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)

Questi due piani in particolare impiegano lo stesso tempo.

Differenze tra FirstMatch e IN->EXISTS

L'idea generale che sottende la strategia FirstMatch è la stessa che sta dietro la trasformazione IN->EXISTS, tuttavia FirstMatch presenta diversi vantaggi:

• Equality propagation works across semi-join bounds, but not subquery bounds. Therefore, converting a subquery to semi-join and using FirstMatch can still give a better execution plan. (TODO example)

• There is only one way to apply the IN->EXISTS strategy and MySQL will do it unconditionally. With FirstMatch, the optimizer can make a choice between whether it should run the FirstMatch strategy as soon as all tables used in the subquery are in the join prefix, or at some later point in time. (TODO: example)

FirstMatch factsheet

• The FirstMatch strategy works by executing the subquery and short-cutting its execution as soon as the first match is found.
• This means, subquery tables must be after all of the parent select's tables that are referred from the subquery predicate.
• EXPLAIN shows FirstMatch as "FirstMatch(tableN)".
• The strategy can handle correlated subqueries.
• But it cannot be applied if the subquery has meaningful GROUP BY and/or aggregate functions.
• Use of the FirstMatch strategy is controlled with the firstmatch=on|off flag in @@optimizer_switch.

See also

• Semi-join subquery optimizations

In-depth material:

• WL#3750: initial specification for FirstMatch