La strategia FirstMatch

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:

• La propagazione dell'uguaglianza funziona attraverso i limiti delle semi-join , ma non quelli delle subquery. Pertanto si può ottenere un piano di esecuzione ancora migliore convertendo la subquery in una semi-join e usando FirstMatch.

• C'è solo un modo per applicare la strategia IN->EXISTS e MySQL lo fa incondizionatamente. Con FirstMatch, l'ottimizzatore può scegliere se eseguire la strategia FirstMatch appena tutte le tabelle utilizzate dalla subquery sono nel prefisso della join, oppure più tardi. (TODO: esempio)

Riassunto

• La strategia FirstMatch esegue la subquery e taglia l'esecuzione appena trova una corrispondenza.
• Ciò significa che le tabelle della subquery devono essere dopo tutte quelle della SELECT madre che vengono nominate nella subquery.
• EXPLAIN mostra FirstMatch come "FirstMatch(tabellaN)".
• Questa strategia è in grado di gestire le subquery correlate.
• Non può però essere usata se la subquery ha una GROUP BY significativa e/o funzioni aggreganti.
• L'uso della strategia FirstMatch si può controllare con il flag firstmatch=on|off in @@optimizer_switch.

Vedi anche

• Ottimizzazioni delle semi-join

Approfondimenti:

• WL#3750: initial specification for FirstMatch